# What is the output polytree after aplying the Ramex algorithm to this graph?

I've been trying to understand the way this algorithm works, but I can't get a consistent result.

It has two phases: the first one coverts a table of events into a graph, and the second where the graph is tranformed into a polytree.

The question is about the second phase, using a back-and-forward heuristic:

This is the heuristic algorithm:

Algorithm 3. Back-and-Forward Heuristic
Input: Network G;
Output: Poly-tree S;
Initialize S;
For each vertex in G
For each edge in G
x = arg_max(weighted forward-vertex not visited in G and connected with S; weighted back-vertex not visited in G and connected with S)
End-for;
Update solution S with x;
End-for;


The example shown in the paper is this:

Fig. 2. (a) Original cyclic network, (b) Forward Heuristic provides a tree solution, (c) Back-and-forward Heuristic provides a poly-tree solution

Right now I'm having trouble applying the back-and-forward algorithm to the vertex b. I'll describe my thought process:

Initialize S -> Take 'a' and put it in the tree (S).
Look for the edges that connect 'a' (the tree S) to any unexplored node and select the one with higher weight -> 'c'.
Add 'c' to the tree. a--674-->c
'a' is now explored/visited.

Move to next vertex - 'b'.
Look for the edges that connect the tree ('a' or 'c') to any unexplored node and select the one with higher weight -> 'd'.
Add 'd' to the tree. a--674-->c--684-->d
'b' is now explored/visited.

Move to next vertex - 'c'.
Look for the edges that connect the tree ('a', 'c' or 'd') to any unexplored node and select the one with higher weight -> 'e'.
Add 'e' to the tree. a--674-->c--684-->d--1080-->e
'c' is now explored/visited.

Move to next vertex - 'd'.
Look for the edges that connect the tree ('a', 'c', 'd' or 'e') to any unexplored node and select the one with higher weight -> 'h'.
Add 'h' to the tree. a--674-->c--684-->d--1080-->e--930-->h
'd' is now explored/visited.


And now 'b' is left hanging because 'b' and 'd' are visited and the algorithm says the connection must be to a node not visited in G and the polytree shows b-->d.

Is my interpretation wrong?

Here's my interpretation of the algorithm, not sure it is completely right but that could help you:

• Initialize S: null (a is added after that)
• Enter in first loop on vertices (assume we start with a)
• Select the edge with highest weight connected to a: a -> c, and add it
• Same with updated S (a or c) c -> d, and add it
• Same with updated S: d -> e
• Same with updated S: e -> h
• Same with updated S: e -> g
• Same with updated S: this is where forward and forward & backward algorithms diverge. Forward algorithm only looks at weights for edges starting from S (this is a -> b), while forward and backward algorithm also screens backward links, so the selected link is b -> d which has a higher weight (396) than a -> b (335)
• Last update of S with e -> f

This is what seems right to explain the figure, and works to build a polytree. I am a bit confused because it does not exactly correspond to what is written in Algorithm 3, but it is not so rare that pseudo-code algorithm make no actual sense, and would yield wrong results if written directly in any programming language.

• It makes sense, so in this case the algorithm is more akin to: while there are nodes in G not in S, search for the heaviest connection to or from the tree to a node not in the tree and add that node. – Eduardo Ribeiro Nov 17 '19 at 13:26