Install-Package SCGraphTheory.Search -Version 2.3.1
dotnet add package SCGraphTheory.Search --version 2.3.1
<PackageReference Include="SCGraphTheory.Search" Version="2.3.1" />
paket add SCGraphTheory.Search --version 2.3.1
#r "nuget: SCGraphTheory.Search, 2.3.1"
// Install SCGraphTheory.Search as a Cake Addin #addin nuget:?package=SCGraphTheory.Search&version=2.3.1 // Install SCGraphTheory.Search as a Cake Tool #tool nuget:?package=SCGraphTheory.Search&version=2.3.1
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);
|.NET||net5.0 net5.0-windows net6.0 net6.0-android net6.0-ios net6.0-maccatalyst net6.0-macos net6.0-tvos net6.0-windows|
|.NET Core||netcoreapp2.0 netcoreapp2.1 netcoreapp2.2 netcoreapp3.0 netcoreapp3.1|
|.NET Standard||netstandard2.0 netstandard2.1|
|.NET Framework||net461 net462 net463 net47 net471 net472 net48|
- SCGraphTheory.Abstractions (>= 1.0.2)
This package is not used by any NuGet packages.
This package is not used by any popular GitHub repositories.