dotnet add package SCGraphTheory.Search --version 3.0.0
NuGet\Install-Package SCGraphTheory.Search -Version 3.0.0
<PackageReference Include="SCGraphTheory.Search" Version="3.0.0" />
paket add SCGraphTheory.Search --version 3.0.0
#r "nuget: SCGraphTheory.Search, 3.0.0"
// 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
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
Visitedproperty. 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
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));
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]
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||Versions 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.|
- SCGraphTheory.Abstractions (>= 1.0.2)
- SCGraphTheory.Abstractions (>= 1.0.2)
NuGet packages (1)
Showing the top 1 NuGet packages that depend on SCGraphTheory.Search:
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.
This package is not used by any popular GitHub repositories.