Graph of contractors and domains that model a problem in the constraint programming framework. Heterogeneous domains can be handled in the same network, which allows to deal with a wide variety of problems such as non-linear equations, differential systems, delays or inter-temporal equations. More...

#include <codac_ContractorNetwork.h>

Collaboration diagram for codac::ContractorNetwork:

[legend]

Public Member Functions
Definition
	ContractorNetwork ()
	Creates an empty Contractor Network (CN)

	~ContractorNetwork ()
	ContractorNetwork destructor.

int	nb_ctc () const
	Returns the number of contractors the graph is made of.

int	nb_dom () const
	Returns the number of domains the graph is made of.

bool	emptiness () const
	Returns `true` if one of the domains is empty, `false` otherwise.

Building the network (domains, contractors)
Interval &	create_interm_var (const Interval &i)
	Creates an Interval intermediate variable with a reference kept in the ContractorNetwork. The variable will be kept alive outside its definition block. This allows for instance to add constraints involving intermediate variables inside iteration loops. The variable exists in the CN but cannot be reached outside its definition block. Its deallocation is handled by the CN.

IntervalVector &	create_interm_var (const IntervalVector &iv)
	Creates an IntervalVector intermediate variable with a reference kept in the ContractorNetwork. The variable will be kept alive outside its definition block. This allows for instance to add constraints involving intermediate variables inside iteration loops. The variable exists in the CN but cannot be reached outside its definition block. Its deallocation is handled by the CN.

Tube &	create_interm_var (const Tube &t)
	Creates a Tube intermediate variable with a reference kept in the ContractorNetwork. The variable will be kept alive outside its definition block. This allows for instance to add constraints involving intermediate variables inside iteration loops. The variable exists in the CN but cannot be reached outside its definition block. Its deallocation is handled by the CN.

TubeVector &	create_interm_var (const TubeVector &tv)
	Creates a TubeVector intermediate variable with a reference kept in the ContractorNetwork. The variable will be kept alive outside its definition block. This allows for instance to add constraints involving intermediate variables inside iteration loops. The variable exists in the CN but cannot be reached outside its definition block. Its deallocation is handled by the CN.

IntervalVector &	subvector (Vector &v, int start_index, int end_index)
	Creates a subvector of a Vector domain.

IntervalVector &	subvector (IntervalVector &iv, int start_index, int end_index)
	Creates a subvector of an IntervalVector domain.

void	add (Ctc &static_ctc, const std::vector< Domain > &v_domains)
	Adds to the graph a static contractor (inherited from Ctc class) with related Domains.

void	add (DynCtc &dyn_ctc, const std::vector< Domain > &v_domains)
	Adds to the graph a dynamic contractor (inherited from DynCtc class) with related Domains.

void	add_data (Tube &x, double t, const Interval &y)
	Adds continuous data \([y]\) to a tube \([x](\cdot)\) at \(t\) (used for realtime applications).

void	add_data (TubeVector &x, double t, const IntervalVector &y)
	Adds continuous data \([\mathbf{y}]\) to a tube \([\mathbf{x}](\cdot)\) at \(t\) (used for realtime applications).

Contraction process
double	contract (bool verbose=false)
	Launch the contraction process.

double	contract (const std::unordered_map< Domain, Domain > &var_dom, bool verbose=false)
	Launch the contraction process with specified domains in place of Variables objects.

double	contract_during (double dt, bool verbose=false)
	Launch the contraction process and stops after \(dt\) seconds.

void	set_fixedpoint_ratio (float r)
	Sets the fixed point ratio defining the end of the propagation process.

void	trigger_all_contractors ()
	Triggers on all contractors involved in the graph.

void	reset_interm_vars ()
	Resets the initial value of the domains declared as intermediate variables.

int	nb_ctc_in_stack () const
	Returns the number of contractors that are waiting for process.

Protected Member Functions
Domain *	add_dom (const Domain &ad)
	Adds an abstract Domain to the graph.

Contractor *	add_ctc (const Contractor &ac)
	Adds an abstract Contractor to the graph.

void	add_ctc_to_queue (Contractor ac, std::deque< Contractor > &ctc_deque)
	Adds a Contractor object in the queue of active contractors.

void	trigger_ctc_related_to_dom (Domain dom, Contractor ctc_to_avoid=nullptr)
	Triggers on the contractors related to the given Domain.

Protected Attributes
std::map< DomainHashcode, Domain * >	m_map_domains
	pointers to the abstract Domain objects the graph is made of

