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

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