Anybody using maxflow algorithm here?

**jutirain** · 11-12-2008

I'm using an implementation of maxflow algorithm from here:
http://www.adastral.ucl.ac.uk/~vladkolm/software.html
(Please see section 3 Maxflow)

The version 2.2 works just fine.
However, when I porting to version 3.0, there are some problems.

First, g++ doesn't implement the template function linking,
so I move all the implementation to header file.
After that, when I call the function maxflow()
The program will crash since the DBlock doesn't work.

Is there anybody using the same code and works just fine?

**dwks** · 11-13-2008

What version of g++ are you using? The README says

Tested under windows, Visual C++ 6.0 compiler and unix (SunOS 5.8
and RedHat Linux 7.0, GNU c++ compiler).

So g++ ought to work, if you have a relatively recent version. That being said, it doesn't compile for me.

I didn't fiddle with it too much, but putting the main() from the README into main.cpp, and running the following worked.

Code:

$ cat *.cpp > all.cpp
$ vim instances.inc  # I added inclusion guards to this file
$ g++ all.cpp -o all
$ ./all
Flow = 3
Minimum cut:
node0 is in the SINK set
node1 is in the SINK set
$

This is with

Code:

g++ (GCC) 4.1.2 20071124 (Red Hat 4.1.2-42)

**jutirain** · 11-20-2008

I've tested the code using g++ 4.1.2 and 4.3.1, both on Ubuntu 8.10, neither of them support template function linking. I'm a little curious about why it's so hard for a compiler to implement this feature.

I've tried to move the function implementation into its header file (graph.h) or cat all the file into one (just as what you did), both of them can work for the simple main.cpp in the readme file.

But somehow they still crashed in my application.

It may due to the problem of size. There is more than 10 ^ 6 nodes in my application (a video segmentation program).

gdb says that the problem occur in DBlock's destructor, so I thought it's probably the problem of memory management, rather than the bug of mine.

**matsp** · 11-20-2008

I'm a little curious about why it's so hard for a compiler to implement this feature.

because essentially, the template code needs to be stored in the object file in such a form that the compiler can generate the relevant expansion of the template for the types being used. As far as I know, there is only one compiler that supports that: Comeau (sp?).

A million nodes doesn't seem that many (yes, of course, if you make a piece of paper for each node and spread them on the floor, it's a huge number, but in computer terms, a million of something isn't a really huge number).

Crashing in delete is usually a sign that your memory handling is broken - usually writing over the edge of an array.

--
Mats

**jutirain** · 11-20-2008

Now I'm just not sure which part of the program produce the memory problem.

I've used version 2.2 and 3.0 of the implementation of this algorithm. Both of them crash only if the size is big enough.

So I thought it may be my fault. However, however, since the API is simple and nothing to do with low level memory management, so I'm not sure whether it's actually a bug of this library.

Any suggestion? Or if there is some computer vision forum to post to?

Thread: Anybody using maxflow algorithm here?

Thread Tools

Search Thread

Display

Anybody using maxflow algorithm here?

Similar Threads

Implement of a Fast Time Series Evaluation Algorithm

Euclid Algorithm (extended)Part2 Doubt about pointers - INITIALIZATION

Binary Search Trees Part III

Request for comments

Tags for this Thread