Generic graph implementation in C#

Question

I am implementing fundamental data structures in C# while trying to learn techniques in the language to make my code cleaner, more concise, and reusable. I have implemented a generic graph with a few elementary search algorithms. What are some ways to improve my implementation and coding style?

/// <summary>
/// Implementation of a generic vertex to be used in any graph
/// </summary>

class Vertex<T>
{

    List<Vertex<T>> neighbors;   
    T value;
    bool isVisited;

    public List<Vertex<T>> Neighbors { get { return neighbors; } set { neighbors = value; } }
    public T Value { get { return value; } set { this.value = value; } }
    public bool IsVisited { get { return isVisited; } set { isVisited = value; } }
    public int NeighborsCount { get { return neighbors.Count; } }

    public Vertex(T value)
    {
        this.value = value;
        isVisited = false;
        neighbors = new List<Vertex<T>>();
    }

    public Vertex(T value, List<Vertex<T>> neighbors)
    {
        this.value = value;
        isVisited = false;
        this.neighbors = neighbors;
    }

    public void Visit()
    {
        isVisited = true;
    }

    public void AddEdge(Vertex<T> vertex)
    {
        neighbors.Add(vertex);
    }

    public void AddEdges(List<Vertex<T>> newNeighbors)
    {
        neighbors.AddRange(newNeighbors);
    }

    public void RemoveEdge(Vertex<T> vertex)
    {
        neighbors.Remove(vertex);
    }


    public override string ToString()
    {

        StringBuilder allNeighbors = new StringBuilder("");
        allNeighbors.Append(value + ": ");

        foreach (Vertex<T> neighbor in neighbors)
        {
            allNeighbors.Append(neighbor.value + "  ");
        }

        return allNeighbors.ToString();

    }

}

--

/// <summary>
/// Implementation of a generic, unweighted, undirected graph
/// </summary>

class UndirectedGenericGraph<T>
{

    // The list of vertices in the graph
    private List<Vertex<T>> vertices;

    // The number of vertices
    int size;

    public List<Vertex<T>> Vertices { get { return vertices; } }
    public int Size { get { return vertices.Count; } }


    public UndirectedGenericGraph(int initialSize)
    {
        if(size < 0)
        {
            throw new ArgumentException("Number of vertices cannot be negative");
        }

        size = initialSize;

        vertices = new List<Vertex<T>>(initialSize);

    }

    public UndirectedGenericGraph(List<Vertex<T>> initialNodes)
    {
        vertices = initialNodes;
        size = vertices.Count;
    }

    public void AddVertex(Vertex<T> vertex)
    {
        vertices.Add(vertex);
    }

    public void RemoveVertex(Vertex<T> vertex)
    {
        vertices.Remove(vertex);
    }

    public bool HasVertex(Vertex<T> vertex)
    {
        return vertices.Contains(vertex);
    }

    public void DepthFirstSearch(Vertex<T> root)
    {
        if (!root.IsVisited)
        {
            Console.Write(root.Value + " ");
            root.Visit();

            foreach(Vertex<T> neighbor in root.Neighbors)
            {
                DepthFirstSearch(neighbor);
            }

        }
    }


    public void BreadthFirstSearch(Vertex<T> root)
    {

        Queue<Vertex<T>> queue = new Queue<Vertex<T>>();

        root.Visit();

        queue.Enqueue(root);

        while(queue.Count > 0)
        {
            Vertex<T> current = queue.Dequeue();

            foreach (Vertex<T> neighbor in current.Neighbors)
            {
                if (!neighbor.IsVisited)
                {
                    Console.Write(neighbor.Value + " ");
                    neighbor.Visit();
                    queue.Enqueue(neighbor);
                }
            }
        }

    }

}

--

class Program
{
    static void Main(string[] args)
    {

        // Create a list of vertices using the Vertex<T> class
        List<Vertex<string>> vertices = new List<Vertex<string>>
        (
            new Vertex<string> []
                {
                new Vertex<string>("Los Angeles"),
                new Vertex<string>("San Francisco"),
                new Vertex<string>("Las Vegas"),
                new Vertex<string>("Seattle"),
                new Vertex<string>("Austin"),
                new Vertex<string>("Portland")
                }
        );

        // Establish edges; Ex. Los Angeles -> San Francisco, Las Vegas, Portland
        vertices[0].AddEdges(new List<Vertex<string>>(new Vertex<string>[] 
        {
            vertices[1], vertices[2], vertices[5]
        }));

        vertices[1].AddEdges(new List<Vertex<string>>(new Vertex<string>[]
        {
            vertices[0], vertices[3], vertices[5]
        }));

        vertices[2].AddEdges(new List<Vertex<string>>(new Vertex<string>[]
        {
            vertices[0], vertices[1], vertices[4]
        }));

        vertices[3].AddEdges(new List<Vertex<string>>(new Vertex<string>[]
        {
            vertices[1], vertices[5]
        }));

        vertices[4].AddEdges(new List<Vertex<string>>(new Vertex<string>[]
        {
            vertices[2]
        }));

        vertices[5].AddEdges(new List<Vertex<string>>(new Vertex<string>[]
        {
            vertices[1], vertices[3]
        }));

        // Create graph using the UndirectedGenericGraph<T> class
        UndirectedGenericGraph<string> testGraph = new UndirectedGenericGraph<string>(vertices);

        // Check to see that all neighbors are properly set up
        foreach(Vertex<string> vertex in vertices)
        {
            Console.WriteLine(vertex.ToString());
        }

        // Test searching algorithms
        testGraph.DepthFirstSearch(vertices[0]);
        //testGraph.BreadthFirstSearch(vertices[0]);

    }
}

