graph:使用包含通配符的节点列表查找子图

Question

有以下问题得到一个名称,是否有解决它的算法？:给定一个图形,无论是否有指向,找到满足给定规范的所有路径

1. 精确节点列表,或
2. '*？' 它表示"任何节点或根本没有节点",或
3. '*{n}'表示'任意n个连续连接的节点'

例如

A -> B -> *? -> D which results in ABXD and ABYD and ABD etc.

要么

A -> *{1} -> D -> *? -> E which results in ABXDZE and ABYDZE and ABDZE etc. etc.

谢谢

ps有没有人知道在R或perl或C中执行此操作的图形库？

Answer 1

我最后做的是：

1. 问题是找到 2 个节点之间长度为 N 的所有路径。周期被排除在外。
2. 以边列表的形式读取数据，例如从->到节点对（假设节点名称是唯一的）
3. 创建一个哈希表（或 boost 和 stl、c++ 中的 unordered_map），其中节点名称作为键，哈希表作为值。
4. 第二个哈希表将包含第一个节点导致的所有节点作为键。

例如

A->B
A->C
B->D
C->E
E->D

将所有数据读入“边缘列表”后，以 Perl 表示法保存输入数据的结果数据结构如下所示：

my %hash = (
'A' => {'B' => 1, 'C' => 1},
'B' => {'D' => 1},
'C' => {'E' => 1},
'E' => {'D' => 1},
);

查找一对节点是否直接连接可以大致如下完成（perl）：

sub search {
    my ($from,$to) = @_;
    if( $to eq '*' ){ return defined($x=$hash{$from}) ? [keys $hash{$from}] : [] }
    return defined($x=$hash{$from}) && defined($x{$to}) ? [$to] : []
}

在上面的函数中，通过将 $to 设置为“*”，可以返回“from”节点连接到的所有节点。返回的是直接连接到 $from 参数的节点的数组引用。

搜索两个节点之间的路径需要递归地使用上述函数。

例如

sub path {
    my ($from,$to, $hops, $save_results) = @_;
    if( $hops < 0 ){ return 0 }
    $results = search($from, '*');
    if( "".@$results == 0 ){ return 0 }
    $found = 0;
    foreach $result (@$results){
        $a_node = new Tree::Nary($result);
        if( path($result, $to, $hops-1, $a_node) == 1 ){
            $save_results->insert($save_results, -1, $a_node);
            $found = 1;
        }
    }
    return $found;

}

如果由于堆栈溢出[原文如此]，深度不是太多（即 $hops < 6 ？），那么使用递归是可以的。

最棘手的部分是读取结果并提取每条路径的节点。经过深思熟虑，我决定使用 Tree::Nary （n 叉树）来存储结果。最后我们得到如下的树：

     |-> B -> D
A -> |-> C -> E -> D

为了提取所有路径，请执行以下操作：

1. 找到所有的叶子节点
2. 从每个叶节点开始，通过其父节点向后移动到根节点并保存节点名称。

上面是使用 perl 实现的，但也使用 boost::unordered_map 作为哈希表在 C++ 中实现。我还没有在当时的 C++ 代码中添加树结构。

结果：对于 3281415 条边和 18601 个唯一节点，perl 需要 3 分钟找到 A->'*'->'*'->B。准备好后我将提供 C++ 代码的更新。