Thread: Anybody using maxflow algorithm here?

  1. #1
    Registered User
    Join Date
    Nov 2007

    Anybody using maxflow algorithm here?

    I'm using an implementation of maxflow algorithm from here:
    (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?

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    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.
    $ cat *.cpp > all.cpp
    $ vim  # 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
    g++ (GCC) 4.1.2 20071124 (Red Hat 4.1.2-42)

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell

    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ:

    My website:
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Nov 2007
    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.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Farncombe, Surrey, England
    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.

    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Nov 2007
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

Tags for this Thread