我正在使用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),但是我不确定从哪里开始寻找。
谢谢!
好,我将翻译您的教程并将其适应您的特定问题。该文档始终假定大量“使用命名空间”;我什么也不会用,所以您知道什么。让我们开始:
#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 !
所以,您的真正问题是:
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。
这里是怎么结束的。我意识到我需要完全在前沿和前沿方面开展工作: