Improve Graph Adjacency List Implementation and Operations

Question

I am studying graphs and I am trying to make a library in C# for myself and anyone else interested, that is didactic and simple, so I can remember how to solve common problems.

I would like to improve it.
How can I improve, for example, the DFS, complete the Prim's algorithm and implement the Kruskal's and Dijkstra's algorithms ?

Create an interface that can be derived for representing different kinds of graphs, like Undirect and Direct Graph, for example.

public interface IGraph
{
            void InsertDirectEdge(int edgeAKey, int edgeBKey,int weight = 0);
            void IsertNewVertex(int vertexKey);
            bool ExistKey(int vertexKey);
            Vertex InitializeDFS(int vertexKeyToFind);
            bool MakeItBipartite();
            Vertex DFS(Vertex root, int vertexKeyToFind);
            void FindNumberOfConnectedComponents();
            void BFS(int startVertexKey);
            Vertex InitialiazeBFS(int vertexKeyToFind);
            bool IsVisited(Vertex v);

            Vertex MarkVertexAsVisited(Vertex v);
            Vertex GetFirstElementOfTheList(int findKey);
            void InsertUndirectedEdge(int vertexAKey, int vertexBKey, int Weight = 0);
            GraphDirect PrimAlgorithm();
            Vertex FindByKey(int vertexKey);
        }

Created a direct graph, with a Dictionary<int,Vertex> to represent a Graph Adjacency List, where the key is an integer.

   public class GraphDirect : IGraph
    {
            private Dictionary<int,Vertex> Vertices { get; set; }

            //For use on the DFS to "break" the recursion.
            private bool finished;

            public GraphDirect()
            {
                Vertices = new Dictionary<int, Vertex>();
            }

            //Initialize all vertices with Unvisited value.
            private void InitializeVertices()
            {
                foreach(int key in this.Vertices.Keys)
                {
                    this.Vertices[key].Status = State.UnVisited;
                }
            }
}

This part is used for Depth-First-Search and probably should be changed to be more elegant and efficient. It should execute in linear time O(|E|), where E is the total number of edges. To call DFS in this case you start calling InitializeDFS(TheKeyYouWantToFind).

public Vertex InitializeDFS(int vertexKeyToFind)
{
            if (this.Vertices.Count == 0)
                return null;
            InitializeVertices();
            finished = false;
            return this.DFS(Vertices.First().Value, vertexKeyToFind);
        }

        private void ProccessVertex(int vertexBeenProcessed, int vertexKeyToFind)
        {
            if (vertexBeenProcessed == vertexKeyToFind)
                finished = true;
            else
                finished = false;
        }

public Vertex DFS(Vertex root, int vertexKeyToFind)
{

        Console.WriteLine("Root = {0}", root.Key);

        ProccessVertex(root.Key, vertexKeyToFind);

        if (finished)
                return root;
        this.Vertices[root.Key].Status = State.Visited;

        while (root.Next != null)
        {
            if (Vertices[root.Next.Key].Status == State.UnVisited)
            {
                root.Next.Status = State.Processed;
                Console.WriteLine("Root.Next = {0}", root.Key);
                DFS(Vertices[root.Next.Key], vertexKeyToFind);
            }
            root = root.Next;
        }
        if (!finished)
            return null;
        else
            return root;
}

This part is to check if the graph is bipartite or not.

void InitializeVerticesColors()
{
    foreach(Vertex v in this.Vertices.Values)
    {
        v.Color = Color.Uncolored;
    }
}

//If is bipartite
public bool MakeItBipartite()
{
    InitializeVerticesColors();
    InitializeVertices();
    return this.BFS2Colors(this.Vertices.First().Key);
}

