README.md
1# CP-Profiler
2
3CP-Profiler provides search tree visualisations for executions of constraint programming solvers.
4
5## Table of Contents
6
7- [Building](#building)
8- [Usage](#usage)
9
10### Building
11
12Dependencies:
13
14- Qt5.x
15
16```
17 git submodule update --init
18 mkdir build && cd build
19 qmake .. && make
20```
21
22### Usage
23
241. Starting CP-Profiler
25
26 `cp-profiler.app/Contents/MacOS/cp-profiler` (Mac)
27
28This starts a local TCP server listening on one of the available ports (6565 by default).
29
302. Executing a supported solver
31
32The solver must implement the profiling protocol (TODO). Integration libraries are available if you wish to extend your solver to work with CP-Profiler.
33
34
35### The Protocol (high level)
36
37The following describes the protocol that a solver must implement to communicate with the profiler.
38
39The protocol distinguishes between the following types of messages: **`Start`**, **`Restart`**, **`Done`**, and **`Node`**.
40
41
42
43The **`Start`** message is sent at the beginning of the execution (**TODO**: multithreaded search). The message has two optional (?) parameters:
44
45- `Name`: execution's descriptor to be presented to the user (e.g. the model's name)
46- `Execution ID`: globally unique identifier used to distinguish between different executions.
47
48**TODO**: any other parameters?
49
50The **`Restart`** message is sent whenever a solver performs a restart in case of a restart-based search.
51
52The **`Done`** message is sent to the profiler at the end of the execution to indicate that no further nodes should be expected.
53
54The **`Node`** message is sent whenever a new node is explored by the solver and contains information necessary for reconstructing the search tree. The required parameters are:
55
56- `Node ID`: unique node identifier in the execution.
57- `Parent ID`: the identifier (`Node ID`) of the parent node. A root node can have an identifier of `-1`. (**TODO**: needs checking)
58- `Alternative`: the node's position relative to its siblings; for the left-most child it is `0`, for the second left-most it is `1` etc.
59- `Number of Children`: the number of children nodes. If not known, can be set to `0` and the node will be extended with extra children later on if necessary. It is, however, advisable to specify the number of children the profiler should expect (for example, the yet to arrive nodes can be visualised to give a better idea about the search).
60- `Status`: allows to distinguish between different types of nodes. Supported values are:
61 - *BRANCH*: internal node in the tree;
62 - *SOLUTION*: leaf node representing a solution;
63 - *FAILURE*: leaf node representing a failure;
64 - *SKIPPED*: leaf node representing unexplored search space due to backjumping.
65
66**Example**. The following sequence of nodes (excluding the `Start` and `Done` messages) produces the simple tree below:
67
68| `Label` | `Node ID` | `Parent ID` | `Alternative` | `Number of Children` | `Status` |
69|:--------:|:---------:|:-----------:|:-------------:|:--------------------:|:--------:|
70| Root | 0 | -1 | -1 | 2 | BRANCH |
71| Failure | 1 | 0 | 0 | 0 | FAILED |
72| Solution | 2 | 0 | 1 | 0 | SOLVED |
73
74
75
76### The Protocol (low level)
77
78Each message starts with a four-byte integer encoding the size of the remainder of the message in bytes. This is followed by a single byte encoding the type of the message. The corresponding values are: **`Node`**: `0`, **`Done`**: `1`, **`Start`**: `2`, **`Restart`**: `3`.
79
80#### `Node` message
81
82In case the message is of the type **`Node`**, the following fields are added in order: `id`, `pid`, `alt`, `children` and `status`.
83
84Node identifiers `id` and `pid` are represented using three four-byte integers: first identifies the identifier of the node within a thread, the second — the identifier of the restart (in a restart-based search), and the third — the identifier of the thread.
85The `alt` and `children` fields are represented by a single four byte integer each.
86The `status` field is represented by a single byte; its possible values are: *SOLVED*: 0, *FAILED*: 1, *BRANCH*: 2, *SKIPPED*: 3.
87All multi-byte integer values are encoded using the *two's compliment* notation in the *big-endian order*.
88
89Additionally, each node message can contain the following optional fields:
90- `label`: branching decision (or any arbitrary string to be drawn together with the node);
91- `nogood`: string representation of a newly generated nogood in a learning solver;
92- `info`: arbitrary information about the node (*TODO*).
93
94Field identifiers and their sizes in bytes:
95
96| field name | field id | size (bytes) |
97|:----------:|:--------:|:------------:|
98| `id` | n/a | 12 |
99| `pid` | n/a | 12 |
100| `alt` | n/a | 4 |
101| `children` | n/a | 4 |
102| `status` | n/a | 1 |
103| `label` | 0 | any |
104| `nogood` | 1 | any |
105| `info` | 2 | any |
106
107**Example**. The following is a possible correspondence between a solver and the profiler that generates the simple tree above.The order in which different fields arrive is shown from top to bottom (rows are numbered for convenience).
108
109*Message 1:*
110
111| Row | Bytes | Interpretation |
112|-----|------------------------------------------------------------------------------------|-------------------------------|
113| 1 | `00 00 00 21` | message size (33) |
114| 2 | `02` | message type (*START*) |
115| 3 | `02` | field (*info*) |
116| 4 | `00 00 00 1B` | string size (27) |
117| 5 | `7b 22 6e 61 6d 65 22 3a 20 22 6d 69 6e 69 6d 61 6c 20 65 78 61 6d 70 6c 65 22 7d` | '{"name": "minimal example"}' |
118
119*Message 2:*
120
121| Row | Bytes | Interpretation |
122|-----|---------------|-------------------------|
123| 6 | `00 00 00 2B` | message size (43) |
124| 7 | `00` | message type (**NODE**) |
125| 8 | `00 00 00 00` | node id (0) |
126| 9 | `FF FF FF FF` | node restart id (-1) |
127| 10 | `FF FF FF FF` | node thread id (-1) |
128| 11 | `FF FF FF FF` | parent id (-1) |
129| 12 | `FF FF FF FF` | parent restart id (-1) |
130| 13 | `FF FF FF FF` | parent thread id (-1) |
131| 14 | `FF FF FF FF` | alternative (-1) |
132| 15 | `00 00 00 02` | children (2) |
133| 16 | `02` | status (*BRANCH*) |
134| 17 | `00` | field (label) |
135| 18 | `00 00 00 04` | string size (4) |
136| 19 | `52 6f 6f 74` | 'Root' |
137
138*Message 3:*
139
140| Row | Bytes | Interpretation |
141|-----|---------------|-------------------------|
142| 20 | `00 00 00 01` | message size (1) |
143| 21 | `01` | message type (**DONE**) |
144
145
146### Tree Visualisations
147
148#### Traditional Tree Visualisation
149
150When a new execution is connected to the profiler it will be added to the list of executions displayed at the top of the main window. For example, in the image below execution *golomb6a.fzn* is shown to be added to the profiler.
151To display the execution, select its name from the list and click the *Show Tree* button. Note that the solver can still be running the execution, in which case the profiler will draw the search tree in real time.
152
153
154
155The image below shows an example of a traditional (node-link) visualisation of the search tree. Different types of nodes are shown differently: branch (internal) nodes are shown as blue circles; nodes representing failures are shown as red squares; solution nodes are shown as green diamonds.
156
157Note that the root of the tree is shown in gold colour indicating the currently selected node. Arrow keys on the keyboard allow the user to navigate the tree by changing which node is selected. `Down` navigates to the first child of the current node, `Shift+Down` — to its last child, `Up` — to its the parent, `Left` — to its next sibling on the left, `Right` — to its next sibling on the right.
158Additionally, pressing `R` will navigate to the root of the tree.
159The same actions are available under the **`Navigation`** menu.
160
161
162
163
164If a subtree contains no solutions, it can be collapsed into a special single node displayed as a large red triangle. By default, the tree will be collapse failed subtrees automatically during its construction as a way to deal with large trees. The image below shows the same search tree as above, but with all failed subtrees collapsed.
165
166
167
168This view of the tree allows the user to show additional information for every node — its label, which usually represents the branching decision made by the solver to move from the parent node to its child. Pressing `L` on the keyboard will display labels for all descendants of the current node. `Shift+L` will display labels on the path to the current node.
169For example, the visualisation above shows branching decisions on the path from the first solution (shown as the new current node) to the root of the tree.
170
171Status bar at the bottom of the window displays node statistics: the depth of the tree and the counts of different types of nodes.
172The scroll bar on the right lets the user to zoom in/out on the visualisation;
173
174#### Similar Subtree Analysis
175
176This analysis allows users to find similarities within a single search tree.
177
178It can be initiated by selecting **`Similar Subtrees`** from the menu **`Analyses`** (shortcut: `Shift+S`).
179The image below shows the result of running the analysis on the search tree above.
180Horizontal bars on the left lists all similarities (patterns) found in the tree.
181Here, the lengths of the bars indicate are configured to indicate how many subtrees belong to a particular pattern (*count*).
182Additionally the bars are sorted so that the patterns with subtrees of larger *size* appear at the top.
183Another property of a pattern is its *height*, which indicates the height/depth of subtrees that the pattern represent.
184
185Note that the second from the top pattern is currently selected (shown with orange outline).
186The view on the right shows a "preview" (traditional visualisation) of one of the subtrees representing the selected pattern.
187The two rows below the show the result of computing the difference in labels on the path from the root to two of the subtrees representing the pattern (in this case it is the first two subtrees encountered when the tree is traversed in the depth-first-search order).
188
189
190
191Changing the configuration menu at the bottom of the window, the user can filter the list of patterns based on their *count* and *height* values.
192They way the length of horizontal bars is determined and the sorting criteria can also be specified there.
193
194Whenever a pattern on the left hand side is selected, the corresponding subtrees will be highlighted on the traditional visualisation by drawing their .
195Additionally, if the option *Hide not selected* is selected (top of the window), the subtrees of t
196
197
198
199**Elimination of subsumed patterns**
200
201A pattern `P` is said to be subsumed by one or more patterns if subtrees of those patterns
202contain all of the subtrees of `P` as descendants.
203
204**Applying filters.**
205
206Should filtered out patterns be allowed to subsume?
207
208
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}