加速图形无法union_set

Question

这个问题与连接：Using boost connected components with cartesian points

我做了例如在一些改变使用笛卡尔点。这里是我当前的代码：

using namespace boost; 
typedef adjacency_list <vecS, vecS, undirectedS, cv::Point> Graph; 
typedef graph_traits<Graph>::vertex_descriptor Vertex; 
typedef graph_traits<Graph>::vertices_size_type VertexIndex; 

int main() 
{ 
    const int VERTEX_COUNT = 10; 
    Graph graph(VERTEX_COUNT); 

    std::vector<VertexIndex> rank(num_vertices(graph)); 
    std::vector<Vertex> parent(num_vertices(graph)); 

    typedef VertexIndex* Rank; 
    typedef Vertex* Parent; 

    disjoint_sets<Rank,Parent> ds(&rank[0], &parent[0]); 

    initialize_incremental_components(graph,ds); 
    incremental_components(graph,ds); 

    graph_traits<Graph>::edge_descriptor edge; 
    bool flag; 

    std::vector<Vertex> verticesVector; 
    //vector of points which creates graph 
    std::vector<cv::Point> points; 

    points.push_back(cv::Point(0,0)); 
    points.push_back(cv::Point(1,1)); 
    points.push_back(cv::Point(2,2)); 
    points.push_back(cv::Point(3,1)); 
    points.push_back(cv::Point(4,2)); 
    points.push_back(cv::Point(0,2)); 
    points.push_back(cv::Point(2,3)); 
    points.push_back(cv::Point(3,3)); 

    int i = 0; 
    for(std::vector<cv::Point>::iterator it = points.begin(); 
      it !=points.end();it++, i++) 
    { 
     verticesVector.push_back(add_vertex(graph)); 
     graph[i].x = (*it).x; 
     graph[i].y = (*it).y; 
    } 

    typedef component_index<VertexIndex> Components; 
    Components components(parent.begin(), parent.end()); 

    BOOST_FOREACH(VertexIndex current_index, components) 
    { 
     std::cout<<"component "<<current_index<<" contains: "; 
     BOOST_FOREACH(VertexIndex child_index, components[current_index]) 
     { 
      std::cout<<child_index<<" "<<" x = "<<graph[current_index].x<<";"<<graph[current_index].y<<"||"; 
     } 
     std::cout<<std::endl; 
    } 

    boost::tie(edge,flag) = add_edge(verticesVector[0],verticesVector[1],graph); 
    ds.union_set(verticesVector[0],verticesVector[1]); 
    boost::tie(edge,flag) = add_edge(verticesVector[1],verticesVector[2],graph); 
    ds.union_set(verticesVector[1],verticesVector[2]); 
    boost::tie(edge,flag) = add_edge(verticesVector[2],verticesVector[3],graph); 
    ds.union_set(verticesVector[2],verticesVector[3]); 
    boost::tie(edge,flag) = add_edge(verticesVector[3],verticesVector[4],graph); 
    ds.union_set(verticesVector[3],verticesVector[4]); 
    boost::tie(edge,flag) = add_edge(verticesVector[1],verticesVector[5],graph); 
    ds.union_set(verticesVector[1],verticesVector[5]); 
    boost::tie(edge,flag) = add_edge(verticesVector[5],verticesVector[6],graph); 
    ds.union_set(verticesVector[5],verticesVector[6]); 
    boost::tie(edge,flag) = add_edge(verticesVector[6],verticesVector[7],graph); 
    ds.union_set(verticesVector[6],verticesVector[7]); 

    Components components2(parent.begin(), parent.end()); 


    /*BOOST_FOREACH(Vertex current_vertex, vertices(graph)) 
    { 
     std::cout<< "representative["<<current_vertex<<"] = " 
     << ds.find_set(current_vertex)<<std::endl; 
    } 

    std::cout<<std::endl;*/ 

    for(std::vector<Vertex>::iterator it = verticesVector.begin(); it != verticesVector.end(); it++) 
    { 
     std::cout<<"representative = "<<ds.find_set((*it))<<std::endl; 
    } 

    BOOST_FOREACH(VertexIndex current_index, components2) 
    { 
     std::cout<<"component "<<current_index<<" contains: "; 
     BOOST_FOREACH(VertexIndex child_index, components[current_index]) 
     { 
      std::cout<<child_index<<" "<<" x,y = "<<graph[current_index].x<<";"<<graph[current_index].y<<"||"; 
     } 
     std::cout<<std::endl; 
    } 

    //write_graphviz(std::cout, graph); 

    getchar(); 
    return 0; 
} 

当试图union_set（）我得到异常：访问冲突读取位置... 我想不通的原因。我已经阅读了关于boost lib的所有主题，试图在文档中进行搜索。

