< Summary

Information
Class: MoreStructures.Graphs.AdjacencyListGraph
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/AdjacencyListGraph.cs
Line coverage
100%
Covered lines: 133
Uncovered lines: 0
Coverable lines: 133
Total lines: 173
Line coverage: 100%
Branch coverage
100%
Covered branches: 6
Total branches: 6
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_Neighborhoods()100%1100%
.ctor(...)100%1100%
GetNumberOfVertices()100%1100%
GetAllEdges()100%1100%
Reverse()100%6100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/AdjacencyListGraph.cs

#LineLine coverage
 1namespace MoreStructures.Graphs;
 2
 3/// <summary>
 4/// A graph data structure, represented as an ordered list of neighborhoods: the i-th item of the list is the set of
 5/// ids of the vertices which are neighbors of the vertex with id i.
 6/// </summary>
 7/// <param name="Neighborhoods">
 8/// A list of sets of integers, each set representing the neighborhood of the corresponding vertex.
 9/// </param>
 10/// <remarks>
 11/// - <b>This representation doesn't support multigraphs</b>, i.e. graphs which can have multiple parallel edges
 12///   between the same two vertices.
 13///   <br/>
 14/// - If the graph can be considered undirected if all edges come in couples with both directions: i.e. when the
 15///   neighborhoods list L is such that <c>if v2 belongs to L[v1], then v1 belongs to L[v2]</c>.
 16///   <br/>
 17/// - The size of this data structure is proportional to the number of edges of the graph, since a vertex has as many
 18///   neighbors as edges connecting to other vertices (possibly including itself).
 19///   <br/>
 20/// - So, this graph representation is particularly useful when the number is edges is smaller or proportional to the
 21///   number of vertices in the graph, i.e. when the graph is <b>sparse</b> (i.e. when e is O(v)).
 22///   <br/>
 23/// - It becomes an expensive representation when the graph is <b>dense</b> (i.e. when e is O(v^2)).
 24///   <br/>
 25/// - While having size proportional to the number of edges, <see cref="AdjacencyListGraph"/> is more convenient than
 26///   <see cref="EdgeListGraph"/> to run neighborhood-based algorithms, such as discovery, because it makes easier
 27///   and faster to get neighbors of a vertex.
 28/// </remarks>
 29/// <example>
 30/// The followin graph:
 31/// <code>
 32///  0 --> 1 &lt;==&gt; 3
 33/// | ^   ^     /
 34/// | |  /     /
 35/// | | /     /
 36/// v |/     /
 37///  2 &lt;-----
 38/// </code>
 39/// is represented as <c>AdjacencyListGraph(new { new { 1, 2 }, new { 3 }, new { 0, 1 }, new { 1, 2 } })</c>.
 40/// </example>
 552641public record AdjacencyListGraph(IList<ISet<int>> Neighborhoods) : IGraph
 21642{
 21643    /// <inheritdoc path="//*[not(self::remarks)]" />
 21644    /// <remarks>
 21645    /// In the <see cref="AdjacencyListGraph"/> representation, corresponds to number of neighborhoods.
 21646    /// <br/>
 21647    /// Time and Space Complexity are O(1).
 21648    /// </remarks>
 12649    public int GetNumberOfVertices() => Neighborhoods.Count;
 21650
 21651    /// <inheritdoc path="//*[not(self::remarks)]" />
 21652    /// <remarks>
 21653    ///     <para id="algorithm">
 21654    ///     ALGORITHM
 21655    ///     <br/>
 21656    ///     - Iterates over all the neighborhoods.
 21657    ///       <br/>
 21658    ///     - For each neighbor v of the vertex u, returns the edge (u, v).
 21659    ///     </para>
 21660    ///     <para id="complexity">
 21661    ///     COMPLEXITY
 21662    ///     <br/>
 21663    ///     - There are v neighbors in total (as many as the number of vertices in the graph).
 21664    ///       <br/>
 21665    ///     - The total number of neighbors across all neighborhoods is e (as many as the number of edges in the
 21666    ///       graph).
 21667    ///       <br/>
 21668    ///     - Therefore Time Complexity is O(v + e). Space Complexity is O(1), since the iteration uses a constant
 21669    ///       amount of space.
 21670    ///     </para>
 21671    /// </remarks>
 21672    public IEnumerable<(int edgeStart, int edgeEnd)> GetAllEdges() =>
 28573        Neighborhoods.SelectMany((v, i) => Enumerable.Repeat(i, v.Count).Zip(v).Select(c => c));
 21674
 21675    /// <inheritdoc path="//*[not(self::remarks)]" />
 21676    /// <remarks>
 21677    ///     <para id="algorithm">
 21678    ///     ALGORITHM
 21679    ///     <br/>
 21680    ///     - Because the neighborhoods list is indexed by the vertex id, the algorithm has just to perform a direct
 21681    ///       access to the <paramref name="start"/>-th item: that is the set of neighbors of the vertex with id
 21682    ///       <paramref name="start"/>.
 21683    ///       <br/>
 21684    ///     - When the value of <paramref name="takeIntoAccountEdgeDirection"/> is <see langword="false"/>, a lookup of
 21685    ///       all neighborhoods is required.
 21686    ///       <br/>
 21687    ///     - In such case it would be better to have neighborhoods list already including bi-directional edges, and
 21688    ///       using <paramref name="takeIntoAccountEdgeDirection"/> = <see langword="true"/>. If not, the advantages of
 21689    ///       having O(1) neighborhood lookup would be lost.
 21690    ///       <br/>
 21691    ///     - If bi-directional edges are not included in the graph, and many calls to this method need to be called
 21692    ///       with <paramref name="takeIntoAccountEdgeDirection"/> = <see langword="true"/>, consider reversing the
 21693    ///       graph using <see cref="Reverse"/>, and keep one structure for direct lookup and the other for reversed
 21694    ///       lookup.
 21695    ///     </para>
 21696    ///     <para id="complexity">
 21697    ///     COMPLEXITY
 21698    ///     <br/>
 21699    ///     - Direct access to the neighborhoods list is a constant time operation.
 216100    ///       <br/>
 216101    ///     - Therefore, when <paramref name="takeIntoAccountEdgeDirection"/> = <see langword="true"/>, Time and Space
 216102    ///       Complexity (when enumerated) are O(avg_e), where avg_e is the average number of edges coming out of the
 216103    ///       <paramref name="start"/> vertex.
 216104    ///       <br/>
 216105    ///     - However, when <paramref name="takeIntoAccountEdgeDirection"/> = <see langword="false"/>, Time Complexity
 216106    ///       becomes O(avg_e + v), where v is the number of vertices of the graph (i.e. the number of total
 216107    ///       neighborhoods defined).
 216108    ///     </para>
 216109    /// </remarks>
 216110    public IEnumerable<IGraph.Adjacency> GetAdjacentVerticesAndEdges(
 216111        int start, bool takeIntoAccountEdgeDirection)
 1128112    {
 5576113        foreach (var end in Neighborhoods[start])
 1096114            yield return new(end, start, end);
 216115
 1128116        if (takeIntoAccountEdgeDirection)
 706117            yield break;
 216118
 4508119        for (var i = 0; i < Neighborhoods.Count; i++)
 1832120        {
 1832121            if (i == start)
 422122                continue;
 216123
 1410124            if (Neighborhoods[i].Contains(start))
 378125                yield return new(i, i, start);
 1410126        }
 422127    }
 216128
 216129    /// <inheritdoc path="//*[not(self::remarks)]" />
 216130    /// <remarks>
 216131    ///     <para id="algorithm">
 216132    ///     ALGORITHM
 216133    ///     <br/>
 216134    ///     - Because <see cref="AdjacencyListGraph"/> has O(avg_e + v) Time Complexity when edges have to be traversed
 216135    ///       in reverse, rather than O(avg_e), which is much smaller on large graphs, a proxy to the original data
 216136    ///       structure is not used.
 216137    ///       <br/>
 216138    ///     - Instead, reversed neighborhoods RV are calculated, by iterating over all neighbors u of the neighborhood
 216139    ///       N[v] of each vertex v of this graph: if u belongs to N[v] then v is added to RV[u], initially set to an
 216140    ///       empty <see cref="HashSet{T}"/>.
 216141    ///       <br/>
 216142    ///     - Finally a new <see cref="AdjacencyListGraph"/> is built out of RV and returned as result.
 216143    ///     </para>
 216144    ///     <para id="complexity">
 216145    ///     COMPLEXITY
 216146    ///     <br/>
 216147    ///     - Unlike in <see cref="AdjacencyMatrixGraph.Reverse"/>, a brand new structure is built, and proxies are not
 216148    ///       used at all.
 216149    ///       <br/>
 216150    ///     - There are as many neighborhoods and reversed neighbors as vertices in the graph.
 216151    ///       <br/>
 216152    ///     - The cost of going through all the neighbors in all the neighborhoods is proportional to the number of
 216153    ///       edges in the graph.
 216154    ///       <br/>
 216155    ///     - Therefore Time and Space Complexity are O(v + e), where v is the number of vertices and e the number of
 216156    ///       edges.
 216157    ///     </para>
 216158    /// </remarks>
 216159    public IGraph Reverse()
 32160    {
 32161        var numberOfVertices = Neighborhoods.Count;
 32162        var reversedNeighborhoods = new ISet<int>[numberOfVertices];
 216163
 272164        for (var vertex = 0; vertex < numberOfVertices; vertex++)
 104165            reversedNeighborhoods[vertex] = new HashSet<int>();
 216166
 272167        for (var vertex = 0; vertex < numberOfVertices; vertex++)
 496168            foreach (var neighbor in Neighborhoods[vertex])
 92169                reversedNeighborhoods[neighbor].Add(vertex);
 216170
 32171        return new AdjacencyListGraph(reversedNeighborhoods);
 32172    }
 216173}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_Neighborhoods()
.ctor(System.Collections.Generic.IList`1<System.Collections.Generic.ISet`1<System.Int32>>)
GetNumberOfVertices()
GetAllEdges()
Reverse()