std::map< ContractorHashcode, Contractor * >	m_map_ctc
	pointers to the abstract Contractor objects the graph is made of

std::deque< Contractor * >	m_deque
	queue of active contractors

float	m_fixedpoint_ratio = 0.0001
	fixed point ratio for propagation limit

double	m_contraction_duration_max = std::numeric_limits<double>::infinity()
	computation time limit

CtcDeriv *	m_ctc_deriv = nullptr
	optional pointer to a CtcDeriv object that can be automatically added in the graph

Visualization
void	set_name (Domain dom, const std::string &name)
	Sets a string name for a given Domain.

void	set_name (Ctc &ctc, const std::string &name)
	Sets a string name for a given static contractor.

void	set_name (DynCtc &ctc, const std::string &name)
	Sets a string name for a given dynamic contractor.

int	print_dot_graph (const std::string &cn_name="cn", const std::string &layer_model="fdp") const
	Generates a dot graph for visualization in PDF file format, by using dot2tex.

Detailed Description

Graph of contractors and domains that model a problem in the constraint programming framework. Heterogeneous domains can be handled in the same network, which allows to deal with a wide variety of problems such as non-linear equations, differential systems, delays or inter-temporal equations.

Member Function Documentation

◆ nb_ctc()

int codac::ContractorNetwork::nb_ctc ( ) const

Returns the number of contractors the graph is made of.

Returns: integer

◆ nb_dom()

int codac::ContractorNetwork::nb_dom ( ) const

Returns the number of domains the graph is made of.

Returns: integer

◆ emptiness()

bool codac::ContractorNetwork::emptiness ( ) const

Returns true if one of the domains is empty, false otherwise.

Returns: emptiness test

◆ create_interm_var() [1/4]

Interval & codac::ContractorNetwork::create_interm_var ( const Interval & i )

Creates an Interval intermediate variable with a reference kept in the ContractorNetwork. The variable will be kept alive outside its definition block. This allows for instance to add constraints involving intermediate variables inside iteration loops. The variable exists in the CN but cannot be reached outside its definition block. Its deallocation is handled by the CN.

Parameters

i	initial domain providing information on the type and initial set of values

Returns: a reference to the created Interval domain variable

◆ create_interm_var() [2/4]

IntervalVector & codac::ContractorNetwork::create_interm_var ( const IntervalVector & iv )

Creates an IntervalVector intermediate variable with a reference kept in the ContractorNetwork. The variable will be kept alive outside its definition block. This allows for instance to add constraints involving intermediate variables inside iteration loops. The variable exists in the CN but cannot be reached outside its definition block. Its deallocation is handled by the CN.

Parameters

iv	initial domain providing information on the type and initial set of values

Returns: a reference to the created IntervalVector domain variable

◆ create_interm_var() [3/4]

Tube & codac::ContractorNetwork::create_interm_var ( const Tube & t )

Creates a Tube intermediate variable with a reference kept in the ContractorNetwork. The variable will be kept alive outside its definition block. This allows for instance to add constraints involving intermediate variables inside iteration loops. The variable exists in the CN but cannot be reached outside its definition block. Its deallocation is handled by the CN.

Parameters

t	initial domain providing information on the type and initial set of values

Returns: a reference to the created Tube domain variable

◆ create_interm_var() [4/4]

TubeVector & codac::ContractorNetwork::create_interm_var ( const TubeVector & tv )

Creates a TubeVector intermediate variable with a reference kept in the ContractorNetwork. The variable will be kept alive outside its definition block. This allows for instance to add constraints involving intermediate variables inside iteration loops. The variable exists in the CN but cannot be reached outside its definition block. Its deallocation is handled by the CN.

Parameters

tv	initial domain providing information on the type and initial set of values

Returns: a reference to the created TubeVector domain variable

◆ subvector() [1/2]

IntervalVector & codac::ContractorNetwork::subvector	(	Vector &	v,
		int	start_index,
		int	end_index )

Creates a subvector of a Vector domain.

Note: Even if the input vector is a Vector object, the created domain is a set enclosing the subvector.

Parameters

v	Vector domain
start_index	first component index of the subvector to be returned
end_index	last component index of the subvector to be returned

Returns: a reference to the created IntervalVector extracted from the Vector domain

◆ subvector() [2/2]

IntervalVector & codac::ContractorNetwork::subvector	(	IntervalVector &	iv,
		int	start_index,
		int	end_index )

Creates a subvector of an IntervalVector domain.

Parameters

iv	IntervalVector domain
start_index	first component index of the subvector to be returned
end_index	last component index of the subvector to be returned

