用于选择连接到一个顶点的所有边和顶点的算法

问题描述 投票:13回答:2

我正在使用Boost Graph来尝试理解我以Graphviz Dot格式生成的一些依赖图。

不幸的是,我对图论不是很了解,所以我很难用图论术语来表述我想知道的东西。

[从具有约150个顶点的有向依存关系图中,我想在一个特定顶点V上“放大”,并构建一个包含V,其所有传入边缘和其传入边缘,所有其导出边缘和其导出边缘的子图。边缘,有点像通过V的最长路径。

这些依赖关系图很纠结,所以我想消除混乱,使其更清楚什么可能影响所讨论的顶点。

例如,给定;

     g
     |
     v
a -> b -> c -> d
|    |         |
v    v         |
e    f <-------+

[如果我要在c上运行算法,我想我想;

     g
     |
     v
a -> b -> c -> d -> f

[不确定b-> f是否也应包括在内...我认为这是因为c之前”的所有顶点都应包含其边缘,而c之后“的所有顶点均应包含其边缘。 ,但在我看来,这将丢失一些信息。

感觉应该有一种算法可以做到这一点(或者更明智,不确定我是否要做一些愚蠢的事情,参见上面的b-> f),但是我不确定从哪里开始寻找。

谢谢!

c++ boost graph
2个回答
42
投票

好,我将翻译您的教程并将其适应您的特定问题。该文档始终假定大量“使用命名空间”;我什么也不会用,所以您知道什么。让我们开始:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>

首先,定义一个顶点和一个边缘:

struct Vertex{
    string name; // or whatever, maybe nothing
};
struct Edge{
    // nothing, probably. Or a weight, a distance, a direction, ...
};

创建类型或图形:

typedef boost::adjacency_list<  // adjacency_list is a template depending on :
    boost::listS,               //  The container used for egdes : here, std::list.
    boost::vecS,                //  The container used for vertices: here, std::vector.
    boost::directedS,           //  directed or undirected edges ?.
    Vertex,                     //  The type that describes a Vertex.
    Edge                        //  The type that describes an Edge
> MyGraph;

现在,您可以使用快捷方式来指定顶点和边的ID的类型:

typedef MyGraph::vertex_descriptor VertexID;
typedef MyGraph::edge_descriptor   EdgeID;

实例化图表:

MyGraph graph;

读取您的Graphviz数据,并提供图形:

for (each Vertex V){
    VertexID vID = boost::add_vertex(graph); // vID is the index of a new Vertex
    graph[vID].name = whatever;
}

[注意,graph[ a VertexID ]提供了一个顶点,但是graph[ an EdgeID ]提供了一个边。这是添加一个的方法:

EdgeID edge;
bool ok;
boost::tie(edge, ok) = boost::add_edge(u,v, graphe); // boost::add_edge gives a std::pair<EdgeID,bool>. It's complicated to write, so boost::tie does it for us. 
if (ok)  // make sure there wasn't any error (duplicates, maybe)
    graph[edge].member = whatever you know about this edge

所以现在您有了图表。您想要获取顶点“ c”的VertexID。为了简单起见,让我们使用线性搜索:

MyGraph::vertex_iterator vertexIt, vertexEnd;
boost::tie(vertexIt, vertexEnd) = vertices(graph);
for (; vertexIt != vertexEnd; ++vertexIt){
    VertexID vertexID = *vertexIt; // dereference vertexIt, get the ID
    Vertex & vertex = graph[vertexID];
    if (vertex.name == std::string("c")){} // Gotcha
}

最后,得到顶点的邻居:

MyGraph::adjacency_iterator neighbourIt, neighbourEnd;
boost::tie(neighbourIt, neighbourEnd) = adjacent_vertices( vertexIdOfc, graph );
for(){you got it I guess}

您也可以使用]获得边缘>

std::pair<out_edge_iterator, out_edge_iterator> out_edges(vertex_descriptor u, const adjacency_list& g)
std::pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor v, const adjacency_list& g)
 // don't forget boost::tie !

所以,您的真正问题是:

  • 找到顶点“ c”的ID
  • 递归查找in_edges
  • 递归查找边缘
  • in_edges的示例(从未编译或尝试过,超出我的脑袋):

void findParents(VertexID vID){
    MyGraph::inv_adjacency_iterator parentIt, ParentEnd;
    boost::tie(parentIt, ParentEnd) = inv_adjacent_vertices(vID, graph);
    for(;parentIt != parentEnd); ++parentIt){
        VertexID parentID = *parentIt;
        Vertex & parent = graph[parentID];
        add_edge_to_graphviz(vID, parentID); // or whatever
        findParents(parentID);
    }
}

反过来说,只需将Parent重命名为Children,然后使用adjacency_iterator / neighbor_vertices。


5
投票

这里是怎么结束的。我意识到我需要完全在前沿和前沿方面开展工作:

© www.soinside.com 2019 - 2024. All rights reserved.