Chronicle - 1 year ago 98
Python Question

# Dividing connected nodes into groups of three

I have a collection of objects (I'll call them nodes) that are connected to each other. Every node is connected to at least one other node, and the entire collection of nodes is one big blob (no outliers). The number of nodes is a multiple of three.

What I want to do is divide the nodes into groups of three connected nodes (with no overlapping between groups).

Every node has a unique ID. The nodes are stored in a document wherein every line is the ID of a node followed by the nodes it is connected to. It looks something like this:

``````30:240
40:210/240/230/60
50:80/220/230/70/210/190/200
60:240/40/230/220
70:90/200/50/220
80:50/170/190/210
90:200/70/180
100:110/160/190/170/200/180
110:100/180
160:170/100
170:80/160/190/100
180:90/200/110/100
190:50/80/200/170/100
200:90/70/100/50/190/180
210:50/80/40/230
220:50/230/70/60
230:50/210/60/40/220
240:40/30/60
``````

I've made some images to help visualize it:

I want to divide my nodes into groups of three, but they must be connected. There are many possible combinations of grouping the nodes. One possibility is the following image:

However, I am struggling to come up with an algorithm that can ensure that every node is in a group of three connected nodes (and no overlapping). In order to avoid overlapping, I "claim" nodes while making groups, which is my way of checking if a node already belongs to another group.

I have come up with the following code:

``````nodes = dict()
with open("input.txt") as f:
split = line.split(":")
node = int(split[0])
nodes[node] = []
for connection in split[1].split("/"):
nodes[node].append(int(connection.strip()))
groups = dict()
claimed = []
for node in nodes:
if node in claimed:
continue
connections = nodes[node]
if len(connections) > 1:
for i in range(len(connections)):
if node in groups and len(groups[node]) == 2:
break
if not connections[i] in claimed:
if not node in groups:
groups[node] = []
groups[node].append(connections[i])
claimed.append(connections[i])
if not node in claimed:
claimed.append(node)
f = open("output.txt",'w')
for group in groups:
line = str(group) + ":"
for node in groups[group]:
line += str(node) + "/"
line = line[:-1] + "\n"
f.write(line)
f.close()
``````

However, this produces the following:

``````160:170/100
80:190
230:50/210
70:90/200
110:180
240:40/30
220:60
``````

Which can be visualized like this:

As you can see, there are four groups of three (in blue), and three groups of two (in orange). This is because I claim nodes as I am making the groups, causing some nodes to no longer have two unclaimed connected nodes for a group.

So my question is: How can I have my nodes claim connected nodes in such a way that other nodes can still form their own groups of three?

Or more basically: How can I divide connected nodes into groups of three connected nodes with no overlapping? Every node needs to be in a group of three.

My question is more about the algorithm than code. I am also open to an entirely different algorithm.