Returns: a reference to the created IntervalVector extracted from the IntervalVector domain

◆ add() [1/2]

void codac::ContractorNetwork::add	(	Ctc &	static_ctc,
		const std::vector< Domain > &	v_domains )

Adds to the graph a static contractor (inherited from Ctc class) with related Domains.

Note: If tubes are involved in the domain list, they must share the same slicing and tdomain. The static contractor will be applied on each slice of these tubes.

Parameters

static_ctc	Ctc contractor object
v_domains	a vector of abstract domains (Interval, Slice, Tube, etc.)

◆ add() [2/2]

void codac::ContractorNetwork::add	(	DynCtc &	dyn_ctc,
		const std::vector< Domain > &	v_domains )

Adds to the graph a dynamic contractor (inherited from DynCtc class) with related Domains.

Note: If tubes are involved in the domain list, they must share the same slicing and tdomain. If the contractor is not "inter-temporal", then it will be applied independently on each slice of these tubes.

Parameters

dyn_ctc	DynCtc contractor object
v_domains	a vector of abstract domains (Interval, Slice, Tube, etc.)

◆ add_data() [1/2]

void codac::ContractorNetwork::add_data	(	Tube &	x,
		double	t,
		const Interval &	y )

Adds continuous data \([y]\) to a tube \([x](\cdot)\) at \(t\) (used for realtime applications).

In this case, the tube represents an enclosure of a trajectory of measurements that are given in realtime.

t must increase at each call of this method. Slices of the tube will be contracted only if provided data completely cover their tdomain. Contracted slices will trigger related contractors, allowing constraint propagation in the graph.

Parameters

x	the tube \([x](\cdot)\) to be contracted with continuous data
t	time of measurement \(t\)
y	bounded measurement, equivalent to the set \([x](t)=[y]\)

◆ add_data() [2/2]

void codac::ContractorNetwork::add_data	(	TubeVector &	x,
		double	t,
		const IntervalVector &	y )

Adds continuous data \([\mathbf{y}]\) to a tube \([\mathbf{x}](\cdot)\) at \(t\) (used for realtime applications).

In this case, the tube vector represents an enclosure of a trajectory of vector measurements that are given in realtime.

t must increase at each call of this method. Slices of the tube will be contracted only if provided data completely cover their tdomain. Contracted slices will trigger related contractors, allowing constraint propagation in the graph.

Parameters

x	the tube \([\mathbf{x}](\cdot)\) to be contracted with continuous data
t	time of measurement \(t\)
y	bounded measurement, equivalent to the set \([\mathbf{x}](t)=[\mathbf{y}]\)

◆ contract() [1/2]

double codac::ContractorNetwork::contract ( bool verbose = false )

Launch the contraction process.

Contractions are performed until a fixed point has been reached on the whole graph.

Parameters

verbose verbose mode, false by default

Returns: the computation time in seconds

◆ contract() [2/2]

double codac::ContractorNetwork::contract	(	const std::unordered_map< Domain, Domain > &	var_dom,
		bool	verbose = false )

Launch the contraction process with specified domains in place of Variables objects.

Contractions are performed until a fixed point has been reached on the whole graph.

Parameters

var_dom	unordered map of type <Var,Domain>, for instance <IntervalVar,Interval>
verbose	verbose mode, `false` by default

Returns: the computation time in seconds

◆ contract_during()

double codac::ContractorNetwork::contract_during	(	double	dt,
		bool	verbose = false )

Launch the contraction process and stops after \(dt\) seconds.

Contractions are performed until a fixed point has been obtained on the whole graph, or if the computation time limit has been reached.

Note that the computation time may slightly exceed \(dt\).

Parameters

dt	allowed computation time
verbose	verbose mode, `false` by default

Returns: the computation time in seconds

◆ set_fixedpoint_ratio()

void codac::ContractorNetwork::set_fixedpoint_ratio ( float r )

Sets the fixed point ratio defining the end of the propagation process.

The ratio \(r\) is a percentage of contraction impact computed on the volume of the domains. For a given domain submitted to a contractor, if the contraction impact after contraction is more than the defined ratio, then the propagation is performed on other contractors related to this domain. Otherwise, the propagation process stops.

\(r=0\) means that the propagation is performed up to a fixed point defined by the floating-point precision value. \(r=0.1\) means that the propagation will be done only if the domain has been contracted by 10%.

Parameters

r	ratio of contraction, \(r\in[0,1]\)

◆ trigger_all_contractors()

void codac::ContractorNetwork::trigger_all_contractors ( )

