Table of Contents

Class DirectedGraph<TVertex, TEdge>

Namespace
Graph1x
Assembly
Graph1x.dll

A simple directed graph (no parallel edges, self-loops allowed) backed by adjacency lists with separate out- and in-edge indexes for O(1) edge lookup in either direction.

public class DirectedGraph<TVertex, TEdge> : IDirectedGraph<TVertex, TEdge>, IMutableGraph<TVertex, TEdge>, IReadOnlyGraph<TVertex, TEdge> where TVertex : notnull where TEdge : IEdge<TVertex>

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Inheritance
DirectedGraph<TVertex, TEdge>
Implements
IDirectedGraph<TVertex, TEdge>
IMutableGraph<TVertex, TEdge>
IReadOnlyGraph<TVertex, TEdge>
Derived
Inherited Members
Extension Methods

Constructors

DirectedGraph()

Initializes an empty graph using the default vertex comparer.

public DirectedGraph()

DirectedGraph(IEqualityComparer<TVertex>)

Initializes an empty graph using vertexComparer to identify vertices.

public DirectedGraph(IEqualityComparer<TVertex> vertexComparer)

Parameters

vertexComparer IEqualityComparer<TVertex>

The comparer used to identify vertices.

Exceptions

ArgumentNullException

vertexComparer is null.

Properties

AllowsParallelEdges

Gets a value indicating whether the graph admits parallel edges between the same endpoints.

public bool AllowsParallelEdges { get; }

Property Value

bool

EdgeCount

Gets the number of edges in the graph.

public int EdgeCount { get; }

Property Value

int

Edges

Gets the edges of the graph.

public IEnumerable<TEdge> Edges { get; }

Property Value

IEnumerable<TEdge>

IsDirected

Gets a value indicating whether edges are directed.

public bool IsDirected { get; }

Property Value

bool

VertexComparer

Gets the comparer used to identify vertices.

public IEqualityComparer<TVertex> VertexComparer { get; }

Property Value

IEqualityComparer<TVertex>

VertexCount

Gets the number of vertices in the graph.

public int VertexCount { get; }

Property Value

int

Vertices

Gets the vertices of the graph.

public IEnumerable<TVertex> Vertices { get; }

Property Value

IEnumerable<TVertex>

Methods

AddEdge(TEdge)

Adds edge to the graph, adding missing endpoint vertices automatically.

public virtual bool AddEdge(TEdge edge)

Parameters

edge TEdge

The edge to add.

Returns

bool

true if added; false if the graph forbids the edge (e.g. a parallel edge on a simple graph).

AddVertex(TVertex)

Adds vertex to the graph.

public bool AddVertex(TVertex vertex)

Parameters

vertex TVertex

The vertex to add.

Returns

bool

true if added; false if it was already present.

AdjacentEdges(TVertex)

Gets the edges incident to vertex. On directed graphs this includes both incoming and outgoing edges.

public IEnumerable<TEdge> AdjacentEdges(TVertex vertex)

Parameters

vertex TVertex

The vertex whose incident edges to enumerate.

Returns

IEnumerable<TEdge>

The incident edges.

Exceptions

ArgumentException

The vertex is not in the graph.

Clear()

Removes every vertex and edge from the graph.

public void Clear()

ContainsEdge(TVertex, TVertex)

Determines whether the graph contains an edge between source and target. On undirected graphs the endpoint order is irrelevant.

public bool ContainsEdge(TVertex source, TVertex target)

Parameters

source TVertex

The first endpoint.

target TVertex

The second endpoint.

Returns

bool

true if such an edge is present.

ContainsVertex(TVertex)

Determines whether the graph contains vertex.

public bool ContainsVertex(TVertex vertex)

Parameters

vertex TVertex

The vertex to look up.

Returns

bool

true if the vertex is present.

Degree(TVertex)

Gets the degree of vertex. Self-loops count twice on undirected graphs; on directed graphs the degree is in-degree plus out-degree.

public int Degree(TVertex vertex)

Parameters

vertex TVertex

The vertex to measure.

Returns

int

The number of edge endpoints incident to the vertex.

Exceptions

ArgumentException

The vertex is not in the graph.

InDegree(TVertex)

Gets the number of edges entering vertex.

public int InDegree(TVertex vertex)

Parameters

vertex TVertex

The vertex to measure.

Returns

int

The in-degree.

Exceptions

ArgumentException

The vertex is not in the graph.

InEdges(TVertex)

Gets the edges entering vertex.

public IEnumerable<TEdge> InEdges(TVertex vertex)

Parameters

vertex TVertex

The vertex whose incoming edges to enumerate.

Returns

IEnumerable<TEdge>

The incoming edges.

Exceptions

ArgumentException

The vertex is not in the graph.

OutDegree(TVertex)

Gets the number of edges leaving vertex.

public int OutDegree(TVertex vertex)

Parameters

vertex TVertex

The vertex to measure.

Returns

int

The out-degree.

Exceptions

ArgumentException

The vertex is not in the graph.

OutEdges(TVertex)

Gets the edges leaving vertex.

public IEnumerable<TEdge> OutEdges(TVertex vertex)

Parameters

vertex TVertex

The vertex whose outgoing edges to enumerate.

Returns

IEnumerable<TEdge>

The outgoing edges.

Exceptions

ArgumentException

The vertex is not in the graph.

RemoveEdge(TVertex, TVertex)

Removes the edge from source to target, whatever its payload.

public bool RemoveEdge(TVertex source, TVertex target)

Parameters

source TVertex

The source endpoint.

target TVertex

The target endpoint.

Returns

bool

true if an edge was removed.

RemoveEdge(TEdge)

Removes edge from the graph. Endpoint vertices stay.

public bool RemoveEdge(TEdge edge)

Parameters

edge TEdge

The edge to remove.

Returns

bool

true if removed; false if it was not present.

Remarks

The stored edge must equal edge under the edge type's default equality — VertexComparer locates the endpoints but never compares payloads. To remove an edge by its endpoints alone, use the endpoint-based overloads on the concrete graph types.

RemoveVertex(TVertex)

Removes vertex and every edge incident to it.

public bool RemoveVertex(TVertex vertex)

Parameters

vertex TVertex

The vertex to remove.

Returns

bool

true if removed; false if it was not present.

Edit this page