Authors: R. Martin (Cosytec), J.-D. Fekete (INRIA), M. Ghoniem (EMN, Nantes)
Nota: the trace syntax analysis part of this software can be used to develop other tools.
Overview
Welcome to the Generic Trace Format Analysis Toolkit version
1.0.0, copyright (C) 2004 INRIA-Rocquencourt, France. This toolkit is designed
to read and analyze GENTRA4CP files. GENTRA4CP (GENeric TRAce for Constraint
Programming) is a new XML format suited to describe activities of a constraint
solver. It is available at http://contraintes.inria.fr/OADymPPaC/Public/Trace/index.html. It has been elaboreated in collaboration
with the following providers of CP tool :
GNU Prolog from INRIA
CHIP from COSYTEC S.A
PALM and CHOCO from Ecole des Mines de Nantes (EMN)
This format is one of the major result of the French RNTL project OADYMPPAC (see http://contraintes.inria.fr/OADymPPaC).
Licensing
This software is published under the terms of the QPL Software License, a
copy of which has been included with this distribution in the license-oadymppac.txt
file. This ToolKit is based on various Free libraries :
GL4JAVA to enhance graphical performances using OpenGL graphical cards (see http://www.jausoft.com/gl4java.html)
LOG4J to log application (see http://logging.apache.org/log4j)
INFOVIS to display graphs and matrices (see http://www.lri.fr/~fekete/InfovisToolkit)
Quick Start
Analysing a trace file
The first action the user must perform is to load a new GENTRA4CP file. To
do so, use the File->Open. The application shows a File selection box.
You can then choose an XML or XML.GZ (compressed) GENTRA4CP file. When chosen
the file, precise the type(s) of analysis to perform. (see Analyzers paragraph
for details) When the OK is clicked, XML file parsing and trace analysis
start. A constant refresh of default views is performed. If the file has
many events a Progress box is displayed. It is possible to interrupt the
analysis. In this case, the application will use only the amount of data
that have been read before the user’s interuption. By this way, it is possible
to work on part of a GENTRA4CP file. By default, visualizations are graph
represented by adgency Matrix.
NOTICE:
If no analysis has been chosen, the file is only parsed. Analysis can be
called back later using the Analysis menu. Tools provided here are not suited
to observe trace containing millions of events. Not only the parsing and
analysis of the trace will be painfully slow but also, visualization results
will also be very confusing.
Concept of visualization
This Toolkit is based on the generic visualization library INFOVIS. The main
concept and aim of this library is to display any kind of complex dataset
using various kind of graphical representations. To do so, the Dataset is
organized into a series of tables of columns :
Rows represents entities to be displayed
Column represents attributes of entities.
A table content is generally consistent (entities of same nature) but it is not absolutely required
Null or empty values are allowed
Values can be numerical of symbolic
References to others entities are allowed
Based on this generic and flexible framework, INFOVIS is able to produced various representations of the dataset.
INFOVIS visualization are dynamic. So any parameter change of value addition
or removal impact immediately the graphical representation.
INFOVIS visualization are reactive : By clicking on a displayed item, it
possible to get the complete description of the corresponding entity.
Modifying the visualization parameters
At the left side of the main application window, the workspace can contain
several visualization windows. At the right side of the main application
window, the workspace contain the configuration panel of the selected visulaization.
The two workspace are separated by an adjustable grip. Using the configuration
panel, it possible to manipulate and reconfigurate the visualization.
This panel is organized in four tabs :
Filter : Each column (attribute of entities) can be filtered to obtain visualization on a subset of datas.
Visual : Each column (attribute of entities) can be used to define color, size, labels,.. of displayed items in a visualization
Excentric labels : A new “tooltip” concept enabling to display large amount of information (no yet available)
Fisheyes : Magnify glass with parameterizable distorsion.
Using these for tabs, it is possible to enrich the dataset representation.
Changing visualization type
INFOVIS can display the same dataset using multiple graphical aspect. The
GENTRA4CP analysis toolkit offers four different kinds of representation
:
Graph node – link
Adgency Matrix
Time series
Scatter Plot
To get a new visualuzation, use the Visualization menu. The visualization corresponding to the dataset produced during the last analysis will be redisplayed using the selected representation.
Managing multiple windows
Performing multiple analysis, using different kind of visualization will
multiply the number of displayed windows and of course overlapping. Rather
than manually resizing and placement the multiples windows, the toolkit allows
several option of windows arrangments :
Horizontal tiling : Window occupy the full width of the workspace
Vertical tiling : Windows occupy the full height of the workspace
Mosaic : Windows are layouted on a rectangular/square grid.
Cascade : Windows are cascaded, i.e. sequentially placed in front.
Manual reisizing and placement is obviously possible,
just like closing and iconifying windows. The toolkit also provides a zoom
capability on the selected window.
Zoom in : reduce the visualization making items twice bigger.
Zoom out: enlarge the visualization making items twice smaller.
Stepped and animated observations
One of the main aim of this tool is to show the dynamic of the resolution
of the traced CP solver. To do so, it exists two way :
A step by step observation : shows the state and evolutions of the system on a reduced range of events
An animated observation : replay the evolution of the resolution
First of all, to use these features, it is necessary
to display on the visualization an “historized” criteria, by selecting Column
Activation
Propagation Qty
For instance, in tab Visual, select Activation in the Color by combo-box. To reduce the observation to a particular segment of trace, use the slider at the bottom of the main wokspace. Adjust the knob of the slider to the willing range. Some part of the visualization will be desactivated. By dragging the knob, it is possible to observe the evolution of the system by segment of execution having the same size By resizing the knob, it is possible to observe the evolution of thesystem on larger/smaller segment of execution By using the Forward/Rewind buttons (<< and >>) it is possible to progress step by step. The step is equal to the half size of the knob. To obtained an animated observation, use the Play (>) button at the bottom left of the main aplication window. The animation starts, replaying evolution of the system event by event. To have a more significant animation, it is possible to adjust the regular step of the animation. To adjust, enter in the text filed at the right of the Play button the number of events wanted. For instance, entering 10 will configure the animation to replay excution by slice of ten events. Animation stop is done by pressing the Play button.
NOTICE :
It is not necessary to stop the animation to modify it step. Step can be adjusted during a playing animation.
Analysis of trace file
Currently this toolkit performed two kind of analysis to observe the concept of propagation of CP Solver:
Influence of the constraints of the problem on variables of the problem (reduction)
Influence of the constraints one to other (propagation chains and explanation)
Variable-Constraint analysis
This feature constructs the weighted graph of reduction of the domains of
the variables by the constraints. Node of this graph are variables or constraints
( labelling constraint included) This graph is obtained as follow :
For each <new-variable> event found in the GENTRA4CP file, a variable node is added to the graph
For each <new-constraint> event found in the GENTRA4CP file, a constraint node is added to the graph
For each <reduce> event found in the GENTRA4CP file, the edge between the constraint node and the variable node is :
Created if not exists. Its Activation weight is set to 1. Its Propagation Qty is calculated (see below)
if exists, its Activation weight is incremented of 1. Its Propagation Qty is incremented with the reduction weight
Visualizing the results of this analysis can show efficiency of contraints to reduce domains of variables.
Constraint-Constraint analysis
This feature constructs the weighted graph of relation between constraints.
If <explanation> are provided in the GENTRA4CP file, then the graph
is obtained as follow :
For each <new-constraint> event found in the GENTRA4CP file, a constraint node is added to the graph
For each <reduce> event found in the GENTRA4CP file, and for each constraint
referenced in the provided explanation, an edge between the reduce constraint
and the explanation constraint is:
Created if not exists. Its Activation weight is set to 1. Its Propagation Qty is calculated using reduce (see below)
If exists, its Activation weight is incremented of 1. Its Propagation Qty is incremented with the reduction weight
If <awake> are provided in in the GENTRA4CP file, then the graph is obtained as follow :
For each <new-constraint> event found in the GENTRA4CP file, a constraint node is added to the graph
For each <awake> event found in the GENTRA4CP file,
for each variable reference by an <update> of the <awake>
for each constraint attached to the variable, an edge between the <awake> constraint and the current constraint is:
Created if not exists. Its Activation weight is set to 1.
If exists, its Activation weight is incremented of 1.
For each <reduce> event found in the GENTRA4CP file,
for each constraint attached to the variable of the <reduce>, if exists
an edge between the two constraints, Propagation Qty is incremented with
the reduction weight
If only <reduce> are provided in in the GENTRA4CP file, then the graph is obtained as follow :
For each <new-constraint> event found in the GENTRA4CP file, a constraint node is added to the graph
For each <reduce> event found in the GENTRA4CP file,
for each constraint attached to the variable, an edge between the <reduce> constraint and the current constraint is:
Created if not exists. Its Activation weight is set to 1. Its Propagation Qty is calculated using reduce (see below)
If exists, its Activation weight is incremented of 1. Its Propagation Qty is incremented with the reduction weight
Evaluation of Propagation Qty
Propagation quantity is always calculated with <reduce> event information, as follow:
If a <delta> is provided, then the quantity of propagation is equal to the number of values appering in the <delta>
If a <vardomain> is provided, the the quantity of propagation is equal
to the diiference of the <vardomain> size and the previous domain size.
The size can be given directly in the GENTRA4CP file
The size can be calculated using range and values given into the <vardomain>
Conlusions and perspectives
This toolkit is an ongoing work. Its initial objective was to mix CP Solver
trace and generic visualization tools. We hope this coulbe helpful to observe
propagation of your own CP solvers We also try to enhance this toolkit by
providing new kind of tools. We aim at defining a much more complete debugging
suite for CP Solvers supporting GENTRA4CP. We are expecting your feedbacks.