[BGL] forced client complexity
If one accepts the axiom that "a picture is worth a thousand words," then it naturally follows that discussion of graphs is always overly prolix. Sadly, the same reasoning is also applicable to the code of graph libraries. Boost.Graph seems to expose and require an unnecessarily large amount of complexity, though. Whereas libraries like Spirit go to great lengths to make hard things easy, BGL seems to try only to make hard things possible. The amount of scaffolding required to use BGL for even the simplest of projects often dwarfs the code size of a naive, yet functional, special-purpose implementation. While I understand that the BGL is deeply entrenched in boost culture, certain academic circles, and even publications, I nonetheless suggest that BGL lacks the ease of use necessary for widespread adoption. Even knowing that ease-of-use is not a criterion for acceptance into boost, looking at what is required of the client to use the BGL always leaves me feeling perplexed. Is there any particular reason that a simplified interface is not made available? Perhaps a container adapter could be packaged with the library allowing a compromise of functionality and flexibility for simplicity? If a graphing problem is trivial, shouldn't BGL provide a trivial solution? Why are the simplest useful examples several hundred lines of code? I apologize for all of my vague criticisms - my intention is not to flame but rather to test the waters. It is difficult for me to assess whether the simplicity I yearn for isn't present for stylistic reasons or whether it would rather necessitate a sacrifice of flexibility, functionality or implementation clarity. Nor is it clear to me to what extent these criteria can be compromised to promote clarity of client code. For what it is worth, the kind of ease-of-use I'm imagining might look like: #include <less_than_10_graph_headers> ... digraph<some_node_type,some_edge_context_type> g; g << "vertex" << make_pair("vertex", "implicit_vertex"); g.add_edge("brother", "sister", "sibling"); if(g.find(make_pair("brother", "sister"))) related = true; Could someone please elucidate on why it is impossible/impractical/unnecessary/whatever for a graph library to have such an interface? Should I accept that the BGL is not the magic bullet graph library and move on, or can this kind of simplicity be somehow found within? Thanks in advance, prs __________________________________ Do you Yahoo!? Yahoo! Finance Tax Center - File online. File on time. http://taxes.yahoo.com/filing.html
Provisional Dissonance wrote:
While I understand that the BGL is deeply entrenched in boost culture, certain academic circles, and even publications, I nonetheless suggest that BGL lacks the ease of use necessary for widespread adoption.
I think one of the biggest issue with BGL is documentation. Specifically, there reference is really lacking -- for example, try to figure out what the 'make_label_writer' function does and in what header it's defined. I remember that I had similiar question about a bunch of other functions, too. Another issue is that I never seem to remember how event visitors work and have to look it up in documentation, which invariably requires looking at 3 or 4 separate pages. My favourite problem is external property maps. I really think that I should be able to just run topological_sort(G, back_inserter(order)); and don't bother if 'G' has vertex_index_t property or not. Currently, if I use anything else than vecS for vertex storage, the above code won't compile. Generally, most of the time I assume that all vertex descriptors are integers, and don't try to write really generic code, because I suspect it too much work. I should admit that basic operations like iteration over adjacent vertices are fine -- they are a bit verbose, but it's not a big problem.
digraph<some_node_type,some_edge_context_type> g; g << "vertex" << make_pair("vertex", "implicit_vertex"); g.add_edge("brother", "sister", "sibling"); if(g.find(make_pair("brother", "sister"))) related = true;
Could someone please elucidate on why it is impossible/impractical/unnecessary/whatever for a graph library to have such an interface? Should I accept that the BGL is not the magic bullet graph library and move on, or can this kind of simplicity be somehow found within?
To tell the truth, I have no idea how to specify vertex properties when adding vertex, so maybe this is the thing to improve first. We might have: add_vertex(g, "brother"); we can also have a way to find a vertex with specific value of specific property: find(g, vertex_name, "brother") - Volodya
Hi Vladimir, Thanks for your comments! On Apr 1, 2004, at 1:49 AM, Vladimir Prus wrote:
Specifically, there reference is really lacking -- for example, try to figure out what the 'make_label_writer' function does
That is documented in write-graphviz.html. Did you find the explanation there hard to understand? (In general, I'm not particularly happy with the read/write graphviz interface, but I don't have time now to do a redesign)
and in what header it's defined.
I've added a "Where Defined" section.
I remember that I had similiar question about a bunch of other functions, too.
When you hit one, let me know.
Another issue is that I never seem to remember how event visitors work and have to look it up in documentation, which invariably requires looking at 3 or 4 separate pages.
Any suggestions on how to improve this?
My favourite problem is external property maps. I really think that I should be able to just run
topological_sort(G, back_inserter(order));
and don't bother if 'G' has vertex_index_t property or not. Currently, if I use anything else than vecS for vertex storage, the above code won't compile.
So is your problem with external property maps, or with some graphs that don't provide a vertex index property?
Generally, most of the time I assume that all vertex descriptors are integers, and don't try to write really generic code, because I suspect it too much work.
I should admit that basic operations like iteration over adjacent vertices are fine -- they are a bit verbose, but it's not a big problem.
[snip]
To tell the truth, I have no idea how to specify vertex properties when adding vertex, so maybe this is the thing to improve first. We might have:
add_vertex(g, "brother");
This is how: add_vertex(std::string("brother"), g) or more explicitly: add_vertex(property<vertex_name_t,std::string>("brother"), g) which I have to admit is pretty ugly. Perhaps one way to avoid the complication of using the property class would be to provide some support for the use of a plain struct where each member is a vertex property.
we can also have a way to find a vertex with specific value of specific property:
find(g, vertex_name, "brother")
Sure. Write it up and we'll add it :) It should only be a few lines of code. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington Graduating in August 2004 and looking for work C++ Booster (http://www.boost.org) _______________________________________________
Hi Jeremy,
On Apr 1, 2004, at 1:49 AM, Vladimir Prus wrote:
Specifically, there reference is really lacking -- for example, try to figure out what the 'make_label_writer' function does
That is documented in write-graphviz.html. Did you find the explanation there hard to understand?
Sorry for being unclear. I mean that if I find 'make_label_writer' call in C++ code, I don't know where to look for documentation. There's no single list of all functions with links to documentation, ala "namespace members" in doxygen documentation.
(In general, I'm not particularly happy with the read/write graphviz interface, but I don't have time now to do a redesign)
and in what header it's defined.
I've added a "Where Defined" section.
Thanks.
I remember that I had similiar question about a bunch of other functions, too.
When you hit one, let me know.
Sure.
Another issue is that I never seem to remember how event visitors work and have to look it up in documentation, which invariably requires looking at 3 or 4 separate pages.
Any suggestions on how to improve this?
Not yet :-( Maybe I'll have some suggestion next time I'll use visitors.
My favourite problem is external property maps. I really think that I should be able to just run
topological_sort(G, back_inserter(order));
and don't bother if 'G' has vertex_index_t property or not. Currently, if I use anything else than vecS for vertex storage, the above code won't compile.
So is your problem with external property maps, or with some graphs that don't provide a vertex index property?
The problem is that if a graph don't privde vertex index property, then it's not possible to create efficient external property map -- the only way I know is std::map, which is not as fast as property maps which use indices.
Generally, most of the time I assume that all vertex descriptors are integers, and don't try to write really generic code, because I suspect it too much work.
I should admit that basic operations like iteration over adjacent vertices are fine -- they are a bit verbose, but it's not a big problem.
[snip]
To tell the truth, I have no idea how to specify vertex properties when adding vertex, so maybe this is the thing to improve first. We might have:
add_vertex(g, "brother");
This is how: add_vertex(std::string("brother"), g) or more explicitly: add_vertex(property<vertex_name_t,std::string>("brother"), g) which I have to admit is pretty ugly.
Ah, but the documentation does not say that std::string is convertible to property<vertex_name_t,std::string>("brother"), at least I can't find it. Also, what happens if vertex_propety is property<vertex_name_t, std::string, property<vertex_index_t, unsigned> > will conversion from std::string or property<vertex_name_t, std::string> work?
Perhaps one way to avoid the complication of using the property class would be to provide some support for the use of a plain struct where each member is a vertex property.
Probably, but we'd need to way to associate PropertyTag with each member. Another idea: isn't this a good application for named function parameters? add_vertex(g, vertex_name_t("brother").vertex_index_t(10)); ? I'm still in dark about named parameters used by BGL or the upcoming named param library, so is not sure if this exact syntax is implementable.
we can also have a way to find a vertex with specific value of specific property:
find(g, vertex_name, "brother")
Sure. Write it up and we'll add it :) It should only be a few lines of code.
Yea, but first the original poster should indicate if this is what he's looking for -- I never needed this myself. - Volodya
Hi Vladimir, On Apr 2, 2004, at 12:58 AM, Vladimir Prus wrote:
Sorry for being unclear. I mean that if I find 'make_label_writer' call in C++ code, I don't know where to look for documentation. There's no single list of all functions with links to documentation, ala "namespace members" in doxygen documentation.
Ahh. Yes, we do need an index.
So is your problem with external property maps, or with some graphs that don't provide a vertex index property?
The problem is that if a graph don't privde vertex index property, then it's not possible to create efficient external property map -- the only way I know is std::map, which is not as fast as property maps which use indices.
Is there some reason you want to have a graph without a vertex index property and also use external property maps? If not, just use graph a with a vertex index internal property. Or am I missing something?
Ah, but the documentation does not say that std::string is convertible to property<vertex_name_t,std::string>("brother"), at least I can't find it.
Oops, there's lots of stuff missing from the docs for property. I've checked in a bunch of additions.
Also, what happens if vertex_propety is
property<vertex_name_t, std::string, property<vertex_index_t, unsigned> >
will conversion from std::string or property<vertex_name_t, std::string> work?
Nope. See the new docs.
Probably, but we'd need to way to associate PropertyTag with each member. Another idea: isn't this a good application for named function parameters?
add_vertex(g, vertex_name_t("brother").vertex_index_t(10));
? I'm still in dark about named parameters used by BGL or the upcoming named param library, so is not sure if this exact syntax is implementable.
That's a good idea. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington Graduating in August 2004 and looking for work C++ Booster (http://www.boost.org) _______________________________________________
Hi Vladimir, On Apr 2, 2004, at 10:08 AM, Jeremy Siek wrote:
Also, what happens if vertex_propety is
property<vertex_name_t, std::string, property<vertex_index_t, unsigned> >
will conversion from std::string or property<vertex_name_t, std::string> work?
Nope. See the new docs.
I answered too quickly. Actually, that will work. But if you were to reverse the order of the name and index properties, it would not work. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington Graduating in August 2004 and looking for work C++ Booster (http://www.boost.org) _______________________________________________
Hi Jeremy,
The problem is that if a graph don't privde vertex index property, then it's not possible to create efficient external property map -- the only way I know is std::map, which is not as fast as property maps which use indices.
Is there some reason you want to have a graph without a vertex index property and also use external property maps? If not, just use graph a with a vertex index internal property. Or am I missing something?
The issue is for all types of graph that don't use vecS for vertices storage, you need to manually initialize vertex index (or am I mistaked?). I looks like a big inconvenience for me, so I basically always assume that I use vecS.
Ah, but the documentation does not say that std::string is convertible to property<vertex_name_t,std::string>("brother"), at least I can't find it.
Oops, there's lots of stuff missing from the docs for property. I've checked in a bunch of additions.
Thanks! The updated docs now answer my question.
Another idea: isn't this a good application for named function parameters?
add_vertex(g, vertex_name_t("brother").vertex_index_t(10));
? I'm still in dark about named parameters used by BGL or the upcoming named param library, so is not sure if this exact syntax is implementable.
That's a good idea.
Ok, placed to the ideas bag ;-) Hopefully one day we can grab it from there and implement -- though need to understand what other users want. - Volodya
Hi Vladimir, On Apr 5, 2004, at 12:55 AM, Vladimir Prus wrote:
The issue is for all types of graph that don't use vecS for vertices storage, you need to manually initialize vertex index (or am I mistaked?). I looks like a big inconvenience for me, so I basically always assume that I use vecS.
Okay, I agree that automatic initialization of the vertex indices would be a good thing to have... may not even by that hard to implement. I'll look into it. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington Graduating in August 2004 and looking for work C++ Booster (http://www.boost.org) _______________________________________________
participants (3)
-
Jeremy Siek -
Provisional Dissonance -
Vladimir Prus