如何获得升压图中顶点的MAX级别（深度） [英] How to get the MAX level(depth) of a vertex in a boost graph

问题描述

一般来说，我是新增的图表和图论。事实上，我对图算法术语的有限知识正在让我感到困难。无论如何，这是我正在尝试做的。

我正在使用 boost :: adjacency_list ，假设我有一个顶点

  struct Node {
 int level; 
 
 $ / code> 

现在我构建了一个完整的图并且我想要找到每个图的等级节点。对我来说，级别意味着从根节点的最大深度。例如考虑图（假设118是根节点）



  118  - > 122 
 118  - > 120 
 122  - > 120 
 122  - > 121 
 121  - > 125 
 121  - > 123 
 123  - > 125 
 125  - > 124 
  

那么 122的等级是1,120是2,121是2 ，123是3,125是4，而124是5 。



在boost中有没有算法可以让我这么做。我敢打赌，它是 boost :: bredth_first_visit 。但我不确定如何正确使用它，以便在访问时将正确的值放入 Node.level 中。

我在类似的问题上发现了另一篇关于堆栈溢出的帖子，这是一种解决方案（它不是为我编译的）。

  typedef boost :: property_map< TaskGraph，boost :: vertex_color_t> :: type color_map_t; 
 color_map_t colorMap; //创建一个颜色映射
 boost :: breadth_first_visit（graph，* boost :: vertices（graph）.first，boost :: color_map（colorMap））; 
  

我想要做的是类似于

  boost :: breadth_first_visit（graph，* boost :: vertices（graph）.first，/ *这里是什么让Node.level得到关卡* /）; 
  

感谢您对术语的帮助和抱歉。不知道 level 是否是图论中的正确术语。

解决方案

查看 Dijkstra算法。
没有简单的方法来做到这一点，boost :: breadth_first_visit将遍历每个节点，但请记住，您仍然必须计算水平，我将其称为成本。

假设你有这张图：

  a-> b 
 b- > c 
 a-> c 
  

什么是C的等级两个或三个？在这里你可能会想用成本这个词来代替。在这种情况下，最低成本选项为2.在这种情况下，如果每个C有两个父指针，则需要遍历每个父指针，以递归方式备份起始节点，从而增加成本。

看起来像这样：

  cost = 1 
 c-> b 
 cost = 2 
 b-> a 
 cost = 3 
 c-> a 
 cost = 2 
  

I am new to boost graphs and graph theory in general. As it happens my limited knowledge on terminology of graph algorithms is making things difficult for me. Anyways here is what I am trying to do.

I am using boost::adjacency_list and let's say I have a vertex

struct Node {
    int level;
}

Now I have a whole graph constructed and I want to find the level of each node. Level for me means here the maximum depth of a node from the root. For example consider the graph (assuming 118 is the root node)

118 -> 122
118 -> 120
122 -> 120
122 -> 121
121 -> 125
121 -> 123
123 -> 125
125 -> 124

then level of 122 is 1, 120 is 2, 121 is 2, 123 is 3, 125 is 4, and 124 is 5.

Is there any algorithm in boost that lets me do this. My bet is that it is boost::bredth_first_visit. But I am not sure how to use it correctly so that it puts the correct values in Node.level while visiting.

I found another post on stack overflow on similar issue and this was kind of the solution (it is not compiling for me.)

typedef boost::property_map<TaskGraph, boost::vertex_color_t>::type color_map_t;
color_map_t colorMap; //Create a color map
boost::breadth_first_visit(graph, *boost::vertices(graph).first, boost::color_map(colorMap));

What I want to do is something like

boost::breadth_first_visit(graph, *boost::vertices(graph).first, /*What goes here so that Node.level gets the level*/);

Thanks for the help and sorry for the terminology. Not sure if level is the correct term in graph theory.

解决方案

Take a look at Dijkstra's Algorithm. There is no simple way to do this, boost::breadth_first_visit will traverse every node, but keep in mind you will still have to calculate the "levels" which I will refer to as costs.

Say you have this graph:

   a->b
   b->c
   a->c

What is the "level" of C, two or three? Here you would probably want to use the term "cost" instead. Here, the least cost option is 2. In this case, if each C has two parent pointers, you need to traverse each parent pointer recursively back up the the starting node, incrementing your cost along the way.

That would look like this:

   cost=1
   c->b
       cost=2
       b->a
           cost=3 
   c->a
       cost=2

这篇关于如何获得升压图中顶点的MAX级别（深度）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！