c++ - ブースト グラフを union_set できません

Question

この質問は次のように接続されています:デカルト ポイントでブースト接続コンポーネントを使用する

デカルト ポイントを使用するために、例にいくつかの変更を加えました。これが私の現在のコードです：

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(): Access violation reading location... しようとすると例外が発生します...理由がわかりません。ブーストライブラリに関するすべてのトピックを読み、ドキュメントを検索しようとしました。

Answer 1

このチュートリアルのおかげでそれを理解しました：1つの頂点に接続されたすべてのエッジと頂点を選択するためのアルゴリズム

問題は次のとおりです。

• 最初にいくつかの頂点でベクトルを初期化しました（例からコピーして貼り付け、変更するのは最善の考えではありませんでした）
• チュートリアルが言うように、「graph[ a VertexID ] は Vertex を与えるが、graph[ an EdgeID ] は Edge を与えることに注意してください」
• いくつかの頂点を追加した後、ばらばらなセットを初期化する必要があります

作業コード:

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;
}

私はまだブーストグラフを学んでいるので、私の間違いを修正して、よりエレガントなソリューションを作ってください。私の結論も正確ではない可能性があります。