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 743, Thu Dec 7 15:31:24 2000 UTC revision 744, Fri Dec 8 04:11:42 2000 UTC
# Line 20  Line 20 
20     structure G   = Graph     structure G   = Graph
21    
22     fun subgraph_view nodes edge_pred (G.GRAPH G) =     fun subgraph_view nodes edge_pred (G.GRAPH G) =
23     let val set  = Intmap.new(32,G.NotFound)     let val set  = IntHashTable.mkTable(32,G.NotFound)
24         val ins  = Intmap.add set         val ins  = IntHashTable.insert set
25         val ins  = fn i => ins (i,true)         val ins  = fn i => ins (i,true)
26         val rmv  = Intmap.rmv set         fun rmv r = (IntHashTable.remove set r; ()) handle _ => ()
27         val find = Intmap.mapWithDefault (set,false)         fun find r = getOpt(IntHashTable.find set r,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
# Line 38  Line 38 
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 () = map (fn (i,_) => (i,#node_info G i))         fun get_nodes () = map (fn (i,_) => (i,#node_info G i))
41                              (Intmap.intMapToList set)                              (IntHashTable.listItemsi 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  foldr (fn ((i,_),l) => find_edges(#out_edges G i,l)) []         in  foldr (fn ((i,_),l) => find_edges(#out_edges G i,l)) []
47                 (Intmap.intMapToList set)                 (IntHashTable.listItemsi set)
48         end         end
49         fun order () = Intmap.elems set         fun order () = IntHashTable.numItems 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  foldr (fn ((i,_),n) => find_edges(#out_edges G i,n)) 0         in  foldr (fn ((i,_),n) => find_edges(#out_edges G i,n)) 0
55                (Intmap.intMapToList set)                (IntHashTable.listItemsi 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 69  Line 69 
69         fun entries() =  foldr (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) []                                  (#in_edges G i) then i::l else l) []
72                              (Intmap.intMapToList set)                              (IntHashTable.listItemsi set)
73         fun exits() =  foldr (fn ((i,_),l) =>         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) []                                  (#out_edges G i) then i::l else l) []
76                                (Intmap.intMapToList set)                                (IntHashTable.listItemsi set)
77         fun forall_nodes f = Intmap.app (fn (i,_) => f(i,#node_info G i)) set         fun forall_nodes f = IntHashTable.appi (fn (i,_) => f(i,#node_info G i)) set
78         fun forall_edges f = Intmap.app (fn (i,_) => app (fn e =>         fun forall_edges f = IntHashTable.appi (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.743  
changed lines
  Added in v.744

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