view-val-graph.hh
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Christian Schulte, 2002
* Guido Tack, 2004
*
* 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.
*
*/
#ifndef __GECODE_INT_VIEW_VAL_GRAPH_HH__
#define __GECODE_INT_VIEW_VAL_GRAPH_HH__
#include <gecode/int.hh>
namespace Gecode { namespace Int { namespace ViewValGraph {
template<class T>
class CombPtrFlag {
private:
ptrdiff_t cpf;
public:
CombPtrFlag(T* p1, T* p2);
void init(T* p1, T* p2);
T* ptr(T* p) const;
int is_set(void) const;
void set(void);
void unset(void);
};
class BiLink {
private:
BiLink* _prev;
BiLink* _next;
public:
BiLink(void);
BiLink* prev(void) const;
BiLink* next(void) const;
void prev(BiLink* l);
void next(BiLink* l);
void add(BiLink* l);
void unlink(void);
void mark(void);
bool marked(void) const;
bool empty(void) const;
};
template<class View> class Edge;
template<class View>
class Node : public BiLink {
public:
Edge<View>* iter;
unsigned int low, min, comp;
Node(void);
Edge<View>* edge_fst(void) const;
Edge<View>* edge_lst(void) const;
static void* operator new(size_t, Space&);
static void operator delete(void*, size_t);
static void operator delete(void*,Space&);
};
template<class View>
class ValNode : public Node<View> {
protected:
const int _val;
Edge<View>* _matching;
ValNode<View>* _next_val;
public:
ValNode(int v);
ValNode(int v, ValNode<View>* n);
int val(void) const;
void matching(Edge<View>* m);
Edge<View>* matching(void) const;
ValNode<View>** next_val_ref(void);
ValNode<View>* next_val(void) const;
void next_val(ValNode<View>* v);
};
template<class View>
class ViewNode : public Node<View> {
protected:
unsigned int _size;
View _view;
Edge<View>* _val_edges;
public:
ViewNode(void);
ViewNode(View x);
Edge<View>* val_edges(void) const;
Edge<View>** val_edges_ref(void);
bool fake(void) const;
View view(void) const;
void update(void);
bool changed(void) const;
bool matched(void) const;
};
template<class View>
class Edge : public BiLink {
protected:
Edge<View>* _next_edge;
CombPtrFlag<Node<View> > sd;
public:
Edge(ValNode<View>* v, ViewNode<View>* x);
Edge(ValNode<View>* v, ViewNode<View>* x, Edge<View>* n);
Node<View>* dst(Node<View>* s) const;
ViewNode<View>* view(ValNode<View>* v) const;
ValNode<View>* val(ViewNode<View>* x) const;
bool used(Node<View>* v) const;
void use(void);
void free(void);
void revert(Node<View>* d);
Edge<View>* next_edge(void) const;
Edge<View>** next_edge_ref(void);
Edge<View>* next(void) const;
static void* operator new(size_t, Space&);
static void operator delete(void*, size_t);
static void operator delete(void*,Space&);
};
template<class View>
class IterPruneVal {
protected:
ViewNode<View>* x;
Edge<View>* e;
public:
IterPruneVal(ViewNode<View>* x);
bool operator ()(void) const;
void operator ++(void);
int val(void) const;
};
}}}
#include <gecode/int/view-val-graph/comb-ptr-flag.hpp>
#include <gecode/int/view-val-graph/bi-link.hpp>
#include <gecode/int/view-val-graph/edge.hpp>
#include <gecode/int/view-val-graph/node.hpp>
#include <gecode/int/view-val-graph/iter-prune-val.hpp>
namespace Gecode { namespace Int { namespace ViewValGraph {
template<class View>
class Graph {
protected:
ViewNode<View>** view;
ValNode<View>* val;
int n_view;
int n_val;
unsigned int count;
typedef Support::StaticStack<ViewNode<View>*,Region> ViewNodeStack;
void init(Space& home, ViewNode<View>* x);
bool match(ViewNodeStack& m, ViewNode<View>* x);
void scc(void);
public:
Graph(void);
operator bool(void) const;
void purge(void);
};
}}}
#include <gecode/int/view-val-graph/graph.hpp>
#endif
// STATISTICS: int-prop
bi-link.hpp
Gecode::Int::ViewValGraph::BiLink::prev
BiLink * prev(void) const
Return previous element.
Definition bi-link.hpp:42
Gecode::Int::ViewValGraph::BiLink::add
void add(BiLink *l)
Add l after this element.
Definition bi-link.hpp:59
Gecode::Int::ViewValGraph::BiLink::unlink
void unlink(void)
Unlink this element.
Definition bi-link.hpp:64
Gecode::Int::ViewValGraph::BiLink::BiLink
BiLink(void)
Initialize as empty (self referenced).
Definition bi-link.hpp:37
Gecode::Int::ViewValGraph::BiLink::empty
bool empty(void) const
Whether element has no previous and next element.
Definition bi-link.hpp:78
Gecode::Int::ViewValGraph::BiLink::marked
bool marked(void) const
Whether element is marked.
Definition bi-link.hpp:74
Gecode::Int::ViewValGraph::BiLink::mark
void mark(void)
Mark element (invalidates next element pointer).
Definition bi-link.hpp:70
Gecode::Int::ViewValGraph::BiLink::next
BiLink * next(void) const
Return next element.
Definition bi-link.hpp:46
Gecode::Int::ViewValGraph::CombPtrFlag
Class for combining two pointers with a flag.
Definition view-val-graph.hh:54
Gecode::Int::ViewValGraph::CombPtrFlag::is_set
int is_set(void) const
Check whether flag is set.
Definition comb-ptr-flag.hpp:49
Gecode::Int::ViewValGraph::CombPtrFlag::init
void init(T *p1, T *p2)
Initialize with pointer p1 and p2.
Definition comb-ptr-flag.hpp:67
Gecode::Int::ViewValGraph::CombPtrFlag::set
void set(void)
Set flag.
Definition comb-ptr-flag.hpp:55
Gecode::Int::ViewValGraph::CombPtrFlag::CombPtrFlag
CombPtrFlag(T *p1, T *p2)
Initialize with pointer p1 and p2.
Definition comb-ptr-flag.hpp:38
Gecode::Int::ViewValGraph::CombPtrFlag::ptr
T * ptr(T *p) const
Return the other pointer when p is given.
Definition comb-ptr-flag.hpp:43
Gecode::Int::ViewValGraph::CombPtrFlag::unset
void unset(void)
Clear flag.
Definition comb-ptr-flag.hpp:61
Gecode::Int::ViewValGraph::Edge
Edges in view-value graph.
Definition view-val-graph.hh:208
Gecode::Int::ViewValGraph::Edge::Edge
Edge(ValNode< View > *v, ViewNode< View > *x)
Construct new edge between x and v.
Definition edge.hpp:38
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::sd
CombPtrFlag< Node< View > > sd
Combine source and destination node and flag.
Definition view-val-graph.hh:213
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::view
ViewNode< View > * view(ValNode< View > *v) const
Return view node when value node v is given.
Definition edge.hpp:64
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::free
void free(void)
Unmark node as used.
Definition edge.hpp:85
Gecode::Int::ViewValGraph::Edge::_next_edge
Edge< View > * _next_edge
Next edge in chain of value edges.
Definition view-val-graph.hh:211
Gecode::Int::ViewValGraph::Edge::use
void use(void)
Mark node as used.
Definition edge.hpp:80
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::Edge::used
bool used(Node< View > *v) const
Whether edge is used (marked or between nodes from the same scc).
Definition edge.hpp:75
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::IterPruneVal::x
ViewNode< View > * x
View node.
Definition view-val-graph.hh:257
Gecode::Int::ViewValGraph::IterPruneVal::val
int val(void) const
Return current value.
Definition iter-prune-val.hpp:58
Gecode::Int::ViewValGraph::IterPruneVal::IterPruneVal
IterPruneVal(ViewNode< View > *x)
Initialize with edges for view node x.
Definition iter-prune-val.hpp:38
Gecode::Int::ViewValGraph::IterPruneVal::operator++
void operator++(void)
Move iterator to next value (if possible).
Definition iter-prune-val.hpp:50
Gecode::Int::ViewValGraph::IterPruneVal::operator()
bool operator()(void) const
Test whether iterator is still at a value or done.
Definition iter-prune-val.hpp:45
Gecode::Int::ViewValGraph::IterPruneVal::e
Edge< View > * e
Current value edge.
Definition view-val-graph.hh:259
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::comp
unsigned int comp
Definition view-val-graph.hh:121
Gecode::Int::ViewValGraph::Node::Node
Node(void)
Initialize.
Definition node.hpp:43
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::_val
const int _val
The value of the node.
Definition view-val-graph.hh:145
Gecode::Int::ViewValGraph::ValNode::ValNode
ValNode(int v)
Initialize with value v.
Definition node.hpp:76
Gecode::Int::ViewValGraph::ValNode::matching
Edge< View > * matching(void) const
Return matching edge (NULL if unmatched).
Definition node.hpp:94
Gecode::Int::ViewValGraph::ValNode::_next_val
ValNode< View > * _next_val
The next value node.
Definition view-val-graph.hh:149
Gecode::Int::ViewValGraph::ValNode::_matching
Edge< View > * _matching
The matching edge.
Definition view-val-graph.hh:147
Gecode::Int::ViewValGraph::ValNode::next_val
ValNode< View > * next_val(void) const
Return next value node.
Definition node.hpp:104
Gecode::Int::ViewValGraph::ValNode::val
int val(void) const
Return value of node.
Definition node.hpp:84
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
The node's view.
Definition view-val-graph.hh:179
Gecode::Int::ViewValGraph::ViewNode::matched
bool matched(void) const
Whether the node is matched.
Definition node.hpp:160
Gecode::Int::ViewValGraph::ViewNode::view
View view(void) const
Return view.
Definition node.hpp:145
Gecode::Int::ViewValGraph::ViewNode::update
void update(void)
Update size of view after change.
Definition node.hpp:155
Gecode::Int::ViewValGraph::ViewNode::_size
unsigned int _size
The size of the view after last change.
Definition view-val-graph.hh:177
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::ViewValGraph::ViewNode::fake
bool fake(void) const
Test whether node has a fake view.
Definition node.hpp:140
Gecode::Int::ViewValGraph::ViewNode::changed
bool changed(void) const
Return whether view has changed its size.
Definition node.hpp:150
Gecode::Int::ViewValGraph::ViewNode::_val_edges
Edge< View > * _val_edges
The first value edge.
Definition view-val-graph.hh:181
Gecode::Int::ViewValGraph::ViewNode::ViewNode
ViewNode(void)
Initialize node for a non-view.
Definition node.hpp:122
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::View
comb-ptr-flag.hpp
edge.hpp
int.hh
node.hpp
iter-prune-val.hpp
Gecode::Int::ViewValGraph
Support classes for propagators using a view-value graph.
Gecode::Int
Finite domain integers.
Gecode
Gecode toplevel namespace
graph.hpp