Fati Chen

Laurent Piccinini

Pascal Poncelet

Arnaud Sallaberry

Node Overlap Removal Algorithms: A Comparative Study

Keywords: Graph drawing, Layout adjustment, Node overlap removal

Many algorithms have been designed to remove node overlapping, and many quality criteria and associated metrics have been proposed to evaluate those algorithms. Unfortunately, a complete comparison of the algorithms based on some metrics that evaluate the quality has never been provided and it is thus difficult for a visualization designer to select the algorithm that best suits his needs. In this paper, we review 21 metrics available in the literature, classify them according to the quality criteria they try to capture, and select a representative one for each class. Based on the selected metrics, we compare 8 node overlap removal algorithms. Our experiment involves 854 synthetic and real-world graphs.

Introduction

Graph drawing algorithms are good at creating rich expressive graph layouts but often consider nodes as points with no dimensions. After changing the size of nodes in the case of annotation or evolving graphs, it causes node overlap which hides information. Post-process algorithms, named layout adjustment [START_REF] Misue | Layout adjustment and the mental map[END_REF], have been proposed to remove node overlap.

The objective of these algorithms is, given an initial positioning of the nodes and a size for each one, to provide a new embedding so that there are no overlapping nodes any more. A classical zoom-in function maintaining the sizes of the nodes (i.e. uniform scaling) provides such an embedding, but it expands the visualisation, resulting in large areas without any objects. Therefore, a node overlap removal algorithm must take into account the area of the drawing, and try to minimise it. Positioning the nodes evenly on a grid meets this objective but will result in the loss of the user's mental picture of the original embedding. Thus, it is also important to minimise the change on the layout.

Since a preliminary work in 1995 [START_REF] Misue | Layout adjustment and the mental map[END_REF], many algorithms have been designed to reach these purposes, and many quality criteria have been proposed to evaluate them. Unfortunately, a complete comparison of the algorithms based on the different criteria has never been provided and it is thus difficult for a visualisation designer to select the one that best suits his needs.

In this paper, our contribution comes in two forms: [START_REF] Barabaśi | Emergence of scaling in random networks[END_REF] We propose a classification of 21 quality metrics, grouping them according to the quality criterion they try to capture. We also discuss their relevance and we select a representative one for each class. [START_REF] Chimani | The open graph drawing framework (OGDF)[END_REF] We compare state-of-the-art node overlapping approaches in regards to the previously selected metrics. This experiment involves 854 graphs, including synthetic ones (random, tree, scale-free, small-world) and real world ones.

The paper is organised as follows: after a brief reminder in Sec.2 of the definitions and the notations used in this paper, we present and discuss the quality criteria and the metrics in Sec. 3. Then we compare the algorithms in Sec. 4. Finally we conclude in Sec. 5.

Preliminaries

In this paper, we use the following definitions and notations.

G = (V, E) denotes a graph where V is the set of nodes and E the set of edges. The number of nodes |V | is denoted by n and the number of edges |E| by m. We consider each node as a rectangle. Thus, for a node v ∈ V , its width and its height are denoted by the couple (w v , h v ) which is not impacted by the layout adjustment.

The initial embedding is defined as an injection

E G : V → R 2 such that ∀v ∈ V , E G (v) = (x v , y v )
where (x v , y v ) are the coordinates of the center of the node v. The overlapping-free embedding is denoted by E G . To simplify notations, we denote

v = (x v , y v ) instead of E G (v), and v = (x v , y v ) instead of E G (v).
Remark that two nodes (u, v) ∈ V 2 are overlapping when :

|x v -x u | < w v + w u 2 and |y v -y u | < h v + h u 2
The bounding box Bb of an embedding E G is defined as the smallest rectangle containing all the nodes of G; w bb (resp. h bb ) denotes the width (resp. the height) of the initial embedding, w bb (resp. h bb ) denotes the width (resp. the height) of the overlapping-free one. They are determined as follows:

w bb = max v∈V x v + w v 2 -min u∈V x u - w u 2 (1)
h bb = max v∈V y v + h v 2 -min u∈V y u - h u 2 (2)
The position of the center of the bounding box is denoted by c bb = (x bb , y bb ) in the initial embedding, and c bb = (x bb , y bb ) in the overlapping-free embedding.

The convex hull of an embedding E G is defined as the smallest convex region containing all the nodes of G. Note that it is computed by using the 4 corners of the nodes, and not only their center, in a way that the rectangles representing the nodes are fully included into it. In the following, Ch denotes the convex hull of the original embedding, Ch the convex hull of the free-overlapping one, c ch the center of mass of Ch, c ch the center of mass of Ch .

Quality Criteria

Many criteria have been proposed in the literature to evaluate the quality of the embeddings resulting from adjustment algorithms. Unfortunately, the experiments provided by the authors of the different approaches are not always based on the same metrics. With a view to provide a uniform protocol of experiment and a complete comparison of the algorithms, we need to review the quality criteria and the metrics used to evaluate them. We also need to select a representative metric for each criterion.

We identified 5 classes of metrics (Orthogonal Ordering preservation, Spread minimisation, Global Shape preservation, Node Movement minimisation and Edge Length preservation), each of them depicting a quality criterion. Table 1 shows the metrics assigned into the classes. The formulas are given in the discussion below.

The following subsections contain the metrics of a specific class. In each of them, we select one representative metric, based on the corresponding quality criterion and the properties that the metrics aim at capturing. Our discussion also sometimes involves the coefficient of correlation of two metrics run following the protocol described in the comparison section, Sec. 4.

Orthogonal Ordering Preservation

The orthogonal ordering class groups the metrics which try to quantify how much an adjustment algorithm preserves the initial orthogonal ordering. We recall that the orthogonal ordering is respected when all nodes satisfy the following conditions:

         x u < x v ⇔ x u < x v y u < y v ⇔ y u < y v x u = x v ⇔ x u = x v y u = y v ⇔ y u = y v
The first metric of this class, oo_o [START_REF] Misue | Layout adjustment and the mental map[END_REF], is equal to 1 if the overlapping-free graph embedding preserves the initial orthogonal ordering, 0 otherwise. Also, if only one couple of nodes does not satisfy those conditions, the value of oo_o is the same as when many ones do not satisfy it.

To overcome this issue, Huang et al. [START_REF] Huang | A new algorithm for removing node overlapping in graph visualization[END_REF] proposed a metric based on the Kendall's Tau distance. For each couple of nodes, they first compute an inversion number inv(u, v) corresponding to 0 if the orthogonal ordering is preserved between them, 1 otherwise. The metric is then defined as the normalised sum of Table 1. List of metrics classified by the quality criteria they try to capture: metrics selected for the comparison appear in bold italics. The Abbreviations are based on some initials of the names. For example, sp_bb_a means that the metric is in the class Spread minimisation, it uses the embedding Bounding Box to quantify the Area spreading. The Range column contains the set of values that the metric can take. The Target column refers to the target value to meet the corresponding criterion. the inversion numbers:

