SharpGraph 1.5.7

SharpGraph

A powerful C# graph library, made by Dirk-Jan Meijer.

Nuget

Getting started

You only need to create two classes in order to use the SharpGraph library.

1. A vertex class, which represents a node.
2. An edge class, which represents a connection between two vertices.

The vertex class should extend the Vertex base class and the edge class should extend either the Line class (undirected edge) or the Arrow class (directed edge).

For a number of types there are special Vertex classes available.

• DecimalValueTypeVertex
• DoubleValueTypeVertex
• FloatValueTypeVertex
• GuidValueTypeVertex
• IntValueTypeVertex
• LongValueTypeVertex
• StringValueTypeVertex

Example code

This is a simplified example of how to create a graph with SharpGraph and search for the shortest path between two cities.

This builds a graph with 4 cities connected to each other.

using SharpGraph.Core;
using SharpGraph.Core.Elements;
using SharpGraph.Core.Elements.ValueTypes;

var graph = new Graph<City, Road>();
var amsterdam = new City("Amsterdam");
var london = new City("London");
var berlin = new City("Berlin");
var paris = new City("Paris");
var amsterdamLondon = new Road(amsterdam, london, "AMS-LON", 540);
var amsterdamBerlin = new Road(amsterdam, berlin, "AMS-BER", 660);
var amsterdamParis = new Road(amsterdam, paris, "AMS-PAR", 506);
var londonBerlin = new Road(london, berlin, "LON-BER", 1100);
var londonParis = new Road(london, paris, "LON-PAR", 470);
var berlinParis = new Road(berlin, paris, "BER-PAR", 1058);
graph
    .AddVertex(amsterdam)
    .AddVertex(london)
    .AddVertex(berlin)
    .AddVertex(paris)
    .AddEdge(amsterdamLondon)
    .AddEdge(amsterdamBerlin)
    .AddEdge(amsterdamParis)
    .AddEdge(londonBerlin)
    .AddEdge(londonParis)
    .AddEdge(berlinParis);

public class City(string name) : StringValueTypeVertex(name);

public class Road(City source, City target, string name, int distance) : Line<City>(source, target)
{
    public string Name { get; } = name;

    public int Distance { get; set; } = distance;

    public override int GetHashCode() => Name.GetStableHashCode();

    public override bool Equals(Line<City>? other)
    {
        if (ReferenceEquals(null, other)) return false;
        if (ReferenceEquals(this, other)) return true;
        if (other.GetType() != GetType()) return false;
        var otherCasted = (Road)other;
        return string.Equals(Name, otherCasted.Name, StringComparison.OrdinalIgnoreCase);
    }
}

Then we find the shortest path between Paris and Berlin.

var shortestPath = graph.ShortestPath(paris, berlin, r => r.Distance);
var roads = string.Join(",", shortestPath.Path.Select(r => r.Name));
var description = $"{roads} in {shortestPath.Path.Sum(p => p.Distance)} distance";
Console.WriteLine(description);

BER-PAR in 1058 distance

We can increase the distance between Paris and Berlin.

berlinParis.Distance = 3000;

The shortest path is a different one now.

shortestPath = graph.ShortestPath(paris, berlin, r => r.Distance);
roads = string.Join(",", shortestPath.Path.Select(r => r.Name));
description = $"{roads} in {shortestPath.Path.Sum(p => p.Distance)} distance";
Console.WriteLine(description);

AMS-PAR,AMS-BER in 1166 distance

All features

The docs are incomplete at this moment, there are a lot of undocumented features!

Acyclic

Indicator whether the graph is a-cyclic: has no cycles.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("B", "C")
  .AddEdge("C", "A");

Console.WriteLine(graph.IsAcyclic());

False

Adjacency list

Return the adjacency list representation of this graph.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
    .CreateNewStringArrowType()
    .AddVertex("A")
    .AddVertex("B")
    .AddVertex("C")
    .AddEdge("A", "B")
    .AddEdge("A", "C")
    .AddEdge("B", "C");

Console.WriteLine(graph.ToAdjacencyListString());

A ->B ->C
B ->C
C

Adjacency matrix

Return the adjacency matrix representation of this graph.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
    .CreateNewStringArrowType()
    .AddVertex("A")
    .AddVertex("B")
    .AddVertex("C")
    .AddEdge("A", "B")
    .AddEdge("A", "C")
    .AddEdge("B", "C");

Console.WriteLine(graph.ToAdjacencyMatrixString());

  A B C
A 0 1 1
B 0 0 1
C 0 0 0

All edge paths

