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

From: HIRAKI Hideaki (hhiraki_at_[hidden])
Date: 2004-03-15 11:47:40

Hello there,
I submitted a bug fix on read_graphviz() to the bug tracker (Bug 
ID 865882, see P.P.S. below for the summary). When thinking about 
possible fixes, I got some questions.

Q1) May boost depend on build tools other than C++ compiler?
There seemed to be a building problem due to the dependency of the 
parser code on some specific versions of bison. This is not a real 
problem because the generated C++ codes are bundled. I think the 
dependency should be removed, if possible.

Q2) How easy is it to migrate a flex/bison code to spirit?
Boost seems to have its own parser generator, spirit. Its features 
are uncertain for me. I just expect that it is straightforward for 
an expert of spirit to write a reentrant parser to be replaced with 
the current flex/bison parser.

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.

Q4) How are the graph adapters for graphs of graphviz library?
Another option imagined is wrapping the graphviz library. This will 
introduce library dependency instead of build tool dependency. But no 
parser need to be developed. A data structure for general subgraph 
will be provided as a wrapped object. BGL seems to include wrappers for 
Stanford GraphBase and LEDA, C++ libraries. How are they adapted to 
graphviz, a C library?

Regards,

Hideaki Hiraki

P. S.  To Vladimir Prus:
I'm sorry to lay this subject aside so long. I appreciate your every effort.

P. P. S.  Summary of the bug:
The problem was that calling read_graphviz() for the second time was 
failed. The fix was to clear the garbage left in static variables:

--- boost_1_31_0/libs/graph/src/graphviz_parser.yy	Fri Aug 29 16:02:59 2003
+++ boost/libs/graph/src/graphviz_parser.yy	Mon Jan 26 18:16:16 2004
@@ -259,6 +259,10 @@
 
 graph_header: graph_type graph_name
   {
+    graphviz::vlist.clear();
+    graphviz::attributes.clear();
+    graphviz::subgraphs.clear();
+    graphviz::nodes.clear();
     std::string* name = static_cast<std::string*>($2);
     graphviz::previous_graph = static_cast<graphviz::Subgraph*>(g);
     graphviz::current_graph = static_cast<graphviz::Subgraph*>(g);

This workaround was found without understanding the code. As this 
worked for me, I gave up digging more. A better fix may remove the 
uses of static variables. The item in the bug tracker has been 
closed but is accessible:
http://sf.net/tracker/index.php?func=detail&aid=865882&group_id=7586&atid=107586