Given a mechanical assembly as a graph, how to find an upper bound on number of assembly paths

Question

The rules are that you can only build from an existing part, so in the example below, B is the only option for the first move = A.

A mechanical assembly might be represented as follows:

  E
  |
  C
  |
A-B
  |
  D
  |
  F

Where the valid assembly paths when starting from A are:

A, B, C, E, D, F
A, B, C, D, E, F
A, B, C, D, F, E
A, B, D, F, C, E
A, B, D, C, F, E
A, B, D, C, E, F

This is a fairly simple example, but providing an upper bound for an arbitrary assembly is difficult since it's related to the "connectivity" of the parts.

n! would be an absolute upper bound I guess, but I'm hopping to find something a little better.

I've also looked at representing the graph with the parts (A, B, C, etc) as the edges and doing Kirchhoff's theorem, but that doesn't work for sparsely connected graphs like the example above.

Any information about the problem would help. I'm not sure if there's a formal description of this type of problem or not.

Answer 1

Your question is quite open-ended, in that you have not specified how accurate the upper bound should be, nor how efficient the algorithm should be. There is certainly a trade-off between the run-time and the accuracy.

---

Ways to get an exact answer:

• Naive brute force - I guess you know what this means (very slow)

• Observe that it is easy to calculate the number of ways of the graph is a tree (start from the leaves, and when they join up, just count number of ways of joining the two branches

  ie. #ways = #ways(branch A) * #ways(branch B) * {#nodes(branch A) + #nodes(branch B)} Choose #nodes(branch A)

  Thus iterate over all possible trees, and sum up the number of ways of assembling the tree.

  This method is faster than a naive brute force, but it is still brute forcing on all the trees

---

For an upper bound:

• $n!$ - very quick but not accurate

• Using the same observation as before (easy to calculate number of ways for a tree), you can use the quick method for all subtrees/leaves off the main component. Then join it all up.

  For example, suppose the main component connected to the root has $a_0$ nodes, then you have two subtrees hanging off that main component with $a_1$ and $a_2$ nodes, each with $b_1$ and $b_2$ ways of assembling them respectively.

  Then, letting $b_0$ = $a_0!$ (an upper bound on the main component), an upper bound on the whole graph is $b_0b_1b_2\frac{(a_0a_1a_2)!}{a_0!a_1!a_2!}$.

  This method is very quick, but although it is a much better upper bound than $n!$, it can still be very far off the exact answer.

• A refinement to either of the above methods can be made, by considering the earliest that a particular node can appear in the sequence. Basically, it is a way of counting such that, for example, since you know $B$ can never be the 1st in the sequence, and $C$ is 3rd or later, etc., you can count in such a way to avoid that possibility.

  For example, in the above example, first consider that there are 2 ways of ordering $E$, $F$, in places 4-6, call this sequence $s_1$. Then there are 2 ways of ordering $C$, $D$ in places 3-6 (sequence $s_2$). So you can now merge the two sequences. Because the intersection of their possible places is 4-6, you know that in place 4-6, there is one element from $s_2$ and two elements from $s_1$. Thus, the number of ways of merging them is $\frac{3!}{2!1!}=3$, thus the merger of the two sequences results in a sequence with $2\times 2 \times 3=12$ ways, in a possible range of places ranked 3-6. After merging with a subsequence consisting of $B$ and a subsequence consisting of just $A$, you have an upper bound of $12$ ways of assembling it.

• Further refinement may also be made by considering the latest a node can appear (eg. $C$ and $D$ cannot be in place 6. Thus, when merging sequences $s_1$ and $s_2$, an even better upper bound is $2\times 2 \times \frac{2!}{1!1!}=8$ ways.

---

There may be other ways I cannot think of. But each refinement will add complexity, and running time to your algorithm.

I am unsure if there exists an efficient algorithm for finding the exact answer (in $P$ time).