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.
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.
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.
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.
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…)
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.
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.