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

   1 package org.simantics.graph.matching;
   2
   3 import gnu.trove.list.array.TIntArrayList;
   4 import gnu.trove.map.hash.TObjectIntHashMap;
   5 import gnu.trove.set.hash.TIntHashSet;
   6
   7 import java.util.Arrays;
   8 import java.util.Comparator;
   9
  10 import org.simantics.databoard.binding.mutable.Variant;
  11
  12 public enum CanonicalizingMatchingStrategy implements GraphMatchingStrategy {
  13         INSTANCE;
  14
  15         private static class Vertex {
  16                 int graph;
  17                 int original;
  18                 int pos;
  19                 Stat[] stats;
  20
  21                 public Vertex(int graph, int original, int pos, Stat[] stats) {
  22                         this.graph = graph;
  23                         this.original = original;
  24                         this.pos = pos;
  25                         this.stats = stats;
  26                 }
  27         }
  28
  29         private static final Comparator<Vertex> VERTEX_COMPARATOR = new Comparator<Vertex>() {
  30                 @Override
  31                 public int compare(Vertex o1, Vertex o2) {
  32                         int pos1 = o1.pos;
  33                         int pos2 = o2.pos;
  34                         if(pos1 < pos2)
  35                                 return -1;
  36                         if(pos1 > pos2)
  37                                 return 1;
  38                         Stat[] stats1 = o1.stats;
  39                         Stat[] stats2 = o2.stats;
  40                         if(stats1.length < stats2.length)
  41                                 return -1;
  42                         if(stats1.length > stats2.length)
  43                                 return 1;
  44                         for(int i=0;i<stats1.length;++i) {
  45                                 int comp = Stat.STAT_COMPARATOR.compare(stats1[i], stats2[i]);
  46                                 if(comp != 0)
  47                                         return comp;
  48                         }
  49                         if(o1.graph < o2.graph)
  50                                 return -1;
  51                         if(o1.graph > o2.graph)
  52                                 return 1;
  53                         if(o1.original < o2.original)
  54                                 return -1;
  55                         if(o1.original > o2.original)
  56                                 return 1;
  57                         return 0;
  58                 }
  59         };
  60
  61         private static int[] generateMapA(int[] aToB) {
  62                 int[] map = new int[aToB.length];
  63                 for(int i=0;i<aToB.length;++i) {
  64                         int c = aToB[i];
  65                         if(c >= 0)
  66                                 map[i] = -1 - c;
  67                         else
  68                                 map[i] = 0;
  69                 }
  70                 return map;
  71         }
  72
  73         private static int[] generateMapB(int[] bToA) {
  74                 int[] map = new int[bToA.length];
  75                 for(int i=0;i<bToA.length;++i) {
  76                         int c = bToA[i];
  77                         if(c >= 0)
  78                                 map[i] = -1 - i;
  79                         else
  80                                 map[i] = 0;
  81                 }
  82                 return map;
  83         }
  84
  85         private static Vertex[] generateVertices(int graph, int[] map, Stat[][] statements) {
  86                 int size = 0;
  87                 for(int s=0;s<map.length;++s)
  88                         if(map[s] == 0)
  89                                 ++size;
  90                 Vertex[] vertices = new Vertex[size];
  91                 for(int s=0,i=0;s<map.length;++s)
  92                         if(map[s] == 0) {
  93                                 Stat[] ns = statements[s];
  94                                 Stat[] stats = new Stat[ns.length];
  95                                 for(int j=0;j<ns.length;++j) {
  96                                         Stat n = ns[j];
  97                                         stats[j] = new Stat(map[n.p], map[n.o]);
  98                                 }
  99                                 Arrays.sort(stats, Stat.STAT_COMPARATOR);
 100                                 vertices[i++] = new Vertex(graph, s, 0, stats);
 101                         }
 102                 return vertices;
 103         }
 104
 105         private static void updateVertices(Vertex[] vertices, int[] map, Stat[][] statements) {
 106                 for(int i=0;i<vertices.length;++i) {
 107                         int s = vertices[i].original;
 108                         Stat[] ns = statements[s];
 109                         Stat[] stats = vertices[i].stats;
 110                         for(int j=0;j<ns.length;++j) {
 111                                 Stat n = ns[j];
 112                                 Stat stat = stats[j];
 113                                 stat.p = map[n.p];
 114                                 stat.o = map[n.o];
 115                         }
 116                         Arrays.sort(stats, Stat.STAT_COMPARATOR);
 117                 }
 118         }
 119
 120         private static Vertex[] concat(Vertex[] as, Vertex[] bs) {
 121                 Vertex[] result = new Vertex[as.length + bs.length];
 122                 System.arraycopy(as, 0, result, 0, as.length);
 123                 System.arraycopy(bs, 0, result, as.length, bs.length);
 124                 return result;
 125         }
 126
 127         static boolean equals(Stat[] stats1, Stat[] stats2) {
 128                 if(stats1.length != stats2.length)
 129                         return false;
 130                 for(int i=0;i<stats1.length;++i) {
 131                         Stat stat1 = stats1[i];
 132                         Stat stat2 = stats2[i];
 133                         if(stat1.p != stat2.p || stat1.o != stat2.o)
 134                                 return false;
 135                 }
 136                 return true;
 137         }
 138
 139         private static boolean updatePositions(Vertex[] can) {
 140                 boolean modified = false;
 141                 int oldPos = can[0].pos;
 142                 Vertex oldVertex = can[0];
 143                 for(int i=1;i<can.length;++i) {
 144                         Vertex curVertex = can[i];
 145                         int curPos = curVertex.pos;
 146                         if(curPos == oldPos) {
 147                                 if(equals(oldVertex.stats, curVertex.stats))
 148                                         curVertex.pos = oldVertex.pos;
 149                                 else {
 150                                         curVertex.pos = i;
 151                                         modified = true;
 152                                 }
 153                         }
 154                         else
 155                                 oldPos = curPos;
 156                         oldVertex = curVertex;
 157                 }
 158                 return modified;
 159         }
 160
 161         private static void updateMap(Vertex[] vertices, int[] map) {
 162                 for(Vertex vertex : vertices)
 163                         map[vertex.original] = vertex.pos;
 164         }
 165
 166         private static int[] groupPositions(Vertex[] can) {
 167                 TIntArrayList result = new TIntArrayList();
 168                 for(int i=0;i<can.length;++i)
 169                         if(can[i].pos == i)
 170                                 result.add(i);
 171                 result.add(can.length);
 172                 return result.toArray();
 173         }
 174
 175         static class TByteArrayIntHashMap extends TObjectIntHashMap<byte[]> {
 176                 @Override
 177                 protected boolean equals(Object one, Object two) {
 178                         return Arrays.equals((byte[])one, (byte[])two);
 179                 }
 180
 181                 @Override
 182                 protected int hash(Object obj) {
 183                         return Arrays.hashCode((byte[])obj);
 184                 }
 185         }
 186
 187         private boolean separateByValues(Vertex[] can, int begin, int end, Variant[] aValues, Variant[] bValues) {
 188                 int valueCount = 0;
 189                 TObjectIntHashMap<Variant> valueIds = new TObjectIntHashMap<Variant>();
 190                 int[] ids = new int[end-begin];
 191                 for(int i=begin;i<end;++i) {
 192                         Vertex v = can[i];
 193                         Variant value = v.graph==0 ? aValues[v.original] : bValues[v.original];
 194                         int valueId = valueIds.get(value);
 195                         if(valueId == 0) {
 196                                 valueIds.put(value, ++valueCount);
 197                                 ids[i-begin] = valueCount-1;
 198                         }
 199                         else
 200                                 ids[i-begin] = valueId-1;
 201                 }
 202                 if(valueCount > 1) {
 203                         Vertex[] vs = Arrays.copyOfRange(can, begin, end);
 204                         int[] temp = new int[valueCount];
 205                         for(int id : ids)
 206                                 ++temp[id];
 207                         int cur = begin;
 208                         for(int i=0;i<temp.length;++i) {
 209                                 int count = temp[i];
 210                                 temp[i] = cur;
 211                                 cur += count;
 212                         }
 213                         for(int i=0;i<ids.length;++i)
 214                                 vs[i].pos = temp[ids[i]];
 215                         for(int i=0;i<ids.length;++i)
 216                                 can[temp[ids[i]]++] = vs[i];
 217                         return true;
 218                 }
 219                 else
 220                         return false;
 221         }
 222
 223         private boolean separateByValues(Vertex[] can, int[] groupPos, Variant[] aValues, Variant[] bValues) {
 224                 boolean modified = false;
 225                 for(int i=0;i<groupPos.length-1;++i) {
 226                         int begin = groupPos[i];
 227                         int end = groupPos[i+1];
 228                         if(end - begin > 2)
 229                                 modified |= separateByValues(can, begin, end, aValues, bValues);
 230                 }
 231                 return modified;
 232         }
 233
 234         private boolean hasBigGroups(Vertex[] can, int[] groupPos) {
 235                 for(int i=0;i<groupPos.length-1;++i) {
 236                         int begin = groupPos[i];
 237                         int end = groupPos[i+1];
 238                         if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1)
 239                                 return true;
 240                 }
 241                 return false;
 242         }
 243
 244         static class UnionFind {
 245                 int[] canonical;
 246
 247                 public UnionFind(int size) {
 248                         canonical = new int[size];
 249                         for(int i=0;i<size;++i)
 250                                 canonical[i] = i;
 251                 }
 252
 253                 public int canonical(int a) {
 254                         int b = canonical[a];
 255                         if(b != a) {
 256                                 int c = canonical[b];
 257                                 if(b != c) {
 258                                         c = canonical(c);
 259                                         canonical[b] = c;
 260                                         canonical[a] = c;
 261                                         return c;
 262                                 }
 263                         }
 264                         return b;
 265                 }
 266
 267                 public void merge(int a, int b) {
 268                         a = canonical(a);
 269                         b = canonical(b);
 270                         canonical[a] = b;
 271                 }
 272         }
 273
 274         private static void guessIsomorphism(Vertex[] can, int[] groupPos) {
 275                 UnionFind uf = new UnionFind(can.length);
 276                 for(int i=0;i<can.length;++i) {
 277                         uf.merge(i, can[i].pos);
 278                         for(Stat stat : can[i].stats) {
 279                                 if(stat.p >= 0)
 280                                         uf.merge(i, stat.p);
 281                                 if(stat.o >= 0)
 282                                         uf.merge(i, stat.o);
 283                         }
 284                 }
 285
 286                 TIntHashSet done = new TIntHashSet();
 287                 for(int i=0;i<groupPos.length-1;++i) {
 288                         int begin = groupPos[i];
 289                         int end = groupPos[i+1];
 290                         if(end - begin > 2 && can[begin].graph == 0 && can[end-1].graph == 1) {
 291                                 int c = uf.canonical(begin);
 292                                 if(done.add(c)) {
 293                                         int middle = begin+1;
 294                                         while(can[middle].graph==0)
 295                                                 ++middle;
 296                                         int j;
 297                                         for(j=0;begin+j < middle && middle+j < end;++j) {
 298                                                 can[begin+j].pos = begin + j*2;
 299                                                 can[middle+j].pos = begin + j*2;
 300                                         }
 301                                         int pos = begin+j*2;
 302                                         for(;begin+j < middle;++j)
 303                                                 can[begin+j].pos = pos;
 304                                         for(;middle+j < end;++j)
 305                                                 can[middle+j].pos = pos;
 306                                 }
 307                         }
 308                 }
 309         }
 310
 311         @Override
 312         public void applyTo(GraphMatching matching) {
 313                 if(matching.size == matching.aGraph.resourceCount ||
 314                                 matching.size == matching.bGraph.resourceCount)
 315                         return;
 316                 long begin1 = System.nanoTime();
 317                 int[] aMap = generateMapA(matching.aToB);
 318                 int[] bMap = generateMapB(matching.bToA);
 319                 Vertex[] aVertices = generateVertices(0,
 320                                 aMap, matching.aGraph.statements);
 321                 Vertex[] bVertices = generateVertices(1,
 322                                 bMap, matching.bGraph.statements);
 323                 Vertex[] can = concat(aVertices, bVertices);
 324                 if(GraphMatching.TIMING)
 325                         System.out.println("    Init:    " + (System.nanoTime()-begin1)*1e-6 + "ms");
 326
 327                 int[] groupPos = null;
 328                 boolean doneSeparationByValues = false;
 329                 while(true) {
 330                         long begin2 = System.nanoTime();
 331                         Arrays.sort(can, VERTEX_COMPARATOR);
 332                         if(GraphMatching.TIMING)
 333                                 System.out.println("    Sort:    " + (System.nanoTime()-begin2)*1e-6 + "ms");
 334
 335                         long begin3 = System.nanoTime();
 336                         if(!updatePositions(can)) {
 337                                 groupPos = groupPositions(can);
 338                                 if(!hasBigGroups(can, groupPos))
 339                                         break;
 340
 341                                 boolean modified = false;
 342                                 if(!doneSeparationByValues) {
 343                                         modified = separateByValues(can, groupPos, matching.aGraph.values, matching.bGraph.values);
 344                                         doneSeparationByValues = true;
 345                                         if(GraphMatching.TIMING)
 346                                                 System.out.println("    - separate by values");
 347                                 }
 348
 349                                 if(!modified) {
 350                                         guessIsomorphism(can, groupPos);
 351                                         if(GraphMatching.TIMING)
 352                                                 System.out.println("    - guess isomorphism");
 353                                 }
 354                         }
 355                         if(GraphMatching.TIMING)
 356                                 System.out.println("    Update1: " + (System.nanoTime()-begin3)*1e-6 + "ms");
 357
 358                         long begin4 = System.nanoTime();
 359                         updateMap(aVertices, aMap);
 360                         updateMap(bVertices, bMap);
 361                         if(GraphMatching.TIMING)
 362                                 System.out.println("    Update2: " + (System.nanoTime()-begin4)*1e-6 + "ms");
 363                         long begin5 = System.nanoTime();
 364                         updateVertices(aVertices, aMap, matching.aGraph.statements);
 365                         updateVertices(bVertices, bMap, matching.bGraph.statements);
 366                         if(GraphMatching.TIMING)
 367                                 System.out.println("    Update3: " + (System.nanoTime()-begin5)*1e-6 + "ms");
 368                 }
 369
 370                 for(int i=0;i<groupPos.length-1;++i) {
 371                         int begin = groupPos[i];
 372                         int end = groupPos[i+1];
 373                         if(end - begin == 2) {
 374                                 Vertex a = can[begin];
 375                                 Vertex b = can[end-1];
 376                                 if(a.graph == 0 && b.graph == 1)
 377                                         matching.map(a.original, b.original);
 378                         }
 379                 }
 380
 381                 if(GraphMatching.DEBUG)
 382                         for(int i=0;i<groupPos.length-1;++i) {
 383                                 int begin = groupPos[i];
 384                                 int end = groupPos[i+1];
 385                                 if(end - begin > 2) {
 386                                         System.out.println("----");
 387                                         for(int j=begin;j<end;++j) {
 388                                                 if(can[j].graph == 0) {
 389                                                         int org = can[j].original;
 390                                                         String name = matching.aGraph.names[org];
 391                                                         System.out.println(name + " (A)");
 392                                                         for(Stat stat : matching.aGraph.statements[org])
 393                                                                 System.out.println("    " + stat.toString(matching.aGraph.names));
 394                                                         Variant value = matching.aGraph.values[org];
 395                                                         if(value != null)
 396                                                                 System.out.println("    " + value);
 397                                                 }
 398                                                 else {
 399                                                         int org = can[j].original;
 400                                                         String name = matching.bGraph.names[org];
 401                                                         System.out.println(name + " (B)");
 402                                                         for(Stat stat : matching.bGraph.statements[org])
 403                                                                 System.out.println("    " + stat.toString(matching.bGraph.names));
 404                                                         Variant value = matching.bGraph.values[org];
 405                                                         if(value != null)
 406                                                                 System.out.println("    " + value);
 407                                                 }
 408                                         }
 409                                 }
 410                         }
 411         }
 412 }