算法选择连接到一个顶点的所有边和顶点 [英] Algorithm for selecting all edges and vertices connected to one vertex

问题描述

我使用加速图形，试图让我在Graphviz的圆点格式产生了一些依赖关系图的感觉。

I'm using Boost Graph to try and make sense of some dependency graphs I have generated in Graphviz Dot format.

不幸的是，我不知道非常关注图论，所以我也很难制定我想在图论术语方面知道的。

Unfortunately I don't know very much about graph theory, so I have a hard time framing what I want to know in terms of graph theory lingo.

从〜150顶点的直接依赖关系图，我想放大的一个特定的顶点V，并建立一个包含子V，其所有入边和入边，它的所有出边和他们的出边，有点像到第五最长的路径。

From a directed dependency graph with ~150 vertices, I'd like to "zoom in" on one specific vertex V, and build a subgraph containing V, all its incoming edges and their incoming edges, all its outgoing edges and their outgoing edges, sort of like a longest path through V.

这些依赖关系图是pretty纠结，所以我想以消除杂波，使之更清晰什么会影响相关的顶点。

These dependency graphs are pretty tangled, so I'd like to remove clutter to make it clearer what might affect the vertex in question.

例如，给定的;

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

如果我是运行C 在的算法，我想我要;

if I were to run the algorithm on c, I think I want;

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

不知道。如果B - > F应包括在内。我认为它是他们所有的入边包括C后的C应该有前顶点，所有顶点应该有自己的出边包括在内，但在我看来，这将失去一些信息。

Not sure if b -> f should be included as well... I think of it as all vertices "before" c should have their in-edges included, and all vertices "after" c should have their out-edges included, but it seems to me that that would lose some information.

这感觉就像应该有一个算法做这个（或更懂事，不知道如果我试图做一些愚蠢的事，CF B-> F时上部），但我不知道从哪里开始寻找。

It feels like there should be an algorithm that does this (or something more sensible, not sure if I'm trying to do something stupid, cf b->f above), but I'm not sure where to start looking.

谢谢！

推荐答案

好了，我会翻译和改编我的教程，您的具体问题。
文档总是假定吨的使用命名空间的;所以你知道什么是什么，我不会使用任何。
让我们开始吧：

Ok, so I'll translate and adapt my tutorial to your specific question. The documentation always assumes tons of "using namespace"; I won't use any so you know what is what. Let's begin :

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

首先，定义一个顶点和边缘：

First, define a Vertex and an Edge :

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的类型：

Now, you can use a shortcut to the type of the IDs of your Vertices and Edges :

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

实例化你的图：

MyGraph graph;

看了你的Graphviz的数据，并喂图：

Read your Graphviz data, and feed the graph :

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

注意图[A VertexID] 给出了一个顶点，但图[一个EdgeID的] 给出了一个边缘。以下是如何添加一个：

Notice that graph[ a VertexID ] gives a Vertex, but graph[ an EdgeID ] gives an Edge. Here's how to add one :

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

所以，现在你有你的图形。你想获得VertexID顶点C。为了保持它的简单，让我们使用线性搜索：

So now you have your graph. You want to get the VertexID for Vertex "c". To keep it simple, let's use a linear search :

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
}

最后，得到一个顶点的邻居：

And finally, to get the neighbours of a vertex :

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 !

所以，你真正的问题：

So, for your real question :

• 找到顶点C的ID


• 找到in_edges递归


• 找到out_edges递归

举例in_edges（从不编译或尝试过，从我的头顶部）：

Example for in_edges (never compiled or tried, out of the top of my head):

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);
    }
}

对于其他方式，只需重命名成父母的儿童，并使用adjacency_iterator / adjacent_vertices。

For the other way around, just rename Parent into Children, and use adjacency_iterator / adjacent_vertices.

希望这有助于。

这篇关于算法选择连接到一个顶点的所有边和顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！