1 function prim's algorithm python

Question

i tried to make a 1 function prims algorithm in python but it doesn't seem to be working

def prim(edges):
    inGraph = ['A']
    discovered = []
    results = []
    counter = 0
    while True:
            tmplist = []
            for i in edges:
                    if inGraph[counter] in i:
                            discovered.append(i)
                            tmplist.append(i)
            for i in tmplist:
                    edges.remove(i)
            tmp = []
            for i in discovered:
                    tmp.append(i[2])
            mini = tmp.index(min(tmp))
            alpha = discovered[mini][0]
            beta = discovered[mini][1]

            if alpha not in inGraph or beta not in inGraph:
                    if alpha in inGraph:
                            inGraph.append(beta)
                    elif beta in inGraph:
                            inGraph.append(alpha)
                    results.append(discovered[mini])
            discovered.pop(mini)
            if discovered == []:
                    break
            counter+=1

    return (inGraph, results)

print [['A', 'B', 1], ['A', 'C', 102], ['B', 'C', 4], ['C', 'F', 2], ['B', 'F', 1], ['F', 'E', 1]] print prim([['A', 'B', 1], ['A', 'C', 102], ['B', 'C', 4], ['C', 'F', 2], ['B', 'F', 1], ['F', 'E', 1]])

the problem lies somewhere with discovered, either the if statement checking to see if it's empty or removing an element from it. I'm just not sure where to put it

Never **alter a list while you iterate over it**: do not call `edges.remove(..)` while you loop over it. — Willem Van Onsem, Feb 21 '17 at 15:50
efficiency doesn't matter and it's not editing though a for loop — Sigma 7, Feb 21 '17 at 15:54
yeah I know but the iterator **has a contract** that you are not allowed to alter the list in the meanwhile. — Willem Van Onsem, Feb 21 '17 at 15:54
see [here](http://stackoverflow.com/questions/1207406/remove-items-from-a-list-while-iterating). — Willem Van Onsem, Feb 21 '17 at 15:55
you call **remove** since the iterator internally stores an index, it will start to make jumps of more than one element. — Willem Van Onsem, Feb 21 '17 at 15:57
even if it is not the problem for now I can generate a testcase within two minutes that will make it a problem... (actually there are even programs that can generate such cases :) — Willem Van Onsem, Feb 21 '17 at 15:58
of course: since you modify the `edges` list while iterating over it, **not all elements will be iterated**, and thus not **all** edges can be discovered. The one problem is linked (if not completely linked) to the other :) — Willem Van Onsem, Feb 21 '17 at 16:01
can you tell me how to fix it, you can't just delete edges.remove(i) — Sigma 7, Feb 21 '17 at 16:02
what about constructing a temporary list of items you have to remove later in the process when the loop has ended? — Willem Van Onsem, Feb 21 '17 at 16:02
do i replace edges with the temp list after or does it stay the same? — Sigma 7, Feb 21 '17 at 16:04
In the list you store each edge you plan to remove, next you iterate over the temp list and remove the edges from the `edges` list. Next you can throw away the temp list. — Willem Van Onsem, Feb 21 '17 at 16:05

Shihab Shahriar Khan · Answer 1 · 2017-02-21T17:00:21.310

0

Imagine only one vertex is connected with 'A', say 'B'. So, at first iteration, you will have only one edge in discovered. After adding 'B' to inGraph, you are popping that only edge from discovered.

So your discovered == [] becomes true and loop breaks, even though there might still be thousand edges connected with 'B'.

To terminate the main loop, calculate the no of vertex and break if len(inGraph)==no_of_vertex.

To do that, you can:

V = set()
for e in edges:
    v.add(e[0])
    v.add(e[1])
no_of_vertex = len(V)
V = None #To help garbage collector

edited Feb 21 '17 at 17:00

answered Feb 21 '17 at 16:06

Shihab Shahriar Khan

4,930
1
18
26

so where do i put the if statement or the `discovered.pop(mini)` – Sigma 7 Feb 21 '17 at 17:49
would this just be added near the end of the function? – Sigma 7 Feb 21 '17 at 18:07
i put it at the end and got this error `Traceback (most recent call last): File "prim.py", line 40, in print prim([['A', 'B', 1], ['A', 'C', 102], ['B', 'C', 4], ['D', 'B', 7], ['D', 'F', 240], ['C', 'F', 2], ['B', 'F', 1], ['F', 'E', 1]]) File "prim.py", line 17, in prim mini = tmp.index(min(tmp)) ValueError: min() arg is an empty sequence` – Sigma 7 Feb 21 '17 at 18:20
at the beginning of function, before while loop starts. – Shihab Shahriar Khan Feb 21 '17 at 20:00

1 function prim's algorithm python

1 Answers1