bundles/org.simantics.graph/src/org/simantics/graph/matching/ComponentMatchingStrategy.java

   1 package org.simantics.graph.matching;
   2
   3 import gnu.trove.list.array.TIntArrayList;
   4 import gnu.trove.map.hash.THashMap;
   5 import gnu.trove.map.hash.TIntIntHashMap;
   6 import gnu.trove.map.hash.TIntObjectHashMap;
   7 import gnu.trove.procedure.TObjectProcedure;
   8
   9 import java.util.ArrayList;
  10 import java.util.Arrays;
  11 import java.util.Comparator;
  12
  13 /**
  14  * Matches isomorphic components of the not yet matched graphs together.
  15  *
  16  * @author Hannu Niemistö
  17  */
  18 public enum ComponentMatchingStrategy implements GraphMatchingStrategy {
  19         INSTANCE;
  20
  21         static class UnionFind {
  22                 int[] canonical;
  23
  24                 public UnionFind(int size) {
  25                         canonical = new int[size];
  26                         for(int i=0;i<size;++i)
  27                                 canonical[i] = i;
  28                 }
  29
  30                 public int canonical(int a) {
  31                         int b = canonical[a];
  32                         if(b != a) {
  33                                 int c = canonical[b];
  34                                 if(b != c) {
  35                                         c = canonical(c);
  36                                         canonical[b] = c;
  37                                         canonical[a] = c;
  38                                         return c;
  39                                 }
  40                         }
  41                         return b;
  42                 }
  43
  44                 public void merge(int a, int b) {
  45                         a = canonical(a);
  46                         b = canonical(b);
  47                         canonical[a] = b;
  48                 }
  49         }
  50
  51         public static int[][] findComponents(int[] map, Stat[][] statements, TIntIntHashMap inverses) {
  52                 int resourceCount = map.length;
  53
  54                 UnionFind uf = new UnionFind(resourceCount);
  55                 for(int s=0;s<resourceCount;++s)
  56                         if(map[s] < 0) {
  57                                 for(Stat stat : statements[s]) {
  58                                         int o = stat.o;
  59                                         if(s < o && map[o] < 0)
  60                                                 uf.merge(s, o);
  61                                 }
  62                                 /*if(inverses.containsKey(s))
  63                                         uf.merge(s, inverses.get(s));
  64                                         */
  65                         }
  66
  67                 TIntObjectHashMap<TIntArrayList> components = new TIntObjectHashMap<TIntArrayList>();
  68                 for(int i=0;i<resourceCount;++i)
  69                         if(map[i] < 0) {
  70                                 int c = uf.canonical(i);
  71                                 TIntArrayList els = components.get(c);
  72                                 if(els == null) {
  73                                         els = new TIntArrayList(2);
  74                                         components.put(c, els);
  75                                 }
  76                                 els.add(i);
  77                         }
  78
  79                 final int[][] result = new int[components.size()][];
  80                 components.forEachValue(new TObjectProcedure<TIntArrayList>() {
  81                         int i = 0;
  82                         @Override
  83                         public boolean execute(TIntArrayList els) {
  84                                 result[i++] = els.toArray();
  85                                 return true;
  86                         }
  87                 });
  88                 return result;
  89         }
  90
  91         public static Stat[][] neighbors(int[] map, Stat[][] statements) {
  92                 int resourceCount = map.length;
  93                 Stat[][] neighbors = new Stat[resourceCount][];
  94
  95                 ArrayList<Stat> stats = new ArrayList<Stat>();
  96                 for(int s=0;s<resourceCount;++s) {
  97                         if(map[s] >= 0) {
  98                                 neighbors[s] = Stat.NO_STATS;
  99                                 continue;
 100                         }
 101
 102                         for(Stat stat : statements[s]) {
 103                                 int pp = map[stat.p] >= 0 ? stat.p : -1;
 104                                 int oo = map[stat.o] >= 0 ? stat.o : -1;
 105                                 stats.add(new Stat(pp, oo));
 106                         }
 107
 108                         if(stats.isEmpty())
 109                                 neighbors[s] = Stat.NO_STATS;
 110                         else {
 111                                 neighbors[s] = stats.toArray(new Stat[stats.size()]);
 112                                 stats.clear();
 113                         }
 114                 }
 115
 116                 return neighbors;
 117         }
 118
 119         static class Component {
 120                 int[] elements;
 121                 Stat[][] neighbors;
 122
 123                 public Component(int[] elements, Stat[][] neighbors) {
 124                         this.elements = elements;
 125                         this.neighbors = new Stat[elements.length][];
 126                         for(int i=0;i<elements.length;++i)
 127                                 this.neighbors[i] = neighbors[elements[i]];
 128                 }
 129
 130                 public void map(int[] map) {
 131                         for(Stat[] stats : neighbors)
 132                                 for(Stat stat : stats)
 133                                         stat.map(map);
 134                 }
 135
 136                 static class PP {
 137                         int element;
 138                         Stat[] stats;
 139
 140                         public PP(int element, Stat[] stats) {
 141                                 this.element = element;
 142                                 Arrays.sort(stats, Stat.STAT_COMPARATOR);
 143                                 this.stats = stats;
 144                         }
 145                 }
 146
 147                 static final Comparator<PP> PP_COMPARATOR = new Comparator<PP>() {
 148                         @Override
 149                         public int compare(PP o1, PP o2) {
 150                                 Stat[] stats1 = o1.stats;
 151                                 Stat[] stats2 = o2.stats;
 152                                 int l1 = stats1.length;
 153                                 int l2 = stats2.length;
 154                                 if(l1 < l2)
 155                                         return -1;
 156                                 else if(l1 > l2)
 157                                         return 1;
 158                                 for(int i=0;i<l1;++i) {
 159                                         Stat s1 = stats1[i];
 160                                         Stat s2 = stats2[i];
 161                                         if(s1.p < s2.p)
 162                                                 return -1;
 163                                         else if(s1.p > s2.p)
 164                                                 return 1;
 165                                         else if(s1.o < s2.o)
 166                                                 return -1;
 167                                         else if(s1.o > s2.o)
 168                                                 return 1;
 169                                 }
 170                                 return 0;
 171                         }
 172                 };
 173
 174                 public void canonicalize(String[] elNames, String[] statNames) {
 175                         PP[] pps = new PP[elements.length];
 176                         for(int i=0;i<elements.length;++i)
 177                                 pps[i] = new PP(elements[i], neighbors[i]);
 178                         Arrays.sort(pps, PP_COMPARATOR);
 179                         for(int i=0;i<pps.length-1;++i)
 180                                 if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0) {
 181                                         System.out.println("AMB " + pps.length + " " + (elNames==statNames));
 182                                         for(i=0;i<pps.length-1;++i) {
 183                                                 if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0)
 184                                                         System.out.print(">   ");
 185                                                 else
 186                                                         System.out.print("    ");
 187                                                 System.out.println(elNames[pps[i].element]);
 188                                                 for(Stat stat : pps[i].stats)
 189                                                         System.out.println("        " + stat.toString(statNames));
 190                                         }
 191                                         break;
 192                                 }
 193                         for(int i=0;i<elements.length;++i) {
 194                                 PP pp = pps[i];
 195                                 elements[i] = pp.element;
 196                                 neighbors[i] = pp.stats;
 197                         }
 198                 }
 199
 200                 public boolean isIsolated() {
 201                         for(Stat[] stats : neighbors)
 202                                 if(stats.length > 0)
 203                                         return false;
 204                         return true;
 205                 }
 206         }
 207
 208         static class TNeighbourObjectHashMap<T> extends THashMap<Stat[][], T> {
 209                 @Override
 210                 protected boolean equals(Object one, Object two) {
 211                         Stat[][] o1 = (Stat[][])one;
 212                         Stat[][] o2 = (Stat[][])two;
 213                         if(o1.length != o2.length)
 214                                 return false;
 215                         for(int i=0;i<o1.length;++i) {
 216                                 Stat[] ss1 = o1[i];
 217                                 Stat[] ss2 = o2[i];
 218                                 if(ss1.length != ss2.length)
 219                                         return false;
 220                                 for(int j=0;j<ss1.length;++j) {
 221                                         Stat s1 = ss1[j];
 222                                         Stat s2 = ss2[j];
 223                                         if(s1.p != s2.p || s1.o != s2.o)
 224                                                 return false;
 225                                 }
 226                         }
 227                         return true;
 228                 }
 229
 230                 @Override
 231                 protected int hash(Object obj) {
 232                         int result = 152433;
 233                         for(Stat[] stats : (Stat[][])obj)
 234                                 for(Stat stat : stats)
 235                                         result = (result*31 + stat.p)*31 + stat.o;
 236                         return result;
 237                 }
 238         }
 239
 240         @Override
 241         public void applyTo(GraphMatching matching) {
 242                 System.out.println("ComponentMatchingStrategy");
 243                 TNeighbourObjectHashMap<ArrayList<int[]>> aComponents = new TNeighbourObjectHashMap<ArrayList<int[]>>();
 244                 {
 245                         Stat[][] neighbors = neighbors(matching.aToB, matching.aGraph.statements);
 246                         //TIntIntHashMap componentSizes = new TIntIntHashMap();
 247                         for(int[] els : findComponents(matching.aToB, matching.aGraph.statements, matching.aGraph.inverses)) {
 248                                 /*for(int el : els)
 249                                         System.out.print(matching.aGraph.names[el] + " ");
 250                                 System.out.println();
 251                                 componentSizes.adjustOrPutValue(els.length, 1, 1);*/
 252                                 Component component = new Component(els, neighbors);
 253                                 if(component.isIsolated())
 254                                         continue;
 255                                 component.map(matching.aToB);
 256                                 component.canonicalize(matching.aGraph.names, matching.bGraph.names);
 257                                 ArrayList<int[]> values = aComponents.get(component.neighbors);
 258                                 if(values == null) {
 259                                         values = new ArrayList<int[]>(1);
 260                                         aComponents.put(component.neighbors, values);
 261                                 }
 262                                 values.add(component.elements);
 263                         }
 264                         /*componentSizes.forEachEntry(new TIntIntProcedure() {
 265                                 @Override
 266                                 public boolean execute(int a, int b) {
 267                                         System.out.println("Components of size " + a + ": " + b);
 268                                         return true;
 269                                 }
 270                         });*/
 271                 }
 272
 273                 ArrayList<Component> bComponents = new ArrayList<Component>();
 274                 {
 275                         Stat[][] neighbors = neighbors(matching.bToA, matching.bGraph.statements);
 276                         for(int[] els : findComponents(matching.bToA, matching.bGraph.statements, matching.bGraph.inverses)) {
 277                                 Component component = new Component(els, neighbors);
 278                                 if(component.isIsolated())
 279                                         continue;
 280                                 component.canonicalize(matching.bGraph.names, matching.bGraph.names);
 281                                 bComponents.add(component);
 282                         }
 283                 }
 284
 285                 for(Component c : bComponents) {
 286                         ArrayList<int[]> candidates = aComponents.get(c.neighbors);
 287                         if(candidates != null)
 288                                 for(int i=0;i<candidates.size();++i) {
 289                                         int[] els = candidates.get(i);
 290                                         if(els != null) {
 291                                                 matching.map(els, c.elements);
 292                                                 if(matching.checkMatch(els, c.elements)) {
 293                                                         if(candidates.size() == 1)
 294                                                                 aComponents.remove(c.neighbors);
 295                                                         else {
 296                                                                 int last = candidates.size()-1;
 297                                                                 int[] temp = candidates.remove(last);
 298                                                                 if(i < last)
 299                                                                         candidates.set(i, temp);
 300                                                         }
 301                                                     break;
 302                                                 }
 303                                                 else
 304                                                         matching.unmap(els, c.elements);
 305                                         }
 306                                 }
 307                 }
 308         }
 309 }