Port the preflow push alg. (max. flow)

[Alpar Juttner]

This ticket is a follow-up of #47.

The affected files are

• lemon/preflow.h
• test/preflow_test.cc
• test/preflow_graph.dim

It depends on #174

[Peter Kovacs]

Andrew V. Goldberg said in his lecture at the ​ESA 2008 conference and also mentioned in his paper, that he rather like the Push-Relabel name instead of Preflow-Push.

From his paper The Partial Augment–Relabel Algorithm for the Maximum Flow Problem, ESA 2008:

The push-relabel method... Sometimes it is referred to as preflow-push, which is misleading: e.g. Karzanov’s implementation of the blocking flow method uses preflows and the push operation.

So it seems to be very important for him to call his algorithm as Push-Relabel. And there is another important reason for that. In this paper Goldberg presents a variant of the known Push-Relabel method, in which push operations are substituted with partial shortest path augmentations. An implementation of this method (called PAR) proved to be more efficient and more robust than his former best code HI-PR, which is an efficient implementation of the highest-label push-relabel algorithm. That's why it would be important for us to implement such an algorithm in LEMON, too. However it is also based on preflows, so using this name for one of the algorithms would be a bit misleading.

I rather suggest to rename Preflow to PushRelabel, and an implementation of the new method could be called AugmentRelabel or something similar.

[Alpar Juttner]

Replying to kpeter:

Andrew V. Goldberg said in his lecture at the ​ESA 2008 conference and also mentioned in his paper, that he rather like the Push-Relabel name instead of Preflow-Push.

It would be nice to follow Goldberg's advice, indeed. My problem with the name PushRelabel is that there are other important push-relabel type algorithms (e.g. bipartite matching, matroid related algorithms (disjoint spanning trees etc.)), and this name doesn't indicate that we are working with flows. On the other hand, the name Preflow seems widely accepted for this algorithm. (It may be, that Golberg has started to advertise this new name only recently, when the augment-relabel type algorithm was invented...)

Also Preflow do not really cause name conflict, the Karzanov's implementation can be called either after his name or something like BlockingFlow. The augment-relabel algorithm can also be called like that.

Anyhow, the right name were GoldbergsPreflowPushRelabelMaxFlowAlgorithm. Each part is important here (except the last one), but we certainly must reduce it to something short, but still meaningful.

[Alpar Juttner]

The attached bundle file​ ports the Preflow implementation. The changesets [660db48f324f], [53c5277ba294] and [624e673efa76] contains the port and some basic trimming, while [f583aecbba6e] changes the LinkElevator to Elevator. This latter changeset should only be put into the main branch after performing some running time tests.

[Peter Kovacs]

I attached two changesets with improvements. Please check it.

Some questions came up for me during making these improvements.

1. I think we should note references (book, article etc.) for most of the algorithms (except for e.g. Bfs, Dfs, Dijkstra, BellmanFord, so the really well-known ones). E.g. it would be nice to have a note in the doc of Preflow about the heuristics that are used in it (and of course a reference for a book/article about the basic/general version of the algorithm).
2. The original article proposing this algorithm was due to Goldberg and Tarjan. Am I right? So maybe Tarjan should also be mentioned in the doc.
3. In Bfs/Dfs/Dijkstra the default graph type is ListDigraph, however in Preflow there is not any default value for this parameter. Should it be set to ListDigraph?
4. I suggest renaming flowInit() to init(), so the class would have an init() and an init(FlowMap) function.
5. For the functions that give e.g. a map for an algorithm there is a note in the doc saying: The destructor deallocates this automatically allocated map, of course. I think these comments are unnecessary, since they are just saying that there isn't memory leak in the code, which is indeed a very fundamental request, that do not have to be "advertised". So I suggest to remove these comments.
6. Do we really need SetElevator named parameter or SetStandardElevator is enough? In Dijkstra SetHeap and SetStandradHeap cause a similar question. In the latter case it can maybe be imagined that a user implements a special heap structure with different constructor interface, but in case of elevators it seems unreal.
7. In Preflow the template parameter names start with underscore (_Digraph, _CapacityMap, _Traits), since the names without underscore are used for public typedefs. Is it better or worse than the naming used in Bfs/Dfs/Dijkstra, e.g. GR, CM, TR?
8. I can't imagine what does "the three min cut values" mean in the test file. Could someone explain it?

[Alpar Juttner]

Replying to kpeter:

I attached two changesets with improvements. Please check it.

Some questions came up for me during making these improvements.

1. I think we should note references (book, article etc.) for most of the algorithms (except for e.g. Bfs, Dfs, Dijkstra, BellmanFord, so the really well-known ones). E.g. it would be nice to have a note in the doc of Preflow about the heuristics that are used in it (and of course a reference for a book/article about the basic/general version of the algorithm).

Yes, if we also target scientists, it would be very useful, even for the "really well-known ones". I just haven't yet been able to find out how to add bibliography to the doxygen doc.

2. The original article proposing this algorithm was due to Goldberg and Tarjan. Am I right? So maybe Tarjan should also be mentioned in the doc.

