Graph<T> Class

Definition

Namespace

Bodu.Collections.Generic.Graphs

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

Graph{T}.Edges.cs

Represents a graph of vertices connected by weighted edges, backed by an adjacency list and supporting either directed or undirected edge semantics.

public sealed class Graph<T> : IReadOnlyWeightedGraph<T>, IReadOnlyGraph<T> where T : notnull

Type Parameters

T

The type of the vertices. Must be non-nullable.

Inheritance

object

Graph<T>

Implements

IReadOnlyWeightedGraph<T>

IReadOnlyGraph<T>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

ComparableExtensions.AtLeast<T>(T, T, IComparer<T>)

ComparableExtensions.AtMost<T>(T, T, IComparer<T>)

ComparableExtensions.IsEqualTo<T>(T, T, IComparer<T>)

ComparableExtensions.Max<T>(T, T, IComparer<T>)

ComparableExtensions.Min<T>(T, T, IComparer<T>)

Examples

var graph = new Graph<int>(GraphKind.Directed);
graph.AddEdge(1, 2);          // referenced vertices are created on demand
graph.AddEdge(1, 3);
graph.AddEdge(2, 4, 2.5);     // weighted edge

foreach (int neighbor in graph.Neighbors(1))
    Console.WriteLine(neighbor);   // 2, 3

// Graph<T> is an IReadOnlyWeightedGraph<T>, accepted directly by GraphAlgorithms.
var reachable = GraphAlgorithms.BreadthFirstSearch(graph, 1).ToList();

Remarks

Edge directedness is fixed at construction by GraphKind. In an undirected graph each edge is stored symmetrically, so a single AddEdge(T, T) makes the two vertices mutual neighbors. Edges carry a non-negative double weight that defaults to 1.0; algorithms that ignore weight treat the graph as unweighted.

Vertices referenced by AddEdge(T, T) are created automatically if absent. Vertex identity is determined by the IEqualityComparer<T> supplied at construction. The graph is not thread-safe for concurrent mutation. Algorithms over the graph are provided by GraphAlgorithms.

Constructors

Graph()

Initializes a new instance of the Graph<T> class as an undirected graph using the default vertex comparer.

public Graph()

Graph(GraphKind)

Initializes a new instance of the Graph<T> class with the specified directedness and the default vertex comparer.

public Graph(GraphKind kind)

Parameters

kind GraphKind

Whether the graph is directed or undirected.

Graph(GraphKind, IEqualityComparer<T>?)

Initializes a new instance of the Graph<T> class with the specified directedness and vertex comparer.

public Graph(GraphKind kind, IEqualityComparer<T>? comparer)

Parameters

kind GraphKind

Whether the graph is directed or undirected.

comparer IEqualityComparer<T>

The comparer used to determine vertex identity, or null to use the default comparer.

Properties

Comparer

Gets the comparer used to determine vertex identity.

public IEqualityComparer<T> Comparer { get; }

Property Value

IEqualityComparer<T>

The comparer supplied at construction, or the default comparer.

EdgeCount

Gets the number of edges in the graph. In an undirected graph each connection counts once.

public int EdgeCount { get; }

Property Value

int

The edge count.

IsDirected

Gets a value indicating whether edges are directed.

public bool IsDirected { get; }

Property Value

bool

true for a directed graph; otherwise, false.

VertexCount

Gets the number of vertices in the graph.

public int VertexCount { get; }

Property Value

int

The vertex count.

Vertices

Gets the vertices of the graph.

public IReadOnlyCollection<T> Vertices { get; }

Property Value

IReadOnlyCollection<T>

A read-only collection of the graph's vertices.

Methods

AddEdge(T, T)

Adds an unweighted edge (weight 1.0) between the specified vertices, creating either vertex if it does not already exist.

public void AddEdge(T from, T to)

Parameters

from T

The source vertex.

to T

The destination vertex.

Exceptions

ArgumentNullException

Either vertex is null.

AddEdge(T, T, double)

Adds or updates a weighted edge between the specified vertices, creating either vertex if it does not already exist.

public void AddEdge(T from, T to, double weight)

Parameters

from T

The source vertex.

to T

The destination vertex.

weight double

The finite, non-negative edge weight.

Remarks

