Chronicle - 6 months ago 35

Python Question

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:

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:

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.