Algorithm: Graph Representation

Overview

Adjacency List

An Adjacency list describes a graph representation, using unordered lists. Specifically, each vertex within the graph representation, consists of a set of neighbors (list).

Example

Consider the following arbitrary graphical representation of vertices, and corresponding (directed) edges.

    b ---> c
   ^        ^
  /          \
 /            \
a <----------> d

Representation: Adjacency List

The following is the adjacency list representation of the given graph:

a, b, c, d = range(4)
N = [
    [b, d], # a
    [c],    # b
    [a, c]  # d
]

Representation: Adjacency Set

The following is the adjacency list representation of the given graph:

a, b, c, d = range(4)
N = [
    {b, d}, # a
    {c},    # b
    {a, c}  # d
]

Note: assuming the hashing function used for accessing a specific index within a set (or dict) is sufficiently good, a look-up is on average, a constant time O(1) operation.

Note: since lists do not implement a hashing function, for pure iteration (without index lookups), lists are significantly faster.

Adjacency Matrix

An adjacency matrix is similar to the earlier adjacency list. However, instead of listing all neighbors present for each node (vertex), an array of rows is used. Specifically, every row contains a position for each possible neighbor.

Example: Simple Matrix

a, b, c, d, e, f, g, h = range(8)

#     a b c d e f g h
N = [[0,1,1,1,1,1,0,0], # a
     [0,0,1,0,1,0,0,0], # b
     [0,0,0,1,0,0,0,0], # c
     [0,0,0,0,1,0,0,0], # d
     [0,0,0,0,0,1,0,0], # e
     [0,0,1,0,0,0,1,1], # f
     [0,0,0,0,0,1,0,1], # g
     [0,0,0,0,0,1,1,0]] # h

>>> N[a][b]
1
>>>sum(N[f])
3

Example: Weighted Matrix

a, b, c, d, e, f, g, h = range(8)
_ = float('inf')

#     a b c d e f g h
W = [[0,2,1,3,9,4,_,_], # a
     [_,0,4,_,3,_,_,_], # b
     [_,_,0,8,_,_,_,_], # c
     [_,_,_,0,7,_,_,_], # d
     [_,_,_,_,0,5,_,_], # e
     [_,_,2,_,_,0,2,2], # f
     [_,_,_,_,_,1,0,6], # g
     [_,_,_,_,_,9,8,0]] # h

>>> W[a][b] < inf
True

Incidence Matrix

Suppose G is a graph with n vertices. An incidence matrix A of G is an n x m matrix, where n rows correspond to the n vertices, while m columns correspond to m edges such that

a_(i,j) = 1, if jth edge (e_j), is incident on the ith vertex (v_i)
a_(i,j) = 0, otherwise

Example

Consider the following arbitrary graphical representation of vertices, and corresponding (non-directed) edges.

       __e1__
     /        \
  v1 --- e2 --- v2
   |          /
   |        /
e5 |      / e3
   |    /
   |  /
   |/
  v4 --- e4 --- v3

Representation: Incidence Matrix

The following is the incidence matrix representation of the given graph:

#        e1 e2 e3 e4 e5
A(G) = [[1, 1, 0, 0, 1], # v1
        [1, 1, 1, 0, 0], # v2
        [0, 0, 0, 1, 0], # v3
        [0, 0, 1, 1, 1]] # v4

Note: a row with all zeros, represents an isolated vertex.

Note: the sum of each column is always equal to 2.

Multigraph

A multigraph is a representation that can have one, or more edges between a pair of vertices. The above incidence matrix, shows an example of a multigraph.

Pseudograph

A pseudograph, is a representation that is allowed to self-loop, and have more than one, or more edges between a pair of vertices.