Re: [boost] [BGL] How to fix read_graphviz? with spirit?

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-03-24 19:29:52

Hello Hiraki,

I don't think that the "induced" subgraph approach taken by 
boost::subgraph
is the problem. There is no problem with interpreting the below graph 
and
subgraph as an induced subgraph. There just happen to be two edges, one
in the subgraph and one not in the subgraph.

I think instead the problem is a bug in the read_graphviz function with
respect to dealing with parallel edges (two edges with the same source
and target). I'll look into fixing the problem.

Cheers,
Jeremy

On Mar 16, 2004, at 3:47 AM, HIRAKI Hideaki wrote:
> Q3) Why boost::subgraph isn't general subgraph but "induced" subgraph?
> BGL seems to have a fundamental restriction on reading graphviz files.
> The graph data read in read_graphviz() is stored in the 
> boost::subgraph<>
> where any edge connecting vertices of a subgraph is assumed to be
> part of the subgraph. This is against the semantics of the graphviz
> format. For example,
>     digraph g0 {
>       edge [color=blue]
>       subgraph g1 {
>         edge [color=red]
>         n1 -> n2
>       }
>       n1 -> n2
>     }
> this graph has one edge in the subgraph g1 (red) and the other not in
> g1 (blue). But the graph read by BGL must have both edges belonging to
> g1. I guess that the complexity to realize this restriction may be the
> cause for the wrong codes in boost/graph/subgraph.hpp (see the comments
> at the lines 603 and 612).
> Anyway, a handy data structure to treat general subgraph is useful. I
> hope boost::subgraph will be the one.