路径/步道/步行的定义 [英] Definition of a path/trail/walk

问题描述

许多谓词定义了一些非循环路径，这些路径是通过二元关系定义的边构建的，与定义传递闭包。因此需要一个通用的定义。

请注意，图论中定义的概念并不容易与通常所期望的相符。最显着的是，我们对边缘的名字不感兴趣。

更糟糕的是，图论也发生了一些变化，引入了散步，注意到

传统上，一条路径指的是现在通常所说的开放式散步。如今，当没有任何资格时，通常认为路径很简单，意味着没有顶点（并且因此没有边）被重复。 （术语链也被用来指所有顶点和边都不同的步行）。

所以我的问题是：如何命名和定义这个功能？

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

  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路径（2，？，？，？）。 
 
： -  meta_predicate路径（2，？，？，？，+）。 
 
 path（R_2，[X0 | Ys]，X0，X）： -  
 path（R_2，Ys，X0，X，[X0]）。 
 
路径（_R_2，[]，X，X，_）。 
路径（R_2，[X1 | Ys]，X0，X，Xs）： -  
 call（R_2，X0，X1），
 non_member（X1，Xs），
路径（R_2，Ys，X1，X，[X1 | Xs]）。 
 
 non_member（_E，[]）。 
 non_member（E，[X | Xs]）： -  
 dif（E，X），
 non_member（E，Xs）。 
  

解决方案

我想专注于命名谓词。 p>

• 与 maplist / 2 ，
  这里的参数顺序并不重要。

名称应使相应参数的含义清晰。




到目前为止，我喜欢 path_from_to_edges 最好，但它也有其优点和缺点。
$ b

  path_from_to_edges（Path，From，To，Edges_2）： -  
 path（Edges_2，Path，From，To） 。 
  

让我们把它分开：






• 亲：路径是一个名词，它不能误读一个动词。对我来说，隐含了一个顶点列表。

至。



• con：边 有点含糊，但使用 lambda表达式这里是最通用的选择。 根据维基百科，一条路径是所有顶点（除了可能是第一个和最后一个 ）都不同的路径。所以需要在说明中加以说明。

使用 lambda表示邻居顶点列表 Ess ：

 ？ -  Ess = [a- [b]，b- [c，a]]，
 From = a，
 path_from_to_edges（Path，From，To，\ X ^ Y ^（member（X-X_neibs，Ess ），构件（Y，X_neibs）））。 
 Ess = [a- [b]，b- [c，a]]，From = a，To = a，Path = [a]; 
 Ess = [a- [b]，b- [c，a]]，From = a，To = b，Path = [a，b]; 
 Ess = [a- [b]，b- [c，a]]，From = a，To = c，Path = [a，b，c]; 
 false。 
  





---





编辑2015-06-02





另一个更好的命名！这更倾向于 maplist / 2 ...

  graph_path_from_to（P_2，Path，From，To）： -  
 path（P_2，Path，From，To）。 
  

当然，图一个名词，而不是动词。





关于path的含义：路径绝对应该允许 From = To 并且不会排除这种情况（使用两两的不等式）。使用额外的 dif（From，To）目标很容易排除这个问题，但不能相反。




Many predicates define some kind of an acyclic path built from edges defined via a binary relation, quite similarly to defining transitive closure. A generic definition is thus called for.

Note that the notions defined in graph theory do not readily match what is commonly expected. Most notably, we are not interested in the edges' names.

Worse, also graph theory has changed a bit, introducing the notion of walk, noting

Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated. (The term chain has also been used to refer to a walk in which all vertices and edges are distinct.)

So my question is: How to name and define this functionality?

What I have done so far is to define:

path(Rel_2, Path, X0,X)

The first argument has to be the continuation of the relation. Then comes either the Path or the pair of vertices.

Example usage

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.

Implementation

:- 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, Ys, X1,X, [X1|Xs]).

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

解决方案

I want to focus on naming the predicate.

• Unlike maplist/2, the argument order isn't of primary importance here.

• The predicate name should make the meaning of the respective arguments clear.

So far, I like path_from_to_edges best, but it has its pros and cons, too.

path_from_to_edges(Path,From,To,Edges_2) :-
    path(Edges_2,Path,From,To).

Let's pick it apart:

• pro: path is a noun, it cannot be mis-read a verb. To me, a list of vertices is implied.

• pro: from stands for a vertex, and so does to.

• con: edges is somewhat vague, but using lambdas here is the most versatile choice.

• con: According to Wikipedia, a path is a trail in which all vertices (except possibly the first and last) are distinct. So that would need to be clarified in the description.

---

Using lambdas for a lists of neighbor vertices Ess:

?- Ess  = [a-[b],b-[c,a]], 
   From = a,
   path_from_to_edges(Path,From,To,\X^Y^(member(X-X_neibs,Ess),member(Y,X_neibs))).
Ess = [a-[b],b-[c,a]], From = a, To = a, Path = [a]     ;
Ess = [a-[b],b-[c,a]], From = a, To = b, Path = [a,b]   ;
Ess = [a-[b],b-[c,a]], From = a, To = c, Path = [a,b,c] ;
false.

---

Edit 2015-06-02

Another shot at better naming! This leans more on the side of maplist/2...

graph_path_from_to(P_2,Path,From,To) :-
   path(P_2,Path,From,To).

Here, graph, of course, is a noun, not a verb.

Regarding the meaning of "path": paths definitely should allow From=To and not exclude that by default (with pairwise term inequalities). It is easy to exclude this with an additional dif(From,To) goal, but not the other way round.

这篇关于路径/步道/步行的定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！