0
$\begingroup$

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

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Eduardo Ribeiro Nov 17 '19 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.