Re: [boost] [BGL] Stoer–Wagner min-cut algorithm

Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-07-16 08:26:41

> Does any of the stuff at <URL:http://www.graphviz.org/doc/FAQ.html#Q22>
> help for that?  It would require coordinates, but you can get those by
> running dot on your graph on a system that you believe produces the
> desired layout.

The `pos` attribute seems like it will work. I will experiment with it to see...

>> Also, I experimented with using <boost/graph/dimacs.hpp> and
>> <boost/graph/read_dimacs.hpp> instead of `parse_noigen.hpp`, but I
>> think that the "NOIGEN format" is a modification of the DIMACS format.
>> As explained on http://www.avglab.com/andrew/CATS/maxflow_formats.htm
>> , DIMACS uses "n" lines, whereas NOIGEN does not. This is why the BGL
>> DIMACS parsing utilities kept throwing exceptions.
>
> How are the source and target of the flow specified in NOIGEN?  I.e., what
> is the equivalent to a DIMACS "n" line?

The NOIGEN format specifies a min-cut problem, which does not use
source and target vertices in the definition of the problem. So, there
is no equivalent to the DIMACS "n" line.