找到给出BOOST图2顶点的多条边 [英] find multiple edges given 2 vertices in BOOST graph

问题描述

我使用Boost图库一些项目，我想找到的倍边缘在图中重复的次数。例如，

 的typedef的boost ::的adjacency_list＆LT;促进血管内皮细胞::，促进血管内皮细胞::，提振:: undirectedS，NODE_INFO，Edge_Info＆GT; Graph_t;
// NODE_INFO和Edge_info是外部节点和边缘性（结构）
 

想，如果我有两个节点，节点1和节点2并没有（节点，节点2）它们之间的边缘。对于每个边缘边缘属性包含时间戳开始，结束..和有可与不同的时间戳图许多这样的边缘。例如。

  EDGE1 =（节点，节点2）与启动= 100，终点= 200。
EDGE2 =（节点，节点2）与启动= 250，终点= 400。
 

我知道，在一个升压图形，给定两个顶点，我们可以找到一个边缘是否在图形或不使用下存在。

 的std ::对＆LT; edge_t，布尔＆GT; P =提振::边缘（节点1，节点，为MyGraph）;
如果（p.second == 1）的cout＆所述;＆下; 边缘存在！ ＆LT;＆LT; ENDL;
否则COUT＆LT;＆LT; 不存在＆所述;＆下; ENDL;
 

但是，这可能意味着，只会返回任何一个边缘，即使具有不同的边缘属性存在多个边缘 - >问题

任何人都可以提出一个想法如何得到两个特定点之间的这种多重边？谢谢！

解决方案

有几个方法可以做到这一点。

1）只是检查出边为所有到所需的目标：

 的boost :: graph_traits＆LT; Graph_t＆GT; :: out_edge_iterator EI，ei_end;
提高::领带（EI，ei_end）= out_edges（节点，为MyGraph）;
INT parallel_count = 0;
对于（; EI = ei_end;！++ EI）{
  如果（目标（* EI，为MyGraph）==节点2）{
    COUT＆LT;＆LT; 找到边缘（节点，节点2）财产：＆LT;＆LT;为MyGraph [* EI＆LT;＆LT; ENDL;
    ++ parallel_count;
  };
};
COUT＆LT;＆LT; ＆的LT，LT＆共有是; parallel_count＆LT;＆LT; 平行边缘。 ＆LT;＆LT; ENDL;
 

2）指定的boost ::多集为 OutEdgeListS 模板参数的adjacency_list ，这将使所谓的额外功能 edge_range 返回一系列迭代器为所有的水货的边缘走出来<$ C $的c>的U 键，进入 v ，为的documentation页状态：

 的std ::对＆LT; out_edge_iterator，out_edge_iterator＆GT;
edge_range（vertex_descriptor的U，vertex_descriptor的V，
           常量的adjacency_list＆安培; G）
 

  
  

返回一对出边迭代器，让范围从u到v的所有平行边。当为的adjacency_list的OutEdgeList是排序根据目标顶点出边的容器，此功能只适用，并允许对平行边。在多集选择选择这样的容器中。

之所以此功能仅适用于多集是因为，以提供（容易）的一系列迭代器平行边，则需要进行分组的边缘一起，这是多重集的情况下，因为它们是由顶点描述符进行排序，因此，所有的并行出边被分组在一起。这是唯一的容器的选择，这将使你这一点，否则，您必须使用选项（1）（注：创建一个 filter_iterator （见的docs ）可以派上用场，如果你真的使用这个有很多）。

I am using Boost Graph library for some project and i want to find number of times an edge is repeated in a graph. for example,

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Node_Info, Edge_Info > Graph_t;  
//node_info and Edge_info are external node and edge properties (structures)

suppose if i have two nodes, node1 and node2 and there is an edge between them (node1, node2). edge property for each edge contains a timestamp start, end.. and there can be many such edges in the graph with different timestamps. for example.

edge1 = (node1, node2) with start = 100, end = 200.
edge2 = (node1, node2) with start = 250, end = 400.

I know that in a boost graph, given two vertices, we can find whether an edge exists in the graph or not using the following.

std::pair < edge_t, bool > p = boost::edge( node1, node2, myGraph );
if(p.second == 1)  cout << "edge exists!" << endl;
else cout << " does not exist " << endl;

But this could mean that it would only return any one edge even if multiple edges exist with different edge properties --> PROBLEM

can anyone suggest an idea how to get such multiple edges between two given nodes? Thanks!

解决方案

There are a couple of ways to do this.

1) Just check the out-edges for all that go to the desired target:

boost::graph_traits<Graph_t>::out_edge_iterator ei, ei_end;
boost::tie(ei, ei_end) = out_edges( node1, myGraph );
int parallel_count = 0;
for( ; ei != ei_end; ++ei) {
  if( target(*ei, myGraph) == node2 ) {
    cout << "Found edge (node1, node2) with property: " << myGraph[*ei] << endl;
    ++parallel_count;
  };
};
cout << "There are a total of " << parallel_count << " parallel edges." << endl;

2) Specify boost::multisetS as the OutEdgeListS template argument to adjacency_list, this will enable an extra function called edge_range which returns a range of iterators for all the "parallel" edges coming out of u and going into v, as the documentation page states:

std::pair<out_edge_iterator, out_edge_iterator>
edge_range(vertex_descriptor u, vertex_descriptor v,
           const adjacency_list& g)

Returns a pair of out-edge iterators that give the range for all the parallel edges from u to v. This function only works when the OutEdgeList for the adjacency_list is a container that sorts the out edges according to target vertex, and allows for parallel edges. The multisetS selector chooses such a container.

The reason why this function is only available for multisetS is because in order to provide (easily) a range of iterators to parallel edges, you need the edges to be grouped together, which is the case for multisetS because they are sorted by vertex-descriptor, and therefore, all parallel out-edges are grouped together. That's the only container choice that will give you this, otherwise, you have to use option (1) (note: creating a filter_iterator (see docs) could come in handy if you really use this a lot).

这篇关于找到给出BOOST图2顶点的多条边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！