标签: transitive-closure

许多谓词定义了某种通过二元关系定义的边构建的非循环路径,与定义传递闭包非常相似.因此需要通用定义.

请注意,图论中定义的概念不容易与通常预期的匹配.最值得注意的是,我们对边缘的名称不感兴趣.

更糟糕的是,图论也发生了一些变化,引入了步行的概念,注意到了

传统上,路径指的是现在通常称为开放式步行的路径.如今,当没有任何限定地陈述时,路径通常被理解为简单,意味着没有重复顶点(因此没有边缘).(术语链也用于指代所有顶点和边缘都不同的步行.)

所以我的问题是:如何命名和定义此功能？

到目前为止我所做的是定义:

path(Rel_2, Path, X0,X)

第一个论点必须是关系的延续.然后是Path顶点或顶点.

用法示例

n(a, b).
n(b, c).
n(b, a).

?- path(n,Xs, a,X).
Xs = [a], X = a ;
Xs = [a, b], X = b ;
Xs = [a, b, c], X = c ;
false.

履行

:- meta_predicate path(2,?,?,?).

:- meta_predicate path(2,?,?,?,+).

path(R_2, [X0|Ys], X0,X) :-
   path(R_2, Ys, X0,X, [X0]).

path(_R_2, [], X,X, _).
path(R_2, [X1|Ys], X0,X, Xs) :-
   call(R_2, X0,X1),
   non_member(X1, Xs),
   path(R_2, …

许多谓词基本上使用某种形式的传递闭包,只是发现终止也必须得到解决.为什么不一次解决这个问题closure0/3:

:- meta_predicate closure0(2,?,?).
:- meta_predicate closure(2,?,?).

:- meta_predicate closure0(2,?,?,+). % internal

closure0(R_2, X0,X) :-
   closure0(R_2, X0,X, [X0]).

closure(R_2, X0,X) :-
   call(R_2, X0,X1),
   closure0(R_2, X1,X, [X1,X0]).

closure0(_R_2, X,X, _).
closure0(R_2, X0,X, Xs) :-
   call(R_2, X0,X1),
   non_member(X1, Xs),
   closure0(R_2, X1,X, [X1|Xs]).

non_member(_E, []).
non_member(E, [X|Xs]) :-
   dif(E,X),
   non_member(E, Xs).

是否存在此定义不能用于实现传递闭包的情况？

为什么dif/2？

详细回答@ WouterBeek的评论:dif/2或者iso_dif/2是理想的,因为它们能够显示或发出潜在问题的信号.但是,在当前的实现中,顶级循环通常会隐藏实际问题.考虑一下closure0(\_^_^true,a,b)本身肯定存在问题的目标.使用以下系统时,实际问题直接不可见.

| ?- closure0(\_^_^true,a,b). % SICStus
yes

?- closure0(\_^_^true,a,b).   % SWI
true ;
true ;
true ...

两个顶级循环都没有显示我们真正想要看到的内容:悬空约束.在SICStus中,我们需要一个伪变量来产生一些替换,在SWI中,查询必须被包装call_residue_vars/2.以这种方式,现在显示所有附加约束的变量.

| …

我是Prolog的新手.我graph.pl在下图中定义:

这是我的Prolog代码:

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
path(X,X).
path(X,Y):- edge(X,Z) ; path(Z,Y).

我理解如下:只有在顶点X和顶点之间Y存在边缘且顶点X和顶点之间Z存在一条路径ZY(某种递归)时,顶点和顶点之间才有路径.

这对于呈现的图表是否正确？当我问Prolog关于顶点A和顶点之间的路径时,F它给了我true......这甚至都不对!这段代码可能有什么问题？

我需要回答这个问题:给定一个依赖图中的节点,通过它们自己的传递依赖对其依赖者进行分组,这些依赖会受特定的起始节点的影响.

换句话说,给定依赖图中的节点,找到直接依赖的集合的集合,其直接依赖于从该特定起始节点导出的公共依赖.

例如,给出伪代码:

let a = 1
let b = 2
let c = a + b
let d = a + b
let e = a
let f = a + e
let g = c + d

你可以计算这个图:

如果我们用作a起始节点,我们可以看到a两者的依赖性,c并且d具有依赖性g.并且f有依赖e和a.

请注意,a根本没有任何影响b,因此在决定如何对依赖者进行分组时不应将其考虑在内a.

使用a作为起始节点,我们想要获得这些分组的依赖集:

groups = {{c, d}, {e, f}}

c并且d具有直接或传递的下游关系,并且e也 …

我希望你能帮我解决这个问题。

我正在尝试了解 Prolog 中的深度优先搜索算法，并且遇到了以下代码

go(Start, Goal) :-
   empty_stack(Empty_been_list),
   stack(Start, Empty_been_list, Been_list),
   path(Start, Goal, Been_list).

% path implements a depth first search in PROLOG

% Current state = goal, print out been list
path(Goal, Goal, Been_list) :-
    reverse_print_stack(Been_list).

path(State, Goal, Been_list) :-
    mov(State, Next),
    % not(unsafe(Next)),
    not(member_stack(Next, Been_list)),
    stack(Next, Been_list, New_been_list),
    path(Next, Goal, New_been_list), !.

reverse_print_stack(S) :-
    empty_stack(S).
reverse_print_stack(S) :-
    stack(E, Rest, S),
    reverse_print_stack(Rest),
    write(E), nl.

我有点明白发生了什么，但我一生都无法找到或发明一些我可以使用的事实。

请帮忙。即使它是一组非常简单的事实，我也只需要从某个地方开始

先感谢您

生成一组元组的传递闭包的最佳方法是什么？

例:

• 输入 Set((1, 2), (2, 3), (3, 4), (5, 0))
• 产量 Set((1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (5, 0))

我正在尝试实现Warshall的算法来快速计算LR(1)闭包.

我想我理解LR(0)的工作原理:

• 图的节点是LR项,如A ? B • C
• 边缘是"过渡"从开始A ? B • C到C ? • D

问题是,LR(1)需要计算前瞻,我无法弄清楚如何将它们合并到算法中.
在我看来,即使我知道任何给定的LR项目的传递闭包,我仍然需要经历所有相同的计算,只是为了弄清楚每个项目的前瞻设置是什么.

甚至可以使用Warshall的算法来计算规范的LR(1)闭包,还是只能用于更受限制的情况(如LR(0),SLR(1)等)？

我试图使用Spark来处理简单的图形问题.我在Spark源文件夹中找到了一个示例程序:transitive_closure.py,它在一个图形中计算传递闭包,不超过200个边和顶点.但是在我自己的笔记本电脑中,它运行超过10分钟并且不会终止.我使用的命令行是:spark-submit transitive_closure.py.

我想知道为什么即使计算这么小的传递闭包结果,火花也是如此之慢？这是常见的情况吗？有没有我想念的配置？

该程序如下所示,可以在他们网站的spark install文件夹中找到.

from __future__ import print_function

import sys
from random import Random

from pyspark import SparkContext

numEdges = 200
numVertices = 100
rand = Random(42)


def generateGraph():
    edges = set()
    while len(edges) < numEdges:
        src = rand.randrange(0, numEdges)
        dst = rand.randrange(0, numEdges)
        if src != dst:
            edges.add((src, dst))
    return edges


if __name__ == "__main__":
    """
    Usage: transitive_closure [partitions]
    """
    sc = SparkContext(appName="PythonTransitiveClosure")
    partitions = int(sys.argv[1]) if len(sys.argv) > 1 else 2
    tc = sc.parallelize(generateGraph(), partitions).cache()

    # Linear …

我正在学习Prolog,我正在复习讲义,所有笔记都说:

给定有向图的以下定义:

path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

如果我们想让它成为一个无向图,edge(X, Y) :- edge(Y, X).单独定义 不起作用,我无法弄清楚为什么.如果Y到X有边,则X到Y有一条边.似乎对我有意义.

这些说明并没有真正说明原因,但它确实定义了正确的解决方案:

edge1(X, Y) :- edge(X, Y).
edge1(X, Y) :- edge(Y, X). 

我们已经拥有的东西.

谁能解释一下这个,请和谢谢？<3

我需要使用Haskell在列表上生成传递闭包.

到目前为止我得到了这个:

import Data.List
qq [] = []
qq [x] = [x]
qq x = vv (sort x)

vv (x:xs) = [x] ++ (member [x] [xs]) ++  (qq xs)

member x [y] = [(x1, y2) | (x1, x2) <- x, (y1, y2) <- qq (y), x2 == y1]

输出1:

*Main> qq [(1,2),(2,3),(3,4)]
[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

输出2:

*Main> qq [(1,2),(2,3),(3,1)]
[(1,2),(1,3),(1,1),(2,3),(2,1),(3,1)]

问题在于第二次输出.它不是在新生成的列表上检查额外的传递闭包,而是返回结果.

为了原型haskell代码,我使用了这个Python代码:

def transitive_closure(angel):
    closure = set(angel)
    while True:
        new_relations = set((x,w) for x,y in closure for q,w in closure …