Get all edge paths between a given source and target vertex.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var vertexA = new StringValueTypeVertex("A");
var vertexB = new StringValueTypeVertex("B");
var vertexC = new StringValueTypeVertex("C");
var vertexD = new StringValueTypeVertex("D");
var edgeAtoB = new StringValueTypeArrow("AB", vertexA, vertexB);
var edgeAtoC = new StringValueTypeArrow("AC", vertexA, vertexC);
var edgeBtoD = new StringValueTypeArrow("BD", vertexB, vertexD);
var edgeCtoD = new StringValueTypeArrow("CD", vertexC, vertexD);
var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex(vertexA)
  .AddVertex(vertexB)
  .AddVertex(vertexC)
  .AddVertex(vertexD)
  .AddEdge(edgeAtoB)
  .AddEdge(edgeAtoC)
  .AddEdge(edgeBtoD)
  .AddEdge(edgeCtoD);
var allEdgePaths = graph
  .AllEdgePaths(new StringValueTypeVertex("A"), new StringValueTypeVertex("D"), 10);
foreach (var path in allEdgePaths) Console.WriteLine(path);

A->B(AB), B->D(BD)
A->C(AC), C->D(CD)

All vertex paths

Get all vertex paths between a given source and target vertex.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var vertexA = new StringValueTypeVertex("A");
var vertexB = new StringValueTypeVertex("B");
var vertexC = new StringValueTypeVertex("C");
var vertexD = new StringValueTypeVertex("D");
var edgeAtoB = new StringValueTypeArrow("AB", vertexA, vertexB);
var edgeAtoC = new StringValueTypeArrow("AC", vertexA, vertexC);
var edgeBtoD = new StringValueTypeArrow("BD", vertexB, vertexD);
var edgeCtoD = new StringValueTypeArrow("CD", vertexC, vertexD);
var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex(vertexA)
  .AddVertex(vertexB)
  .AddVertex(vertexC)
  .AddVertex(vertexD)
  .AddEdge(edgeAtoB)
  .AddEdge(edgeAtoC)
  .AddEdge(edgeBtoD)
  .AddEdge(edgeCtoD);
var allVertexPaths = graph
  .AllVertexPaths(new StringValueTypeVertex("A"), new StringValueTypeVertex("D"), 10);
foreach (var path in allVertexPaths) Console.WriteLine(path);

A, B, D
A, C, D

Cycles

Indicator whether the graph has cycles.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("B", "C")
  .AddEdge("C", "A");

Console.WriteLine(graph.HasCycles());

True

Dense

Indicator whether the graph is dense.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("A", "C");

Console.WriteLine(graph.IsDense());

False

Density

The ratio between the current number of edges to the maximum number of edges possible in the graph.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("A", "C");

Console.WriteLine(graph.Density());

0,3333333333333333

Note that the density for undirected graphs is a factor 2 higher.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringLineType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("A", "C");

Console.WriteLine(graph.Density());

0,6666666666666666

Depth first search

Create a depth-first search object which can be given a vertex callback and a stop on cycle detection flag. To get the DFS results, just call .Compute().

using System.Text;
using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddVertex("D")
  .AddVertex("E")
  .AddVertex("F")
  .AddEdge("A", "B")
  .AddEdge("B", "C")
  .AddEdge("C", "D")
  .AddEdge("C", "E")
  .AddEdge("E", "F");

var graphWalkedString = new StringBuilder();
graph
  .DepthFirstSearch()
  .SetVertexCallback((_, v) => graphWalkedString.Append(v.Name))
  .Compute(null, _ => false);
Console.WriteLine(graphWalkedString);

ABCDEF

Depth first search with stop condition

Create a depth-first search object which can be given a vertex callback and a stop on cycle detection flag. To get the DFS results, just call .Compute().

using System.Text;
using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddVertex("D")
  .AddVertex("E")
  .AddVertex("F")
  .AddEdge("A", "B")
  .AddEdge("B", "C")
  .AddEdge("C", "D")
  .AddEdge("C", "E")
  .AddEdge("E", "F");

var graphWalkedString = new StringBuilder();
graph
  .DepthFirstSearch()
  .SetVertexCallback((_, v) => graphWalkedString.Append(v.Name))
  .Compute(null, v => string.Equals(v.Name, "D", StringComparison.OrdinalIgnoreCase));
Console.WriteLine(graphWalkedString);

ABCD

Directed

Indicator whether the graph is a directed graph: has directed edges.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("A", "C");

Console.WriteLine(graph.IsDirected());

True

DAG, Directed Acyclic Graph

Indicator whether the graph is a directed acyclic graph.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("A", "C");

Console.WriteLine(graph.IsDirectedAcyclic());

True

Edges

Get all the edges that are currently in the graph. This example counts them.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringLineType()
  .AddVertex("A")
  .AddVertex("B")
  .AddEdge("A", "B");

Console.WriteLine(graph.Edges.Count);

1

Hamiltonian

