1
$\begingroup$

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:

  1. Graphs must be used in order (first WX, then CS, then MA, then GM)
  2. 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)
  3. 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?

E.g.,

The route: A-B-C-D-E-F-G

Where

  1. A-B is found on graphs 1, 2, 3, 4
  2. B-C found in graphs 1, 2, 3, 4
  3. C-D found in graphs 3, 4
  4. D-E found in graphs 2, 4
  5. E-F found in graphs 2, 3
  6. 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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! I don't understand the problem statement or what the inputs are. What constitutes a route, and what are the conditions a route has to satisfy to be valid? What do you mean by "given sets of vertices, which must be combined in order"? Can you specify your problem more precisely? Can you describe the problem in an abstract way, maybe in the language of graphs and sets, giving a formal definition of what routes are valid? I couldn't follow your example. Is there some relationship between city names like Woking and two-letter digraphs like WX? What do you mean by "set WX"? $\endgroup$ – D.W. Feb 22 '17 at 21:57
  • $\begingroup$ hi, thanks, I changed a lot of the language that was imprecise. let me know if it's still confusing. $\endgroup$ – thelawnet Feb 22 '17 at 22:23
  • $\begingroup$ It would probably be a good idea if you abstracted the problem a little more (do we really need to know what the possible routes are, see maps etc.). If you formulate a concise computational problem, you are much more likely to get a good answer, I believe. $\endgroup$ – Juho Feb 23 '17 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.