On Wed, 19 Jun 2002, stas_fomin wrote:
stas_f> > By using a custom container (use a std::set with your custom
stas_f> comparison
stas_f> > function) for the EdgeList type, you can get the out-edges of each
stas_f> vertex
stas_f> > sorted, but there currently is not a way to get the entire edge list
stas_f> > sorted.
stas_f> Ok... But BGL docs is less understandable (in comparison with
stas_f> LEDAbook) for me (I know I am stupid).
Have you tried reading the BGL book?
stas_f> So, please, show me small example of declaration
stas_f> of some graph with out_edges sorted according to some function...
Here you go. Also, this example is checked into the libs/graph/example/
directory.
#include
#include <iostream>
#include <functional>
#include <string>
#include
#include
/*
Sample output:
0 --chandler--> 1 --joe--> 1
1 --chandler--> 0 --joe--> 0 --curly--> 2 --dick--> 3 --dick-->
3
2 --curly--> 1 --tom--> 4
3 --dick--> 1 --dick--> 1 --harry--> 4
4 --tom--> 2 --harry--> 3
name(0,1) = chandler
name(0,1) = chandler
name(0,1) = joe
*/
template <class StoredEdge>
struct order_by_name
: public std::binary_function
{
bool operator()(const StoredEdge& e1, const StoredEdge& e2) const {
// Order by target vertex, then by name.
// std::pair's operator< does a nice job of implementing
// lexicographical compare on tuples.
return std::make_pair(e1.get_target(), boost::get(boost::edge_name,
e1))
< std::make_pair(e2.get_target(), boost::get(boost::edge_name, e2));
}
};
struct ordered_set_by_nameS { };
#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
namespace boost {
template <class ValueType>
struct container_gen {
typedef std::multiset type;
};
template <>
struct parallel_edge_traits {
typedef allow_parallel_edge_tag type;
};
}
#endif
int
main()
{
#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
std::cout << "This program requires partial specialization" <<
std::endl;
#else
using namespace boost;
typedef property EdgeProperty;
typedef adjacency_list graph_type;
graph_type g;
add_edge(0, 1, EdgeProperty("joe"), g);
add_edge(1, 2, EdgeProperty("curly"), g);
add_edge(1, 3, EdgeProperty("dick"), g);
add_edge(1, 3, EdgeProperty("dick"), g);
add_edge(2, 4, EdgeProperty("tom"), g);
add_edge(3, 4, EdgeProperty("harry"), g);
add_edge(0, 1, EdgeProperty("chandler"), g);
property_map::type id = get(vertex_index,
g);
property_map::type name = get(edge_name, g);
graph_traits::vertex_iterator i, end;
graph_traits::out_edge_iterator ei, edge_end;
for (boost::tie(i, end) = vertices(g); i != end; ++i) {
std::cout << id[*i] << " ";
for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end;
++ei)
std::cout << " --" << name[*ei] << "--> " << id[target(*ei, g)] << "
";
std::cout << std::endl;
}
std::cout << std::endl;
bool found;
typedef graph_traits Traits;
Traits::edge_descriptor e;
Traits::out_edge_iterator e_first, e_last;
tie(e, found) = edge(0, 1, g);
if (found)
std::cout << "name(0,1) = " << name[e] << std::endl;
else
std::cout << "not found" << std::endl;
std::cout << std::endl;
tie(e_first, e_last) = edge_range(0, 1, g);
while (e_first != e_last)
std::cout << "name(0,1) = " << name[*e_first++] << std::endl;
#endif
return 0;
}
----------------------------------------------------------------------
Jeremy Siek http://php.indiana.edu/~jsiek/
Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu
C++ Booster (http://www.boost.org) office phone: (812) 855-3608
----------------------------------------------------------------------
