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
 [smlnj] / sml / branches / SMLNJ / src / MLRISC / graphs / digraph.sml

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

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,
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,
# 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