Unable to call boost::clear_vertex while using listS for the vertex and edge lists
Date : November 29 2020, 04:01 AM
|
I think the issue was by ths following , You're running into iterator debugging checks from MSVC. That's GOOD because otherwise you might not know about it and your program would have (silent?) Undefined Behaviour. Now let me look at the code. double minEdgeWeight =
subGraph[*out_edges(u, subGraph).first].weight; // initialize minEdgeWeight to weight of first out edge
/home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:82:30: runtime error: load of value 3200171710, which is not a valid value for type 'boost::default_color_type'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:82:30 in
/home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:83:13: runtime error: load of value 3200171710, which is not a valid value for type 'ColorValue' (aka 'boost::default_color_type')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:83:13 in
/home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:87:15: runtime error: load of value 3200171710, which is not a valid value for type 'ColorValue' (aka 'boost::default_color_type')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:87:15 in
sotest: /home/sehe/custom/boost_1_67_0/boost/graph/two_bit_color_map.hpp:86: void boost::put(const two_bit_color_map<IndexMap> &, typename property_traits<IndexMap>::key_type, boost::two_bit_color_type) [IndexMap = boost::associative_property_map<std::map<void *, unsigned long, std::less<void *>, std::allocator<std::pair<void *const, unsigned long> > > >]: Assertion `(std::size_t)i < pm.n' failed.
struct VertexData {
vertex_descriptor pred;
double dist = 0, dist2 = 0;
boost::default_color_type color = {};
};
msth(msth.vertex(2));
vertex_descriptor vertex(std::size_t n) const {
return boost::vertex(n, subGraph);
}
// Problem here; The problem has to do with removing vertices/edges and destabilizing the graph, thereby making
// it impossible to iterate through the graph
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iomanip>
#include <numeric>
typedef boost::adjacency_list_traits<boost::listS, boost::listS, boost::undirectedS>
GraphTraits; // to simplify the next definition
typedef GraphTraits::vertex_descriptor vertex_descriptor; // vertex descriptor for the graph
typedef GraphTraits::edge_descriptor edge_descriptor; // edge descriptor for the graph
typedef double Weight;
struct VertexData {
std::string name;
VertexData(std::string name = "") : name(std::move(name)) {}
//
vertex_descriptor pred {};
Weight dist = 0, dist2 = 0;
boost::default_color_type color = {};
friend std::ostream& operator<<(std::ostream &os, VertexData const &vd) {
return os << "{name:" << std::quoted(vd.name) << "}";
}
};
struct EdgeData {
Weight weight = 1;
};
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, VertexData, EdgeData>
MyGraphType; // graph type
class MST_Heuristic : public boost::astar_heuristic<MyGraphType, Weight> {
struct do_nothing_dijkstra_visitor : boost::default_dijkstra_visitor {};
auto make_index() const {
std::map<vertex_descriptor, size_t> m;
size_t n=0;
for (auto vd : boost::make_iterator_range(vertices(subGraph)))
m[vd] = n++;
return m;
}
public:
MST_Heuristic(MyGraphType g) : subGraph(g), firstRun(true) {}
Weight operator()(vertex_descriptor u) {
if (firstRun) {
auto idx = make_index();
dijkstra_shortest_paths(
subGraph, u,
get(&VertexData::pred, subGraph), // calculate the shortest path from the start for each vertex
get(&VertexData::dist2, subGraph),
get(&EdgeData::weight, subGraph),
boost::make_assoc_property_map(idx), std::less<Weight>(),
std::plus<Weight>(), std::numeric_limits<Weight>::infinity(), 0, do_nothing_dijkstra_visitor(),
get(&VertexData::color, subGraph));
}
Weight minEdgeWeight = std::numeric_limits<Weight>::max(); // initialize minEdgeWeight to weight of first out edge
for (auto ed : make_iterator_range(out_edges(u, subGraph))) {
minEdgeWeight = std::min(subGraph[ed].weight, minEdgeWeight); // find distance from nearest unvisited vertex to the current vertex
}
clear_vertex(u, subGraph);
remove_vertex(u, subGraph);
{
auto idx = make_index();
prim_minimum_spanning_tree(subGraph, vertex(0), // calculate the minimum spanning tree
get(&VertexData::pred, subGraph), get(&VertexData::dist, subGraph),
get(&EdgeData::weight, subGraph), boost::make_assoc_property_map(idx),
do_nothing_dijkstra_visitor());
}
//// combine
Weight MSTDist = 0.0;
Weight startDist = std::numeric_limits<Weight>::infinity();
for (auto vd : boost::make_iterator_range(vertices(subGraph))) // estimate distance to travel all the unvisited vertices
{
MSTDist += subGraph[vd].dist;
startDist = std::min(startDist, subGraph[vd].dist2);
}
firstRun = false;
return minEdgeWeight + MSTDist + startDist; // return the result of the heuristic function
}
vertex_descriptor vertex(std::size_t n) const {
return boost::vertex(n, subGraph);
}
private:
MyGraphType subGraph;
bool firstRun;
};
int main() {
MyGraphType g;
auto v1 = add_vertex({"one"}, g);
auto v2 = add_vertex({"two"}, g);
auto v3 = add_vertex({"three"}, g);
auto v4 = add_vertex({"four"}, g);
auto v5 = add_vertex({"five"}, g);
add_edge(v1, v2, g);
add_edge(v2, v3, g);
add_edge(v3, v4, g);
add_edge(v4, v5, g);
print_graph(g, get(&VertexData::name, g));
MST_Heuristic msth(g);
msth(msth.vertex(2));
}
one <--> two
two <--> one three
three <--> two four
four <--> three five
five <--> four
Boards Message : |
You Must Login
Or Sign Up
to Add Your Comments . |
Share :
|
Why can't I use boost graph write_graphviz with OutEdgeList=listS and VertexList=listS
Date : March 29 2020, 07:55 AM
I wish this help you write_graphviz needs the vertex_id property to display vertex identifier labels. An adjacency_list that uses listS as the vertex container does not automatically provide this vertex_id property. This behavior makes sense, because in a linked list, there is no such thing as a key or index that can be used to uniquely identify an element. Remember that a linked list is neither a random-access sequence, nor an associative container. You'll either have to supply your own vertex_id property getter, or use a vertex container that has an inherent vertex_id property.
|
How to create a PropertyMap for a boost graph using listS as vertex container?
Date : March 29 2020, 07:55 AM
I hope this helps you . I have a boost graph defined as , Works! typedef boost::adjacency_list
<boost::setS, boost::listS,
boost::undirectedS,
boost::no_property,
boost::no_property> Graph;
typedef boost::graph_traits<Graph>::vertex_iterator VertexIterator;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDesc;
typedef std::map<VertexDesc, size_t> VertexDescMap;
Graph graph;
...
VertexDescMap idxMap;
boost::associative_property_map<VertexDescMap> indexMap(idxMap);
VertexIterator di, dj;
boost::tie(di, dj) = boost::vertices(_graph);
for(int i = 0; di != dj; ++di,++i){
boost::put(indexMap, (*di), i);
}
std::map<VertexDesc, size_t> compMap;
boost::associative_property_map<VertexDescMap> componentMap(compMap);
boost::associative_property_map<VertexDescMap>& componentMap;
boost::connected_components(_graph, componentMap, boost::vertex_index_map(indexMap));
|
in boost graph lib, how do I get a specific out-edge of a vertex without iterating over all the out-edges of that vertex
Date : March 29 2020, 07:55 AM
I think the issue was by ths following , Let's say I have a graph, with edges each containing a char. From a vertex, I want to get a specific out-edge with a specific char. Since the edge container can be set to a set or a hash-set, I assume there is a way to do this without iterating through the vertex's out-edges. I'm also assuming/hoping the edge container is keyed on the type the edge contains. , Are you looking for how to use edge descriptors? Edge i_edge = add_edge(currentVertex, endVertex, 'i', g).first;
// later...
// Now I want that edge containing the letter 'i'.
char yougotit = g[i_edge];
assert('i' == yougotit);
#include <boost/graph/adjacency_list.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <iostream>
using namespace boost::adaptors;
using namespace boost;
typedef boost::adjacency_list<setS, vecS, directedS, std::string, char> MyGraph;
typedef boost::graph_traits<MyGraph>::vertex_descriptor Vertex;
typedef boost::graph_traits<MyGraph>::edge_descriptor Edge;
int main() {
MyGraph g;
// setup
add_vertex(std::string("xxx"), g);
Vertex currentVertex = g.vertex_set()[0];
Vertex endVertex = add_vertex(std::string("yyy"), g);
add_edge(currentVertex, endVertex, 'i', g);
for (auto matching : boost::edges(g) | filtered([&g](auto const& e) { return g[e] == 'i'; }))
std::cout << matching << " --> " << g[matching] << "\n";
}
(0,1) --> i
|
Find connected components using Boost Graph library, with the vertex and edge type being boost::listS
Tag : cpp , By : Keonne Rodriguez
Date : March 29 2020, 07:55 AM
will be helpful for those in need The docs say¹ the component map needs to model a writable property map with key vertex_descriptor and storing the compoment id as value. You should probably use make_assoc_property_map with a map: std::map<Cluster::vertex_descriptor, int> subclusters;
int nclusters = boost::connected_components(A, boost::make_assoc_property_map(subclusters)); // find the connected components
for (auto& p : subclusters) {
std::cout << "Vertex " << boost::get(boost::vertex_index, A, p.first) << " is in cluster " << p.second << "\n";
}
0 -- 1
0 -- 2
1 -- 2
Vertex 0 is in cluster 0
Vertex 1 is in cluster 0
Vertex 2 is in cluster 0
Vertex 3 is in cluster 1
typedef boost::adjacency_list<
boost::listS,
boost::listS,
boost::undirectedS,
boost::property<boost::vertex_index_t, int>
> Cluster;
Cluster A;
add_vertex(0, A);
add_vertex(1, A);
add_vertex(2, A);
add_vertex(3, A);
std::vector<int> subclusters(4);
auto comp_map = make_iterator_property_map(subclusters.begin(), get(boost::vertex_index, A));
int nclusters = connected_components(A, comp_map); // find the connected components
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <iostream>
typedef boost::adjacency_list<
boost::listS,
boost::listS,
boost::undirectedS,
boost::property<boost::vertex_index_t, int>
> Cluster;
int main() {
Cluster A;
add_vertex(0, A);
add_vertex(1, A);
add_vertex(2, A);
add_vertex(3, A);
for (int i = 0; i < 2; i++) {
for (int j = (i + 1); j < 3; j++) {
std::cout << i << " -- " << j << "\n";
add_edge(vertex(i, A), vertex(j, A), A);
}
} // add edge between 0-1, 0-2, 1-2.
// NOTE: 4, not "num_vertices", but enough to accomodate the highest value
// of the `vertex_index` property
std::vector<int> subclusters(4);
auto comp_map = make_iterator_property_map(subclusters.begin(), get(boost::vertex_index, A));
int nclusters = connected_components(A, comp_map); // find the connected components
for (size_t id = 0; id < subclusters.size(); ++id) {
std::cout << "Vertex id " << id << " is in cluster " << subclusters.at(id) << "\n";
}
}
0 -- 1
0 -- 2
1 -- 2
Vertex id 0 is in cluster 0
Vertex id 1 is in cluster 0
Vertex id 2 is in cluster 0
Vertex id 3 is in cluster 1
|
How to use boost::graph algorithms with listS, setS as vertex/edge containers?
Date : March 29 2020, 07:55 AM
|
|
|
Related QUESTIONS :
|