Class DirectionableVisit

A IVisitStrategy implementation which can perform the visit taking into account or not the direction of the edges of the graph, based on the DirectedGraph property.

Inheritance

System.Object

DirectionableVisit

FullyIterativeHashSetBasedGraphVisit

FullyRecursiveHashSetBasedGraphVisit

Implements

IVisitStrategy

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: MoreStructures.Graphs.Visitor

Assembly: MoreStructures.dll

Syntax

public abstract class DirectionableVisit : IVisitStrategy

Constructors

| Improve this Doc View Source

DirectionableVisit(Boolean)

Declaration

protected DirectionableVisit(bool directedGraph)

Parameters

Type	Name	Description
System.Boolean	directedGraph

Properties

| Improve this Doc View Source

DirectedGraph

Whether the provided IGraph should be considered as directed (i.e. edges should be traversed from start to end) or inderected (i.e. edges should be traversed both from start to end and from end to start).

Declaration

public bool DirectedGraph { get; }

Property Value

Type	Description
System.Boolean

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

public abstract 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

public abstract 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

public virtual 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

DepthFirstSearchAndConnectedComponentsOfGraph(IGraph)

Runs a Depth First Search and returns vertices and related connected components.

Declaration

protected abstract IEnumerable<(int, int)> DepthFirstSearchAndConnectedComponentsOfGraph(IGraph graph)

Parameters

Type	Name	Description
IGraph	graph	The IGraph instance to be explored.

Returns

Type	Description
IEnumerable<System.ValueTuple<System.Int32, System.Int32>>	A sequence of couples of System.Int32, the first being the vertex id and the second being the label of the connected component, the vertex belongs to.

Remarks

Generalizes both DepthFirstSearchOfGraph(IGraph) and ConnectedComponents(IGraph) methods, which have very similar implementations. Check those two methods for further information.

| 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

public abstract 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

public virtual 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.

| Improve this Doc View Source

RaiseAlreadyVisitedVertex(VisitEventArgs)

Invoke the AlreadyVisitedVertex event with the provided args.

Declaration

protected virtual void RaiseAlreadyVisitedVertex(VisitEventArgs args)

Parameters

Type	Name	Description
VisitEventArgs	args	The arguments to be provided, when raising the event.

| Improve this Doc View Source

RaiseVisitedVertex(VisitEventArgs)

Invoke the VisitedVertex event with the provided args.

Declaration

protected virtual void RaiseVisitedVertex(VisitEventArgs args)

Parameters

Type	Name	Description
VisitEventArgs	args	The arguments to be provided, when raising the event.

| Improve this Doc View Source

RaiseVisitingVertex(VisitEventArgs)

Invoke the VisitingVertex event with the provided args.

Declaration

protected virtual void RaiseVisitingVertex(VisitEventArgs args)

Parameters

Type	Name	Description
VisitEventArgs	args	The arguments to be provided, when raising the event.

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

public 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

public 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

public 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.

Implements

IVisitStrategy

Extension Methods

SuffixStructureNodeExtensions.GetAllSuffixesFor<TEdge, TNode>(TNode, TextWithTerminator)