1/* $Id$ 2 3 Part of CLP(Q) (Constraint Logic Programming over Rationals) 4 5 Author: Leslie De Koninck 6 E-mail: Leslie.DeKoninck@cs.kuleuven.be 7 WWW: http://www.swi-prolog.org 8 http://www.ai.univie.ac.at/cgi-bin/tr-online?number+95-09 9 Copyright (C): 2006, K.U. Leuven and 10 1992-1995, Austrian Research Institute for 11 Artificial Intelligence (OFAI), 12 Vienna, Austria 13 14 This software is based on CLP(Q,R) by Christian Holzbaur for SICStus 15 Prolog and distributed under the license details below with permission from 16 all mentioned authors. 17 18 This program is free software; you can redistribute it and/or 19 modify it under the terms of the GNU General Public License 20 as published by the Free Software Foundation; either version 2 21 of the License, or (at your option) any later version. 22 23 This program is distributed in the hope that it will be useful, 24 but WITHOUT ANY WARRANTY; without even the implied warranty of 25 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 26 GNU General Public License for more details. 27 28 You should have received a copy of the GNU Lesser General Public 29 License along with this library; if not, write to the Free Software 30 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 31 32 As a special exception, if you link this library with other files, 33 compiled with a Free Software compiler, to produce an executable, this 34 library does not by itself cause the resulting executable to be covered 35 by the GNU General Public License. This exception does not however 36 invalidate any other reasons why the executable file might be covered by 37 the GNU General Public License. 38*/ 39 40:- module(clpcd_combine, 41 [ 42 combine/3, 43 normalize/2 44 ]). 45 46% combine(Ga,Gb,Gc) 47% 48% Combines the vertices of Ga and Gb into Gc. 49 50combine(Ga,Gb,Gc) :- 51 normalize(Ga,Gan), 52 normalize(Gb,Gbn), 53 ugraph_union(Gan,Gbn,Gc). 54 55% 56% both Ga and Gb might have their internal ordering invalidated 57% because of bindings and aliasings 58% 59 60normalize([],[]) :- !. 61normalize(G,Gsgn) :- 62 G = [_|_], 63 keysort(G,Gs), % sort vertices on key 64 group(Gs,Gsg), % concatenate vertices with the same key 65 normalize_vertices(Gsg,Gsgn). % normalize 66 67normalize_vertices([],[]). 68normalize_vertices([X-Xnb|Xs],Res) :- 69 ( normalize_vertex(X,Xnb,Xnorm) 70 -> Res = [Xnorm|Xsn], 71 normalize_vertices(Xs,Xsn) 72 ; normalize_vertices(Xs,Res) 73 ). 74 75% normalize_vertex(X,Nbs,X-Nbss) 76% 77% Normalizes a vertex X-Nbs into X-Nbss by sorting Nbs, removing duplicates (also of X) 78% and removing non-vars. 79 80normalize_vertex(X,Nbs,X-Nbsss) :- 81 var(X), 82 sort(Nbs,Nbss), 83 strip_nonvar(Nbss,X,Nbsss). 84 85% strip_nonvar(Nbs,X,Res) 86% 87% Turns vertext X-Nbs into X-Res by removing occurrences of X from Nbs and removing 88% non-vars. This to normalize after bindings have occurred. See also normalize_vertex/3. 89 90strip_nonvar([],_,[]). 91strip_nonvar([X|Xs],Y,Res) :- 92 ( X==Y % duplicate of Y 93 -> strip_nonvar(Xs,Y,Res) 94 ; var(X) % var: keep 95 -> Res = [X|Stripped], 96 strip_nonvar(Xs,Y,Stripped) 97 ; % nonvar: remove 98 nonvar(X), 99 Res = [] % because Vars<anything 100 ). 101 102% group(Vert,Res) 103% 104% Concatenates vertices with the same key. 105 106group([],[]). 107group([K-Kl|Ks],Res) :- 108 group(Ks,K,Kl,Res). 109 110group([],K,Kl,[K-Kl]). 111group([L-Ll|Ls],K,Kl,Res) :- 112 ( K==L 113 -> append(Kl,Ll,KLl), 114 group(Ls,K,KLl,Res) 115 ; Res = [K-Kl|Tail], 116 group(Ls,L,Ll,Tail) 117 )