Class EdgeListGraph

A graph data structure, represented as an unsorted list of unlabelled edges, connecting unlabelled vertices.

Inheritance

System.Object

EdgeListGraph

Implements

IGraph

System.IEquatable<EdgeListGraph>

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: MoreStructures.Graphs

Assembly: MoreStructures.dll

Syntax

public class EdgeListGraph : IGraph, IEquatable<EdgeListGraph>

Remarks

This representation does support multigraphs, i.e. graphs which can have multiple parallel edges between the same two vertices.
If the edges are considered directional, i.e. (s, e) is considered as a different edge from (e, s), the resulting graph is directed. Otherwise, the resulting graph is undirected.
The size of this data structure is proportional to the number of edges of the graph.
So, this graph representation is particularly useful when the number is edges is smaller or proportional to the number of vertices in the graph, i.e. when the graph is sparse (i.e. when e is O(v)).
It becomes an expensive representation when the graph is dense (i.e. when e is O(v^2)).
While having size proportional to the number of edges, EdgeListGraph is less convenient than AdjacencyListGraph to run neighborhood-based algorithms, such as discovery, because it makes more complex and slower to get neighbors of a vertex.

Examples

The followin graph:

 0 --> 1 <==> 3
| ^   ^     /
| |  /     /
| | /     /
v |/     /
 2 <-----

is represented as EdgeListGraph(4, new { (0, 1), (0, 2), (1, 3), (2, 0), (2, 1), (3, 1), (3, 2) }).

Constructors

| Improve this Doc View Source

EdgeListGraph(Int32, IList<(Int32 start, Int32 end)>)

A graph data structure, represented as an unsorted list of unlabelled edges, connecting unlabelled vertices.

Declaration

public EdgeListGraph(int NumberOfVertices, IList<(int start, int end)> Edges)

Parameters

Type	Name	Description
System.Int32	NumberOfVertices	The total number n of vertices in the graph, identified with ids from 0 to n - 1.
IList<System.ValueTuple<System.Int32, System.Int32>>	Edges	The list of edges of the graph, each one represented as a couple of ids of the vertices which constitute the extremes of the edge. Edges can be considered as directional or not, depending on the scenario.

Remarks

This representation does support multigraphs, i.e. graphs which can have multiple parallel edges between the same two vertices.
If the edges are considered directional, i.e. (s, e) is considered as a different edge from (e, s), the resulting graph is directed. Otherwise, the resulting graph is undirected.
The size of this data structure is proportional to the number of edges of the graph.
So, this graph representation is particularly useful when the number is edges is smaller or proportional to the number of vertices in the graph, i.e. when the graph is sparse (i.e. when e is O(v)).
It becomes an expensive representation when the graph is dense (i.e. when e is O(v^2)).
While having size proportional to the number of edges, EdgeListGraph is less convenient than AdjacencyListGraph to run neighborhood-based algorithms, such as discovery, because it makes more complex and slower to get neighbors of a vertex.

Examples

The followin graph:

 0 --> 1 <==> 3
| ^   ^     /
| |  /     /
| | /     /
v |/     /
 2 <-----

is represented as EdgeListGraph(4, new { (0, 1), (0, 2), (1, 3), (2, 0), (2, 1), (3, 1), (3, 2) }).

Properties

| Improve this Doc View Source

Edges

Declaration

public IList<(int start, int end)> Edges { get; set; }

Property Value

Type	Description
IList<System.ValueTuple<System.Int32, System.Int32>>

| Improve this Doc View Source

NumberOfVertices

Declaration

public int NumberOfVertices { get; set; }

Property Value

Type	Description
System.Int32

Methods

| Improve this Doc View Source

GetAdjacentVerticesAndEdges(Int32, Boolean)

Declaration

public IEnumerable<IGraph.Adjacency> GetAdjacentVerticesAndEdges(int start, bool takeIntoAccountEdgeDirection)

Parameters

Type	Name	Description
System.Int32	start
System.Boolean	takeIntoAccountEdgeDirection

Returns

Type	Description
IEnumerable<IGraph.Adjacency>

Remarks

ALGORITHM
- Because the edge list is unsorted, and there is no "index" or additional data structure which can help retrieving neighbors quickly, the algorithm has to linearly scan the entire edge list, looking for neighbors.

COMPLEXITY
- Checking whether each edge is a neighbor or not only requires comparing the edge start, when taking into account edge directions, or both start and end, when considering edges as undirected.
- Both are constant time operations.
- Therefore Time Complexity is O(e), where e is the number of edges, and Space Complexity is O(1).

| Improve this Doc View Source

GetAllEdges()

Declaration

public IEnumerable<(int edgeStart, int edgeEnd)> GetAllEdges()

Returns

Type	Description
IEnumerable<System.ValueTuple<System.Int32, System.Int32>>

Remarks

ALGORITHM
- Just returns the underlying list of edges, as is.

COMPLEXITY
- Time and Space Complexity are O(1).

| Improve this Doc View Source

GetNumberOfVertices()

Declaration

public int GetNumberOfVertices()

Returns

Type	Description
System.Int32

Remarks

In the EdgeListGraph representation, it's explicitely set in NumberOfVertices.
Time and Space Complexity are O(1).

| Improve this Doc View Source

Reverse()

Declaration

public IGraph Reverse()

Returns

Type	Description
IGraph

Remarks

ALGORITHM
- An IGraph proxy is created, wrapping this instance of IGraph.
- GetNumberOfVertices() is dispatched to the proxied graph.
- GetAdjacentVerticesAndEdges(Int32, Boolean) is directly implemented, accessing Edges directly.
- The implementation is very similar to the one of EdgeListGraph: the only difference is that start and end vertices of each edge are inverted.

COMPLEXITY
- Since this method just creates a proxy, Time and Space Complexity are O(1).
- All operations on the proxy have the same Time and Space Complexity as the corresponding methods in EdgeListGraph.

Implements

IGraph

System.IEquatable<T>

Extension Methods

SuffixStructureNodeExtensions.GetAllSuffixesFor<TEdge, TNode>(TNode, TextWithTerminator)