The Graph Theory in C# (Part 9)
The Graph needs to be smart and self-validating. Likewise, it should be lightweight. The finishing touches give the Graph its proper constructor and a method that ultimately ends my quest.
The Graph should be easy to create. Just instantiate a new one. Optionally, you can give it a name and you're ready to load it up with vertices and edges.
Finally, I added a method to create the graph's DOT representation.
Voila!
The Graph should be easy to create. Just instantiate a new one. Optionally, you can give it a name and you're ready to load it up with vertices and edges.
public string Name { get; set; }
public Graph(string name = "graph")
{
Name = name;
}
This code defines a constructor that can optionally accept a name. The Graph's default Name is "graph".Finally, I added a method to create the graph's DOT representation.
public string ToDOTString()
{
StringBuilder sb = new StringBuilder();
bool undirected = Edges.AsParallel()
.Where((edge) => !edge.Value.Directed)
.Count() > 0;
sb.AppendLine((undirected ? "" : "di") + "graph "
+ Name + " {");
foreach (var edgeName in Edges.Keys)
{
sb.AppendLine(" " + edgeName + ";");
}
sb.AppendLine("}");
return sb.ToString();
}
And that, ladies and gentlemen, seals the deal! Below is the full code.
Graph.cs
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Text;
namespace Mendz.Graphs
{
public class Graph
{
public string Name { get; set; }
private ConcurrentDictionary<int, Vertex> _vertices =
new ConcurrentDictionary<int, Vertex>();
public ReadOnlyDictionary<int, Vertex> Vertices
{
get
{
return new ReadOnlyDictionary<int, Vertex>(_vertices);
}
}
public int Order
{
get
{
return _vertices.Count;
}
}
private ConcurrentDictionary<string, Edge> _edges =
new ConcurrentDictionary<string, Edge>();
public ReadOnlyDictionary<string, Edge> Edges
{
get
{
return new ReadOnlyDictionary<string, Edge>(_edges);
}
}
public int Size
{
get
{
return _edges.Count;
}
}
public Graph(string name = "graph")
{
Name = name;
}
public bool AddVertex(object value)
{
return AddVertex(new Vertex(value));
}
public bool AddVertex(Vertex vertex)
{
return _vertices.TryAdd(vertex.ID, vertex);
}
public Vertex RemoveVertex(int id)
{
object o = new object();
_edges
.AsParallel()
.Where((edge) =>
edge.Value.Tail.ID == id || edge.Value.Head.ID == id)
.ForAll((edge) =>
{
lock (o)
{
RemoveEdge(edge.Key);
}
});
Vertex removedVertex;
_vertices.TryRemove(id, out removedVertex);
return removedVertex;
}
public Vertex RemoveVertex(Vertex vertex)
{
return RemoveVertex(vertex.ID);
}
public bool AddEdge(int tailID, int headID,
bool directed = false, int weight = 0, string label = "")
{
return AddEdge(Edge.Create(_vertices[tailID], _vertices[headID],
directed, weight, label));
}
protected bool AddEdge(Edge edge)
{
return _edges.TryAdd(edge.Name, edge);
}
public Edge RemoveEdge(string name)
{
Edge removedEdge;
_edges.TryRemove(name, out removedEdge);
return removedEdge;
}
public Edge RemoveEdge(Edge edge)
{
return RemoveEdge(edge.Name);
}
public string ToDOTString()
{
StringBuilder sb = new StringBuilder();
bool undirected = Edges.AsParallel()
.Where((edge) => !edge.Value.Directed)
.Count() > 0;
sb.AppendLine((undirected ? "" : "di") + "graph "
+ Name + " {");
foreach (var edgeName in Edges.Keys)
{
sb.AppendLine(" " + edgeName + ";");
}
sb.AppendLine("}");
return sb.ToString();
}
}
}
A quick test is to create a console application, instantiate Graph graph = new Graph(); fill up graph.Vertices and graph.Edges; and print out using graph.ToDOTString(). The result is your graph in DOT notation, which can be fed in to graph rendering and visualization tools. A Microsoft Research product called MSAGL should be of interest (and should I mention open-source at GitHub?). If your test generated a DOT successfully, try visualizing it using http://rise4fun.com/agl/.Voila!
Comments
Post a Comment