1 #ifndef _EDGEGRAPH_FDJDJQPQ 2 #define _EDGEGRAPH_FDJDJQPQ 3 4 #include <set> 5 #include <string.h> 6 7 #include "abstract_constraint.hpp" 8 #include "../partition_stack.hpp" 9 #include "../partition_refinement.hpp" 10 #include "library/hash.hpp" 11 #include "library/mono_set.hpp" 12 #include "library/graph.hpp" 13 14 15 class GraphRefiner 16 { 17 18 GraphRefiner(); 19 public: GraphRefiner(int points)20 GraphRefiner(int points) : 21 mset(points, 0), 22 msetspare(points, 0), 23 edgesconsidered(0) 24 { 25 26 }; 27 28 // Construct these once, for use in filterGraph, as the cost is fairly big 29 vec1<HashType> mset; 30 vec1<HashType> msetspare; 31 32 int edgesconsidered; 33 34 template<typename GraphType> hashCellSimple(PartitionStack * ps,const GraphType & points,MonoSet & monoset,int cell)35 void hashCellSimple(PartitionStack* ps, const GraphType& points, MonoSet& monoset, int cell) 36 { 37 Range<PartitionStack::cellit> r = ps->cellRange(cell); 38 for(int i : r) 39 { 40 debug_out(4, "filter", "filtering " << i); 41 int i_cell = ps->cellOfVal(i); 42 int hash = quick_hash(i_cell); 43 debug_out(4, "filter", "initial cell" << ps->cellOfVal(i) << ":" << i_cell); 44 for(const auto& edge : points.neighbours(i)) 45 { 46 monoset.add(ps->cellOfVal(edge.target())); 47 HashType new_hash = quick_hash(hash + edge.colour()); 48 debug_out(4, "filter", "adding to " << edge << ":" << new_hash); 49 edgesconsidered++; 50 mset[edge.target()] += new_hash; 51 } 52 } 53 } 54 55 template<typename GraphType> hashNeighboursOfVertexDeep2(PartitionStack * ps,const GraphType & points,MonoSet & hitcells,int vertex,HashType hash)56 void hashNeighboursOfVertexDeep2(PartitionStack* ps, const GraphType& points, 57 MonoSet& hitcells, int vertex, HashType hash) 58 { 59 for(const auto& edge : points.neighbours(vertex)) 60 { 61 hitcells.add(ps->cellOfVal(edge.target())); 62 HashType new_hash = quick_hash(hash + edge.colour()); 63 edgesconsidered++; 64 msetspare[edge.target()] += new_hash; 65 } 66 } 67 68 template<typename Range, typename GraphType> hashRangeDeep2(PartitionStack * ps,const GraphType & points,MonoSet & hitcells,Range cell)69 void hashRangeDeep2(PartitionStack* ps, const GraphType& points, MonoSet& hitcells, Range cell) 70 { 71 for(int i : cell) 72 { 73 int i_cell = ps->cellOfVal(i); 74 int hash = quick_hash(i_cell + mset[i]); 75 hashNeighboursOfVertexDeep2(ps, points, hitcells, i, hash); 76 } 77 } 78 79 template<typename GraphType> hashNeighboursOfVertexDeep(PartitionStack * ps,const GraphType & points,MonoSet & hitcells,MonoSet & hitvertices,int vertex,HashType hash)80 void hashNeighboursOfVertexDeep(PartitionStack* ps, const GraphType& points, 81 MonoSet& hitcells, MonoSet& hitvertices, int vertex, HashType hash) 82 { 83 for(const auto& val : points.neighbours(vertex)) 84 { 85 hitcells.add(ps->cellOfVal(val.target())); 86 hitvertices.add(val.target()); 87 HashType new_hash = quick_hash(hash + val.colour()); 88 edgesconsidered++; 89 mset[val.target()] += new_hash; 90 } 91 } 92 93 template<typename Range, typename GraphType> hashRangeDeep(PartitionStack * ps,const GraphType & points,MonoSet & hitcells,MonoSet & hitvertices,Range cell)94 void hashRangeDeep(PartitionStack* ps, const GraphType& points, 95 MonoSet& hitcells, MonoSet& hitvertices, Range cell) 96 { 97 for(int i : cell) 98 { 99 int i_cell = ps->cellOfVal(i); 100 int hash = quick_hash(i_cell); 101 hashNeighboursOfVertexDeep(ps, points, hitcells, hitvertices, i, hash); 102 } 103 } 104 105 template<typename GraphType, typename CellList> filterGraph(PartitionStack * ps,const GraphType & points,const CellList & cells,int path_length)106 SplitState filterGraph(PartitionStack* ps, const GraphType& points, 107 const CellList& cells, int path_length) 108 { 109 timing_start("GraphRefining"); 110 // Would not normally go this low level, but it is important this is fast 111 memset(&(mset.front()), 0, mset.size() * sizeof(mset[0])); 112 edgesconsidered = 0; 113 MonoSet monoset(ps->cellCount()); 114 debug_out(3, "EdgeGraph", "filtering: " << cells.size() << " cells out of " << ps->cellCount()); 115 if(path_length == 1) { 116 for(int c : cells) 117 { 118 hashCellSimple(ps, points, monoset, c); 119 } 120 } 121 else 122 { 123 MonoSet hitvertices(ps->domainSize()); 124 for(int c : cells) 125 { 126 hashRangeDeep(ps, points, monoset, hitvertices, ps->cellRange(c)); 127 } 128 129 memset(&(msetspare.front()), 0, msetspare.size() * sizeof(msetspare[0])); 130 hashRangeDeep2(ps, points, monoset, hitvertices.getMembers()); 131 for(int i : range1(mset.size())) { 132 mset[i] += msetspare[i] * 71; 133 } 134 } 135 debug_out(3, "EdgeGraph", "filtering " << mset << " : " << monoset); 136 auto ret = filterPartitionStackByFunctionWithCells(ps, [&](auto i) -> auto& { return mset[i]; }, monoset); 137 timing_end("GraphRefining"); 138 return ret; 139 } 140 }; 141 142 template<typename VertexType, GraphDirected directed = GraphDirected_yes> 143 class EdgeColouredGraph : public AbstractConstraint 144 { 145 Graph<VertexType, directed> points; 146 GraphConfig config; 147 148 GraphRefiner refiner; 149 150 public: name() const151 virtual std::string name() const 152 { return "Graph<" + VertexType::type() + ">"; } 153 154 EdgeColouredGraph(const vec1<vec1<VertexType>> & _points,GraphConfig gc,PartitionStack * ps)155 EdgeColouredGraph(const vec1<vec1<VertexType> >& _points, GraphConfig gc, PartitionStack* ps) 156 : AbstractConstraint(ps), points(_points, ps->domainSize()), config(gc), 157 refiner(ps->domainSize()), 158 advise_branch_monoset(ps->domainSize()) 159 { } 160 private: 161 162 163 public: 164 triggers()165 std::vector<TriggerType> triggers() 166 { 167 std::vector<TriggerType> v; 168 v.push_back(Trigger_Change); 169 return v; 170 } 171 signal_start()172 SplitState signal_start() 173 { 174 return refiner.filterGraph(ps, points, range1(ps->cellCount()), config.start_path_length); 175 } 176 signal_changed(const vec1<int> & v)177 virtual SplitState signal_changed(const vec1<int>& v) 178 { 179 Stats::ConstraintInvoke(Stats::CON_EdgeGraph); 180 debug_out(1, "EdgeGraph", "signal_changed"); 181 return refiner.filterGraph(ps, points, v, config.normal_path_length); 182 } 183 184 // We cache this monoset to save allocations. 185 MonoSet advise_branch_monoset; advise_branch()186 virtual int advise_branch() 187 { 188 int best_cell = -1; 189 int best_neighbours = 0; 190 int best_size = std::numeric_limits<int>::max(); 191 for(int i : range1(ps->cellCount())) 192 { 193 if(ps->cellSize(i) > 1) 194 { 195 advise_branch_monoset.clear(); 196 int cellfirstmem = *(ps->cellStartPtr(i)); 197 for(const auto& edge : points.neighbours(cellfirstmem)) 198 { 199 int cell = ps->cellOfVal(edge.target()); 200 if(ps->cellSize(cell) > 1) 201 advise_branch_monoset.add(cell); 202 } 203 204 if(advise_branch_monoset.size() > best_neighbours || 205 (advise_branch_monoset.size() == best_neighbours && 206 ps->cellSize(i) < best_size) 207 ) 208 { 209 best_cell = i; 210 best_neighbours = advise_branch_monoset.size(); 211 best_size = ps->cellSize(i); 212 } 213 } 214 } 215 216 return best_cell; 217 } 218 verifySolution(const Permutation & p)219 virtual bool verifySolution(const Permutation& p) 220 { 221 for(int i : range1(points.vertices())) 222 { 223 const vec1<VertexType>& p_i = points.neighbours(i); 224 vec1<VertexType> image_set; 225 for(const auto& edge : p_i) { 226 int pnt = edge.target(); 227 int pnt_image = p[pnt]; 228 image_set.push_back(VertexType(pnt_image, edge.colour())); 229 } 230 std::sort(image_set.begin(), image_set.end()); 231 232 if(points.neighbours(p[i]) != image_set) { 233 return false; 234 } 235 } 236 return true; 237 } 238 }; 239 240 #endif 241