1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2% 3% FILE: Env/libgraph.pl 4% 5% Author : Sebastian Sardina 6% Time-stamp: <03/12/26 20:05:04 ssardina> 7% email : ssardina@cs.toronto.edu 8% WWW : www.cs.toronto.edu/~ssardina 9% TESTED : SWI Prolog 5.0.10 http://www.swi-prolog.org 10% ECLiPSe 5.3 on RedHat Linux 6.2-7.2 11% TYPE CODE : system independent predicates 12% 13% DESCRIPTION: Library for implementing graphs 14% 15% This file provides primitive 16% 17%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 18% 19% December 26, 2003 20% 21% This software was developed by the Cognitive Robotics Group under the 22% direction of Hector Levesque and Ray Reiter. 23% 24% Do not distribute without permission. 25% Include this notice in any copy made. 26% 27% 28% Copyright (c) 2000 by The University of Toronto, 29% Toronto, Ontario, Canada. 30% 31% All Rights Reserved 32% 33% Permission to use, copy, and modify, this software and its 34% documentation for non-commercial research purpose is hereby granted 35% without fee, provided that the above copyright notice appears in all 36% copies and that both the copyright notice and this permission notice 37% appear in supporting documentation, and that the name of The University 38% of Toronto not be used in advertising or publicity pertaining to 39% distribution of the software without specific, written prior 40% permission. The University of Toronto makes no representations about 41% the suitability of this software for any purpose. It is provided "as 42% is" without express or implied warranty. 43% THE UNIVERSITY OF TORONTO DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS 44% SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND 45% FITNESS, IN NO EVENT SHALL THE UNIVERSITY OF TORONTO BE LIABLE FOR ANY 46% SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER 47% RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF 48% CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 49% CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 50% 51%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 52% 53% Primitive actions are called using perform/3: 54% 55% -- perform(CommandList) 56% CommandL is a list-char codifying the command to be executed 57% 58% OBS: If ActionT is the term containing the primitive action to be 59% called, your code using internet.pl should do something like this: 60% 61% term_to_atom(perform(ActionT), ActionA), % Convert into a list-chars 62% concat_atom(['eclipse -b ', Dir, 'lib/internet.pl -e ','\'', 63% ActionA,'\''], Command), 64% exec(Command). 65% 66% or issue the shell comamnd: 67% 68% eclipse -b <path>/internet.pl -e 'perform(<ActionAsListChar>' 69% 70% 71% The following low-level internet/system primitive actions are provided 72% (i.e., they are legal commands to be used with perform/1) 73% 74% -- browser_new(+ID) 75% create a new web browser called IdWeb 76% -- browser_close(+ID) 77% remove web browser IdWeb 78% -- browser_refresh(+ID) 79% refresh content of URL 80% -- browser_open(+ID, +URL) 81% set browser IdWeb to URL 82% 83% -- check_string_after(+URL, +S, +PAfter) 84% sense whether there is a string S in in address A after pos PAfter 85% -- check_pos_string(+A, +S, +PAfter) 86% sense the position in address A of string S after position PAfter 87% -- read_string_between(+A, +D1, +D2, +PAfter): 88% sense the string between D1 and D2 in address A after pos PAfter 89% -- read_string_length(+URL, +D, +L, +PAfter): 90% sense the string in address A that starts with string D for 91% a length of L and after position PAfter 92% -- read_html_field(+URL, +FieldName, +Cont, +PAfter): 93% sense the next string value of field FieldName after position PAfter 94% that includes string Cont 95% -- download(+URL, +File) 96% download address URL to file File sense the process id number 97% -- check_web_file(+URL) 98% senses whether WebFile exists 99% 100% -- sense_proc_term(+Pid) 101% senses whether process Pid is finished 102% -- kill_proc(+Pid) 103% kills process Pid 104% -- wait_proc(+Pid) 105% waits for process Pid to finish 106% -- sense_proc_exists(+Pid) 107% sesnes whether process Pid exists 108% -- sense_file_exists(+File) 109% senses whether file File exists 110% -- say(+Phrase, +Language) 111% speak Phrase in Language (requires a voice synthesis 112% like festival) 113% 114% The following actions may generate the following exogenous actions: 115% 116% -- int_bool_after(URL, String, PAfter, Bool) : 117% Bool=there is String after PAfter in URL 118% -- int_pos(URL, String, PAfter, Pos) : 119% Pos=the next String after PAfter in URL is at position Pos 120% -- int_string_between(URL, Del1, Del2, PAfter, String) : 121% String=string between Del1 and Del2 in URL after PAfter 122% -- int_string_length(URL, Del, Lenght, PAfter, String) : 123% String=string after Del1 of length Length in URL after PAfter 124% -- int_html_field(URL, FieldName, PAfter, String, Pos) : 125% String=value of field FieldName containing Cont in URL after PAfter 126% Pos=starting postition of String 127% -- int_bool_download(URL, File, Status) : 128% Downloading of URL to File finished with Status (ok/failed) 129% -- int_bool_urlexists(URL, Bool) : 130% Bool= URL exists 131% -- int_proc_waited(Pid, Status) 132% Status = result of waiting process Pid (may be failed) 133% 134% 135% REQUIRED: 136% 137% -- compat_swi/compat_ecl compatibility libraries 138%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 139:- module(libgraph, 140 [getNode/2, 141 getNEdge/4, 142 getEdge/4, 143 % 144 add_node/3, 145 add_edges/3, 146 add_edge/3, 147 add_nedges/3, 148 remove_node/3, 149 remove_edges/3, 150 remove_nedges/3, 151 combine_nodes/4, 152 % 153 path_graph_short/5, 154 path_graph/5, 155 % 156 sub_graph/3 157 ]). 158 159 160%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 161% GRAPH REPRESENTATION 162%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 163 164% A GRAPH HAS THE FOLLOWING STRUCTURE: 165% graph(Nodes, Edges) or graph(Nodes, Edges, NEdges) WHERE: 166% 167% - Nodes is a list of nodes, e.g., Nodes=[station(1),station(2),station(3)] 168% 169% - Edges is a list of edges of the form "edge(Node1,Node2,Annot)" 170% where Node1, Node2 are nodes and Annot is any anottation 171% e.g., edge(station(1),station(2),north) 172% 173% - NEdges describes the edges that are NOT present in the graph 174% (this is used to specify incompletely defined graphs) 175 176 177 178 179%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 180% QUERY TOOLS 181%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 182 183% There is an edge in the graph from X to Y with annotation A 184getEdge(X,Y,A,graph(Nodes,Edges)):- getEdge(X,Y,A,graph(Nodes,Edges,[])). 185getEdge(X,Y,A,graph(_,Edges,_)) :- member(edge(X,Y,A), Edges). 186 187% There is an nedge in the graph from X to Y with annotation A 188getNEdge(X,Y,A,graph(_,_,NEdges)) :- member(edge(X,Y,A), NEdges). 189 190% N is a node in the graph 191getNode(N,graph(Nodes,_)) :- getNode(N,graph(Nodes,_,_,[])). 192getNode(N,graph(Nodes,_,_)) :- member(N,Nodes). 193 194 195 196%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 197% PRIMITIVE DYNAMIC OPERATIONS ON A GRAPH (ADD AND REMOVE NODES/EDGES) 198%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 199 200% 201% Add a node N to a graph 202% 203add_node(N, graph(Nodes,Edges,NEdges), graph([N|Nodes],Edges,NEdges)). 204add_node(N, graph(Nodes,Edges), graph([N|Nodes],Edges)). 205 206% 207% Add a list of edges to a graph 208% 209add_edges([], G, G) :- !. 210add_edges([edge(X,Y,D)|Tail], G, GN) :- 211 \+ getEdge(X,Y,D,G), !, 212 add_edge(edge(X,Y,D),G,G2), % Add this single edge 213 add_edges(Tail, G2, GN). 214add_edges([_|Tail], G, GN) :- !, add_edges(Tail, G, GN). 215 216% Add one edge to a graph 217add_edge(E, graph(Nodes,Edges), graph(Nodes,[E|Edges])). 218add_edge(E, graph(Nodes,Edges,NEdges), graph(Nodes,[E|Edges],NEdges)). 219 220add_nedges([], G, G) :- !. 221add_nedges([edge(X,Y,D)|Tail], G, GN) :- 222 \+ getNEdge(X,Y,D,G), !, 223 add_nedge(edge(X,Y,D),G,G2), % Add this signle edge 224 add_nedges(Tail, G2, GN). 225add_nedge([_|Tail], G, GN) :- !, add_nedges(Tail, G, GN). 226 227% Add one nedge to a graph 228add_nedge(NE, graph(Nodes,Edges,NEdges), graph(Nodes,Edges,[NE|NEdges])). 229 230 231% 232% Remove node N from a graph (i.e., remove node and all its edges) 233% 234remove_node(N, G, GN) :- 235 remove_edges([edge(N,_,_),edge(_,N,_)], G, G2), 236 remove_nedges([edge(N,_,_),edge(_,N,_)], G2, G3), 237 delete_node(N, G3, GN). 238 239delete_node(N,graph(Nodes,Edges), graph(Nodes2, Edges)) :- 240delete_node(N,graph(Nodes,Edges,[]), graph(Nodes2, Edges,_)). 241delete_node(N,graph(Nodes,Edges, NEdges), graph(Nodes2, Edges, NEdges)) :- 242 remove_element(Nodes, N, Nodes2). 243 244 245% 246% Remove a list of edges E from a graph 247% 248remove_edges(E, graph(Nodes, Edges), graph(Nodes, Edges2)) :- 249 remove_edges(E, graph(Nodes, Edges, []), graph(Nodes, Edges2, _)). 250remove_edges(E, graph(Nodes, Edges, NEdges), graph(Nodes, Edges2, NEdges)) :- 251 subtractvar(Edges, E, Edges2). 252remove_nedges(E, graph(Nodes, Edges, NEdges), graph(Nodes, Edges, NEdges2)) :- 253 subtractvar(NEdges, E, NEdges2). 254 255 256 257 258 259% 260% Combine nodes N1 and N2 in G into a single node N2. GNew is new combined graph 261% 262combine_nodes(N1,N2,G,GNew) :- 263 allSolutions(edge(N2,X,D), getEdge(N1,X,D,G), L1), 264 allSolutions(edge(X,N2,D), getEdge(X,N1,D,G), L2), 265 append(L1,L2,LE), % Edges that may have to be incorporated to node N2 266 % 267 allSolutions(edge(N2,X,D), getNEdge(N1,X,D,G), LN1), 268 allSolutions(edge(X,N2,D), getNEdge(X,N1,D,G), LN2), 269 append(LN1,LN2,LNE), % NEdges that may have to be incorporated to node N2 270 % 271 remove_node(N1,G,G2), % Remove node N1 272 add_edge(LE, G2, G3), 273 add_nedge(LNE, G3, GNew). 274 275 276%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 277% PATH COMPUTATIONS 278%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 279 280% A PATH is a sequence (list) of node names. 281% e.g., [station(1),station(5),station(6),station(2)] is a path 282% from station(1) to station(2) 283 284% P is the shortest path in G from X to Y (and with length less than Limit) 285path_graph_short(X, Y, G, Limit, P) :- path_graph_short(X,Y,G,0,Limit, P). 286 287path_graph_short(X,X,_,0,[]) :- fail, !. 288path_graph_short(X,Y,G,N,_,P) :- path_graph(X,Y,G,N,P). 289path_graph_short(X,Y,G,N,L,P) :- 290 L2 is L-1, N2 is N+1, path_graph_short(X,Y,G,N2,L2,P). 291 292% path_graph(X, Y, G, L, P): P is a path of length L from X to Y in graph G 293path_graph(X, Y, graph(_,E), L, Path) :- 294 path_graph(X, Y, graph(_,E,[]), L, Path). 295path_graph(Y, X, graph(_,E,_), L, [Y|LV]) :- 296 length(LV, L), % Build a list LV of variables of length L 297 path1_graph(E, X, [Y|LV]). 298 299path1_graph(_, X, [X]). 300path1_graph(E, X, [Y | Path1]) :- 301 member(edge(Z,Y,_), E), % We can go from Y to Z with an edge in E 302% append(GList, VList, Path1), 303% ground(GList), 304% \+ member(Z, Path1), 305 Path1=[Z|_], 306 path1_graph(E, X, Path1). 307 308 309 310 311%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 312% SUBGRAPH COMPUTATION 313%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 314 315% sub_graph(G1, G2, Map): 316% the (possibly) incomplete graph G2 is an exact subgraph of G1 under mapping Map 317sub_graph(graph(_, Edges1), G2, Map) :- 318 abstract_graph(G2, graph(_,AEdges2, ANEdges2), Map), 319 sublist(AEdges2, Edges1), 320 \+ (member(E, ANEdges2), member(E, Edges1)). 321 322 323% abstract_graph(G, AG, Map): 324% AG is a (variable) abstraction graph of a concrete graph G. 325% An abstraction graph results from replacing each node with a unique variable 326% Map = list of (X,N) where X is a node in AG and N is a node in G, X-->N 327abstract_graph(graph(Nodes,Edges), graph(ANodes,AEdges,ANEdges), Map) :- 328 abstract_graph(graph(Nodes,Edges,[]), graph(ANodes,AEdges,ANEdges), Map). 329abstract_graph(graph([],Edges,NEdges), graph([],Edges,NEdges), []). 330abstract_graph(graph([N|R],Edges,NEdges),graph([X|RA],EdgesA,NEdgesA),[(X,N)|Map]):- 331 abstract_node(N,X,Edges,Edges2), 332 abstract_node(N,X,NEdges,NEdges2), 333 abstract_graph(graph(R,Edges2,NEdges2), graph(RA, EdgesA,NEdgesA), Map). 334 335% abstract_node(+N,-X,+Edges,-EdgesA): 336% EdgesA is Edges with all ground node N replaced by variable X 337abstract_node(_,_,[],[]). 338abstract_node(N,X,[edge(S,D,A)|R],[edge(X,D,A)|RA]) :- 339 S==N, !, 340 abstract_node(N,X,R,RA). 341abstract_node(N,X,[edge(S,D,A)|R],[edge(S,X,A)|RA]) :- 342 D==N, !, 343 abstract_node(N,X,R,RA). 344abstract_node(N,X,[edge(S,D,A)|R],[edge(S,D,A)|RA]) :- 345 abstract_node(N,X,R,RA). 346 347 348 349 350 351 352%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 353% OTHER TOOLS 354%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 355 356 357% Like setof/3 but returns an empty list of G fails 358allSolutions(T, G, L) :- setof(T,G,L) -> true ; L=[]. 359 360 361% A version of substract/3 in SWI that deals with variables as elements 362substractvar(L1,[],L1). 363substractvar(L1,[E|Tail],L2) :- 364 remove_element(L1,E,L3), 365 substractvar(L3,Tail,L2). 366 367% Remove all elements E from a list (handle variables in the list) 368remove_element([],_,[]). 369remove_element([X|L1],E,L2) :- 370 E==X, !, 371 remove_element(L1,E,L2). 372remove_element([X|L1],E,[X|L2]) :- 373 remove_element(L1,E,L2). 374 375 376 377%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 378% EOF: lib/libgraph.pl 379%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%