Q: Graphs. Sorting edges. Possible? How to?
Hello. I a newbie in BGL and I rewrite my LEDA code now... I have to sort (order) edges according to some functor. For example (simplified): typedef adjacency_list<vecS, vecS, bidirectionalS> MyGraph; typedef graph_traits < MyGraph >::edge_descriptor MyGraphEdge; typedef graph_traits < MyGraph >::edge_iterator MyEdgeIter; class MyCompareEdges{ public: bool operator()(MyGraphEdge e1, MyGraphEdge e2) const { return true; } }; .... { MyGraph Gr(10); MyEdgeIter ei_beg, ei_end; MyCompareEdges comp; tie(ei_beg, ei_end) = edges(Gr); std::sort(ei_beg, ei_end, comp); //Error C2676 } And I have error C2676 (below the message...). Questions: 1. Is it possible to sort edges in the graph? 2. How to... Thanks all in advance... Stas Fomin. P.S. vecS, setS, listS for edge container... - C2676. ------------------------------ d:\projects\lib\cpp_libs\libboost\boost\iterator_adaptors.hpp(264) : error C2676: binary '+=' : 'class std::list<struct boost::list_edge<unsigned int,struct boost::no_property>,class std::allocator<struct boost::list_edge<unsigned int,struct boost:: no_property> > >::iterator' does not define this operator or a conversion to a type acceptable to the predefined operator d:\projects\lib\cpp_libs\libboost\boost\iterator_adaptors.hpp (911) : see reference to function template instantiation 'void __thiscall boost::default_iterator_policies::advance(struct boost::iterator_adaptor<class std::list<struct boost::lis t_edge<unsigned int,struct boost::no_property>,class std::allocator<struct boost::list_edge<unsigned int,struct boost::no_property> > >::iterator,struct boost::detail::undirected_edge_iter_policies,class boost::detail::edge_desc_impl<struct boost::b idirectional_tag,unsigned int>,class boost::detail::edge_desc_impl<struct boost::bidirectional_tag,unsigned int>,class boost::detail::edge_desc_impl<struct boost::bidirectional_tag,unsigned int> *,struct boost::multi_pass_input_iterator_tag,int> &,i nt)' being compiled Error executing cl.exe.
Hi Stas, The edge_iterator's of the BGL are read only. You can not reorder the graph through the iterators. By using a custom container (use a std::set with your custom comparison function) for the EdgeList type, you can get the out-edges of each vertex sorted, but there currently is not a way to get the entire edge list sorted. People keep asking about this... I need to look into providing better support for this. Or if someone else wants to look into this, we'd all be grateful. Cheers, Jeremy On Tue, 18 Jun 2002, stas_fomin wrote: stas_f> Hello. stas_f> I a newbie in BGL and I rewrite my LEDA code now... stas_f> stas_f> I have to sort (order) edges according to some functor. stas_f> stas_f> For example (simplified): stas_f> stas_f> typedef adjacency_list<vecS, vecS, bidirectionalS> MyGraph; stas_f> typedef graph_traits < MyGraph >::edge_descriptor MyGraphEdge; stas_f> typedef graph_traits < MyGraph >::edge_iterator MyEdgeIter; stas_f> stas_f> class MyCompareEdges{ stas_f> public: stas_f> bool operator()(MyGraphEdge e1, MyGraphEdge e2) const stas_f> { stas_f> return true; stas_f> } stas_f> }; stas_f> stas_f> .... stas_f> stas_f> { stas_f> MyGraph Gr(10); stas_f> MyEdgeIter ei_beg, ei_end; stas_f> MyCompareEdges comp; stas_f> tie(ei_beg, ei_end) = edges(Gr); stas_f> std::sort(ei_beg, ei_end, comp); //Error C2676 stas_f> } stas_f> stas_f> And I have error C2676 (below the message...). stas_f> stas_f> Questions: stas_f> 1. Is it possible to sort edges in the graph? stas_f> 2. How to... stas_f> stas_f> stas_f> Thanks all in advance... stas_f> Stas Fomin. stas_f> stas_f> P.S. stas_f> vecS, setS, listS for edge container... - C2676. stas_f> stas_f> ------------------------------ stas_f> d:\projects\lib\cpp_libs\libboost\boost\iterator_adaptors.hpp(264) : stas_f> error C2676: binary '+=' : 'class std::list<struct stas_f> boost::list_edge<unsigned int,struct boost::no_property>,class stas_f> std::allocator<struct boost::list_edge<unsigned int,struct boost:: stas_f> no_property> > >::iterator' does not define this operator or a stas_f> conversion to a type acceptable to the predefined operator stas_f> d:\projects\lib\cpp_libs\libboost\boost\iterator_adaptors.hpp stas_f> (911) : see reference to function template instantiation 'void stas_f> __thiscall boost::default_iterator_policies::advance(struct stas_f> boost::iterator_adaptor<class std::list<struct boost::lis stas_f> t_edge<unsigned int,struct boost::no_property>,class stas_f> std::allocator<struct boost::list_edge<unsigned int,struct stas_f> boost::no_property> > >::iterator,struct stas_f> boost::detail::undirected_edge_iter_policies,class stas_f> boost::detail::edge_desc_impl<struct boost::b stas_f> idirectional_tag,unsigned int>,class stas_f> boost::detail::edge_desc_impl<struct stas_f> boost::bidirectional_tag,unsigned int>,class stas_f> boost::detail::edge_desc_impl<struct stas_f> boost::bidirectional_tag,unsigned int> *,struct stas_f> boost::multi_pass_input_iterator_tag,int> &,i stas_f> nt)' being compiled stas_f> Error executing cl.exe. stas_f> stas_f> stas_f> stas_f> stas_f> stas_f> stas_f> Info: <http://www.boost.org> stas_f> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> stas_f> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com> stas_f> stas_f> stas_f> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ stas_f> stas_f> ---------------------------------------------------------------------- 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 ----------------------------------------------------------------------
Thank you, Jeremy.
The edge_iterator's of the BGL are read only. You can not reorder the graph through the iterators.
It is annoys me. Reordering edges will be very useful, for example, reordering edges in planar graph (according to some planar layout) for (re)computing faces...
By using a custom container (use a std::set with your custom comparison function) for the EdgeList type, you can get the out-edges of each vertex sorted, but there currently is not a way to get the entire edge list sorted. Ok... But BGL docs is less understandable (in comparison with LEDAbook) for me (I know I am stupid).
So, please, show me small example of declaration of some graph with out_edges sorted according to some function... I would be be very grateful. Regards, Stas.
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 <boost/config.hpp> #include <iostream> #include <functional> #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp> /* 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<StoredEdge,StoredEdge,bool> { 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<ordered_set_by_nameS, ValueType> { typedef std::multiset<ValueType, order_by_name<ValueType> > type; }; template <> struct parallel_edge_traits<ordered_set_by_nameS> { 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<edge_name_t, std::string> EdgeProperty; typedef adjacency_list<ordered_set_by_nameS, vecS, undirectedS, no_property, EdgeProperty> 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<graph_type, vertex_index_t>::type id = get(vertex_index, g); property_map<graph_type, edge_name_t>::type name = get(edge_name, g); graph_traits<graph_type>::vertex_iterator i, end; graph_traits<graph_type>::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<graph_type> 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 ----------------------------------------------------------------------
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) --- In Boost-Users@y..., Jeremy Siek <jsiek@c...> 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 <boost/config.hpp> #include <iostream> #include <functional> #include <string>
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp>
/* 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<StoredEdge,StoredEdge,bool> { 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<ordered_set_by_nameS, ValueType> { typedef std::multiset<ValueType, order_by_name<ValueType> > type; }; template <> struct parallel_edge_traits<ordered_set_by_nameS> { 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<edge_name_t, std::string> EdgeProperty; typedef adjacency_list<ordered_set_by_nameS, vecS, undirectedS, no_property, EdgeProperty> 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<graph_type, vertex_index_t>::type id = get (vertex_index, g); property_map<graph_type, edge_name_t>::type name = get(edge_name, g);
graph_traits<graph_type>::vertex_iterator i, end; graph_traits<graph_type>::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<graph_type> 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 -------------------------------------------------------------------- --
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)
--- In Boost-Users@y..., Jeremy Siek <jsiek@c...> 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 <boost/config.hpp> #include <iostream> #include <functional> #include <string>
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp>
/* 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<ordered_set_by_nameS, ValueType> { // typedef std::multiset<ValueType, order_by_name<ValueType> > type; // }; //template <> //struct parallel_edge_traits<ordered_set_by_nameS> { // typedef allow_parallel_edge_tag type; // }; // } //#endif Replaced by ..... namespace boost { struct orderedmultisetS { template <class T> struct bind_ { typedef std::multiset<T, order_by_name<T> > 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" <loopylozzysdad@y...> 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<StoredEdge,StoredEdge,bool> { 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<ordered_set_by_nameS, ValueType> { typedef std::multiset<ValueType, order_by_name<ValueType> > type; }; template <> struct parallel_edge_traits<ordered_set_by_nameS> { 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<edge_name_t, std::string> EdgeProperty; typedef adjacency_list<ordered_set_by_nameS, vecS, undirectedS, no_property, EdgeProperty> 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<graph_type, vertex_index_t>::type id = get (vertex_index, g); property_map<graph_type, edge_name_t>::type name = get (edge_name, g);
graph_traits<graph_type>::vertex_iterator i, end; graph_traits<graph_type>::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<graph_type> 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 ------------------------------------------------------------------ -- --
Hi Richard, On Wed, 6 Nov 2002, loopylozzysdad wrote: Richar> Hi, Richar> Richar> I did work out the answer to my own question. I can't explain Richar> how/why this works but by copying from the header files I ended up Richar> with the following changes to Jeremy's posted code...[1] Richar> Good luck if you want it - please don't ask me to explain it! I can explain it :) As hinted by the #ifndef, the commented out version of container_gen uses partial specialization. The first parameter to container_gen is specialized, but the second is left as a template. Partial spec. is not yet supported by VC++ (but soon will be). The change you made is one of the classic ways of replacing partial specialization with full specialization. You remove the unspecialized parameter, and instead add a nested class template (here it is bind_). Cheers, Jeremy Richar> Richard Richar> Richar> Richar> [1] Richar> Comment out from original .... Richar> //struct ordered_set_by_nameS { }; Richar> Richar> //#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION Richar> //namespace boost { Richar> // template <class ValueType> Richar> //struct container_gen<ordered_set_by_nameS, ValueType> { Richar> // typedef std::multiset<ValueType, order_by_name<ValueType> > Richar> type; Richar> // }; Richar> //template <> Richar> //struct parallel_edge_traits<ordered_set_by_nameS> { Richar> // typedef allow_parallel_edge_tag type; Richar> // }; Richar> // } Richar> //#endif Richar> Richar> Replaced by ..... Richar> namespace boost { Richar> struct orderedmultisetS { Richar> template <class T> Richar> struct bind_ { typedef std::multiset<T, order_by_name<T> > Richar> type; }; // std::less<T> Richar> }; Richar> Richar> BOOST_CONTAINER_SELECTOR(orderedmultisetS); Richar> Richar> template <> Richar> struct parallel_edge_traits<orderedmultisetS> { Richar> typedef disallow_parallel_edge_tag type; Richar> }; Richar> Richar> } Richar> ---------------------------------------------------------------------- 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 ----------------------------------------------------------------------
On Tue, 18 Jun 2002, Jeremy Siek wrote: jsiek> By using a custom container (use a std::set with your custom comparison jsiek> function) for the EdgeList type, you can get the out-edges of each vertex jsiek> sorted, but there currently is not a way to get the entire edge list jsiek> sorted. I just realized that I'm probably wrong about the second part of the above statement. I think you can get the whole edge list sorted via a similar approach as the out-edges. I recently added a 7th template paramter to adjacency_list, which makes it possible to customize the edge-list container. Cheers, Jeremy ---------------------------------------------------------------------- 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 ----------------------------------------------------------------------
participants (4)
-
Jeremy Siek -
loopylozzysdad -
loopylozzysdad -
stas_fomin