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

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