[BGL] How to fix read_graphviz? with spirit?
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
Hi Hiraki, On Mar 16, 2004, at 3:47 AM, HIRAKI Hideaki wrote:
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.
That sounds reasonable.
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.
I am also not an expert with the spirit parser, but that sounds like a promising direction. Another approach would be to just write the parser by hand in C++.
Q3) Why boost::subgraph isn't general subgraph but "induced" subgraph?
Hmm, I thought graphviz used induced subgraphs. I'll look into this.
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?
That's an interesting idea. I bet it would be straightforward to implement such an adaptor, so if you were to implement it, it would be a welcome addition to the BGL. Cheers, Jeremy
Jeremy Siek wrote:
Hi Hiraki,
On Mar 16, 2004, at 3:47 AM, HIRAKI Hideaki wrote:
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.
That sounds reasonable.
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.
I am also not an expert with the spirit parser, but that sounds like a promising direction. Another approach would be to just write the parser by hand in C++.
Sorry I missed this post. Yes, you can write reentrant parsers using Spirit. How long it will take depends, of course, on the complexity of your grammar. It might help if you could post your grammar to Spirit's mailing list, in the hope that, perhaps someone might have already implemented something similar. It's also good that you already have a grammar to begin with. For instance, Hartmut Kaiser transformed the C parser from YACC to Spirit in a fairly short time, IIRC. It involved some adjustment for transforming LR to LL (dealing with left recursion, etc.). For further discussion, please post to: Spirit-general mailing list Spirit-general@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/spirit-general Cheers, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
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.
Hello Jeremy, I think the parallel edges are dealt just fine. I have thought it's impossible to be "two edges, one in the subgraph and one not in the subgraph" under the induced subgraph approach. Do you mean the second edge can be interpreted as not in the subgraph? Thanks, Hideaki Hiraki At Thu, 25 Mar 2004 11:29:52 +1100, Jeremy Siek wrote:
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.
participants (6)
-
HIRAKI Hideaki -
Jeremy Siek -
Joel de Guzman