Interface IVisitStrategy

An algorithm exploring IGraph instances.

Namespace: MoreStructures.Graphs.Visitor
Assembly: MoreStructures.dll
Syntax
public interface IVisitStrategy

Methods

| Improve this Doc View Source

BreadthFirstSearchFromVertex(IGraph, Int32)

Runs a partial Breadth First Search of the provided graph, returning the list of vertices which are reachable from the vertex with id vertex, along the edges of the graph, in the order in which they have been explored.

Declaration
IEnumerable<int> BreadthFirstSearchFromVertex(IGraph graph, int vertex)
Parameters
Type Name Description
IGraph graph

The IGraph instance to be explored.
Can be considered directed or undirected, depending on the actual exploration implementation and visit.
System.Int32 vertex

The System.Int32 id identifying the vertex, from which the exploration has to be started. Different starting points will result into different sequences (by items and/or order) of vertices.
Returns
Type Description
IEnumerable<System.Int32>

The sequence of vertices, lazily generated. Neighbors of the same vertex are visited by ascending id.
| Improve this Doc View Source

BreadthFirstSearchFromVertices(IGraph, IEnumerable<Int32>)

Runs a partial Breadth First Search of the provided graph, returning the list of vertices which are reachable from the provided vertices, along the edges of the graph, in the order in which they have been explored.

Declaration
IEnumerable<int> BreadthFirstSearchFromVertices(IGraph graph, IEnumerable<int> vertices)
Parameters
Type Name Description
IGraph graph

The IGraph instance to be explored.
Can be considered directed or undirected, depending on the actual exploration implementation and visit.
IEnumerable<System.Int32> vertices

The sequence of System.Int32 ids identifying the vertices, from which the exploration has to be started. Different starting points will result into different sequences (by items and/or order) of vertices.
Returns
Type Description
IEnumerable<System.Int32>

The sequence of vertices, lazily generated. Neighbors of the same vertex are visited by ascending id.
| Improve this Doc View Source

ConnectedComponents(IGraph)

Explores the provided graph entirely, via a Depth First Search, returning the mapping between the id of each vertex and the label of its connected component.

Declaration
IDictionary<int, int> ConnectedComponents(IGraph graph)
Parameters
Type Name Description
IGraph graph

The IGraph instance to be explored.
Can be considered directed or undirected, depending on the actual exploration implementation and visit.
However, connected components usually make sense for undirected graphs only, since a vertex can reach any other vertex of the same connected component only when edges can be traversed in both directions.
Returns
Type Description
IDictionary<System.Int32, System.Int32>

A dictionary, mapping the id of each vertex of the graph to the label of its connected component, which is a non-negative integer.
| Improve this Doc View Source

DepthFirstSearchFromVertex(IGraph, Int32)

Runs a partial Depth First Search of the the provided graph, returning the list of vertices which are reachable from the vertex with id vertex, along the edges of the graph, in the order in which they have been explored.

Declaration
IEnumerable<int> DepthFirstSearchFromVertex(IGraph graph, int vertex)
Parameters
Type Name Description
IGraph graph

The IGraph instance to be explored. Can be considered directed or undirected, depending on the actual exploration implementation and visit.
System.Int32 vertex

The System.Int32 id identifying the vertex, from which the exploration has to be started. Different starting points will result into different sequences (by items and/or order) of vertices.
Returns
Type Description
IEnumerable<System.Int32>

The sequence of vertices, lazily generated. Neighbors of the same vertex are visited by ascending id.
| Improve this Doc View Source

DepthFirstSearchOfGraph(IGraph)

Explores the provided graph entirely, returning its list of vertices in the order in which they have been explored.

Declaration
IEnumerable<int> DepthFirstSearchOfGraph(IGraph graph)
Parameters
Type Name Description
IGraph graph

The IGraph instance to be explored.
Can be considered directed or undirected, depending on the actual exploration implementation and visit.
Returns
Type Description
IEnumerable<System.Int32>

The sequence of vertices, lazily generated. Neighbors of the same vertex are visited by ascending id.

Events

| Improve this Doc View Source

AlreadyVisitedVertex

Invoked when a node would be about to be visited, but it has been already visited before, and won't be visited again.

Declaration
event EventHandler<VisitEventArgs> AlreadyVisitedVertex
Event Type
Type Description
EventHandler<VisitEventArgs>
Remarks

The event may happen multiple times per vertex per graph visit and can signal the presence of one or more cycles (if the connected component across visits is the same).
Unlike VisitingVertex and VisitedVertex, the event may also not happen at all, for example in trees.
It surely is raised at least once in graphs with cycles. However, cycles are not required for this event to happen: for example, a vertex is encountered multiple times in DAGs.
/ Check VisitEventArgs for the contextual information carried by the event (such as its connected component and previous vertex).

| Improve this Doc View Source

VisitedVertex

Invoked just after a node has been visited, by DepthFirstSearchOfGraph(IGraph), ConnectedComponents(IGraph), DepthFirstSearchFromVertex(IGraph, Int32) or any other method exploring vertices of the graph.

Declaration
event EventHandler<VisitEventArgs> VisitedVertex
Event Type
Type Description
EventHandler<VisitEventArgs>
Remarks

The event happens at most once per vertex per graph visit.
/ Check VisitEventArgs for the contextual information carried by the event.

| Improve this Doc View Source

VisitingVertex

Invoked when a node is about to be visited, by DepthFirstSearchOfGraph(IGraph), ConnectedComponents(IGraph), DepthFirstSearchFromVertex(IGraph, Int32) or any other method exploring vertices of the graph.

Declaration
event EventHandler<VisitEventArgs> VisitingVertex
Event Type
Type Description
EventHandler<VisitEventArgs>
Remarks

The event happens at most once per vertex per graph visit.
/ Check VisitEventArgs for the contextual information carried by the event.

Extension Methods