logo
down
shadow

Unable to call boost::clear_vertex while using listS for the vertex and edge lists


Unable to call boost::clear_vertex while using listS for the vertex and edge lists

Content Index :

Unable to call boost::clear_vertex while using listS for the vertex and edge lists
Tag : cpp , By : Kenny
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 

Comments
No Comments Right Now !

Boards Message :
You Must Login Or Sign Up to Add Your Comments .

Share : facebook icon twitter icon

Why can't I use boost graph write_graphviz with OutEdgeList=listS and VertexList=listS


Tag : development , By : Nate Bedortha
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?


Tag : development , By : Jojo
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


Tag : cpp , By : Kyle
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?


Tag : cpp , By : MP.
Date : March 29 2020, 07:55 AM
Related Posts Related QUESTIONS :
  • Could this publish / check-for-update class for a single writer + reader use memory_order_relaxed or acquire/release for
  • Passing a function identifier as an rvalue reference and applying std::move() to it
  • The conditional operator is not allowing the program to terminate
  • Define a c++ string as "\"
  • memcpy on __declspec naked returns unexpected bytes
  • What is the proper way to link enums with CMake?
  • is it safe to use the same mutex with lock_gard and without it in other parts of code
  • How to decode MAP Invoke messages using asn1c generated code
  • How do you write multiple lines in a .txt with recursion?
  • Member function with strange type causing callback function mismatch
  • Visual Studio optimisations break SDL graphical output
  • How to use less memory in Sieve_of_Eratosthenes
  • Covariance in Callback Parameters C++
  • switch may fall through (no it may not)
  • Compilation fails calling Cocoa function from C++
  • How to handle classes with differently named member functions in algorithms?
  • Convert QString to QJsonArray
  • Data exchange finished in CPropertyPage::OnOK?
  • Template member specialization in template class
  • Is it not possible to assign a struct to an index of a vector?
  • Why is empty unordered_map.find not returning end()?
  • Template argument deduction for inheriting specializations
  • dlopen undefined reference
  • Member function of class with template arguments and default arguments outside class
  • Is it possible to implement a non-owning "slightly smart" pointer on top of standard weak pointers?
  • how to configure the AcquireCredentialsHandleA correctly
  • Using private versions of global extern variables with OpenMP
  • Eigen Block wrong amount of columns and rows
  • Memory alignment rules in inheritance
  • Is nullptr falsy?
  • tm_wday returns a large integer outside 0-6 range
  • Scope a using declaration, inside a header
  • How to specify constructor's template arguments inside a new expression?
  • Sort an array via x86 Assembly (embedded in C++)?? Possible?
  • How to Replace only Part of the Variable using #define
  • How do you compare the performace of valarrays vs built-in arrays?
  • Is it normal for C++ static initialization to appear twice in the same backtrace?
  • c++ generate a good random seed for psudo random number generators
  • Why isn't my operator overloading working properly?
  • Getting meaningful error messages from fstream's in C++
  • C++: Converting Julian dates to Gregorian
  • Could someone explain this interesting behaviour with Sleep(1)?
  • Is it possible to roll a significantly faster version of modf
  • Updating pointer using signals and slots
  • How are classes more secure than structures?
  • finding "distance" between two pixel's colors
  • C++ Greatest Number Verification
  • Why does my token return NULL and how can I fix it?(c++)
  • C++ enforce conditions on inherited classes
  • what happened if an exception is not captured?
  • Redundant naming in C/C++ typedefs/structs
  • question about STL thread-safe and STL debugging
  • killing a separate thread having a socket
  • Returning the size of available virtual memory at run-time in C++
  • Parallel computing for integrals
  • How do I force my std::map to deallocate memory used?
  • C++ Templates: implicit conversion, no matching function for call to ctor
  • Adding python script to c++ project
  • C++ private pointer "leaking"?
  • Initializing Primitive Array to One Value
  • shadow
    Privacy Policy - Terms - Contact Us © scrbit.com