c++ - 是否有一种(文学)算法可将每个传入边缘的节点拆分为一个节点？

Question

是否有一个(文学)算法可将in度> 1的所有节点拆分为每个传入边缘一个节点，以便每个拆分节点仅具有一个传入边缘和所有原始出局边缘？

例:
假设我们有以下有向图:A <-> B <-> C(从A到B，B到A，B到C和C到B的有向边)

B的度数为2，这意味着B应该分为两个节点，每个节点都具有一个输入边缘以及所有原始输出边缘。

该算法应将此图更改为以下形式:

A-> B_A

B_A-> C

B_A-> A

C-> B_C

B_C-> A

B_C-> C

另外，如果您可以提出一个合适的数据结构来存储结果图，我会很高兴(请记住，原始图的节点表示网格坐标，因此结果图的顶点也应如此)。

Answer 1

首先，我创建了一个非常简单的图形描述作为输入。它是用分号分隔的“顶点-> Vertex1，Vertex2，VertexN”列表。

我认为，每个人都可以轻松理解:

std::string graphDefinition("a->b; b->a,c,d; c->b; d->b");

不幸的是，我需要15行代码，将其拆分并转换为图形表示形式。这基本上是一个邻接表。我用

std::map<std::string, std::vector<std::string>>

第一个字符串是“From”部分，并且 std::vector包含所有“To”或“Target” -Vertices。

为了构建DirectedGraph，我做了一个单独的函数。

附加函数将DirectedGraph转换为您指定的格式。为此，它检查顶点在右侧(目标)出现多少次。这些是顶点多于箭头的顶点。对于这些，我检查它们在哪条边上，然后创建一个由找到的顶点组成的新顶点。

最后，我再次遍历该图并添加所有边，在所有边的所有右侧上只有一个顶点的地方。

抱歉，这有点复杂。但请阅读并消化。

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <regex>
#include <map>

// Sime typedefs
using Vertex = std::string;
using TargetVertex = std::vector<Vertex>;
using FromTo = std::pair<Vertex, Vertex>;
using DirectedGraph = std::map<Vertex, TargetVertex>;

// Build a directed graph from a given string in a special format
DirectedGraph buildFromDefinitionString(std::string& s) {
    // Local lamda to trim strings
    auto trim = [](const std::string& s) { return std::regex_replace(s, std::regex("^ +| +$"), "$1"); };
    std::regex re1{ ";" }; std::regex re2{ "->" }; std::regex re3{ "," };

    // Split source line along ";"
    TargetVertex edge(std::sregex_token_iterator(s.begin(), s.end(), re1, -1), {});

    // Split substring along "->"
    std::vector <FromTo> fromTo;
    std::transform(edge.begin(), edge.end(), std::back_inserter(fromTo), [&re2](const std::string& s) {
        TargetVertex ft(std::sregex_token_iterator(s.begin(), s.end(), re2, -1), {});
        return std::make_pair(ft[0], ft[1]);});

    // Split target strings along ","
    DirectedGraph directedGraph;    
    for (const FromTo& ft : fromTo) {
        TargetVertex tv(std::sregex_token_iterator(ft.second.begin(), ft.second.end(), re3, -1), {});
        // Build graph
        for (const Vertex v : tv) {
            directedGraph[trim(ft.first)].push_back(std::move(trim(v)));
        }
    }
    return directedGraph;
}

DirectedGraph convert(const DirectedGraph& dg) {
    DirectedGraph result{};

    for (const auto& ge1 : dg) {
        // How many times is a vertex on the right hand side        
        size_t sum{ 0 };
        // Count all occurences of current evaluate vertex on target side
        for (const auto& ge2 : dg) {
            sum += std::count(ge2.second.begin(), ge2.second.end(), ge1.first);
        }
        // So, now we have the sum of occurrences
        std::cout << "Vertex " << ge1.first << " is " << sum << " times a target\n";
        // For all vertecis with indegree > 1
        while (sum-- > 1) {
            // Go again through the complete directed graph and check, where the current vertex is on the target side
            for ( auto& ge2 : dg) {
                if (auto search = std::find(ge2.second.begin(), ge2.second.end(), ge1.first); search != ge2.second.end()) {
                    // Build new string
                    Vertex newVertex = ge1.first + "_" + ge2.first;
                    result[newVertex] = ge1.second;
                }
            }
        }
    }
    // For those where there is only an indegree of 1
    for (const auto& r : result) {
        if (r.first.size() > 1) {
            result[r.first.substr(r.first.rfind('_')+1)].push_back(r.first);
        }
    }
    return result;
}

int main() {
    // A lambda for printing a graph
    auto printGraph = [](DirectedGraph& dg) { for (const auto& ge : dg) 
        for (Vertex v : ge.second)  std::cout << ge.first << " --> " << v << "\n"; };

    // The definition string for our graph
    std::string graphDefinition("a->b; b->a,c,d; c->b; d->b");

    // Build our graph data structure
    DirectedGraph dg1 = buildFromDefinitionString(graphDefinition);
    printGraph(dg1);

    // Convert it as per task definition
    DirectedGraph dg2= convert(dg1);
    printGraph(dg2);

    return 0;
}