Dynamic Programming based Graph Algorithms

These class of algorithms takes a Graph as input, using it’s adjacancy matrix , generates other matrix. Some examples are

  • Transitive clousure of graph
  • All pair shortest path problem

Standard import statement

In [1]:
from openanalysis.matrix_animator import MatrixAnimator
import numpy as np       # Needed to work with arrays

Implementation Notes

  • The algorithm should be implemented as a method
  • The algorithm works on a networkx graph
  • Obtain the adjacancy matrix as follws
def algorithm_name(G):
    import networkx as nx
    M = nx.to_numpy_matrix(G)
    # do other work now
  • If Graph is weighted, matrix elements are weights. Default weight for an edge is 1. If an edge doesn’t exsist, its weight will be treated as 0. When working with weighted graphs, You have to MANUALLY set those weigthts to infinity.
m, n = M.shape
for i in range(0, n):
    for j in range(0, n):
        if i != j and D[i, j] == 0:
           M[i, j] = float('inf')
  • After each change in matrix, yield matrix, yield copy of current version of matrix, along with a tuple containing current 3 co-ordinates at which change is caused
yield np.array(D), (i, j, k)

Example Warshall- Floyd Algorithm

Warshal-Floyd Algorithm computes All Pair Shortest Paths of a Graph using its adjacancy matrix

Now, Let’s implement the algorithm

In [2]:
def Floyd_Warshall(G):                # Must have signature like this
    D = nx.to_numpy_matrix(G)         # Obtaining Adj. matrix
    m, n = D.shape
    for i in range(0, n):             # Making non-diagonal zeros to infinity, as it is a Weighted Graph
        for j in range(0, n):
            if i != j and D[i, j] == 0:
                D[i, j] = float('inf')
    yield np.array(D), (0, 0, 0)      # Starting yield
    count = 0
    for k in range(0, n):
        for i in range(0, n):
            for j in range(0, n):
                if D[i, j] > D[i, k] + D[k, j]:
                    yield np.array(D), (i, j, k)  # yield as array changes
                    D[i, j] = D[i, k] + D[k, j]
                count += 1
    yield np.array(D), (0, 0, 0)

Visualizing the Algorithm - MatrixAnimator class

  • __init__(self, fn, G):
    • fn : A function yielding matrix along with 3-tuple
    • G : Graph on which fn has to be applied and visualized
  • animate(self, save=False):
    • save is True implies animation is saved in output/ folder
  • apply_to_graph(self, show_graph=True):
    • applies self.fn to self.G and displays the result
    • show_graph is True implies Graph is shown along with adjacancy matrix and final matrix

Here we shall create a matrix from numpy array, and assign random weights to its edges. Then we apply our function to graph

In [3]:
import networkx as nx
M = nx.from_numpy_matrix(
        [[0, 1, 0, 0, 1, 0],
         [1, 0, 1, 0, 1, 0],
         [0, 1, 0, 1, 0, 0],
         [0, 0, 1, 0, 1, 1],
         [1, 1, 0, 1, 0, 0],
         [0, 0, 0, 1, 0, 0]]
import random
for u, v in M.edges():
    M.edge[u][v]['weight'] = random.randint(1, 10)
animator = MatrixAnimator(Floyd_Warshall, M)

After executing


go to output/ directory to see the mp4 files

Example File

You can see more examples at Github