Reviewing Mendz.Graphs.Vertex

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. This article focuses on the Vertex.

The Vertex class is pretty solid, but it has a weak link. Originally, I was thinking that making the IDGenerator a nested static class would help make sure that each Vertex is created with a unique ID. However, I realized that if another thread or parallel process decides to seed the IDGenerator, all new vertices thereafter will get ID values from the new seed, which can create gaps in the ID series, missing on and wasting away possible ID values.

Pulling the IDGenerator out as a class on its own allows developers to have more control on how IDs are generated. For example, developers can create individually seeded instances for each thread that creates vertices. As a class all its own, the IDGenerator can be used wherever and whenever runtime generated IDs are needed. The IDGenerator is no longer exclusive to the Vertex.

IDGenerator.cs
using System;
using System.Threading;

namespace Mendz.Library
{
    public class IDGenerator
    {
        private object o = new object();
        private volatile int _id = 1;

        public IDGenerator(int seed = 1)
        {
            Seed(seed);
        }

        public void Seed(int seed)
        {
            lock (o)
            {
                if (seed < 1)
                {
                    throw new ArgumentOutOfRangeException("seed", 
                        "The seed cannot be less than 1.");
                }
                if (_id < seed)
                {
                    _id = seed;
                }
            }
        }

        public int Generate()
        {
            lock (o)
            {
                int id = _id;
                _id = Interlocked.Increment(ref _id);
                return id;
            }
        }
    }
}

This code defines a thread-safe IDGenerator in Mendz.Library. The private field for the ID is set to volatile. In the Seed() method, seeding is wrapped in a lock block. In the Generate() method, wrapped in a lock block, I used Interlocked to increment the ID. This construct prevents Generate() from clashing with a concurrent/parallel call to Seed(), and vice versa.

Without its own IDGenerator, the Vertex can no longer be created by just passing a value/object. Creating a Vertex now requires that the ID is always passed along with the value/object. Thus, the constructor that accepts only a value/object must be removed.

The new Vertex class now has a Weight property. This addition gives support for vertex-weighted graphs.

The new Vertex class also inherits IComparable, which is implemented to compare by Vertex.ID. This allows collections of Vertex instances (ex. Vertex[] _indexedVertices;) to be sorted directly (ex. Array.Sort(_indexedVertices);) without having to extract or store copies of the vertex IDs.

The overall design of the Vertex remains the same. It's still basically a container for an ID and an object value. To save memory, the value may be the same as the ID, or perhaps any simple type (ex. GUID) that can be used to lazy load or refer to a domain object instance.

Vertex.cs
namespace Mendz.Graphs
{
    public class Vertex : IComparable<Vertex>
    {
        public int ID { get; private set; }

        public object Value { get; set; }

        public double Weight { get; set; }

        public Vertex(int id, object value)
        {
            ID = id;
            Value = value;
        }

        #region Overrides
        public override bool Equals(object obj)
        {
            if (obj == null || !(obj is Vertex))
            {
                return false;
            }
            return ID == ((Vertex)obj).ID;
        }

        public override int GetHashCode()
        {
            return ID;
        }
        #endregion

        #region Implements
        public int CompareTo(Vertex other)
        {
            return ID.CompareTo(other.ID);
        }
        #endregion
    }
}

Update: Added the Weight property.