I have a sort of a one level tree structure as:
Where p are parent nodes, c are child nodes and b are hypothetical branches.
I want to find all combinations of branches under the constraint that only one parent can branch to only one child node, and two branches can not share parent and/or child.
E.g. if combo
is the set of combinations:
combo[0] = [b[0], b[3]]
combo[1] = [b[0], b[4]]
combo[2] = [b[1], b[4]]
combo[3] = [b[2], b[3]]
I think that's all of them. =)
How can this be achived automaticly in Python for arbitrary trees of this structures i.e. the number of p:s, c:s and b:s are arbitrary.
EDIT:
It is not a tree but rather a bipartite directed acyclic graph
Here's one way to do it. There are lot's of micro-optimizations that could be made but their efficacy would depend on the sizes involved.
import collections as co
import itertools as it
def unique(list_):
return len(set(list_)) == len(list_)
def get_combos(branches):
by_parent = co.defaultdict(list)
for branch in branches:
by_parent[branch.p].append(branch)
combos = it.product(*by_parent.values())
return it.ifilter(lambda x: unique([b.c for b in x]), combos)
I'm pretty sure that this is at least hitting optimal complexity as I don't see a way to avoid looking at every combination that is unique by parent.