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, (V2 in an edge V1 → V2) 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..! 😀