SharpGraph 1.4.4

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).

Example code

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

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

// Initialize the graph.
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);

// 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);

// 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);

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);
    }
}

This gives the following result on the console.

BER-PAR in 1058 distance
AMS-PAR,AMS-BER in 1166 distance

All features

Adjacency list

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());

This will output the following adjacency matrix.

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

Adjacency matrix

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());

This will output the following adjacency matrix.

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

All edge paths

using MoreLinq.Extensions;
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);
allEdgePaths.ForEach(Console.WriteLine);

This will output the following paths.

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

All vertex paths

using MoreLinq.Extensions;
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
    .AllVertexPaths(new StringValueTypeVertex("A"), new StringValueTypeVertex("D"), 10);
allEdgePaths.ForEach(Console.WriteLine);

This will output the following paths.

A, B, D
A, C, D

Depth first search

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(v => string.Equals(v.Name, "D", StringComparison.OrdinalIgnoreCase));
Console.WriteLine(graphWalkedString);

This will output the following string.

ABCD

Hamiltonian property

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());

This will output the following boolean.

True

Hamiltonian cycles

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