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/branches/SMLNJ/src/MLRISC/graphs/digraph.sml
ViewVC logotype

Diff of /sml/branches/SMLNJ/src/MLRISC/graphs/digraph.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 410, Fri Sep 3 00:25:03 1999 UTC revision 411, Fri Sep 3 00:25:03 1999 UTC
# Line 1  Line 1 
1  (*  (*
2   *  Directed graph in adjacency list format.   *  Directed graph in adjacency list format.
3   *   *
4     * -- Allen
5   *)   *)
6    
7  functor DirectedGraphFn(A : ARRAY_SIG) : GRAPH_IMPLEMENTATION =  functor DirectedGraphFn(A : ARRAY) :
8    sig include GRAPH_IMPLEMENTATION
9    
10        type 'e adjlist   = 'e Graph.edge list A.array
11        type 'n nodetable = 'n option A.array
12    
13        (* This function exposes the internal representation! *)
14        val newGraph :
15            { name  : string,
16              info  : 'g,
17              succ  : 'e adjlist,
18              pred  : 'e adjlist,
19              nodes : 'n nodetable
20            } -> ('n,'e,'g) Graph.graph
21    end =
22  struct  struct
23    
24     structure G = Graph     structure G = Graph
25     structure A = A     structure A = A
26    
27     fun graph(name,graph_info,n) =     type 'e adjlist   = 'e Graph.edge list A.array
28     let val succ          = A.array(n,[])     type 'n nodetable = 'n option A.array
29         val pred          = A.array(n,[])  
30         val nodes         = A.array(n,NONE)     fun newGraph{name,info,succ,pred,nodes} =
31         val node_count    = ref 0     let val node_count    = ref 0
32         val edge_count    = ref 0         val edge_count    = ref 0
33         val entries       = ref []         val entries       = ref []
34         val exits         = ref []         val exits         = ref []
# Line 25  Line 40 
40            (new_nodes := (!new_nodes) @ (!garbage_nodes); garbage_nodes := [])            (new_nodes := (!new_nodes) @ (!garbage_nodes); garbage_nodes := [])
41         fun get_nodes() =         fun get_nodes() =
42            A.foldri(fn(i,SOME n,l) =>(i,n)::l|(_,_,l) => l) [] (nodes,0,NONE)            A.foldri(fn(i,SOME n,l) =>(i,n)::l|(_,_,l) => l) [] (nodes,0,NONE)
43         fun get_edges() = List.concat(A.foldl op:: [] succ)         fun get_edges() = List.concat(A.foldr op:: [] succ)
44         fun order() = !node_count         fun order() = !node_count
45         fun size()  = !edge_count         fun size()  = !edge_count
46         fun capacity() = A.length nodes         fun capacity() = A.length nodes
# Line 100  Line 115 
115    
116     in  G.GRAPH {     in  G.GRAPH {
117            name            = name,            name            = name,
118            graph_info      = graph_info,            graph_info      = info,
119            new_id          = new_id,            new_id          = new_id,
120            add_node        = add_node,            add_node        = add_node,
121            add_edge        = add_edge,            add_edge        = add_edge,
# Line 131  Line 146 
146         }         }
147     end     end
148    
149       fun graph(name,info,n) =
150       let val succ  = A.array(n,[])
151           val pred  = A.array(n,[])
152           val nodes = A.array(n,NONE)
153       in  newGraph{name=name,info=info,nodes=nodes,succ=succ,pred=pred} end
154  end  end
155    
156  structure DirectedGraph = DirectedGraphFn(DynamicArray)  structure DirectedGraph = DirectedGraphFn(DynamicArray)
157    
 (*  
  * $Log$  
  *)  

Legend:
Removed from v.410  
changed lines
  Added in v.411

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