[Home]Documentation - Graph Library

BOOST WIKI | RecentChanges | Preferences | Page List | Links List

This page is for discussion of problems in the Boost Graph Library documentation

Back to graph library pages

Creating custom edge property tag

In the documentation, under "Using adjacency_list", subsection "Custom Edge Properties", it shows a method for declaring a custom property tag:

> struct flow_t {
>   typedef edge_property_tag kind;
> };
> struct capacity_t {
>   typedef edge_property_tag kind;
> };

It goes on to say that an alternative method is this:

> enum edge_myflow_t { edge_myflow };
> enum edge_mycapacity_t { edge_mycapacity };
> namespace boost {
>   BOOST_INSTALL_PROPERTY(edge, myflow);
>   BOOST_INSTALL_PROPERTY(edge, mycapacity);
> }

In the rest of the code included in the documentation, it uses the first method. Finally, it says:

>  The file edge_property.cpp shows the complete source code for this example.

However, the code in edge_property.cpp is completely different -- using the second method rather than the first. So, at a minimum, the final sentence is wrong.

I suggest the alternative methods should both be shown in the sample code. I made the necessary changes to edge_property.cpp -- here's the diff (against Boost release 1.30.0):

> #define ALTERNATE  // comment this out to see an alternate method
> #ifdef ALTERNATE
> struct flow_t {
>     typedef edge_property_tag kind;
> };
> struct capacity_t {
>     typedef edge_property_tag kind;
> };
> #else
> #endif
<   property_map<Graph, edge_mycapacity_t>::const_type
> #ifdef ALTERNATE
>   typename property_map<Graph, capacity_t>::const_type capacity = get(capacity_t(), G);
>   typename property_map<Graph, flow_t>::const_type flow = get(flow_t(), G);
> #else
>   typename property_map<Graph, edge_mycapacity_t>::const_type
<   property_map<Graph, edge_myflow_t>::const_type
>   typename property_map<Graph, edge_myflow_t>::const_type
> #endif
> #ifdef ALTERNATE
>   typedef property<capacity_t, int> Cap;
>   typedef property<flow_t, int, Cap> Flow;
>   typedef adjacency_list<vecS, vecS, bidirectionalS, no_property, Flow> Graph;
> #else
> #endif
> #ifdef ALTERNATE
>   property_map<Graph, flow_t>::type
>     flow = get(flow_t(), G);

> #else
> #endif

    - People/Chuck Messenger

Outdated method for making property tag

In "Using adjacency_list", then "Custom Vertex Properties", it shows the following code to generate a custom vertex:

>   struct first_vertex_name_t {
>       typedef vertex_property_tag kind;
>   };
>   typedef property<first_vertex_name_t, std::string> FirstNameProperty;
>   typedef adjacency_list<vecS, vecS, directedS,
>                          FirstNameProperty> MyGraphType;

Later, it says:

>   The complete source code to this example is in the file interior_property_map.cpp

While the above code seems to work fine, it is confusing - it is apparantly an older, non-recommended/non-standard technique. Presumably, as per discussion in the previous subsection, "Custom Edge Properties", and as demonstrated in the sample code in interior_property_map.cpp, the correct method would be:

>   enum vertex_first_name_t { vertex_first_name };
>   namespace boost {
>       BOOST_INSTALL_PROPERTY(vertex, first_name);
>   }

The doc should be updated to show this method. Or, at a minimum, the sample code should be changed to use the method described in the doc.

    - People/Chuck Messenger

push_dispatch(), etc, are defunct

In "Using adjacency_list", then "Push and Erase for the Edge List Container", it says:

>   The family of push_dispatch() and erase_dispatch() function overloads handle
>   the various ways inserting and erasing can be done with standard containers.
>       template <class Container, class T>
>       std::pair<typename Container::iterator, bool>
>       push(Container& c, const T& v)
>       {
>           return push_dispatch(c, v, container_category(c));
>       }
>       template <class Container, class T>
>       void erase(Container& c, const T& x)
>       {
>           erase_dispatch(c, x, container_category(c));
>       }

I can't find push_dispatch, erase_dispatch or container_category anywhere in boost_1_30_0/boost/graph. Apparantly, the above is no longer true.

It would be useful to have sample code showing how to implement a fully-custom container, as opposed to the existing custom-container code, which uses an std::list with a custom allocator. The current code doesn't need to deal with the above push() and erase() issues, since BGL has built-in support for std::list. Therefore, there is no sample code showing how to properly implement push() and erase().

    - People/Chuck Messenger

random_access_iterator_property_map is defunct

In "Property Maps", then "Exterior Properties", the following example code is shown:

>   boost::random_access_iterator_property_map
>       <int*, int, int&, EdgeID_Map>
>            capacity(capacity_array, edge_id),
>            flow(flow_array, edge_id);

However, a complete search of boost_1_30_0 revealed that random_access_iterator_property_map appears in only 2 places:

    boost/graph/detail/self_avoiding_walk.hpp, e.g.:

         typedef random_access_iterator_property_map<Iter*,Iter,Iter&> IterD;


So, apparantly random_access_iterator_property_map is obsolete.

Later, the doc says:

>  The complete source code for this example is in
>             examples/exterior_edge_properties.cpp.

