Documentation - Graph Library

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):

78a79,88
> #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
86c96
<
---
> #endif
95c105,109
<   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
97c111
<   property_map<Graph, edge_myflow_t>::const_type
---
>   typename property_map<Graph, edge_myflow_t>::const_type
98a113
> #endif
125a141,145
> #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
129a150
> #endif
163a185,188
> #ifdef ALTERNATE
>   property_map<Graph, flow_t>::type
>     flow = get(flow_t(), G);

> #else
165a191
> #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;

    libs/graph/doc/using_property_maps.html

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;
           ++first;
       }
   }

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.

• Suggestion 1: If vertex descriptors are really 0-based integer indeces, then dispense with all the confusing vertex_descriptor stuff. It makes things more confusing than they need to be. Alternatively, if it is seen as being really important to keep vertex descriptors generic, then change exterior_property_map.cpp, etc., to use a conforming access method. And what about edge descriptors? Are they really 0-based indeces too?

• Suggestion 2: Point out that a vertex_descriptor is generally just a 0-based integer index. That would have helped me understand what was going on. Or, better yet, spell out some scenarios: for example, if you're using adjacency_list<>, then maybe a vertex_descriptor is an integer, but if you're using graph implementation X, vertex_descriptor is a Y. Etc. That is, spell out some scenarios in order to make things more concrete, and therefore, more comprehensible.

• Suggestion 3: Explain how the internal property maps work -- that some of them, apparantly, have special behavior. In particular, it seems that vertex_index_t property maps get auto-initialized to the identity function: index[x] = x. Spell this out (if true), and gives some other concrete examples.

    - 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