joy13975
commented
5 years ago After some research, it turns out that hub selection as defined above (as a result of previous discussion with Fabio) is similar to the Graph Coloring Problem (NP-complete/NP-hard with optimization). In particular, we want to test all coloring configurations and not just one possible configuration (in which case there is optimized algorithm for k>3). Below is why I think elfin needs to solve this another way, or solve a smaller problem than defined above.
Consider a user-designed path guide network forming a # (hash/pound/sharp) shape, which has 4 branchpoints (each with 4 branches). Let's narrow the case by making Assumption A: that the user intends the branchpoints to have higher spatial priority than the bridges steming from them (the 1H and 2H cases). This means elfin should place hubs at exactly the translation specified by the branchpoints indead of trying to move them for overal optimality.
With the current module database (xdb.json), there is exactly one hub module that is able to implement a four-way branchpoint as such (the D49_aC2_ext hub). There are four branchpoints, at each of which a D49_aC2_ext instance can be in one of four distinct orientations - imagine aligning a + sign to an x sign.
If we can constrain D49_aC2_ext to those four orientations (i.e. assuming finding those orientations against user-defined path guide branches can be done in constant time), then there are as many as 4^4 = 256 hub configurations. With future hubs it may be possible to reduce the number of hub configurations by termini "path-compatibility"-based elimination (testing whether there exists a path between the source and destination termini), but in the D49_aC2_ext hub, every terminus is path-compatible with every other terminus, so there's no elimination.
The number of hub configurations C can be formulated as the product of Ti over i = [0, N), where N is the number of branchpoints, and Tiis the total number of hub orientations at branchpointi` summed over all possible hub choices at that branchpoint.
In the above scenario there are 12 sub problems for each # hub configuration (8xOne Hinge, 4xDouble Hinge). With 256 hub configurations, the GA solver needs solve 12x256=3072 sub problems. I think this is a big increase in complexity, and this is considering a relatively small case.
At the time of writing this comment there are actually no other hubs that could be used to implement any branchpoint with 3 or more branches, which makes the complexity increase seem smaller than it actually is. If and when a new hub similar to D49_aC2_ext in degree and termini compatibility gets introduced, we will get 4^(4+4) = 65536 hub configurations. If we can solve all 12 sub problems of one hub configuration under 1 second (this is extremely optimistic), this will take 18 hours.
The above is constrained by Assumption A, i.e. not even taking into account the ordering problem if the user intends for some or all hubs to be moveable on the condition that the movement optimizes another part of the network.
I have so far not been able to think of a clean solution to this hub assignment problem. Memoization can help save recomputation for identical 2H cases. For instance, the # shape case could be reduced to 32 + 64 = 96 segment runs with only D49_aC2_ext, and the number grows linearly with the number of hubs choices per branchpoint.
Related TODO: #12.
In the most general case, the input network may involve branch points.
Determine a way to optimally place hubs (which hub and at in orientation) at branch points. These placed hubs allow #12 to break a complex network into sub problems solvable by the GA.