patterncsharpModerate

Generic graph implementation in C#

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

genericimplementationgraph

Problem

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?

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

class Vertex
{

    List> neighbors;   
    T value;
    bool isVisited;

    public List> 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>();
    }

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

    public void Visit()
    {
        isVisited = true;
    }

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

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

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

    public override string ToString()
    {

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

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

        return allNeighbors.ToString();

    }

}

--

```
///
/// Implementation of a generic, unweighted, undirected graph
///

class UndirectedGenericGraph
{

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

// The number of vertices
int size;

public List> Vertices { get { return vertices; } }
public int Size {

Solution

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> we are preventing the user passing in an Vertex[] or a Collection>. If we declare it as IEnumerable> 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> rather than a List> 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
{
    public Vertex(T value, params Vertex[] parameters) 
        : this(value, (IEnumerable>)parameters) { }

    public Vertex(T value, IEnumerable> neighbors = null)
    {
        Value = value;
        Neighbors = neighbors?.ToList() ?? new List>();
        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> Neighbors { get; }

    public bool IsVisited { get; set; }

    public int NeighborCount  => Neighbors.Count; 

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

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

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

    public void RemoveEdge(Vertex 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("Los Angeles");
    var sf = new Vertex("San Francisco");
    var lv = new Vertex("Las Vegas");
    var se = new Vertex("Seattle");
    var au = new Vertex("Austin");
    var po = new Vertex("Portland");

    var testGraph = new UndirectedGenericGraph();

    // 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 con

Code Snippets

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

}

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

}

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

}

Context

StackExchange Code Review Q#131583, answer score: 10

Revisions (0)

No revisions yet.