SharpGraph 1.5.3

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

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

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,2222222222222222

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

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

Is 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

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"
      }
    }
  ]
}

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

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

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