Search code examples
pythonadjacency-matrixminimum-spanning-tree

Shortcut to creating an adjacency matrix


I need a short and sweet version of the python code I wrote. So basically what I have is a text file with values such as below:

x
a b c
d e f

First line is the number of nodes. From second line, the values are read into NODE1, NODE2, Weight. I am taking these values and creating an adjacency matrix out of it. This will be an undirected graph so matrix[u][v] will equal matrix[v][u]. This is the code I have :

with open(filename, 'r') as textfile:
            firstLine = int(textfile.readline())
            for line in textfile:
                a, b, c = line.split()
                a = int(a)
                b = int(b)
                c = float(c)
                graph[a][b] = graph[b][a] = c

Now I need to populate the diagonals as zero, and other unassigned indices to infinity.


Solution

  • with open(filename, 'r') as textfile:
        file_lines = text_file.readlines()
    
        # Initialize graph with -1 value, i.e. path do not exists representing infinite
        # Note: If negative weight is allowed, use the value which you want to symbolize infinte
        total_node = int(file_lines[0])
        my_graph = [[-1]*total_node]*total_node
    
        # Update weight based on available path
        for line in file_lines[1:]:
            s = line.split()
            u, v, w = int(s[0]), int(s[1]), float(s[2])
            my_graph[u][v] = my_graph[v][u] = w
    
        # Update diagonals to zero
        for i in range(total_node):
            my_graph[i][i] = my_graph[i][total_node - (i+1)] = 0