How do I store this in an adjacency list for graphs in python?

Question

Suppose I have a text file containing this:

0 1 4
0 2 3
1 4 7
5 3 8

The columns represent:

1. a vertex
2. another vertex
3. the distance between these two vertices.

For example, in the first line in the text file, 4 is the distance between points 0 and 1.

So how would I store the vertices and distances in an adjacency list in python?

Answer 1

In graph theory, an adjacent-list, is a collection of unordered lists used to represent a graph. Each list describes the set of neighbors of a vertex in the graph.

Since you are talking about adjacent list of weighted graph, you need to define a structure to store both vertex and weight. A graph theory or data structure way to implement adjacent list is like this:

class Node():
    def __init__(self, v, w, next=None):
        self.v = v
        self.w = w
        self.next = next
    ...

class LinkedList():
    def __init__(self, head=None)
        self.head = head

    def add_node():
        pass
    ...

Here Node class is the base element to compose LinkedList and LinkedList is used to represent adjacent list of one vertex. I do not implement the whole classes for you. See python-linked-list.

Assuming your graph is directed, the adjacent list of this graph is:

0 -> [1:4]-> [2:3]
1 -> [4:7]
2 -> []
3 -> []
4 -> []
5 -> [3:8]

in which, 0 -> [1:4] -> [2:3] represents the adjacent list of vertex 0, which contains two edges: 0->1 with weight 4 and 0->2 with weight 3. [1:4] could be described by class Node, and the whole row could be represented by class LinkedList. Check weighted-graph-adjacent-list for more information.

To represent the whole graph, you can simply use a list of LinkedList, e.g.,

g = [LinkedList_for_0, LinkedList_for_1, ...]

In this approach, g[i] will be the adjacent list of vertex i.

To build the whole graph, you can iterate over all edges:

g = [[] for v in range(number_of_vertex)]
for f, t, w in edges:
    g[f].add_node(Node(t,w))

In above, as I said, it's a more data structure way to implement the adjacent list. If you would to practice your understanding of data structure and graph theory knowledge, you can try this way. But, actually, unlike C/C++ array type (fixed size), python list is a mutable type, you can do operations like add, delete on a python list. So LinkedList is actually unnecessarily needed. We can redefine the these classes in a pythonic way:

class Node():
    def __init__(self, v, w):
        self.v = v
        self.w = w

Here, the Node class do not contain next member. So the adjacent list can be represented as a list of Node, e.g., adjacent list of vertex 0:

[Node(1,4), Node(2,3)]

And the whole graph can be represented as a two dimensional list (Here we assume this is a undirected graph.):

[
 [Node(1,4), Node(2,3)],
 [Node(0,4), Node(4,7)],
 [Node(0,3)],
 [Node(5,8)],
 [Node(1,7)],
 [Node(3,8)]
] 

The python way algorithm:

g = [[] for v in range(number_of_vertex)]
for f,t,w in edges:
    g[f].append(Node(t,w))
    g[t].append(Node(f,w))

Note: you need to add a new node for both ends of an edge.

In practice, when handling graph problems, I believe edge-list or sparse matrix is the most common representation. So if it possible, I would suggest you used this kind of representation.

Thanks.