I have this code, which adds edges with a weight to a graph from adjacency matrix:

matrix = [[0, 1, 2, 3, 4],
          [1, 0, 5, 6, 0],
          [2, 5, 0, 0, 0],
          [3, 0, 0, 0, 6],
          [4, 0, 0, 6, 0]]


g1 = Graph(len(matrix))
for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] > 0:
            g1.add_edge(i, j, matrix[i][j])

The problem with this code is that it adds same edges twice, f.e it adds edge 0 - 1 and 1 -0, 0 - 2 and 2 - 0. What I want is to add those edges only once. Is this possible somehow?

I added this print print(f'Addind edge {i}-{j} with weight {matrix[i][j]}') statement so you could see what is happening. Output:

Addind edge 0-1 with weight 1
Addind edge 0-2 with weight 2
Addind edge 0-3 with weight 3
Addind edge 0-4 with weight 4
Addind edge 1-0 with weight 1
Addind edge 1-2 with weight 5
Addind edge 1-3 with weight 6
Addind edge 2-0 with weight 2
Addind edge 2-1 with weight 5
Addind edge 3-0 with weight 3
Addind edge 3-4 with weight 6
Addind edge 4-0 with weight 4
Addind edge 4-3 with weight 6

CodePudding user response：

One way to solve this is to add an additional check for the edge that is being added, before actually adding the edge. For example, you can add a check to make sure the edge is not already present in the graph. You can do this by looping through the graph and checking if the edge is already present before adding it.

Here is an example of how to do this:

g1 = Graph(len(matrix))
for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] > 0:
            # check if the edge is already present
            if not g1.has_edge(i, j):
                g1.add_edge(i, j, matrix[i][j])

CodePudding user response：

To add edges to a graph from an adjacency matrix such that each edge is added only once, you can use the following approach:

1. Check if the value at the current matrix[i][j] position is greater than 0. This indicates that there is an edge between the vertices i and j with weight matrix[i][j].
2. If matrix[i][j] is greater than 0, check if j is greater than i. This ensures that we only add each edge once, since for an undirected graph, the edge i-j is the same as the edge j-i.
3. If j is greater than i, add the edge i-j to the graph with weight matrix[i][j]. Here is an example of how you can modify your code to implement this approach:

matrix = [[0, 1, 2, 3, 4],
          [1, 0, 5, 6, 0],
          [2, 5, 0, 0, 0],
          [3, 0, 0, 0, 6],
          [4, 0, 0, 6, 0]]

g1 = Graph(len(matrix))
for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] > 0 and j > i:  # Check if matrix[i][j] is greater than 0 and j is greater than i
            g1.add_edge(i, j, matrix[i][j])  # Add edge i-j with weight matrix[i][j]

With this change, the code will only add each edge once, resulting in the following output when you print the edges in the graph:

Addind edge 0-1 with weight 1
Addind edge 0-2 with weight 2
Addind edge 0-3 with weight 3
Addind edge 0-4 with weight 4
Addind edge 1-2 with weight 5
Addind edge 1-3 with weight 6
Addind edge 3-4 with weight 6