Class FullyRecursiveHashSetBasedGraphVisit

A IVisitStrategy implementation which uses an of System.Int32 to store already visited vertices, while visiting the graph, and performs the visit recursively.

Inheritance
System.Object
DirectionableVisit
FullyRecursiveHashSetBasedGraphVisit
Implements
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 class FullyRecursiveHashSetBasedGraphVisit : DirectionableVisit, IVisitStrategy

Constructors

| Improve this Doc View Source

FullyRecursiveHashSetBasedGraphVisit(Boolean)

Declaration
public FullyRecursiveHashSetBasedGraphVisit(bool directedGraph)
Parameters
Type Name Description
System.Boolean directedGraph

Methods

| Improve this Doc View Source

BreadthFirstSearchFromVertex(IGraph, Int32)

Declaration
public override IEnumerable<int> BreadthFirstSearchFromVertex(IGraph graph, int vertex)
Parameters
Type Name Description
IGraph graph
System.Int32 vertex
Returns
Type Description
IEnumerable<System.Int32>
Overrides
Remarks

ADVANTAGES AND DISADVANTAGES
Implemented fully recursively, so limited by stack depth and usable with graphs of a "reasonable" size.

ALGORITHM
- The algorithm closely resembles DepthFirstSearchFromVertex(IGraph, Int32) with one foundamental difference: the recursive calls to neighbors of each vertex generate which are iterated lazily and in parallel, one element of each at a time, up until all enumerators are done.
- Let's take as an example a graph in which neighbors of vertex 0 are 1 and 2, neighbors of vertex 1 are 3 and 4 and neighbors of vertex 2 are 5 and 4.
- The visit of vertex 0 will first yield the vertex 0 itself.
- It then yields the 1st element of the enumerable of BFS from vertex 1, which is the vertex 1 itself.
- After that, it yields the 1st element of the enumerable of BFS from vertex 2, which is the vertex 2 itself.
- After that, since there are no other neighbors of 0, moves to the 2nd elements of each of the enumerators.
- It yields the 2nd element of the enumerable of BFS from vertex 1, which is the vertex 3.
- It then yields the 2nd element of the enumerable of BFS from vertex 2, which is the vertex 5.
- Etc, until all enumerators are done (i.e. System.Collections.IEnumerator.MoveNext is false.

COMPLEXITY
- Same consideration about complexity as in DepthFirstSearchFromVertex(IGraph, Int32) apply. What is different is just the order of visit, not edges or vertices visited.
- Therefore, Time Complexity is O(v * Ta + e) and Space Complexity is O(v * Sa + e), where v is the number of vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the neighborhood of a given vertex.

| Improve this Doc View Source

BreadthFirstSearchFromVertices(IGraph, IEnumerable<Int32>)

Declaration
public override IEnumerable<int> BreadthFirstSearchFromVertices(IGraph graph, IEnumerable<int> vertices)
Parameters
Type Name Description
IGraph graph
IEnumerable<System.Int32> vertices
Returns
Type Description
IEnumerable<System.Int32>
Overrides
Remarks

The algorithm is very similar to BreadthFirstSearchFromVertex(IGraph, Int32), with the only difference that all vertices in the vertices sequence are visited, in parallel, instead of a single one.
Because the vertices may or may not belong to different connected components, this algorithm returns "-1" as connected component for all visited vertices.
Time Complexity is O(v * Ta + e) and Space Complexity is O(v + e + Sa), exactly as for BreadthFirstSearchFromVertex(IGraph, Int32), since in the worst case the entire graph has to be explored.

| Improve this Doc View Source

ConnectedComponents(IGraph)

Declaration
public override IDictionary<int, int> ConnectedComponents(IGraph graph)
Parameters
Type Name Description
IGraph graph
Returns
Type Description
IDictionary<System.Int32, System.Int32>
Overrides
Remarks

ADVANTAGES AND DISADVANTAGES
Implemented fully recursively, so limited by stack depth and usable with graphs of a "reasonable" size.

ALGORITHM
- The algorithm is a simple variation of DepthFirstSearchOfGraph(IGraph).
- All vertices from 0 to GetNumberOfVertices() - 1 are explored.
- An of already visited vertices is shared across all visits, to ensure that a vertex is not visited twice.
- A current value of the connected component is instantiated at 0 and incremented every time a new connected component is explored, i.e. every time the vertex i, of the top-level iteration, has not been visited yet, meaning that none of the connected components explored so far contains it.
- The resulting mapping between vertex id and connected component value is returned as result.

COMPLEXITY
- The algorithm closely resembles DepthFirstSearchOfGraph(IGraph), with the added complexity of instantiating and populating a of the mapping between vertices and connected component labels.
- Because the implementation used is a , which is hash-based, such additional operations are performed in constant time.
- Therefore the complexity of this method is the same as DepthFirstSearchOfGraph(IGraph): Time Complexity is O(v * Ta + e) and Space Complexity is O(v * Sa + e), where v is the number of vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the neighborhood of a given vertex.

| Improve this Doc View Source

DepthFirstSearchAndConnectedComponentsOfGraph(IGraph)

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

Declaration
protected override 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.
Overrides
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)