private bool BFS2Colors(int startVertexKey)
{
    if (this.Vertices.Count == 0)
        return true;

    int white = 0;

    Queue<Vertex> Q = new Queue<Vertex>();
    Console.WriteLine("Starting at: {0}", this.Vertices[startVertexKey].Key);
    this.Vertices[startVertexKey].Color = Color.White;
    Console.WriteLine("White");
    this.GetFirstElementOfTheList(startVertexKey).Status = State.Visited;
    Q.Enqueue(this.GetFirstElementOfTheList(startVertexKey));

    while (Q.Count != 0)
    {
        white = (this.Vertices[Q.Peek().Key].Color == Color.White) ? 1 : 0;

        List<Vertex> children = GetChildrenOfVertex(Q.Dequeue());

        foreach (Vertex v in children)
        {
            if (this.Vertices[v.Key].Status == State.UnVisited)
            {

                Console.WriteLine("Passed to {0}", v.Key);

                if (white == 1)
                    this.Vertices[v.Key].Color = Color.Black;
                else
                    this.Vertices[v.Key].Color = Color.White;

                if (this.Vertices[v.Key].Color == Color.White)
                    Console.WriteLine("Child color white");
                else if (this.Vertices[v.Key].Color == Color.Black)
                    Console.WriteLine("Child Color Black");
                this.Vertices[v.Key].Status = State.Visited;
                Q.Enqueue(this.Vertices[v.Key]);
            }
        }
    }
    return true;
}

This part if for checking the number of Connected Components of a Graph.

    public void FindNumberOfConnectedComponents()
    {
        int c = 0;

        InitializeVertices();

        foreach (Vertex v in this.Vertices.Values)
        {
            if (v.Status == State.UnVisited)
            {
                //Counting the number of components
                c++;
                Console.WriteLine("Component number {0}", c);
                this.BFS(v.Key);
            }
        }
    }

This is to do a Breath-First-Search (BFS) looking for a key.

public void BFS(int startVertexKey)
{

if (this.Vertices.Count == 0)
    return;

Queue<Vertex> Q = new Queue<Vertex>();
Console.WriteLine("Starting at: {0}", this.Vertices[startVertexKey].Key);

this.GetFirstElementOfTheList(startVertexKey).Status = State.Visited;
Q.Enqueue(this.GetFirstElementOfTheList(startVertexKey));

while (Q.Count != 0)
{
    List<Vertex> children = GetChildrenOfVertex(Q.Dequeue());

    foreach (Vertex v in children)
    {
        if (this.Vertices[v.Key].Status == State.UnVisited)
        {

            Console.WriteLine("Passed to {0}", v.Key);
            this.Vertices[v.Key].Status = State.Visited;
            Q.Enqueue(this.Vertices[v.Key]);
        }
    }
}

}


private List<Vertex> GetChildrenOfVertex(Vertex headVertex)
{
    List<Vertex> vertexes = new List<Vertex>();
    Vertex v = headVertex.Next;

while (v != null)
{
    vertexes.Add(v);
    v = v.Next;
}
return vertexes;
}


public Vertex InitialiazeBFS(int vertexKeyToFind)
{
           InitializeVertices();
           return BFS(this.Vertices.First().Key,vertexKeyToFind);
}

private Vertex BFS(int startVertexKey, int vertexKeyToFind)
{
        if (this.Vertices.Count == 0)
            return null;

        //Starting from the first element
        Queue<Vertex> Q = new Queue<Vertex>();
        Console.WriteLine("Starting at: {0}", this.Vertices[startVertexKey].Key);
        this.GetFirstElementOfTheList(startVertexKey).Status = State.Visited;
        Q.Enqueue(this.GetFirstElementOfTheList(startVertexKey));

        while (Q.Count != 0)
        {
            List<Vertex> children = GetChildrenOfVertex(Q.Dequeue());

            foreach (Vertex v in children)
            {
                if (this.Vertices[v.Key].Status == State.UnVisited)
                {
                    Console.WriteLine("Passed to {0}", v.Key);
                    if (v.Key == vertexKeyToFind)
                        return v;
                    this.Vertices[v.Key].Status = State.Visited;
                    Q.Enqueue(this.Vertices[v.Key]);
                }
            }
        }

        return null;
}

public bool IsVisited(Vertex v)
{
    if (v == null)
        return false;
   return this.Vertices[v.Key].Status == State.Visited;
}

public Vertex MarkVertexAsVisited(Vertex v)
{
    if (v == null) return null;
    this.Vertices[v.Key].Status = State.Visited;
    return this.Vertices[v.Key];
}


