Class BreadthFirstSearchAlgorithm<TVertex, TEdge>

A breath first search algorithm for directed graphs.

Inheritance
System.Object
AlgorithmBase<IVertexListGraph<TVertex, TEdge>>
RootedAlgorithmBase<TVertex, IVertexListGraph<TVertex, TEdge>>
BreadthFirstSearchAlgorithm<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 BreadthFirstSearchAlgorithm<TVertex, TEdge> : RootedAlgorithmBase<TVertex, IVertexListGraph<TVertex, TEdge>>, IAlgorithm<IVertexListGraph<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

BreadthFirstSearchAlgorithm(IAlgorithmComponent, IVertexListGraph<TVertex, TEdge>, IQueue<TVertex>, IDictionary<TVertex, GraphColor>)

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

Declaration
public BreadthFirstSearchAlgorithm(IAlgorithmComponent host, IVertexListGraph<TVertex, TEdge> visitedGraph, IQueue<TVertex> vertexQueue, IDictionary<TVertex, GraphColor> verticesColors)
Parameters
Type Name Description
IAlgorithmComponent host

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

Graph to visit.
IQueue<TVertex> vertexQueue

Queue of vertices to treat.
System.Collections.Generic.IDictionary<TVertex, GraphColor> verticesColors

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

visitedGraph is null.
System.ArgumentNullException

vertexQueue is null.
System.ArgumentNullException

verticesColors is null.
| Improve this Doc View Source

BreadthFirstSearchAlgorithm(IAlgorithmComponent, IVertexListGraph<TVertex, TEdge>, IQueue<TVertex>, IDictionary<TVertex, GraphColor>, Func<IEnumerable<TEdge>, IEnumerable<TEdge>>)

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

Declaration
public BreadthFirstSearchAlgorithm(IAlgorithmComponent host, IVertexListGraph<TVertex, TEdge> visitedGraph, IQueue<TVertex> vertexQueue, IDictionary<TVertex, GraphColor> verticesColors, Func<IEnumerable<TEdge>, IEnumerable<TEdge>> outEdgesFilter)
Parameters
Type Name Description
IAlgorithmComponent host

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

Graph to visit.
IQueue<TVertex> vertexQueue

Queue of vertices to treat.
System.Collections.Generic.IDictionary<TVertex, GraphColor> verticesColors

Vertices associated to their colors (treatment states).
System.Func<System.Collections.Generic.IEnumerable<TEdge>, System.Collections.Generic.IEnumerable<TEdge>> outEdgesFilter

Function that is used filter out-edges of a vertex.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

vertexQueue is null.
System.ArgumentNullException

verticesColors is null.
System.ArgumentNullException

outEdgesFilter is null.
| Improve this Doc View Source

BreadthFirstSearchAlgorithm(IVertexListGraph<TVertex, TEdge>)

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

Declaration
public BreadthFirstSearchAlgorithm(IVertexListGraph<TVertex, TEdge> visitedGraph)
Parameters
Type Name Description
IVertexListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
| Improve this Doc View Source

BreadthFirstSearchAlgorithm(IVertexListGraph<TVertex, TEdge>, IQueue<TVertex>, IDictionary<TVertex, GraphColor>)

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

Declaration
public BreadthFirstSearchAlgorithm(IVertexListGraph<TVertex, TEdge> visitedGraph, IQueue<TVertex> vertexQueue, IDictionary<TVertex, GraphColor> verticesColors)
Parameters
Type Name Description
IVertexListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
IQueue<TVertex> vertexQueue

Queue of vertices to treat.
System.Collections.Generic.IDictionary<TVertex, GraphColor> verticesColors

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

visitedGraph is null.
System.ArgumentNullException

vertexQueue is null.
System.ArgumentNullException

verticesColors is null.

Properties

| Improve this Doc View Source

OutEdgesFilter

Filter of edges.

Declaration
public Func<IEnumerable<TEdge>, IEnumerable<TEdge>> OutEdgesFilter { get; }
Property Value
Type Description
System.Func<System.Collections.Generic.IEnumerable<TEdge>, System.Collections.Generic.IEnumerable<TEdge>>
| 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.IVertexListGraph<TVertex, TEdge>>.Initialize()
| Improve this Doc View Source

InternalCompute()

Algorithm compute step.

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

Events

| Improve this Doc View Source

BlackTarget

Fired when the target vertex of an out-edge from the currently treated vertex is marked as black.

Declaration
public event EdgeAction<TVertex, TEdge> BlackTarget
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

ExamineVertex

Fired when a vertex is going to be analyzed.

Declaration
public event VertexAction<TVertex> ExamineVertex
Event Type
Type Description
VertexAction<TVertex>
| 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

GrayTarget

Fired when the target vertex of an out-edge from the currently treated vertex is marked as gray.

Declaration
public event EdgeAction<TVertex, TEdge> GrayTarget
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

NonTreeEdge

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

Declaration
public event EdgeAction<TVertex, TEdge> NonTreeEdge
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| 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