SCGraphTheory.Search 2.3.1

.NET Standard 2.0
There is a newer version of this package available.
See the version list below for details.
NuGet\Install-Package SCGraphTheory.Search -Version 2.3.1
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.
dotnet add package SCGraphTheory.Search --version 2.3.1
<PackageReference Include="SCGraphTheory.Search" Version="2.3.1" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add SCGraphTheory.Search --version 2.3.1
#r "nuget: SCGraphTheory.Search, 2.3.1"
#r directive can be used in F# Interactive, C# scripting and .NET Interactive. 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=2.3.1

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

SCGraphTheory.Search

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.

Notes:

  • 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 Versions
.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
MonoAndroid monoandroid
MonoMac monomac
MonoTouch monotouch
Tizen tizen40 tizen60
Xamarin.iOS xamarinios
Xamarin.Mac xamarinmac
Xamarin.TVOS xamarintvos
Xamarin.WatchOS xamarinwatchos
Compatible target framework(s)
Additional computed target framework(s)
Learn more about Target Frameworks and .NET Standard.

NuGet packages

This package is not used by any NuGet packages.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
2.3.2 38 9/16/2022
2.3.1 60 7/30/2022
2.3.0 77 7/13/2022
2.2.2 179 9/5/2021
2.2.1 153 5/25/2021
2.2.0 197 4/18/2021
2.1.0 185 4/8/2021
2.0.1 229 3/20/2021
2.0.0 144 3/20/2021
1.0.1 336 2/29/2020
1.0.0 289 2/29/2020
1.0.0-pre.2 198 2/29/2020