The Graph Theory in C# (Part 8)

When I started this quest, I found out that the graph in graph theory is complicated. However, focusing on the graph's definition made it look so simple in C#. After working on the Vertex and the Edge classes, I realized that I would need to expand my Graph class to something smarter.

G = (V, E) such that V is a collection of vertices and E is a collection of (u,v) edges where u,v in V. The last phrase "where u,v in V" sets a rule that can't be ignored. The Graph should be self-validating. The edges of the graph must contain vertices that are known to the graph.

The original code of the Graph is not good enough. The Graph needs more control with how the Vertices and Edges are populated and maintained. I should therefore make them internally settable but externally readable.

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

This code creates internal stores for the vertices and edges. It also changes the exposed Vertices and Edges properties as read-only collections. Note the Order property represents the order of the graph, which by definition is the number vertices that make up the graph. Note that the Size property represents the size of the graph, which by definition is the number of edges that make up the graph.

The following codes provide the methods needed to manage the Graph's vertices.

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

This code shows how to add and remove vertices. Adding a vertex to the graph is pretty straightforward. However, removing a vertex should check that edges with endpoints containing the removed vertex are also removed.

The following codes provide the methods needed to manage the Graph's edges.

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

This code shows how to add and remove edges. Removing an edge from the graph is pretty straightforward. However, adding an edge should check that the edge's tail and head exist in the graph's vertices.

Observe that the Vertex.ID is heavily used. It is the primary way that the vertices are identified in the Graph. It is important that all vertices in the graph are assigned a unique ID.

This Graph is in better shape. A few more finishing touches and it should be ready for primetime. Meanwhile, the Graph has the ability to behave like a collection managing its collections. It adheres to the definition of the graph and is self-validating. This is exciting (nerd-talk)!