首页 文章

Boost图库中两个节点之间的所有路径

提问于
浏览 次
1

我需要在图中的两个节点之间找到所有简单（非循环）路径 . 我理解如何通过改进的广度优先搜索来实现这一点，因此在Boost中查看BFS，但我看不出如何改变算法的步骤，只有访问者 .

在我从头开始编写新算法之前，有没有办法通过使用现有的算法在BGL中实现这一点，无论是否有自定义访问者？

c++ boost graph-theory boost-graph

1 回答

  • 2

    我们需要更多地了解您的图表 . 我有一个“类似”的问题 .

    这可能不是您正在寻找的，但它是相似的 . 这是我在带有根的有向图上使用的DFS访问者，用于计算从起始节点到所有其他（可到达）节点的路径数 .

    这是有效的，因为我的图是一个根植的DAG . 我必须首先反转图形，以便我的起始节点实际上是一个汇聚节点 . 然后，源节点成为DAG的根 . 如果我想要实际路径，我可能会添加一个告诉路径历史的堆栈 .
    enter image description here

    //depth first search to calculate path number, calculates the number of paths to a target
// conceptually equivalent to a topological sort.
class PathNumDFSVisitor:public boost::default_dfs_visitor{

public:
    PathNumDFSVisitor(boost::unordered_map<std::string,std::size_t>& inMap):pathNumMap(inMap){}

    template < typename Vertex, typename Graph >
    void finish_vertex(Vertex u, const Graph & g)
    {
        std::string term = g[u].termId;

        if(boost::out_degree(u,g) == 0){
            pathNumMap[term] = 1;
        }else{
            pathNumMap[term] = 0;
            //Iterate over the children of the term to add the child annotations
            typename boost::graph_traits< Graph >::out_edge_iterator ei, e_end;
            for(tie(ei, e_end) = boost::out_edges(u, g); ei != e_end; ++ei){

                Vertex v = boost::target(*ei, g);

                std::string childTermId = g[v].termId;
                pathNumMap[term] += pathNumMap[childTermId];
            }
        }
    }

    boost::unordered_map<std::string,std::size_t>& pathNumMap;
};

    但是，在一般情况下，我建议计算一条最短路径，然后依次取每条边，找到从源到目标的备用路径 . 现在该边缘可以是两条或更多条边，而这又需要放宽并考虑用于替代路径 . 像Sehe所说，它将是一个发电机，并且它可以在一般的无向图中快速爆炸 . 也许如果我们对您的图形约束有更多了解，我们可以提供更多帮助 .

    也许添加最大路径长度条件可以帮助约束您生成的简单路径数 .

    考虑这个通用的完全连接图 .
    enter image description here

    我们需要计算 A 和 B 之间的所有路径 .

    所以我们需要所有2条边路径所有2条边路径加上......

    所以我们需要 A - B ，一个边缘 .

    然后是所有2条边路径 . A - ? - B ，有3个

    然后所有3条边路径 A - ? - ? - B ，有3 * 2 .

    等等有4个或更多边 .

    你可以看到N增长我们达到N-2 * N-3 * N-4 ......等等 . 这是一个因子爆炸，O（N！） .

    这些示例说明了不同的拓扑结构如何导致非常不同的算法和复杂性 . 从SO获得直接/有用的答案给出任何有用的细节 .

    回复于

相关问题