c – 更改相邻顶点的值并删除自循环

发布时间：2020-12-16 07:08:56 所属栏目：百科来源：网络整理

导读：尝试使用boost :: graph编写一个 Karger’s algorithm 示例(第一列是顶点,其他是相邻顶点)： 1 2 3 2 1 3 4 3 1 2 4 4 2 3 假设我merge 2比1,我得到了结果 1 2 3 2 1 1 3 4 2 1 3 4 3 1 2 4 4 2 3 第一个问题：如何更改顶点1的相邻顶点(“2”到“1”)？我天

尝试使用boost :: graph编写一个 Karger’s algorithm

示例(第一列是顶点,其他是相邻顶点)：

> 1 2 3
> 2 1 3 4
> 3 1 2 4
> 4 2 3

假设我merge 2比1,我得到了结果

> 1 2 3 2 1 1 3 4
> 2 1 3 4
> 3 1 2 4
> 4 2 3

第一个问题：如何更改顶点1的相邻顶点(“2”到“1”)？

我天真的解决方案

template<typename Vertex,typename Graph>
void change_adjacent_vertices_value(Vertex input,Vertex value,Graph &g)
{
    for (auto it = boost::adjacent_vertices(input,g);
         it.first != it.second; ++it.first){
        if(*it.first == value){
            *(it.first) = input; //error C2106: '=' : left operand must be l-value
        }
    }
}

显然,我不能通过这种方式将相邻顶点的值设置为“1”

“change_adjacent_vertices_value”后我想要的结果

> 1 1 3 1 1 1 3 4
> 2 1 3 4
> 3 1 2 4
> 4 2 3

第二个问题：我怎么能弹出相邻的顶点？

假设我想从顶点1中弹出连续的1
我期待的结果

> 1 1 3 1 3 4
> 2 1 3 4
> 3 1 2 4
> 4 2 3

像“pop_adjacent_vertex”这样的任何函数都可以使用？

解决方法

首先,在大多数情况下,图形顶点描述符只是一个整数或指针.这意味着代码中的分配不会更改图形.

相反,你应该使用Mutable Graph：http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/MutableGraph.html概念中的API

在您的情况下,代码可能如下所示：

///adds all edges from src to target and removes the vertex src from the graph
template<typename Vertex,typename Graph>
void merge_vertices(Vertex src,Vertex tgt,Graph &g)
{
    for (auto it = boost::out_edges(src,g);
         it.first != it.second; ++it.first)
    {
        Vertex u = target(*it.first,g);
        add_edge(u,tgt,g); 
        //Note,if edges have properties,you should extract and copy them as well
    }
    clear_vertex(src,g);  //removes all edges to/from "src"
    remove_vertex(src,g); //removes vertex src itself
}

为了避免混淆,我建议使用图形,当删除边或顶点时,顶点和边描述符不会失效.

它导致以下测试示例：

typedef boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS > graph_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;

int main(int,char**)
{
    typedef std::map<vertex_t,size_t> IndexMap;
    IndexMap mapIndex;

    graph_t g;
    vertex_t v0 = add_vertex(g);
    mapIndex[v0]=0;
    vertex_t v1 = add_vertex(g);
    mapIndex[v1]=1;
    vertex_t v2 = add_vertex(g);
    mapIndex[v2]=2;
    vertex_t v3 = add_vertex(g);
    mapIndex[v3]=3;

    add_edge(v0,v2,g);
    add_edge(v1,v3,v0,g);
    std::cout << "Before merging " << std::endl;
    boost::print_graph(g,boost::make_assoc_property_map(mapIndex));

    merge_vertices(v1,g);
    std::cout << "After merging "<< std::endl;

    boost::print_graph(g,boost::make_assoc_property_map(mapIndex));;
}

结果：

Before merging 
0 <--> 2 1 
1 <--> 3 0 
2 <--> 0 
3 <--> 1 
After merging 
0 <--> 2 2 
2 <--> 0 3 0 
3 <--> 2

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!