Abbreviation

oo_kt = u =v inv(u, v) n(n -1)
Strobelt et al. [START_REF] Strobelt | Rolled-out wordles: A heuristic method for overlap removal of 2d data representatives[END_REF] introduced the number of inversions:

oo_ni = (u,v)∈V 2 xu>xv 1 if x u < x v 0 otherwise + (u,v)∈V 2 xu>xv 1 if y u < y v 0 otherwise
This metric has the drawback of providing non-normalized values. However, it holds the benefit of penalizing inversions occurring on each axis independently (x-and y -axis), instead of penalizing in the same manner an inversion occurring in only one axis and an inversion occurring in the two axes. Thus, in our study, we combine the two metrics by using a normalised version of the latter:

oo_nni = oo_ni n(n -1)

Spread Minimisation

A classical zoom-in function maintaining the sizes of the nodes (i.e. uniform scaling) provides an overlapping-free embedding, but it expands the visualisation, resulting in large areas without any objects. To avoid this issue, quality metrics have been introduced to quantify embedding spreading. Their purpose is to favour algorithms inducing low spreading. The L1 metric length [START_REF] Li | Using spring algorithms to remove node overlapping[END_REF] is the ratio:

sp_bb_l1ml = max(w bb , h bb ) max(w bb , h bb )
The drawback of this technique is to consider only one dimension of the embedding, width or height. For instance, considering an example where w bb = 4, h bb = 2, w bb = 4, h bb = 4, the value of the L1 metric length is 1 (which is the target value), whereas the area of the overlapping-free embedding is twice as large as in the initial embedding. The ratio between the bounding box areas of the two embeddings [START_REF] Misue | Layout adjustment and the mental map[END_REF] overcomes this issue:

