jjzjj

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

coder 2024-02-25 原文

试着写一个Karger’s algorithm与 boost::图表

示例(第一列为顶点，其他为相邻顶点):

  • 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”这样的函数吗？

最佳答案

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

相反，您应该使用来自可变图概念的 API:http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/MutableGraph.html

在您的情况下，代码可能如下所示:

///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,g);
    add_edge(v1,v0,g);
    std::cout << "Before merging " << std::endl;
    boost::print_graph(g, boost::make_assoc_property_map(mapIndex));

    merge_vertices(v1,v2,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

关于c++ - 更改相邻顶点的值并删除自循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23976339/

相邻ampvertexboostlic++algorithmboost-graph

有关c++ - 更改相邻顶点的值并删除自循环的更多相关文章

  1. ruby-on-rails - Ruby on Rails 迁移，将表更改为 MyISAM - 2

    如何正确创建Rails迁移，以便将表更改为MySQL中的MyISAM？目前是InnoDB。运行原始执行语句会更改表，但它不会更新db/schema.rb，因此当在测试环境中重新创建表时，它会返回到InnoDB并且我的全文搜索失败。我如何着手更改/添加迁移，以便将现有表修改为MyISAM并更新schema.rb，以便我的数据库和相应的测试数据库得到相应更新？ 最佳答案 我没有找到执行此操作的好方法。您可以像有人建议的那样更改您的schema.rb，然后运行:rakedb:schema:load，但是，这将覆盖您的数据。我的做法是(假设

  2. ruby - 树顶语法无限循环 - 2

    我脑子里浮现出一些关于一种新编程语言的想法，所以我想我会尝试实现它。一位friend建议我尝试使用Treetop(Rubygem)来创建一个解析器。Treetop的文档很少，我以前从未做过这种事情。我的解析器表现得好像有一个无限循环，但没有堆栈跟踪；事实证明很难追踪到。有人可以指出入门级解析/AST指南的方向吗？我真的需要一些列出规则、常见用法等的东西来使用像Treetop这样的工具。我的语法分析器在GitHub上，以防有人希望帮助我改进它。class{initialize=lambda(name){receiver.name=name}greet=lambda{IO.puts("He

  3. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  4. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  5. ruby - 我可以使用 Ruby 从 CSV 中删除列吗？ - 2

    查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html

  6. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  7. ruby - 我可以使用 aws-sdk-ruby 在 AWS S3 上使用事务性文件删除/上传吗？ - 2

    我发现ActiveRecord::Base.transaction在复杂方法中非常有效。我想知道是否可以在如下事务中从AWSS3上传/删除文件:S3Object.transactiondo#writeintofiles#raiseanexceptionend引发异常后，每个操作都应在S3上回滚。S3Object这可能吗？？ 最佳答案 虽然S3API具有批量删除功能，但它不支持事务，因为每个删除操作都可以独立于其他操作成功/失败。该API不提供任何批量上传功能(通过PUT或POST)，因此每个上传操作都是通过一个独立的API调用完成的

  8. ruby-on-rails - 项目升级后 Pow 不会更改 ruby​​ 版本 - 2

    我在我的Rails项目中使用Pow和powifygem。现在我尝试升级我的ruby​​版本(从1.9.3到2.0.0，我使用RVM)当我切换ruby​​版本、安装所有gem依赖项时，我通过运行railss并访问localhost:3000确保该应用程序正常运行以前，我通过使用pow访问http://my_app.dev来浏览我的应用程序。升级后，由于错误Bundler::RubyVersionMismatch:YourRubyversionis1.9.3,butyourGemfilespecified2.0.0，此url不起作用我尝试过的:重新创建pow应用程序重启pow服务器更新战俘

  9. ruby - Capistrano 3 在任务中更改 ssh_options - 2

    我尝试使用不同的ssh_options在同一阶段运行capistranov.3任务。我的production.rb说:set:stage,:productionset:user,'deploy'set:ssh_options,{user:'deploy'}通过此配置，capistrano与用户deploy连接，这对于其余的任务是正确的。但是我需要将它连接到服务器中配置良好的an_other_user以完成一项特定任务。然后我的食谱说:...taskswithoriginaluser...task:my_task_with_an_other_userdoset:user,'an_othe

  10. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

随机推荐