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

   1 package org.simantics.graph.matching;\r
   2 \r
   3 import gnu.trove.set.hash.THashSet;\r
   4 \r
   5 import java.util.Arrays;\r
   6 \r
   7 import org.simantics.graph.representation.TransferableGraph1;\r
   8 \r
   9 /**\r
  10  * Matching of two transferable graphs.\r
  11  * \r
  12  * @author Hannu Niemistö\r
  13  */\r
  14 public class GraphMatching {\r
  15         public static final boolean DEBUG = false;\r
  16         public static final boolean TIMING = false;\r
  17 \r
  18         int aOriginalSize;\r
  19         int bOriginalSize;\r
  20         CanonicalGraph aGraph;\r
  21         CanonicalGraph bGraph;\r
  22         protected int[] aToB;\r
  23         protected int[] bToA;\r
  24         int size;\r
  25         \r
  26         public GraphMatching(TransferableGraph1 a, TransferableGraph1 b) {\r
  27                 long begin = System.nanoTime();\r
  28                 this.aGraph = new CanonicalGraph(a);\r
  29                 this.bGraph = new CanonicalGraph(b);\r
  30                 aToB = new int[this.aGraph.resourceCount];\r
  31                 Arrays.fill(aToB, -1);\r
  32                 bToA = new int[this.bGraph.resourceCount];\r
  33                 Arrays.fill(bToA, -1);\r
  34                 this.aOriginalSize = a.resourceCount;\r
  35                 this.bOriginalSize = b.resourceCount;\r
  36                 if(TIMING) {\r
  37                         long end = System.nanoTime();\r
  38                         System.out.println("Initialization: " + (end-begin)*1e-6 + "ms");\r
  39                 }\r
  40         }\r
  41 \r
  42         public void print() {\r
  43                 System.out.println("Resources in a:  " + aGraph.resourceCount);\r
  44                 System.out.println("Identities in a: " + aGraph.identities.length);\r
  45                 System.out.println("Statements in a: " + aGraph.statements.length/6);\r
  46                 System.out.println();\r
  47                 System.out.println("Resources in b:  " + bGraph.resourceCount);\r
  48                 System.out.println("Identities in b: " + bGraph.identities.length);\r
  49                 System.out.println("Statements in b: " + bGraph.statements.length/6);\r
  50                 System.out.println();\r
  51                 System.out.println("Match size:      " + size());\r
  52         }\r
  53 \r
  54         public int size() {             \r
  55                 return size;\r
  56         }\r
  57         \r
  58         public void recomputeSize() {\r
  59                 int count = 0;\r
  60                 for(int b : aToB)\r
  61                         if(b >= 0)\r
  62                                 ++count;\r
  63                 size = count;\r
  64         }\r
  65 \r
  66         public void map(int a, int b) {\r
  67                 //if(aToB[a] < 0 && bToA[b] < 0) {\r
  68                         ++size;\r
  69                         aToB[a] = b;\r
  70                         bToA[b] = a;\r
  71                         /*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&\r
  72                                         aGraph.inverses.get(a) != a) {\r
  73                                 int invA = aGraph.inverses.get(a);\r
  74                                 int invB = bGraph.inverses.get(b);\r
  75                                 ++size;\r
  76                                 aToB[invA] = invB;                      \r
  77                                 bToA[invB] = invA;                      \r
  78                         }*/\r
  79                 /*}\r
  80                 else\r
  81                         System.out.println("ERR");*/\r
  82         }\r
  83         \r
  84         public void map(int[] as, int[] bs) {\r
  85                 for(int i=0;i<as.length;++i)\r
  86                         map(as[i], bs[i]);\r
  87         }\r
  88         \r
  89         public void unmap(int a, int b) {\r
  90                 --size;\r
  91                 aToB[a] = -1;\r
  92                 bToA[b] = -1;\r
  93                 /*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&\r
  94                                 aGraph.inverses.get(a) != a) {\r
  95                         int invA = aGraph.inverses.get(a);\r
  96                         int invB = bGraph.inverses.get(b);\r
  97                         --size;\r
  98                         aToB[invA] = -1;\r
  99                         bToA[invB] = -1;\r
 100                 }*/\r
 101         }\r
 102         \r
 103         public void unmap(int[] as, int[] bs) {\r
 104                 for(int i=0;i<as.length;++i)\r
 105                         unmap(as[i], bs[i]);\r
 106         }\r
 107 \r
 108         public boolean checkMatch(int[] as, int[] bs) {\r
 109                 for(int i=0;i<as.length;++i)\r
 110                         if(!checkMatch(as[i], bs[i]))\r
 111                                 return false;\r
 112                 return true;\r
 113         }\r
 114 \r
 115         public boolean checkMatch(int a, int b) {\r
 116                 Stat[] aStats = aGraph.statements[a];\r
 117                 Stat[] bStats = bGraph.statements[b];\r
 118                 if(aStats.length != bStats.length)\r
 119                         return false;\r
 120                 THashSet<Stat> mappedStats = new THashSet<Stat>();\r
 121                 int[] aToB = this.aToB;\r
 122                 for(Stat stat : aStats) {\r
 123                         int mp = aToB[stat.p];\r
 124                         int mo = aToB[stat.o];\r
 125                         if(mp < 0 || mo < 0)\r
 126                                 return false;\r
 127                         mappedStats.add(new Stat(mp, mo));\r
 128                 }\r
 129                 for(Stat stat : bStats)\r
 130                         if(!mappedStats.contains(stat))\r
 131                                 return false;\r
 132                 return true;\r
 133         }\r
 134         \r
 135         public int maxSize() {\r
 136                 return Math.min(aGraph.resourceCount, bGraph.resourceCount);\r
 137         }\r
 138         \r
 139         public int[] getAToB() {\r
 140                 return aToB;\r
 141         }\r
 142         \r
 143         public int[] getBToA() {\r
 144                 return bToA;\r
 145         }\r
 146         \r
 147         public static int[] cut(int[] map, int domainSize, int rangeSize) {\r
 148                 int[] newMap = new int[domainSize];\r
 149                 for(int i=0;i<domainSize;++i) {\r
 150                         int temp = map[i];\r
 151                         if(temp >= rangeSize)\r
 152                                 newMap[i] = -1;\r
 153                         else\r
 154                                 newMap[i] = temp;\r
 155                 }\r
 156                 return newMap;\r
 157         }\r
 158         \r
 159         public void match() {\r
 160                 apply(IdentityMatchingStrategy.INSTANCE);\r
 161                 apply(CanonicalizingMatchingStrategy.INSTANCE);\r
 162                 while(true) {\r
 163                         if(size == maxSize())\r
 164                                 break;\r
 165                         int curSize = size;\r
 166                         apply(VotingMatchingStrategy.INSTANCE);\r
 167                         if(size == curSize)\r
 168                                 break;\r
 169                 }\r
 170                 aToB = cut(aToB, aOriginalSize, bOriginalSize);\r
 171                 bToA = cut(bToA, bOriginalSize, aOriginalSize);\r
 172         }\r
 173         \r
 174         private void apply(GraphMatchingStrategy strategy) {\r
 175                 if(TIMING) {\r
 176                         long begin = System.nanoTime();\r
 177                         strategy.applyTo(this);\r
 178                         long end = System.nanoTime();           \r
 179                         System.out.println(strategy.getClass().getSimpleName() + ": " + \r
 180                                         (end - begin)*1e-6 + "ms");\r
 181                 }\r
 182                 else\r
 183                         strategy.applyTo(this);\r
 184         }\r
 185 }\r