分层无向图表示

Question

我要代表这样的图形：

Graph = graph([Object1,Object2,Object3,Object4], 
       [arc(Object1,Object2,connected), 
       arc(Object2,Object4,connected), 
       arc(Object3,Object4,connected), 
       arc(Object1,Object3,connected), 
       arc(Object2,Object3,parallel), 
       arc(Object1,Object4,parallel), 
       arc(Object2,Object3,similar_size), 
       arc(Object1,Object4,similar_size)]) 

我对代码没有限制，但是我会坚持这种表示，它适用于所有我已经编码的其他结构。

我的意思是无向图，其中顶点是一些对象，边代表它们之间的无向关系。为了给你在这个特定的例子中更多的背景，我试图表示一个矩形，所以对象是它的四个边（段）。这些片段使用顶点等以相同的方式表示。重点是构建图表的层次结构，它表示同一级别上的对象之间的约束。

问题存在于边缘的表示中。表示弧（a，b）最明显的方法是将（a，b）和（b，a）放入程序中。但是，这会使我的程序泛滥成倍的数据泛滥。例如，如果我有顶点a，b，c，d。我可以构建段（a，b），（a，c），（a，d），（b，c），（b，d），（c，d）。但我也得到（b，a），（c，a）等等。在这一点上它不是问题。但后来我建立了一个矩形。它可以构建段（a，b），（b，c），（c，d），（a，d）。我想得到答案 - 有一个矩形。然而，你可以计算出这个矩形的组合数。这也需要太多的时间来计算，显然我不想在矩形级完成。

我想过排序元素。我可以在一个段中排序顶点。但是，如果我想要在矩形中对段进行排序，则约束不再有效。图表变成了指示。例如考虑前两个关系，假设我们有弧（a，b）和（a，c）。如果没有对弧进行排序，则程序按照我的要求进行回答：arc（b，a，connected），arc（a，c，connected）匹配：Object1 = b，Object2 = a，Object4 = c。如果我对元素进行排序，它不再有效，因为我不能有弧（b，a，连接）和弧（a，b，连接）试用。只有第二个。我会坚持排序，但我不知道如何解决这个最后的问题。

希望我说得很清楚。我宁愿尽量接近我已有的表示和想法。但全新的也是非常受欢迎的。我不期待任何确切的答案，而是让我朝着正确的方向倾斜，或者提出具体的东西来读，因为我对Prolog来说很新，也许这个问题并不罕见。

我想从昨天开始解决这个问题，不能拿出任何简单的答案。我查看了一些离散数学和通用无向图表示，如邻接表。如果有任何不清楚的地方，请告诉我 - 我会尽力提供更多细节。

Answer 1

有趣的问题，虽然有点广泛，因为它没有说明你实际想要做的弧，矩形等;只有某些用途时，表示可能是有效的（时间/空间/优雅）。无论如何，这里有一些想法：

排序
明显的问题是你提到的问题;

arc(X,Y):- 
    arc_data(X,Y) 
    ; arc_data(Y,X). 

注意，你应该不做这样的事情：

arc(a,b). 
arc(b,c). 
arc(X,Y):- 
    arc(Y,X) 

，因为这将导致一个无限循环，如果你可以通过引入成功，如果有序对存在一个条款，解决它该弧线不存在。 如果第一个参数是大于第二个，你可以但只有检查：

arc(a,b). 
arc(b,c). 
arc(X,Y):- 
    compare(>,X,Y), 
    arc(Y,X) 

这种做法不会解决可能出现由于有两种方式表示的弧的多种解决方案。 最简单的解决将是只检查一个解决方案，其中只有一个解决方案是使用once/1预计：

3 ?- arc(X,Y). 
X = a, 
Y = b ; 
X = b, 
Y = a. 

4 ?- once(arc(X,Y)). 
X = a, 
Y = b. 

当然你不能做到这一点的时候可能有多种解决方案。

另一种方法是强制执行进一步的抽象：此刻，当你有两个点（a，b），您可以创建弧（arc(a,b)或arc(b,a)）检查，如果这些点连接后。相反，你应该通过谓词创建弧（也可以检查点是否连接）。好处是，你不再涉足直接弧的表示，因此可以强制执行排序（是的，它基本上是面向对象）：

cv_arc(X,Y,Arc):- 
     (arc(X,Y), 
     Arc = arc(X,Y)) 
    ; (arc(Y,X), 
     Arc = arc(Y,X)). 

（假设为数据库arc(a,b)）：

6 ?- cv_arc(a,b,A). 
    A = arc(a, b). 

    7 ?- cv_arc(b,a,A). 
    A = arc(a, b). 

    8 ?- cv_arc(b,c,A). 
    false. 

当然，你需要遵循类似的原则为其余的对象;我假设你正在做这样的事情找一个矩形：由于电弧

rectangle(A,B,C,D):- 
    arc(A,B), 
    arc(B,C), 
    arc(C,D), 
    arc(D,A). 

除了重复的（这是解决），这将承认ABCD，DABC等不同的矩形：

28 ?- rectangle(A,B,C,D). 
A = a, 
B = b, 
C = c, 
D = d ; 
A = b, 
B = c, 
C = d, 
D = a ; 
A = c, 
B = d, 
C = a, 
D = b ; 
A = d, 
B = a, 
C = b, 
D = c. 

我们将再次做同样的：

rectangle(rectangle(A,B,C,D)):- 
    cv_arc(A,B,AB), 
    cv_arc(B,C,BC), 
    compare(<,AB,BC), 
    cv_arc(C,D,CD), 
    compare(<,BC,CD), 
    cv_arc(D,A,DA), 
    compare(<,CD,DA). 

和运行与arc(a,b). arc(b,c). arc(c,d). arc(a,d).：

27 ?- rectangle(R). 
R = rectangle(a, b, c, d) ; 
false. 

请注意，如果弧的顺序错误，我们没有重新排列矩形;我们只是失败了。这样我们就避免了重复的解决方案（如果我们命令它们并将它作为有效的矩形接受，我们将有相同的矩形四次），但是找到矩形的时间增加了。我们通过停止搜索第一个无序的弧而不是创建整个矩形来减少开销。另外，如果订购电弧，开销也会减少（因为第一次匹配会被排序）。另一方面，如果我们考虑以这种方式搜索所有矩形的复杂性，那么开销并不那么重要。此外，它只适用于我们只需要第一个矩形;如果我们想要获得更多解决方案或确保没有其他解决方案，prolog会搜索整棵树，无论它是否报告解决方案。