Problem definition
I've got a connected, undirected graph with n nodes and root r. I need to find all combinations of paths with a length in range(l) that connect all the nodes.
In the end I want to find the optimal combination of paths, where the weight of the edge is determined by both the length and its location in the sequence.
I've tried some solution directions, but end up with so many options that it becomes a computational nightmare. In my case, n = 35, all nodes have degree 8 to 10 and path length should be 7 or 8.
I'm using Python 3.5.
Possible solutions
In all cases I start with defining all possible paths. Therefor I use a solution with the NetworkX package as found here: All paths of length L from node n using python
# Create a random graph that looks like the real one
G = nx.dense_gnm_random_graph(n=35, m=164, seed=0)
# Find all paths from root with length 0 to 8
n = 0
L = 8
no_n_node = G.nodes()
no_n_node.remove(n)
result = []
for paths in (nx.all_simple_paths(G=G, source=n, target=target, cutoff=L) for target in no_n_node):
result+=paths
# Only keep paths of length 7 or 8
res78 = []
for path in result:
if len(path) >= 8:
res78.append(path[1:])
This results in 24,383,690 paths, reduced to 'only' 3,181,622 collections of 7 or 8 points (order of nodes in path neglected)
This is where I get stuck, as I now want to find all combinations of the found paths that visit all nodes, but all only once.
How to proceed, option 1
My first idea was to brute force: - for all unique paths, remove nodes from graph - compute all paths of length in range(l) in remaining graph - etc But this are way too many computations
How to proceed, option 2
The other idea I had was to find, independent of their connections, all possible combinations of nodes that combined contain all nodes once (the spanning set). How to compute a spanning set, I based on Algorithm to generate (not quite) spanning set in Python
data = G.nodes()
data.remove[0]
from itertools import combinations
def cut(lst, indexes):
last = 0
for i in indexes:
yield tuple(lst[last:i])
last = i
yield tuple(lst[last:])
def generate(lst, n):
for indexes in combinations(tuple(range(1,len(lst))), n - 1):
yield (tuple(cut(lst, indexes)))
This results in a list of 2^n. I tried to make a spanning set with only sub_sets of length 7 or 8, but didn't know how to do it.
I guess it's still computational too heavy, but what I then wanted to do is: - get out of the spanning sets, only the ones that contain only collections that also can be found in the paths - for all this subset, find the shortest path in the collection, starting from the root (traveling salesman problem)
edit/addition
Different direction
An other direction I thought about after a nights sleep, is to find all the spanning trees, only keep the one that don't have sub-branches and only have branches of certain length. Remaining question: how to find all spanning trees? I found How to efficiently generate all possible spanning trees from a graph that might get me started.
end of edit
Does anyone have suggestions on how to optimize the algorithms I use or know a function in NetworkX that I missed but will make it all somewhat easier?
