Reviewing Mendz.Graphs.Graph
The Graph Theory in C# presented the Graph, Vertex and Edge classes to implement the graph theory's definition of a graph: G = (V, E). While reviewing Mendz.Graphs for memory and performance optimization, it went through dramatic changes and enhancements. Previously, I reviewed the Vertex and Edge. This article focuses on the Graph.
The changes to the Vertex have no impact to the Graph. The changes to the Edge, however, require a lot of changes to the Graph. Most of the changes are really around the new Edge.ID, which is now a tuple. In the original version of the Graph, it used the Edge.Name as key to identify an edge in Graph.Edges. Now, the Edge.ID is used. From string to tuple is a breaking change, but it has to be done... and so be it.
The changes to the Vertex have no impact to the Graph. The changes to the Edge, however, require a lot of changes to the Graph. Most of the changes are really around the new Edge.ID, which is now a tuple. In the original version of the Graph, it used the Edge.Name as key to identify an edge in Graph.Edges. Now, the Edge.ID is used. From string to tuple is a breaking change, but it has to be done... and so be it.
- In line with the Edge, the Graph is also changed into a sealed class. I needed the Graph to equally enforce the rule which states that the edge's endpoints should be vertices that exist in Graph.Vertices. This will prevent anyone from extending the Graph that can break the rule. As a consolation, I decided to add a dynamic Expansion property, which will allow developers to dynamically add attributes to the Graph.
- The internal edges collection has been modified from using Edge.Name to using Edge.ID as key, a tuple (int tail, int directed, int head). Note that this feature requires the System.ValueTuple NuGet package. The primary reason for this is for indexing. As strings with numeric values, edge names don't sort as I want them to. Edge.ID sorts numerically, which is the desired behavior.
- The Vertices and Edges properties have been modified so that each no longer creates a new ReadOnlyDictionary instance every time the property is called. Their respective ReadOnlyDictionary instances are instead initialized in the constructor. Granted that ReadOnlyDictionary is just a wrapper to the internal vertices and edges collections, changes to either vertices or edges are automatically available to their corresponding ReadOnlyDictionary wrapper instance.
- Note that the Vertices and Edges properties expose access to items via ReadOnlyCollection wrappers. GetVertex() and GetEdge() methods have been created to access items in the internal vertices and edges directly. These are really just syntactic sugar for those who like working with getter methods. There is no promise that these should work better or faster than going through the Vertices and Edges properties.
- ToDOTString() has been renamed to override ToString() instead. This decision aligns with the Edge.ToString() implementation, which also returns a DOT notation. Just like in the Edge, as a consolation, I also gave the Graph its own ToStringByValue() method, which internally uses Edge.ToStringByValue().
- I added indexing support. This is the most important enhancement to the Graph. It is also the most challenging and nerve-wracking aspect to work on, mostly because I couldn't decide on what type to use. In the end, I decided on a simple Array, which has a BinarySearch() method that I want to take advantage of. The Graph has new indexing methods: IndexVertices() and IndexEdges(). When called, the Graph maintains internal copies of the indexes created by these methods.
- As a consequence of the Graph maintaining internal copies of the indexes, the Add/RemoveVertex and Add/RemoveEdge methods have been modified to include the internal copies of the indexes in their maintenance. Basically, changes to the Graph data can invalidate and void the index. By simply setting the index to null, calling its index method recreates the index. In general, it is recommended that all calls to Add*/Remove*() methods are done before calling the index methods.
Graph.cs
using System;
using System.Collections.Concurrent;
using System.Collections.ObjectModel;
using System.Linq;
using System.Text;
using System.Threading;
namespace Mendz.Graphs
{
public sealed class Graph
{
private object o = new object();
private object iv = new object();
private object ie = new object();
private volatile int _directedEdgeCount = 0;
public string Name { get; set; }
private ConcurrentDictionary<int, Vertex> _vertices =
new ConcurrentDictionary<int, Vertex>();
private ReadOnlyDictionary<int, Vertex> _readOnlyVertices;
public ReadOnlyDictionary<int, Vertex> Vertices
{
get
{
return _readOnlyVertices;
}
}
private Vertex[] _indexedVertices = null;
public int Order
{
get
{
return _vertices.Count;
}
}
private ConcurrentDictionary<(int tail, int directed, int head), Edge> _edges =
new ConcurrentDictionary<(int tail, int directed, int head), Edge>();
private ReadOnlyDictionary<(int tail, int directed, int head),Edge> _readOnlyEdges;
public ReadOnlyDictionary<(int tail, int directed, int head), Edge> Edges
{
get
{
return _readOnlyEdges;
}
}
private Edge[] _indexedEdges = null;
public int Size
{
get
{
return _edges.Count;
}
}
public dynamic Expansion { get; set; }
public Graph(string name = "G")
{
Name = name;
_readOnlyVertices = new ReadOnlyDictionary<int, Vertex>(_vertices);
_readOnlyEdges =
new ReadOnlyDictionary<(int tail, int directed, int head), Edge>(_edges);
}
public bool AddVertex(int id, object value)
{
return AddVertex(new Vertex(id, value));
}
public bool AddVertex(Vertex vertex)
{
lock (o)
{
if (_vertices.TryAdd(vertex.ID, vertex))
{
lock (iv)
{
_indexedVertices = null;
}
return true;
}
return false;
}
}
public Vertex RemoveVertex(int id)
{
lock (o)
{
if (_vertices.TryRemove(id, out Vertex removedVertex))
{
lock (iv)
{
_indexedVertices = null;
}
bool removed = false;
if (_edges.Count > 0)
{
object obj = new object();
_edges
.AsParallel()
.Where((edge) =>
edge.Value.Tail.ID == id || edge.Value.Head.ID == id)
.ForAll((edge) =>
{
lock (obj)
{
Edge e = RemoveEdge(edge.Key);
if (!removed && e != null)
{
removed = true;
}
}
});
}
if (removed)
{
lock (ie)
{
_indexedEdges = null;
}
}
}
return removedVertex;
}
}
public Vertex RemoveVertex(Vertex vertex)
{
return RemoveVertex(vertex.ID);
}
public Vertex GetVertex(int id)
{
return _vertices[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));
}
private bool AddEdge(Edge edge)
{
lock (o)
{
if (_edges.TryAdd(edge.ID, edge))
{
lock (ie)
{
_indexedEdges = null;
}
if (edge.Directed)
{
Interlocked.Increment(ref _directedEdgeCount);
}
return true;
}
return false;
}
}
public Edge RemoveEdge((int tail, int directed, int head) id)
{
lock (o)
{
if (_edges.TryRemove(id, out Edge removedEdge))
{
lock (ie)
{
_indexedEdges = null;
}
if (removedEdge.Directed)
{
Interlocked.Decrement(ref _directedEdgeCount);
}
}
return removedEdge;
}
}
public Edge RemoveEdge(Edge edge)
{
return RemoveEdge(edge.ID);
}
public Edge GetEdge((int tail, int directed, int head) id)
{
return _edges[id];
}
public Edge GetEdge(string name)
{
return _edges[Edge.NameToID(name)];
}
public Vertex[] IndexVertices()
{
lock (iv)
{
if (_indexedVertices == null)
{
_indexedVertices = _vertices.Values.ToArray<Vertex>();
Array.Sort(_indexedVertices);
}
return _indexedVertices;
}
}
public Edge[] IndexEdges()
{
lock (ie)
{
if (_indexedEdges == null)
{
_indexedEdges = _edges.Values.ToArray<Edge>();
Array.Sort(_indexedEdges);
}
return _indexedEdges;
}
}
public string ToStringByValue()
{
return ToString((edge) => edge.ToStringByValue());
}
private string ToString(Func<Edge, string> eval)
{
StringBuilder sb = new StringBuilder();
sb.AppendLine((_directedEdgeCount > 0 ? "di" : "") + "graph " + Name + " {");
foreach (var edge in _edges.Values)
{
sb.AppendLine(" " + eval(edge) + ";");
}
sb.AppendLine("}");
return sb.ToString();
}
#region Overrides
public override string ToString()
{
return ToString((edge) => edge.Name);
}
#endregion
}
}
Update: Changed default graph name to "G".
Comments
Post a Comment