有向无环图中所有连接的源汇对的集合有一个术语吗？

Question

我有一个非常大的有向无环图，它由连接的较小 DAG 组成。通过较大的图表进行分析需要很长时间才能找到：

• 源的所有连接接收器
• 水槽的所有连接源

我在想，我可以将较小的 DAG 减少到一组它们的源汇对，以稍微加快端到端的分析速度。 （来源：入度 = 零；汇：出度 = 零。）因此，对于子图的玩具版本...

...源汇对的集合将是：[(A,E), (A,D), (C,D)].

DAG 的这组连接的源汇对有名称吗？

我知道如何进行还原。有效率的？也许，也许不是，所以我想搜索更多信息。我没有图论的学术背景，我不知道要搜索什么术语。对于这个分析，我可以丢失源和汇之间的所有节点和边缘信息进行分析（数据将保留在原始图中，这更多是用于分析的伴随减少），所以我不认为这是一个传递性减少，它保留了所有中间节点。

数据存在于关系数据库中，所以我无法利用图形数据库必须提供的一些查询或工具。

Answer 1

算法：

- Loop over vertices
  - If out degree zero add to sinks
- Loop over vertices
  - If in degree zero
      - Run Dijsktra starting from vertex
      - Loop over sinks
          - If sink reachable, add to sinks connected to source
      - Add source and connected sinks to output

执行签名

/// @brief Find connected source and sinks
/// @param g the graph
/// @return vector of vectors containing a source index and the connected sink indices
///
/// A source has a zero in-degree, a sink has a zero out-degree

std::vector<std::vector<int>> sourceToSink(
    const cGraph &g);

单元测试

TEST(sourceToSink)
{
    raven::graph::cGraph g;
    g.directed();
    g.findorAdd("a", "b");
    g.findorAdd("b", "e");
    g.findorAdd("b", "d");
    g.findorAdd("c", "d");

    auto res = sourceToSink( g );

    CHECK_EQUAL(2,res.size());
    std::vector<std::string> exp1 { "a","e","d"};
    CHECK(std::equal(
        exp1.begin(),
        exp1.end(),
        g.userName(res[0]).begin() ));
    std::vector<std::string> exp2 { "c","d"};
    CHECK(std::equal(
        exp2.begin(),
        exp2.end(),
        g.userName(res[1]).begin() ));
}

实施

std::vector<std::vector<int>> sourceToSink(
        const cGraph &g)
    {
        std::vector<std::vector<int>> ret;

        // find sinks
        std::vector<int> vsink;
        for (int vi = 0; vi < g.vertexCount(); vi++)
        {
            if (!g.adjacentOut(vi).size())
                vsink.push_back(vi);
        }

        // loop over vertices
        for (int vi = 0; vi < g.vertexCount(); vi++)
        {
            // check for source
            if (g.adjacentIn(vi).size())
                continue;

            // find path to every other vertex
            std::vector<double> dist;
            std::vector<int> pred;
            dijsktra(g, vi, dist, pred);

            // find connected sinks
            std::vector<int> vConnected;
            vConnected.push_back(vi);
            for (int si : vsink)
            {
                if (pred[si] >= 0)
                    vConnected.push_back(si);
            }
            ret.push_back(vConnected);
        }
        return ret;
    }

随机生成图的性能

节点	边	来源	运行时间
10K	50K	75	9 秒
100K	500K	67K	25 秒
1,000K	5,000K	?	仍在运行

完整的应用程序代码在https://github.com/JamesBremner/PathFinder