A simple graph data structure specifically written to be compatible with the Unity game engine, but perfectly usable on it's own.
It's been compiled under the .Net 3.5 runtime
In trying to find a good graph library for Unity I found many that were compatible with Mono but wouldn't work with Unity. So I decided to create yet another one, but make sure it was compatible in the hopes that the next poor soul that comes along looking for a graph library won't have to go through what I did.
This library is in its early stages, but the functionality that's here is well tested.
You can find the releases here.
To make it available to your Unity project, download the MonoGraph.dll
and place it somewhere in your project's Assets
folder.
using MonoGraph;
using System;
var stringGraph = new AdjacencyListGraph<string, Edge<string>>();
// Add vertices to graph
stringGraph.AddVertex("a");
stringGraph.AddVertex("b");
stringGraph.AddVertex("d");
stringGraph.AddVertex("e");
// Add edges to graph: a->b, a->c, a->d, b->c, b->e
stringGraph.AddDirectedEdge(new Edge<string>("a", "b"));
stringGraph.AddDirectedEdge(new Edge<string>("a", "c"));
stringGraph.AddDirectedEdge(new Edge<string>("a", "d"));
stringGraph.AddDirectedEdge(new Edge<string>("b", "c"));
stringGraph.AddDirectedEdge(new Edge<string>("b", "e"));
// Find all edges going out from "a"
foreach(var edge in stringGraph.EdgeIterator("a"){
System.WriteLine(string.Format("{0} goes to {1}", edge.Start, edge.End);
}
// Outputs:
// a goes to b
// a goes to c
// a goes to d
The libary tends toward being simple and modular. It doesn't do a whole lot for you, but provides a base you can build off of.
Currently the only implementation. It might more accurately be called an AdjacencyDictionaryGraph as it stores vertices and their edges as TVertex, List<TEdge>>
pairs in a dictionary, where TEdge and TVertex are the types chosen for your vertices and edges.
AdjacencyListGraph<TVertex, TEdge>()
In general TVertex will be a string
or int
and TEdge will be the Edge<TVertex>
class provided by this library
var stringGraph = new AdjacencyListGraph<string, Edge<string>>();
var intGraph = new AdjacencyListGraph<int, Edge<int>>();
Note that the type of vertex and the type of the Edge
must match
Vertices are added using AdjacencyListGraph.AddVertex(TVertex vertex)
stringGraph.AddVertex("a");
intGraph.AddVertex(42);
Note: Edges must be between vertices that already exist in the graph or an VertexNotFoundException
will be thrown.
Edges are added using either AdjacencyListGraph.AddDirectedEdge(TEdge edge)
or AdjacencyListGraph.AddBidirectionalEdge(TEdge edge)
AddBidirectionalEdge
creates 2 edges, 1 in both directions
// Assume both vertices already both exist in the graph
stringGraph.AddDirectedEdge(new Edge<string>("a", "b"));
stringGraph.AddBidirectionalEdge(new Edge<string>("c", "d"));
// Equivalent to:
stringGraph.AddDirectedEdge(new Edge<string>("c", "d"));
stringGraph.AddDirectedEdge(new Edge<string>("d", "c"));
Using AdjacencyListGraph.VertexIterator()
foreach(string vertex in stringGraph.VertexIterator()){
Console.WriteLine(vertex);
}
Using AdjacencyListGraph.EdgeIterator(TVertex vertex)
// Find all neighbors of "a"
Console.WriteLine("Neighbors of a:");
foreach(var edge in stringGraph.EdgeIterator("a")){
Console.WriteLine(string.Format("a leads to {0}", edge.End));
}
// Outputs:
// Neighbors of a:
// a leads to b
// a leads to c
// etc
Using AdjacencyListGraph.AllEdgeIterator()
// Assume graph has edges a->b, a->c, b->c, c->a
Console.WriteLine("All edges:");
foreach(var edge in stringGraph.AllEdgeIterator()){
Console.WriteLine(string.Format("{0}->{1}"));
}
// Outputs:
// All edges:
// b->c
// c->a
// a->b
// a->c
Vertices can be any hashable type (int
, string
, user defined classes, etc).
Edges can any hashable type that implements the IEdgeInterface
from this libaray. It's essentially a tuple of two vertices, Start
, and End
.
An Edge
type is included that should cover your basic needs
A type that implements the IEdgeInterface
must have properties Start
and End
It must also implement a method Reversed
that returns a new copy of itself with Start
and End
reversed so that
new CustomEdge<int>(1, 2).Reversed() == new CustomEdge<int>(2, 1) // => true
Right now, only an implementation of Dijkstra's shortest path algorithm comes with the libary. More algorithms will be added as I make them or get PRs.
Algorithms are implemented as classes in the MonoGraph.Algorithms
namespace
This computes the shortest path from a starting vertex to all other vertices in the graph.
It takes in a graph object and a dictionary mapping edges to their costs.
After creating the DijkstraShortestPath
object, run DijkstraShortestPath.ComputeAllFromVertex(TVertex startVertex)
. Results will be stored in the fields:
Dictionary<TVertex, double> ComputedCosts;
Dictionary<TVertex, TVertex> ComputedPaths;
and will only contain valid data after the computation has finished
// Create the graph
var testGraph = new AdjacencyListGraph<string, Edge<string>>;
// List of all vertices in graph
var vertices = new List<string> {"a", "b", "c", "d", "e"};
// Costs for crossing an edge
// This example shows that when getting a to b it's quicker to go the path a->d->c->b
// than it is to go a->b because of the higher cost of a->b
var edgesCosts = new Dictionary<Edge<string>, double> {
{new Edge<string>("a", "d"), 3.0},
{new Edge<string>("a", "b"), 20.0},
{new Edge<string>("a", "e"), 2.0},
{new Edge<string>("d", "c"), 2.0},
{new Edge<string>("c", "b"), 2.0},
{new Edge<string>("e", "d"), 2.0}
};
// Add each vertex to the graph
foreach(var vertex in vertices){
testGraph.AddVertex(vertex);
}
// Add each edge to the graph
foreach(var edge in edgesCosts.Keys){
testGraph.AddDirectedEdge(edge);
}
// Create shortest path object
var shortestPath = new Algorithms.DijkstraShortestPath<string, Edge<string>>;
// Run the computation
shortestPath.ComputeAllFromVertex("a");
// Cost from "a" to "b" is 7
shortestPath.ComputedCosts["b"]; // => 7
// Paths are stored in shortestPath.ComputedPaths
// Path from a to b is determined in reverse order
shortestPath.ComputedPaths["b"]; // -> c
shortestPath.ComputedPaths["c"]; // -> d
shortestPath.ComputedPaths["d"]; // -> a
// a->d->c->b