Indicator whether the graph contains a Hamiltonian cycle. Note that this is a NP-complete problem: computation is extremely expensive but validating an answer is cheap.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
    .CreateNewStringLineType()
    .AddVertex("A")
    .AddVertex("B")
    .AddVertex("C")
    .AddVertex("D")
    .AddVertex("E")
    .AddVertex("F")
    .AddEdge("A", "B")
    .AddEdge("B", "E")
    .AddEdge("E", "D")
    .AddEdge("D", "F")
    .AddEdge("F", "C")
    .AddEdge("C", "A");

Console.WriteLine(graph.IsHamiltonian());

True

Hamiltonian cycles

Get all the Hamiltonian cycles in the graph. A Hamiltonian cycle is a cycle that visits each vertex exactly once.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
    .CreateNewStringLineType()
    .AddVertex("A")
    .AddVertex("B")
    .AddVertex("C")
    .AddVertex("D")
    .AddVertex("E")
    .AddVertex("F")
    .AddEdge("A", "B")
    .AddEdge("B", "E")
    .AddEdge("E", "D")
    .AddEdge("D", "F")
    .AddEdge("F", "C")
    .AddEdge("C", "A");

foreach (var cycle in graph.HamiltonianCycles())
{
    Console.WriteLine(string.Join(" -> ", cycle));
}

A -> C -> F -> D -> E -> B
A -> B -> E -> D -> F -> C
B -> E -> D -> F -> C -> A
B -> A -> C -> F -> D -> E
C -> F -> D -> E -> B -> A
C -> A -> B -> E -> D -> F
D -> F -> C -> A -> B -> E
D -> E -> B -> A -> C -> F
E -> D -> F -> C -> A -> B
E -> B -> A -> C -> F -> D
F -> D -> E -> B -> A -> C
F -> C -> A -> B -> E -> D

Maximum depth

Compute the maximum depth of the graph. The depth is the length of the longest path from the source to a sink. Can only be computed for a tree.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddVertex("D")
  .AddVertex("E")
  .AddEdge("A", "B")
  .AddEdge("A", "C")
  .AddEdge("B", "D")
  .AddEdge("D", "E");

Console.WriteLine(graph.MaximumDepth());

3

Multi graph

Indicator whether the graph is a multi graph: has multiple edges between the same vertices.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("A", "C")
  .AddEdge(new StringValueTypeArrow("A to B", new StringValueTypeVertex("A"), new StringValueTypeVertex("B")));

Console.WriteLine(graph.IsMultiGraph());

True

Sinks

Get all the sinks: the vertices with no outgoing arrows. Only applies for a directed graph, where the edges are directed. Also known as leaf nodes.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddEdge("A", "B");

foreach(var vertex in graph.Sinks) Console.WriteLine(vertex);

B

Sources

Get all the sources: the vertices with no incoming arrows. Only applies for a directed graph, where the edges are directed.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddEdge("A", "B");

foreach(var vertex in graph.Sources) Console.WriteLine(vertex);

A

Sparse

Indicator whether the graph is sparse: density lower than 0.5, see also the density property.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("A", "C");

Console.WriteLine(graph.IsSparse());

True

ToJson

Serialize the graph to a json format.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringLineType()
  .AddVertex("A")
  .AddVertex("B")
  .AddEdge("A", "B");

Console.Write(graph.ToJson());

{
  "Vertices": [
    {
      "Id": "fe3cf531-ebbf-4ebc-a710-a65a4d4299e6",
      "Data": {
        "Name": "A"
      }
    },
    {
      "Id": "f44f3e78-0364-4e94-847b-59acc4d01aa4",
      "Data": {
        "Name": "B"
      }
    }
  ],
  "Edges": [
    {
      "Point1Id": "fe3cf531-ebbf-4ebc-a710-a65a4d4299e6",
      "Point2Id": "f44f3e78-0364-4e94-847b-59acc4d01aa4",
      "Data": {
        "Name": "AB"
      }
    }
  ]
}

Tree

Indicator whether this graph is a tree: a DAG, single source, backward branching always 1.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringArrowType()
  .AddVertex("A")
  .AddVertex("B")
  .AddVertex("C")
  .AddEdge("A", "B")
  .AddEdge("A", "C");

Console.WriteLine(graph.IsTree());

True

Vertices

Get all the vertices that are currently in the graph. This example counts them.

using SharpGraph.Core;
using SharpGraph.Core.Elements.ValueTypes;

var graph = GraphFactory
  .CreateNewStringLineType()
  .AddVertex("A")
  .AddVertex("B")
  .AddEdge("A", "B");

Console.WriteLine(graph.Vertices.Count);

2

Test coverage

The unit test line coverage is currently 61.5%. This is run by

dotnet test --collect:"XPlat Code Coverage"

reportgenerator \
  -reports:"**/TestResults/**/coverage.cobertura.xml" \
  -targetdir:"coveragereport" \
  -reporttypes:Html