[Yap-commits] CVS: library dgraphs.yap, 1.9, 1.10 undgraphs.yap, 1.5, 1.6 wdgraphs.yap, 1.3, 1.4 wundgraphs.yap, 1.4, 1.5

[Vitor S. C. <vs...@us...>]

Update of /cvsroot/yap/library
In directory sc8-pr-cvs10.sourceforge.net:/tmp/cvs-serv14577/library

Modified Files:
	dgraphs.yap undgraphs.yap wdgraphs.yap wundgraphs.yap 
Log Message:
improve graphs a bit.


Index: dgraphs.yap
===================================================================
RCS file: /cvsroot/yap/library/dgraphs.yap,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- dgraphs.yap	26 Mar 2008 14:41:44 -0000	1.9
+++ dgraphs.yap	26 Jun 2008 13:09:15 -0000	1.10
@@ -5,17 +5,17 @@
 
 :- module( dgraphs,
 	   [
-	    dgraph_add_edge/4,
-	    dgraph_add_edges/3,
+	    dgraph_vertices/2,
+	    dgraph_edge/3,
+	    dgraph_edges/2,
 	    dgraph_add_vertex/3,
 	    dgraph_add_vertices/3,
-	    dgraph_del_edge/4,
-	    dgraph_del_edges/3,
 	    dgraph_del_vertex/3,
 	    dgraph_del_vertices/3,
-	    dgraph_edge/3,
-	    dgraph_edges/2,
-	    dgraph_vertices/2,
+	    dgraph_add_edge/4,
+	    dgraph_add_edges/3,
+	    dgraph_del_edge/4,
+	    dgraph_del_edges/3,
 	    dgraph_to_ugraph/2,
 	    ugraph_to_dgraph/2,
 	    dgraph_neighbors/3,
@@ -31,7 +31,8 @@
 	    dgraph_max_path/5,
 	    dgraph_min_paths/3,
 	    dgraph_isomorphic/4,
-	    dgraph_path/3]).
+	    dgraph_path/3,
+	    dgraph_reachable/3]).
 
 :- reexport(library(rbtrees),
 	[rb_new/1 as dgraph_new]).
@@ -191,7 +192,7 @@
 delete_edge(Edges0, V, Edges) :-
 	ord_del_element(Edges0, V, Edges).
 
-dgraph_del_vertices(G0, Vs, GF) -->
+dgraph_del_vertices(G0, Vs, GF) :-
 	sort(Vs,SortedVs),
 	delete_all(SortedVs, G0, G1),
 	delete_remaining_edges(SortedVs, G1, GF).
@@ -362,7 +363,7 @@
 
 dgraph_min_paths(V1, Graph, Paths) :-
 	dgraph_to_wdgraph(Graph, WGraph),
-	wdgraph_min_path(V1, WGraph, Paths).
+	wdgraph_min_paths(V1, WGraph, Paths).
 
 dgraph_path(V, G, [V|P]) :-
 	rb_lookup(V, Children, G),
@@ -403,3 +404,18 @@
 	rb_lookup(V1,NV1,Map),
 	rb_lookup(V2,NV2,Map),
 	translate_edges(Edges,Map,TEdges).
+
+dgraph_reachable(V, G, Edges) :-
+	rb_lookup(V, Children, G),
+	ord_list_to_rbtree([V-[]],Done0),
+	reachable(Children, Done0, _, G, Edges, []).
+
+reachable([], Done, Done, _, Edges, Edges).
+reachable([V|Vertices], Done0, DoneF, G, EdgesF, Edges0) :-
+	rb_lookup(V,_, Done0), !,
+	reachable(Vertices, Done0, DoneF, G, EdgesF, Edges0).
+reachable([V|Vertices], Done0, DoneF, G, [V|EdgesF], Edges0) :-
+	rb_lookup(V, Kids, G),
+	rb_insert(Done0, V, [], Done1),
+	reachable(Kids, Done1, DoneI, G, EdgesF, EdgesI),
+	reachable(Vertices, DoneI, DoneF, G, EdgesI, Edges0).

Index: undgraphs.yap
===================================================================
RCS file: /cvsroot/yap/library/undgraphs.yap,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- undgraphs.yap	26 Mar 2008 14:41:45 -0000	1.5
+++ undgraphs.yap	26 Jun 2008 13:09:15 -0000	1.6
@@ -29,7 +29,8 @@
 	    dgraph_vertices/2 as undgraph_vertices,
 	    dgraph_complement/2 as undgraph_complement,
 	    dgraph_symmetric_closure/2 as dgraph_to_undgraph,
-	    dgraph_edge/3 as undgraph_edge
+	    dgraph_edge/3 as undgraph_edge,
+	    dgraph_reachable/3 as undgraph_reachable
 	    ]).
 
 

Index: wdgraphs.yap
===================================================================
RCS file: /cvsroot/yap/library/wdgraphs.yap,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- wdgraphs.yap	5 Dec 2007 12:17:24 -0000	1.3
+++ wdgraphs.yap	26 Jun 2008 13:09:15 -0000	1.4
@@ -18,6 +18,8 @@
 	    dgraph_to_wdgraph/2,
 	    wdgraph_neighbors/3,
 	    wdgraph_neighbours/3,
+	    wdgraph_wneighbors/3,
+	    wdgraph_wneighbours/3,
 	    wdgraph_transpose/2,
 	    wdgraph_transitive_closure/2,
 	    wdgraph_symmetric_closure/2,
