c++ - 选择连接到一个顶点的所有边和顶点的算法

Question

我正在使用 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)，但我不确定从哪里开始寻找.

谢谢!

Answer 1

好的，所以我将根据您的具体问题翻译和调整我的教程。 文档总是假设大量的“使用命名空间”；我不会使用任何，所以你知道什么是什么。 让我们开始吧:

#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 ] 给出了 Vertex，但 graph[ an EdgeID ] 给出了 Edge。添加方法如下:

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
• 递归查找 out_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/similar_vertices。