graph.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #include <climits>
00035
00036 namespace Gecode { namespace Int { namespace ViewValGraph {
00037
00038 template<class View>
00039 forceinline
00040 Graph<View>::Graph(void)
00041 : view(NULL), val(NULL), n_view(0), n_val(0), count(1U) {}
00042
00043 template<class View>
00044 forceinline
00045 Graph<View>::operator bool(void) const {
00046 return view != NULL;
00047 }
00048
00049 template<class View>
00050 forceinline void
00051 Graph<View>::init(Space& home, ViewNode<View>* x) {
00052 Edge<View>** edge_p = x->val_edges_ref();
00053 ViewValues<View> xi(x->view());
00054 ValNode<View>** v = &val;
00055 while (xi() && (*v != NULL)) {
00056 if ((*v)->val() == xi.val()) {
00057
00058 *edge_p = new (home) Edge<View>(*v,x);
00059 edge_p = (*edge_p)->next_edge_ref();
00060 v = (*v)->next_val_ref();
00061 ++xi;
00062 } else if ((*v)->val() < xi.val()) {
00063
00064 v = (*v)->next_val_ref();
00065 } else {
00066
00067 ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
00068 *v = nv; v = nv->next_val_ref();
00069 *edge_p = new (home) Edge<View>(nv,x);
00070 edge_p = (*edge_p)->next_edge_ref();
00071 ++xi; n_val++;
00072 }
00073 }
00074
00075 while (xi()) {
00076 ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
00077 *v = nv; v = nv->next_val_ref();
00078 *edge_p = new (home) Edge<View>(nv,x);
00079 edge_p = (*edge_p)->next_edge_ref();
00080 ++xi; n_val++;
00081 }
00082 *edge_p = NULL;
00083 }
00084
00085 template<class View>
00086 forceinline bool
00087 Graph<View>::match(ViewNodeStack& m, ViewNode<View>* x) {
00088 count++;
00089 start:
00090
00091 {
00092 Edge<View>* e = x->val_edges();
00093
00094 assert(e != NULL);
00095 do {
00096 if (!e->val(x)->matching()) {
00097 e->revert(x); e->val(x)->matching(e);
00098
00099 while (!m.empty()) {
00100 x = m.pop(); e = x->iter;
00101 e->val(x)->matching()->revert(e->val(x));
00102 e->revert(x); e->val(x)->matching(e);
00103 }
00104 return true;
00105 }
00106 e = e->next_edge();
00107 } while (e != NULL);
00108 }
00109
00110 Edge<View>* e = x->val_edges();
00111 do {
00112 if (e->val(x)->matching()->view(e->val(x))->min < count) {
00113 e->val(x)->matching()->view(e->val(x))->min = count;
00114 m.push(x); x->iter = e;
00115 x = e->val(x)->matching()->view(e->val(x));
00116 goto start;
00117 }
00118 next:
00119 e = e->next_edge();
00120 } while (e != NULL);
00121 if (!m.empty()) {
00122 x = m.pop(); e = x->iter; goto next;
00123 }
00124
00125 return false;
00126 }
00127
00128 template<class View>
00129 forceinline void
00130 Graph<View>::purge(void) {
00131 if (count > (UINT_MAX >> 1)) {
00132 count = 1;
00133 for (int i=0; i<n_view; i++)
00134 view[i]->min = 0;
00135 for (ValNode<View>* v = val; v != NULL; v = v->next_val())
00136 v->min = 0;
00137 }
00138 }
00139
00140 template<class View>
00141 forceinline void
00142 Graph<View>::scc(void) {
00143 Region r;
00144
00145 Support::StaticStack<Node<View>*,Region> scc(r,n_val+n_view);
00146 Support::StaticStack<Node<View>*,Region> visit(r,n_val+n_view);
00147
00148 count++;
00149 unsigned int cnt0 = count;
00150 unsigned int cnt1 = count;
00151
00152 for (int i=0; i<n_view; i++)
00153
00154
00155
00156
00157
00158
00159
00160 if (view[i]->min < count-1) {
00161 Node<View>* w = view[i];
00162 start:
00163 w->low = w->min = cnt0++;
00164 scc.push(w);
00165 Edge<View>* e = w->edge_fst();
00166 while (e != w->edge_lst()) {
00167 if (e->dst(w)->min < count) {
00168 visit.push(w); w->iter = e;
00169 w=e->dst(w);
00170 goto start;
00171 }
00172 next:
00173 if (e->dst(w)->low < w->min)
00174 w->min = e->dst(w)->low;
00175 e = e->next();
00176 }
00177 if (w->min < w->low) {
00178 w->low = w->min;
00179 } else {
00180 Node<View>* v;
00181 do {
00182 v = scc.pop();
00183 v->comp = cnt1;
00184 v->low = UINT_MAX;
00185 } while (v != w);
00186 cnt1++;
00187 }
00188 if (!visit.empty()) {
00189 w=visit.pop(); e=w->iter; goto next;
00190 }
00191 }
00192 count = cnt0+1;
00193 }
00194
00195
00196 }}}
00197
00198