Graph algorithms - seminary - methods of representing a graph

Exercices

1. Create a python representation based on a collection of outbound neighbours for each vertex
2. Interface: given a graph g and a vertex x, it should allow to do for y in g.parseNOut(x)
3. Choices: vertices are numbers from 0 to n-1 or they are arbitrary hashables; the graph is created with no vertices and the vertices are added one by one, vs the graph is created by giving the number of vertices or the collection of vertices.
4. Make a main program that creates a small graph and then it parses the vertices and prints all neighbours for each vertex:

       for x in g.parseX(): # this parses all vertices
           line = str(x) + " :"
           for y in g.parseNOut(x):
               line = line + " " + str(y)
           print(line)
     

5. Create a random graph with n vertices and m edges; make the main program parse the outbound neighbours of all vertices and the inbound neighbours of all vertices, but without printing (just masure the time needed).
6. Compare the time needed for the previous operation for:
   • n being, in turn, 1000, 10000, 100000, 1000000;
   • m=10*n;
   • using each of the three representations: for each vertex we have the collection of outbound neighbours; for each vertex we have both the collection of inbound and the collection of outbound neighbours; adjacency matrix

Some theory

Graph representation:

Adjacency matrix

A_i,j = true iff there is an edge from i to j

• simple;
• can find fast (O(1)) if there is an edge from i to j;
• uses a lot of memory - O(N²) - very expensive if the graph is sparse, that is, if the number of edges is much smaller than the number of vertices squared
• parsing the set of neighbours of a vertex is also slow - O(N), which can be much slower than O(deg(x))

List of neighbours for each vertex

The graph is represented as a list or dictionary, with one entry for each vertex, and where values are the list or the set of (outbound) neighbours or edges from the current vertex.

• most space effective for sparse graphs;
• parsing N^out(x) in O(outdeg(x));
• parsing Nⁱⁿ(x) is very slow.

Double list of neighbours for each vertex

As above, but for each vertex, we have two lists or sets: one for inbound edges, and one for outbound edges.

• double the space needed for the simple list of neighbours;
• parsing both N^out(x) and Nⁱⁿ(x) in O(outdeg(x)), resp. O(indeg(x));
• adding or removing an edge implies modifying in 2 places.

Order of magnitude for real-world problems:

• The road map of the world is of the order of 10⁸ (one hundred millions) vertices.
• For a planar (undirected) graph, we can prove that m <= 3n-6, so all planar graphs are sparse. A road map is almost a planar graph (usually, there are few overpasses).

Sample implementation: graph.py