0
$\begingroup$

Let's say I have a set of non-repeating arcs, e.g. (0,1), (3,0), (0,3), (1,2), (2,3), ("set" because they don't repeat).
Here's an example of a graph for which this series of arcs would form a valid path: Graph

And a valid path would be (0,1), (1,2), (2,3), (3,0), (0,3).

Note that the path might not be unique (and that's fine). And I don't care where we start in the path, as long as all arcs in the set are traversed.

Given a directed adjacency matrix, how to put together a path describing this set of arcs? Seems to me like there should always be a way to do this. Having trouble putting together an algorithm to do so.

This question is related, but I'm trying to generalize from this: https://stackoverflow.com/questions/53761877/get-route-from-unordered-set-of-tuples

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't understand what problem you're trying to solve. What does "recover path" mean - what path? What do you mean by "a path describing this set of arcs"? The problem statement is not clear. What is the precise relationship between the path you're trying to find and the set of arcs? Are you trying to find a path that traverses each of the arcs exactly once? $\endgroup$
    – D.W. ♦
    Apr 3 at 6:43
  • $\begingroup$ Sorry about that. Definition of "path": "A path is a sequence of arcs with the property that each terminal vertex in the sequence is the source vertex of the next arc in the sequence". If the set of arcs is unordered, how do I order them to form a path? Yes, I'm trying to find a path that traverses each of the arcs in the given set exactly once, and only the arcs in the given set. Vertices may be repeated, as in my example above, but arcs may not be. $\endgroup$
    – IsalanOnkar
    Apr 3 at 14:54

1 Answer 1

Reset to default
2
$\begingroup$

Let $E$ be the set of your edges, and let $V$ be the set of all the edge's endpoints. Consider the graph $G=(V,E)$. You're asking for a Directed Eulerian trail of $G$.

One possible way to so so, is the following: assume that each vertex has the same in- and out-degree (more on how this assumption can be removed later) and look for an Eulerian cycle of $G$. Start from any vertex $u$, pick any outgoing edge $(u,v)$, walk to $v$, delete $(u,v)$, and repeat until encounter $v$ again. At the end of this process either you have followed an Eulerian cycle (i.e., you deleted all edges), or you followed a cycle $C$ and are left with a graph $G'$ containing some vertex $w$ that is in $C$ and has non-zero in/out-degree in $G'$. You can then repeat the above procedure from $w$ on $G'$ and merge the resulting cycle $C'$ with $C$ (on the shared vertex $w$). Continue repeating the above until you have a cycle that traverse all edges.

If not all vertices have the same in- and out-degree, then for an Eulerian trail to exist there must be exactly two distinct vertices $u,v$ that violate this property (these are exactly the endpoints of the trail). Find an Eulerian cycle $C$ of the graph $(V, E \cup \{ (u,v)\})$ or $(V, E \cup \{ (v,u)\})$ (whichever satisfies the property, if any) and then delete $(u,v)$ from $C$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ In my answer $G$ is the graph that contains exactly the arcs you have been given (I never mention any "original graph") . An Eulerian trail tells you exactly which arcs to traverse and in what order to obtain a path that uses each of the arcs you have been given exactly once. $\endgroup$
    – Steven
    Apr 5 at 13:10
  • $\begingroup$ Right, thanks. Getting closer but I don't totally understand. When you say "delete 𝑣, and repeat until encounter 𝑣 again", do you mean "delete arc $(u,v)$? ". I'm confused because later you say "..you deleted all edges". Furthermore if I delete $v$ from $V$, and don't delete the corresponding arcs, then that leaves me with arcs with endpoints that aren't in $V$. $\endgroup$
    – IsalanOnkar
    Apr 5 at 23:22
  • $\begingroup$ Sorry, "delete $v$" was meant to be "delete $(u,v)$" $\endgroup$
    – Steven
    Apr 6 at 12:22
  • $\begingroup$ Would this work on graphs with multiple directed arcs between two vertices? e.g. (u,v) appears 2 times in the set of arcs. IT seems like it works to me, but I'm just checking. THanks :) $\endgroup$
    – IsalanOnkar
    Apr 10 at 21:19
  • $\begingroup$ Yes, it would work on multigraphs. You can also split each parallel edge by adding a new vertex in the middle, run the algorithm the resulting simple graph and then remove the "split vertices" from the resulting trail (that is if the sequence of vertices is $u,x,v$, where $x$ is a split vertices, you can delete $x$ and its incident edges, and add the direct edge $(u,v)$). $\endgroup$
    – Steven
    Apr 11 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.