Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* Copyright (C) 2009 Matthew Fluet. |
2 | * Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh | |
3 | * Jagannathan, and Stephen Weeks. | |
4 | * Copyright (C) 1997-2000 NEC Research Institute. | |
5 | * | |
6 | * MLton is released under a BSD-style license. | |
7 | * See the file MLton-LICENSE for details. | |
8 | *) | |
9 | ||
10 | signature EQUIVALENCE_GRAPH_STRUCTS = | |
11 | sig | |
12 | end | |
13 | ||
14 | (* An equivalence graph is an equivalence relation with a weight function on | |
15 | * classes and an edge relation between classes. | |
16 | * | |
17 | * The main operation is coarsen, which takes an equivalence graph and coarsens | |
18 | * the equivalence relation so that the class weights are as large as possible | |
19 | * subject to a constraint. | |
20 | *) | |
21 | ||
22 | signature EQUIVALENCE_GRAPH = | |
23 | sig | |
24 | include EQUIVALENCE_GRAPH_STRUCTS | |
25 | ||
26 | structure Class: | |
27 | sig | |
28 | (* The type of equivalence classes. *) | |
29 | type t | |
30 | ||
31 | val plist: t -> PropertyList.t | |
32 | end | |
33 | ||
34 | (* The type of equivalence graphs. *) | |
35 | type t | |
36 | ||
37 | (* Make two classes equivalent. | |
38 | * The size of the resulting class is the sum of the sizes of the original | |
39 | * two classes. This is a no-op if the classes are already equivalent. | |
40 | *) | |
41 | val == : t * Class.t * Class.t -> unit | |
42 | ||
43 | (* Add a new edge between two classes. *) | |
44 | val addEdge: t * Class.t * Class.t -> unit | |
45 | ||
46 | (* Make the equivalence relation as coarse as possible so that the | |
47 | * number of edges between classes is minimized, subject to the constraint | |
48 | * that the sum of the node sizes in an equivalence class is | |
49 | * <= maxClassSize. Classes for which this constraint was violated by | |
50 | * previous calls to == should not be made coarser. | |
51 | *) | |
52 | val coarsen: t * {maxClassSize: int} -> unit | |
53 | ||
54 | (* Return a new relation. *) | |
55 | val new: unit -> t | |
56 | ||
57 | (* newClass (g, {classSize}) adds a new class to the equivalence graph. *) | |
58 | val newClass: t * {size: int} -> Class.t | |
59 | end |