Answer to Question #294957 in Python for Sathvika Pallapothula

Question

Problem 3: A multi-graph is a graph which may have more than one edge (parallel edges) between a pair of vertices. Suppose that these graphs may also have self-loops (an edge from a vertex to itself). Given such a graph G as an input, print the adjacency list representation of an equivalent undirected graph G’, in which all the multiple edges between two vertices are replaced by a single edge, and all self-loops are removed. Your algorithm should run in O(n+m) time. Input Format: The input is a text file which gives the adjacency list representation of the multigraph. The first line specifies the number of vertices and edges n and m. The next m lines specify the m edges, one edge per line. Assume the vertices are numbered 0 to n-1.

Output Format: The adjacency list representation of the new graph G’.

Sample Input (for the graph above): 3 6

0 0

0 2

2 2

0 2

0 2

0 1

Sample Output: Adjacency list representation of G’: 0: 1 2 1: 0 2: 0

Answer 1

# There is no need to specify the number of vertices and edges in the file as
# this is redundant information. For this reason, the script uses a file that
# contains only the matrix without any other information.
import numpy as np

def read_f(name_f):
    given_file = open(name_f, 'r')

    lines = given_file.readlines()
    digits = []
    for line in lines:
        for c in line:
            if c.isdigit() == True:
                digits.append(int(c))
    given_file.close()
    size_g = int(len(digits)**(1/2))
    digits = np.array(digits).reshape(size_g, size_g)
    for i in range(size_g):
        for j in range(size_g):
            if i == j:
                digits[i][j] = 0
            elif digits[i][j] > 0:
                digits[i][j] = 1
                digits[j][i] = 1
    print("Result matrix: \n", digits)
    print('The adjacency list representation: ')
    for i in range(size_g):
        row = []
        for j in range(size_g):
            if digits[i][j] == 1:
                row.append(j)
        print(f'{i}: ', row)


def main():
    name_f = 'test.txt'
    read_f(name_f)

if __name__ == "__main__":
    main()