@@ -25,7 +27,8 @@
 	    wdgraph_min_path/5,
 	    wdgraph_min_paths/3,
 	    wdgraph_max_path/5,
-	    wdgraph_path/3]).
+	    wdgraph_path/3,
+	    wdgraph_reachable/3]).
 
 :- reexport(library(dgraphs),
 	    [dgraph_add_vertex/3 as wdgraph_add_vertex,
@@ -279,13 +282,19 @@
 	cvt_neighbs(WEs, Es).
 
 wdgraph_neighbors(V, WG, Neighbors) :-
-	rb_lookup(V, WG, EdgesList0),
+	rb_lookup(V, EdgesList0, WG),
 	cvt_wneighbs(EdgesList0, Neighbors).
 
 wdgraph_neighbours(V, WG, Neighbors) :-
-	rb_lookup(V, WG, EdgesList0),
+	rb_lookup(V, EdgesList0, WG),
 	cvt_wneighbs(EdgesList0, Neighbors).
 
+wdgraph_wneighbors(V, WG, Neighbors) :-
+	rb_lookup(V, Neighbors, WG).
+
+wdgraph_wneighbours(V, WG, Neighbors) :-
+	rb_lookup(V, Neighbors, WG).
+
 wdgraph_transpose(Graph, TGraph) :-
 	rb_visit(Graph, Edges),
 	rb_clone(Graph, TGraph, NewNodes),
@@ -433,3 +442,17 @@
 	wdgraph_to_dgraph(WG, G),
 	dgraph_path(V, G, P).
 
+wdgraph_reachable(V, G, Edges) :-
+	rb_lookup(V, Children, G),
+	ord_list_to_rbtree([V-[]],Done0),
+	reachable(Children, Done0, _, G, Edges, []).
+
+reachable([], Done, Done, _, Edges, Edges).
+reachable([V-_|Vertices], Done0, DoneF, G, EdgesF, Edges0) :-
+	rb_lookup(V,_, Done0), !,
+	reachable(Vertices, Done0, DoneF, G, EdgesF, Edges0).
+reachable([V-_|Vertices], Done0, DoneF, G, [V|EdgesF], Edges0) :-
+	rb_lookup(V, Kids, G),
+	rb_insert(Done0, V, [], Done1),
+	reachable(Kids, Done1, DoneI, G, EdgesF, EdgesI),
+	reachable(Vertices, DoneI, DoneF, G, EdgesI, Edges0).

Index: wundgraphs.yap
===================================================================
RCS file: /cvsroot/yap/library/wundgraphs.yap,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- wundgraphs.yap	3 Jun 2008 22:43:14 -0000	1.4
+++ wundgraphs.yap	26 Jun 2008 13:09:15 -0000	1.5
@@ -13,6 +13,8 @@
 	    wundgraph_edges/2,
 	    wundgraph_neighbors/3,
 	    wundgraph_neighbours/3,
+	    wundgraph_wneighbors/3,
+	    wundgraph_wneighbours/3,
 	    wdgraph_to_wundgraph/2,
 	    wundgraph_to_undgraph/2,
 	    wundgraph_min_tree/3,
@@ -32,7 +34,9 @@
 	    wdgraph_min_path/5 as wundgraph_min_path,
 	    wdgraph_min_paths/3 as wundgraph_min_paths,
 	    wdgraph_max_path/5 as wundgraph_max_path,
-	    wdgraph_path/3 as wundgraph_path]).
+	    wdgraph_path/3 as wundgraph_path,
+	    wdgraph_reachable/3 as wundgraph_reachable
+	   ]).
 
 :- use_module( library(wdgraphs),
 	   [
@@ -96,6 +100,25 @@
 wundgraph_neighbors(V,Vertices,Children) :-
 	wdgraph_neighbors(V,Vertices,Children0),
 	(
+	    wdel_me(Children0,V,Children)
+	->
+	    true
+	;
+	    Children = Children0
+	).
+
+wundgraph_wneighbours(V,Vertices,Children) :-
+	wdgraph_wneighbours(V,Vertices,Children0),
+	(
+	    wdel_me(Children0,V,Children)
+	->
+	    true
+	;
+	    Children = Children0
+	).
+wundgraph_wneighbors(V,Vertices,Children) :-
+	wdgraph_wneighbors(V,Vertices,Children0),
+	(
 	    del_me(Children0,V,Children)
 	->
 	    true
@@ -104,7 +127,7 @@
 	).
 
 del_me([], _, []).
-del_me([K-_|Children], K1, NewChildren) :-
+del_me([K|Children], K1, NewChildren) :-
 	( K == K1 ->
 	    Children = NewChildren
 	;
@@ -116,6 +139,19 @@
 	    compact(Children, MoreChildren)
 	).
 
+wdel_me([], _, []).
+wdel_me([K-A|Children], K1, NewChildren) :-
+	( K == K1 ->
+	    Children = NewChildren
+	;
+	    K @< K1 ->
+	    NewChildren = [K-A|ChildrenLeft],
+	    wdel_me(Children, K1, ChildrenLeft)
+	;
+	    NewChildren = [K-A|MoreChildren],
+	    compact(Children, MoreChildren)
+	).
+
 wundgraph_del_edge(Vs0,V1,V2,K,VsF) :-
 	wdgraph_del_edge(Vs0,V1,V2,K,Vs1),
 	wdgraph_del_edge(Vs1,V2,V1,K,VsF).