Chronicle Chronicle - 21 days ago 6
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:

nodes, ungrouped

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:

nodes, grouped properly

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:
for line in f.readlines():
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:

nodes, grouped wrongly

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.

Answer

I'm not sure if it works in every edge case, but if you can find a path through the graph that passes through every node once, you can just group that path into sections of three. Depending on the size of the graph, you could potentially do that with a simple DFS.

EDIT: For this to work you need to trim off all tails (paths of no return) but that just means you'll need to count off the nodes slightly differently when you're grouping the ones adjacent to the tail.