# 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

- applies

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(
np.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)
animator.apply_to_graph()
```

After executing

```
animator.animate(save=True)
```

go to `output/`

directory to see the mp4 files