graph.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2003
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <climits>
namespace Gecode { namespace Int { namespace ViewValGraph {
template<class View>
forceinline
Graph<View>::Graph(void)
: view(NULL), val(NULL), n_view(0), n_val(0), count(1U) {}
template<class View>
forceinline
Graph<View>::operator bool(void) const {
return view != NULL;
}
template<class View>
forceinline void
Graph<View>::init(Space& home, ViewNode<View>* x) {
Edge<View>** edge_p = x->val_edges_ref();
ViewValues<View> xi(x->view());
ValNode<View>** v = &val;
while (xi() && (*v != NULL)) {
if ((*v)->val() == xi.val()) {
// Value node does already exist, create new edge
*edge_p = new (home) Edge<View>(*v,x);
edge_p = (*edge_p)->next_edge_ref();
v = (*v)->next_val_ref();
++xi;
} else if ((*v)->val() < xi.val()) {
// Skip to next value node
v = (*v)->next_val_ref();
} else {
// Value node does not yet exist, create and link it
ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
*v = nv; v = nv->next_val_ref();
*edge_p = new (home) Edge<View>(nv,x);
edge_p = (*edge_p)->next_edge_ref();
++xi; n_val++;
}
}
// Create missing value nodes
while (xi()) {
ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
*v = nv; v = nv->next_val_ref();
*edge_p = new (home) Edge<View>(nv,x);
edge_p = (*edge_p)->next_edge_ref();
++xi; n_val++;
}
*edge_p = NULL;
}
template<class View>
forceinline bool
Graph<View>::match(ViewNodeStack& m, ViewNode<View>* x) {
count++;
start:
// Try to find matching edge cheaply: is there a free edge around?
{
Edge<View>* e = x->val_edges();
// This holds true as domains are never empty
assert(e != NULL);
do {
if (!e->val(x)->matching()) {
e->revert(x); e->val(x)->matching(e);
// Found a matching, revert all edges on stack
while (!m.empty()) {
x = m.pop(); e = x->iter;
e->val(x)->matching()->revert(e->val(x));
e->revert(x); e->val(x)->matching(e);
}
return true;
}
e = e->next_edge();
} while (e != NULL);
}
// No, find matching edge by augmenting path method
Edge<View>* e = x->val_edges();
do {
if (e->val(x)->matching()->view(e->val(x))->min < count) {
e->val(x)->matching()->view(e->val(x))->min = count;
m.push(x); x->iter = e;
x = e->val(x)->matching()->view(e->val(x));
goto start;
}
next:
e = e->next_edge();
} while (e != NULL);
if (!m.empty()) {
x = m.pop(); e = x->iter; goto next;
}
// All nodes and edges unsuccessfully tried
return false;
}
template<class View>
forceinline void
Graph<View>::purge(void) {
if (count > (UINT_MAX >> 1)) {
count = 1;
for (int i=0; i<n_view; i++)
view[i]->min = 0;
for (ValNode<View>* v = val; v != NULL; v = v->next_val())
v->min = 0;
}
}
template<class View>
forceinline void
Graph<View>::scc(void) {
Region r;
Support::StaticStack<Node<View>*,Region> scc(r,n_val+n_view);
Support::StaticStack<Node<View>*,Region> visit(r,n_val+n_view);
count++;
unsigned int cnt0 = count;
unsigned int cnt1 = count;
for (int i=0; i<n_view; i++)
/*
* The following test is subtle: for scc, the test should be:
* view[i]->min < count
* However, if view[i] < count-1, then the node has already been
* reached on a path and all edges connected to the node have been
* marked anyway! So just ignore this node altogether for scc.
*/
if (view[i]->min < count-1) {
Node<View>* w = view[i];
start:
w->low = w->min = cnt0++;
scc.push(w);
Edge<View>* e = w->edge_fst();
while (e != w->edge_lst()) {
if (e->dst(w)->min < count) {
visit.push(w); w->iter = e;
w=e->dst(w);
goto start;
}
next:
if (e->dst(w)->low < w->min)
w->min = e->dst(w)->low;
e = e->next();
}
if (w->min < w->low) {
w->low = w->min;
} else {
Node<View>* v;
do {
v = scc.pop();
v->comp = cnt1;
v->low = UINT_MAX;
} while (v != w);
cnt1++;
}
if (!visit.empty()) {
w=visit.pop(); e=w->iter; goto next;
}
}
count = cnt0+1;
}
}}}
// STATISTICS: int-prop
Gecode::Int::ViewValGraph::Edge
Edges in view-value graph.
Definition view-val-graph.hh:208
Gecode::Int::ViewValGraph::Edge::val
ValNode< View > * val(ViewNode< View > *x) const
Return value node when view node x is given.
Definition edge.hpp:69
Gecode::Int::ViewValGraph::Edge::next_edge
Edge< View > * next_edge(void) const
Return next edge in list of value edges.
Definition edge.hpp:91
Gecode::Int::ViewValGraph::Edge::next_edge_ref
Edge< View > ** next_edge_ref(void)
Return reference to next edge in list of value edges.
Definition edge.hpp:96
Gecode::Int::ViewValGraph::Edge::dst
Node< View > * dst(Node< View > *s) const
Return destination of edge when source s is given.
Definition edge.hpp:51
Gecode::Int::ViewValGraph::Edge::next
Edge< View > * next(void) const
Return next edge in list of edges per node.
Definition edge.hpp:101
Gecode::Int::ViewValGraph::Edge::revert
void revert(Node< View > *d)
Revert edge to node d for matching.
Definition edge.hpp:57
Gecode::Int::ViewValGraph::Graph::ViewNodeStack
Support::StaticStack< ViewNode< View > *, Region > ViewNodeStack
Stack used during matching.
Definition view-val-graph.hh:307
Gecode::Int::ViewValGraph::Graph::purge
void purge(void)
Purge graph if necessary (reset information to avoid overflow).
Definition graph.hpp:130
Gecode::Int::ViewValGraph::Graph::Graph
Graph(void)
Construct graph as not yet initialized.
Definition graph.hpp:40
Gecode::Int::ViewValGraph::Graph::init
void init(Space &home, ViewNode< View > *x)
Initialize the edges for the view node x.
Definition graph.hpp:51
Gecode::Int::ViewValGraph::Graph::count
unsigned int count
Marking counter.
Definition view-val-graph.hh:305
Gecode::Int::ViewValGraph::Graph::view
ViewNode< View > ** view
Array of view nodes.
Definition view-val-graph.hh:297
Gecode::Int::ViewValGraph::Graph::match
bool match(ViewNodeStack &m, ViewNode< View > *x)
Find a matching for node x.
Definition graph.hpp:87
Gecode::Int::ViewValGraph::Graph::n_view
int n_view
Number of view nodes.
Definition view-val-graph.hh:301
Gecode::Int::ViewValGraph::Graph::n_val
int n_val
Number of value nodes.
Definition view-val-graph.hh:303
Gecode::Int::ViewValGraph::Graph::scc
void scc(void)
Compute the strongly connected components.
Definition graph.hpp:142
Gecode::Int::ViewValGraph::Graph::val
ValNode< View > * val
Array of value nodes.
Definition view-val-graph.hh:299
Gecode::Int::ViewValGraph::Node
Base-class for nodes (both view and value nodes).
Definition view-val-graph.hh:116
Gecode::Int::ViewValGraph::Node::edge_fst
Edge< View > * edge_fst(void) const
Return first edge (organized by bi-links).
Definition node.hpp:48
Gecode::Int::ViewValGraph::Node::min
unsigned int min
Definition view-val-graph.hh:121
Gecode::Int::ViewValGraph::Node::iter
Edge< View > * iter
Next edge for computing strongly connected components.
Definition view-val-graph.hh:119
Gecode::Int::ViewValGraph::Node::edge_lst
Edge< View > * edge_lst(void) const
Return last edge (organized by bi-links).
Definition node.hpp:53
Gecode::Int::ViewValGraph::Node::low
unsigned int low
Values for computing strongly connected components.
Definition view-val-graph.hh:121
Gecode::Int::ViewValGraph::ValNode
Value nodes in view-value graph.
Definition view-val-graph.hh:142
Gecode::Int::ViewValGraph::ValNode::next_val_ref
ValNode< View > ** next_val_ref(void)
Return pointer to next value node fields.
Definition node.hpp:99
Gecode::Int::ViewValGraph::ViewNode
View nodes in view-value graph.
Definition view-val-graph.hh:174
Gecode::Int::ViewValGraph::ViewNode::view
View view(void) const
Return view.
Definition node.hpp:145
Gecode::Int::ViewValGraph::ViewNode::val_edges
Edge< View > * val_edges(void) const
Return first edge of all value edges.
Definition node.hpp:130
Gecode::Int::ViewValGraph::ViewNode::val_edges_ref
Edge< View > ** val_edges_ref(void)
Return pointer to first edge fields of all value edges.
Definition node.hpp:135
Gecode::Int::ViewValues
Value iterator for integer views.
Definition view.hpp:94
Gecode::Iter::Ranges::ToValues::val
int val(void) const
Return current value.
Definition ranges-values.hpp:129
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::StaticStack
Stack with fixed number of elements.
Definition static-stack.hpp:42
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition static-stack.hpp:137
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition static-stack.hpp:116
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition static-stack.hpp:98
Gecode::Int::ViewValGraph
Support classes for propagators using a view-value graph.
Gecode::Int
Finite domain integers.
Gecode
Gecode toplevel namespace
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
forceinline
#define forceinline
Definition config.hpp:187