DM559/DM545 – Linear and Integer Programming

Networks and Graphs in Python¶

The module networkx to be found also via Anaconda implements several algorithms and drawing procedures for graphs. A graph can be represented by its incidence matrix, which is a binary, symmetric, square matrix. Let's generate one at random.

In [1]:

import networkx as nx
import numpy as np
A = np.reshape(np.random.random_integers(0,1,size=100),(10,10))
A

Out[1]:

array([[1, 0, 1, 1, 1, 1, 0, 1, 1, 0],
       [0, 1, 1, 0, 1, 1, 1, 0, 1, 1],
       [1, 0, 1, 1, 0, 1, 0, 0, 0, 1],
       [0, 0, 1, 1, 0, 1, 1, 0, 0, 1],
       [0, 1, 1, 1, 1, 1, 0, 0, 0, 1],
       [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
       [0, 1, 0, 1, 0, 1, 0, 1, 1, 1],
       [0, 1, 0, 0, 0, 1, 1, 0, 0, 0],
       [0, 1, 0, 0, 1, 1, 0, 1, 0, 1],
       [0, 1, 1, 0, 0, 0, 0, 1, 0, 0]])

In [2]:

np.array_equal(A.T,A)

Out[2]:

False

In [3]:

B = A+A.T
C = np.array(B==1,dtype=int)
np.array_equal(C.T,C)

Out[3]:

True

In [4]:

G = nx.Graph(C)
D = nx.DiGraph(A)

In [5]:

%matplotlib inline

In [6]:

nx.draw(G)

In [7]:

nx.draw(D)