Answer 1

我已经想通了感谢这个教程：Algorithm for selecting all edges and vertices connected to one vertex

的问题是：

• 我与一些顶点首先初始化向量（复制粘贴由例如和修改并不好主意）
• 作为教程说“请注意，图表[A VertexID]给出一个顶点，但图[一EdgeID的]给出的边缘”
• 分离集应该初始化加入一些顶点后

工作代码：

using namespace boost; 

typedef adjacency_list <vecS, vecS, undirectedS, cv::Point> Graph; 
typedef graph_traits<Graph>::vertex_descriptor Vertex; 
typedef graph_traits<Graph>::vertices_size_type VertexIndex; 

int main() 
{ 
    Graph graph; 

    graph_traits<Graph>::edge_descriptor edge; 
    bool flag; 

    std::vector<Vertex> verticesVector; 
    Vertex verticesTable[8]; 
    std::vector<cv::Point> points; 

    points.push_back(cv::Point(0,0)); 
    points.push_back(cv::Point(1,1)); 
    points.push_back(cv::Point(2,2)); 
    points.push_back(cv::Point(3,1)); 
    points.push_back(cv::Point(4,2)); 
    points.push_back(cv::Point(0,2)); 
    points.push_back(cv::Point(2,3)); 
    points.push_back(cv::Point(3,3)); 

    int i = 0; 
    for(std::vector<cv::Point>::iterator it = points.begin(); it != points.end(); it++, i++) 
    { 
     verticesTable[i] = add_vertex(graph); 
     graph[verticesTable[i]].x = (*it).x; 
     graph[verticesTable[i]].y = (*it).y; 
    } 

    std::vector<VertexIndex> rank(num_vertices(graph)); 
    std::vector<Vertex> parent(num_vertices(graph)); 

    typedef VertexIndex* Rank; 
    typedef Vertex* Parent; 

    disjoint_sets<Rank,Parent> ds(&rank[0], &parent[0]); 

    initialize_incremental_components(graph,ds); 
    incremental_components(graph,ds); 

    typedef component_index<VertexIndex> Components; 
    Components components(parent.begin(), parent.end()); 

    Graph::vertex_iterator vertexIt, vertexEnd; 
    boost::tie(vertexIt,vertexEnd) = vertices(graph); 
    for(;vertexIt != vertexEnd; ++vertexIt) 
    { 
     Vertex a = *vertexIt; 
     cv::Point &b = graph[a]; 
     std::cout<<"Point: "<<b.x<<";"<<b.y<<std::endl; 
    } 

    boost::tie(edge,flag) = add_edge(verticesTable[0],verticesTable[1],graph); 
    ds.union_set(verticesTable[0],verticesTable[1]); 
    boost::tie(edge,flag) = add_edge(verticesTable[1],verticesTable[2],graph); 
    ds.union_set(verticesTable[1],verticesTable[2]); 
    //boost::tie(edge,flag) = add_edge(verticesTable[2],verticesTable[3],graph); 
    //ds.union_set(verticesTable[2],verticesTable[3]); 
    boost::tie(edge,flag) = add_edge(verticesTable[3],verticesTable[4],graph); 
    ds.union_set(verticesTable[3],verticesTable[4]); 
    boost::tie(edge,flag) = add_edge(verticesTable[1],verticesTable[5],graph); 
    ds.union_set(verticesTable[1],verticesTable[5]); 
    boost::tie(edge,flag) = add_edge(verticesTable[5],verticesTable[6],graph); 
    ds.union_set(verticesTable[5],verticesTable[6]); 
    boost::tie(edge,flag) = add_edge(verticesTable[6],verticesTable[7],graph); 
    ds.union_set(verticesTable[6],verticesTable[7]); 

    BOOST_FOREACH(Vertex current_vertex, vertices(graph)) 
    { 
     std::cout<< "representative["<<current_vertex<<"] = " 
     << ds.find_set(current_vertex)<<std::endl; 
    } 

    std::cout<<std::endl; 

    Components components2(parent.begin(), parent.end()); 

    BOOST_FOREACH(VertexIndex current_index, components2) 
    { 
     std::cout<<"component "<<current_index<<" contains: "; 
     BOOST_FOREACH(VertexIndex child_index, components2[current_index]) 
     { 
       std::cout<<child_index<<" "<<" x,y = "<<graph[verticesTable[child_index]].x<<";"<<graph[verticesTable[child_index]].y<<"||"; 
     } 
     std::cout<<std::endl; 
    } 

    //write_graphviz(std::cout, graph); 

    getchar(); 

    return 0; 
} 

我还在学习提升图形，所以请纠正我的错误，让更多的优雅的解决方案。 我的结论也可能不完全正确。