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