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

you can use this script for weighted-graph !

from collections import defaultdict

adj = defaultdict(list)

content = open('input.txt', 'r').readlines()

for line in content:
    u, v, w = map(int, line.strip().split(' '))
    # if edge is on-way
    adj[u].append((v, w))
    # otherwise,
    adj[u].append((v, w))
    adj[v].append((u, w))

Answer 2

Take a look at NetworkX library, it's awesome and easy to use.

From the docs, you can have edge attributes storing any value of interest - distance, in your case:

Edges often have data associated with them. Arbitrary data can associated with edges as an edge attribute. If the data is numeric and the intent is to represent a weighted graph then use the ‘weight’ keyword for the attribute. Some of the graph algorithms, such as Dijkstra’s shortest path algorithm, use this attribute name to get the weight for each edge.

A possible implementation in your case would be:

import networkx as nx

G=nx.Graph()

for line in file:
    a, b, w = map(int, line.strip().split(' '))
    G.add_edge(a, b, weight=w)

Answer 3

Nested dictionaries are a natural way to represent adjacency lists. Dictionaries are convenient in this situation because they can represent sparse mappings better than lists, and allow efficient lookups.

adjacency_list = {}
for line in open(file):
    from, to, weight = map(int, line.split())
    adjacency_list.setdefault(from, {})[to] = weight
    adjacency_list.setdefault(to, {})[from] = weight  # for undircted graph add reverse edges

To get the weight of an edge between node i and j, you'd lookup adjacency_list.get(i, {}).get(j) (which will return None if the edge doesn't exist).

If you didn't want to deal with setdefault and get, you might want to use a defaultdict for at least the top-level dictionary. If you initialize with adjacency_list = defaultdict(dict), then setting the weights would just be adjacency_list[from][to] = weight (the inner dictionaries will be created automatically whenever they're needed).

Answer 4

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.