I want to find all possible train routes from the user's chosen city A to city Z, given that for any combination of cities there is defined one or more combinations of one or more graphs that can be traversed.
The graphs are defined in KML files, and the valid combinations are also pre-defined.
The number of valid combinations varies between one and around seventy. The number of graphs used varies between typically one or two, up to, in complex cases, as many as six.
A typical (albeit more complex than average) combination of graphs for a given pair of inputs looks like this WX+SU+GC+CM. This means you must traverse graph WX, starting at node 'A' (the user's specified origin) to any node that is also found on graph SU, and then traverse graph SU from that node to any node that is also found on graph GC, then traverse node GC from that node to any node found on CM, and finally traverse graph CM from that node to the destination 'B'.
Graphs WX and graphs CS intersect at two points 'C' and 'D' each with one path possible on graph WX.
Graph CS and MA intersect at around fifteen different points
MA and GM intersect at several points.
What is the best way to find all valid routes between the two cities?
Note the rules:
- Graphs must be used in order (first WX, then CS, then MA, then GM)
- Once you have left a graph you must not use it again (so if you use an edge found on CS, you cannot subsequently use a edge from WX, although if that edge is ALSO found on WX, there is no problem)
- At least one edge must be used from each set - you cannot skip any set.
Is it best to just put all of the edges from all the graphs into one graph, find all the routes (depth-first search?), and then after doing this check if the edges can be visited in order?
The route: A-B-C-D-E-F-G
- A-B is found on graphs 1, 2, 3, 4
- B-C found in graphs 1, 2, 3, 4
- C-D found in graphs 3, 4
- D-E found in graphs 2, 4
- E-F found in graphs 2, 3
- F-G found in graphs 3, 4
is NOT valid, because you cannot traverse it without going back a graph, either at node 4, or node 5.