Class BidirectionalDepthFirstSearchAlgorithm<TVertex, TEdge>

A depth and height first search algorithm for directed graphs.

Inheritance
System.Object
AlgorithmBase<IBidirectionalGraph<TVertex, TEdge>>
RootedAlgorithmBase<TVertex, IBidirectionalGraph<TVertex, TEdge>>
BidirectionalDepthFirstSearchAlgorithm<TVertex, TEdge>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: QuikGraph.Algorithms.Search
Assembly: QuikGraph.dll
Syntax
public sealed class BidirectionalDepthFirstSearchAlgorithm<TVertex, TEdge> : RootedAlgorithmBase<TVertex, IBidirectionalGraph<TVertex, TEdge>>, IAlgorithm<IBidirectionalGraph<TVertex, TEdge>>, IComputation, IAlgorithmComponent, IVertexPredecessorRecorderAlgorithm<TVertex, TEdge>, ITreeBuilderAlgorithm<TVertex, TEdge>, IDistanceRecorderAlgorithm<TVertex>, IVertexColorizerAlgorithm<TVertex> where TEdge : IEdge<TVertex>
Type Parameters
Name Description
TVertex

Vertex type.
TEdge

Edge type.
Remarks

This is a modified version of the classic DFS algorithm where the search is performed both in depth and height.

Constructors

| Improve this Doc View Source

BidirectionalDepthFirstSearchAlgorithm(IAlgorithmComponent, IBidirectionalGraph<TVertex, TEdge>, IDictionary<TVertex, GraphColor>)

Initializes a new instance of the BidirectionalDepthFirstSearchAlgorithm<TVertex, TEdge> class.

Declaration
public BidirectionalDepthFirstSearchAlgorithm(IAlgorithmComponent host, IBidirectionalGraph<TVertex, TEdge> visitedGraph, IDictionary<TVertex, GraphColor> verticesColors)
Parameters
Type Name Description
IAlgorithmComponent host

Host to use if set, otherwise use this reference.
IBidirectionalGraph<TVertex, TEdge> visitedGraph

Graph to visit.
System.Collections.Generic.IDictionary<TVertex, GraphColor> verticesColors

Vertices associated to their colors (treatment states).
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

verticesColors is null.
| Improve this Doc View Source

BidirectionalDepthFirstSearchAlgorithm(IBidirectionalGraph<TVertex, TEdge>)

Initializes a new instance of the BidirectionalDepthFirstSearchAlgorithm<TVertex, TEdge> class.

Declaration
public BidirectionalDepthFirstSearchAlgorithm(IBidirectionalGraph<TVertex, TEdge> visitedGraph)
Parameters
Type Name Description
IBidirectionalGraph<TVertex, TEdge> visitedGraph

Graph to visit.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
| Improve this Doc View Source

BidirectionalDepthFirstSearchAlgorithm(IBidirectionalGraph<TVertex, TEdge>, IDictionary<TVertex, GraphColor>)

Initializes a new instance of the BidirectionalDepthFirstSearchAlgorithm<TVertex, TEdge> class.

Declaration
public BidirectionalDepthFirstSearchAlgorithm(IBidirectionalGraph<TVertex, TEdge> visitedGraph, IDictionary<TVertex, GraphColor> verticesColors)
Parameters
Type Name Description
IBidirectionalGraph<TVertex, TEdge> visitedGraph

Graph to visit.
System.Collections.Generic.IDictionary<TVertex, GraphColor> verticesColors

Vertices associated to their colors (treatment states).
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

verticesColors is null.

Properties

| Improve this Doc View Source

MaxDepth

Gets or sets the maximum exploration depth, from the start vertex.

Declaration
public int MaxDepth { get; set; }
Property Value
Type Description
System.Int32

Maximum exploration depth.
Remarks

Defaulted to int.MaxValue.

Exceptions
Type Condition
System.ArgumentOutOfRangeException

Value is negative or equal to 0.
| Improve this Doc View Source

ProcessAllComponents

In case a root vertex has been set, indicates if the algorithm should walk through graph parts of other components than the root component.

Declaration
public bool ProcessAllComponents { get; set; }
Property Value
Type Description
System.Boolean
| Improve this Doc View Source

VerticesColors

Stores vertices associated to their colors (treatment state).

Declaration
public IDictionary<TVertex, GraphColor> VerticesColors { get; }
Property Value
Type Description
System.Collections.Generic.IDictionary<TVertex, GraphColor>

Methods

| Improve this Doc View Source

GetVertexColor(TVertex)

Gets the GraphColor associated to the given vertex.

Declaration
public GraphColor GetVertexColor(TVertex vertex)
Parameters
Type Name Description
TVertex vertex

The vertex.
Returns
Type Description
GraphColor

The vertex GraphColor.
Exceptions
Type Condition
System.ArgumentNullException

vertex is null.
VertexNotFoundException

vertex has no associated color.
| Improve this Doc View Source

Initialize()

Called on algorithm initialization step.

Declaration
protected override void Initialize()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IBidirectionalGraph<TVertex, TEdge>>.Initialize()
| Improve this Doc View Source

InternalCompute()

Algorithm compute step.

Declaration
protected override void InternalCompute()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IBidirectionalGraph<TVertex, TEdge>>.InternalCompute()

Events

| Improve this Doc View Source

BackEdge

Fired when an edge is going to be treated when coming from a gray vertex.

Declaration
public event EdgeAction<TVertex, TEdge> BackEdge
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| Improve this Doc View Source

DiscoverVertex

Fired when a vertex is discovered and under treatment.

Declaration
public event VertexAction<TVertex> DiscoverVertex
Event Type
Type Description
VertexAction<TVertex>
| Improve this Doc View Source

ExamineEdge

Fired when an edge is going to be analyzed.

Declaration
public event EdgeAction<TVertex, TEdge> ExamineEdge
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| Improve this Doc View Source

FinishVertex

Fired when a vertex is fully treated.

Declaration
public event VertexAction<TVertex> FinishVertex
Event Type
Type Description
VertexAction<TVertex>
| Improve this Doc View Source

ForwardOrCrossEdge

Fired when an edge is going to be treated when coming from a black vertex.

Declaration
public event EdgeAction<TVertex, TEdge> ForwardOrCrossEdge
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| Improve this Doc View Source

InitializeVertex

Fired when a vertex is initialized.

Declaration
public event VertexAction<TVertex> InitializeVertex
Event Type
Type Description
VertexAction<TVertex>
| Improve this Doc View Source

StartVertex

Fired on a starting vertex once before the start of the search from it.

Declaration
public event VertexAction<TVertex> StartVertex
Event Type
Type Description
VertexAction<TVertex>
| Improve this Doc View Source

TreeEdge

Fired when an edge is going to be treated when coming from a white vertex.

Declaration
public event EdgeAction<TVertex, TEdge> TreeEdge
Event Type
Type Description
EdgeAction<TVertex, TEdge>

Implements

Extension Methods