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

# SCM Repository

[smlnj] View of /sml/branches/idlbasis-devel/src/MLRISC/graphs/acyclic-graph.sml
 [smlnj] / sml / branches / idlbasis-devel / src / MLRISC / graphs / acyclic-graph.sml # View of /sml/branches/idlbasis-devel/src/MLRISC/graphs/acyclic-graph.sml

Sat Apr 17 18:47:12 1999 UTC (21 years, 1 month ago) by monnier
Original Path: sml/branches/SMLNJ/src/MLRISC/graphs/acyclic-graph.sml
File size: 850 byte(s)
```version 110.16
```
```(*
*)

signature ACYCLIC_SUBGRAPH_VIEW =
sig

(* Acyclic node induced subgraph *)
val acyclic_view : Graph.node_id list ->
('n,'e,'g) Graph.graph ->
('n,'e,'g) Graph.graph
end

structure AcyclicSubgraphView : ACYCLIC_SUBGRAPH_VIEW =
struct

structure G = Graph
structure A = HashArray
structure S = Subgraph_P_View

fun acyclic_view nodes (G as G.GRAPH g) =
let val ord = A.array(#capacity g (),~1)
fun order(i,[]) = ()
| order(i,n::ns) = (A.update(ord,n,i); order(i+1,ns))
val _ = order(0,nodes)
fun node_p i = A.sub(ord,i) >= 0
fun edge_p (i,j) =
let val i = A.sub(ord,i)
in  i >= 0 andalso i < A.sub(ord,j) end
in  S.subgraph_p_view nodes node_p edge_p G
end

end

(*
* \$Log\$
*)
```