How do I represent a graph given as an adjacency list in C#?

Question

I am going to program various graph algorithms, and as input, I have given graphs on the form of adjacency lists.

Here's an example:

1 2 3 4

2 1 3 4

3 1 2 4

4 1 2 3 5

5 4 6

6 5

The graph has 6 vertices, represented by 6 rows (and the first entry of each row denotes the number of the vertex representing that row). The remaining entries in a row denote the vertices that the vertex corresponding to that row are adjacent to.

What is a good way of representing this in C#? The differing number of entries in each row seem to rule out an array, so I found these lists of lists.

I am going to manipulate the graph, e.g. contract edges, and I am looking for a data structure in which graph manipulations are both possible and efficient.

Answer 1

When I had a similar task, I found it easy to have the following classes:

    class Edge
    {
    public Node From;
    public Node To;
    }

    class Node
    {
         public List<Edge> EdgesIn;
         public List<Edge> EdgesOut;
    }

    class Graph
    {
         public List<Node> Nodes;
    }

Answer 2

Looks like dictionary with a list of integers as a value structure cold be useful:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<int, List<int>> graph = new Dictionary <int, List<int>>();
        graph[1] = new List<int> {2, 3, 4};
        graph[2] = new List<int> {1, 3, 4};
        graph[3] = new List<int> {1, 2, 4};
        graph[4] = new List<int> {1, 2, 3, 5};
        graph[5] = new List<int> {4, 6};
        graph[6] = new List<int> {5};
    }
}

Answer 3

If you'll choose coding of custom classes for working with graphs this info may be helpful. But all info here on java

Answer 4

I found that a convenient way of representing graphs is the GraphSON format. You can check it out here: GraphSON format. An example of it:

{
   "graph": {
       "mode":"NORMAL",
       "vertices": [
           {
               "_id": "1",
               "_type": "vertex"
           },
           {
               "_id": "2",
               "_type": "vertex"
           },
           {
               "_id": "3",
               "_type": "vertex"
           }
       ],
       "edges": [
           {
               "weight": 1,
               "_id": "11",
               "_type": "edge",
               "_outV": "2",
               "_inV": "1"
           },
           {
               "weight": 0.5,
               "_id": "12",
               "_type": "edge",
               "_outV": "3",
               "_inV": "2"
           }
       ]
   }
}