< Summary

Information
Class: MoreStructures.Graphs.Visitor.FullyIterativeHashSetBasedGraphVisit
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/Visitor/FullyIterativeHashSetBasedGraphVisit.cs
Line coverage
100%
Covered lines: 70
Uncovered lines: 0
Coverable lines: 70
Total lines: 264
Line coverage: 100%
Branch coverage
100%
Covered branches: 22
Total branches: 22
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_Vertex()100%1100%
.ctor(...)100%1100%
DepthFirstSearchAndConnectedComponentsOfGraph()100%8100%
DepthFirstSearchOfGraph(...)100%1100%
ConnectedComponents(...)100%1100%
DepthFirstSearchFromVertex()100%4100%
BreadthFirstSearchFromVertex()100%4100%
BreadthFirstSearchFromVertices()100%6100%
ProcessXifo(...)100%6100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/Visitor/FullyIterativeHashSetBasedGraphVisit.cs

#LineLine coverage
 1using MoreStructures.XifoStructures;
 2
 3namespace MoreStructures.Graphs.Visitor;
 4
 5/// <summary>
 6/// A <see cref="IVisitStrategy"/> implementation which uses an <see cref="HashSet{T}"/> of <see cref="int"/> to store
 7/// already visited vertices, while visiting the graph, and performs the visit iteratively, using a
 8/// <see cref="XStack{T}"/>.
 9/// </summary>
 10public class FullyIterativeHashSetBasedGraphVisit : DirectionableVisit
 11{
 3461612    private record struct XifoFrame(int Vertex, bool Processed, int ConnectedComponent, int? PreviousVertex);
 13
 14    /// <inheritdoc path="//*[not(self::summary)]"/>
 15    /// <summary>
 16    ///     <inheritdoc cref="FullyIterativeHashSetBasedGraphVisit"/>
 17    /// </summary>
 42418    public FullyIterativeHashSetBasedGraphVisit(bool directedGraph) : base(directedGraph)
 42419    {
 42420    }
 21
 22    /// <inheritdoc/>
 23    protected override IEnumerable<(int, int)> DepthFirstSearchAndConnectedComponentsOfGraph(IGraph graph)
 10824    {
 10825        var stack = new XStack<XifoFrame>();
 10826        var alreadyVisited = new HashSet<int>(); // Populated by ProcessXifo
 10827        var numberOfVertices = graph.GetNumberOfVertices();
 28
 10829        var currentConnectedComponent = 0;
 96830        for (var vertex = 0; vertex < numberOfVertices; vertex++)
 38331        {
 32            // Here RaiseAlreadyVisitedVertex should not be triggered, since the vertex is not been checked due to an
 33            // incoming edge from another vertex, but rather to explore vertices in connected components which haven't
 34            // been explored yet.
 38335            if (alreadyVisited.Contains(vertex))
 19936                continue;
 37
 18438            stack.Push(new(vertex, false, currentConnectedComponent, null));
 113939            while (stack.Count > 0)
 96240            {
 176541                var maybeOutputItem = ProcessXifo(graph, stack, alreadyVisited, e => e.OrderByDescending(i => i));
 95542                if (maybeOutputItem >= 0)
 39643                    yield return (maybeOutputItem, currentConnectedComponent);
 95544            }
 45
 17746            currentConnectedComponent++;
 17747        }
 10148    }
 49
 50    /// <inheritdoc path="//*[not(self::remarks)]"/>
 51    /// <remarks>
 52    ///     <para id="advantages">
 53    ///     ADVANTAGES AND DISADVANTAGES
 54    ///     <br/>
 55    ///     <inheritdoc cref="DocFragments" path="/remarks/para[@id='fully-iterative-advantages']"/>
 56    ///     </para>
 57    ///     <para id="algorithm">
 58    ///     ALGORITHM
 59    ///     <br/>
 60    ///     - The total number of vertices of the graph is found via <see cref="IGraph.GetNumberOfVertices"/>.
 61    ///       <br/>
 62    ///     - If such number is v, vertices are identified by integers from 0 to v - 1.
 63    ///       <br/>
 64    ///     - Iterate over all vertices, visiting all other vertices reachable from the current vertex i, in the same
 65    ///       way visit is performed by <see cref="IVisitStrategy.DepthFirstSearchFromVertex(IGraph, int)"/>.
 66    ///       <br/>
 67    ///     - All visits share the same <see cref="HashSet{T}"/> of visited vertices, so that, if a vertex has been
 68    ///       visited before, directly or via another vertex, it's not visited again.
 69    ///       <br/>
 70    ///     - Every time a new vertex is visited, such vertex is yielded into the output sequence.
 71    ///     </para>
 72    ///     <para id="complexity">
 73    ///     COMPLEXITY
 74    ///     <br/>
 75    ///     - The complexity of retrieving the total number of vertices depends on
 76    ///       <see cref="IGraph.GetNumberOfVertices"/>. While being specific to the <see cref="IGraph"/>
 77    ///       implementation being used, all implementation provide O(1) runtime for such operation.
 78    ///       <br/>
 79    ///     - The <see cref="HashSet{T}"/> shared across all visits ensures that each vertex is visited at most once.
 80    ///       <br/>
 81    ///     - Because each vertex is visited at most once throughout the entire execution, edges are visited at most
 82    ///       once, when edge direction is taken into account during the visit, and twice, when it is not.
 83    ///       <br/>
 84    ///     - Thoughout the entire execution, a single vertex in the stack is processed at a time, while the stack can
 85    ///       grow to contain up to e (directed edges) or 2 * e items (undirected edges).
 86    ///       <br/>
 87    ///     - Therefore, Time Complexity is O(v * Ta + e) and Space Complexity is O(v + e + Sa), where v is the number
 88    ///       of vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the
 89    ///       neighborhood of a given vertex.
 90    ///     </para>
 91    ///     <inheritdoc
 92    ///         cref="FullyRecursiveHashSetBasedGraphVisit.DepthFirstSearchOfGraph"
 93    ///         path="/remarks/para[@id='complexity-and-events']"/>
 94    /// </remarks>
 6395    public override IEnumerable<int> DepthFirstSearchOfGraph(IGraph graph) => base.DepthFirstSearchOfGraph(graph);
 96
 97    /// <inheritdoc path="//*[not(self::remarks)]"/>
 98    /// <remarks>
 99    ///     <para id="advantages">
 100    ///     ADVANTAGES AND DISADVANTAGES
 101    ///     <br/>
 102    ///     <inheritdoc cref="DocFragments" path="/remarks/para[@id='fully-iterative-advantages']"/>
 103    ///     </para>
 104    ///     <para id="algorithm">
 105    ///     ALGORITHM
 106    ///     <br/>
 107    ///     - The algorithm is a simple variation of <see cref="DepthFirstSearchOfGraph(IGraph)"/>, with the
 108    ///       differences explained in <see cref="FullyRecursiveHashSetBasedGraphVisit.ConnectedComponents(IGraph)"/>.
 109    ///     </para>
 110    ///     <para id="complexity">
 111    ///     COMPLEXITY
 112    ///     <br/>
 113    ///     - The analysis of complexity is done in
 114    ///       <see cref="FullyRecursiveHashSetBasedGraphVisit.ConnectedComponents(IGraph)"/>.
 115    ///       <br/>
 116    ///     - Time Complexity is O(v * Ta  + e) and Space Complexity is O(v + e + Sa), where v is the number of
 117    ///       vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the
 118    ///       neighborhood of a given vertex.
 119    ///     </para>
 120    ///     <inheritdoc
 121    ///         cref="FullyRecursiveHashSetBasedGraphVisit.DepthFirstSearchOfGraph"
 122    ///         path="/remarks/para[@id='complexity-and-events']"/>///
 123    /// </remarks>
 29124    public override IDictionary<int, int> ConnectedComponents(IGraph graph) => base.ConnectedComponents(graph);
 125
 126    /// <inheritdoc path="//*[not(self::remarks)]"/>
 127    /// <remarks>
 128    ///     <para id="advantages">
 129    ///     ADVANTAGES AND DISADVANTAGES
 130    ///     <br/>
 131    ///     <inheritdoc cref="DocFragments" path="/remarks/para[@id='fully-iterative-advantages']"/>
 132    ///     </para>
 133    ///     <para id="algorithm">
 134    ///     ALGORITHM
 135    ///     <br/>
 136    ///     - The algorithm closely resembles to
 137    ///       <see cref="FullyRecursiveHashSetBasedGraphVisit.DepthFirstSearchFromVertex(IGraph, int)"/>,
 138    ///       the only difference being that the state of the visit is stored into a <see cref="XStack{T}"/>,
 139    ///       instantiated in the heap, rather than in the call stack.
 140    ///       <br/>
 141    ///     - A <see cref="XStack{T}"/> is used, and not a <see cref="XQueue{T}"/>, to preserve the order of visit by
 142    ///       depth, and not by breadth.
 143    ///     </para>
 144    ///     <para id="complexity">
 145    ///     COMPLEXITY
 146    ///     <br/>
 147    ///     - As for <see cref="FullyRecursiveHashSetBasedGraphVisit.DepthFirstSearchFromVertex(IGraph, int)"/>,
 148    ///       Time Complexity is O(v * Ta + e) and Space Complexity is O(v + e + Sa), where v is the number of
 149    ///       vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the
 150    ///       neighborhood of a given vertex.
 151    ///     </para>
 152    ///     <inheritdoc
 153    ///         cref="FullyRecursiveHashSetBasedGraphVisit.DepthFirstSearchOfGraph"
 154    ///         path="/remarks/para[@id='complexity-and-events']"/>
 155    /// </remarks>
 156    public override IEnumerable<int> DepthFirstSearchFromVertex(IGraph graph, int vertex)
 285157    {
 285158        var stack = new XStack<XifoFrame>();
 285159        var alreadyVisited = new HashSet<int>(); // Populated by ProcessXifo
 285160        stack.Push(new(vertex, false, 0, null)); // Single connected component "0"
 1938161        while (stack.Count > 0)
 3021162            if (ProcessXifo(graph, stack, alreadyVisited, e => e.OrderByDescending(i => i)) is var v and >= 0)
 667163                yield return v;
 285164    }
 165
 166    /// <inheritdoc path="//*[not(self::remarks)]"/>
 167    /// <remarks>
 168    ///     <para id="advantages">
 169    ///     ADVANTAGES AND DISADVANTAGES
 170    ///     <br/>
 171    ///     <inheritdoc cref="DocFragments" path="/remarks/para[@id='fully-iterative-advantages']"/>
 172    ///     </para>
 173    ///     <para id="algorithm">
 174    ///     ALGORITHM
 175    ///     <br/>
 176    ///     - The algorithm closely resembles <see cref="DepthFirstSearchFromVertex(IGraph, int)"/>, the only
 177    ///       difference being that a <see cref="XQueue{T}"/> is used, and not a <see cref="XStack{T}"/>, to visit by
 178    ///       breadth, and not by depth.
 179    ///     </para>
 180    ///     <para id="complexity">
 181    ///     COMPLEXITY
 182    ///     <br/>
 183    ///     - Same consideration about complexity as in <see cref="DepthFirstSearchFromVertex(IGraph, int)"/> apply.
 184    ///       What is different is just the order of visit, not edges or vertices visited.
 185    ///       <br/>
 186    ///     - Therefore, Time Complexity is O(v * Ta + e) and Space Complexity is O(v + e + Sa), where v is the number
 187    ///       of vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the
 188    ///       neighborhood of a given vertex.
 189    ///     </para>
 190    ///     <inheritdoc
 191    ///         cref="FullyRecursiveHashSetBasedGraphVisit.DepthFirstSearchOfGraph"
 192    ///         path="/remarks/para[@id='complexity-and-events']"/>
 193    /// </remarks>
 194    public override IEnumerable<int> BreadthFirstSearchFromVertex(IGraph graph, int vertex)
 96195    {
 96196        var queue = new XQueue<XifoFrame>();
 96197        var alreadyVisited = new HashSet<int>(); // Populated by ProcessXifo
 96198        queue.Push(new(vertex, false, 0, null)); // Single connected component "0"
 937199        while (queue.Count > 0)
 1611200            if (ProcessXifo(graph, queue, alreadyVisited, e => e.OrderBy(i => i)) is var v and >= 0)
 314201                yield return v;
 90202    }
 203
 204    /// <inheritdoc path="//*[not(self::remarks)]"/>
 205    /// <remarks>
 206    ///     The algorithm is very similar to <see cref="BreadthFirstSearchFromVertex(IGraph, int)"/>, with the only
 207    ///     difference that all vertices in the <paramref name="vertices"/> sequence are pushed to the queue, instead
 208    ///     of a single one.
 209    ///     <br/>
 210    ///     Because the vertices may or may not belong to different connected components, this algorithm returns "-1"
 211    ///     as connected component for all visited vertices.
 212    ///     <br/>
 213    ///     Time Complexity is O(v * Ta + e) and Space Complexity is O(v + e + Sa), exactly as for
 214    ///     <see cref="BreadthFirstSearchFromVertex(IGraph, int)"/>, since in the worst case the entire graph has to be
 215    ///     explored.
 216    /// </remarks>
 217    public override IEnumerable<int> BreadthFirstSearchFromVertices(IGraph graph, IEnumerable<int> vertices)
 105218    {
 105219        var queue = new XQueue<XifoFrame>();
 105220        var alreadyVisited = new HashSet<int>(); // Populated by ProcessXifo
 533221        foreach (var vertex in vertices)
 109222            queue.Push(new(vertex, false, -1, null));
 951223        while (queue.Count > 0)
 1583224            if (ProcessXifo(graph, queue, alreadyVisited, e => e.OrderBy(i => i)) is var v and >= 0)
 296225                yield return v;
 105226    }
 227
 228    private int ProcessXifo(
 229        IGraph graph, IXifoStructure<XifoFrame> xifo, HashSet<int> alreadyVisited,
 230        Func<IEnumerable<int>, IEnumerable<int>> neighborsProcessor)
 4308231    {
 4308232        var (vertex, processed, connectedComponent, previousVertex) = xifo.Pop();
 233
 4308234        if (processed)
 1644235        {
 1644236            RaiseVisitedVertex(new(vertex, connectedComponent, previousVertex));
 1644237            return -2;
 238        }
 239
 240        // The following check is not done in the foreach loop of neighbors, to respect the order in which
 241        // RaiseAlreadyVisitedVertex events are raised. Triggering a RaiseAlreadyVisitedVertex event directly in the
 242        // loop below would produced an inverted sequence of events in DFS, where a XStack is used and children are
 243        // pushed onto the stack in reversed order.
 2664244        if (alreadyVisited.Contains(vertex))
 991245        {
 991246            RaiseAlreadyVisitedVertex(new(vertex, connectedComponent, previousVertex));
 984247            return -1;
 248        }
 249
 1673250        RaiseVisitingVertex(new(vertex, connectedComponent, previousVertex));
 251
 1673252        alreadyVisited.Add(vertex);
 1673253        var unexploredVertices = graph
 1673254            .GetAdjacentVerticesAndEdges(vertex, DirectedGraph)
 3672255            .Select(neighbor => neighbor.Vertex);
 256
 1673257        xifo.Push(new(vertex, true, connectedComponent, previousVertex));
 258
 9017259        foreach (var unexploredVertex in neighborsProcessor(unexploredVertices))
 1999260            xifo.Push(new(unexploredVertex, false, connectedComponent, vertex));
 261
 1673262        return vertex;
 4301263    }
 264}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_Vertex()
.ctor(System.Boolean)
DepthFirstSearchAndConnectedComponentsOfGraph()
DepthFirstSearchOfGraph(MoreStructures.Graphs.IGraph)
ConnectedComponents(MoreStructures.Graphs.IGraph)
DepthFirstSearchFromVertex()
BreadthFirstSearchFromVertex()
BreadthFirstSearchFromVertices()
ProcessXifo(MoreStructures.Graphs.IGraph,MoreStructures.XifoStructures.IXifoStructure`1<MoreStructures.Graphs.Visitor.FullyIterativeHashSetBasedGraphVisit/XifoFrame>,System.Collections.Generic.HashSet`1<System.Int32>,System.Func`2<System.Collections.Generic.IEnumerable`1<System.Int32>,System.Collections.Generic.IEnumerable`1<System.Int32>>)