2

Well, I'm facing a problem with a small work I have in hands right now...

The main goal is, having a given graph (without weights, and directed), I have to discover the group of paths(if possible, only one path, but they can be more) with minimum total length, that cover all edges. Other "constraint" is that the graph, is a DFA, so the paths should start in an initial state, and end in an acceptance state (they're marked).

Initially I found that this was similar to the Chinese Postman Problem, and in fact, it is. But in my case, the graph is directed (I believe this changes thing a bit), and there isn't any problem in processing an edge more than once, since the resultant path remains the shortest.

I've read some things about Euler paths, and T-Joins, and this is probably the solution to my problem. If I understood it right, what I should do is to find an Euler path in my graph and, if there isn't one, make it exist, duplicating the T-Joins, or something like that... I had lots of trouble understanding this, I don't even know if this is the answer to my problem... (shortest and most understandable text I found here: http://en.wikipedia.org/wiki/Route_inspection_problem)

Just to leave a short example, given this graph (1 is initial and 5 is acceptance):

1 -> 2; 2 -> 3; 2 -> 4; 4 -> 5;

The answer to my problem should be: 1 -> 2 -> 4 -> 5 and 1 -> 2 -> 3. (In this case I would also have to handle the fact that 3 isn't an acceptance state, but that edge had to be covered. But I can easily get through that by flagging all the states with no edges to other nodes as acceptance states).

Hope I explained everything well enough.

Thanks in advance!

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
norim_13
  • 303
  • 2
  • 11
  • The Wikipedia article you linked mentions a CPP variant for digraphs, called **[New York Street Sweeper Problem](http://www.geocities.com/model_based_testing/model-based.htm)** (scroll down). Does that help? – jweyrich Apr 24 '14 at 01:51
  • I believe that the Sweeper Problem is indeed my problem. Thank you very much. But now I'm having trouble implementing that method... It consists in Eulerizing the graph, and getting the Euler path. To Eulerize the graph, I have to force every node to have its indegree equal to the number of edges from it to other nodes. Is there any known algorithm for this? I've already developed some code, but it's not working at all... – norim_13 Apr 25 '14 at 00:32
  • The ["Eulerizing" Graphs](http://webspace.ship.edu/jehamb/mls/MLS%201-3.pptx) presentations from the [Math for Liberal Studies](http://webspace.ship.edu/jehamb/mls/index.html) book teaches how to Eulerize a graph. After you have an Euler graph, you'll have to find Euler path(s)/cycle(s) - for that you may pick one of the algorithms cited on the [Eulerian Path](http://en.wikipedia.org/wiki/Eulerian_path) article. – jweyrich Apr 25 '14 at 18:56
  • Thanks for the suggestion, but I believe that it's not what I need, since it teaches how to Eulerize a non directed graph, and mine is directed... – norim_13 Apr 25 '14 at 22:41
  • I believe I know how to Eulerize. I think I only have to make all nodes have as many edges coming in as edges going out. The problem is knowing what edges should be duplicated in order to force this... I mean, if I have a node with two edges coming in, and one going out, of course I'll have to duplicate the only edge going out. But if there are three ins, and two outs? What should be the criteria? – norim_13 Apr 25 '14 at 22:44
  • While finding an Euler path on directed graphs seems relatively easy, I don't know a solution for Eulerizing a directed graph - or even if there's a formal (optimal) one besides brute-forcing. – jweyrich Oct 28 '14 at 18:31

0 Answers0