c++ - 如何将一组 C++ 动态分配的对象表示为 BGL(Boost Graph Library)图以获得它们的依赖图？

Question

有一组 C++ 动态分配的对象为:

class MyObject;
MyObject* a = ....;
MyObject* b = ....;
MyObject* c = ....;

具有已知的依赖关系:

• b 依赖于 a
• c 依赖于 b

如何尽可能简单地将这些对象表示为 BGL graph为了获得他们的dependency graph ？

因此，依赖图应该是一个指针列表，如:a、b、c(或以相反的顺序)。

我知道可以使用 boost::topological_sort 获得依赖图.直到现在我还没有找到处理对象指针的 BGL 图的示例。相反，我发现了很多 examples based on integers .

Answer 1

整数是图的顶点和边的索引。因此，在您的示例中，第一个顶点是 a，第二个顶点是 b，而第一条边连接顶点 1 和 2(a 和 b)

每个顶点都有属性。因此，在您的示例中，第一个顶点被命名为 a 并且有一个指向 a 的指针。

图形算法使用整数索引来操作图形，您的代码可以使用索引返回您感兴趣的属性，例如名称和指针。

以下是我将如何编写您发布的示例的代码:

/**

Bundled properties for graph vertices

Simply contains a pointer to the associated MyObject

*/

class cVertex
{
public:
    MyObject * pObject;
};

class cEdge
{

};

class cGraphProps
{

};

....

// The BGL graph
typedef boost::adjacency_list <
    boost::vecS, boost::vecS, boost::directedS,
    cVertex, cEdge, cGraphProps  >
    graph_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;

graph_t myGraph;

// Create objects and associate them with graph vertices
MyObject * a = new MyObject( 'a');
vertex_t va = boost::add_vertex( myGraph );
myGraph[ va ].pObject = a;
MyObject * b = new MyObject( 'b');
vertex_t vb = boost::add_vertex( myGraph );
myGraph[ vb ].pObject = b;
MyObject * c = new MyObject( 'c');
vertex_t vc = boost::add_vertex( myGraph );
myGraph[ vc ].pObject = c;

// specify the 'dependencies' between the myObjects
boost::add_edge( vb, va, myGraph );
boost::add_edge( vc, vb, myGraph );

// sort the vertices into order according to dependencies
std::deque<int> topo_order;
boost::topological_sort( myGraph, std::front_inserter(topo_order));

// Print the results.
for(std::deque<int>::const_iterator i = topo_order.begin();
    i != topo_order.end();
    ++i)
{
    std::cout << myGraph[*i].pObject->x << std::endl;
}