Answer 1

Vertex

The separate properties and backing store are redundant. We don't do anything extra when getting or setting the values so we can just use the properties.

When we have multiple constructors, we should chain them, or in this case, we can just use an optional parameter. (The params version makes initialization a bit simpler).

We should make the incoming parameter as general as possible. By declaring it as a List<Vertex<T>> we are preventing the user passing in an Vertex<T>[] or a Collection<Vertex<T>>. If we declare it as IEnumerable<Vertex<T>> we can pass in each of these, as well as the list. It means an extra call inside the constructor (ToList()) but this is just one place.

Usually I would make the value for the vertex readonly (I would expect the neighbors to change but not the vertex value) if this is wrong, we can just make the value read/write.

The use of Visit() and making the IsVisited setter public is redundant, we need to use Visit() and make the setter private (in which case we can only search once) or we need to remove Visit().

As with the constructor, when adding multiple neighbors (AddEdge() ) we should pass in an IEnumerable<Vertex<T>> rather than a List<Vertex<T>> and should add the params version.

If we are worried enough about performance that we want to use StringBuilder in ToString() we should get rid of the + " " calls inside it, we can use string formatting instead. (The Aggregate() call is just showing off, sorry)

This still leaves us with the trailing space for the last neighbor, but if we can live with this we're fine. However, unless performance is a real issue, I would drop the StringBuilder and just use string.Join()

class Vertex<T>
{
    public Vertex(T value, params Vertex<T>[] parameters) 
        : this(value, (IEnumerable<Vertex<T>>)parameters) { }

    public Vertex(T value, IEnumerable<Vertex<T>> neighbors = null)
    {
        Value = value;
        Neighbors = neighbors?.ToList() ?? new List<Vertex<T>>();
        IsVisited = false;  // can be omitted, default is false but some
                            // people like to have everything explicitly
                            // initialized
    }

    public T Value { get; }   // can be made writable

    public List<Vertex<T>> Neighbors { get; }

    public bool IsVisited { get; set; }

    public int NeighborCount  => Neighbors.Count; 

    public void AddEdge(Vertex<T> vertex)
    {
        Neighbors.Add(vertex);
    }

    public void AddEdges(params Vertex<T>[] newNeighbors)
    {
        Neighbors.AddRange(newNeighbors);
    }

    public void AddEdges(IEnumerable<Vertex<T>> newNeighbors)
    {
        Neighbors.AddRange(newNeighbors);
    }

    public void RemoveEdge(Vertex<T> vertex)
    {
        Neighbors.Remove(vertex);
    }

    public override string ToString()
    {
        return Neighbors.Aggregate(new StringBuilder($"{Value}: "), (sb, n) => sb.Append($"{n.Value} ")).ToString();
        //return $"{Value}: {(string.Join(" ", Neighbors.Select(n => n.Value)))}";
    }

}

UndirectedGraph

There are a number of comments on the code below but first we should look at the design and usage.

From the usage in the searches, we can see that for each pair in the graph we need a link to its neighbors and vice versa.

e.g.

if we say that A and B are connected, we need to add B as a neighbor for A and A as a neighbor for B,

but the current interface makes this a cumbersome and error possible affair.

• It is possible to add a vertex and not add its neighbor to the graph or not add its neighbor to itself (even though it is in the graph).
• It is possible to remove a vertex from the graph without removing it from its neighbors.

(and as a coding practice, the use of the indices into the list makes errors a lot more possible)

If we start with the idea that a pair of nodes is to be added, and design the interface around this, we make things a lot easier to use and safer.

public void CheckVertices()
{
    var la = new Vertex<string>("Los Angeles");
    var sf = new Vertex<string>("San Francisco");
    var lv = new Vertex<string>("Las Vegas");
    var se = new Vertex<string>("Seattle");
    var au = new Vertex<string>("Austin");
    var po = new Vertex<string>("Portland");

    var testGraph = new UndirectedGenericGraph<string>();

    // la <=> sf, lv, po
    testGraph.AddPair(la, sf);
    testGraph.AddPair(la, lv);
    testGraph.AddPair(la, po);

    // sf <=> se, po
    testGraph.AddPair(sf, se);
    testGraph.AddPair(sf, po);

    // lv <=> au
    testGraph.AddPair(lv, au);

    // se <=> po
    testGraph.AddPair(se, po);

    // Check to see that all neighbors are properly set up
    foreach (var vertex in testGraph.Vertices)
    {
        System.Diagnostics.Debug.WriteLine(vertex.ToString());
     }

    // Test searching algorithms
    testGraph.DepthFirstSearch(la, (m) => System.Diagnostics.Debug.WriteLine(m));

}

