Question

You will implement two algorithms to find the shortest path in a graph.

def prim(G,start_node): Takes a graph G and node to start at. Prims edges used in MST.

def kruskal(G): Takes a graph G and prints the edges in the MST in order found.

You may represent the graphs as adjacency matrix or list. You MAY NOT include any graph libraries.

The graph you are working on will be give in a file with the following format. The graph is undirected. That means if an edge from 2 to 1 is in the file, it may be used in both directions.

• Line 1: The number of Nodes in the Graph
• Lines 2-EOF: Every other line in the file contains an edge
  • First Value is the first node
  • Second Value is the second node
  • Third Value is the weight of the edge

Note: You should store the weights as floats.

The program will have a text interface. First ask for the file name of the graph to work with. Then implement 4 text commands.

prim x - Runs Pim's Algorithm starting at node X. X must be an integer

kruskal - Runs Kruskal's algorithm

help - prints this list of commands

exit - Exits the program

On a bad command print out "Unknown Command"

You must implement this using only standard python3 libraries. You may not use any outside libraries. For example, open source graph libraries.

When printing an edge, always print the smaller vertex first then the larger vertex.

Example Execution Traces are provided below.

Welcome to Minimum Spanning Tree Finder

Give the file name graph is in:

input1.txt

Commands:

exit or ctrl-d - quits the program

help - prints this menu

prim integer_value - run's Prim's algorithm starting at node given

kruskal - runs Kruskal's algorithm

Enter command:

Bad Command Unknown Command

Enter command:

help

Commands:

exit or ctrl-d - quits the program

help - prints this menu

prim integer_value - run's Prim's algorithm starting at node given

kruskal - runs Kruskal's algorithm

Enter command:

prim 0

Running Prim's Algorithm Starting Node: 0

Added 2

Using Edge [0, 2, 1.0]

Added 5

Using Edge [2, 5, 4.0]

Added 3

Using Edge [3, 5, 2.0]

Added 1

Using Edge [1, 2, 7.0]

Added 4

Using Edge [1, 4, 3.0]

Enter command:

exit

Bye

The content of the files is shown below.

input1.txt

6
0 3 5
3 5 2
5 4 10
4 1 3
1 0 8
0 2 1
2 3 6
2 5 4
2 4 9
2 1 7

input2.txt

9
0 1 4
0 7 10
1 7 13
7 8 9
7 6 1
1 2 8
8 2 3
8 6 6
2 3 7
2 5 5
6 5 2
3 5 14
3 4 11
5 4 12

input3.txt

8
4 5 35
4 7 37
5 7 28
0 7 16
1 5 32
0 4 38
2 3 17
1 7 19
0 2 26
1 2 36
1 3 29
2 7 34
6 2 40
3 6 52
6 0 58
6 4 93

Answer 1

python code

solution

//output

//copyable code

#declare the variable data and debug_value

data = False

debug_value = False

# Global variables

D_istinct_Nodes = None

Graph_Nodes = [[None]]

#function prim algorithm

def prim(Graph_Nodes, start_node):

    G1 = Graph_Nodes

    global D_istinct_Nodes

    D_istancevalue = [float("inf") for k in range(0, len(G1))]

    D_istancevalue[start_node] = 0

    d_Nodes = D_istinct_Nodes

    d_Nodes.remove(start_node)

    number_nodes = len(d_Nodes);

    lastNode = start_node

    #check the condition if weight node is less than zero

    while len(d_Nodes) > 0:

        small_valueWeight = float("inf")

        new_Node = -1

        small_Inode = -1

        small_Jnode = -1

        #calculate the distance

        for i1 in range(0, len(G1)):

            for j1 in range(0, len(G1)):

                if i1 not in d_Nodes or j1 in d_Nodes:

                    continue

                if G1[j1][i1] < small_valueWeight:

                    small_valueWeight = G1[j1][i1]

                    new_Node = i1

                    small_valueI = j1

                    small_valueJ = i1

                if G1[i1][j1] < small_valueWeight:

                    small_valueWeight = G1[i1][j1]

                    new_Node = i1

                    small_valueI = i1

                    small_valueJ = j1

        if small_valueWeight == float("inf"):

            break

        G1[small_valueI][small_valueJ] = float("inf")

        G1[small_valueJ][small_valueI] = float("inf")

        print("Added " + str(new_Node))

        print("Using Edge [" + str(small_valueI) + "," + str(small_valueJ) + "," + str(small_valueWeight) + "]")

        d_Nodes.remove(new_Node)

        lastNode = small_valueI

#kruskal algorithm

