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/trunk/src/MLRISC/graphs/acyclic-graph.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/graphs/acyclic-graph.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 412 - (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