< Summary

Information
Class: MoreStructures.Graphs.Visitor.FullyRecursiveHashSetBasedGraphVisit
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/Visitor/FullyRecursiveHashSetBasedGraphVisit.cs
Line coverage
100%
Covered lines: 118
Uncovered lines: 0
Coverable lines: 118
Total lines: 399
Line coverage: 100%
Branch coverage
100%
Covered branches: 36
Total branches: 36
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
DepthFirstSearchAndConnectedComponentsOfGraph()100%6100%
DepthFirstSearchOfGraph(...)100%1100%
ConnectedComponents(...)100%1100%
DepthFirstSearchFromVertex(...)100%1100%
BreadthFirstSearchFromVertex(...)100%1100%
BreadthFirstSearchFromVertices()100%2100%
RDepthFirstSearchFromVertex()100%6100%
RBreadthFirstSearchFromVertex()100%4100%
EnumerateInParallel()100%10100%
get_Enumerators()100%1100%
get_MoveNextValues()100%1100%
get_MoveNextCount()100%1100%
.ctor(...)100%4100%
CurrentValueDefinedAndAtLevel(...)100%2100%
MoveNext(...)100%2100%

File(s)

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

#LineLine coverage
 1namespace MoreStructures.Graphs.Visitor;
 2
 3/// <summary>
 4/// A <see cref="IVisitStrategy"/> implementation which uses an <see cref="HashSet{T}"/> of <see cref="int"/> to store
 5/// already visited vertices, while visiting the graph, and performs the visit recursively.
 6/// </summary>
 7public class FullyRecursiveHashSetBasedGraphVisit : DirectionableVisit
 8{
 9    /// <inheritdoc path="//*[not(self::summary)]"/>
 10    /// <summary>
 11    ///     <inheritdoc cref="FullyRecursiveHashSetBasedGraphVisit"/>
 12    /// </summary>
 74713    public FullyRecursiveHashSetBasedGraphVisit(bool directedGraph) : base(directedGraph)
 74714    {
 74715    }
 16
 17    /// <inheritdoc/>
 18    protected override IEnumerable<(int, int)> DepthFirstSearchAndConnectedComponentsOfGraph(IGraph graph)
 18019    {
 18020        var alreadyVisited = new HashSet<int>(); // Populated by RExplore
 18021        var numberOfVertices = graph.GetNumberOfVertices();
 22
 18023        var currentConnectedComponent = 0;
 190824        for (var vertex = 0; vertex < numberOfVertices; vertex++)
 77425        {
 26            // Here RaiseAlreadyVisitedVertex should not be triggered, since the vertex is not been checked due to an
 27            // incoming edge from another vertex, but rather to explore vertices in connected components which haven't
 28            // been explored yet.
 77429            if (alreadyVisited.Contains(vertex))
 39930                continue;
 31
 267332            foreach (var outputItem in RDepthFirstSearchFromVertex(
 37533                graph, alreadyVisited, vertex, currentConnectedComponent, null))
 77434                yield return (outputItem, currentConnectedComponent);
 35
 37536            currentConnectedComponent++;
 37537        }
 18038    }
 39
 40    /// <inheritdoc path="//*[not(self::remarks)]"/>
 41    /// <remarks>
 42    ///     <para id="advantages">
 43    ///     ADVANTAGES AND DISADVANTAGES
 44    ///     <br/>
 45    ///     Implemented fully recursively, so limited by stack depth and usable with graphs of a "reasonable" size.
 46    ///     </para>
 47    ///     <para id="algorithm">
 48    ///     ALGORITHM
 49    ///     <br/>
 50    ///     - An <see cref="HashSet{T}"/> of the ids of already visited vertices is instantiated to an empty set.
 51    ///       <br/>
 52    ///     - Vertices are iterated over, from the first (id = 0), to the last (id = v - 1, where v is the total number
 53    ///       of vertices).
 54    ///       <br/>
 55    ///     - The total number of vertices is retrieved via <see cref="IGraph.GetNumberOfVertices"/>.
 56    ///       <br/>
 57    ///     - If the vertex i has not already been visited (i.e. it appears in the <see cref="HashSet{T}"/>), it is
 58    ///       visited, with the same algorithm it would be visited by
 59    ///       <see cref="DepthFirstSearchFromVertex(IGraph, int)"/>.
 60    ///       <br/>
 61    ///     - The order of visit is returned as a sequence of integers.
 62    ///       <br/>
 63    ///     - The set of already visited vertices is updated, adding the visited vertex, every time a visit is made,
 64    ///       and it is shared by all visits of all vertices, whether they are connected to each other or not.
 65    ///       <br/>
 66    ///     - When the sequence of recursive visits terminates, all vertices of the graph will have been visited.
 67    ///     </para>
 68    ///     <para id="complexity">
 69    ///     COMPLEXITY
 70    ///     <br/>
 71    ///     - Instantiating and adding items to the set of already visited vertices are constant-time operations.
 72    ///       <br/>
 73    ///     - The set of already visited vertices ensures that each vertex of the graph is visited at most once.
 74    ///       <br/>
 75    ///     - To reach all vertices, the algorithm goes through all edges of the graph.
 76    ///       <br/>
 77    ///     - Because each vertex is visited at most once throughout the entire execution, edges are visited at most
 78    ///       once, when edge direction is taken into account during the visit, and twice, when it is not.
 79    ///       <br/>
 80    ///     - The complexity of retrieving the total number of vertices depends on
 81    ///       <see cref="IGraph.GetNumberOfVertices"/>. While being specific to the <see cref="IGraph"/>
 82    ///       implementation being used, all implementation provide O(1) runtime for such operation.
 83    ///       <br/>
 84    ///     - Checking whether a neighbor has already been visited is a O(1) operation, because the set used is an
 85    ///       <see cref="HashSet{T}"/>.
 86    ///       <br/>
 87    ///     - Therefore, Time Complexity is O(v * Ta + e) and Space Complexity is O(v * Sa + e), where
 88    ///       v is the number of vertices, e is the number of edges and Ta and Sa are the time and space cost of
 89    ///       retrieving the neighborhood of a given vertex.
 90    ///     </para>
 91    ///     <para id="complexity-and-events">
 92    ///     COMPLEXITY AND EVENTS
 93    ///     <br/>
 94    ///     - Event handlers are externally defined and have been considered O(1) in this analysis.
 95    ///       <br/>
 96    ///     - To include them in the analysis, it should be taken into account that
 97    ///       <see cref="IVisitStrategy.VisitingVertex"/> and <see cref="IVisitStrategy.VisitedVertex"/> happen once
 98    ///       per visited vertex, whereas <see cref="IVisitStrategy.AlreadyVisitedVertex"/> can happen globally as many
 99    ///       times as the number of edges.
 100    ///     </para>
 101    /// </remarks>
 105102    public override IEnumerable<int> DepthFirstSearchOfGraph(IGraph graph) => base.DepthFirstSearchOfGraph(graph);
 103
 104    /// <inheritdoc path="//*[not(self::remarks)]"/>
 105    /// <remarks>
 106    ///     <para id="advantages">
 107    ///     ADVANTAGES AND DISADVANTAGES
 108    ///     <br/>
 109    ///     Implemented fully recursively, so limited by stack depth and usable with graphs of a "reasonable" size.
 110    ///     </para>
 111    ///     <para id="algorithm">
 112    ///     ALGORITHM
 113    ///     <br/>
 114    ///     - The algorithm is a simple variation of <see cref="DepthFirstSearchOfGraph(IGraph)"/>.
 115    ///       <br/>
 116    ///     - All vertices from 0 to <see cref="IGraph.GetNumberOfVertices"/> - 1 are explored.
 117    ///       <br/>
 118    ///     - An <see cref="HashSet{T}"/> of already visited vertices is shared across all visits, to ensure that a
 119    ///       vertex is not visited twice.
 120    ///       <br/>
 121    ///     - A current value of the connected component is instantiated at 0 and incremented every time a new
 122    ///       connected component is explored, i.e. every time the vertex i, of the top-level iteration, has not been
 123    ///       visited yet, meaning that none of the connected components explored so far contains it.
 124    ///       <br/>
 125    ///     - The resulting mapping between vertex id and connected component value is returned as result.
 126    ///     </para>
 127    ///     <para id="complexity">
 128    ///     COMPLEXITY
 129    ///     <br/>
 130    ///     - The algorithm closely resembles <see cref="DepthFirstSearchOfGraph(IGraph)"/>, with the added complexity
 131    ///       of instantiating and populating a <see cref="IDictionary{TKey, TValue}"/> of the mapping between vertices
 132    ///       and connected component labels.
 133    ///       <br/>
 134    ///     - Because the <see cref="IDictionary{TKey, TValue}"/> implementation used is a
 135    ///       <see cref="Dictionary{TKey, TValue}"/>, which is hash-based, such additional operations are performed in
 136    ///       constant time.
 137    ///       <br/>
 138    ///     - Therefore the complexity of this method is the same as <see cref="DepthFirstSearchOfGraph(IGraph)"/>:
 139    ///       Time Complexity is O(v * Ta + e) and Space Complexity is O(v * Sa + e), where v is the number of
 140    ///       vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the
 141    ///       neighborhood of a given vertex.
 142    ///     </para>
 143    ///     <inheritdoc cref="DepthFirstSearchOfGraph" path="/remarks/para[@id='complexity-and-events']"/>
 144    /// </remarks>
 27145    public override IDictionary<int, int> ConnectedComponents(IGraph graph) => base.ConnectedComponents(graph);
 146
 147    /// <inheritdoc path="//*[not(self::remarks)]"/>
 148    /// <remarks>
 149    ///     <para id="advantages">
 150    ///     ADVANTAGES AND DISADVANTAGES
 151    ///     <br/>
 152    ///     Implemented fully recursively, so limited by stack depth and usable with graphs of a "reasonable" size.
 153    ///     </para>
 154    ///     <para id="algorithm">
 155    ///     ALGORITHM
 156    ///     <br/>
 157    ///     - A <see cref="HashSet{T}"/> of the ids of already visited vertices is instantiated to an empty set.
 158    ///       <br/>
 159    ///     - The set of already visited vertices is updated, adding the visited vertex, every time a visit is made.
 160    ///       <br/>
 161    ///     - The visit starts from the specified start vertex and looks for all the neighboring edges of such vertex
 162    ///       (taking into account the direction of the edge or not, depending on the specified parameters).
 163    ///       <br/>
 164    ///     - Only neighboring edges connecting the start vertex to a vertex not already visited are taken into
 165    ///       account.
 166    ///       <br/>
 167    ///     - However, to reach all relevant vertices, the algorithm may go through all edges of the graph.
 168    ///       <br/>
 169    ///     - All other vertices are skipped, since those vertices, their neighborhood, neighbors of their neighborhood
 170    ///       etc. have already been visited in previous steps of the recursive visit.
 171    ///       <br/>
 172    ///     - When the recursive visit terminates, all vertices directly or indirectly connected to the start vertex S
 173    ///       (i.e. all vertices V for which there is a path of edges e1, e2, ..., en, connecting S to V) will
 174    ///       have been visited.
 175    ///       <br/>
 176    ///     - Vertices which are not connected to S (i.e. for which there is no path), are not included in the
 177    ///       resulting sequence of vertices.
 178    ///     </para>
 179    ///     <para id="complexity">
 180    ///     COMPLEXITY
 181    ///     <br/>
 182    ///     - Instantiating and adding items to the set of already visited vertices are constant-time operations.
 183    ///       <br/>
 184    ///     - The set of already visited vertices ensures that each vertex of the graph is visited at most once.
 185    ///       <br/>
 186    ///     - The complexity of retrieving the neighborhood of a vertex depends on the implementation of
 187    ///       <see cref="IGraph.GetAdjacentVerticesAndEdges(int, bool)"/>, thus on the specific <see cref="IGraph"/>
 188    ///       implementation being used.
 189    ///       <br/>
 190    ///     - Checking whether a neighbor has already been visited is a O(1) operation, because the set used is an
 191    ///       <see cref="HashSet{T}"/>.
 192    ///       <br/>
 193    ///     - Therefore, Time Complexity is O(v * Ta + e) and Space Complexity is O(v * Sa + e), where v is the number
 194    ///       of vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the
 195    ///       neighborhood of a given vertex.
 196    ///     </para>
 197    ///     <inheritdoc cref="DepthFirstSearchOfGraph" path="/remarks/para[@id='complexity-and-events']"/>
 198    /// </remarks>
 199    public override IEnumerable<int> DepthFirstSearchFromVertex(IGraph graph, int vertex)
 296200    {
 296201        var alreadyVisited = new HashSet<int>(); // Populated by RExplore
 296202        var lazyExploration = RDepthFirstSearchFromVertex(
 296203            graph, alreadyVisited, vertex, 0, null); // Single connected component "0"
 296204        MoreLinq.MoreEnumerable.Consume(lazyExploration);
 296205        return alreadyVisited;
 296206    }
 207
 208    /// <inheritdoc path="//*[not(self::remarks)]"/>
 209    /// <remarks>
 210    ///     <para id="advantages">
 211    ///     ADVANTAGES AND DISADVANTAGES
 212    ///     <br/>
 213    ///     Implemented fully recursively, so limited by stack depth and usable with graphs of a "reasonable" size.
 214    ///     </para>
 215    ///     <para id="algorithm">
 216    ///     ALGORITHM
 217    ///     <br/>
 218    ///     - The algorithm closely resembles <see cref="DepthFirstSearchFromVertex(IGraph, int)"/> with one
 219    ///       foundamental difference: <b>the recursive calls to neighbors of each vertex generate
 220    ///       <see cref="IEnumerable{T}"/> which are iterated lazily and in parallel, one element of each
 221    ///       <see cref="IEnumerator{T}"/> at a time</b>, up until all enumerators are done.
 222    ///       <br/>
 223    ///     - Let's take as an example a graph in which neighbors of vertex 0 are 1 and 2, neighbors of vertex 1 are 3
 224    ///       and 4 and neighbors of vertex 2 are 5 and 4.
 225    ///       <br/>
 226    ///     - The visit of vertex 0 will first yield the vertex 0 itself.
 227    ///       <br/>
 228    ///     - It then yields the 1st element of the enumerable of BFS from vertex 1, which is the vertex 1 itself.
 229    ///       <br/>
 230    ///     - After that, it yields the 1st element of the enumerable of BFS from vertex 2, which is the vertex 2
 231    ///       itself.
 232    ///       <br/>
 233    ///     - After that, since there are no other neighbors of 0, moves to the 2nd elements of each of the
 234    ///       enumerators.
 235    ///       <br/>
 236    ///     - It yields the 2nd element of the enumerable of BFS from vertex 1, which is the vertex 3.
 237    ///       <br/>
 238    ///     - It then yields the 2nd element of the enumerable of BFS from vertex 2, which is the vertex 5.
 239    ///       <br/>
 240    ///     - Etc, until all enumerators are done (i.e. <see cref="System.Collections.IEnumerator.MoveNext"/> is
 241    ///       <see langword="false"/>.
 242    ///     </para>
 243    ///     <para id="complexity">
 244    ///     COMPLEXITY
 245    ///     <br/>
 246    ///     - Same consideration about complexity as in <see cref="DepthFirstSearchFromVertex(IGraph, int)"/> apply.
 247    ///       What is different is just the order of visit, not edges or vertices visited.
 248    ///       <br/>
 249    ///     - Therefore, Time Complexity is O(v * Ta + e) and Space Complexity is O(v * Sa + e), where v is the number
 250    ///       of vertices, e is the number of edges and Ta and Sa are the time and space cost of retrieving the
 251    ///       neighborhood of a given vertex.
 252    ///     </para>
 253    ///     <inheritdoc cref="DepthFirstSearchOfGraph" path="/remarks/para[@id='complexity-and-events']"/>
 254    /// </remarks>
 255    public override IEnumerable<int> BreadthFirstSearchFromVertex(IGraph graph, int vertex)
 198256    {
 198257        return BreadthFirstSearchFromVertices(graph, new[] { vertex });
 198258    }
 259
 260    /// <inheritdoc path="//*[not(self::remarks)]"/>
 261    /// <remarks>
 262    ///     The algorithm is very similar to <see cref="BreadthFirstSearchFromVertex(IGraph, int)"/>, with the only
 263    ///     difference that all vertices in the <paramref name="vertices"/> sequence are visited, in parallel, instead
 264    ///     of a single one.
 265    ///     <br/>
 266    ///     Because the vertices may or may not belong to different connected components, this algorithm returns "-1"
 267    ///     as connected component for all visited vertices.
 268    ///     <br/>
 269    ///     Time Complexity is O(v * Ta + e) and Space Complexity is O(v + e + Sa), exactly as for
 270    ///     <see cref="BreadthFirstSearchFromVertex(IGraph, int)"/>, since in the worst case the entire graph has to be
 271    ///     explored.
 272    /// </remarks>
 273    public override IEnumerable<int> BreadthFirstSearchFromVertices(IGraph graph, IEnumerable<int> vertices)
 414274    {
 414275        var alreadyVisited = new HashSet<int>();
 414276        var verticesEnumerators = vertices
 414277            .Select(vertex =>
 426278                RBreadthFirstSearchFromVertex(graph, vertex, alreadyVisited, -1, null, 0).GetEnumerator())
 414279            .ToList();
 280
 3516281        foreach (var (descendantVertex, _) in EnumerateInParallel(verticesEnumerators, 0))
 1137282            yield return descendantVertex;
 414283    }
 284
 285    private IEnumerable<int> RDepthFirstSearchFromVertex(
 286        IGraph graph, HashSet<int> alreadyVisited, int vertex, int connectedComponent, int? previousVertex)
 1427287    {
 1427288        RaiseVisitingVertex(new(vertex, connectedComponent, previousVertex));
 289
 1427290        alreadyVisited.Add(vertex);
 1427291        yield return vertex;
 292
 1427293        var neighbors = graph
 1427294            .GetAdjacentVerticesAndEdges(vertex, DirectedGraph)
 3050295            .OrderBy(neighbor => neighbor.Vertex);
 296
 7527297        foreach (var (unexploredVertex, _, _) in neighbors)
 1623298        {
 1623299            if (alreadyVisited.Contains(unexploredVertex))
 867300            {
 867301                RaiseAlreadyVisitedVertex(new(unexploredVertex, connectedComponent, vertex));
 867302                continue;
 303            }
 304
 4492305            foreach (var outputItem in RDepthFirstSearchFromVertex(
 756306                graph, alreadyVisited, unexploredVertex, connectedComponent, vertex))
 1112307                yield return outputItem;
 756308        }
 309
 1427310        RaiseVisitedVertex(new(vertex, connectedComponent, previousVertex));
 1427311    }
 312
 313    private IEnumerable<(int value, int level)> RBreadthFirstSearchFromVertex(
 314        IGraph graph, int vertex, HashSet<int> alreadyVisited, int connectedComponent, int? previousVertex, int level)
 2402315    {
 2402316        if (alreadyVisited.Contains(vertex))
 1265317            yield break;
 318
 1137319        RaiseVisitingVertex(new(vertex, connectedComponent, previousVertex));
 320
 1137321        alreadyVisited.Add(vertex);
 1137322        yield return (vertex, level);
 323
 1137324        var neighborsEnumerators = graph
 1137325            .GetAdjacentVerticesAndEdges(vertex, DirectedGraph)
 1976326            .OrderBy(neighbor => neighbor.Vertex)
 1976327            .Select(neighbor => RBreadthFirstSearchFromVertex(
 1976328                graph, neighbor.Vertex, alreadyVisited, connectedComponent, vertex, level + 1).GetEnumerator())
 1137329            .ToList();
 330
 5283331        foreach (var descendantVertex in EnumerateInParallel(neighborsEnumerators, level + 1))
 936332            yield return descendantVertex;
 333
 1137334        RaiseVisitedVertex(new(vertex, connectedComponent, previousVertex));
 1137335    }
 336
 337    private static IEnumerable<(int value, int level)> EnumerateInParallel(
 338        IList<IEnumerator<(int value, int level)>> enumerators, int level)
 1551339    {
 1551340        var parallelEnumeration = new ParallelEnumeration(enumerators);
 341
 1551342        var currentLevel = level;
 3036343        while (parallelEnumeration.MoveNextCount > 0)
 1485344        {
 1485345            var skippedBecauseOfHigherLevel = 0;
 7224346            for (var i = 0; i < enumerators.Count; i++)
 2127347            {
 4200348                while (parallelEnumeration.CurrentValueDefinedAndAtLevel(i, currentLevel))
 2073349                {
 2073350                    yield return enumerators[i].Current;
 2073351                    parallelEnumeration.MoveNext(i);
 2073352                }
 353
 2127354                if (parallelEnumeration.MoveNextValues[i])
 636355                    skippedBecauseOfHigherLevel++;
 2127356            }
 357
 1485358            if (skippedBecauseOfHigherLevel == parallelEnumeration.MoveNextCount)
 1485359                currentLevel++;
 1485360        }
 1551361    }
 362
 363    private sealed class ParallelEnumeration
 364    {
 4782365        public IList<IEnumerator<(int value, int level)>> Enumerators { get; }
 10473366        public bool[] MoveNextValues { get; }
 8346367        public int MoveNextCount { get; private set; }
 368
 1551369        public ParallelEnumeration(IList<IEnumerator<(int value, int level)>> enumerators)
 1551370        {
 1551371            var moveNextValues = new bool[enumerators.Count];
 1551372            var moveNextCount = 0;
 373
 7906374            for (var i = 0; i < enumerators.Count; i++)
 2402375            {
 2402376                moveNextValues[i] = enumerators[i].MoveNext();
 2402377                if (moveNextValues[i])
 1137378                    moveNextCount++;
 2402379            }
 380
 1551381            Enumerators = enumerators;
 1551382            MoveNextValues = moveNextValues;
 1551383            MoveNextCount = moveNextCount;
 1551384        }
 385
 386        public bool CurrentValueDefinedAndAtLevel(int enumeratorIndex, int level)
 4200387        {
 4200388            return MoveNextValues[enumeratorIndex] && Enumerators[enumeratorIndex].Current.level == level;
 4200389        }
 390
 391        public void MoveNext(int enumeratorIndex)
 2073392        {
 2073393            MoveNextValues[enumeratorIndex] = Enumerators[enumeratorIndex].MoveNext();
 394
 2073395            if (!MoveNextValues[enumeratorIndex])
 1137396                MoveNextCount--;
 2073397        }
 398    }
 399}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

.ctor(System.Boolean)
DepthFirstSearchAndConnectedComponentsOfGraph()
DepthFirstSearchOfGraph(MoreStructures.Graphs.IGraph)
ConnectedComponents(MoreStructures.Graphs.IGraph)
DepthFirstSearchFromVertex(MoreStructures.Graphs.IGraph,System.Int32)
BreadthFirstSearchFromVertex(MoreStructures.Graphs.IGraph,System.Int32)
BreadthFirstSearchFromVertices()
RDepthFirstSearchFromVertex()
RBreadthFirstSearchFromVertex()
EnumerateInParallel()
get_Enumerators()
get_MoveNextValues()
get_MoveNextCount()
.ctor(System.Collections.Generic.IList`1<System.Collections.Generic.IEnumerator`1<System.ValueTuple`2<System.Int32,System.Int32>>>)
CurrentValueDefinedAndAtLevel(System.Int32,System.Int32)
MoveNext(System.Int32)