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

# SCM Repository

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

# Annotation of /sml/branches/idlbasis-devel/src/MLRISC/graphs/acyclic-graph.sml

Revision 848 - (view) (download)

 1 : monnier 245 (* 2 : monnier 411 * Acyclic subgraph adaptor. This takes a linear order of node id 3 : * return a view in which only the edges (and nodes) consistent with 4 : * the linear order is visible. 5 : * 6 : * -- Allen 7 : monnier 245 *) 8 : 9 : signature ACYCLIC_SUBGRAPH_VIEW = 10 : sig 11 : 12 : (* Acyclic node induced subgraph *) 13 : val acyclic_view : Graph.node_id list -> 14 : ('n,'e,'g) Graph.graph -> 15 : ('n,'e,'g) Graph.graph 16 : end 17 : 18 : structure AcyclicSubgraphView : ACYCLIC_SUBGRAPH_VIEW = 19 : struct 20 : 21 : structure G = Graph 22 : structure A = HashArray 23 : structure S = Subgraph_P_View 24 : 25 : fun acyclic_view nodes (G as G.GRAPH g) = 26 : let val ord = A.array(#capacity g (),~1) 27 : fun order(i,[]) = () 28 : | order(i,n::ns) = (A.update(ord,n,i); order(i+1,ns)) 29 : val _ = order(0,nodes) 30 : fun node_p i = A.sub(ord,i) >= 0 31 : fun edge_p (i,j) = 32 : let val i = A.sub(ord,i) 33 : in i >= 0 andalso i < A.sub(ord,j) end 34 : in S.subgraph_p_view nodes node_p edge_p G 35 : end 36 : 37 : end 38 :

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