Yes, he should be.

3. In Bfs/Dfs/Dijkstra the default graph type is ListDigraph, however in Preflow there is not any default value for this parameter. Should it be set to ListDigraph?

In theory, why not. In practice I'm a bit concerned about the increased compilation time in all cases like that.

4. I suggest renaming flowInit() to init(), so the class would have an init() and an init(FlowMap) function.

Agreed.

5. For the functions that give e.g. a map for an algorithm there is a note in the doc saying: The destructor deallocates this automatically allocated map, of course. I think these comments are unnecessary, since they are just saying that there isn't memory leak in the code,

For we it tells a bit more: If you deallocate it off your own bat, you'll be in trouble.

6. Do we really need SetElevator named parameter or SetStandardElevator is enough? In Dijkstra SetHeap and SetStandradHeap cause a similar question. In the latter case it can maybe be imagined that a user implements a special heap structure with different constructor interface, but in case of elevators it seems unreal.

Yes, it is unrealistic. I still believe that the bast solution would be to get rid of the traits class completely. Assuming that we don't do it, it might be good to have an interface similar to the heaps in Dijkstra.

4. In Preflow the template parameter names start with underscore (_Digraph, _CapacityMap, _Traits), since the names without underscore are used for public typedefs. Is it better or worse than the naming used in Bfs/Dfs/Dijkstra, e.g. GR, CM, TR?

Neither of them.

8. I can't imagine what does "the three min cut values" mean in the test file. Could someone explain it?

svn blame will tell you whose door you should knock on.

[Peter Kovacs]

Replying to alpar:

Yes, if we also target scientists, it would be very useful, even for the "really well-known ones". I just haven't yet been able to find out how to add bibliography to the doxygen doc.

Try e.g. the attached bib2dox script on a bibtex file. Not a perfect solution, but it works properly. (I just modified a script that I found with google.)

5. For the functions that give e.g. a map for an algorithm there is a note in the doc saying: The destructor deallocates this automatically allocated map, of course. I think these comments are unnecessary, since they are just saying that there isn't memory leak in the code,

For we it tells a bit more: If you deallocate it off your own bat, you'll be in trouble.

I do not understand it exactly. Why would you deallocate it? When would you do it? The class only gives back const reference, so nobody would think about deallocate it outside the class. And if you modify the class implementation itself, you see the source code, so you won't make such a fault.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Yes, if we also target scientists, it would be very useful, even for the "really well-known ones". I just haven't yet been able to find out how to add bibliography to the doxygen doc.

Try e.g. the attached bib2dox script on a bibtex file. Not a perfect solution, but it works properly. (I just modified a script that I found with google.)

It is basically a good idea (I generate my publication list in a similar way, actually). My concern is that bibtex2html is not really a ubiquitous tools, maybe because it is written in the somewhat exotic !OCaml language. We may also want to have a look at these (in the future):

• ​http://people.csail.mit.edu/rahimi/bibtex/
• ​http://www.irisa.fr/lagadic/soft/bib2html/bib2html.html
• ​http://www.authopilot.com/xml/home.htm

Btw. could you tell me how to refer properly the items of bibliography generated by your script from the other parts of the documentation?

PS: This discussion seems pretty much off-topic at this ticket.

[Peter Kovacs]

Replying to alpar:

I attched a bundle file containing three changesets. The first two are sligthly modified variants of my previous changesets [9b8778f1d992] and [65649fefece8] according to your answers. The third one renames flowInit() to init(). They are based on [624e673efa76].

svn blame will tell you whose door you should knock on.

It seems that I should ask Jacint, but I don't know him.

I do not understand it exactly. Why would you deallocate it? When would you do it? The class only gives back const reference, so nobody would think about deallocate it outside the class. And if you modify the class implementation itself, you see the source code, so you won't make such a fault.

Could you please answer this?

[Peter Kovacs]

Replying to alpar:

PS: This discussion seems pretty much off-topic at this ticket.

I created a separate ticket for that. See #184.

I think the 6 changesets from [660db48f324f] to [873168ab5620] could be pushed to the main branch. The only question is [f583aecbba6e] (LinkedElevator --> Elevator), that I cannot answer yet.

[Peter Kovacs]

Maybe it isn't the best idea to hide the traits class totally (as I thought before). E.g. the public typedefs refers to it. So now I think it would be better if only the template parameter doc would be hidden. Then the traits class isn't as dominant in the doc as before, but if you wants to find, you can.

See [551369181b50].

[Peter Kovacs]

New reorganized bundle containing all my previous modifications

[Peter Kovacs]

Replying to kpeter:

See [551369181b50].

Consider to use the new attached bundle file instead of all my previous changesets. It is only slightly modified, but it is more clear and it is organized in a better way with better commit logs.

[Alpar Juttner]

The port went to the main. I kept the original name (Preflow) for this stuff, but if someone comes up with a better name, I'm open to the change (until the next release, of course).

[Peter Kovacs]

Note that [f583aecbba6e] (LinkedElevator -> Elevator) has not been pushed to the main branch yet.