Boost logo

Boost :

Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-15 11:28:00


On Thu, 15 Jul 2010, Daniel Trebbien wrote:

>> Could you please write this up into a shell script, listing the names of
>> your dot files and what rendering program you used for each?
>
> Hello Jeremiah,
>
> I apologize for the delay.
>
> Attached is a shell script that will generate GIF images using
> Graphviz. Unfortunately, it seems that when I tried this script using
> version 2.26.3 (20100126.1600) of Graphviz on Debian Squeeze, the
> generated images were different than the images that I generated with
> Graphviz version 2.24.0 (20090616.2323) on Windows. Currently I do not
> see a way to use the newer versions of Graphviz to generate the same,
> or similar, images because I do not think that the DOT format allows
> fine-tuned control over where nodes are drawn in the images.

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.

> 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?

-- Jeremiah Willcock


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk