< Summary

Information
Class: MoreStructures.Graphs.AdjacencyMatrixGraph
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/AdjacencyMatrixGraph.cs
Line coverage
100%
Covered lines: 140
Uncovered lines: 0
Coverable lines: 140
Total lines: 189
Line coverage: 100%
Branch coverage
N/A
Covered branches: 0
Total branches: 0
Branch coverage: N/A
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

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

File(s)

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

#LineLine coverage
 1namespace MoreStructures.Graphs;
 2
 3/// <summary>
 4/// A graph data structure, represented as a matrix: the (i, j) element of the matrix is true if the vertex with id i
 5/// is neighbor of the vertex with id j, and false otherwise.
 6/// </summary>
 7/// <param name="AdjacencyMatrix">
 8/// A square matrix of boolean, each value representing whether a vertex is neighborhood of another one.
 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. the matrix is
 15///   simmetrix, i.e. <c>M[i, j] == M[j, i] for all (i, j)</c>.
 16///   <br/>
 17/// - The size of this data structure is proportional to the square of the number of vertices of the graph.
 18///   <br/>
 19/// - So, this graph representation is particularly useful when the number is edges is proportional to the square of
 20///   the number of vertices v in the graph, and O(v) retrieval of the incoming and outgoing edges is required.
 21///   <br/>
 22/// - Performance is O(v), whether <c>takeIntoAccountEdgeDirection</c> is true or not.
 23///   <br/>
 24/// - Notice that O(v) is worse than O(avg_e), where avg_e is the average number of edges coming out of a vertex, for
 25///   sparse graphs, and comparable for dense graphs.
 26///   <br/>
 27/// - This representation is particularly convenient when used as a directed graph and traversal has often to be done
 28///   in reversed direction, since <see cref="Reverse"/> is an O(1) operation (it just builds a proxy to the original
 29///   graph) and <see cref="GetAdjacentVerticesAndEdges(int, bool)"/> has comparable O(v) complexities when traversing
 30///   edges according to their direction or in any direction.
 31///   <br/>
 32/// - Notice that <see cref="AdjacencyListGraph"/> has better runtime (O(avg_e)) when edges are traversed according to
 33///   their direction, and worse runtime (O(avg_e + v)) when edges are traversed in any direction.
 34///   <br/>
 35/// - <see cref="EdgeListGraph"/> has consistent runtime in both traversal (O(e)), but e is O(v^2) in dense graphs,
 36///   leading to sensibly worse performance in such scenarios.
 37/// </remarks>
 38/// <example>
 39/// The followin graph:
 40/// <code>
 41///  0 --> 1 &lt;==&gt; 3
 42/// | ^   ^     /
 43/// | |  /     /
 44/// | | /     /
 45/// v |/     /
 46///  2 &lt;-----
 47/// </code>
 48/// is represented as <c>AdjacencyMatrixGraph(new {{ F, T, T, F }, { F, F, F, T }, { T, T, F, F }, {F, T, T, F }})</c>.
 49/// </example>
 1558650public record AdjacencyMatrixGraph(bool[,] AdjacencyMatrix) : IGraph
 18451{
 18452    /// <inheritdoc path="//*[not(self::remarks)]" />
 18453    /// <remarks>
 18454    /// In the <see cref="AdjacencyMatrixGraph"/> representation, corresponds to the edge of the square matrix.
 18455    /// <br/>
 18456    /// Time and Space Complexity are O(1).
 18457    /// </remarks>
 12658    public int GetNumberOfVertices() => AdjacencyMatrix.GetLength(0);
 18459
 18460    /// <inheritdoc path="//*[not(self::remarks)]" />
 18461    /// <remarks>
 18462    ///     <para id="algorithm">
 18463    ///     ALGORITHM
 18464    ///     <br/>
 18465    ///     - Iterates over all the cells of the adjacency matrix M.
 18466    ///       <br/>
 18467    ///     - For each adjacency M[u, v] set in M, the edge (u, v) is returned.
 18468    ///     </para>
 18469    ///     <para id="complexity">
 18470    ///     COMPLEXITY
 18471    ///     <br/>
 18472    ///     - The adjacency matrix has v rows and v columns, where v is the number of vertices in the graph.
 18473    ///       <br/>
 18474    ///     - Therefore Time Complexity is O(v^2). Space Complexity is O(1), since the iteration uses a constant
 18475    ///       amount of space.
 18476    ///     </para>
 18477    /// </remarks>
 18478    public IEnumerable<(int edgeStart, int edgeEnd)> GetAllEdges() =>
 4079        from u in Enumerable.Range(0, AdjacencyMatrix.GetLength(0))
 79080        from v in Enumerable.Range(0, AdjacencyMatrix.GetLength(1))
 66081        where AdjacencyMatrix[u, v]
 15582        select (u, v);
 18483
 18484    /// <inheritdoc path="//*[not(self::remarks)]" />
 18485    /// <remarks>
 18486    ///     <para id="algorithm">
 18487    ///     ALGORITHM
 18488    ///     <br/>
 18489    ///     - Unlike the adjacency list representation, the matrix representation allows to access neighborhoods based
 18490    ///       on both outgoing and incoming edges of a given vertex (the first is a row, the second is a column).
 18491    ///       <br/>
 18492    ///     - Therefore, unlike the adjacency list representation, when the value of
 18493    ///       <paramref name="takeIntoAccountEdgeDirection"/> is <see langword="false"/>, a lookup of all neighborhoods
 18494    ///       defined in the matrix (i.e. a full matrix lookup) is not required.
 18495    ///       <br/>
 18496    ///     - Instead, a single additional lookup of the neighborhood of incoming edges, is required, in addition to
 18497    ///       the lookup of the of the neighborhood of outgoing edges.
 18498    ///       <br/>
 18499    ///     - Notice that, while in the adjacency list representation the neighborhood precisely contains the number of
 184100    ///       neighboring vertices, avg_e, in the adjacency matrix representation the neighborhood is in the form of a
 184101    ///       boolean array of v items, where v is the number of vertices of the graph.
 184102    ///     </para>
 184103    ///     <para id="complexity">
 184104    ///     COMPLEXITY
 184105    ///     <br/>
 184106    ///     - Direct accesses to the two neighborhoods of interest are constant time operations, since it is about
 184107    ///       retrieving a row and a column given their index, respectively.
 184108    ///       <br/>
 184109    ///     - The matrix is a square matrix of v rows and columns, so each of the neighborhoods to check has v
 184110    ///       elements.
 184111    ///       <br/>
 184112    ///     - Each neighborhood has to be linearly scanned, looking for <see langword="true"/> values.
 184113    ///       <br/>
 184114    ///     - Therefore, Time and Space Complexity (when enumerated) are O(v).
 184115    ///     </para>
 184116    /// </remarks>
 184117    public IEnumerable<IGraph.Adjacency> GetAdjacentVerticesAndEdges(
 184118        int start, bool takeIntoAccountEdgeDirection)
 1076119    {
 11490120        for (var j = 0; j < AdjacencyMatrix.GetLength(1); j++)
 4669121        {
 4669122            if (AdjacencyMatrix[start, j])
 1050123                yield return new(j, start, j);
 4669124        }
 184125
 1076126        if (takeIntoAccountEdgeDirection)
 680127            yield break;
 184128
 4192129        for (var i = 0; i < AdjacencyMatrix.GetLength(0); i++)
 1700130        {
 1700131            if (AdjacencyMatrix[i, start])
 404132                yield return new(i, i, start);
 1700133        }
 396134    }
 184135
 184136    /// <inheritdoc path="//*[not(self::remarks)]" />
 184137    /// <remarks>
 184138    ///     <para id="algorithm">
 184139    ///     ALGORITHM
 184140    ///     <br/>
 184141    ///     - An <see cref="IGraph"/> proxy is created, wrapping this instance of <see cref="IGraph"/>.
 184142    ///       <br/>
 184143    ///     - <see cref="IGraph.GetNumberOfVertices"/> is dispatched to the proxied graph.
 184144    ///       <br/>
 184145    ///     - <see cref="IGraph.GetAdjacentVerticesAndEdges(int, bool)"/> is directly implemented, accessing
 184146    ///       <see cref="AdjacencyMatrix"/> directly.
 184147    ///       <br/>
 184148    ///     - The implementation is very similar to the one of <see cref="AdjacencyMatrixGraph"/>: the only difference
 184149    ///       is that columns and rows are inverted.
 184150    ///     </para>
 184151    ///     <para id="complexity">
 184152    ///     COMPLEXITY
 184153    ///     <br/>
 184154    ///     - Since this method just creates a proxy, Time and Space Complexity are O(1).
 184155    ///       <br/>
 184156    ///     - All operations on the proxy have the same Time and Space Complexity as the corresponding methods in
 184157    ///       <see cref="AdjacencyMatrixGraph"/>.
 184158    ///     </para>
 184159    /// </remarks>
 24160    public IGraph Reverse() => new ReverseGraph(this);
 184161
 184162    sealed private class ReverseGraph : ReverseProxyGraph<AdjacencyMatrixGraph>
 184163    {
 24164        public ReverseGraph(AdjacencyMatrixGraph graph) : base(graph)
 24165        {
 24166        }
 184167
 184168        public override IEnumerable<IGraph.Adjacency> GetAdjacentVerticesAndEdges(
 184169            int start, bool takeIntoAccountEdgeDirection)
 52170        {
 52171            var adjacencyMatrix = Proxied.AdjacencyMatrix;
 184172
 632173            for (var i = 0; i < adjacencyMatrix.GetLength(0); i++)
 264174            {
 264175                if (adjacencyMatrix[i, start])
 46176                    yield return new(i, start, i);
 264177            }
 184178
 52179            if (takeIntoAccountEdgeDirection)
 26180                yield break;
 184181
 316182            for (var j = 0; j < adjacencyMatrix.GetLength(1); j++)
 132183            {
 132184                if (adjacencyMatrix[start, j])
 23185                    yield return new(j, j, start);
 132186            }
 26187        }
 184188    }
 184189}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_AdjacencyMatrix()
.ctor(System.Boolean[0...,0...])
GetNumberOfVertices()
GetAllEdges()
Reverse()