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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-06-18 13:14:10

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_at_[hidden]>
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_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------