from openanalysis.matrix_animator import MatrixAnimator
import numpy as np       # Needed to work with arrays

"""
Explanation: Dynamic Programming  based  Graph Algorithms
These class of algorithms takes a Graph as input, using it's adjacancy matrix , generates result matrix. Some examples are

Transitive clousure of graph 
All pair shortest path problem

Standard import statement
End of explanation
"""


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)

"""
Explanation: Implementation Notes

The algorithm should be implemented as a method
The algorithm works on a networkx graph
Obtain the adjacancy matrix as follws

python
    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. 
python
        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

python
     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
End of explanation
"""


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()

"""
Explanation: 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
End of explanation
"""


