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 -&gt; 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 -&gt; 'c'.
Add 'c' to the tree. a--674--&gt;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 -&gt; 'd'.
Add 'd' to the tree. a--674--&gt;c--684--&gt;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 -&gt; 'e'.
Add 'e' to the tree. a--674--&gt;c--684--&gt;d--1080--&gt;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 -&gt; 'h'.
Add 'h' to the tree. a--674--&gt;c--684--&gt;d--1080--&gt;e--930--&gt;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 -&gt; c, and add it
Same with updated S (a or c) c -&gt; d, and add it
Same with updated S: d -&gt; e
Same with updated S: e -&gt; h
Same with updated S: e -&gt; g
Same with updated S: this is where forward and forward &amp; backward algorithms diverge. Forward algorithm only looks at weights for edges starting from S (this is a -&gt; b), while forward and backward algorithm also screens backward links, so the selected link is b -&gt; d which has a higher weight (396) than a -&gt; b (335)
Last update of S with e -&gt; 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.