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

   1 package org.simantics.graph.matching;
   2
   3 import gnu.trove.list.array.TIntArrayList;
   4 import gnu.trove.map.hash.TIntDoubleHashMap;
   5 import gnu.trove.map.hash.TIntIntHashMap;
   6 import gnu.trove.map.hash.TIntObjectHashMap;
   7 import gnu.trove.procedure.TIntDoubleProcedure;
   8 import gnu.trove.procedure.TIntObjectProcedure;
   9
  10 public enum VotingMatchingStrategy implements GraphMatchingStrategy {
  11         INSTANCE;
  12
  13         public static void vote(
  14                         final TIntDoubleHashMap[] voting,
  15                         int[] aToB,
  16                         int[] bToA,
  17                         Stat[] aStat,
  18                         Stat[] bStat,
  19                         final String[] bNames) {
  20                 final TIntObjectHashMap<TIntArrayList> aMap =
  21                         new TIntObjectHashMap<TIntArrayList>();
  22                 for(Stat stat : aStat) {
  23                         int mp = aToB[stat.p];
  24                         if(mp >= 0 && aToB[stat.o] < 0) {
  25                                 TIntArrayList l = aMap.get(mp);
  26                                 if(l == null) {
  27                                         l = new TIntArrayList(2);
  28                                         aMap.put(mp, l);
  29                                 }
  30                                 l.add(stat.o);
  31                         }
  32                 }
  33                 TIntObjectHashMap<TIntArrayList> bMap =
  34                         new TIntObjectHashMap<TIntArrayList>();
  35                 for(Stat stat : bStat) {
  36                         int p = stat.p;
  37                         int o = stat.o;
  38                         if(bToA[p] >= 0 && bToA[o] < 0) {
  39                                 TIntArrayList l = bMap.get(p);
  40                                 if(l == null) {
  41                                         l = new TIntArrayList(2);
  42                                         bMap.put(p, l);
  43                                 }
  44                                 l.add(o);
  45                         }
  46                 }
  47                 /*System.out.println("---------------------------------------");
  48                 aMap.forEachEntry(new TIntObjectProcedure<TIntArrayList>() {
  49                         @Override
  50                         public boolean execute(int a, TIntArrayList b) {
  51                                 System.out.println("a " + bNames[a] + " -> " + b);
  52                                 return true;
  53                         }
  54                 });
  55                 bMap.forEachEntry(new TIntObjectProcedure<TIntArrayList>() {
  56                         @Override
  57                         public boolean execute(int a, TIntArrayList b) {
  58                                 System.out.println("b " + bNames[a] + " -> " + b);
  59                                 return true;
  60                         }
  61                 });*/
  62                 bMap.forEachEntry(new TIntObjectProcedure<TIntArrayList>() {
  63                         @Override
  64                         public boolean execute(int p, TIntArrayList bos) {
  65                                 TIntArrayList aos = aMap.get(p);
  66                                 if(aos != null && aos.size() <= 4 && bos.size() <= 4) {
  67                                         final double weight = 1.0 / bos.size();
  68                                         for(int i=0;i<aos.size();++i)
  69                                                 for(int j=0;j<bos.size();++j)
  70                                                         voting[aos.get(i)].adjustOrPutValue(bos.get(j), weight, weight);
  71                                 }
  72                                 return true;
  73                         }
  74                 });
  75         }
  76
  77         @Override
  78         public void applyTo(GraphMatching matching) {
  79                 int[] aToB = matching.aToB;
  80                 final int[] bToA = matching.bToA;
  81                 int resourceCount = aToB.length;
  82                 Stat[][] aStatements = matching.aGraph.statements;
  83                 Stat[][] bStatements = matching.bGraph.statements;
  84                 TIntIntHashMap aInv = matching.aGraph.inverses;
  85                 TIntIntHashMap bInv = matching.bGraph.inverses;
  86
  87                 TIntDoubleHashMap[] voting = new TIntDoubleHashMap[resourceCount];
  88                 for(int i=0;i<resourceCount;++i)
  89                         if(aToB[i] < 0)
  90                                 voting[i] = new TIntDoubleHashMap();
  91                 for(int s=0;s<resourceCount;++s) {
  92                         int ms = aToB[s];
  93                         if(ms >= 0 && ms < bStatements.length)
  94                                 vote(voting, aToB, bToA, aStatements[s], bStatements[ms], matching.bGraph.names);
  95                 }
  96
  97                 for(int a=0;a<resourceCount;++a) {
  98                         TIntDoubleHashMap votes = voting[a];
  99                         if(votes != null && !votes.isEmpty()) {
 100                                 final int[] best = new int[] { -1 };
 101                                 votes.forEachEntry(new TIntDoubleProcedure() {
 102                                         double bestWeight = 0.9;
 103                                         @Override
 104                                         public boolean execute(int b, double weight) {
 105                                                 if(weight > bestWeight && bToA[b] < 0) {
 106                                                         bestWeight = weight;
 107                                                         best[0] = b;
 108                                                 }
 109                                                 return true;
 110                                         }
 111                                 });
 112                                 if(best[0] >= 0) {
 113                                         int b = best[0];
 114                                         matching.map(a, b);
 115                                         if(aInv.contains(a) && bInv.contains(b) && aInv.get(a) != a)
 116                                                 matching.map(aInv.get(a), bInv.get(b));
 117                                 }
 118                         }
 119                 }
 120         }
 121
 122 }