Search code examples
pythonpython-3.xgraph-theoryadjacency-matrix

Correctly changing the values of an adjacency matrix to represent an undirect graph

I am trying to solve a question on graphs. However, a really strange error is happening while I try to build the adjacency matrix.

This is the task: enter image description here

This is the input in an easy copy/paste format:

4 4
1 2
3 2
4 3
1 4
1 4

These are the steps so far that I did trying to solve the problem:

  1. Read the input data
  2. Make edges like a pair (tuple) of two vertexes, for instance, (v1, v2) express that there is an edge between vertex 1 and 2.

  3. Based on the "n" number of Edges, I created a "nxn" quadratic matrix. I filled all the items as 0s. On the next step, I try to change "0" to "1" if there is a connection between vertexes.

    Observation: I created two functions. One to create a adjacency matrix to be filled. Another, named fill_matrix to change zeros (0) to ones (1) when appropriate.

  4. Now is where the problem appears. I tried to iterate over my edges and change the Adjacency Matrix.

However, a bizarre thing happens. The same function, with the same parameters, provide different outputs. I really don't understand why this is happening!

This is my code so far:

#Uses python3

import sys

input = sys.stdin.read()
#print ("input", input)

data = list(map (int, input.split()))
#print ("data", data)

nodes_num = data[0]
#print ("number of nodes", nodes_num)

edges_num = data[1]
#print ("number of edges", edges_num)

data = data[2:]
#print ("data withou initial numbers", data)

vertex_start = data[-2]
#print ("initial node", vertex_start)

vertex_end = data[-1]
#print ("final node", vertex_end)

data_edges = data[0:len(data)-2]
#print ("list with the relation of the edges", data_edges)

# this function cnverts the list of edges in appropriate pairs as tupples
def make_edge_pairs(edges_list):

    edges_list_even = edges_list[::2]
    edges_list_odd = edges_list[1::2]
    # using zip function to interlacte odds and events as proper pairs
    edges_tuples_objects = zip(edges_list_even,edges_list_odd)
    edges_list_tuplas = [ ]

    for pair in edges_tuples_objects:

        edges_list_tuplas.append(pair)

    return edges_list_tuplas

def create_adjacency_matrix(vertex_num):

    adj_matrix = []
    lines_list = []

    for i in range(0,vertex_num):

        lines_list.append(0)

    for j in range(0,vertex_num):
        adj_matrix.append(lines_list)

    return adj_matrix

matriz_adj = create_adjacency_matrix(nodes_num)
print ("matriz adj",matriz_adj)

in_case_edges_list = make_edge_pairs(data_edges)
print ("in_case_edges_list", in_case_edges_list)

edges_list = [(1, 2), (3, 2), (4, 3), (1, 4)]
print ("edges_list", edges_list)

matrix_to_be_fill = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
print("matrix_to_be_fill",matrix_to_be_fill)

print(matrix_to_be_fill==matriz_adj)
print (edges_list==in_case_edges_list)

def fill_matrix(matrix, edges_list):

    #print (matrix, edges_list)

    for tupla in edges_list:
       lin = (tupla[0]) - 1
       col = (tupla[1]) - 1
       matrix[lin][col] = 1
       matrix[col][lin] = 1
    return matrix

print (fill_matrix(matriz_adj,in_case_edges_list))
print (fill_matrix(matrix_to_be_fill,in_case_edges_list))

This excerpt guarantees that the inputs are the same since both return True:

print(matrix_to_be_fill==matriz_adj)
print (edges_list==in_case_edges_list)

However, the functions with the same outputs return different outputs:

print (fill_matrix(matriz_adj,in_case_edges_list))
print (fill_matrix(matrix_to_be_fill,in_case_edges_list))

I wish this list of lists as the output in both cases:

[[0, 1, 0, 1],
 [1, 0, 1, 0],
 [0, 1, 0, 1],
 [1, 0, 1, 0]]

This is the correct representation of the relationship between vertexes!

I know there are other forms of representing the relationship between vertexes and edges in Python. But I would like to fix this and continue to work on this approach.

I run the code with:

python3 reachability.py < sample_1.txt

The file sample_1.txt just have the input I showed before.

Solution

  • The issue is that every row is the same list:

    def create_adjacency_matrix(vertex_num):

    adj_matrix = []
    lines_list = []

    for i in range(0,vertex_num):

        lines_list.append(0)

    for j in range(0,vertex_num):
        adj_matrix.append(lines_list)

    return adj_matrix

    Change adj_matrix.append(lines_list) to adj_matrix.append(lines_list[:])

    Or write it as:

    def create_adjacency_matrix(vertex_num):

    adj_matrix = []

    for j in range(0,vertex_num):
        lines_list = []

        for i in range(0,vertex_num):
            lines_list.append(0)

        adj_matrix.append(lines_list)

    return adj_matrix