Different result upon shuffling a list

Question

I want to divide an uncomplete graph into seperate, unconnected bodies. The edges of the graph are in the list edges.

The code gives a different result upon shuffling the order of the edges. Why is that?

from random import shuffle

edges = [('7', '9'), ('2', '8'), ('4', '10'), ('5', '9'), ('1', '2'), ('1', '6'), ('6', '10')]
bodylist = []
shuffle(edges)

for edge in edges:
    #If at least one node of the edge is anywhere in bodylist, append the new nodes to that list.
    try:
        index = [i for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body][0]
        bodylist[index].append(edge[0])
        bodylist[index].append(edge[1])
    #If not, make a new list containing the new nodes.
    except:
        bodylist.append([edge[0], edge[1]])

print([set(x) for x in bodylist])

Expected output: [{'1', '2', '8', '4', '6', '10'}, {'9', '5', '7'}]

Some of the actual outputs: [{'9', '5', '7'}, {'1', '2', '8'}, {'10', '4', '6', '1'}]

[{'9', '7', '5'}, {'6', '2', '1', '8'}, {'6', '10', '4'}]

Note that the expected output also comes out from time to time. (It should be always so)

I will also appreciate different approaches, since this one is probably not the best.

Answer 1

Suppose you have the three edges [(1, 2), (3, 4), (2, 3)]. This describes a connected graph.

However, your code will first check for (1, 2), find nothing so add this to the bodylist.

Then, it will look for (3, 4), find neither 3 or 4 so add it as a new list.

Finally it will add (2, 3) to the first list but it will not come back to fix its mistake, it will not realize that (3, 4) belong to the same body.

In order to solve this, you can loop entirely through the remaining edges each time you add a new edge to a body in order to check if there is a connection:

while edges:
    current_edge = edges.pop(0)
    body = {current_edge[0], current_edge[1]}
    i = 0
    while i < len(edges):
        if edges[i][0] in body or edges[i][1] in body:
            body.add(edges[i][0])
            body.add(edges[i][1])
            edges.pop(i) # Edge added, no need to check it again
            i = 0 # Restart the loop
        else:
            i += 1
    bodylist.append(body)

What you are looking for is called connected component of a graph.

If you are looking for efficient algorithm, you should take a look to this answer.

Answer 2

This is because your algorithm is wrong. The issue with your algorithm is that it depends on the edges that we start creating the bodies list with. To explain this lets take a simple example of an graph with 4 edges as - edges = [('1','2'),('2','3'),('3','4'),('1','4')] .

First case -

>>> edges = [('1','2'),('2','3'),('3','4'),('1','4')]
>>> bodylist = []
>>> for edge in edges:
...     #If at least one node of the edge is anywhere in bodylist, append the new nodes to that list.
...     try:
...         index = [i for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body][0]
...         bodylist[index].append(edge[0])
...         bodylist[index].append(edge[1])
...     #If not, make a new list containing the new nodes.
...     except:
...         bodylist.append([edge[0], edge[1]])
...
>>> print([set(x) for x in bodylist])
[{'4', '1', '3', '2'}]

You get a single body with the vertices - 1, 2, 3, 4 . Why?

Becuase you started with (1,2) added that to body list. Then you took (2,3) , you see that 2 is already there in the item added in body list, you add it again to the same one and this goes on and all are added to same body.

---

Now , lets take same edges in a different order - edges = [('1','2'),('3','4'),('2','3'),('1','4')] . This turns out as -

>>> edges = [('1','2'),('3','4'),('2','3'),('1','4')]
>>> bodylist = []
>>> .... #same logic
>>> print([set(x) for x in bodylist])
[{'4', '1', '3', '2'}, {'4', '3'}]

As you can see this time, you got two different bodies (and obviously they are wrong) Why?

Again you started with (1,2) , added that to the bodylist as a body, then you took (3,4) , checking this, you see that none of the vertices are already there in any body, hence you added this to a separate body. Taking the third element (2,3) , you see that this is there in both first as well as second body, but your logic is to just take the first body and add the element to that. (Do you see where you are going wrong?)

---

This is why you get different results when you shuffle the list, as the order is important for your logic (which is wrong).

What you need to do is that, if you find vertices for an edge in multiple bodies, you need to merge both bodies into a single body.

---

Another advice, we do not need to add lists into bodylist instead we can use sets for each body .

A sample solution would look like -

from random import shuffle

edges = [('7', '9'), ('2', '8'), ('4', '10'), ('5', '9'), ('1', '2'), ('1', '6'), ('6', '10')]
bodylist = []
shuffle(edges)

for edge in edges:
    bodies = [body for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body]
    if len(bodies) > 0:
        tempset = {edge[0],edge[1]}
        for x in bodies:
            tempset.update(x)
            print('tempset :',tempset)
            bodylist.remove(x)
        bodylist.append(tempset)
    else:
        bodylist.append({edge[0],edge[1]})

print([set(x) for x in bodylist])