sp_bb_a = w bb × h bb w bb × h bb
While the result gives an unbounded value greater than 1, Huang et al. [START_REF] Huang | A new algorithm for removing node overlapping in graph visualization[END_REF] proposes a normalised version producing values in the interval [0, 1[:

sp_bb_na = 1 - w bb × h bb w bb × h bb
Unfortunately, this criterion is poorly intuitive and it is hard to figure out what the values represent.

In our comparison, we selected another version of the ratio of areas involving convex hulls [START_REF] Strobelt | Rolled-out wordles: A heuristic method for overlap removal of 2d data representatives[END_REF], as it better captures the concrete area of the drawing: sp_ch_a = area(Ch ) area(Ch)

Global Shape Preservation

This class contains metrics that try to capture the ability of the algorithms to preserve the global shape of the initial embedding. The first one was proposed by Li et al. [START_REF] Li | Using spring algorithms to remove node overlapping[END_REF]:

gs_bb_ar =        if w bb > h bb w bb × h bb h bb × w bb otherwise h bb × w bb w bb × h bb
The underlying idea is to capture the variation of the aspect ratio (w bb /h bb ) between the initial and the overlapping-free embedding. For instance, let us consider an example where w bb = 3, h bb = 2, w bb = 6, h bb = 4. In this case, the overlapping-free embedding is twice as large as the initial one but the aspect ratio remains the same 3/2. The gs_bb_ar is 1, which is the target value. Now let us consider another example where w bb = 3, h bb = 2, w bb = 4, h bb = 6. In this case, the initial aspect ratio is 3/2 whereas the overlapping-free one is 2/3. The gs_bb_ar is now 2.25, which is not the target value; it reveals a distortion of the initial embedding during the overlap removal process. The main drawback of this metric is that it can reach values in the interval ]0, +∞[ while the target value is 1. Thus, it is hard to decide, for instance, which algorithm is the best between two of them if the first one obtains a score of 0.67 and the second one a score of 4.56. To overcome this issue, we propose to refine it as follows:

gs_bb_iar = max w bb × h bb h bb × w bb , h bb × w bb w bb × h bb
In this case, the target value is 1 and the metric cannot reach values below it. This criterion is the one we selected for our study.

An alternative to this approach based on the convex hull has been proposed by Strobelt et al. [START_REF] Strobelt | Rolled-out wordles: A heuristic method for overlap removal of 2d data representatives[END_REF]. The idea is to evaluate the distortion of the convex hull by comparing, between both embeddings, the distances of convex hull points to their center. Let θ (resp. θ ) be the euclidean distance between the center of mass c ch (resp. c ch ) of the convex hull Ch (resp. Ch ) and the intersection of the convex hull with the line going through c ch (resp. c ch ) and with an angle θ (θ varying from 0 • to 350 • in 10 • steps). Then, the difference is defined as the ratio d θ = θ / θ . The metric is the standard deviation of the 36 measures of d θ :

gs_ch_sd = 1 36 θ=10k k=0,••• ,35 (d θ -d) 2
where d = 1 36

θ=10k k=0,••• ,35
d θ is the mean value Based on the experiments presented below in Sec. 4, we observed that gs_bb_iar and gs_ch_sd have a correlation coefficient of 0.77, showing that they both tend to capture similar aspects of the adjustment process. We selected the former for its simplicity and its ease of interpretation.

Node Movement Minimisation

This class contains the metrics quantifying the changes in node positions after running an adjustment algorithm. The underlying intuition is that an algorithm involving high node movements will provide an overlapping-free configuration different from the original one, and thus may result in a substantial loss of the mental model.

The simplest metric of this class was presented by Huang et al. [START_REF] Huang | A new algorithm for removing node overlapping in graph visualization[END_REF]:

nm_mn = nb n
Here, nb represents the number of nodes which have moved between the initial and the overlapping-free embedding. The main drawback of this approach is that a node overlap removal algorithm may induce very small changes in most nodes, which does not affect the mental model preservation, while inducing a very bad result. To tackle this problem and add more granularity over the evaluation of node movements, a series of metrics have been proposed, based on the same underlying quality function:

nm_dm = f (n) × v∈V dist(v, v )
where f is a normalising function of n = |V | and dist is a distance between v and v . Table 2 sums up the ones used in the literature.

Table 2. Functions used to tune the distances moved metric.

dist(v, v ) \ f (n) 1 1/n 1 k √ 2×n v -v nm_dm_me [17] nm_dm_ne [13] v -v 2 nm_dm_se [14] nm_dm_imse |x v -xv| + |y v -yv| nm_dm_h [10]
The function f comes in three different forms. Marriott et al. [START_REF] Marriott | Removing node overlapping in graph layout using constrained optimization[END_REF] and Huang et al. [START_REF] Huang | Force-transfer: a new approach to removing overlapping nodes in graph layout[END_REF] do not include any f , which is similar to having f (n) = 1. The drawback is that the resulting value highly depends on the number of nodes in the graph. That is why Strobelt et al. [START_REF] Strobelt | Rolled-out wordles: A heuristic method for overlap removal of 2d data representatives[END_REF] proposed to use the mean of the distances, which corresponds to f (n) = 1/n. Finally, Lyons et al. [START_REF] Lyons | Algorithms for cluster busting in anchored graph drawing[END_REF] proposed

f (n) = 1/(k √ 2 × n),
where k is the maximum between w bb and h bb . In this case, k √ 2 is the diagonal of a square containing the embedding, thus a maximum distance available for a node. Thus, this f function normalises the values of the metric. Unfortunately, this normalisation induces very small values that are hard to interpret. That is why we preferred using f (n) = 1/n for our study.

Three dist functions have been proposed in the literature. The most intuitive one is the Euclidean distance v -v [START_REF] Strobelt | Rolled-out wordles: A heuristic method for overlap removal of 2d data representatives[END_REF][START_REF] Lyons | Algorithms for cluster busting in anchored graph drawing[END_REF]. The squared Euclidean distance v -v 2 [START_REF] Marriott | Removing node overlapping in graph layout using constrained optimization[END_REF] avoids the square root computation and discriminates high changes better. It is the one we selected for our study. The Manhattan distance |x vx v | + |y v -y v | has also been used [START_REF] Huang | Force-transfer: a new approach to removing overlapping nodes in graph layout[END_REF], but it is less intuitive and has close results (nm_dm_se and nm_dm_h have a correlation coefficient of 0.9).

Let us consider an adjustment algorithm that pushes nodes on the x-axis. The preservation of the global shape is not optimal but the preservation of the configuration should reach a good score, as a node on right-top in the initial embedding would remain on right-top in the overlapping-free embedding. In order to better capture the relative movement of a node between the two embeddings, a shif t function can be applied to align the center of the initial bounding box with the center of the final one, and a scale function to align the size of the initial bounding box to the size of the final one:

shif t(v) = (x v + x bb -x bb , y v + y bb -y bb ) scale(v) =(x v × w bb w bb , y v × h bb h bb )
Considering this, we selected the following node movement metric:

nm_dm_imse = 1 n × v∈V v -scale(shif t(v))
2 nm_d [5] (the complete formula is available in the paper) is also based on the idea that the metric should be based on modified initial positions to capture the relative movement of the nodes between the two embeddings. Besides including the shif t and the scale functions, it also rotates the initial embedding with an angle θ that minimizes the distances between the nodes of the initial embedding and the ones of the overlapping-free embedding:

rotation(v) = (x v cos θ -y v sin θ, x v sin θ + y v cos θ)
We have not included the rotation in our experiment as we consider that it can induce a loss of the mental model (think about the recognition of a map turned inside down).

An alternative to quantify how much an overlapping-free configuration may result in a substantial loss of the mental model is to look at the neighbourhoods at the nodes and compare them before and after the adjustment. Based on a KN N approach, Nachmanson et al. [START_REF] Nachmanson | Node overlap removal by growing a tree[END_REF] proposed the following metric:

nm_knn(k) = v∈V (k -|N k (v) ∩ N k (v )|)
where N k (v) (resp. N k (v )) denotes the k nearest neighbours of v (resp. v ), in terms of Euclidean distance, in the initial (resp. overlapping-free) embedding. We did not select this metric because, unlike the other metrics of the class, it requires to fix a parameter (k).

Edge Length Preservation

This class contains the two metrics based on edge lengths. The set of edges can be E or can be another set derived from the graph.

Standard force-based layout algorithms tend to produce uniform lengths of edges. Indeed, the first metric of this class captures whether the edge lengths of a graph remain uniform or not after applying an adjustment algorithm [START_REF] Li | Using spring algorithms to remove node overlapping[END_REF]:

el_r = max (u,v)∈E 2 u -v min (u,v)∈E 2 u -v
While many layout algorithms are not designed to produce uniform edge lengths, we did not select this approach, which is not related to the mental model preservation for these algorithms. We preferred the next one, based on a Delaunay triangulation. Let E dt be the set of edges of a Delaunay triangulation performed on the nodes of the initial embedding. The second metric of this class, el_rsdd, is based on computing the coefficient of variation, also known as the relative standard deviation, of the edge lengths ratio as follows [START_REF] Gansner | Efficient, proximity-preserving node overlap removal[END_REF]:

r uv = ||u -v || ||u -v|| , (u, v) ∈ E 2 dt r = 1 |E dt | (u,v)∈E 2 dt r uv el_rsdd = 1 |E dt | (u,v)∈E 2 dt (r uv -r) 2 r

Algorithms Comparison

In this section, we compare 8 algorithms of the literature in terms of quality and running time: uniform Scaling, PFS [START_REF] Misue | Layout adjustment and the mental map[END_REF], PFS' [START_REF] Hayashi | A layout adjustment problem for disjoint rectangles preserving orthogonal order[END_REF], FTA [START_REF] Huang | A new algorithm for removing node overlapping in graph visualization[END_REF], VPSC [START_REF] Dwyer | Fast node overlap removal[END_REF], PRISM [START_REF] Gansner | Efficient, proximity-preserving node overlap removal[END_REF], RWordle-L [START_REF] Strobelt | Rolled-out wordles: A heuristic method for overlap removal of 2d data representatives[END_REF], and GTREE [START_REF] Nachmanson | Node overlap removal by growing a tree[END_REF]. The quality of an overlapping-free embedding is evaluated with the metrics identified in the last section, by following a 3 steps procedure:

Step 1: Datasets We generate 840 synthetic graphs containing 10 to 1,000 nodes. These graphs are provided by 4 generation models available on the OGDF library [START_REF] Chimani | The open graph drawing framework (OGDF)[END_REF]: random graphs [START_REF] Erdös | On random graphs[END_REF], random trees, small world graphs [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], and scale-free graphs [START_REF] Barabaśi | Emergence of scaling in random networks[END_REF]. We also use 14 real-world graphs selected from the Graphviz test suite3 [START_REF] Gansner | An open graph visualization system and its applications to software engineering[END_REF], previously used by the authors of PRISM [START_REF] Gansner | Efficient, proximity-preserving node overlap removal[END_REF] and GTREE [START_REF] Nachmanson | Node overlap removal by growing a tree[END_REF].

Step 2: Overlapping-free embedding computation Synthetic graphs resulting from the first step are initially positioned by the F M 3 layout algorithm [START_REF] Hachul | Drawing large graphs with a potential-field-based multilevel algorithm[END_REF]. Then, we apply the 8 node overlap removal algorithms, thus providing a set of 6,720 overlapping-free graph embeddings. Graphviz test suite graphs are initially positioned by the SF DP layout algorithm [START_REF] Hu | Efficient, high-quality force-directed graph drawing[END_REF] to follow the same baseline embedding as Gansner et al. [START_REF] Gansner | Efficient, proximity-preserving node overlap removal[END_REF]. We then apply the 8 node overlap removal algorithms thus providing 112 overlapping-free graph embeddings.

Step 3: Metrics computation We finally compute the values of the 5 selected metrics on the 6.832 overlapping-free synthetic and real-world graph embeddings. We also measure the computation time of the algorithms.

Quality

Fig. 1 and2 show the aggregated metrics values on the synthetic and realworld datasets. Unsurprisingly, Scaling, PFS and PFS' obtain the best scores at oo_nni as it is proved that they maintain the original orthogonal ordering. Though, all the algorithms tested got good results for this criterion. Scaling highly increases the size of the embedding, which induces a bad score for sp_ch_a. P F S also obtains a bad score for this criterion. VPSC and RWordle-L produce the most compact embeddings, while the other algorithms give intermediary results. Scaling preserves the initial global shape4 (gs_bb_iar score). PFS is the worst algorithm on this criterion. The other algorithms obtained good median scores on synthetic graphs, but the third quartile scores show that FTA and VPSC can produce a certain amount of distorted embeddings. This is confirmed by the tests on real-world graphs, where they obtain worse results.

Scaling obtains the best results for the node movement minimisation criterion, followed by VPSC and RWordle-L. FTA also obtained a good median score on synthetic graphs, but its third quartile value shows that it can generate a certain amount of embeddings with high changes, as also illustrated by the bad score obtained on the real-world graphs. PFS' and PRISM obtained intermediary results. Finally, GTREE had bad results on the synthetic graphs, while it obtained pretty good ones on the real-world graphs.

Scaling preserves relative edge lengths. All the other criteria obtained comparable median score between 0.17 and 0.31. However, the third quartile on the synthetic graphs shows that FTA, VPSC and RWordle-L generate a certain amount of embeddings with high variations. This observation is confirmed by the results on the real-world graphs for FTA and RWordle-L.

Computation Time

Fig. 3 and4 show the aggregated running time values on the synthetic and realworld datasets. Scaling, PFS, PFS' and VPSC require lower running time. FTA and GTREE induce intermediate running time, but the third quartile shows that FTA can induce a certain amount of time consuming embedding computations. Finally, PRISM is time consuming for small graphs, but have intermediate results for larger graphs, while RWordle-L has good results for small graphs but is very time-consuming for larger ones.

Conclusion

As a conclusion, even if Scaling optimises 4 out of 5 criteria and is very fast to compute on the graphs of our datasets, it does not represent a satisfying solution as it increases the size of the embedding too much. PFS is also not satisfying as it got poor results on 3 criteria. FTA obtained intermediate results over all the criteria, which is less good than all its remaining competitors. PFS' and PRISM obtained comparable results but the latter is more time-consuming. Both have intermediate results for shape preservation and node movement minimisation, which might be considered as two essential criteria. GTREE suffers from inducing high node movements on our datasets. Overall, VPSC and RWordle-L obtained the best quality results. While RWordle-L outperforms VPSC on global shape preservation and is comparable on the other criteria, VPSC outperforms RWordle-L in terms of running time. Finally, considering the different types of graphs (random graphs, random trees, small world graphs, and scale-free graphs), we did not observe any significant differences in terms of results.

Fig. 1 .

 1 Fig. 1. Aggregated values of the selected metrics among the synthetic graphs: first quartile, median and third quartile.

Fig. 2 .

 2 Fig. 2. Mean values of the selected metrics among the real-world graphs.

Fig. 3 .

 3 Fig. 3. Aggregated running times among the synthetic graphs, function of number of nodes (10 to 1,000): first quartile, median and third quartile.

Fig. 4 .

 4 Fig. 4. Mean values of running times among the real-world graphs.

https://gitlab.com/graphviz/graphviz/blob/master/rtest/graphs/(accessed: 2019-07)

The global shape preservation score for Scaling is not 1 because of the size of the nodes that remains the same between the initial and the overlapping-free embeddings.

Acknowledgement This research has been partly funded by a national French grant (ANR Daphne 17-CE28-0013-01).


Guillaume Touya
email: guillaume.touya@ign.fr

Cécile Duchêne
email: cecile.duchene@ign.fr

Anne Ruas
email: anne.ruas@ign.fr

Collaborative Generalisation: Formalisation of Generalisation Knowledge to Orchestrate Different Cartographic Generalisation Processes

Keywords: cartographic generalisation, constraints, ontology, interoperability

Cartographic generalisation seeks to summarise geographical information from a geographic database to produce a less detailed and readable map. This paper deals with the problem of making different automatic generalisation processes collaborate to generalise a complete map. A model to orchestrate the generalisation of different areas (cities, countryside, mountains) by different adapted processes is proposed. It is based on the formalisation of cartographic knowledge and specifications into constraints and rules sets while processes are described to formalise their capabilities. The formalised knowledge relies on generalisation domain ontology. For each available generalisation process, the formalised knowledge is then translated into process parameters by an adapted translator component. The translators allow interoperable triggers and allow the choice of the proper process to apply on each part of the space. Applications with real processes illustrate the usability of the proposed model.

Introduction

Cartographic generalisation is a process that seeks to summarise and characterise geographical information from a geographic database in order to produce a less detailed and readable map. Automatic generalisation processes were necessary to ease the production of map series and are growingly required nowadays with the development of on-demand mapping. Many automatic generalisation methods were developed in the past years but none is actually able to tackle all the problems raised by thematic and landscape heterogeneity present in a map [START_REF] Touya | First thoughts for the orchestration of generalisation methods on heterogeneous landscapes[END_REF]. Rather than developing another process that would try to solve all problems of the generalisation of a map, we believe that trying a collaborative approach is a better solution. The aim of this work is to make the available generalisation processes collaborate by generalising only the part of the map they are good at. To simplify, we want to know when, where, how and why to apply a generalisation process. When developing the first generalisation processes, research already tackled these questions concerning the sequencing of atomic algorithms [START_REF] Mcmaster | Cartographic generalization in digital environment: A framework for implementation in a gis[END_REF], but the problems raised are quite different at the process level.

The paper deals with one aspect of the solution of the generalisation process sequencing problem: making different generalisation processes interoperable to be sequenced in neighbouring or identical part of cartographic space may be difficult. For instance, in the agent-based process of [START_REF] Ruas | A Prototype Generalisation System Based on the Multi-Agent System Paradigm[END_REF], cartographic constraints, that express the map specifications, are translated in objects with methods to monitor the process, in the least squares process of [START_REF] Harrie | Simultaneous Graphic Generalization of Vector Data Sets[END_REF], the constraints are translated into equations to monitor the process and the road selection process of [START_REF] Touya | A Road network Selection Process based on Data Enrichment and Structure Detection[END_REF] is monitored by a big set of parameters. In order to deal with this heterogeneity of inputs and make the processes interoperable, we propose to formalise specifications and cartographic knowledge as (1) constraints, (2) rules sets, (3) ontology and (4) process descriptions.

The second section of the paper presents briefly the collaborative generalisation model we propose to optimise the sequencing of generalisation processes. The third section deals with the formalisation of the cartographic knowledge to enable the collaboration between processes. Then, the fourth section explains how the formal knowledge is used to orchestrate the processes. Finally, the last section draws some conclusions and details ongoing work on the proposed collaborative model.

A Collaborative Approach for Generalisation

Definition of Collaborative Generalisation

We define collaborative generalisation as an approach that makes generalisation processes collaborate to generalise the part of the space they are relevant for (Fig. 1).

The data to generalise is partitioned in spaces adapted to the available processes (urban areas, rural areas, mountain areas and road network in Fig. 1).Then, each space is generalised by the most appropriate process, the mapping being guided by knowledge on automated cartography, on the user specifications and on the processes capabilities. The side effects at the generalised parts neighbourhood are monitored along the whole collaborative process. Indeed, if "process 4" of Fig. 1 displaces the road network after the other three processes were triggered, it may cause new overlap conflicts with already generalised buildings and such conflicts have to be corrected.

Fig. 1.

The collaboration principle between generalisation processes. A process 1 is carried out on the town area, etc. Side effects are corrected at the neighbourhood of application spaces.

We choose the notion of Collaboration in analogy with Multiagent Systems where there is collaboration when the agents share a common goal and coordinate to achieve it [START_REF] Weiss | Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence[END_REF]. We consider that the Collaborative Generalisation approach makes the processes collaborate to reach the common goal of a well generalised map.

The Issues Related to Collaborative Generalisation

Several problems are raised by the collaborative generalisation approach. The first question concern the partitioning of the space into portions relevant for a generalisation process that we call geographic spaces: it is necessary to define the relevant spaces for each available process, their relevant boundaries, and to develop algorithms to create automatically the outline of the space. Moreover, such an approach requires to model what happens at the boundaries of the generalised geographic spaces: side effects have to be monitored. It is also necessary to find a method to reach the relevant sequence to apply. Furthermore, manual and automated cartographic generalisation require treatment homogeneity over the map. The use of different processes to generalise a complete map could jeopardise homogeneity so the collaborative generalisation approach has to take care of this issue.

Finally, some problems of collaborative generalisation are due to the use of different processes that were not developed for working together. This issue is close to the problem of designing a generalisation process based on web services [START_REF] Regnauld | Evolving from automating existing map production systems to producing maps on demand automatically[END_REF]. Thus, it is necessary to know how the underlying model can enable the sequencing of processes with different inputs and outputs. [START_REF] Duchêne | Combining Three Multi-agent Based Generalisation Models: AGENT, CartACom and GAEL[END_REF] proposes a method two combine three generalisation processes into one model and highlights the issue interoperability between generalisation processes modelled differently.

Necessary Components for a Collaborative Generalisation Approach

We propose to divide the collaborative generalisation approach in five main components and three main resources (Fig. 2): the partitioning, side effects, scheduling, registry and translator components and the geographic spaces, formalised generalisation knowledge and available processes resources. This subsection describes and illustrates these components and resources. We define a resource as the required elements that can be considered as inputs of the generalisation as they are used by the Collaborative Generalisation process or guide it. We define a component as an element that is acting in the Collaborative Generalisation and that uses resources as inputs and outputs.

The available generalisation processes are the generalisation processes that are accessible from the software platform where the Collaborative Generalisation model is implemented. The processes can either be implemented on the same platform as the model or called as web services, as in [START_REF] Regnauld | Evolving from automating existing map production systems to producing maps on demand automatically[END_REF].

The geographic spaces are the portions of initial data that are relevant for generalisation processes and that help to process large amounts of data [START_REF] Touya | First thoughts for the orchestration of generalisation methods on heterogeneous landscapes[END_REF]. These spaces can be metric (i.e. a limited part of earth) as the urban or coastal areas, thematic as the road network (relevant space e.g. for the elastic beams [START_REF] Bader | Cartographic Displacement in Generalization: Introducing Elastic Beams[END_REF]) or mixed as the mountain roads. The geographic spaces do not necessarily form a partition and often overlap as a rural and a mountain space.

The partitioning component is composed of spatial analysis algorithms capable of delimiting the spaces as in [START_REF] Chaudhry | Creating mountains out of mole hills: Automatic identification of hills and ranges using morphometric analysis[END_REF]. The partitioning component allows creating the relevant geographic spaces at the beginning of the collaborative process. The partitioning component notably requires to know which are the spaces that are useful to computed according to the user specifications and the available processes. Such knowledge is included in the formalised generalisation knowledge resource. The geographic spaces being identified, we define a sequence of collaborative generalisation as a list of pairs (geographic space, generalisation process) interrupted by side effect processes. For instance a collaborative sequence could be: (Urban space 1, Process 1), (Urban space 2, Process 1), (Rural space 1, Process 2), side effects correction in Rural space 1 neighbourhood, (Mountain space 1, Process 3)... The registry component aims at matching the pairs as yellow pages answering the question: what is the process to generalise this space? The registry records the services that the available generalisation processes are able to provide. Then, when a geographic space requests for generalisation, the registry component answers with a list of relevant processes. The registry mechanism is detailed more in section 4.4. The registry component clearly requires a description of the generalisation processes capabilities and needs to have access to user specifications to decide the application relevance of a process, both included in the formalised generalisation knowledge resource. The formal description of the generalisation processes capabilities is detailed in section 3.6.

The scheduling component chains the pairings of spaces and processes in an optimal sequence. It decides at each step which space has to query the registry for generalisation and evaluates the generalisation results. To iteratively choose the next space to be generalised, the scheduling component requires both user specification and general knowledge on the major steps of generalisation. The sequence is not linear but optimised by a trial and error strategy guided by general knowledge and online evaluation.

The side effects component relies on the observation of the neighbourhood of the spaces generalised by the scheduling component. The component monitors the potential side effects by triggering a deformation process as [START_REF] Gaffuri | Three reuse example of a generic deformation model in map generalisation[END_REF] that reduces conflicts without undoing the previous generalisations. The component requires to know user specifications in order to maintain the ones that are altered by side effects.

The translator component parameterises the available processes according to the user specifications whatever the process parameterisation system is. The translator component is detailed in sections 4.1 to 4.3.

Finally, the formalised generalisation knowledge resource gathers user specifications, generalisation processes descriptions and general knowledge on the scheduling steps of generalisation. We developed a Collaborative Generalisation model that relies on the components and resources described in this section, the CollaGen model (for Collaborative Generalisation). This paper focuses on the formalised generalisation knowledge resource modelling in CollaGen, presented in the next section. The interactions between the formalised knowledge and the translator and registry components are described in the fourth section.

Formalisation of Generalisation Knowledge

Organisation of the Formalised Generalisation Knowledge

In order to provide knowledge to the CollaGen model, user specifications and knowledge on cartographic generalisation are formalised in a machine interpretable way. User specifications cover here both the user requirements for the generalised map and the cartographic rules for map legibility. The formalised knowledge required for collaborative generalisation can be divided in five parts: generalisation domain ontology, generalisation constraints set, operation rules set, sequencing rules set and process descriptions. Fig. 3 shows how this formalised knowledge is organised to feed the collaborative process. The formalised knowledge is generated by three actors of the collaborative model that correspond to three times in the model life: the model designer that implements the five components and designs the generalisation ontology and the sequencing rules; the process developer that makes generalisation processes available and describe them, enriching potentially the ontology; the user that aims at generalising his data and then translates his specifications into generalisation constraints and operation rules.

The five following sections describe in detail the formalisation model of each piece of formalised knowledge and explain how the models are instantiated.

A Generalisation Domain Ontology

Automatic cartographic generalisation requires as input data an adapted data schema [START_REF] Ruas | Automating the generalisation of geographical data: the age of maturity?[END_REF]. The adapted data schema is the initial schema of the geographic database used to produce the generalised map, enriched with implicit concepts made explicit in the data to allow the automatic process. The implicit concepts useful for automatic generalisation can be of different kinds: meso concepts [START_REF] Ruas | A Prototype Generalisation System Based on the Multi-Agent System Paradigm[END_REF] like "group of building", "city" or "highway interchange"; procedural concepts that are necessary for the use of a particular process like the "fields" for a GAEL process [START_REF] Gaffuri | Three reuse example of a generic deformation model in map generalisation[END_REF], "dead ends" for a road selection process or "small compacts" for a CartACom process [START_REF] Ruas | A Prototype Generalisation System Based on the Multi-Agent System Paradigm[END_REF]; explicit geographic relations like the proximities between objects or the accessibility of a facility by a road. The generalisation constraints that mostly formalise the user specifications may concern the concepts and data added in the adapted schema. We define a generalisation domain ontology as a domain ontology concerning the automatic generalisation process. The generalisation domain ontology should be made of:

 The concepts that can be present in an adapted data schema (meso, procedural concepts and geographic relations plus topographic concepts).  The known relevant geographic spaces.  The properties that may be constrained by user specifications.  Generalisation operator taxonomy.  A taxonomy of the generalisation processes available on the platform.

The geographic properties of concepts that are likely to be constrained by user specifications are included in the ontology as ontology properties. For instance, "area", "granularity" or "absolute_position" are some of the properties defined on the "building" concept while "sinuosity", "length" and "coalescence" are some "road" properties because constraints are often defined on these properties. Properties are also defined on the geographic relations: the "proximity" relation as a "minimum distance" property. The modelling of properties as results of spatial analysis measurements is advanced. Defining that shape should be measured by a mix of "compactness", "concavity" and "elongation" properties is not possible yet. Describing more in detail the properties as in [START_REF] Lüscher | Where is the terraced house? On the use of ontologies for recognition of urban concepts in cartographic databases[END_REF] would help to make a direct link between the atomic properties and the spatial analysis methods to measure the atomic properties and more abstract ones. Associations related to the adapted schema are also included in the ontology (e.g. the association "a meso_entity is composed of geographic_entities"). Some restrictions are defined on the associations. For example, the meso composition association can be restricted for building groups to only buildings and roads.

Our implementation of the generalisation domain ontology, in OWL 2, is built upon a topographic database concept taxonomy that was originally created in OWL by an automatic natural language process [START_REF] Abadie | Création d'une ontologie à partir des spécifications textuelles pour l'intégration des bases de données géographiques[END_REF], manually enriched by the properties, associations and new concepts necessary to produce the generalisation domain ontology. The concepts possibly present in the adapted schema where classified using the national mapping experience of the laboratory. The generalisation operator taxonomy chosen as the most relevant for this ontology is extracted from [START_REF] Mustière | Apprentissage supervisé pour la généralisation cartographique[END_REF] Then, the well-known meso, procedural and relations were added to the ontology with specific associations like a meso_entity "is composed of" geographic_entities.

The generalisation domain ontology is used as the support of generalisation knowledge sharing and integration, which is one of the applications of ontology [START_REF] Horrocks | Ontologies and the semantic web[END_REF].

Formalisation of Generalisation Constraints

In the first years of cartographic generalisation research, constraints have quickly been considered as the best way to formalise the map specifications [START_REF] Beard | Constraints on rule formation[END_REF]. Indeed, constraints, like "inter-distance between buildings must be at least 0.1 map mm", are a convenient way to express the legibility conditions of a map. Generalisation constraints classifications were also suggested [START_REF] Ruas | A Prototype Generalisation System Based on the Multi-Agent System Paradigm[END_REF][START_REF] Burghardt | Investigations on cartographic constraint formalisation[END_REF]. Several research or production projects have proposed models to capture the user specifications in the form of generalisation constraints using table templates or OCL expressions [START_REF] Burghardt | Investigations on cartographic constraint formalisation[END_REF][START_REF] Stoter | A Data Model for Multi-scale Topographical Data[END_REF] while commercial software like Clarity™ (1Spatial) or Axpand® (Axes Systems) propose ad-hoc constraints expression models. We developed a model to express the different user and map specifications as constraints that rely on the referred models and classifications (Fig. 4). Four types of constraints are defined from the classification of [START_REF] Burghardt | Investigations on cartographic constraint formalisation[END_REF]: micro constraints (constraints on single objects), meso constraints (constraints on group of objects or patterns) and relational constraints (constraints on the geographic relation between two objects) and the macro constraints (constraints on the population of all objects of a kind). Only the last type is not present in the classification of [START_REF] Ruas | A Prototype Generalisation System Based on the Multi-Agent System Paradigm[END_REF]. Our contribution is the rest of the formal model described in Fig. 4. The model is described using the two following constraints examples:  C1: "Buildings' area must be over 0.2 map mm² in urban areas".  C2: "Very concave buildings should maintain initial concavity with 10% margin"

The major properties of a constraint are its name, and the concept ("building" for C1 and C2) and character constrained ("area" for C1 and "concavity" for C2) from the ontology. Then, generalisation constraints are characterised by an expression type, a selection criterion and a space restriction. The expression type is an object that holds both the kind of expression of the constraint and the threshold values. For example, the "threshold" type of expression means that the constraint is like: "concept.character < value". Thus C1 has a "threshold" expression type with ">" as operator, "0.2" as value and "map mm²" as unit. C2 has a "margin" expression type with a "10%" value. Five kind of expression types have been defined. The selection criterion is a query that selects one part of the objects of the constrained concept. For instance, C2 has a selection criterion that queries only very concave buildings (a threshold has to be given to translate "very" in understandable concavity value). The selection criterion can be seen has an implementation of the OGC Filter standard [START_REF]Filter Encoding Implementation Specification[END_REF] for constraints. The space restriction is a set of geographic spaces from the ontology where the constraint is only applied. When the set is empty, the constraint concerns every part of space. Only C1 has a space restriction as the constraint is only valid in urban spaces.

A Graphical User Interface (GUI) form has been developed to help the user capture the constraints and implement the formal model. 70 constraints have been captured, extracted from French NMA experience.

Formalisation of Operation Rules

Although generalisation constraints may express most of user specifications, some part of the specifications cannot be appropriately expressed by generalisation constraints. Indeed, some of the constraints extracted from the EuroSDR test [START_REF] Burghardt | Investigations on cartographic constraint formalisation[END_REF], particularly the ones advising or forbidding actions to apply ("...buildings should be aggregated"), are clearly rules that were forced to fit in the constraints template. So, we consider that it is simpler for a user to express them as Operation Rules. The rules are modelled following equation ( 1):

Conclusion Premise Premise    ... 2 1 (1)
Conclusions are generalisation operations from the ontology that are advised or not (e.g. "Roundabout diameter < 100 m implies Collapse to point"). A premise is a simple condition expressed with a threshold on a concept property, as in "threshold typed" constraints introduced in 3.3. Operation Rules can be seen as a convenient vector for modelling systematic operations as in the above roundabout rule. Operation rules are also a way to guide generalisation processes in their actions: the rule "buildings should not be aggregated in urban spaces" helps to parameterise the generalisation process that will be chosen to generalise urban spaces.

Formalisation of Sequencing Rules

The CollaGen model allows the expression of "sequencing rules" that represent general knowledge in automated cartographic generalisation and provide general guidelines to the scheduling component. The sequencing rules correspond to the Global Master Plan described in [START_REF] Ruas | Strategies for Automated Generalization[END_REF]. The Global Master Plan described how the main steps of generalisation are chained. For instance, the well-known rule "Network selection must be carried out before cartographic generalisation" can be expressed and processed thanks to sequencing rules. As operation rules, the sequencing rules are modelled using premises and a conclusion. Fig. 5 shows the model of sequencing premises and conclusions. Premises refer to a particular place in the sequence of generalisation processes: "after network selection" or "when each part of the space has been processed once at least" are instances of particular places in the sequence. Conclusions can be either a geographic space ("Urban spaces should be processed first in cartographic generalisation") or a process ("Geometry Collapses should be processed first") from the ontology.

The implemented sequencing rules allow to sequence the generalisation process in four main steps: the geometry type changes (e.g. collapse of roundabouts to points), the selection (elimination of useless objects), the cartographic generalisation and the graphic generalisation [START_REF] Harrie | Simultaneous Graphic Generalization of Vector Data Sets[END_REF] (correction of remaining legibility conflicts). Fig. 5. The UML data schema of the Sequencing Rules model. A premise is a situation in the processes sequence and the conclusion is a generalisation process or a geographic space.

Formal Description of Generalisation Processes

As an analogy to web service composition, the composition of generalisation processes requires the description of their capabilities and requirements. The relevance domain of the different generalisation processes has to be formalised to know where they can be applied. For instance, we should be able to say that the CartACom process [START_REF] Ruas | A Prototype Generalisation System Based on the Multi-Agent System Paradigm[END_REF] is relevant on rural spaces or low density spaces and that the Elastic Beams [START_REF] Bader | Cartographic Displacement in Generalization: Introducing Elastic Beams[END_REF] are relevant on flexibility graphs [START_REF] Lemarié | Generalisation process for top100: research in generalisation brought to fruition[END_REF] (conflicting sub-graphs of the road network adapted to the Beams). We should also formalise which constraints can be handled by a process in order to know if it is adapted to particular situation. Regarding web service composition, the description of the service capabilities can be formalised by pre-conditions and post-conditions [START_REF] Lutz | Ontology-Based Descriptions for Semantic Discovery and Composition of Geoprocessing Services[END_REF]. The pre-conditions correspond to the conditions the input data have to meet to be properly processed. The postconditions describe the expected data modifications caused by the process. In the CollaGen model, this model is followed to describe the capabilities of generalisation processes in our collaborative model where pre-conditions are the relevant spaces for application and the post-conditions are the a priori handled constraints and rules (Fig. 6). Pre-conditions refer to spaces described in the ontology and post-conditions refer to constraints and rules present in the sets of constraints and rules defined by the user.

Fig. 6. UML class diagram of the generalisation process description for interoperability between processes. The pre-conditions are the spaces where the process is applicable and the post-conditions are the rules and constraints a priori satisfied after process execution.

To go further in the process description details, some properties are associated to the processes among which the generalisation method the process is an instance of (e.g. "AGENT specialised for urban generalisation" is an instance of "AGENT model"). It enables to link this process to the Sequencing Rules. The name of the programming component that allows to execute the process, is mentioned ("nameJava" attribute of class ProcessDescription in Fig. 6), which is a way of distinguishing function and component [START_REF] Bucher | Acquiring service oriented descriptions of GI processing software from experts[END_REF]. Added to that, the scale range class allows to define for the process the initial and final scales for an appropriate use of the process (e.g. the urban specialised AGENT process is appropriate for 1:10k to 1:50k). The limit scale ranges are also included in the class. Moreover, the required data enrichments to run the process (e.g. "dead-ends", "road partition" or "building alignments") are described in terms of meso or procedural ontology concepts that are expected to be added in the data. If the process is chosen by the registry component to generalise a given geographic space, the first step is then to process the enrichments on the space. Finally, the trust attribute on both PreCondition and PostCondition classes (Fig. 6) is an a priori evaluation of the relevance of each condition, provided by the process provider.

A GUI helps the process provider to fill the description that is automatically translated into the CollaGen description model. Eight generalisation processes available on our research platform are described including AGENT [START_REF] Ruas | A Prototype Generalisation System Based on the Multi-Agent System Paradigm[END_REF], CartACom [START_REF] Ruas | A Prototype Generalisation System Based on the Multi-Agent System Paradigm[END_REF], least squares [START_REF] Harrie | Simultaneous Graphic Generalization of Vector Data Sets[END_REF], GAEL [START_REF] Gaffuri | Three reuse example of a generic deformation model in map generalisation[END_REF], elastic beams [START_REF] Bader | Cartographic Displacement in Generalization: Introducing Elastic Beams[END_REF] and a road geometry collapse [START_REF] Touya | A Road network Selection Process based on Data Enrichment and Structure Detection[END_REF].

Processing Generalisations from Formal Knowledge

This section describes how the formal knowledge is used in the model by the translator and registry component. Section 4.1 deals with the need for matching the data schema to the ontology. Section 4.2 shows how the use of translator functions allows to trigger interoperable generalisations. Section 4.3 explains how, for a given geographic space, the relevant generalisation process is chosen. Some automatically triggered generalisation results illustrate the CollaGen model in section 4.4.

Matching Data Schema to the Ontology

Linking information resources (a geo-database schema here) to an ontology is made through a process called annotation [START_REF] Lemmens | Lost and found, the importance of modelling map content semantically[END_REF]. In the CollaGen translator component, we used the annotation method called registration mapping that is a separate source containing the matching between schema elements and ontology concepts [START_REF] Lemmens | Lost and found, the importance of modelling map content semantically[END_REF]. In the registration mapping, the useful ontology concepts, properties and associations are mapped to the equivalent in the data schema. For instance, the concept "road" is mapped to the class "BD_TOPO_Road_Section". We define the useful concepts as the ones that are actually used in the collaborative process (referred to in the constraints, operation rules and process descriptions).

Making the registration mapping automatically would require natural language processes that are not priority of this research so we opted for an interactive method.

For instance, a test case with one process, "urban AGENT" that requires the enrichment with building groups and three constraints on building minimal area, minimal granularity and inter distance, requires several mappings: first the ontology concepts "building" and "building group" have to be mapped to classes of the data schema; then the properties "area", granularity" on "building" and "building inter distance" on "building group" have to be mapped to the attributes of the data schema.

Translating Knowledge into Process Parameters

Once the objects of the database are matched to the ontology thanks to the registration mapping, the link between the objects and the related can be made and so generalisation can be triggered. The generalisation processes first need to be parameterised according to the expressions and values held by the constraints and the rules captured by the user. As generalisation processes are very complex, they often require a big set of parameters and proper initialisations (e.g. defining constraints for AGENT, equations for the Least squares), giving importance to this translation step. We consider a process parameterised when all required parameters and initialisations have been set up. Thus, registering a generalisation process to the CollaGen model also requires providing a translator component that is able to read the constraints and translate them into the process parameters. A translator function of the component can be considered as a simple programming interface that enables the publishing of the process as a service, which is a key point of geo-processing interoperability [START_REF] Bucher | Acquiring service oriented descriptions of GI processing software from experts[END_REF]. Each generalisation process is provided with its standardised translator function (Equation 2). The body of the translator function consists in searching, for each parameter, for a constraint or rule in the sets that correspond to the parameter and in getting the value held in the constraint as the parameter. parameterised process = f(p, C, R, rm).

(

) 2
Where p is the process to be parameterised, C is the constraints set, R is the operation rules set and rm is the registration mapping. Fig. 7. Generalisation results from two different processes parameterised automatically by the formal knowledge and the translators. On the left, a road geometry collapse process parameterised with the translation of two rules concerning roundabouts and branching crossroads (highlighted with arrows). On the right, a least squares process parameterised with constraints on proximity between roads and buildings and on building size and granularity.

We developed the translator functions for the 8 generalisation processes available on our platform. For instance, the road geometry collapse process has simply real threshold parameters while the CartACom process is parameterised with constraints and the least squares process with equation systems. Fig. 7 shows two generalisation results from these three processes obtained with automatic trigger and parameterisation from the formal knowledge we captured to test our model, and the translator. A third result obtained with CartACom process is presented in Fig. 8.

Choosing the Best Process to Generalise a Geographic Space

As mentioned in section 2, the generalisation process descriptions are stored in a yellow pages registry that can be consulted to find the best process to generalise a geographic space designated by the scheduling component. The CollaGen implementation of the registry responds to a request with a list of relevant processes in relevance order. As in web search engines, the registry response is divided in two steps, the filter step that selects only the relevant services and the ordering step that orders the filter response in terms of relevance. In CollaGen, the filter step questions the pre-conditions of the descriptions (i.e. the geographic spaces a priori accepted as possible input for the process), and keeps the processes whose pre-conditions correspond to the space concerned by the request. For instance, if only the AGENT process and the least squares process have "urban space" in their pre-conditions, an urban space requesting a generalisation will only get these two answers. As a first approximation, the ordering step of the request is made in two times. A first ordering is made according to the "trust" value (integer between 1 and 5) of the pre-condition. Then, pre-conditions with the same trust value are ordered according to the postconditions, that are the constraints and rules a priori satisfied. The more the postconditions match the actual constraints conflicts, the best the process is rated. Fig. 8 illustrates the choice of the best process to generalise a "Rural" geographic space. Three of the eight available processes have a pre-condition about rural spaces: "CartACom" (trust value of 4), "Urban AGENT" (trust value of 2) and "least squares" (trust value of 2). "CartACom" is put on top of the list and tried first. The ordering of the two remaining ones is done comparing the conflicts in the rural space to the postconditions. For instance, the preservation constraint "preserve parallelism between roads and buildings" causes conflicts that should be dealt by the post-conditions. Finally, the "least squares" is advised first for a better preservation of the parallelism constraint. Anyway, as the generalisation with the CartACom process is evaluated as satisfying, the following propositions in the list are not considered.

4.4

Some Results With Several Processes Although the CollaGen model is not fully implemented some results can be presented. Fig. 12 shows several processes parameterised by the translator that are executed on the same situation. The four processes used in this example are fully interoperable within CollaGen and we can see that the third sequence gives the best results. It is hopefully the first one proposed by the registry regarding the rural space the situation is in: the registry proposes CartACom with the rural space in firstly generalised then proposes the Least Squares as the best process for final graphic generalisation [START_REF] Harrie | Simultaneous Graphic Generalization of Vector Data Sets[END_REF].

Conclusions and Further Work

The paper introduced and defined the collaborative generalisation approach. In such an approach the initial data is partitioned in different geographic spaces (cities, countryside, mountains, etc.) that are generalised by the more appropriate of the available automatic processes while side effects between spaces are controlled. We presented an important aspect of the CollaGen model (our implementation of collaborative generalisation): to enable the interoperability of the processes and the homogeneity of the generalisation, cartographic knowledge and user specifications are formalised in constraints and operation rules sets, sequencing rules and process descriptions, all based on generalisation domain ontology. Once the initial data is annotated with the ontology, translator components allow parameterising the processes and the processes can be chosen and triggered on a given geographic space.

To go further, some classical generalisation constraints could be integrated in the ontology to ease the capture of specifications by the user. But before, two topics have to be tackled more deeply to make the CollaGen model operational. First, the management of the side effects has to be clarified: when do we exactly need to trigger the correction and how do we observe the related conflicts? Then, the scheduling component implementation has to be finalised.

Fig. 2 .

 2 Fig. 2. The main Components (rectangles) and Resources (ellipses) of a Collaborative Generalisation Model and how the components act on the resources (plain arrows). The Formalised Generalisation Knowledge is used by all five components. The Side Effects and the Partitioning components act on Spaces while the Registry and the Iterating component act on both Spaces and Processes and the Translator only acts on Processes.

Fig. 3 .

 3 Fig. 3. A diagram of the 5 parts of formalised knowledge and their use in the collaborative model. The dashed arrows show that the Ontology provides shared concepts to every part.

Fig. 4 .

 4 Fig. 4. UML class diagram of the Generalisation Constraints formal model. A constraint concerns a concept and one of its characters from the ontology and has an expression type, a selection criterion and a space restriction.

Fig. 8 .

 8 Fig. 8. A Rural space (built by the partitioning component) generalised by the CartACom process according to the request to the registry of generalisation processes.

Fig. 9 .

 9 Fig. 9. (1) a situation before generalisation. (2) the situation generalised with an AGENT based process then a Least Squares process: some conflicts remain. (3) the situation generalised with a CartACom process then a Beams process: some side effects are created by the beams. (4) the situation generalised with CartACom then Least Squares: it is correctly generalised.