Declaration
public override IEnumerable<int> DepthFirstSearchFromVertex(IGraph graph, int vertex)
Parameters
Type Name Description
IGraph graph
System.Int32 vertex
Returns
Type Description
IEnumerable<System.Int32>
Overrides
Remarks

ADVANTAGES AND DISADVANTAGES
Implemented fully recursively, so limited by stack depth and usable with graphs of a "reasonable" size.

ALGORITHM
- A of the ids of already visited vertices is instantiated to an empty set.
- The set of already visited vertices is updated, adding the visited vertex, every time a visit is made.
- The visit starts from the specified start vertex and looks for all the neighboring edges of such vertex (taking into account the direction of the edge or not, depending on the specified parameters).
- Only neighboring edges connecting the start vertex to a vertex not already visited are taken into account.
- However, to reach all relevant vertices, the algorithm may go through all edges of the graph.
- All other vertices are skipped, since those vertices, their neighborhood, neighbors of their neighborhood etc. have already been visited in previous steps of the recursive visit.
- When the recursive visit terminates, all vertices directly or indirectly connected to the start vertex S (i.e. all vertices V for which there is a path of edges e1, e2, ..., en, connecting S to V) will have been visited.
- Vertices which are not connected to S (i.e. for which there is no path), are not included in the resulting sequence of vertices.

COMPLEXITY
- Instantiating and adding items to the set of already visited vertices are constant-time operations.
- The set of already visited vertices ensures that each vertex of the graph is visited at most once.
- The complexity of retrieving the neighborhood of a vertex depends on the implementation of GetAdjacentVerticesAndEdges(Int32, Boolean), thus on the specific IGraph implementation being used.
- Checking whether a neighbor has already been visited is a O(1) operation, because the set used is an .
- Therefore, Time Complexity is O(v * Ta + e) and Space Complexity is O(v * Sa + e), where v is the number of vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the neighborhood of a given vertex.

| Improve this Doc View Source

DepthFirstSearchOfGraph(IGraph)

Declaration
public override IEnumerable<int> DepthFirstSearchOfGraph(IGraph graph)
Parameters
Type Name Description
IGraph graph
Returns
Type Description
IEnumerable<System.Int32>
Overrides
Remarks

ADVANTAGES AND DISADVANTAGES
Implemented fully recursively, so limited by stack depth and usable with graphs of a "reasonable" size.

ALGORITHM
- An of the ids of already visited vertices is instantiated to an empty set.
- Vertices are iterated over, from the first (id = 0), to the last (id = v - 1, where v is the total number of vertices).
- The total number of vertices is retrieved via GetNumberOfVertices().
- If the vertex i has not already been visited (i.e. it appears in the ), it is visited, with the same algorithm it would be visited by DepthFirstSearchFromVertex(IGraph, Int32).
- The order of visit is returned as a sequence of integers.
- The set of already visited vertices is updated, adding the visited vertex, every time a visit is made, and it is shared by all visits of all vertices, whether they are connected to each other or not.
- When the sequence of recursive visits terminates, all vertices of the graph will have been visited.

COMPLEXITY
- Instantiating and adding items to the set of already visited vertices are constant-time operations.
- The set of already visited vertices ensures that each vertex of the graph is visited at most once.
- To reach all vertices, the algorithm goes through all edges of the graph.
- Because each vertex is visited at most once throughout the entire execution, edges are visited at most once, when edge direction is taken into account during the visit, and twice, when it is not.
- The complexity of retrieving the total number of vertices depends on GetNumberOfVertices(). While being specific to the IGraph implementation being used, all implementation provide O(1) runtime for such operation.
- Checking whether a neighbor has already been visited is a O(1) operation, because the set used is an .
- Therefore, Time Complexity is O(v * Ta + e) and Space Complexity is O(v * Sa + e), where v is the number of vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the neighborhood of a given vertex.

COMPLEXITY AND EVENTS
- Event handlers are externally defined and have been considered O(1) in this analysis.
- To include them in the analysis, it should be taken into account that VisitingVertex and VisitedVertex happen once per visited vertex, whereas AlreadyVisitedVertex can happen globally as many times as the number of edges.

Implements

Extension Methods