TL;DR: I would very much like for the order of iteration of in_edges
on my graph (adjacency_list
with edge_list of setS
) to be
determinstic, but as far as I can tell, the order of iteration is
determined by a comparison operator that is just pointer
comparison---thus iteration order is determined by the vagaries of
malloc
. Help!
For concreteness, my graph and related types are:
struct VertexCargo { int Id; ... };
typedef adjacency_list<setS, vecS, bidirectionalS, property<vertex_info_t, VertexCargo> > Graph;
typedef graph_traits<Graph>::edge_descriptor ED;
typedef graph_traits<Graph>::vertex_descriptor VD;
My logic, in case anyone spots a fallacy anywhere:
in_edges
iteration is directly determined by iteration of the edge list containeredge list of
setS
implies underlying containerstd::set<edge_desc_impl>
Note: this assumption was incorrect; it is actually astd::set<StoredEdge
, which offers a comparator that compares on edge target.std::set<edge_desc_impl>
iteration order determined byoperator<(edge_desc_impl, edge_desc_impl)
operator<(edge_desc_impl, edge_desc_impl)
ends up being just a pointer comparison;
The operator< is defined in boost/graph/detail/edge.hpp
(boost 1.58):
30 template <typename Directed, typename Vertex>
31 class edge_desc_impl : public edge_base<Directed,Vertex> {
...
35 typedef void property_type;
36
37 inline edge_desc_impl() : m_eproperty(0) {}
38
39 inline edge_desc_impl(Vertex s, Vertex d, const property_type* eplug)
40 : Base(s,d), m_eproperty(const_cast<property_type*>(eplug)) { }
41
42 property_type* get_property() { return m_eproperty; }
43 const property_type* get_property() const { return m_eproperty; }
44
45 // protected:
46 property_type* m_eproperty;
47 };
48
...
63
64 // Order edges according to the address of their property object
65 template <class D, class V>
66 inline bool
67 operator<(const detail::edge_desc_impl<D,V>& a,
68 const detail::edge_desc_impl<D,V>& b)
69 {
70 return a.get_property() < b.get_property();
71 }
I would really like it if there were a way to induce the comparison
(and thus iteration order) to be based on something deterministic
(i.e. not pointer addresses determined by mallloc; for example a
custom operator I write that looks at VertexCargo::Id
for source and
target of the edges) but it looks like that might not be workable here
because of the void*
cast.
From the code above it also looks possible (?) to inject a property
giving the desired ordering. But that strikes me as a hack.
Anybody have wisdom to share?
Note on the answer
@sehe's response is the correct answer---the underlying container is in fact a std::set<StoredEdge>
, which defines an operator<
that compares on the edge target; this is deterministic when the vertex container selector is vecS
but not in general (since the vertex identifiers in other cases are basically pointers gotten from malloc).
As I expected (from my recollection) the edge lists (both in/out) are already ordered by their targets, hence they are deterministic.
This is especially unambiguous when the VertexContainer selector is
vecS
because, there, thevertex_descriptor
is a simple integral type, that doubles as yourvertex_index_t
property anyways.Down The Rabbit Hole
Because I'm not a Boost Graph developer, and hence I donot know the architecture of the BGL types like
adjacency_list
, I naively started at our top-level entry point:Which is instantiated as:
Filling in
Points us the instantiation at
adj_list_gen<...>::config
and there the iterator is declared asAnd because the container selector is
setS
, it will be astd::set
ofStoredEdge
, which isWhich evaluates to
Now this, of course, points to the implementation of the EdgeList...
Now Hold It! Hit The Brakes
But what's most important is the total weak ordering imposed - so we don't go further down that rabbit-hole, but instead shift our attention to
stored_edge_iter<>::operator<
or similar.Aha! The ordering is already deterministically defined. You can access it directly using e.g.
But you don't need to. Using the generic graph accessors would be pretty much the same:
And you can verify that the collections are properly sorted as expect using e.g.
DEMO
Here's a full demo including all the above and asserting all the expected orderings on a large random-generated graph:
Live On Coliru