However, this file doesn't exist. Instead, examples/exterior_properties.cpp appears to be the intended file. However, the code in this file is quite different. Below I compare what's in the doc to what's in exterior_properties.cpp. First, the following is identical (ignoring formatting/identifier names):

   typedef adjacency_list<vecS, vecS, bidirectionalS, 
     no_property, property<edge_index_t, std::size_t> > Graph;
   const int num_vertices = 9;
   Graph G(num_vertices);

   int capacity_array[] = { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 };
   int flow_array[] = { 8, 12, 12, 12, 12, 12, 16, 16, 16, 8 };

   // Add edges to the graph, and assign each edge an ID number.
   add_edge(0, 1, 0, G);
   // ...

   typedef property_map<Graph, edge_index_t>::type EdgeID_Map;
   EdgeID_Map edge_id = get(edge_index, G);

Then, in the doc we have:

   typedef boost::graph_traits<Graph>::edge_descriptor Edge;  // (CHM note: this line is superfluous)

   random_access_iterator_property_map <int*, int, int&, EdgeID_Map>
               capacity(capacity_array, edge_id), flow(flow_array, edge_id);

   print_network(G, capacity, flow);

while in exterior_properties.cpp, we have:

   typedef iterator_property_map<int*, EdgeID_Map, int, int&> IterMap;

   print_network(G, IterMap(capacity_array, edge_id), IterMap(flow_array, edge_id));

which could be rewritten as:

   iterator_property_map <int*, EdgeID_Map, int, int&>
               capacity(capacity_array, edge_id), flow(flow_array, edge_id);

   print_network(G, capacity, flow);

to be analogous to the doc. Hence, iterator_property_map<> apparantly replaces random_access_iterator_property_map<>, with different argument ordering.

Apparantly, the doc is out of date.

    - People/Chuck Messenger

using vertex_descriptor as a 0-based index

In examples/exterior_property_map.cpp, there is a completely different, and simpler, method for implementing/accessing an exterior property map -- the map is simply an array of the right length, indexed by vertex_descriptor's. We have:

   who_owes_who(edges(G).first, edges(G).second, G, names);

where names is a string*. Then:

   template <class EdgeIter, class Graph, class Name>
   void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G, Name name)
       while (first != last) {
           cout << name[source(*first,G)] << " owes " << name[target(*first,G)]
                      << " some money" << endl;

So, what's with all the iterator_property_map<> stuff? It looks like you can just dispense with it, since source() and target(), which supposedly return graph_traits<>::vertex_descriptor's, really just return integers (i.e. they're used to index a string*).

In other sample code, do something like the following, in order to convert a vertex_descriptor into a 0-based integral index:

    typename property_map<G, vertex_index_t>::type index = get(vertex_index, graph);

    typename graph_traits<G>::edge_descriptor e;
    typename graph_traits<G>::out_edge_iterator out_i, out_end;

    for (tie(out_i, out_end) = out_edges(v, graph); out_i != out_end; ++out_i) {
        e = *out_i;
        Vertex src = source(e, graph);
        Vertex targ = target(e, graph);
        cout << "(" << index[src] << "," << index[targ] << ") ";

Why go to all that trouble, when apparantly, source() and target() are already 0-based indexes? That is, apparantly, "index[x]" in the above code always returns x -- i.e. it's the identity function.

In another section ("File Dependency Example"), we have the following code:

    typedef graph_traits<Graph>::vertex_descriptor Vertex;

    const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp", ... };

    typedef list<Vertex> MakeOrder;
    MakeOrder make_order;
    topological_sort(g, front_inserter(make_order));

    cout << "make ordering: ";
    for (MakeOrder::iterator i = make_order.begin(); i != make_order.end(); ++i)
        cout << name[*i] << " ";
    cout << endl;

Again, a vertex_descriptor is being used as a 0-based index. I've seen many other examples in the documenation of a vertex_descriptor being used as a 0-based index.

    - People/Chuck Messenger

Why not use in_degree()?

In the section "File Dependency Example", we see the following code to calculate the in-degree of each node:

    vector<int> in_degree(N, 0);
    Graph::vertex_iterator i, iend;
    Graph::out_edge_iterator j, jend;
    for (tie(i, iend) = vertices(g); i != iend; ++i)
        for (tie(j, jend) = out_edges(*i, g); j != jend; ++j)
            in_degree[target(*j, g)] += 1;

This seems strange, since I'd have thought we can see the in-degree directly, by looking at the in_edges():

    Graph::vertex_iterator i, iend;
    Graph::in_edge_iterator j, jend;
    for (tie(i, iend) = vertices(g); i != iend; ++i) {
        tie(j, jend) = in_edges(*i, g);
        if (jend - j == 0)
            no in-edges...

Why is the in_degree[] calculation necessary? An explanation would be helpful -- e.g. in_edges() is inefficient, and why in_edges() is inefficient.

    - People/Chuck Messenger

I changed the name of this wiki page, to be consistent. Here's the old page: BGL Notes This note is here only to keep the BGL Notes page alive, because I linked to it from the outside world...

    - People/Chuck Messenger

BOOST WIKI | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited May 17, 2003 6:12 am (diff)
Disclaimer: This site not officially maintained by Boost Developers