Re: [Boost-users] Q: Graphs. Sorting edges. Possible? How to?

I've found this partial solution for what I'm searching for. This code sorts by target, name. I want to sort by source, target. I find that in boost::graph adjacency_list edge descriptors there is a "get_target" method, but no "get_source" method. Can someone tell me how to either find the equivalent or give the comparison function object a non-default constructor so I can pass it a graph reference? Actually in the latter, I need assistance in feeding the graph reference to the graph object at construction time, not writing a constructor. Jeremy Siek wrote:

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