Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/graphs/subgraph.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/graphs/subgraph.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 411, Fri Sep 3 00:25:03 1999 UTC revision 429, Wed Sep 8 09:47:00 1999 UTC
# Line 18  Line 18 
18  struct  struct
19    
20     structure G = Graph     structure G = Graph
    structure Set = HashSet  
21    
22     fun subgraph_view nodes edge_pred (G.GRAPH G) =     fun subgraph_view nodes edge_pred (G.GRAPH G) =
23     let val set  = Set.create{order=Int.compare,hash=fn i=>i} 10     let val set  = Intmap.new(32,G.NotFound)
24         val ins  = Set.insert set         val ins  = Intmap.add set
25         val rmv  = Set.remove set         val ins  = fn i => ins (i,true)
26         val find = Set.contains set         val rmv  = Intmap.rmv set
27           val find = Intmap.mapWithDefault (set,false)
28    
29         val _    = app ins nodes         val _    = app ins nodes
30         fun edge_p (e as (i,j,_)) = find i andalso find j andalso edge_pred e         fun edge_p (e as (i,j,_)) = find i andalso find j andalso edge_pred e
31         fun check i = if find i then () else raise G.Subgraph         fun check i = if find i then () else raise G.Subgraph
# Line 36  Line 37 
37             (check i; app check_edge es; #set_out_edges G (i,es))             (check i; app check_edge es; #set_out_edges G (i,es))
38         fun set_in_edges (j,es) =         fun set_in_edges (j,es) =
39             (check j; app check_edge es; #set_in_edges G (j,es))             (check j; app check_edge es; #set_in_edges G (j,es))
40         fun get_nodes () = Set.fold (fn (i,l) => (i,#node_info G i)::l) [] set         fun get_nodes () = map (fn (i,_) => (i,#node_info G i))
41                                (Intmap.intMapToList set)
42         fun get_edges () =         fun get_edges () =
43         let fun find_edges([],l) = l         let fun find_edges([],l) = l
44               | find_edges(e::es,l) =               | find_edges(e::es,l) =
45                   if edge_p e then find_edges(es,e::l) else find_edges(es,l)                   if edge_p e then find_edges(es,e::l) else find_edges(es,l)
46         in  Set.fold (fn (i,l) => find_edges(#out_edges G i,l)) [] set         in  foldr (fn ((i,_),l) => find_edges(#out_edges G i,l)) []
47                   (Intmap.intMapToList set)
48         end         end
49         fun order () = Set.size set         fun order () = Intmap.elems set
50         fun size  () =         fun size  () =
51         let fun find_edges([],n) = n         let fun find_edges([],n) = n
52               | find_edges(e::es,n) =               | find_edges(e::es,n) =
53                   if edge_p e then find_edges(es,n+1) else find_edges(es,n)                   if edge_p e then find_edges(es,n+1) else find_edges(es,n)
54         in  Set.fold (fn (i,n) => find_edges(#out_edges G i,n)) 0 set         in  foldr (fn ((i,_),n) => find_edges(#out_edges G i,n)) 0
55                  (Intmap.intMapToList set)
56         end         end
57         fun out_edges i = (List.filter edge_p (#out_edges G i))         fun out_edges i = (List.filter edge_p (#out_edges G i))
58         fun in_edges i  = (List.filter edge_p (#in_edges G i))         fun in_edges i  = (List.filter edge_p (#in_edges G i))
# Line 62  Line 66 
66                                         (#in_edges G i))                                         (#in_edges G i))
67         fun exit_edges i = (List.filter(fn (_,j,_) => not(find j))         fun exit_edges i = (List.filter(fn (_,j,_) => not(find j))
68                                         (#out_edges G i))                                         (#out_edges G i))
69         fun entries() =  Set.fold (fn (i,l) =>         fun entries() =  foldr (fn ((i,_),l) =>
70                             if List.exists (fn (j,_,_) => not(find j))                             if List.exists (fn (j,_,_) => not(find j))
71                                  (#in_edges G i) then i::l else l) [] set                                  (#in_edges G i) then i::l else l) []
72         fun exits() =  Set.fold (fn (i,l) =>                              (Intmap.intMapToList set)
73           fun exits() =  foldr (fn ((i,_),l) =>
74                             if List.exists (fn (_,j,_) => not(find j))                             if List.exists (fn (_,j,_) => not(find j))
75                                  (#out_edges G i) then i::l else l) [] set                                  (#out_edges G i) then i::l else l) []
76         fun forall_nodes f = Set.app (fn i => f(i,#node_info G i)) set                                (Intmap.intMapToList set)
77         fun forall_edges f = Set.app (fn i => app (fn e =>         fun forall_nodes f = Intmap.app (fn (i,_) => f(i,#node_info G i)) set
78           fun forall_edges f = Intmap.app (fn (i,_) => app (fn e =>
79                                                    if edge_p e then f e else ())                                                    if edge_p e then f e else ())
80                                               (#out_edges G i)) set                                               (#out_edges G i)) set
81     in     in

Legend:
Removed from v.411  
changed lines
  Added in v.429

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0