SCGraphTheory.Search 2.4.0-pre.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);