SCGraphTheory.Search 3.0.0

.NET 7.0 .NET Standard 2.0
dotnet add package SCGraphTheory.Search --version 3.0.0
NuGet\Install-Package SCGraphTheory.Search -Version 3.0.0
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package.
<PackageReference Include="SCGraphTheory.Search" Version="3.0.0" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add SCGraphTheory.Search --version 3.0.0
#r "nuget: SCGraphTheory.Search, 3.0.0"
#r directive can be used in F# Interactive and Polyglot Notebooks. Copy this into the interactive tool or source code of the script to reference the package.
// Install SCGraphTheory.Search as a Cake Addin
#addin nuget:?package=SCGraphTheory.Search&version=3.0.0

// Install SCGraphTheory.Search as a Cake Tool
#tool nuget:?package=SCGraphTheory.Search&version=3.0.0


Graph search algorithms that work against any graph type implementing the interfaces defined in the SCGraphTheory.Abstractions package.

Classic search algorithms

The Classic namespace contains (single-source) implementations of the breadth-first, depth-first (including limited and iterative deepening variants), Dijkstra, and A-star search algorithms, all conforming to a common interface - ISearch<TNode,TEdge>. They should be fairly intuitive to use. Here are some example instantiations:

var breadthFirst = new BreadthFirstSearch<MyNodeType, MyEdgeType>(
    source: mySpecificSourceNode,
    isTarget: n => n == mySpecificTargetNode);

var depthFirst = new DepthFirstSearch<MyNodeType, MyEdgeType>(
    source: mySpecificSourceNode,
    isTarget: n => n == mySpecificTargetNode);

var dijkstra = new DijkstraSearch<MyNodeType, MyEdgeType>(
    source: mySpecificSourceNode,
    isTarget: n => n.MyProperty == myDesiredValue,
    getEdgeCost: e => e.MyEdgeCost);

var aStar = new AStarSearch<MyNodeType, MyEdgeType>(
    source: myGraph.MyNodeIndex[0, 0],
    isTarget: n => n.Coords == targetCoords,
    getEdgeCost: e => e.MyEdgeCost,
    getEstimatedCostToTarget: n => EuclideanDistance(n.Coords, targetCoords));

Searches are executed step-by-step via the NextStep() method of the ISearch<TNode,TEdge> interface. This (as opposed to having to execute a search all the way to completion) is to maximise the flexibility with which potentially expensive searches can be executed. A Complete() extension method is defined though; which continuously calls NextStep() until the search completes.


  • All search algorithms expose details of visited edges via the Visited property. This does add a little to the memory footprint that is overhead if you don't need this information. The extra is relatively small though, since all of the algorithms require a quick way to determine if a node has already been visited anyway. Using a Dictionary (as opposed to a HashSet) for this is a relatively minor addition. If it comes to it, NextStep() could be modified to return the explored edge, so that recording the search tree could be a higher level concern. No current plans to do this, though.

Local search algorithms

The Local namespace contains implementations of the (steepest-ascent) hill climb and simulated annealing search algorithms. They should also be fairly intuitive to use. Here are some example instantiations:

var hillClimb = new HillClimb<MyNodeType, MyEdgeType>(
    source: mySpecificSourceNode,
    getUtility: n => n.MyUtilityProp);

var simulatedAnnealing = new SimulatedAnnealing<MyNodeType, MyEdgeType>(
    source: mySpecificSourceNode,
    getUtility: n => n.MyUtilityProp,
    annealingSchedule: t => Math.Max(1 - (.01f * t), 0));

Like the Classic searches, the local searches are executed step-by-step via a NextStep() method. This (as opposed to having to execute a search all the way to completion) is to maximise the flexibility with which potentially expensive searches can be executed.

And-or search algorithms [v2.3 onwards]

The AndOr namespace contains implementations (well, just a DFS for now) of search algorithms for "and-or" graphs. The overall approach taken here is that a delegate is used to identify edges that actually represent a set of conjoined "and" edges (all of which must ultimately lead to a target node in a search solution). The actual edges are represented by the outbound edges of the node that the collection edge connects to. Another way of looking at this is that we divide our graph into "or" nodes and "and" nodes. See the Specialized.AndOr namespace in the test graphs project for a couple of and-or graph examples.

var andOrDFS = new AndOrDFS<MyBaseNodeType, MyBaseEdgeType>(
    source: mySourceNode,
    isTarget: IsTargetNode,
    isAndEdgeCollection: e => e is MyConjoinedEdgeCollectionType);
Product Compatible and additional computed target framework versions.
.NET net5.0 was computed.  net5.0-windows was computed.  net6.0 was computed.  net6.0-android was computed.  net6.0-ios was computed.  net6.0-maccatalyst was computed.  net6.0-macos was computed.  net6.0-tvos was computed.  net6.0-windows was computed.  net7.0 is compatible.  net7.0-android was computed.  net7.0-ios was computed.  net7.0-maccatalyst was computed.  net7.0-macos was computed.  net7.0-tvos was computed.  net7.0-windows was computed. 
.NET Core netcoreapp2.0 was computed.  netcoreapp2.1 was computed.  netcoreapp2.2 was computed.  netcoreapp3.0 was computed.  netcoreapp3.1 was computed. 
.NET Standard netstandard2.0 is compatible.  netstandard2.1 was computed. 
.NET Framework net461 was computed.  net462 was computed.  net463 was computed.  net47 was computed.  net471 was computed.  net472 was computed.  net48 was computed.  net481 was computed. 
MonoAndroid monoandroid was computed. 
MonoMac monomac was computed. 
MonoTouch monotouch was computed. 
Tizen tizen40 was computed.  tizen60 was computed. 
Xamarin.iOS xamarinios was computed. 
Xamarin.Mac xamarinmac was computed. 
Xamarin.TVOS xamarintvos was computed. 
Xamarin.WatchOS xamarinwatchos was computed. 
Compatible target framework(s)
Additional computed target framework(s)
Learn more about Target Frameworks and .NET Standard.

NuGet packages (1)

Showing the top 1 NuGet packages that depend on SCGraphTheory.Search:

Package Downloads

Basic but fully functional and documented classical planning implementations. Somewhat influenced by "Artificial Intelligence: A Modern Approach" (Russell & Norvig). Includes state- and goal-space search as well as a GraphPlan implementation.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
3.0.0 458 1/3/2023
3.0.0-pre.6 264 1/2/2023
3.0.0-pre.5 139 12/9/2022
3.0.0-pre.4 55 12/9/2022
3.0.0-pre.3 86 11/11/2022
3.0.0-pre.2 71 11/11/2022
3.0.0-pre.1 69 11/10/2022
2.5.0 360 10/14/2022
2.4.0 431 10/9/2022
2.4.0-pre.1 71 10/9/2022
2.3.3 311 10/8/2022
2.3.2 776 9/16/2022
2.3.1 326 7/30/2022
2.3.0 346 7/13/2022
2.2.2 272 9/5/2021
2.2.1 245 5/25/2021
2.2.0 290 4/18/2021
2.1.0 281 4/8/2021
2.0.1 318 3/20/2021
2.0.0 232 3/20/2021
1.0.1 434 2/29/2020
1.0.0 386 2/29/2020
1.0.0-pre.2 225 2/29/2020