On an undirected graph, a self-loop (from equals to under Comparer) is stored as a single adjacency entry, so it contributes 1 to Degree(T) - diverging from the classical graph-theory convention, in which an undirected self-loop counts twice toward its vertex's degree.

Exceptions

ArgumentNullException

Either vertex is null.

ArgumentOutOfRangeException

weight is not a finite, non-negative number (it is NaN, infinite, or negative).

AddVertex(T)

Adds a vertex to the graph.

public bool AddVertex(T vertex)

Parameters

vertex T

The vertex to add.

Returns

bool

true if the vertex was added; false if it already existed.

Exceptions

ArgumentNullException

vertex is null.

Clear()

Removes all vertices and edges from the graph.

public void Clear()

ContainsEdge(T, T)

Determines whether an edge exists between the specified vertices.

public bool ContainsEdge(T from, T to)

Parameters

from T

The source vertex.

to T

The destination vertex.

Returns

bool

true if the edge exists; otherwise, false.

Exceptions

ArgumentNullException

Either vertex is null.

ContainsVertex(T)

Determines whether the graph contains the specified vertex.

public bool ContainsVertex(T vertex)

Parameters

vertex T

The vertex to locate.

Returns

bool

true if the vertex exists; otherwise, false.

Exceptions

ArgumentNullException

vertex is null.

Degree(T)

Returns the out-degree of the specified vertex.

public int Degree(T vertex)

Parameters

vertex T

The vertex whose degree is requested.

Returns

int

The number of outgoing edges; for an undirected graph this is the vertex's degree.

Remarks

The value is the out-edge (adjacency-entry) count. Because an undirected self-loop is stored once, it contributes 1 - not the 2 that the classical graph-theory degree convention would assign an undirected self-loop.

Exceptions

ArgumentNullException

vertex is null.

ArgumentException

vertex is not in the graph.

Neighbors(T)

Returns the vertices adjacent to the specified vertex via outgoing edges.

public IEnumerable<T> Neighbors(T vertex)

Parameters

vertex T

The vertex whose neighbors are requested.

Returns

IEnumerable<T>

The neighboring vertices.

Exceptions

ArgumentNullException

vertex is null.

ArgumentException

vertex is not in the graph.

RemoveEdge(T, T)

Removes the edge between the specified vertices.

public bool RemoveEdge(T from, T to)

Parameters

from T

The source vertex.

to T

The destination vertex.

Returns

bool

true if the edge existed and was removed; otherwise, false.

Exceptions

ArgumentNullException

Either vertex is null.

RemoveVertex(T)

Removes a vertex and every edge incident to it.

public bool RemoveVertex(T vertex)

Parameters

vertex T

The vertex to remove.

Returns

bool

true if the vertex was found and removed; otherwise, false.

Exceptions

ArgumentNullException

vertex is null.

TryAddEdge(T, T, double)

Attempts to add a weighted edge between the specified vertices without overwriting an existing edge.

public bool TryAddEdge(T from, T to, double weight = 1)

Parameters

from T

The source vertex.

to T

The destination vertex.

weight double

The finite, non-negative edge weight.

Returns

bool

true if the edge was added; false if it already existed.

Exceptions

ArgumentNullException

Either vertex is null.

ArgumentOutOfRangeException

weight is not a finite, non-negative number (it is NaN, infinite, or negative).

TryGetEdgeWeight(T, T, out double)

Attempts to get the weight of the edge between the specified vertices.

public bool TryGetEdgeWeight(T from, T to, out double weight)

Parameters

from T

The source vertex.

to T

The destination vertex.

weight double

When this method returns, contains the edge weight if found; otherwise, zero.

Returns

bool

true if the edge exists; otherwise, false.

Exceptions

ArgumentNullException

Either vertex is null.

WeightedNeighbors(T)

Returns the neighbors of the specified vertex paired with their edge weights.

public IEnumerable<(T Neighbor, double Weight)> WeightedNeighbors(T vertex)

Parameters

vertex T

The vertex whose weighted neighbors are requested.

Returns

IEnumerable<(T Neighbor, double Weight)>

The neighboring vertices and the weights of the edges reaching them.

Exceptions

ArgumentNullException

vertex is null.

ArgumentException

vertex is not in the graph.

Applies to

Product	Versions
.NET	8, 10