public Vertex GetFirstElementOfTheList(int findKey)
{
    if (this.Vertices.ContainsKey(findKey))
        return this.Vertices[findKey];

    return null;
}


    public bool ExistKey(int vertexKey)
    {
        if (this.FindByKey(vertexKey) == null)
            return false;
        else
            return true;
    }

These are operations used to insert new vertices, undirect edges and direct edges. Also find an element on the graph by it's key, return null if it doesn't exist on the graph.

public void IsertNewVertex(int vertexKey)
{
    if (!this.ExistKey(vertexKey))
    {
        this.Vertices.Add(vertexKey, new Vertex(vertexKey));
    }
}

public void InsertUndirectedEdge(int vertexAKey, int vertexBKey, int Weight = 0)
{
    this.InsertDirectEdge(vertexAKey, vertexBKey, Weight);
    this.InsertDirectEdge(vertexBKey, vertexAKey, Weight);
}


public void InsertDirectEdge(int vertexAKey, int vertexBKey, int weightEdge = 0)
{
    //Create the vertex A on the vertex list
    if (!this.ExistKey(vertexAKey))
    {
        this.IsertNewVertex(vertexAKey);
    }
    //Create the vertex B on the vertex list
    if (!this.ExistKey(vertexBKey))
    {
        this.IsertNewVertex(vertexBKey);
    }

    //Add the vertex B on the vertex A position on the Dictionary, as the second element of the list
    Vertex vertexB = new Vertex(vertexBKey);
    vertexB.Weight = weightEdge;
    vertexB.Next = this.Vertices[vertexAKey].Next;
    this.Vertices[vertexAKey].Next = vertexB;

}

public Vertex FindByKey(int vertexKey)
{
    if (this.Vertices.ContainsKey(vertexKey))
        return this.Vertices[vertexKey];

    return null;
}

This is a Prim's algorithm used to find the minimum spanning tree of a Graph using Greedy algorithm, and it is still incomplete.

public GraphDirect PrimAlgorithm()
{
            if (this.Vertices.First().Value == null)
                return null;

            GraphDirect SpanningTree = new GraphDirect();

            Vertex v = this.Vertices.First().Value;
            v.SpanningTreeVertex = true;
            Console.WriteLine("v.key = {0}",v.Key);
            SpanningTree.IsertNewVertex(v.Key);
            Queue<Vertex> Q = new Queue<Vertex>();
            Q.Enqueue(v);
            int min = int.MaxValue;
            Vertex minVertex = null;
            while (Q.Count != 0)
            {
                Vertex parent = Q.Dequeue();
                List<Vertex> children = GetChildrenOfVertex(parent);

                foreach (Vertex vet in children)
                {
                    if (vet.Status == State.UnVisited && vet.Weight < min)
                    {
                        min = vet.Weight;
                        minVertex = vet;
                    }
                }
                //TODO: 
                minVertex.Status = State.Visited;
                SpanningTree.InsertUndirectedEdge(parent.Key, minVertex.Key, min);

            }

            return SpanningTree;
         }

Created the states of the graph for DFS, and Colors for checking if a graph is bipartite or not, also the Vertex is represented bellow, where the Key is the integer that uniquely identify it, and attached to the class you can add any attributes like Value for example.

public enum State { Visited = 0, UnVisited = 1, Processed = 2 }
public enum Color { White = 0, Black = 1, Uncolored = 2 }

public class Vertex
{
    public int Key;
    public int Value;
    public State Status = State.UnVisited;
    public Vertex Next;
    public Color Color = Color.Uncolored;
    public bool SpanningTreeVertex = false;
    public int Weight = 0;

    public Vertex(int key)
    {
        this.Key = key;
        this.Value = 0;
    }

    public Vertex(int key, int value)
    {
        this.Key = key;
        this.Value = value;
    }
}

An example showing how to use the GraphDirect class on a Console Application:

public class Start
{
     public static void Main(){
         GraphDirect gDirect = new GraphDirect();

         gDirect.InsertDirectEdge(2, 7, 2);
         gDirect.InsertDirectEdge(7, 4, 4);
         gDirect.InsertDirectEdge(4, 6, 5);
         gDirect.InsertDirectEdge(8, 3, 5);
         gDirect.InsertDirectEdge(6, 2, 4);

        }
}

Answer 1

You have put too many responsibilities in a single interface and class. Your IGraph interface knows not only about graph itself, but also about all the possible methods of traversing this graph. It breaks Single-responsibility principle, Open/closed principle (as you'll have to edit Graph if you want to add more search methods) and Interface segregation principle.

What you should do is refactor your interface and implementation so that:

• There is an interface IGraph that describes all necessary methods and properties of a graph, i.e. ability to get adjacent vertices of a certain vertex, and methods of mutating a graph if needed (I would start with immutable graph first). Also I would add a generic parameter that defines the type of vertices. It should not include any functionality related to methods of traversing the graph, that is no BFS/DFS/Bipartite etc.
• Graph class should not contain any data related to searching, that is no Visited states, no colors, etc.
• Define a new class for each method of working with graph, e.g. BreadthFirstSearch class, DepthFirstSearch class, etc. Each of those should work with IGraph and store information required for their processing, e.g. all those vertex visited states, etc. If there is some common functionality (like visited states) you may introduce a base class that all others will inherit from.

That will make your code decoupled, different graph traversal methods would be independent from others, and code would be much easier to read and understand.

Example of Graph and BreadthFirstSearch implementation:

public interface IGraph<TVertex>
{
    bool Contains(TVertex vertex);
    IEnumerable<TVertex> GetAdjacent(TVertex vertex);
}

public class Graph<TVertex> : IGraph<TVertex>
{
    private readonly Dictionary<TVertex, List<TVertex>> _edges;

    public Graph(params Tuple<TVertex, TVertex>[] directEdges)
    {
        _edges = directEdges
            .GroupBy(tuple => tuple.Item1, tuple => tuple.Item2)
            .ToDictionary(g => g.Key, g => g.ToList());

        //Adding vertices that are used as a target to the list of available vertices
        foreach (var missingVertex in directEdges
            .Where(tuple => !_edges.ContainsKey(tuple.Item2))
            .Select(tuple => tuple.Item2))
        {
            _edges[missingVertex] = new List<TVertex>();
        }
    }

    public bool Contains(TVertex vertex)
    {
        return _edges.ContainsKey(vertex);
    }

    public IEnumerable<TVertex> GetAdjacent(TVertex vertex)
    {
        List<TVertex> adjacentVertices;
        return _edges.TryGetValue(vertex, out adjacentVertices) ? adjacentVertices : Enumerable.Empty<TVertex>();
    }
}

public class BreadthFirstSearch<TVertex>
{
    private readonly IGraph<TVertex> _graph;

    public BreadthFirstSearch(IGraph<TVertex> graph)
    {
        _graph = graph;
    }

    public IEnumerable<TVertex> GetAllReachableVertices(TVertex startingVertex)
    {
        HashSet<TVertex> visited = new HashSet<TVertex> { startingVertex };
        Queue<TVertex> horizon = new Queue<TVertex> { startingVertex };

        while (horizon.Count > 0)
        {
            var nextVertexToExpand = horizon.Dequeue();
            yield return nextVertexToExpand;

            foreach (var vertex in _graph.GetAdjacent(nextVertexToExpand).Where(vertex => !visited.Contains(vertex)))
            {
                visited.Add(vertex);
                horizon.Enqueue(vertex);
            }
        }
    }
}

Usage:

public class Program
{
    public static void Main()
    {
        var graph = new Graph<int>(
            Tuple.Create(2, 7),
            Tuple.Create(7, 4),
            Tuple.Create(4, 6),
            Tuple.Create(8, 3),
            Tuple.Create(6, 2));

        var breadthFirstSearch = new BreadthFirstSearch<int>(graph);

        foreach (var vertex in breadthFirstSearch.GetAllReachableVertices(4))
        {
            Console.WriteLine("Next vertex is {0}", vertex);
        }
    }
}