Code Comments

As with Vertex if we have multiple constructors, we should chain them and I have added the params version to help initialization.

I am dubious of the initialSize constructor. It smells of Premature Optimization, I would omit it unless we find that it is needed. There is also a functional problem with it. size will always be 0, the check should be against initialSize also, size is not read from anywhere. It looks like a remnant.

The two searches (DepthFirstSearch and BreadthFirstSearch) are not searches, they display the nodes (Rename to xxxDisplay?)

We should never have calls to Console.Write in our functional code. Say we want to write the items to a file instead of the screen? We should pass in an action and invoke this action on each node.

The BreadthFirst version doesn't work quite correctly, it should display the root node first (it dones't) and I don't have time to fix it now so I have omitted it.

class UndirectedGenericGraph<T>
{

    public UndirectedGenericGraph(params Vertex<T>[] initialNodes)
        : this((IEnumerable<Vertex<T>>)initialNodes) { }

    public UndirectedGenericGraph(IEnumerable<Vertex<T>> initialNodes = null)
    {
        Vertices = initialNodes?.ToList() ?? new List<Vertex<T>>();
    }

    public List<Vertex<T>> Vertices { get; }

    public int Size => Vertices.Count;

    public void AddPair(Vertex<T> first, Vertex<T> second)
    {
        AddToList(first);
        AddToList(second);
        AddNeighbors(first, second);
    }

    public void DepthFirstSearch(Vertex<T> root, Action<string> writer)
    {
        UnvisitAll();
        DepthFirstSearchImplementation(root, writer);

    }

    private void DepthFirstSearchImplementation(Vertex<T> root, Action<string> writer)
    {
        if (!root.IsVisited)
        {
            writer($"{root.Value} ");
            root.IsVisited = true;

            foreach (Vertex<T> neighbor in root.Neighbors)
            {
                DepthFirstSearchImplementation(neighbor, writer);
            }
        }
    }

    private void AddToList(Vertex<T> vertex)
    {
        if (!Vertices.Contains(vertex))
        {
            Vertices.Add(vertex);
        }
    }

    private void AddNeighbors(Vertex<T> first, Vertex<T>  second)
    {
        AddNeighbor(first, second);
        AddNeighbor(second, first);
    }

    private void AddNeighbor(Vertex<T> first, Vertex<T> second)
    {
        if (!first.Neighbors.Contains(second))
        {
            first.AddEdge(second);
        }
    }

    private void UnvisitAll()
    {
        foreach(var vertex in Vertices)
        {
            vertex.IsVisited = false;
        }
    }

}

Answer 2

In addition to AlanT's great review:

The IsVisited property is actually not a property of the graph, because it stores the state of the search. That state should be decoupled from the Vertex class. Consider to implement the "searches" as separate classes:

class DeepthFirstIterator<T>
{
    private readonly Vertex<T> root;
    private readonly HashSet<Vertex<T>> visited = new HashSet<Vertex<T>>();
    public DeepthFirstIterator(Vertex<T> rootVertex)
    {
        root = rootVertex;
    }

    public IEnumerable<Vertex<T>> Iterate()
    {
        visited.Clear();

        return DepthFirstSearch(root, visited);
    }

    private IEnumerable<Vertex<T>> DepthFirstSearch(Vertex<T> vertex, HashSet<Vertex<T>> visited)
    {
        if (visited.Contains(vertex))
            yield break;

        visited.Add(vertex);

        yield return vertex;

        foreach (Vertex<T> neighbor in vertex.Neighbors.SelectMany(n => DepthFirstSearch(n, visited)))
            yield return neighbor;
    }
}

Usage:

foreach (var vertex in new DeepthFirstIterator<string>(vertices[0]).Iterate())
        Console.WriteLine(vertex.Value);

Answer 3

A few more minor things from me:

• Try to be consistent in your code style. For example if you use var, use var everywhere wherever possible. There are diverse opinions about whether var eliminating the code readability and understanding in general vs. helping better variable naming and shorter code etc. I'll leave that choice for using it or not to you, but try to be consistent throughout the code.
• Some code-style checker tools like when each field, property and class has modifiers. In general it is a good idea to explicitly have the modifiers.
• For production quality code you should guide your code with Debug.Assert() and/or Contract.Assert() statements in each public method entrance to validate arguments of your input. You can learn more about those in the following discussion about Debug.Assert vs Contract.Assert