Python networkx (graph library) example

Posted on Tue 06 June 2017 in misc

This is just for me to look it up again later:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#!/usr/bin/env python3

"""
A small example that uses networkx and pyplot to create a DiGraph, 
draw it and compute floyd-warshall on it.
"""

import networkx as nx
import matplotlib.pyplot as plt

#https://www.debian.org/vote/2013/vote_001
# The beats matrix:
#
#           1   2   3   4
#Option 1       88  62  319
#Option 2   252     141 355
#Option 3   279 210     353
#Option 4   51  24  30   
BEATS_MATRIX = [
    [0, 88, 62, 319],
    [252, 0, 141, 355],
    [279, 210, 0, 353],
    [51, 24, 30, 0],
]
NUM_OPTIONS = 4

# create a graph with candidates that beat each other
G=nx.DiGraph()

# create nodes for all options
for option in range(NUM_OPTIONS):
    G.add_node(option + 1)

# connect winner to loser options
for o1 in range(NUM_OPTIONS):
    for o2 in range(o1+1, NUM_OPTIONS):
        if BEATS_MATRIX[o1][o2] > BEATS_MATRIX[o2][o1]:
            u = o1+1
            v = o2+1
            c = BEATS_MATRIX[o1][o2] - BEATS_MATRIX[o2][o1]
        else:
            u = o2+1
            v = o1+1
            c = BEATS_MATRIX[o2][o1] - BEATS_MATRIX[o1][o2]
        print("option {} wins over {} by {} votes".format(u, v, c))
        G.add_edge(u, v, weight=c)


# all pairs shortest path example
distance = nx.floyd_warshall(G)
for u in range(1, NUM_OPTIONS+1):
    for v in range(1, NUM_OPTIONS+1):
        print("{} ".format(distance[u][v]), end="")
    print()

#drawing example
pos=nx.spectral_layout(G) # positions for all nodes
nx.draw_networkx_nodes(G, pos, node_size=700)
nx.draw_networkx_edges(G, pos, edgelist=G.edges(), width=1)
nx.draw_networkx_labels(G, pos, font_size=15, font_family='sans-serif')
edge_labels=dict([((u,v,),d['weight'])
             for u,v,d in G.edges(data=True)])
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels,\
    font_size=15, font_family='sans-serif')

plt.axis('off')
plt.show()