View Javadoc

1   // PartialOrderDomainAssignment.java, created Jul 11, 2004 12:59:33 PM by joewhaley
2   // Copyright (C) 2004 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package net.sf.bddbddb.ir;
5   
6   import java.util.Collection;
7   import java.util.HashSet;
8   import java.util.Iterator;
9   import java.util.LinkedHashSet;
10  import java.util.LinkedList;
11  import java.util.List;
12  import java.util.Map;
13  import java.util.Set;
14  import java.io.BufferedWriter;
15  import java.io.IOException;
16  import java.io.PrintStream;
17  import jwutil.collections.GenericMultiMap;
18  import jwutil.collections.MultiMap;
19  import jwutil.collections.Pair;
20  import jwutil.collections.UnionFindWithConstraints;
21  import net.sf.bddbddb.Attribute;
22  import net.sf.bddbddb.BDDSolver;
23  import net.sf.bddbddb.Relation;
24  import net.sf.bddbddb.Solver;
25  import net.sf.bddbddb.dataflow.PartialOrder.ConstraintGraph;
26  import net.sf.bddbddb.dataflow.PartialOrder.Constraints;
27  
28  /***
29   * PartialOrderDomainAssignment
30   * 
31   * @author John Whaley
32   * @version $Id: PartialOrderDomainAssignment.java 622 2005-08-30 11:06:31Z joewhaley $
33   */
34  public class PartialOrderDomainAssignment extends UFDomainAssignment {
35      Collection beforeConstraints;
36      List ileavedConstraints;
37  
38      /***
39       * @param s
40       */
41      public PartialOrderDomainAssignment(Solver s, Constraints[] constraintMap) {
42          super(s, constraintMap); // super() calls initialize() for us.
43      }
44  
45      void initialize() {
46          beforeConstraints = new LinkedList();
47          ileavedConstraints = new LinkedList();
48          super.initialize();
49      }
50      
51      public void doAssignment() {
52          super.doAssignment();
53      }
54  
55      boolean wouldBeLegal(Object a1, Object a2) {
56          if (!super.wouldBeLegal(a1, a2)) return false;
57          List path = new LinkedList();
58          ConstraintGraph graph = new ConstraintGraph(beforeConstraints);
59          if (graph.isPath(a1, a2, path) || graph.isPath(a2, a1, path)) {
60              if (TRACE) solver.out.println("Cannot,rep cycle detected: " + path);
61              return false;
62          }
63          return true;
64      }
65  
66      boolean forceBefore(Object o1, Object o2) {
67          beforeConstraints = updateConstraints(beforeConstraints);
68          Object rep1 = uf.find(o1);
69          Object rep2 = uf.find(o2);
70          Pair tempConstraint = new Pair(rep1, rep2);
71          if (beforeConstraints.contains(tempConstraint)) {
72              if (TRACE) solver.out.println(o1 + " already before " + o2);
73              return true;
74          }
75          beforeConstraints.add(tempConstraint);
76          List cycle = new LinkedList();
77          if (!constraintsSatisfied(cycle)) {
78              if (TRACE) solver.out.println("rep cycle detected: " + cycle);
79              beforeConstraints.remove(tempConstraint);
80              return false;
81          }
82          if (TRACE) solver.out.println("adding before constraint: " + tempConstraint);
83          return true;
84      }
85  
86      /* (non-Javadoc)
87       * @see net.sf.bddbddb.ir.DomainAssignment#forceBefore(net.sf.bddbddb.Relation, net.sf.bddbddb.Attribute, net.sf.bddbddb.Relation, net.sf.bddbddb.Attribute)
88       */
89      boolean forceBefore(Relation r1, Attribute a1, Relation r2, Attribute a2) {
90          Pair p1 = new Pair(r1, a1);
91          Pair p2 = new Pair(r2, a2);
92          return forceBefore(p1, p2);
93      }
94  
95      boolean forceInterleaved(Object o1, Object o2) {
96          if (TRACE) solver.out.println("Forcing " + o1 + " interleaved " + o2);
97          //update constraint reps
98          ileavedConstraints = updateConstraints(ileavedConstraints);
99          Object rep1 = uf.find(o1);
100         Object rep2 = uf.find(o2);
101         Pair newConstraint = new Pair(rep1, rep2);
102         if (ileavedConstraints.contains(newConstraint)) {
103             if (TRACE) solver.out.println(o1 + " already interleaved with " + o2);
104             return true;
105         }
106         ileavedConstraints.add(newConstraint);
107         if (TRACE) solver.out.println("adding interleaved constraint: " + newConstraint);
108         return true;
109     }
110 
111     /* (non-Javadoc)
112      * @see net.sf.bddbddb.ir.DomainAssignment#forceBefore(net.sf.bddbddb.Relation, net.sf.bddbddb.Attribute, net.sf.bddbddb.Relation, net.sf.bddbddb.Attribute)
113      */
114     boolean forceInterleaved(Relation r1, Attribute a1, Relation r2, Attribute a2) {
115         Pair p1 = new Pair(r1, a1);
116         Pair p2 = new Pair(r2, a2);
117         return forceInterleaved(p1, p2);
118     }
119 
120     boolean constraintsSatisfied(List cycle) {
121         if (TRACE) solver.out.println("Before Constraints: " + beforeConstraints);
122         ConstraintGraph graph = new ConstraintGraph(beforeConstraints);
123         if (TRACE) solver.out.println("Before graph: " + graph);
124         return !graph.isCycle(cycle);
125     }
126 
127     private List updateConstraints(Collection constraints) {
128         List newCons = new LinkedList(constraints);
129         List adds = new LinkedList();
130         for (Iterator it = newCons.iterator(); it.hasNext();) {
131             Pair c = (Pair) it.next();
132             Object crep1 = uf.find(c.left);
133             Object crep2 = uf.find(c.right);
134             if (crep1.equals(crep2)){
135                 it.remove();
136                 continue;
137             }
138             if (!crep1.equals(c.left) || !crep2.equals(c.right)) {
139                 it.remove();
140                 adds.add(new Pair(crep1, crep2));
141             }
142         }
143         newCons.addAll(adds);
144         return newCons;
145     }
146 
147     public void setVariableOrdering() {
148         TRACE = true;
149         if (beforeConstraints.size() == 0 && ileavedConstraints.size() == 0) {
150             if (TRACE) solver.out.println("No constraints specified using default ordering");
151             super.setVariableOrdering();
152         }
153       //  solver.out.println("beforeConstraints: " + beforeConstraints);
154         if (TRACE) solver.out.println("Interleaved constraints: " + ileavedConstraints);
155         //solver.out.println("physical domains: " + physicalDomains);
156         MultiMap ileavedDomains = new GenericMultiMap();
157         Collection nodes = new LinkedHashSet(physicalDomains.keySet());
158         
159        
160         for (Iterator it = ileavedConstraints.iterator(); it.hasNext();) {
161             Pair c = (Pair) it.next();
162             Object rep1 = uf.find(c.left);
163             Object rep2 = uf.find(c.right);
164             if (TRACE) solver.out.println("interleave constraint: " + c);
165             if (TRACE) solver.out.println(c.left + " rep = " + rep1);
166             if (TRACE) solver.out.println(c.right + " rep = " + rep2);
167             if (rep1.equals(rep2)) continue;
168             nodes.remove(rep1);
169             nodes.remove(rep2);
170             uf.union(rep1, rep2);
171             Object newRep = uf.find(rep1);
172             nodes.add(newRep);
173             if (TRACE) solver.out.println("New rep: " + newRep);
174             List domains = new LinkedList();
175             Object d1 = ileavedDomains.get(rep1);
176             if (d1 != null) {
177                 domains.addAll((Collection) d1);
178             } else {
179                 Object mapdomain = physicalDomains.get(rep1);
180                 domains.add(mapdomain);
181             }
182             Object d2 = ileavedDomains.get(rep2);
183             if (d2 != null) {
184                 domains.addAll((Collection) d2);
185             } else {
186                 domains.add(physicalDomains.get(rep2));
187             }
188             if (TRACE) solver.out.println("interleaved: " + domains);
189             ileavedDomains.addAll(newRep, domains);
190         }
191         beforeConstraints = updateConstraints(beforeConstraints);
192       //  Constraints cons = new Constraints(new TreeSet(beforeConstraints));
193        // cons.satisfy();
194       //  beforeConstraints = (SortedSet) cons.getBeforeConstraints();
195         ConstraintGraph graph = new ConstraintGraph(nodes, beforeConstraints);
196         
197         if (TRACE) solver.out.println("Nodes: " + nodes);
198         if (TRACE) solver.out.println("Constraints: " + beforeConstraints);
199         String order = graphToOrder(TRACE, graph, uf, ileavedDomains, physicalDomains);
200         BDDSolver s = (BDDSolver) solver;
201         s.VARORDER = order;
202         s.setVariableOrdering();
203     }
204 
205     public static String graphToOrder(boolean trace, ConstraintGraph graph, UnionFindWithConstraints uf, MultiMap ileavedDomains, Map domainMap){
206         
207         PrintStream out = System.out;
208         Set visited = new HashSet();
209         int i = 0;
210         if (trace) out.println("Order graph: " + graph);
211         StringBuffer sb = new StringBuffer();
212         for (Collection roots = graph.getRoots(); !roots.isEmpty();) {
213             if (trace) out.println("Nodes left: " + graph.getNodes());
214             if (trace) out.println("Roots: " + roots);
215             for (Iterator it = roots.iterator(); it.hasNext();) {
216                 Object root = it.next();
217                 Object rep = uf.find(root);
218                 if (!visited.contains(rep)) {
219                     sb.append((i != 0) ? "_" : "");
220                     i++;
221                     visited.add(rep);
222                     if (trace) out.println("root: " + rep);
223                     Collection ileaved = ileavedDomains.getValues(rep);
224                     if (ileaved != null && ileaved.size() != 0) {
225                         
226                         if (trace) out.println("interleaved");
227                         Iterator jt = ileaved.iterator();
228                         sb.append(jt.next());
229                         while (jt.hasNext())
230                             sb.append("x" + jt.next());
231                     } else {
232                         sb.append(domainMap.get(rep));
233                     }
234                 }
235                 graph.removeEdgesFrom(root);
236                 graph.removeNode(root);
237             }
238             roots = graph.getRoots();
239         }
240         return sb.toString();
241     }
242     /* (non-Javadoc)
243      * @see net.sf.bddbddb.ir.DomainAssignment#saveDomainAssignment(java.io.BufferedWriter)
244      */
245     public void saveDomainAssignment(BufferedWriter out) throws IOException {
246         super.saveDomainAssignment(out);
247         for (Iterator it = beforeConstraints.iterator(); it.hasNext();) {
248             Pair c = (Pair) it.next();
249             String left;
250             if (c.left instanceof Pair) {
251                 Pair p = (Pair) c.left;
252                 left = p.left+" "+p.right;
253             } else {
254                 left = c.left.toString();
255             }
256             String right;
257             if (c.right instanceof Pair) {
258                 Pair p = (Pair) c.right;
259                 right = p.left+" "+p.right;
260             } else {
261                 right = c.right.toString();
262             }
263             out.write(left+" < "+right+"\n");
264         }
265         for (Iterator it = ileavedConstraints.iterator(); it.hasNext();) {
266             Pair c = (Pair) it.next();
267             String left;
268             if (c.left instanceof Pair) {
269                 Pair p = (Pair) c.left;
270                 left = p.left+" "+p.right;
271             } else {
272                 left = c.left.toString();
273             }
274             String right;
275             if (c.right instanceof Pair) {
276                 Pair p = (Pair) c.right;
277                 right = p.left+" "+p.right;
278             } else {
279                 right = c.right.toString();
280             }
281             out.write(left+" ~ "+right+"\n");
282         }
283     }
284 }