Anybody using maxflow algorithm here?

This is a discussion on Anybody using maxflow algorithm here? within the Game Programming forums, part of the General Programming Boards category; 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 ...

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    33

    Anybody using maxflow algorithm here?

    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?

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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)
    dwk

    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: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    33
    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
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    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
    Posts
    33
    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, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21