1

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

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

具有已知的依赖关系：

  • b取决于a
  • c取决于b

这些对象如何尽可能简单地表示为BGL 图以获得它们的依赖图？

因此，依赖图应该是一个指针列表，如：、、a（或相反的顺序）。bc

我知道可以使用boost::topological_sort获得依赖图。直到现在我还没有找到一个处理指向对象的指针的 BGL 图的例子。相反，我发现了许多基于整数的示例。

4

2 回答 2

2

整数是图的顶点和边的索引。因此，在您的示例中，第一个顶点是 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;
}
于 2013-07-04T10:36:34.400 回答
0

我编写了这个实现，但如果可能的话，我更喜欢一个更简单的实现：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>

class MyObject
{
public:
    char x;
    MyObject( const char c): x( c) {}
};

int main()
{
    auto a = new MyObject( 'a');
    auto b = new MyObject( 'b');
    auto c = new MyObject( 'c');

    typedef std::vector<const MyObject*> Objects;
    Objects objects;
    objects.push_back( c); // c = 0
    objects.push_back( a); // a = 1
    objects.push_back( b); // b = 2

    typedef std::vector<size_t> Indexes;
    Indexes indexes;

    {
        typedef std::unordered_map<Objects::value_type, size_t> PtrIntMap;
        PtrIntMap ptrIntMap;
        std::for_each( objects.begin(), objects.end(), [&ptrIntMap]( Objects::reference item) { ptrIntMap.insert( std::make_pair( item, ptrIntMap.size())); });

        using namespace boost;
        adjacency_list<> g( objects.size());
        add_edge( ptrIntMap.at( b), ptrIntMap.at( a), g);
        add_edge( ptrIntMap.at( c), ptrIntMap.at( b), g);

        topological_sort( g, std::back_inserter( indexes)); 
    }

    Objects dependencies( indexes.size());
    std::transform( indexes.begin(), indexes.end(), dependencies.begin(), [&objects]( Indexes::value_type index) { return objects[ index]; });
    std::for_each( dependencies.begin(), dependencies.end(), []( const Objects::value_type item) { std::cout << item->x << ' '; });
}
于 2013-07-05T12:09:43.550 回答