Adjacency List Implementation in C#

Hello people..! This is a special extension for my discussion on Graph Theory Basics. Here, I give you the code for implementing the Adjacency List in C# using the .Net Library. Some of the features of this code are –

• The Adjacency List is an array of LinkedList<>, where each element is a Tuple<>. This Tuple stores two values, the destination vertex, (V₂ in an edge V₁ → V₂) and the weight of the edge.
• For adding an edge, we can call –
  • void addEdgeAtEnd(int startVertex, int endVertex, int weight) – To append an edge to the linked list.
  • void addEdgeAtBegin(int startVertex, int endVertex, int weight) – To add an edge at the beginning of the linked list.
• Methods have been provided to return the number of vertices.
• An Indexer has been provided to help in retrieving the edges from a vertex. We can use Count property on this, to get the number of edges from a vertex.
• bool removeEdge(int startVertex, int endVertex, int weight) – Tries to remove the first occurrence an edge from the adjacency list. Returns true if successfull.

using System;
using System.Collections.Generic;

namespace TheoryOfProgramming
{
    class AdjacencyList
    {
        LinkedList<Tuple<int, int>>[] adjacencyList;

        // Constructor - creates an empty Adjacency List
        public AdjacencyList(int vertices)
        {
            adjacencyList = new LinkedList<Tuple<int, int>>[vertices];

            for (int i = 0; i < adjacencyList.Length; ++i)
            {
                adjacencyList[i] = new LinkedList<Tuple<int, int>>();
            }
        }

        // Appends a new Edge to the linked list
        public void addEdgeAtEnd(int startVertex, int endVertex, int weight)
        {
            adjacencyList[startVertex].AddLast(new Tuple<int, int>(endVertex, weight));
        }

        // Adds a new Edge to the linked list from the front
        public void addEdgeAtBegin(int startVertex, int endVertex, int weight)
        {
            adjacencyList[startVertex].AddFirst(new Tuple<int, int>(endVertex, weight));
        }

        // Returns number of vertices
        // Does not change for an object
        public int getNumberOfVertices()
        {
            return adjacencyList.Length;
        }

        // Returns a copy of the Linked List of outward edges from a vertex
        public LinkedList<Tuple<int, int>> this[int index]
        {
            get
            {
                LinkedList<Tuple<int, int>> edgeList 
                               = new LinkedList<Tuple<int, int>>(adjacencyList[index]);

                return edgeList;
            }
        }

        // Prints the Adjacency List
        public void printAdjacencyList()
        {
            int i = 0;

            foreach (LinkedList<Tuple<int, int>> list in adjacencyList)
            {
                Console.Write("adjacencyList[" + i + "] -> ");

                foreach (Tuple<int, int> edge in list)
                {
                    Console.Write(edge.Item1 + "(" + edge.Item2 + ")");
                }

                ++i;
                Console.WriteLine();
            }
        }

        // Removes the first occurence of an edge and returns true
        // if there was any change in the collection, else false
        public bool removeEdge(int startVertex, int endVertex, int weight)
        {
            Tuple<int, int> edge = new Tuple<int, int>(endVertex, weight);

            return adjacencyList[startVertex].Remove(edge);
        }
    }

    class TestGraph
    {
        public static void Main()
        {
            Console.WriteLine("Enter the number of vertices -");
            int vertices = Int32.Parse(Console.ReadLine());

            AdjacencyList adjacencyList = new AdjacencyList(vertices + 1);
            
            Console.WriteLine("Enter the number of edges -");
            int edges = Int32.Parse(Console.ReadLine());

            Console.WriteLine("Enter the edges with weights -");
            int startVertex, endVertex, weight;

            for (int i = 0; i < edges; ++i)
            {
                startVertex = Int32.Parse(Console.ReadLine());
                endVertex = Int32.Parse(Console.ReadLine());
                weight = Int32.Parse(Console.ReadLine());

                adjacencyList.addEdgeAtEnd(startVertex, endVertex, weight);
            }

            adjacencyList.printAdjacencyList();
            adjacencyList.removeEdge(1, 2, 1);
            adjacencyList.printAdjacencyList();
        }
    }
}

One sweet thing about this code is that we can easily store more information in an edge. We can do so by adding elements to the generic Tuple<>… We need to give each input in a single line, otherwise an exception is thrown. If not we must split the input and then parse the array elements. This is an example demonstrates it –

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Enter -> startVertex endVertex weight");

        // Spilt by space as delimeter
        String[] input = Console.ReadLine().Split(' ');

        int startVertex = Int32.Parse(input[0]);
        int endVertex = Int32.Parse(input[1]);
        int weight = Int32.Parse(input[2]);

        Console.WriteLine(startVertex);
        Console.WriteLine(endVertex);
        Console.WriteLine(weight);

    }
}

Feel free to comment if you have any doubts..! Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 … Keep practising..! Happy Coding..! 😀

Advertisements