Graph Library: Ordered Vertex List?
Hi Guys, I would like to use an ordered vertex list (ie based on property type) in an implementation that I am working on such that duplication can be avoided. I have read and understand how to implement an ordered edge list thanks to the previous posts but am finding it hard to get started! Perhaps I have missed the key example? It appears that from the way config::VertList is constructed that it may be a similar process in nature? adj_list_impl::add_vertex appears to discard the boolean return value from the associative insertion. Would such a construction allow me to avoid the duplication I seek to avoid? I am guessing so, but some advice would give me a confidence "boost". ( <-- It's a lame pun: I really do need help ;-) ) My first steps are below rehashing the excellent ordered edges example with a simple search/replace and maching my target container base. I'll keep plugging along with it anyway and it may just compile one day. Suggestions/Ideas/Refs/Ptrs are appreciated. Matt --- first guess follows --- template <class VertDesc> struct order_by_name : public std::binary_function<VertDesc,VertDesc,bool> { bool operator()(const VertDesc& v1, const VertDesc& v2) const { // Order by vertex name. return boost::get(boost::vertex_name, v1) < boost::get(boost::vertex_name, v2); } }; #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION struct ordered_set_by_nameS { }; namespace boost { template <class ValueType> struct container_gen<ordered_set_by_nameS, ValueType> { typedef std::set<ValueType, order_by_name<ValueType> > type; }; } #else struct ordered_set_by_nameS { template <class T> struct bind_ { typedef std::multiset<T, order_by_name<T> > type; }; }; namespace boost { template <> struct container_selector<ordered_set_by_nameS> { typedef ordered_set_by_nameS type; }; } #endif
Furthermore, I now have another pre-emptive question (in addition to those attached below) following on from my efforts ...: I am trying to use a custom property. How do I write the equivalent of (ie using a boost predefined map?): boost::get(boost::vertex_name, v1) such that I can access my custom property value_type? I am not sure how to resolve for my graph_t as described below...? Thanks again, Matt --- In Boost-Users@yahoogroups.com, "dmatt001" <dmatt001@y...> wrote:
Hi Guys,
I would like to use an ordered vertex list (ie based on property type) in an implementation that I am working on such that duplication can be avoided. I have read and understand how to implement an ordered edge list thanks to the previous posts but am finding it hard to get started!
Perhaps I have missed the key example? It appears that from the way config::VertList is constructed that it may be a similar process in nature? adj_list_impl::add_vertex appears to discard the boolean return value from the associative insertion. Would such a construction allow me to avoid the duplication I seek to avoid? I am guessing so, but some advice would give me a confidence "boost". ( <-- It's a lame pun: I really do need help ;-) )
My first steps are below rehashing the excellent ordered edges example with a simple search/replace and maching my target container base. I'll keep plugging along with it anyway and it may just compile one day. Suggestions/Ideas/Refs/Ptrs are appreciated.
Matt
--- first guess follows ---
template <class VertDesc> struct order_by_name : public std::binary_function<VertDesc,VertDesc,bool> { bool operator()(const VertDesc& v1, const VertDesc& v2) const { // Order by vertex name. return boost::get(boost::vertex_name, v1) < boost::get(boost::vertex_name, v2); } };
#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
struct ordered_set_by_nameS { }; namespace boost {
template <class ValueType> struct container_gen<ordered_set_by_nameS, ValueType> { typedef std::set<ValueType, order_by_name<ValueType> > type;
}; } #else
struct ordered_set_by_nameS {
template <class T> struct bind_ { typedef std::multiset<T, order_by_name<T> > type; };
};
namespace boost {
template <> struct container_selector<ordered_set_by_nameS> { typedef ordered_set_by_nameS type;
}; } #endif
Hi! I get a graph from graphviz data. I would like to pick up one node and compute all the distance(number of edge) from this node to the others. My graph is undirected and unvaluated. I have wrote a function but I get wrong results: The graph: 0 <--> 1 1 <--> 0 2 2 <--> 1 3 4 5 3 <--> 2 4 <--> 2 5 <--> 2 6 7 6 <--> 5 7 <--> 5 the distance from 0: 2 3 4 3 3 5 4 4 parent[0] = 1 parent[1] = 2 parent[2] = 5 parent[3] = 2 parent[4] = 2 parent[5] = 7 parent[6] = 5 parent[7] = 5 Here is my code: std::vector<Vertex> p(boost::num_vertices(g)); boost::graph_traits<GraphvizGraph>::vertices_size_type d[num_vertices(g)]; std::fill_n(d, num_vertices (g), 0); breadth_first_search (g, u, visitor(make_bfs_visitor (std::make_pair(record_predecessors(&p[0],on_examine_edge()),record_distanc= es(&d[0],on_examine_edge())))) ); do you see something wrong? regards /Jérémie
Hi
Here is my code: std::vector<Vertex> p(boost::num_vertices(g)); boost::graph_traits<GraphvizGraph>::vertices_size_type d[num_vertices(g)];
std::fill_n(d, num_vertices (g), 0); breadth_first_search (g, u, visitor(make_bfs_visitor (std::make_pair(record_predecessors(&p[0],on_examine_edge()),record_d
istanc= es(&d[0],on_examine_edge())))) );
You are using on_examine_edge event, use on_tree_edge instead. Regards -- Janusz Piwowarski
participants (4)
-
dmatt001 -
Janusz Piwowarski -
Jeremie