Class AdjacencyMatrixGraph

A graph data structure, represented as a matrix: the (i, j) element of the matrix is true if the vertex with id i is neighbor of the vertex with id j, and false otherwise.

Inheritance

System.Object

AdjacencyMatrixGraph

Implements

IGraph

System.IEquatable<AdjacencyMatrixGraph>

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 AdjacencyMatrixGraph : IGraph, IEquatable<AdjacencyMatrixGraph>

Remarks

This representation doesn't support multigraphs, i.e. graphs which can have multiple parallel edges between the same two vertices.
If the graph can be considered undirected if all edges come in couples with both directions: i.e. the matrix is simmetrix, i.e. M[i, j] == M[j, i] for all (i, j).
The size of this data structure is proportional to the square of the number of vertices of the graph.
So, this graph representation is particularly useful when the number is edges is proportional to the square of the number of vertices v in the graph, and O(v) retrieval of the incoming and outgoing edges is required.
Performance is O(v), whether takeIntoAccountEdgeDirection is true or not.
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 sparse graphs, and comparable for dense graphs.
This representation is particularly convenient when used as a directed graph and traversal has often to be done in reversed direction, since Reverse() is an O(1) operation (it just builds a proxy to the original graph) and GetAdjacentVerticesAndEdges(Int32, Boolean) has comparable O(v) complexities when traversing edges according to their direction or in any direction.
Notice that AdjacencyListGraph has better runtime (O(avg_e)) when edges are traversed according to their direction, and worse runtime (O(avg_e + v)) when edges are traversed in any direction.
EdgeListGraph has consistent runtime in both traversal (O(e)), but e is O(v^2) in dense graphs, leading to sensibly worse performance in such scenarios.

Examples

The followin graph:

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

is represented as AdjacencyMatrixGraph(new {{ F, T, T, F }, { F, F, F, T }, { T, T, F, F }, {F, T, T, F }}).

Constructors

| Improve this Doc View Source

AdjacencyMatrixGraph(Boolean[,])

A graph data structure, represented as a matrix: the (i, j) element of the matrix is true if the vertex with id i is neighbor of the vertex with id j, and false otherwise.

Declaration

public AdjacencyMatrixGraph(bool[, ] AdjacencyMatrix)

Parameters

Type	Name	Description
System.Boolean[,]	AdjacencyMatrix	A square matrix of boolean, each value representing whether a vertex is neighborhood of another one.

Remarks

This representation doesn't support multigraphs, i.e. graphs which can have multiple parallel edges between the same two vertices.
If the graph can be considered undirected if all edges come in couples with both directions: i.e. the matrix is simmetrix, i.e. M[i, j] == M[j, i] for all (i, j).
The size of this data structure is proportional to the square of the number of vertices of the graph.
So, this graph representation is particularly useful when the number is edges is proportional to the square of the number of vertices v in the graph, and O(v) retrieval of the incoming and outgoing edges is required.
Performance is O(v), whether takeIntoAccountEdgeDirection is true or not.
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 sparse graphs, and comparable for dense graphs.
This representation is particularly convenient when used as a directed graph and traversal has often to be done in reversed direction, since Reverse() is an O(1) operation (it just builds a proxy to the original graph) and GetAdjacentVerticesAndEdges(Int32, Boolean) has comparable O(v) complexities when traversing edges according to their direction or in any direction.
Notice that AdjacencyListGraph has better runtime (O(avg_e)) when edges are traversed according to their direction, and worse runtime (O(avg_e + v)) when edges are traversed in any direction.
EdgeListGraph has consistent runtime in both traversal (O(e)), but e is O(v^2) in dense graphs, leading to sensibly worse performance in such scenarios.

Examples

The followin graph:

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

is represented as AdjacencyMatrixGraph(new {{ F, T, T, F }, { F, F, F, T }, { T, T, F, F }, {F, T, T, F }}).

Properties

| Improve this Doc View Source

AdjacencyMatrix

Declaration

public bool[, ] AdjacencyMatrix { get; set; }

Property Value

Type	Description
System.Boolean[,]

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
- Unlike the adjacency list representation, the matrix representation allows to access neighborhoods based on both outgoing and incoming edges of a given vertex (the first is a row, the second is a column).
- Therefore, unlike the adjacency list representation, when the value of takeIntoAccountEdgeDirection is false, a lookup of all neighborhoods defined in the matrix (i.e. a full matrix lookup) is not required.
- Instead, a single additional lookup of the neighborhood of incoming edges, is required, in addition to the lookup of the of the neighborhood of outgoing edges.
- Notice that, while in the adjacency list representation the neighborhood precisely contains the number of neighboring vertices, avg_e, in the adjacency matrix representation the neighborhood is in the form of a boolean array of v items, where v is the number of vertices of the graph.

COMPLEXITY
- Direct accesses to the two neighborhoods of interest are constant time operations, since it is about retrieving a row and a column given their index, respectively.
- The matrix is a square matrix of v rows and columns, so each of the neighborhoods to check has v elements.
- Each neighborhood has to be linearly scanned, looking for true values.
- Therefore, Time and Space Complexity (when enumerated) are O(v).

| 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
- Iterates over all the cells of the adjacency matrix M.
- For each adjacency M[u, v] set in M, the edge (u, v) is returned.

COMPLEXITY
- The adjacency matrix has v rows and v columns, where v is the number of vertices in the graph.
- Therefore Time Complexity is O(v^2). Space Complexity is O(1), since the iteration uses a constant amount of space.

| Improve this Doc View Source

GetNumberOfVertices()

Declaration

public int GetNumberOfVertices()

Returns

Type	Description
System.Int32

Remarks

In the AdjacencyMatrixGraph representation, corresponds to the edge of the square matrix.
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 AdjacencyMatrix directly.
- The implementation is very similar to the one of AdjacencyMatrixGraph: the only difference is that columns and rows 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 AdjacencyMatrixGraph.

Implements

IGraph

System.IEquatable<T>

Extension Methods

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