CODEWITHSUNDEEP
pythonpython-3.xmatrixdistanceadjacency-matrix
Barbara
Barbara

Reputation: 11

How to write a function distance_matrix which computes the distance matrix of a graph without using NetworkX functions in Python?

I have to write a write a function distance matrix in python which computes the distance matrix of a graph. I can use the NetworkX function adjacency_matrix to compute the adjacency matrix of the input graph, but I cannot use any other NetworkX functions.

I know that the function has to computes the distance matrix of a graph. It needs to a matrix, represented as an array of type numpy.ndarray, of the same shape as the adjacency matrix of the graph. 

Am = np.eye(48)
A = nx.adjacency_matrix(G).toarray()
A1 = np.eye(48)
def distance_matrix(G):
    for m in range(1,49,1):
        Am=np.linalg.matrix_power(A,m)
        for i in range(48):
            for j in range(48):
                if Am[i,j]>0 and A1[i, j] == 0 :
                    A1[i, j] = m and np.diagonal(B)==0 
        return A1
print(distance_matrix(G))

I know that the diagonal has to be equal to 0 and the rest of the entries have to be shortest path from one node to the other. I think...

Upvotes: 1

Views: 921

Answers (1)

Felipe Miranda
Felipe Miranda

Reputation: 56

Changing a bit the floyd_warshall_predecessor_and_distance function from networkx source code is posible to calculate de distance matrix :

def distance_matrix(G, weight='weight'):
    from collections import defaultdict
    #G is a graph from networkx package.
    dist = defaultdict(lambda : defaultdict(lambda: float('inf')))
    for u in G:
        dist[u][u] = 0

    undirected = not G.is_directed()
    for u,v,d in G.edges(data=True):
        e_weight = d.get(weight, 1.0)
        dist[u][v] = min(e_weight, dist[u][v])

        if undirected:
            dist[v][u] = min(e_weight, dist[v][u])

    for w in G:
        for u in G:
            for v in G:
                if dist[u][v] > dist[u][w] + dist[w][v]:
                    dist[u][v] = dist[u][w] + dist[w][v]

    return dict(dist)

Upvotes: 1

Related Questions