|
From: Vitor S. C. <vs...@us...> - 2008-06-26 13:09:14
|
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). |