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

View of /MLRISC/trunk/graphs/acyclic-graph.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2126 - (download) (annotate)
Thu Nov 2 16:11:29 2006 UTC (12 years, 7 months ago) by blume
File size: 989 byte(s)
moved MLRISC to toplevel
(*
 * Acyclic subgraph adaptor.  This takes a linear order of node id
 * return a view in which only the edges (and nodes) consistent with
 * the linear order is visible.
 *
 * -- Allen
 *)

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


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