Class FullyIterativeHashSetBasedGraphVisit

A IVisitStrategy implementation which uses an of System.Int32 to store already visited vertices, while visiting the graph, and performs the visit iteratively, using a XStack<T>.

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

Constructors

| Improve this Doc View Source

FullyIterativeHashSetBasedGraphVisit(Boolean)

Declaration
public FullyIterativeHashSetBasedGraphVisit(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

ALGORITHM
- The algorithm closely resembles DepthFirstSearchFromVertex(IGraph, Int32), the only difference being that a XQueue<T> is used, and not a XStack<T>, to visit by breadth, and not by depth.

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 + e + Sa), 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 pushed to the queue, 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

ALGORITHM
- The algorithm is a simple variation of DepthFirstSearchOfGraph(IGraph), with the differences explained in ConnectedComponents(IGraph).

COMPLEXITY
- The analysis of complexity is done in ConnectedComponents(IGraph).
- Time Complexity is O(v * Ta + e) and Space Complexity is O(v + e + Sa), 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

ALGORITHM
- The algorithm closely resembles to DepthFirstSearchFromVertex(IGraph, Int32), the only difference being that the state of the visit is stored into a XStack<T>, instantiated in the heap, rather than in the call stack.
- A XStack<T> is used, and not a XQueue<T>, to preserve the order of visit by depth, and not by breadth.

COMPLEXITY
- As for DepthFirstSearchFromVertex(IGraph, Int32), Time Complexity is O(v * Ta + e) and Space Complexity is O(v + e + Sa), 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

ALGORITHM
- The total number of vertices of the graph is found via GetNumberOfVertices().
- If such number is v, vertices are identified by integers from 0 to v - 1.
- Iterate over all vertices, visiting all other vertices reachable from the current vertex i, in the same way visit is performed by DepthFirstSearchFromVertex(IGraph, Int32).
- All visits share the same of visited vertices, so that, if a vertex has been visited before, directly or via another vertex, it's not visited again.
- Every time a new vertex is visited, such vertex is yielded into the output sequence.

COMPLEXITY
- 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.
- The shared across all visits ensures that each vertex is visited at most once.
- 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.
- Thoughout the entire execution, a single vertex in the stack is processed at a time, while the stack can grow to contain up to e (directed edges) or 2 * e items (undirected edges).
- Therefore, Time Complexity is O(v * Ta + e) and Space Complexity is O(v + e + Sa), 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.

Implements

Extension Methods