0
$\begingroup$

I have a graph and I'm trying to enumerate all paths that start at node $S$, end at node $E$, uses each edge, and minimizes the number of edges used (i.e. it can only re-use an edge if strictly necessary).

What I am wondering is that if I have a solution path, e.g. $SADBCABE$, can I find all other valid paths that use the same set of edges by iterating over the ways in which I can reverse loops?

In other words, the example path has two loops: one that over $A$ ($ADBCA$), and one over $B$ ($BCAB$). This leads to five possible paths that can be made by reversing these paths that can be named: $A_0B_0$, $A_0B_1$, $A_1B_0$, $A_1B_1$, and $B_1A_1$. Here, $B_1A_1$ refers to reversing path $B$ and then reversing path $A$. This example makes it clear that order matters.

Will this method of enumeration miss any paths containing the same edge set?


EDIT: After some discussion in the comments, it is clear that further reversals on the five paths listed above could produce previously unfound paths. It seems like to use this methodology, I would also have to keep a fringe set and ensure that all reversals on the fringe produce paths that I've already found before removing it. This would no longer be a simple enumeration of permutations, but rather a BFS, which is unfortunately less deterministic. Is this already a known problem that I could read more about? I've tried Googling various things about domino trains (since each edge could be thought of as a domino), but I didn't find anything.

$\endgroup$
  • $\begingroup$ In $SABCDAFCGAE$, there are just two "ordered simple cycles", $ABCDA$ and $AFCGA$, and I don't think they can be interleaved into, e.g., $SABCGAFCDAE$. Whether this is a counterexample depends on what you mean by "cycle" -- while the two I gave above are the only simple cycles produced as you walk along the given path, they are not the only cycles if you consider the set (without order) of edges contained in the path. $\endgroup$ – j_random_hacker Dec 5 '17 at 10:52
  • 1
    $\begingroup$ @j_random_hacker The path you listed can be found eventually. Note that $CDAFC$ is also a cycle, and by repeatedly reversing the three $A$ cycles and the one $C$ cycle, that path can be constructed. I wrote a Python script to randomly reverse cycles until your's was found, the shortest sequence I found was: $SABCFADCGAE$, $SABCFAGCDAE$, $SAFCBAGCDAE$, $SABCFAGCDAE$, $SABCGAFCDAE$. $\endgroup$ – Jared Goguen Dec 9 '17 at 21:44
  • $\begingroup$ @j_random_hacker However, this does bring to light one important thing: further reversals on the five paths originally listed can produce new paths, so thank you for that. It seems like to use this methodology, I would also have to keep a fringe set and ensure that all reversals on the fringe produce paths that I've already found before removing it. This would no longer be a simple enumeration of permutations, but rather a BFS, which is unfortunately less deterministic. $\endgroup$ – Jared Goguen Dec 9 '17 at 21:48
  • 1
    $\begingroup$ The problem of finding such a path is called the Chinese Postman Problem. $\endgroup$ – Marcelo Fornet Dec 14 '17 at 15:33

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.