Re: Q: Graphs. Sorting edges. Possible? How to?

Hi,

This answer (from Jeremy) is EXACTLY what I want! Sadly though I am 'compilationally challenged' i.e. Visual C++ .NET chokes on it! I don't understand the workaround in the header files enough to get it working for me. Can anyone give me a clue about how to make the same idea work in VC++.

Thanks - Richard Howells (LoopyLozzysDad at yahoo dot com)

...

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

--- In Boost-Users@y..., Jeremy Siek wrote: 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 -

Hi, I did work out the answer to my own question. I can't explain how/why this works but by copying from the header files I ended up with the following changes to Jeremy's posted code...[1] Good luck if you want it - please don't ask me to explain it! Richard [1] Comment out from original .... //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 Replaced by ..... namespace boost { struct orderedmultisetS { template <class T> struct bind_ { typedef std::multiset type; }; // std::less<T> }; BOOST_CONTAINER_SELECTOR(orderedmultisetS); template <> struct parallel_edge_traits<orderedmultisetS> { typedef disallow_parallel_edge_tag type; }; } --- In Boost-Users@y..., "loopylozzysdad" wrote: -

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@o... C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ------------------------------------------------------------------ -- --