Freebie: A C# adjacency list implementation

Just wrote this. Thought someone might be able to use it as a reference... best post it here before I refactor it yet again

Could be useful for anyone rolling their own pathfinding implementations as I will be. The benefit of an adjacency list (vs. edge list or adjacency matrix) is that adjacency lists are excellent if you want to represent a relatively sparse graph (low average vertex degree) and traverse it rapidly. On the other hand, adj. lists are not very fast at removals. The trade-offs were good for my spec. See here for more info.

Code (csharp):

1. using System.Collections;
2. using System.Collections.Generic;
3. using System;
4.  
5. public class AdjacencyList<K>
6. {
7.     private List<List<K>> _vertexList = new List<List<K>>();
8.     private Dictionary<K, List<K>> _vertexDict = new Dictionary<K, List<K>>();
9.  
10.     public AdjacencyList(K rootVertexKey)
11.     {
12.         AddVertex(rootVertexKey);
13.     }
14.    
15.     private List<K> AddVertex(K key)
16.     {
17.         List<K> vertex = new List<K>();
18.         _vertexList.Add(vertex);
19.         _vertexDict.Add(key, vertex);
20.        
21.         return vertex;
22.     }
23.    
24.     public void AddEdge(K startKey, K endKey)
25.     {      
26.         List<K> startVertex = _vertexDict.ContainsKey(startKey) ? _vertexDict[startKey] : null;
27.         List<K> endVertex = _vertexDict.ContainsKey(endKey) ? _vertexDict[endKey] : null;
28.  
29.         if (startVertex == null)
30.             throw new ArgumentException("Cannot create edge from a non-existent start vertex.");
31.  
32.         if (endVertex == null)
33.             endVertex = AddVertex(endKey);
34.  
35.         startVertex.Add(endKey);
36.         endVertex.Add(startKey);
37.     }
38.    
39.     public void RemoveVertex(K key)
40.     {
41.         List<K> vertex = _vertexDict[key];
42.        
43.         //First remove the edges / adjacency entries
44.         int vertexNumAdjacent = vertex.Count;
45.         for (int i = 0; i < vertexNumAdjacent; i++)
46.         {  
47.             K neighbourVertexKey = vertex[i];
48.             RemoveEdge(key, neighbourVertexKey);
49.         }
50.  
51.         //Lastly remove the vertex / adj. list
52.         _vertexList.Remove(vertex);
53.         _vertexDict.Remove(key);
54.     }
55.    
56.     public void RemoveEdge(K startKey, K endKey)
57.     {
58.         ((List<K>)_vertexDict[startKey]).Remove(endKey);
59.         ((List<K>)_vertexDict[endKey]).Remove(startKey);
60.     }
61.    
62.     public bool Contains(K key)
63.     {
64.         return _vertexDict.ContainsKey(key);
65.     }
66.    
67.     public int VertexDegree(K key)
68.     {
69.         return _vertexDict[key].Count;
70.     }
71. }
72.  

Generic K is really intended for you to make a choice between using int (for speed) and string (for convenience) handles for your vertices in your client/implementation class. Using anything else would be a bit misguided I'd think.

You will probably want to disallow pseudograph characteristics -- self-loops and multiple edges between vertex pairs. I've foregone including that as you may wish to handle it at a higher level. This class is meant to be "close to the metal".

 

Hey, that's pretty cool. Will have a proper look at it later.

 

If you ever need an undirected graph implementation in C# for Unity, the Adjacency List script above does a great job at handling different data types for that purpose.

By using "Generic K", the script can be used with various data types by simply doing the following:

To create a graph using ints:

Code (CSharp):

1. AdjacencyList<int> myList = new AdjacencyList<int> ();

To create a graph using strings:

Code (CSharp):

1. AdjacencyList<string> myList = new AdjacencyList<string> ();

To create a graph using a custom class, e.g. "Ball", you defined:

Code (CSharp):

1. AdjacencyList<Ball> myList = new AdjacencyList<Ball> ();

You can then iterate through the graph using foreach.

 

Can you elaborate on this. I've got the Adjacency List in my project but I'm having trouble seeing how I test to see if two vertices are linked by an edge. I see Contains and VertexDegree as public methods but neither seems to give me a relationship and the lists are all private members.

 

Think I figured it out myself. Added this method.

Code (CSharp):

1.     public List<K> FindNeighbours(K key)
2.     {
3.         return _vertexDict[key];
4.     }

 

Just wanted to add in that Cynicide's addition allows you to remove VertexDegree() from this function. If you change the added function name to GetNeighboursOf(), calling Count() on the returned List is rather intuitive and flows more naturally than VertexDegree().