remove direct edge when an indirect one exists

Topics: algorithm
Mar 12, 2010 at 12:14 PM

Hi,

I'm looking at an application where I would need to remove the direct edge when an indirect one exists.

The example would be three vertexes, A, B and C and three edges, from A to B, from B to C and from A to C.

This graph would mean that vertex C can start when both A and B are ready. In this case I could remove the edge from A to C, as that one is implied by the path from A -> B -> C. A direct edge can always be removed if there is an indirect one.

I feel I somehow have to use a shortest path algorithm but I'm unsure how. Any help would be greatly appreciated.


Thanks!

Mar 29, 2010 at 1:46 PM

It seems I can use the HoffmanPavleyRankedShortestPathAlgorithm to find all the paths between vertexes and their length. If there are 2 paths or more and one path has length 1 I can delete that one.

It would mean tho I have to traverse the graph from the starting node completely and to do the HoffmanPavleyRankedShortestPathAlgorithm calculation for every vertex found. After that from the node after the starting node and do the whole calculation again. This is doable but doesn't sound like an elegant solution.

Is there a better solution to solve this?

Apr 1, 2010 at 8:53 AM
If I get you right, what you are looking for is a spanning tree. If the graph is directed, the term is "arborescence".
Apr 3, 2010 at 8:04 PM

Hi Hieronymus,

thanks for your reaction. I fail to see however how I can use a spanning tree.

What I'm doing at the moment is use a DFS and put all the paths found in a list. I'm then going through that list in a double loop and for every vertex in the outer loop I try all the vertices in the inner loop and do a HoffmanPavley on the two vertices. If in the resulting paths from HoffmanPavley I find one path with a length of 1 I delete that one.

Strangly enough that takes care of a few of instances but some other still popup.

I'll look into the spanning tree a bit more.