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

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