Triggers on all contractors involved in the graph.

This method can be used to reset the propagation process when domains have been updated externally: outside the ContractorNetwork.

◆ nb_ctc_in_stack()

int codac::ContractorNetwork::nb_ctc_in_stack ( ) const

Returns the number of contractors that are waiting for process.

If the propagation process reached a fixed point, then this number is zero.

Returns: number of active contractors

◆ set_name() [1/3]

void codac::ContractorNetwork::set_name	(	Domain	dom,
		const std::string &	name )

Sets a string name for a given Domain.

Parameters

dom	domain to name
name	string of characters

◆ set_name() [2/3]

void codac::ContractorNetwork::set_name	(	Ctc &	ctc,
		const std::string &	name )

Sets a string name for a given static contractor.

Parameters

ctc	static contractor (inherited from Ctc) to name
name	string of characters

◆ set_name() [3/3]

void codac::ContractorNetwork::set_name	(	DynCtc &	ctc,
		const std::string &	name )

Sets a string name for a given dynamic contractor.

Parameters

ctc	dynamic contractor (inherited from DynCtc) to name
name	string of characters

◆ print_dot_graph()

int codac::ContractorNetwork::print_dot_graph	(	const std::string &	cn_name = "cn",
		const std::string &	layer_model = "fdp" ) const

Generates a dot graph for visualization in PDF file format, by using dot2tex.

Parameters

cn_name name of the graph (and rendered file)

layer_model

custom layer model for rendering (dot2tex)

dot - hierarchical or layered drawings of directed graphs
neato - attempts to minimize a global energy function, which is equivalent to statistical multi-dimensional scaling
fdp - layouts similar to those of neato, but does this by reducing forces rather than working with energy
sfdp - multiscale version of fdp for the layout of large graphs
twopi - radial layouts, nodes are placed on concentric circles depending their distance from a given root node
circo - circular layout, suitable for certain diagrams of multiple cyclic structures

Returns: system command success

◆ add_dom()

Domain * codac::ContractorNetwork::add_dom ( const Domain & ad )

protected

Adds an abstract Domain to the graph.

If an equal Domain already exists in the graph, then a pointer to it is returned, and the ad object is not added. Otherwise, ad is added and its pointer is returned.

Parameters

ad	abstract Domain object

Returns: the pointer to the related Domain object in the graph

◆ add_ctc()

Contractor * codac::ContractorNetwork::add_ctc ( const Contractor & ac )

protected

Adds an abstract Contractor to the graph.

If an equal Contractor already exists in the graph, then a pointer to it is returned, and the ac object is not added. Otherwise, ac is added and its pointer is returned.

Parameters

ac	abstract Contractor object

Returns: the pointer to the related Contractor object in the graph

◆ add_ctc_to_queue()

void codac::ContractorNetwork::add_ctc_to_queue	(	Contractor *	ac,
		std::deque< Contractor * > &	ctc_deque )

protected

Adds a Contractor object in the queue of active contractors.

Parameters

ac	Contractor to be added
ctc_deque	queue of contractors

◆ trigger_ctc_related_to_dom()

void codac::ContractorNetwork::trigger_ctc_related_to_dom	(	Domain *	dom,
		Contractor *	ctc_to_avoid = nullptr )

protected

Triggers on the contractors related to the given Domain.

Parameters

dom	pointer to the Domain
ctc_to_avoid	optional pointer to a Contractor to not activate

The documentation for this class was generated from the following file:

/home/simon/codac/src/core/cn/codac_ContractorNetwork.h

Public Member Functions

Protected Member Functions

Protected Attributes

Visualization

Detailed Description

Member Function Documentation

◆ nb_ctc()

◆ nb_dom()

◆ emptiness()

◆ create_interm_var() [1/4]

◆ create_interm_var() [2/4]

◆ create_interm_var() [3/4]

◆ create_interm_var() [4/4]

◆ subvector() [1/2]

◆ subvector() [2/2]

◆ add() [1/2]

◆ add() [2/2]

◆ add_data() [1/2]

◆ add_data() [2/2]

◆ contract() [1/2]

◆ contract() [2/2]

◆ contract_during()

◆ set_fixedpoint_ratio()

◆ trigger_all_contractors()

◆ nb_ctc_in_stack()

◆ set_name() [1/3]

◆ set_name() [2/3]

◆ set_name() [3/3]

◆ print_dot_graph()

◆ add_dom()

◆ add_ctc()

◆ add_ctc_to_queue()

◆ trigger_ctc_related_to_dom()