# Paths in Directed Graphs **URL:** \ **Category:** Factual Questions\ **Created:** [March 23, 2004, 9:18pm UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988 "2004-03-23T21:18:35Z")\ **Posts on this page:** 12\ **Page:** 1
**Author:** ![MaxTheVool](https://avatars.discourse-cdn.com/v4/letter/m/9fc29f/32.png) [@MaxTheVool](https://boards.straightdope.com/u/MaxTheVool)\ **Post date:** [March 23, 2004, 9:18pm UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/1 "2004-03-23T21:18:35Z")
I have a directed graph with some number of nodes and some number of directed edges connecting them. I want to solve the following two problems: (a) what is the longest connected path which doesn’t traverse any edge more than once? (b) what is the longest closed loop (if any) which doesn’t traverse any edge more than once? (note: this is not a homework question, or anything of that sort). This question is similar to finding an Euler Circuit, which is an “easy” problem, but the fact that the edges are directed seems to make it much trickier. Thoughts? thanks. ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [March 24, 2004, 2:47am UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/2 "2004-03-24T02:47:02Z")
I’m not quite sure what you mean by > [@](#): > > This question is similar to finding an Euler Circuit, which is an “easy” problem, but the fact that the edges are directed seems to make it much trickier. If you’re saying that the directed Eulerian-circuit problem is harder than the nondirected version, I don’t think that’s right (see below); but if you’re saying that the directed version of this maximum-length-path probem is harder than the nondirected version I might agree. First, the problem of finding an Eulerian circuit (if one exists) in a directed graph is essentially the same as in the nondirected case. Clearly an Eulerian circuit will only exist if all nodes have equal indegree and outdegree, so assume this is true. Such a graph (having no sources or sinks) decomposes into a set of directed cycles. Now you can form an Eulerian circuit by starting with any one of these circuits and adding other circuits connected to this one, one at a time, until all have been added. (If you can’t do this then the original graph must not have been connected.) The conditions for an Eulerian path are similar. But the questions you ask are different from those of finding an Eulerian path; they are of the form “find the longest path…” rather than “does a maximum-length path exist…”. The former type of question is often harder to answer than the latter. The constraints above can place bounds on the path length: for a graph with v vertices and e edges, if the indegree=outdegree constraint is violated at n vertices, then at least k=sum(|outdegree-indegree|)/2 of the edges must be removed for the constraints to be fully satisfied, so the longest path must have at most e-k edges. But this bound cannot always be met. The problem is equivalent to finding the smallest subgraph (of the given graph) with the same values of outdegree-indegree for each vertex, since these are the edges that must be removed for the remaining graph to have an Eulerian circuit. This problem seems somewhat similar to the problem of finding the **minimum spanning tree** (which has efficient solution, e.g. Kruskal’s algorithm) but I haven’t found a solution to it yet. That’s all I’ve got so far. ---
**Author:** ![dre2xl](https://avatars.discourse-cdn.com/v4/letter/d/34f0e0/32.png) [@dre2xl](https://boards.straightdope.com/u/dre2xl)\ **Post date:** [March 24, 2004, 3:00am UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/3 "2004-03-24T03:00:27Z")
Modify Dijkstra’s algorithm. I’m sure you can do it easily… personally, if I knew the length between vertices beforehand, I’d apply v\_Max - v +1 to each length (there’s probably something wrong with that reasoning, but I’m too tired to figure it out). Alternatively you could always do a depth-first search. > **[Electrical, Electronic and Computer Engineering | UWA](https://www.uwa.edu.au/schools/engineering/electrical-electronic-and-computer-engineering)** > > Electrical, Electronic and Computer Engineering delves deep into the world of technology, giving students a thorough understanding of how electronics work. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [March 24, 2004, 3:51am UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/4 "2004-03-24T03:51:19Z")
These are trivial variations of Hamiltonian Path and Circuit. I used to give this out as a homework question when I taught Theory. (Ahem.) That makes them NP-Hard. All the terms used here are in your textbook. ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [March 24, 2004, 5:45am UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/5 "2004-03-24T05:45:59Z")
> [@ftg](#): > > These are trivial variations of Hamiltonian Path and Circuit. I used to give this out as a homework question when I taught Theory. (Ahem.) > > That makes them NP-Hard. > > All the terms used here are in your textbook. Really? Hamiltonian paths are those in which each _vertex_ is visited once; in these problems each _edge_ is visited (at most) once. I know that the problem of finding the longest simple path (i.e., the longest path visiting no vertex more than once) is NP-hard, but that’s not what he’s asking here. I’m not saying that **MaxTheVool’s** problems aren’t NP-hard, just that I don’t see a trivial reduction from Hamiltonian-circuit. ---
**Author:** ![ccwaterback](https://avatars.discourse-cdn.com/v4/letter/c/df705f/32.png) [@ccwaterback](https://boards.straightdope.com/u/ccwaterback)\ **Post date:** [March 24, 2004, 6:25am UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/6 "2004-03-24T06:25:25Z")
Here’s some info: [http://www.ics.uci.edu/~eppstein/161/960215.html](http://www.ics.uci.edu/~eppstein/161/960215.html) [http://www.cs.utoronto.ca/~mitchell/ai-course/s1.html](http://www.cs.utoronto.ca/~mitchell/ai-course/s1.html) ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [March 24, 2004, 2:22pm UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/7 "2004-03-24T14:22:43Z")
No I did _not_ read the OP wrong. I clearly saw that edges were being asked about. The reduction from HP/HC is in indeed trivial. It requires merely doubling the number of vertices and adding one extra edge per vertex. It is _extremely_ simple, which is what makes it a good _homework question_. Given that it is NP-Hard, Prim-Dijkstra, DFS and BFS are all _completely irrelevant_. **ccwaterback** ’s links are of absolutely no use in solving this problem. I will _not_ provide the reduction given that I have no way to determine if the OP is asking a homework question or not. I will not post solutions to possible homework questions here. I taught university level Theoretical Computer Science for 21 years. Hence I have a certain attitude about students going online and trying to have others do their work for them. ---
**Author:** ![MaxTheVool](https://avatars.discourse-cdn.com/v4/letter/m/9fc29f/32.png) [@MaxTheVool](https://boards.straightdope.com/u/MaxTheVool)\ **Post date:** [March 24, 2004, 6:28pm UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/8 "2004-03-24T18:28:26Z")
> [@ftg](#): > > No I did _not_ read the OP wrong. I clearly saw that edges were being asked about. The reduction from HP/HC is in indeed trivial. It requires merely doubling the number of vertices and adding one extra edge per vertex. It is _extremely_ simple, which is what makes it a good _homework question_. > > Given that it is NP-Hard, Prim-Dijkstra, DFS and BFS are all _completely irrelevant_. **ccwaterback** ’s links are of absolutely no use in solving this problem. > > I will _not_ provide the reduction given that I have no way to determine if the OP is asking a homework question or not. I will not post solutions to possible homework questions here. > > I taught university level Theoretical Computer Science for 21 years. Hence I have a certain attitude about students going online and trying to have others do their work for them. Well, I suppose you have no reason to believe me here, but… I’m 30, I’ve been a professional video game programmer for 8+ years, and I haven’t done any homework since I graduated in 1995. The question arose from the following puzzle: take the names of every Magic: The Gathering card ever printed (there are 6500+ of them) and find a sequence of them such that the last word in one card’s name is the same as the first word in the next card’s name. For instance: Oblivion Stone | Stone Spirit | Spirit Shield | Shield Sphere | Sphere of Resistance | Resistance Fighter. I was considering writing a program to attempt to find an optimal solution. My first plan was to construct a graph with each node being a card, and each edge being a connection between cards. So the “Shield Sphere” node would have an edge to the “Sphere of Resistance” node, and so forth. In a graph of that sort, the longest-sequence (or longest-loop) question is more or less trying to find the longest Hamilton Circuit (or whatever it is that you call an incomplete Hamilton Circuit). After some consideration, I realized that a better plan would be to have each node of the graph represent a word, with the edges being individual cards. So “Stone” would connect to “Spirit” which would connect to “Shield” and so forth. In a graph of that sort, the challenge of finding the longest sequence becomes the question I originally posed. Sadly, as it appears to be NP-complete, I may be out of luck (although I can always just write some simple search algorithm and get a reasonably long sequence, I just won’t be assured that it’s maximal). (I believe the conversion between the two different types of graphs I was discussing is similar to what you you were discussing at the top of this thread…) ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [March 24, 2004, 7:12pm UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/9 "2004-03-24T19:12:21Z")
> [@ftg](#): > > No I did _not_ read the OP wrong. I clearly saw that edges were being asked about. The reduction from HP/HC is in indeed trivial. It requires merely doubling the number of vertices and adding one extra edge per vertex. It is _extremely_ simple, which is what makes it a good _homework question_. Ah, you’re right, I see now; yes, it is trivial. I wasn’t thinking correctly about the reduction last night. ---
**Author:** ![ccwaterback](https://avatars.discourse-cdn.com/v4/letter/c/df705f/32.png) [@ccwaterback](https://boards.straightdope.com/u/ccwaterback)\ **Post date:** [March 24, 2004, 8:07pm UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/10 "2004-03-24T20:07:51Z")
I’ve noticed through the years, people with too much experience tend to over-complicate solutions. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [March 24, 2004, 10:01pm UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/11 "2004-03-24T22:01:45Z")
Despite the general problem being NP complete, I suspect that this particular case is feasibly solveable, by virtue of being sparse. The graph isn’t even connected, so disconnected pieces can be thrown away right off the bat, and most words are used in very few cards. In fact, most cards contain a very uncommon word, like “Æther” or “Hasban”, and many words show up predominantly as the first word or last word (generally an adjective followed by a noun), which would mean they wouldn’t form many connections. So if you run your breadth-first search, it shouldn’t actually run into too many long dead ends. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [March 25, 2004, 3:35am UTC](https://boards.straightdope.com/t/paths-in-directed-graphs/235988/12 "2004-03-25T03:35:54Z")
Now, if it’s heuristics for HP you’re looking for, then you want to start going thru Scientific Citations looking for the name “Dana Angluin.” She’s at the “top” of the citation tree for this. Then you start looking for newer stuff citing her earlier papers. BFS is going to provide a much worse approximation than DFS. BFS finds _short_ paths, not long ones. If you go with one node/word, you’re going to have _some_ nodes of very high degree. The best simple heuristics don’t like that. Note: One of my kids won the MtG contest at the local Con a couple years ago. I understand the context a bit thru years of osmosis.