< Summary

Information
Class: MoreStructures.Graphs.EdgeListGraph
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/EdgeListGraph.cs
Line coverage
100%
Covered lines: 137
Uncovered lines: 0
Coverable lines: 137
Total lines: 179
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_NumberOfVertices()100%1100%
.ctor(...)100%1100%
GetNumberOfVertices()100%1100%
GetAllEdges()100%1100%
Reverse()100%1100%

File(s)

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

#LineLine coverage
 1namespace MoreStructures.Graphs;
 2
 3/// <summary>
 4/// A graph data structure, represented as an unsorted list of unlabelled edges, connecting unlabelled vertices.
 5/// </summary>
 6/// <param name="NumberOfVertices">
 7/// The total number n of vertices in the graph, identified with ids from 0 to n - 1.
 8/// </param>
 9/// <param name="Edges">
 10/// The list of edges of the graph, each one represented as a couple of ids of the vertices which constitute the
 11/// extremes of the edge. Edges can be considered as directional or not, depending on the scenario.
 12/// </param>
 13/// <remarks>
 14/// - <b>This representation does support multigraphs</b>, i.e. graphs which can have multiple parallel edges
 15///   between the same two vertices.
 16///   <br/>
 17/// - If the edges are considered directional, i.e. (s, e) is considered as a different edge from (e, s), the resulting
 18///   graph is directed. Otherwise, the resulting graph is undirected.
 19///   <br/>
 20/// - The size of this data structure is proportional to the number of edges of the graph.
 21///   <br/>
 22/// - So, this graph representation is particularly useful when the number is edges is smaller or proportional to the
 23///   number of vertices in the graph, i.e. when the graph is <b>sparse</b> (i.e. when e is O(v)).
 24///   <br/>
 25/// - It becomes an expensive representation when the graph is <b>dense</b> (i.e. when e is O(v^2)).
 26///   <br/>
 27/// - While having size proportional to the number of edges, <see cref="EdgeListGraph"/> is less convenient than
 28///   <see cref="AdjacencyListGraph"/> to run neighborhood-based algorithms, such as discovery, because it makes more
 29///   complex and slower to get neighbors of a vertex.
 30/// </remarks>
 31/// <example>
 32/// The followin graph:
 33/// <code>
 34///  0 --> 1 &lt;==&gt; 3
 35/// | ^   ^     /
 36/// | |  /     /
 37/// | | /     /
 38/// v |/     /
 39///  2 &lt;-----
 40/// </code>
 41/// is represented as <c>EdgeListGraph(4, new { (0, 1), (0, 2), (1, 3), (2, 0), (2, 1), (3, 1), (3, 2) })</c>.
 42/// </example>
 4556843public record EdgeListGraph(int NumberOfVertices, IList<(int start, int end)> Edges) : IGraph
 73444{
 73445    /// <inheritdoc path="//*[not(self::remarks)]" />
 73446    /// <remarks>
 73447    /// In the <see cref="EdgeListGraph"/> representation, it's explicitely set in <see cref="NumberOfVertices"/>.
 73448    /// <br/>
 73449    /// Time and Space Complexity are O(1).
 73450    /// </remarks>
 291851    public int GetNumberOfVertices() => NumberOfVertices;
 73452
 73453    /// <inheritdoc path="//*[not(self::remarks)]" />
 73454    /// <remarks>
 73455    ///     <para id="algorithm">
 73456    ///     ALGORITHM
 73457    ///     <br/>
 73458    ///     - Just returns the underlying list of edges, as is.
 73459    ///     </para>
 73460    ///     <para id="complexity">
 73461    ///     COMPLEXITY
 73462    ///     <br/>
 73463    ///     - Time and Space Complexity are O(1).
 73464    ///     </para>
 73465    /// </remarks>
 73466
 5467    public IEnumerable<(int edgeStart, int edgeEnd)> GetAllEdges() => Edges;
 73468
 73469
 73470    /// <inheritdoc path="//*[not(self::remarks)]" />
 73471    /// <remarks>
 73472    ///     <para id="algorithm">
 73473    ///     ALGORITHM
 73474    ///     <br/>
 73475    ///     - Because the edge list is unsorted, and there is no "index" or additional data structure which can help
 73476    ///       retrieving neighbors quickly, the algorithm has to linearly scan the entire edge list, looking for
 73477    ///       neighbors.
 73478    ///     </para>
 73479    ///     <para id="complexity">
 73480    ///     COMPLEXITY
 73481    ///     <br/>
 73482    ///     - Checking whether each edge is a neighbor or not only requires comparing the edge start, when taking into
 73483    ///       account edge directions, or both start and end, when considering edges as undirected.
 73484    ///       <br/>
 73485    ///     - Both are constant time operations.
 73486    ///       <br/>
 73487    ///     - Therefore Time Complexity is O(e), where e is the number of edges, and Space Complexity is O(1).
 73488    ///     </para>
 73489    /// </remarks>
 73490    public IEnumerable<IGraph.Adjacency> GetAdjacentVerticesAndEdges(
 73491        int start, bool takeIntoAccountEdgeDirection)
 3944592    {
 3944593        if (takeIntoAccountEdgeDirection)
 3859294        {
 3859295            var adjacencies = Edges
 49049696                .Where(edge => edge.start == start)
 8665197                .Select(edge => new IGraph.Adjacency(edge.end, edge.start, edge.end));
 21181298            foreach (var adjacency in adjacencies)
 4805999                yield return adjacency;
 38510100            yield break;
 734101        }
 734102
 9851103        foreach (var edge in Edges)
 3646104        {
 3646105            if (edge.start == start)
 871106            {
 871107                yield return new(edge.end, edge.start, edge.end);
 871108                continue;
 734109            }
 2775110            if (edge.end == start)
 765111            {
 765112                yield return new(edge.start, edge.start, edge.end);
 765113            }
 2775114        }
 853115    }
 734116
 734117    /// <inheritdoc path="//*[not(self::remarks)]" />
 734118    /// <remarks>
 734119    ///     <para id="algorithm">
 734120    ///     ALGORITHM
 734121    ///     <br/>
 734122    ///     - An <see cref="IGraph"/> proxy is created, wrapping this instance of <see cref="IGraph"/>.
 734123    ///       <br/>
 734124    ///     - <see cref="IGraph.GetNumberOfVertices"/> is dispatched to the proxied graph.
 734125    ///       <br/>
 734126    ///     - <see cref="IGraph.GetAdjacentVerticesAndEdges(int, bool)"/> is directly implemented, accessing
 734127    ///       <see cref="Edges"/> directly.
 734128    ///       <br/>
 734129    ///     - The implementation is very similar to the one of <see cref="EdgeListGraph"/>: the only difference
 734130    ///       is that start and end vertices of each edge are inverted.
 734131    ///     </para>
 734132    ///     <para id="complexity">
 734133    ///     COMPLEXITY
 734134    ///     <br/>
 734135    ///     - Since this method just creates a proxy, Time and Space Complexity are O(1).
 734136    ///       <br/>
 734137    ///     - All operations on the proxy have the same Time and Space Complexity as the corresponding methods in
 734138    ///       <see cref="EdgeListGraph"/>.
 734139    ///     </para>
 734140    /// </remarks>
 574141    public IGraph Reverse() => new ReverseGraph(this);
 734142
 734143    sealed private class ReverseGraph : ReverseProxyGraph<EdgeListGraph>
 734144    {
 574145        public ReverseGraph(EdgeListGraph graph) : base(graph)
 574146        {
 574147        }
 734148
 734149        public override IEnumerable<IGraph.Adjacency> GetAdjacentVerticesAndEdges(
 734150            int start, bool takeIntoAccountEdgeDirection)
 949151        {
 949152            var edges = Proxied.Edges;
 734153
 949154            if (takeIntoAccountEdgeDirection)
 923155            {
 923156                var adjacencies = edges
 7154157                    .Where(edge => edge.end == start)
 1811158                    .Select(edge => new IGraph.Adjacency(edge.start, edge.end, edge.start));
 4543159                foreach (var adjacency in adjacencies)
 888160                    yield return adjacency;
 921161                yield break;
 734162            }
 734163
 346164            foreach (var edge in edges)
 134165            {
 134166                if (edge.end == start)
 23167                {
 23168                    yield return new(edge.start, edge.end, edge.start);
 23169                }
 734170
 134171                if (edge.start == start)
 23172                {
 23173                    yield return new(edge.end, edge.end, edge.start);
 23174                    continue;
 734175                }
 111176            }
 26177        }
 734178    }
 734179}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_NumberOfVertices()
.ctor(System.Int32,System.Collections.Generic.IList`1<System.ValueTuple`2<System.Int32,System.Int32>>)
GetNumberOfVertices()
GetAllEdges()
Reverse()