CODEWITHSUNDEEP
pythondiscrete-mathematicsdigraphs
icodealittle
icodealittle

Reputation: 11

Read digraph from a file

Hi all – I'm new to coding if anybody is wondering.

This is my first time posting here and I'm currently stuck on one of my assignments. The code below is my draft code.

The expected output for adjacency_list is:

[[1,3], [2], [3], [0,2]]
# with possibly [3,1] instead of [1,3] or [0,2] instead of [2,0]

The output from my code is:

[[1, 3], [2], [3], [0, 2]] – which is what I wanted

And for the expected output for maximal_path is:

[0, 1, 2, 3] and [0, 3, 2]

Whereas my output is:

[0, 1, 3, 2] – which is totally different from the expected output that my professor wanted. I have been going through the second function and keep hitting a dead end. Can anyone show where my mistake is with the second function?

Here is the digraph.txt list: 

6 4
0 1
0 3
1 2
2 3
3 0
3 2

–

Thank you!

def adjacency_list(file_name):

    # create empty list
    adj_temp_list = []

    # open input file
    f = open('digraph0.txt','r')

    # read first line
    in_file = f.readline()

    first_row = [int(i) for i in in_file.strip().split()]

    # first_row[0] represents number of edges and first_row[1] represents number of vertices

    # add number of vertices amount of empty lists to adj_temp_list
    for i in range(first_row[1]):

        adj_temp_list.append([])

    # read edges( each line represents one edge)
    for i in range(first_row[0]):
        line = f.readline()

        # split the line and convert the returned list into a list of integers
        vertex=[int(i) for i in line.strip().split()]

        # vertex[0] and vertex[1] represents start vertex and end vertex respectively.
        # that is, vertex[1] is adjacent vertex or neighbour to vertex[0]
        # Thus, append vertex[1] to the adjcency list of vertex[0]

        adj_temp_list[vertex[0]].append(vertex[1])

    # close input file
    f.close()

    # create a new empty list
    adj_list=[]

    # sort each list in the adj_temp_list and append to adj_list
    for lst in adj_temp_list:
        lst.sort()
        adj_list.append(lst)

    # return the adjacency list
    return adj_list

def maximal_path(file_name,start):

    # call adjacency_list function to get adjacency list
    adj_list=adjacency_list(file_name)

    # create max_path as an empty list
    max_path=[]

    # create a boolean list that represents which vertex is added to path
    # Thus, initialize the list such that it represents no vertex is added to path
    visited=[False]*len(adj_list)

    # create an empty list(stack)
    stack=[]

    # add start vertex to stack list
    stack.append(start)

    # process until there is no possibility to extend the path
    while True:

    # get a node u from stack and remove it from stack
        u=stack[0]
        stack=stack[1:]

    # set vertex u visited and add it to max_path
        visited[u]=True
        max_path.append(u)

    # find whether u has unvisited neighbours to extend path or not
        existNeighbour=False
        for v in adj_list[u]:
            if visited[v]==False:
                existNeighbour=True
                break

    # if u has unvisited adjacent vertices
        if existNeighbour==True:

        # push all un-visited neighbours into stack
            for v in adj_list[u]:
                stack.append(v)

    # if u has no unvisited adjacent vertices, exit the loop
        else:
            break

# return the maximal path
    return max_path

Upvotes: 1

Views: 371

Answers (1)

eshanrh
eshanrh

Reputation: 348

Your approach is what's known as a Breadth First Search, or BFS. When you append new nodes to the end of the stack, the graph is explored layer by layer. The most minimal change you can make to your program to get your expected output is to insert the new nodes in the beginning of the stack.

stack.insert(0,v)

Upvotes: 0

Related Questions