def kruskal(Graph_Nodes):

    G = Graph_Nodes

    global D_istinct_Nodes

    #calulate the distance nodes

    D_istancevalue = [float("inf") for i1 in range(0, len(G))]

    d_Nodes = D_istinct_Nodes

    number_nodes = len(d_Nodes);

    Distinct_Edges = None

    while len(d_Nodes) > 0:

        small_valueWeight = float("inf")

        new_Node = -1

        small_Inode = -1

        small_Jnode = -1

        #check the weight nodes

        for i1 in range(0, number_nodes):

            for j1 in range(0, number_nodes):

                if j1 not in d_Nodes and i1 not in d_Nodes:

                    continue

                if G[j1][i1] < small_valueWeight:

                    small_valueWeight = G[j1][i1]

                    new_Node = i1

                    small_valueI = j1

                    small_valueJ = i1

                if G[i1][j1] < small_valueWeight:

                    small_valueWeight = G[i1][j1]

                    new_Node = i1

                    small_valueI = i1

                    small_valueJ = j1

        if small_valueWeight == float("inf"):

            break

        G[small_valueI][small_valueJ] = float("inf")

        G[small_valueJ][small_valueI] = float("inf")

        if Distinct_Edges is None or not (small_valueI in Distinct_Edges[0] and small_valueJ in Distinct_Edges[0]):

            print("Select Edge [" + str(small_valueI) + "," + str(small_valueJ) + "," + str(small_valueWeight) + "]")

        if Distinct_Edges is None:

            Distinct_Edges = [[small_valueI, small_valueJ]]

        else:

            Distinct_Edges.append([small_valueI, small_valueJ])

        last_Index = len(Distinct_Edges) - 1

        for i1 in range(len(Distinct_Edges) - 1, 0, -1):

            if (small_valueI in Distinct_Edges[i1 - 1] or small_valueJ in Distinct_Edges[i1 - 1]) and (

                    small_valueI in Distinct_Edges[last_Index] or small_valueJ in Distinct_Edges[last_Index]):

                for node in Distinct_Edges[last_Index]:

                    Distinct_Edges[i1 - 1].append(node)

               

                Distinct_Edges.remove(Distinct_Edges[last_Index])

                last_Index = i1 - 1

        count = 0

        for i1 in range(0, number_nodes):

            if i1 in Distinct_Edges[0]:

                count += 1

               

        if len(Distinct_Edges) == 1 and count >= number_nodes:

            break

#dijstra algorithm          

def Dijkstra(G, start_node):

    global D_istinct_Nodes

    D_istancevalue = [float("inf") for i1 in range(0, len(G))]

    prev = [None for i1 in range(0, len(G))]

    D_istancevalue[start_node] = float(0)

    d_Nodes = D_istinct_Nodes

    while len(d_Nodes) > 0:

        small_value = [-1, -1, float("inf")]

        for i1 in range(0, len(d_Nodes)):

            for j1 in range(0, len(d_Nodes)):

                D_i = d_Nodes[i1]

                Dj = d_Nodes[j1]

                if G[D_i][Dj] < small_value[2]:

                    small_value = [D_i, Dj, float(G[D_i][Dj])]

        smallNode = small_value[0]

        if smallNode < 0:

            break

        d_Nodes.remove(smallNode)

        for j1 in range(0, len(G)):

            # if G[i][j] != float("inf"):

            alt = float(D_istancevalue[smallNode] + G[smallNode][j1])

            if alt < D_istancevalue[j1]:

                D_istancevalue[j1] = alt

                prev[j1] = smallNode

    return D_istancevalue

#floyd algorithm

def floyd(inG):

    G = inG

    for i1 in range(0, len(G)):

        G[i1][i1] = float(0)

    for i1 in range(0, len(G)):

        for j1 in range(0, len(G)):

            for k1 in range(0, len(G)):

                if G[i1][j1] > (G[i1][k1] + G[k1][j1]):

                    G[i1][j1] = G[i1][k1] + G[k1][j1]

    return G

#help command

def print_Help():

  

    print(

        "Commands: \n exit or ctrl-d - quit the program\n help - prints this menu\nprim integer_value - run's Prim's algorithm starting at node given\nkruskal - runs Kruskal's algorithm")

#make graph node generated

def makeGraph_Nodes(in_fileName):

    try:

        in_file = open(in_fileName, 'r')

    except IOError:

        print("Invalid file...\n")

        exit(-1)

    else:

        global Graph_Nodes

        global D_istinct_Nodes

        number_nodes = int(in_file.readline())

        Graph_Nodes = [[float("inf") for i1 in range(0, number_nodes)] for j1 in range(0, number_nodes)]

        D_istinct_Nodes = [i1 for i1 in range(0, number_nodes)]

        line1 = in_file.readline()

        while line1 != "":

            fields = line1.split(" ", line1.count(" "))

            Graph_Nodes[int(fields[0])][int(fields[1])] = float(fields[2])

            line1 = in_file.readline()

    in_file.close()

#display the nodes

def printGraph_Nodes():

    number_nodes = len(Graph_Nodes)

    for i in range(0, number_nodes):

        for j in range(0, number_nodes):

            print(i, j, Graph_Nodes[i][j])

#print the output part

print("Welcome to Minimum Spanning Tree ")

in_fileName = ""

if debug_value:

    #input file

    in_fileName = "input1.txt"

else:

    if data:

        in_fileName = input("Give the filename Graph_Nodes is in: ")

    else:

        in_fileName = input("Give the filename Graph_Nodes is in: ")

makeGraph_Nodes(in_fileName)

if debug_value:

    printGraph_Nodes()

print_Help()

while True:

    makeGraph_Nodes(in_fileName)

    in_Command = ""

    if data:

        in_Command = input("please Enter command: ")

    else:

        in_Command = input("please Enter command: ")

    if in_Command == "exit":

        print("Bye")

        break

    elif in_Command.find("floyd") != -1:

        makeGraph_Nodes(in_fileName)

        D_istancevalues = floyd(Graph_Nodes)

        for i in range(0, len(D_istancevalues)):

            print(D_istancevalues[i])

        if debug_value:

            print("Floyd")

   elif in_Command.find("Dijkstra") != -1:

        param = int(in_Command.split(" ", 2)[1])

        output = Dijkstra(Graph_Nodes, param)

        print(output)

        if debug_value:

            print("Dijkstra");

    elif in_Command.find("prim") != -1:

        param = int(in_Command.split(" ", 2)[1])

        prim(Graph_Nodes, param)

    elif in_Command.find("kruskal") != -1:

        print("Kruskal's Algorithm")

        kruskal(Graph_Nodes)

    elif in_Command == "help":

        print_Help()

    elif in_Command == "pg":

     printGraph_Nodes()