Class AdjacencyListGraph

A graph data structure, represented as an ordered list of neighborhoods: the i-th item of the list is the set of ids of the vertices which are neighbors of the vertex with id i.

Inheritance
System.Object
AdjacencyListGraph
Implements
System.IEquatable<AdjacencyListGraph>
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 AdjacencyListGraph : IGraph, IEquatable<AdjacencyListGraph>
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. when the neighborhoods list L is such that if v2 belongs to L[v1], then v1 belongs to L[v2].
  • The size of this data structure is proportional to the number of edges of the graph, since a vertex has as many neighbors as edges connecting to other vertices (possibly including itself).
  • 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, AdjacencyListGraph is more convenient than EdgeListGraph to run neighborhood-based algorithms, such as discovery, because it makes easier and faster to get neighbors of a vertex.
Examples

The followin graph:

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

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

Constructors

| Improve this Doc View Source

AdjacencyListGraph(IList<ISet<Int32>>)

A graph data structure, represented as an ordered list of neighborhoods: the i-th item of the list is the set of ids of the vertices which are neighbors of the vertex with id i.

Declaration
public AdjacencyListGraph(IList<ISet<int>> Neighborhoods)
Parameters
Type Name Description
IList<ISet<System.Int32>> Neighborhoods

A list of sets of integers, each set representing the neighborhood of the corresponding vertex.
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. when the neighborhoods list L is such that if v2 belongs to L[v1], then v1 belongs to L[v2].
  • The size of this data structure is proportional to the number of edges of the graph, since a vertex has as many neighbors as edges connecting to other vertices (possibly including itself).
  • 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, AdjacencyListGraph is more convenient than EdgeListGraph to run neighborhood-based algorithms, such as discovery, because it makes easier and faster to get neighbors of a vertex.
Examples

The followin graph:

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

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

Properties

| Improve this Doc View Source

Neighborhoods

Declaration
public IList<ISet<int>> Neighborhoods { get; set; }
Property Value
Type Description
IList<ISet<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 neighborhoods list is indexed by the vertex id, the algorithm has just to perform a direct access to the start-th item: that is the set of neighbors of the vertex with id start.
- When the value of takeIntoAccountEdgeDirection is false, a lookup of all neighborhoods is required.
- In such case it would be better to have neighborhoods list already including bi-directional edges, and using takeIntoAccountEdgeDirection = true. If not, the advantages of having O(1) neighborhood lookup would be lost.
- If bi-directional edges are not included in the graph, and many calls to this method need to be called with takeIntoAccountEdgeDirection = true, consider reversing the graph using Reverse(), and keep one structure for direct lookup and the other for reversed lookup.

COMPLEXITY
- Direct access to the neighborhoods list is a constant time operation.
- Therefore, when takeIntoAccountEdgeDirection = true, Time and Space Complexity (when enumerated) are O(avg_e), where avg_e is the average number of edges coming out of the start vertex.
- However, when takeIntoAccountEdgeDirection = false, Time Complexity becomes O(avg_e + v), where v is the number of vertices of the graph (i.e. the number of total neighborhoods defined).

| 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 neighborhoods.
- For each neighbor v of the vertex u, returns the edge (u, v).

COMPLEXITY
- There are v neighbors in total (as many as the number of vertices in the graph).
- The total number of neighbors across all neighborhoods is e (as many as the number of edges in the graph).
- Therefore Time Complexity is O(v + e). 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 AdjacencyListGraph representation, corresponds to number of neighborhoods.
Time and Space Complexity are O(1).

| Improve this Doc View Source

Reverse()

Declaration
public IGraph Reverse()
Returns
Type Description
IGraph
Remarks

ALGORITHM
- Because AdjacencyListGraph has O(avg_e + v) Time Complexity when edges have to be traversed in reverse, rather than O(avg_e), which is much smaller on large graphs, a proxy to the original data structure is not used.
- Instead, reversed neighborhoods RV are calculated, by iterating over all neighbors u of the neighborhood 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 empty .
- Finally a new AdjacencyListGraph is built out of RV and returned as result.

COMPLEXITY
- Unlike in Reverse(), a brand new structure is built, and proxies are not used at all.
- There are as many neighborhoods and reversed neighbors as vertices in the graph.
- The cost of going through all the neighbors in all the neighborhoods is proportional to the number of edges in the graph.
- Therefore Time and Space Complexity are O(v + e), where v is the number of vertices and e the number of edges.

Implements

System.IEquatable<T>

Extension Methods