Lom Messan Hillah

Ariele-Paolo Maesano
email: ariele.maesano@lip6.fr

Fabio De Rosa
email: fabio.de-rosa@simple-eng.com

Libero Maesano
email: libero.maesano@simple-eng.com

Marco Lettere

Riccardo Fontanelli
email: riccardo.fontanelli@dedalus.eu

Service functional test automation

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Services are everywhere. They are involved in services architectures built of service components that: (i) expose service APIs, (ii) interact through service protocols (REST/XML, REST/JSON, SOAP…) and (iii) are deployed independently of each other. The SOA approach has been used for fifteen years to let distributed vertical applications cooperate. More recently, systems have exposed service APIs for interaction with mobile apps. Presently, the internal structure of applications, once monolithic, is going to be designed as a micro-services architecture [START_REF] Newman | Building Microservices[END_REF] that is particularly well adapted for cloud deployment. Services are loosely coupled, allowing agility of design, development, integration (continuous integration -CI), delivery (continuous delivery -CD) and deployment. The Calabria Cephalalgic Network (CCN) [START_REF] Conforti | Calabria cephalalgic network": innovative services and systems for the integrated clinical management of headache patients[END_REF] is a multi-owner distributed application that supports the headache integrated care processes, effectively coordinating different care settings (general practitioners, specialists, clinics, labs...) in a patientcentred vision. The application is designed as a services architecture (Figure 1), is operational today and its components' services are physically deployed in different data centres. The service APIs are compliant with the HL7/OMG HSSP international standards (RLUS, IXS, CTS2...) [13]. Dedalus [12], a company specialised in healthcare systems, is in charge of the provision within the CCN of the Patient record, the Patient identity and the Terminology services. CCN service-oriented architecture allows Dedalus to put in place a modular integration process with one separate source code repository and one separate build per service component. Actually, the service integration process is a full testing process, constituted of all the testing activities: functional, security, fault tolerance and performance test. In order to improve agility and time-to-market, these activities shall be organised in an optimized manner. The service integration and delivery process pattern that is becoming popular is the CD pipeline [15], in which the testing activities are placed as stages between the service build formation and its deployment in the production environment. The transition from a stage to the next is permitted only whether the stage tests pass, otherwise the sequence is interrupted and restarts with the check-in of the updated code. An example of service CD pipeline is sketched in Figure 2. The test tasks in each stage and the chosen sequence of the test stages can and should maximise the effectiveness (the fault exposing potential and the troubleshooting efficacy) and the efficiency (the fault detection rate) of the testing tasks. Test effectiveness and efficiency are important even for completely automated stages -to say nothing about manual ones -that can be heavyweight and can slow the entire process.

In the CD pipeline sketched in Figure 2, the successfully constituted build is firstly submitted to acceptance white-box tests. All the subsequent test stages target different aspects of the service external behaviour and are independent of the service implementation technology. The subsequent two stages are about functional test and are detailed in the section 'Automated functional test'. The security tests followthey can be effective and efficient only whether the service build passes the functional tests. The last two stages are about quality of service: the fault tolerance tests challenge the resilience of the service implementation in the face of failures of the underlying computing resources or the unavailability of the services it interacts with. Lastly, the performance tests concern mainly the service invocation and provision latency. The CD pipeline can be more or less automated. A single CD pipeline stage can be fully automated whether: (i) its internal tasks can be fully automated and produces automatically a meaningful report and (ii) the automated tasks can be invoked through APIs by the CD server (for instance Jenkins [14]). This paper reports a solution of automation of service functional test. The section 'Related work' gives the motivation for doing research on the topic and a short review of the state of the art. The section 'Automated functional test' presents the prototype developed within the MIDAS project and provided as-a-service by the MIDAS SaaS [16]. Dedalus has incorporated the functional test automation services in its integration process: this experience is presented in the 'Prototype usage in an operational environment' section. The 'Conclusion' discusses major advantages and drawbacks of the new solution and outlines future work.

Related work

Service test and, in particular, end-to-end test of complex services architectures is difficult, knowledge intensive, hard to manage and expensive in terms of labour effort, hardware/software equipment and time-to-market. Since the inception of the service orientation, service testing automation has been a critical challenge for researches and practitioners [START_REF] Bozkurt | Testing web services: A survey[END_REF] [1] [START_REF] Yoo | Regression testing minimization, selection and prioritisation: a survey[END_REF]. In particular, tasks such as: (i) automated optimised generation of test inputs [START_REF] Bozkurt | Testing web services: A survey[END_REF], (ii) automated generation of test oracles [START_REF] Barr | The oracle problem in software testing: A survey[END_REF], and (iii) optimised management of test suite for different test activities -such as first testing, re-testing, regression testing [START_REF] Yoo | Regression testing minimization, selection and prioritisation: a survey[END_REF],

has not yet found automation solutions that can be applied to real complex services architecture such as those that are implemented in healthcare [START_REF] Conforti | Calabria cephalalgic network": innovative services and systems for the integrated clinical management of headache patients[END_REF]. Model-based testing (MBT) utilises formal models (structural, functional and behavioural) of the services architecture under test to undertake the automation of the testing tasks [START_REF] Hierons | Using formal specifications to support testing[END_REF]. The "first-generation" MBT research is essentially focused on test input generation. More recently, formal methods, especially SAT/SMT-based techniques have been leveraged [START_REF] Jehan | Functional SOA testing based on constraints[END_REF] that allow the exhaustive exploration of the system execution traces, and efficient test input generation satisfying constraints (formal properties expressed in temporal logic). Jehan and colleagues [START_REF] Jehan | Functional SOA testing based on constraints[END_REF] use a constraint solver to compute the expected inputs for each particular execution of the business process as extracted from the control flow graph. The MIDAS approach to the prioritization of test cases [START_REF] Yoo | Regression testing minimization, selection and prioritisation: a survey[END_REF] is entirely original [START_REF] Namin | Bayesian reasoning for software testing[END_REF]: it is based on the usage of probabilistic graphical models [10] [7] in order to dynamically choose the next test case to run on the basis of the preceding verdicts. Moreover, the scheduler is able to establish a dynamic relationship between test case prioritization and the generation of new test cases, by supplying on the fly to the generator evidence-driven directives based on the preceding verdicts.

Automated functional test

Test environments

The service functional test automation is illustrated through an example of a simplified services architecture related to the CCN application (Figure 3). In order to provide its service, eHealth service consumes the Patient record, the Patient identity and the Terminology services. These services that are not consumers of other services are called terminal services.

Unit test stage

The unit test stage includes the following tasks: (i) produce test inputs (stimuli), (ii) produce test oracles (expected outcomes), (iii) deploy and initialise the build in an appropriate environment (service under test -SUT), (iv) configure and generate the test system, (v) bind the test system with the SUT, (vi) run test cases (transmit stimuli, collect and log outcomes), (vii) arbitrate test outcomes against test oracles, (viii) schedule test case runs (dynamic scheduling), (ix) plan test campaigns (reactive planning) and (x) report test campaigns. For every terminal service, the unit test environment architecture is similar to that sketched in Figure 4. For non-terminal services, such as the eHealth service, the typical unit test environment is depicted in Figure 5. The test tasks involved in the stage are the same as those for terminal services, but in the test system are generated, in addition to the stimulator, three mocks that "virtualise" the downstream services. The binding sub-task enables the mocks receipt the requests of the eHealth service, and send back the canned responses. The test system must be able to evaluate against the oracles that the requests that are issued target the appropriate services, are in time, are in the exact sequence and are the right ones.

End-to-end test stage

The services architecture under test (SAUT) distributed environment is deployed with the lastest release builds of the downstream services. In the test system are generated the interceptors that catch the exchanges forth and back between the eHealth service and the downstream services (Figure 6). This test environment is put in place in the end-toend stages of the CD pipelines of all the services involved in the SAUT, including the terminal services. An interesting point is that the end-toend tests can highlight functional failures of any of the SAUT servicesnot only of the service of the pipeline in which the stage is accomplished -and so eventually reveal service tight coupling -when a change in one service produces an unexpected failure in another service. End-to-end testing of multi-owner services architecture requires collaborative testing projects that involve all the service owners and that explore systematically the cooperation scenarios between all the services. Systematic endto-end testing campaigns are mandatory for first testing of new distributed applications, but are also recommended as regular activities of re-testing and regression testing. A collaborative testing project involving all the owners of the CCN application services is in progress.

Test automation methods

The MIDAS functional test prototype brings automation solutions (test automation methods) for the most critical test tasks: (i) configuration of the test system against distributed services architectures, (ii) test case (input/oracle) generation based on constraint propagation and symbolic execution, (iii) intelligent dynamic test case prioritisation and scheduling, (iv) intelligent reactive planning of test campaign with on-the-fly, evidence-based generation of new test cases. These test automation methods are provided as services by the MIDAS SaaS.

Automated configuration of the test system

The structure of the test system (stimulators, mocks, interceptors) is automatically generated from the SAUT model and the test configuration model. The former model is represented through an XML document depicting the actual components of the SAUT and the actual wires between them -interaction links that are typed by service specifications (e.g. WSDL documents). The latter model is obtained from the former model: (i) by adding virtual components (stimulators, mocks) and the corresponding virtual wires to actual components and (ii) by designating the actual wires to be observed (interceptors).

Automated generation of test cases

Each SAUT component is equipped with a protocol state machine (PSM), modelled as a Harel state-chart [START_REF] Harel | Statecharts: a visual formalism for complex systems[END_REF], that represents the interaction states of the component and the transitions triggered by received messages (events), filtered by conditions (guards) and producing effects described as data-flow transfer functions. The service component PSMs are represented through standard SCXML documents [17] and the conditions and transfer functions are expressed in Javascript. Test cases (inputs and oracles) are generated from the set of models (Figure 7). The test cases generation process relies on model-checking the PSM models using TLA+ [18], a well-known formal specification language based on temporal logic. TLA+ is backed by the TLC model checker to exhaustively check correctness properties across all possible executions of the system and by the TLAPS proof system that relies on SMT (Satisfiability-Modulo Theory) solvers for checking TLA+ proofs. The PSMs and the generation parameters are translated into a TLA+ companion algorithm language (PlusCal) that is afterwards compiled into TLA+. Through assertions, execution traces of the system that match some criteria -for instance where messages of some specific types, or containing some specific values, are exchanged -are requested to the proof system. Input data are then extracted from the execution traces and fed to the SCXML engine, which executes the PSMs for the scenarios triggered by the input data and produces the related oracles.

Automated dynamic scheduling of test runs

Automated dynamic scheduling takes places in the MIDAS test system that is equipped with automated execution and arbitration of test cases (Figure 8). In this context, the scheduler is able to choose the next test case to run on the basis of the past test verdicts. The cycle schedule/execute/arbitrate continues until there are no more test cases to run or some halting condition is met. The objectives of dynamic scheduling are (i) precocious detection of failures and (ii) localisation of faulty elements (troubleshooting).

The dynamic scheduler builds a Bayesian Network (BN) model [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF] from (i) the SAUT model, (ii) the test suite and (iii) user's beliefs on the SAUT. The BN is compiled into an Arithmetic Circuit (AC) [START_REF] Maesano | Bayesian dynamic scheduling for service composition testing[END_REF]. At each test run the verdicts are inserted as evidences in the AC and the subsequent inference calculates a fitness probability for each remaining test case that, combined with a scheduling policy (e.g. max-fitness, max-entropy...), allows the scheduler to choose the next test case.

Automated reactive planning of test campaigns

The idea behind a fully automated workflow for functional testing is to use the scheduler to drive not only the choice among a set of existing test cases but also the generation of new test cases. The test campaign starts with a minimal test suite and, on the basis of evidences (verdicts) brought from the past test runs, the scheduler calculates the degree of ignorance (Shannon entropy) on SAUT elements and recommends the generation of test cases whose execution would diminish this ignorance. This feature is operational and its usage in test campaigns is in progress.

Prototype usage in an operational environment

Dedalus currently utilises a home-made framework for service unit testing that has already significantly shrunk the effort of manually producing and executing test cases and test suites. The major limitations of this solution can be labelled as: (i) "test case overhead", (ii) "unit testing only", (iii) "lack of planning and scheduling", (iv) "manageability". The "test case overhead" issue relates to the necessity of creating a huge amount of test cases since the services to be tested (such as RLUS) are specified as generic and the payload structure varies according to the instantiation of the service. In addition, typical content transferred in the healthcare domain is made of very complex data structures with several thousands of atomic data types. The automated generation of test cases brought by the MIDAS prototype reduces dramatically the effort that was formerly dedicated to test case handwriting. Moreover, the home-made testing framework is able to support only service unit testing. End-to-end test of service compositions with MIDAS requires only the drafting of the appropriate SAUT, test configuration and PSM models. With the aforementioned huge amount of test cases, the optimisation of the test campaigns is a must. The home-made test framework doesn't have any support for test cases prioritization and test case generation optimization. MIDAS intelligent scheduler and reactive planning facility propose solutions to the optimisation problem that are technically operational and whose evaluation is in progress. Last but not least, with the home-made framework every change in the deployed SAUT (IP addresses, ports, URIs, parametrizations) requires a significant effort of reconfiguration by hands of every individual test case, practically preventing any continuous integration approach. With the MIDAS prototype, the SAUT models, the test configuration models, the PSMs and the generated test suites are independent of the SAUT physical locations that are indicated as configuration parameters to be instantiated at test run time.

Conclusion

The collection of functional test automation methods of the MIDAS prototype covers all the service functional test tasks, including the most "intelligent" and knowledge-based ones. Furthermore, the test automation methods are provided as services, allowing the MIDAS SaaS user both to invoke them individually and to easily combine them in service integration and delivery processes directed by CI/CD servers. These methods are actually integrated as services by a MIDAS partner (Dedalus) in its specific integration and delivery process of healthcare distributed applications and services architectures. Experiences for assessing and mastering advanced features such as dynamic scheduling for re-testing and regression testing and evidence-based test case generation are in progress. Current drawbacks of the MIDAS prototype are manageability and usability issues and are the matters of future work: (i) taking into account REST/JSON service testing; (ii) automated check of the alignment of the SAUT deployment with the SAUT model; (iii) simplifying the specification of the test configuration; (iv) better handling of passive oracles (generated from incomplete specifications).


Bastien Cazaux
email: cazaux@lirmm.fr

Eric Rivals
email: rivals@lirmm.fr

A linear time algorithm for Shortest Cyclic Cover of Strings

Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring of a set of input words. The Shortest Cyclic Cover of Strings (SCCS) problem asks, instead of a single linear superstring, for a set of cyclic strings that contain the words as substrings and whose sum of lengths is minimal. SCCS is used as a crucial step in polynomial time approximation algorithms for the notably hard Shortest Superstring problem, but it is solved in cubic time. The cyclic strings are then cut and merged to build a linear superstring. SCCS can also be solved by a greedy algorithm. Here, we propose a linear time algorithm for solving SCCS based on a Eulerian graph that captures all greedy solutions in linear space. Because the graph is Eulerian, this algorithm can also find a greedy solution of SCCS with the least number of cyclic strings. This has implications for solving certain instances of the Shortest linear or cyclic Superstring problems.

Introduction

The possibility of merging two words into a longer one according to their overlap -for instance merging abcde with cdeba into abcdeba -allows to infer the sequence of a target molecule from the short reads produced by sequencing machines. In computer science, merging results in a superstring of the input words. The action of merging is heavily used in any genome assembler (although not necessarily on the complete reads, sometimes only on substrings of the reads) and given the redundancy of the sequencing, which yields a high density of reads, the objective is to compute a shortest superstring of a set of input words [START_REF] Gusfield | Algorithms on Strings, Trees and Sequences[END_REF]. In bioinformatics, the task of genome assembly is worsened by the inaccuracy of the sequencing and by the structure of the genome which contains repeated sequences [START_REF] Gusfield | Algorithms on Strings, Trees and Sequences[END_REF]. However, progresses on the model question, called Shortest (linear) Superstring Problem (SLiS), still shed light on the difficulty of assembly. Moreover, the target molecule can be a linear or a circular structure. It is also interesting to address the question of the Shortest Cyclic Superstring (SCyS). Finding superstrings also has application in data compression. Indeed, as a superstring represents a condensed representation of the initial language, it can serve as a compressed version of the input set.

Let P := {s 1 , . . . , s |P | } be a set of input words and denote the sum of their lengths by ||P ||, i.e. the norm of P . Without loss of generality, we always assume that P is factor free, i.e. for any two strings of P , none is a substring of the other. From the computational viewpoint, finding a shortest superstring is known to be hard to solve (NP-hard even on a binary alphabet) and to approximate (Max-SNP hard) [START_REF] Gallant | On finding minimal length superstrings[END_REF][START_REF] Blum | Linear approximation of shortest superstrings[END_REF]. The research in the last 25 years has mainly focused on polynomial time approximation algorithms for SLiS (see [START_REF] Golovnev | Approximating Shortest Superstring Problem Using de Bruijn Graphs[END_REF] for a recent list). Despite these efforts, the algorithm greedy (Algorithm 1), an algorithm that iteratively updates the input set by merging two maximally overlapping strings until one string is left, was conjectured to approximate the shortest superstring with ratio 2 [START_REF] Tarhio | A greedy approximation algorithm for constructing shortest common superstrings[END_REF][START_REF] Blum | Linear approximation of shortest superstrings[END_REF]. This is better than most known algorithms, and the conjecture is still valid. The question of approximating the superstring can be reformulated on a complete weighted digraph, the so-called distance graph: each input word is a vertex and an arc encodes the directional merging of the two words. The weight of an arc from u to v equals the length of the prefix of u that is not covered by the overlap of v (e.g., the corresponding prefix of abcde to cdeba is ab, and the weight would be 2). Then a shortest linear superstring is associated with a Hamiltonian path on this graph, and a shortest cyclic superstring with a Hamiltonian cycle [START_REF] Blum | Linear approximation of shortest superstrings[END_REF]. Yet those problems are also hard to approximate and most approximation algorithms for SLiS resort to a relaxed question, namely Shortest Cyclic Cover of Strings (SCCS). These algorithms solve SCCS by computing a minimum assignment on the distance graph in O(||P ||+|P |

3 ) [START_REF] Papadimitriou | Combinatorial optimization : algorithms and complexity[END_REF], and then transform the cycles into cyclic strings. Our work focuses on SCCS. We propose an algorithm that uses only linear time in ||P ||, and for this sake introduce the superstring graph, which captures all solutions of greedy for SCCS (see Sections 4 and 3). These greedy solutions are called greedy superstrings. Exploring the graph properties, we show that it gives, for a subset of instances of the shortest linear and cyclic superstring problems, interesting approximations or even exact solutions (Section 4).

Notation and problem definition

For any rooted tree T , V T is the set of nodes of T . For a node v of V T , Children T (v) is the set of children of v in T . We denote by [i, j] the set of integers between i and j.

We consider two kinds of strings: linear and cyclic strings (see Figures 1a and1b). For a string s, the length of s is |s|. For a linear string s and i ≤ j in [1, |s|], s[i, j] is the linear substring of s beginning at the position i and ending at the position j, s[i] is the substring s[i, i], s [1, j] is a prefix of s and s[i, |s|] is a suffix of s. A prefix (or suffix) s of s is proper if s is different of s. For another linear string t, the overlap from s to t, denoted by ov(s, t), is the longest substring which is a proper suffix of s and a proper prefix of t. The prefix from s to t, denoted by pr(s, t), is such that s = pr(s, t)ov(s, t). The merge of s with t is the linear word pr(s, t)t if s = t, and the cyclic word pr(s, t) otherwise. A linear superstring of a set P of linear strings is a linear string w such that each string of P is a substring of w. We say that a linear string w is a substring of a cyclic string c if there exists w c a linear permutation of c such that w is a substring of w ∞ c (where w ∞ c = w c w c . . .) -see Figure 1c. A cyclic cover of P is a set C of cyclic strings such that each linear string of P is a substring of a cyclic string of C.

We define the following problem:

Problem 1 (Shortest Cyclic Cover of Strings)

Input: A set of linear strings P .

Output: A cyclic cover C of P that minimises ||C||.

Let σ be a permutation of {1, . . . , |P |}, we can split up σ in cyclic permutations: σ = σ 1 • . . . • σ m . For each cyclic permutation σ i of length n i , we denote the cyclic string by: 2: Running example with the input set P := {ababb, aab, abba, abaa}. Instance of a cyclic cover of P obtained with a permutation σ. We obtain the cyclic cover P (σ) = {ababba, aba} (ababba and aba are cyclic words). and, P (σ) = {P (σ 1 ), . . . , P (σ m )} (See Figure 2).

P (σ i ) = pr(s σi(1) , s σi(2) ) . . . pr(s σi(ni-1) , s σi(ni) ) pr(s σi(ni) , s σi(1)
It is easy to see, that for each permutation σ of {1, . . . , |P |}, P (σ) is a cyclic cover of P and for each optimal solution w of Problem 1 (SCCS), there exists σ a permutation of {1, . . . , |P |} such that w = P (σ).

Related works

Let us briefly recall some crucial works in the study of shortest superstrings and of Shortest Cyclic Cover of Strings.

Since SLiS does not admit a PTAS, numerous works on SLiS have reported polynomial time approximation algorithms with a constant ratio ranging from 4 to > 2 (see [START_REF] Golovnev | Approximating Shortest Superstring Problem Using de Bruijn Graphs[END_REF]Table 1]). A majority of these model SLiS as a minimum weight Hamiltonian path problem on the distance graph G of P (where an arc (s i , s j ) is weighted by |pr(s i , s j )| for any valid i, j). Note that if instead it is weighted by |ov(s i , s j )|, we obtain the Overlap Graph, and SLiS becomes equivalent to finding a maximum weight Hamiltonian path [START_REF] Blum | Linear approximation of shortest superstrings[END_REF]. Clearly, the weight of a cyclic cover of G (i.e., the sum of the weight of all cycles) is lower than that of a Hamiltonian cycle, which itself gives a lower bound of the weight of a Hamiltonian path on G. Hence, most algorithms rely on solving SCCS, which is polynomial. Blum et al. [START_REF] Blum | Linear approximation of shortest superstrings[END_REF] were the first to exhibit such an algorithm and to prove that it achieves a constant ratio of 3 for SLiS. This algorithm first solves SCCS and in a second step combines the cyclic strings by running a greedy algorithm on them. Teng and Yao improved this ratio by an algorithm that recursively solves SCCS [START_REF] Teng | Approximating shortest superstrings[END_REF]. After that, many authors have investigated the combinatorial properties of words and of some specific cycles, which enabled them to further improve the approximation (e.g. [START_REF] Breslauer | Rotations of periodic strings and short superstrings[END_REF][START_REF] Mucha | Lyndon words and short superstrings[END_REF][START_REF] Paluch | Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring[END_REF]), but all need to solve SCCS. To do so, they compute a Minimum Assignment on the distance graph. An assignment (or cyclic cover) of a digraph G is a set of cycles such that every vertex of G belongs to exactly one cycle. To solve SCCS on an instance P , approximation algorithms for SLiS first ) time and space using the Generalised Suffix Tree (GST) of P [START_REF] Gusfield | An efficient algorithm for the all pairs suffix-prefix problem[END_REF], then 2/ compute a minimum cyclic cover using the Hungarian algorithm in O(|P |

3 ) time [START_REF] Papadimitriou | Combinatorial optimization : algorithms and complexity[END_REF]. Once the cyclic cover is known, the algorithm in [START_REF] Teng | Approximating shortest superstrings[END_REF] also requires to compute a particular assignment called a canonical assignment, which takes an additional O(||P ||) using the suffix tree based algorithm of [START_REF] Gusfield | Faster implementation of a shortest superstring approximation[END_REF]. However, the complexity bottleneck of algorithms using a cyclic cover remains the O(||P || + |P |

3 ) time to build the graph and compute the cover. It was also shown that greedy (Algorithm 1) solves SCCS exactly [START_REF] Cazaux | Approximation of greedy algorithms for max-atsp, maximal compression, maximal cycle cover, and shortest cyclic cover of strings[END_REF]. To the best of our knowledge, there is currently no linear time algorithm for solving SCCS.

Theorem 1 ([6]

) For Shortest Cyclic Cover of Strings, Algorithm greedy yields an optimal solution.

Explanations about Algorithm greedy

An overlap is said to be greedy-feasible if a greedy solution takes it. Let u 1 , u 2 , v 1 and v 2 be four strings. We say that the overlaps ov(u 1 , u 2 ) and ov(v 1 , v 2 ) are dependent if and only if u 1 = v 1 or u 2 = v 2 . When Algorithm greedy merges u with v, it chooses the overlap between u and v and forbids any overlap beginning by u and ending by v, i.e. it forbids all overlaps that are dependent of ov(u, v). We say that a set of overlaps is independent if each overlap is not dependent of another.

Thus, Algorithm greedy makes a series of choices to select a sequence of greedy-feasible and independent overlaps:

• In the first step of the Algorithm greedy chooses an overlap among the longest overlaps.

• In the second step, it chooses an overlap among the longest overlaps which are independent of the first overlap.

• At each further step, it takes a maximum overlap that is independent of the previously selected overlaps.

• In the end, it outputs a set of overlaps that are maximal (for the inclusion as a base in a matroid). This set of overlaps is independent.

As the set of overlaps at the end of greedy is maximal, there exists a permutation σ of {1, . . . , |P |}, such that for all i in {1, . . . , |P |}, ov(s i , s σ(i) ) is an overlap of our set of overlaps. Thus, we obtain the following property which is similar at a well-known property on the solution of the greedy algorithm for SLiS [START_REF] Vassilevska | Explicit inapproximability bounds for the shortest superstring problem[END_REF]Def. of Induced(π, S) and Def. The suffix tree of a word w is a data structure that indexes all substrings of w. Each arc is labelled with a substring of w such the concatenation of the labels along a branch from the root to a leaf spells out a suffix of w. A constraint requires that the labels of arcs from a node to its offspring start with different symbols. Thus, each node represents a prefix of a suffix, i.e. a substring of w. In fact, each internal node is the longest common prefix of all leaves in its subtree. Traversing an arc extends the represented string on its right. The word depth of a node is the length of the string it represents. An example of (generalised) suffix tree is shown on Figure 3: the sole suffix tree structure is displayed on Figure 3a. For instance, the node 2 represents the string aa. Going from node 3 to node 1 extends the string represented by a b to yield the string aab.

ST are equipped with additional arcs called Suffix Links (SL): a SL links a node representing au (with a a letter and u a string) to the node representing u. Let us label the SL by the letter a. The notion of SL is usually restricted to internal nodes, but it extends naturally to leaves. We consider that each node has its SL. Traversing a SL removes the first letter of the word: it shortens the represented word at the front. To each SL, we associate a label, which is the letter it removes. For instance, in Figure 3, traversing the SL of node 1 shortens the word aab to ab, which is the string represented by node 2 . The label of that SL is a (labels of SL are not represented in this figure). It is known that, if SLs are reversed (considered in the other direction), they form a tree rooted in the root of the ST, and all leaves are on the same branch of this tree [START_REF] Cazaux | Reverse engineering of compact suffix trees and links: A novel algorithm[END_REF]. Note that the chain of SL starting from any node goes up to the root of T (For simplicity, assume the root has a SL to itself). In the tree composed by the suffix links is displayed on Figure 3b. Moreover, in the figures, the SL are drawn as an arc from a child to its parent in L (See Figure 3).

For simplicity, we say that a suffix tree arc is blue, while SL are red. So, we have the blue tree, denoted T , and the red tree, denoted L, on the same nodes.

The GST generalises this principle to several words. From now on, the generalised suffix tree of P is the pair (T, L). An extensive introduction to GST and their applications can be found in [START_REF] Gusfield | Algorithms on Strings, Trees and Sequences[END_REF]. The distinction between explicit and implicit nodes is skipped here, but explained in [START_REF] Gusfield | Algorithms on Strings, Trees and Sequences[END_REF][START_REF] Breslauer | On suffix extensions in suffix trees[END_REF].

Overlaps

Basically, all suffixes and all substrings of words of P are represented in the GST. If a word u overlaps a word v, then a suffix of u equals to a prefix of v. Hence, one expects the overlap to be represented somewhere in the GST. Indeed, if an internal node representing the suffix of u appears on the branch spelling v, then u overlaps v. This internal node exists since this substring occurs at least twice (in u and in v), and represents the overlap. Let us call such node an overlap node from u to v. In our representation, the internal node is labelled with the starting position of that suffix in u on the branch leading the leaf of v. For example, in Figure 3 the node 2 is located on the branch of 1 . It is also on the branches of 1 and 1 . It represents the string ab. So we know that aab overlaps abba, abaa and ababb, with the overlap ab.

Clearly, all overlap nodes from u to v are ancestors of another. Moreover, the word depth of an overlap node gives the length of the corresponding overlap. Hence, the maximum overlap between two words is the deepest overlap node of those words. For instance, both nodes 4 and 3 are ancestors of 1 meaning that abaa overlaps aab with two possible overlaps: a and aa, of length 1 and 2 respectively.

All these notions are known. Indeed, it is known that one can compute efficiently all overlaps for each pair of words in P using the GST of P . In fact, one usually computes pairwise the maximum overlaps for P [START_REF] Gusfield | An efficient algorithm for the all pairs suffix-prefix problem[END_REF], to build the prefix or the overlap graph of P (as mentioned in introduction).

27th June 2014 5 LIRMM (a) the tree T , which is the basic structure of the suffix tree -in blue arcs, and (b) L, the tree made by the suffix links of T -in red arcs. Square nodes represent words that occur as a suffix of some input word, circle nodes are the other nodes of T . Each square node stores its positions of occurrences in S; for simplicity, we display the starting position as a number and the word of S in which it occurs as its colour, instead of showing the list of pairs (i, j). The square node labelled by a red 2, which represents the string ab, means that this string occurs as the suffix starting at position 2 in the red word aab. A square node labelled with a 1 represents an input word.

Merge and Red-Blue Paths

Above the overlap node was defined only using T ; the SL (hence L) were not involved. Let us now give an alternative definition using T and L.

If u overlaps v, then a suffix of u equals a prefix of v. We have seen that the overlaps is a node on the branch spelling v. We can also find this precise suffix of u starting at the node representing u by following enough suffix links. This means going up in the red tree from the node u. Hence, one sees that an overlap node from u to v is an ancestor of u in L (the red tree), and an ancestor of v in T (the blue tree). We obtain an alternative definition: an overlap node from u to v is a red ancestor of u and a blue ancestor of v. For simplicity, let us say it is a red-blue ancestor of the ordered pair (u, v). Now, we see that the maximum overlap of (u, v) is the lowest red-blue ancestor of (u, v). Also, if the red path reaches the root, then the overlap is the empty word (and their merge is simply their concatenation).

In other words, any overlap for a pair (u, v) corresponds to a Red-Blue path from u to v in (T, L).

The merge of u and v using their maximum overlap ov(u, v) is the word w := pr(u, v)ov(u, v)su(u, v), where u := pr(u, v)ov(u, v) and v := ov(u, v)su(u, v). We state this definition with the maximum overlap, but it is valid with any overlap; the larger the overlap, the shorter the merge. We denote by Pathuv the Red-Blue path which corresponds to the maximum overlap between u and v.

Assume we want to spell out the (linear) merge of u and v using the overlap node w in (T, L). It can be done in three steps:

1. traverse T from the root to u: this spells out u with the labels of blue arcs; 2. go up L from u to w following the red arcs: it is possible since w is a red ancestor of u (here we skip one by one all letters of pr(u, v))

3. go down T from w to v using blue arcs, which is possible since v is a descendant of w; this spells out su(u, v).

A merge of (u, v) is a linear superstring of {u, v}. The process above can be generalised to spell out any cyclic superstring of a cyclic permutation of words (w 1 , w 2 , . . . , w n ) using some given pairwise overlaps: one starts from the node representing w 1 , then performs steps 2 and 3 using the appropriate Red-Blue path from w 1 to w 2 to merge them, then iterates only steps 2 and 3 for each following word until one reaches w 1 again. This circuit on the GST is called a Red-Blue circuit.

Example 1 For instance in Figure 3, the Red-Blue circuit corresponding to the cyclic merge of the words ababb, abba, and then aab in this order, contains three Red-Blue paths: for the pairs (ababb, abba), (abba, aab) and then for (aab, ababb). This circuit starts at node 1 goes up with SL to node 2 and then 3 which is a red-blue ancestor of (ababb, abba), then goes down with blue arcs to 1 . This is the Red-Blue path for (ababb, abba), which spells out ab with the SL labels. Then the circuit goes up with SL to 2 , 3 , and 4 , which is an ancestor of 1 . This spells out abb with SL labels. Then, it goes down to 1 . This makes up the Red-Blue path for (abba, aab). Then, the circuit goes up to 2 , which is an ancestor of 1 ; this spells out a with one red label. Then, it goes down and back to 1 , which was the starting node. Altogether the sequence of red labels spells out ababba, while the sequence of blue labels yields aababb: both write the same cyclic word.

Now, let us state a more subtle property. For a Red-Blue circuit, writing all blue labels in order or writing all red labels in order spell out the same superstring (a red label is a label of a SL). Hence, the number of blue arcs is smaller than the number of red arcs, which is the superstring length. A proof of a slightly different version of this property can be found in [5, Section 4.3 on p. 18].

The Superstring Graph

Here, we are going to show that the choices made by Algorithm greedy for SCCS are not really choices. In fact, we will show that each greedy solution can be represented by a unique graph embedded in the Generalised Suffix Tree. As this graph turns out to be computable in linear time, one can derive a greedy solution for SCCS in linear time.

27th June 2014 7 LIRMM

u 1 v 1 v 2 u 2 l k k (a) on the strings u 1 v 1 v 2 k k u 2 k (b) in the Overlap Graph u 1 v 1 v 2 u 2 l k -k (c) in the Superstring Graph G P ()

Equivalence of greedy solutions

Let w be a greedy solution of SCCS. By Proposition 2, there exists a permutation σ such that w = P (σ). For each cyclic permutation σ i of σ, we denote by c(σ i ) the Red-Blue circuit obtained from σ i in the GST.

We denote by G P (σ) = (V, R, B) the directed multigraph built with the arcs of the Red-Blue paths of all the c(σ i ), where R denotes the set of Red arcs, and B denotes the set of Blue arcs of all the c(σ i ).

A graph is said to be Eulerian, if there exists a Eulerian path on this graph, i.e. a path that visits each arc of the graph exactly once. As G P (σ) is a collection of Red-Blue circuits, which are made of Red-Blue paths, each connected component of G P (σ) is Eulerian. (With each additional circuit, the graph remains Eulerian.)

For each permutation of {1, . . . , |P |}, we can build the corresponding multigraph G P (). We have the following proposition.

Proposition 3 Let w 1 and w 2 be two greedy solutions of SCCS and let σ 1 and σ 2 be their respective permutations of {1, . . . , |P |}. Then G P (σ 1 ) = G P (σ 2 ).

Proof 1 (Idea of the proof ) Let w = P (σ) be a greedy solution of SCCS. Let us show that the choices made by Algorithm greedy for SCCS do not influence G P (σ). Clearly, independent overlaps do not influence the graph. So, let us focus on dependent overlaps, because they are the shear choices made by greedy.

Let ov(u 1 , v 1 ,) and ov(u 1 , v 2 ,) be two dependent and greedy-feasible overlaps. Assume that ov(u 1 , v 1 ,) is the overlap choosen by greedy to obtain w, thus there exists u 2 in P such that ov(u 2 , v 2 ,) is the overlap choosen by greedy to obtain w. By the definition of greedy, we have that |ov(u

1 , v 1 , ) | ≥ |ov(u 2 , v 2 , ) |. Let us show that there exits a Red-Blue path from u 2 to v 1 in G P (σ). As |ov(u 1 , v 1 , ) | ≥ |ov(u 2 , v 2 , ) |, we have that ov(u 2 , v 2 ,) is a prefix of ov(u 1 , v 2 ,)
, and thus a prefix of ov(u 1 , v 1 ,). Hence in the GST, the node ov(u 2 , v 2 ,) is an ancestor of ov(u 1 , v 1 ,), and ov(u 1 , v 1 ,) is a node in the Red-Blue paths from u 1 to v 1 and from u 2 to v 2 . Thus, we have both Red-Blue paths from u 1 to v 2 and from u 2 to v 1 are in G P (σ) (see Figure 4). By Proposition 3, the graph G P () represents all the solutions of the greedy algorithm for SCCS. We called this graph, the Superstring Graph of P , and denote it by G P . An example of Superstring Graph for P := {abb, bbb, bbc} is shown in Figure 6.

27th June 2014 8 LIRMM

To sum up, we know that for each greedy solution w, there exists a permutation of {1, . . . , |P |} that can be translated into a set of Red-Blue circuits, c(w) = {c 1 (w), . . . , c m (w)}. Remember that each Red-Blue circuit is made by chaining Red-Blue paths. Let c be a multi-cycle of G. We say that c covers G P if each arc of G P is included in a single cycle of c. By Proposition 3, for each greedy solution w we have that c(w) covers G P .

By the following proposition, we have that each multi-cycle that covers G comes from a greedy solution.

Proposition 4 {multi-cycle p | p covers G P } = {c(w) | w is a greedy solution}.

To prove Proposition 4, we first need a lemma. A crossing in G P is a node that has red in-and out-going arcs and blue in-and out-going arcs.

Lemma 5 (Absence of crossing) G P does not contain any crossing.

Proof 2 (Lemma 5) It is enough to see that the only nodes that can have a red out-going arc and a blue in-going arc correspond to the words of P . But if v ∈ P , v is a leaf in T and in L by Definition of the GST, and thus v has neither a blue arc going out, nor a red arc going in.

Proof 3 (of Proposition 4) To understand this equality, it is sufficient to note that there is a relation between choosing the longest overlap in greedy and the absence of crossing in G P .

Proof of ⊆. Let us show {multi-cycle p | p covers G P } ⊆ {c(w) | w is a greedy solution} by contraposition. Assume that there exists a multi-cycle p covering G P and there does not exist a greedy solution w of P such that p = c(w). Then, there exist four nodes v 1 , v 2 , v 3 and v 4 in P such that |ov(v 1 , v 2 )| < |ov(v 3 , v 4 )|, and such that both P ath(v 1 , v 4 ) and P ath(v 2 , v 3 ) are in p. Hence, the node ov(v 3 , v 4 ) is a crossing in G P . As there does not exist any crossing in G P (Lemma 5), we obtain a contradiction, and get {multi-cycle p | p covers G P } ⊆ {c(w) | w is a greedy solution}.

Proof of ⊇.

Reciprocally, assume that there exists a greedy solution w of P and there does not exist a multi-cycle p that covers G P such that p = c(w). Thus, there exists an arc of c(w) which is not an arc of G P . Among those arcs, let e = (u, v) be the one with the deepest node ( i.e. longest word) v in T . By the definition of G P , e belongs to R ( i.e. is a red arc), because it is the deepest of its kind. Let v 1 and v 2 be the nodes of P such that e belongs to P ath(v 1 , v 2 ). As e is not in G P , for each u in P such that P ath(v 1 , u) is in G P , u = v 2 . Thus, there exists v 4 in P such that

P ath(v 1 , v 4 ) is in G P and |ov(v 1 , v 2 )| < |ov(v 1 , v 4 )|.
As w is a greedy solution of P , there exists v 3 in P and not in

G P such that P ath(v 3 , v 4 ) is in c(w) and |ov(v 1 , v 4 )| ≤ |ov(v 3 , v 4 )|.
Thus, there exists an arc in c(w) that is not in G P with a deeper extremity than e. This contradicts our hypothesis and we get {c(w) | w is a greedy solution} ⊆ {multi-cycle p | p covers G P }.

Characterisation of the Superstring Graph and a construction algorithm

Now, we are going to characterise the Superstring Graph and give a linear time algorithm to build it from a set of words. For this algorithm, we define and compute weights (respectively n() and d()) for the red and for the blue arcs of the GST. Finally, the SG will be composed of those arcs having a strictly positive weight (and of the nodes visited by them).

As greedy selects overlaps in order of decreasing length, one can see it as a recursive algorithm that progresses along the branches of the GST of P . On the GST, greedy progresses from the leaves toward the root, i.e. in order of decreasing word depth of the nodes. Let us use this recursive side of greedy to explain the Superstring Graph.

Let v a node of the GST, when greedy sees the overlaps of length |v|, it has already considered overlaps of larger lengths. We define two weights n() and d() such that: 27th June 2014 9 LIRMM

• n(v) is the number of strings of P which have v as suffix and are not merged on their right with another string of P with a larger overlap.

• d(v) is the number of strings of P which have v as prefix and are not been merged on their left with another string of P with a larger overlap.

In other words, n(v) is the number of leafs of the subtree of v in L that are not yet merged on their right, and d(v) is the number of leafs of the subtree of v in T that have not yet been merged on their left. First, it can be seen easily seen that a node v which has no other leaf both in its subtrees in L and in T , is a string of P . Thus, for these nodes we set,

n(v) = d(v) := 1.
For the other nodes, we use the recursion of greedy. In fact, we can determine how many strings of P have not yet been merged with another string by looking the weights n() and d() of the children of v in L and of its children in T (see Figure 5).

Let a(v) be the difference between the sum of the n(u ) of the children u of v in L and the sum of the d(u) of the children u of v in T :

a(v) := u ∈ Children L (v) n(u ) - u ∈ Children T (v) d(u).
Hence, the absolute value of a(v) is the largest number of strings of P that we can merge with another strings of P with the overlap v by greedy. With a(v), we can calculate n(v) and d(v): With this recursive definition of the weights n() and d(), we can construct the Superstring Graph from the GST of P . Whenever the weight of an arc of the GST is equal to 0, this arc does not belong to the Superstring Graph. Similarly, if for a node, say v, all of its in-going and out-going arcs have a zero weight, v is isolated and is not included in the Superstring Graph -this corresponds to the subset U in Definition 1 (which states another definition of the Superstring Graph). Algorithm 2, on its third line (in blue), computes a cyclic cover of G P . This requires to perform a random choice when facing two alternative out-going arcs. Clearly, the combination of all possible successive choices allows to produce all possible cyclic covers of G P . Certain choices will generate a solution containing several cycles to cover one connected component (see Figure 6b), although it is always possible to cover one connected component with a single cycle (see Figure 6c). Thus, any two cyclic covers may differ in their number of cycles, i.e. in their cardinality. This gives rise naturally to a new question, to a new variant of SCCS, which we define below. Algorithm 3: The Superstring Graph algorithm for SCCS Figure 7: An instance with an optimal solution that is not a solution of greedy for SCCS (however, the solution of the SG is also optimal). Let P = {abec, bed, cf abe, dgab}. (Top) the generalised suffix tree, (middle) the SG, and (bottom) an optimal solution of SCCS that consists in single cycle, while the SG has two components. it is a greedy solution it solves Problem 2. We obtain Theorem 7. The minimisation of the number of cyclic strings by Algorithm 3 is illustrated in Figure 6.

If a(v) ≥ 0, we have n(v) := a d(v) := 0, if a(v) < 0, we have n(v) := 0 d(v) := -a. t w v 1 v 2 u 1 u 2 n(v) n ( u 1 ) n ( u 2 ) d (v ) d ( v 1 ) d ( v2 ) v
Theorem 7 Algorithm 3 solves Problem 2 in linear time.

Proof 5 As the connected components of the Superstring Graph are Eulerian, this is done in linear time and space in the size of G P . By Proposition 4, a label of a Eulerian multi-cycle of G P is an optimal solution for the Problem 2.

Remark: Although for SCCS, all solutions of greedy are optimal, some optimal solutions are not output by greedy. Thus, the question of finding a shortest cyclic cover with a minimum number of elements is not solved by the Algorithm 3 (see a counter example in Figure 7).

Consequences of the topology of the Superstring Graph

The characterisation of the SG can also be applied to solve or approximate the "classical" shortest superstring problem (SLiS -for Shortest Linear Superstring), in which the solution is a linear superstring, as well as its variant where the solution is a single cyclic word (SCyS -for Shortest Cyclic Superstring). Let w OP T (SLiS) , respectively w OP T (SCyS) , denote an optimal solution for SLiS, resp. for SCyS. Let w a greedy solution for SCCS, we have: |w| ≤ w OP T (SCyS) ≤ w OP T (SLiS) . If the SG is connected, then w is a cyclic superstring of P , i.e. a solution of SCyS. By the above relation, it is an optimal solution for SCyS. Now, from this cyclic superstring, we can easily derive a linear superstring of P . Basically, we cut the cyclic string at the start of a suffix of a word of P and pre-catenate the corresponding prefix. Let v a node of the SG such that n(v) = d(v) = 0, then v is a prefix of some word of P . Then vw makes up a linear superstring of P . We obtain |w| ≤ w OP T (SLiS) ≤ |v| + |w|. As |v| ≤ w OP T (SLiS) , we get |v| + |w| ≤ 2 w OP T (SLiS) . In other words, for instances P that have a connected SG, we obtain a 2-approximation for the shortest linear superstring. Furthermore, if the Eulerian cycle visits the root of the suffix tree, then v is the empty word and then |w| ≤ w OP T (SLiS) ≤ |w|, meaning that w is an optimal linear superstring.

Note that there exist non trivial instances, with an arbitrary large norm, whose SG is connected: any instance in which all words are cyclic shifts of another belong to this class. As the SG can be built and explored in linear time in ||P ||, one can use this procedure as a predicate to check whether SCyS or SLiS are solvable in linear time. If not, one can launch a more complex approximation algorithm [START_REF] Paluch | Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring[END_REF].

Conclusion

We consider the problem Shortest Cyclic Cover of Strings, which is solved by Algorithm greedy. The set of solutions of greedy can be exponential. Nevertheless, with the SG, we exhibit a characterisation of this set in a graph that is Eulerian and linear in the input size. This enables us to solve SCCS in linear time, but also to find a greedy solution with the least number of cyclic strings. Moreover, this approach can solve or approximate some non trivial instances of the shortest superstring problems. Our approach can be adapted to a variant of SCCS where the multiplicity of each input word is given as input.

Currently, approximation algorithms for shortest superstring problems use a procedure for solving SCCS that takes cubic time (i.e. O(||P || + |P |

3 ) time) and quadratic space in the number of strings. This step represents their time complexity bottleneck since other steps can be done in O(||P ||) time. Using our algorithm makes the overall time complexity linear in the input size.

Figure 1 :

 1 Figure 1: (c) shows how the linear word (a) is included in the cyclic word (b).

Proposition 2

 2 Let w a greedy solution of SCCS, there exists a permutation σ of {1, . . . , |P |} such that w = P (σ). 27th June 2014 4 LIRMM 2 Generalised Suffix Tree, overlap, merge, and Red-Blue Paths

Figure 3 :

 3 Figure3: (c) The GST of P := {ababb, aab, abba, abaa}. The GST of P is in fact composed of two trees: (a) the tree T , which is the basic structure of the suffix tree -in blue arcs, and (b) L, the tree made by the suffix links of T -in red arcs. Square nodes represent words that occur as a suffix of some input word, circle nodes are the other nodes of T . Each square node stores its positions of occurrences in S; for simplicity, we display the starting position as a number and the word of S in which it occurs as its colour, instead of showing the list of pairs (i, j). The square node labelled by a red 2, which represents the string ab, means that this string occurs as the suffix starting at position 2 in the red word aab. A square node labelled with a 1 represents an input word.

Figure 4 :

 4 Figure 4: Example with three overlaps: two dependent ones, between u 1 and v 1 and between u 1 and v 2 , and another overlap between u 2 and v 2 : shown on the strings (a), in the overlap graph (b), and in the Superstring Graph (c).

Figure 5 :

 5 Figure 5: General scheme of the in-and out-going arcs of a node v in GST. The red arcs belong to R and the blue arcs to B. If a weight is zero, the arc is not included in the Superstring Graph.

Definition 1 Theorem 6

 16 The Superstring Graph G P = (V, R, B) whereV = V T \ U27th June 2014 10 LIRMM A linear time algorithm for Shortest Cyclic Cover of Strings B. Cazaux & E. RivalsR = {(u, w) n(u) | u ∈ V T , w the parent of u in L} B = {(t, v) d(v) | v ∈ V T , t the parent of v in T } and U = {v ∈ V T | vis not an extremity of an arc of R ∪ B} where n() and d() are the weights on arcs as defined above. Algorithm 2 solves SCCS in linear time and space.Proof 4 Correctness. By Proposition 4, the set w of cyclic words computed by Algorithm 2 is a solution of greedy for SCCS. Hence, each word of P appears as a substring of a cyclic word in w, and by Theorem 1, the norm of w is minimal.Complexity. The Superstring Graph of P is embedded in the generalised suffix tree of P , and thus built in a time linear in ||P ||. By Proposition 2, the length of a solution of greedy is bounded by ||P ||; thus, the length of a multi-cycle of G P is bounded by 2 × ||P ||. Consequently, one can find a multi-cycle also in O(||P ||) time and space. Finally, traversing all its cycles takes a time proportional in the size of the Superstring Graph.Algorithm 2: The Superstring Graph algorithm for SCCS 1 Input: P a set of linear words. Output: w a greedy solution for SCCS; 2 build G P the Superstring Graph of P ; 3 compute a cyclic cover c = (c 1 , . . . , c n ) of G P ; 4 for j ∈ [1, n] do 5 traverse c j : list the words of P whose node is in c j and insert the cyclic string of the concatenation of the prefix in w;6 return w Note that with Algorithm 2, one obtains a cyclic cover.4 Implications of the Superstring Graph4.1 SCCS with a cardinality constraint on greedy solutionsWe can split up G P into connected components: G P = {C 1 , . . . , C g }. By Proposition 4, each multi-cycle c of G P can be partitioned in a subset of cycles c = S 1 ∪ . . . ∪ S g , where each set of cycles S i covers a connected component C i of G P .

Problem 2 (Figure 6 :

 26 Figure6: A Superstring Graph and SCCS solutions. (a) the generalised suffix tree and the Superstring Graph (SG) for P := {abb, bbb, bbc}. Square nodes of T represent strings that are suffixes of some word of P : the integer in the square node is a starting position of its suffix. A word of P is identified by its colour. Figure(b) and (c) show the two multi-cycles which cover SG and the respective sets of cyclic strings. This example is well known for showing the lower bound of the approximation ratio of the greedy algorithm for SLiS. The SG for this instance is connected and thus finds the optimal solution.

  algorithm for Shortest Cyclic Cover of Strings B. Cazaux & E. Rivals

  : list the words of P whose node is in c j and insert the cyclic string of the concatenation of the prefix in w;Output : A set of cyclic strings c, with the least number of elements, that is a solution of the greedy algorithm on Shortest Cyclic Cover of Strings.Algorithm 3 differs from Algorithm 2 only on the third line: instead of computing any cyclic cover of G P , it computes a Eulerian multi-cycle of G P . This is possible since each connected component of the Superstring Graph is Eulerian and it can be done in linear time in the norm of P . A Eulerian multi-cycle of G P covers each connected component with a single cycle, hence it minimises the cardinality of the cyclic cover, and as

	A linear time algorithm for Shortest Cyclic Cover of Strings	B. Cazaux & E. Rivals
	6 return w
	27th June 2014	12	LIRMM

1 Input: P a set of linear words. Output: w a greedy solution for SCCS; 2 build G P the Superstring Graph of P ;

3 compute a Eulerian multi-cycle c = (c 1 , . . . , c n ) of G P ; 4 for j ∈ [1, n] do 5 traverse c j

27th June 2014

Acknowledgements: This work is supported by ANR Colib'read (ANR-12-BS02-0008) and Défi MASTODONS SePhHaDe from CNRS.


Romaric Breil

Cooperative air traffic structuring

in collaboration with

Multi-Agent System

• Resilient, fast and scalable method for problem solving • Composed of agents (aircraft) cooperating to elaborate their trajectories • Decisions taken by each aircraft, based on knowledge of its local environment

Cooperative Air Traffic Structuring

Conflict Avoidance by Speed Regulation

• Aircraft send messages containing their estimated trajectories • Each aircraft selects optimal speed changes based on this shared knowledge • Speeds are selected within [-6%, +3%] of its optimal speed

Macro-Structuring of Air Traffic

• The system reduces traffic complexity by structuring trajectories into flows • The traffic complexity is monitored in real time • The route network is dynamically adapted to fit the traffic complexity Romaric Breil, PhD student : romaric.breil@capgemini.com Laurent Lapasset, R&D Manager : laurent.lapasset@capgemini.com


Marina Sergeeva

Daniel Delahaye

Catherine Mancel

Leila Zerrouki

Nick Schede

3d

3D Sectors Design by Genetic Algorithm Towards Automated Sectorisation

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Abstract-The aim of this work is to develop a research prototype to support the validation of new airspace sector design methodology. To do this, an algorithm has been developed that manages main features of the sector design process. The proposed method is based on a mathematical modeling and heuristic optimization techniques. In order to run this algorithm efficiently a pre-processing step has been proposed, which creates an initial division of the airspace into Voronoi cells using k-means clustering algorithm. Then, due to the induced combinatorial complexity, a stochastic optimization algorithm based on artificial evolution has been applied to solve the sectorisation problem. An evaluation of the algorithm is presented as well, with a comparison to existing sectorisation with the support of the operational expertise.

Index Terms-genetic algorithm; k-means clustering; sector design

I. INTRODUCTION

This paper presents an ongoing research work performed in the scope of the SESAR program to assess the concept of the sector design, supported by automated tools. The objective is to optimize the sector design of the European airspace with the support of automation in order to increase an adaptability of sector configurations.

In comparison with a currently used fixed route network, the SESAR program introduces the User Preferred Routing (UPR) concept, to enable the airspace users to freely plan the 4D trajectory that best fits their business needs. On contrary to a fixed-route network, a free route environment will produce a larger number of different trajectories for which a new and more adaptable sectorisation should be proposed. The dynamic nature of the automatic sector design process will support most efficiently the implementation of the UPR concept.

First, we start with a brief description of the current Air Traffic Management (ATM) system in Europe. The airspace is partitioned into sectors, each of them being controlled by a group of Air Traffic Controllers. Air traffic controllers monitor the traffic and check that aircraft follow their planned trajectories. An elementary sector is defined as a volume of the airspace, within which the air traffic controller can perform his controlling function. The number of sectors in the airspace is usually determined by the capacity of one controller to manage several aircraft simultaneously. Area Control Centers (ACC) consists of several elementary sectors. When one elementary sector is regularly close to saturation, or significant and permanent change of traffic patterns occurs, a new sectorisation of the ACC should be proposed.

Currently airspace is redesigned by qualified operational airspace experts, who first, identify a problem in the existing sectors and then propose a new sector design, which they build manually, or with the support of visualization and what-if tools for the assessment of the sectors design. However, due to the complexity of the task, it requires a significant amount of time for the experts to find an acceptable and satisfying solution. The aim of the present work is to propose a mathematical modeling and heuristic optimization methods as part of a global methodology for the sector design of the European airspace, developed in the scope of SESAR project P07.05.04, co-financed by the EU and EUROCONTROL ( [START_REF] Project | Dynamic airspace configuration[END_REF]). The aim of this project is to develop a research prototype (decisionsupport tool) to support new sectorization methodologies based on 4D trajectories to deal with the implementation of the Free Routing concept in the short-term future. Resulting algorithms are integrated within EUROCONTROL research prototype to support SESAR validation exercises.

This paper is organized as follows: in section 2, a short literature review will be presented; in section 3, a mathematical model of the problem of the airspace sector design is proposed. In this section, we also describe in detail the creation of initial blocks that are used for the design of elementary sectors. In section 4, a GA approach for the sectorisation problem is described. Finally, in section 5, results and operational analysis will be presented.

II. PREVIOUS RELATED WORKS

A number of different methods are proposed in literature which solve airspace sectorisation problem [START_REF] Flener | Automatic airspace sectorisation: A survey[END_REF], [START_REF] Allignol | Review: Constraint programming for air traffic management: A survey[END_REF]. The choice of the appropriate algorithm derives from the way the sector design process is defined. Existing approaches can be divided on approaches that are aiming to change existing sectors borders and on approaches that start from "scratch". Most of the existing works are concentrated on a 2D sector design, while only few studies include the third dimension [START_REF] Delahaye | 3d airspace design by evolutionary computation[END_REF], [START_REF] Jagare | Airspace sectorisation using constraint programming[END_REF]. Different optimization methods have been used in research of the sector design problem. The most common methods are Constraint Programming [START_REF] Flener | Propagators and violation functions for geometric and workload constraints arising in airspace sectorisation[END_REF], [START_REF] Trandac | Optimized sectorization of airspace with constraints[END_REF], Mixed Integer Programming [START_REF] Tien | Optimizing airspace sectors for varying demand patterns using multi-controller staffing[END_REF]- [START_REF] Chatterji | Air traffic sector configuration change frequency[END_REF], Clustering Algorithms [START_REF] Brinton | Airspace partitioning using flight clustering and computational geometry[END_REF], Evolutionary Algorithms (EAs) [START_REF] Delahaye | 3d airspace design by evolutionary computation[END_REF], [START_REF] Degtyarev | Solution of sectorization problems for an air traffic management area. ii. development of sectorization algorithms[END_REF]- [START_REF] Delahaye | Airspace sectoring by evolutionary computation[END_REF], Computational Geometry [START_REF] Basu | Geometric algorithms for optimal airspace design and air traffic controller workload balancing[END_REF], Global optimization and several other techniques [START_REF] Paul | An efficient and effective partitioning algorithm for air traffic management[END_REF], [START_REF] Klein | An efficient method for airspace analysis and partitioning based on equalized traffic mass[END_REF]. Works can also vary in the way how the ATC workload is quantified during the sectors evaluation process. Several complexity metrics have been proposed in works [START_REF] Masalonis | Dynamic density and complexity metrics for realtime traffic flow management[END_REF], [START_REF] Kopardekar | Airspace complexity measurement: An air traffic control simulation analysis[END_REF] to evaluate the workload of the airspace sectors.

Here, is a short overview of the most promising methods found in recent literature. Research works [START_REF] Delahaye | 3d airspace design by evolutionary computation[END_REF] and [START_REF] Xue | Airspace sector redesign based on voronoi diagrams[END_REF] use Genetic algorithm (GA) for sectors design. In work [START_REF] Delahaye | 3d airspace design by evolutionary computation[END_REF], on a first step, airspace is divided into elementary cells using 2D Voronoi diagram, where each center of cell is a conflict point between two aircraft trajectories. At the beginning of the second step, centers of sectors are chosen randomly. Then, sectors are composed from Voronoi cells during an association process. Resulting sectors are supposed to be balanced, regarding the workload, due to the optimization process. A fitness function used in this work includes the total workload imbalance and the total flow cut (the transfer traffic between neighboring sectors). Almost the same approach is proposed in [START_REF] Xue | Airspace sector redesign based on voronoi diagrams[END_REF]. In this work, a methodology based on the Voronoi Diagram and Genetic Algorithm (GA) is investigated. The Voronoi Diagram is applied to divide the airspace into a group of convex polygons with no overlap. Genetic Algorithm is used to perform the multi-objective optimization. In this work, the following objectives were included: minimizing monitoring workload variance, minimizing coordinating workload, and maximizing dwelling time in a sector.

In recent research, a big attention has been paid to methods based on Constraint Programming [START_REF] Allignol | Review: Constraint programming for air traffic management: A survey[END_REF], [START_REF] Jagare | Airspace sectorisation using constraint programming[END_REF]- [START_REF] Trandac | Optimized sectorization of airspace with constraints[END_REF]. Authors of [START_REF] Flener | Propagators and violation functions for geometric and workload constraints arising in airspace sectorisation[END_REF] have studied constraints that arise in airspace sectorization. In this work, authors give for each constraint an analysis of what algorithms and properties are required under systematic search and stochastic local search. Under stochastic local search, efficient algorithms are proposed for maintaining constraint and variable violations, as well as efficient algorithms for probing the effect of local search moves. The main limitation on using the Constraint Programming is that it works satisfactorily only with small instants of the problem [START_REF] Trandac | Optimized sectorization of airspace with constraints[END_REF]. It is not easy to adapt it to a 3D extension of sectors design as well [START_REF] Jagare | Airspace sectorisation using constraint programming[END_REF].

Most of the previous approaches do not take into account the third dimension as well as some important airspace design aspects, such as shape of the sector. As a matter of fact, one must be able to generate sectors that have to be balanced in terms of the workload and operationally acceptable by the airspace experts in terms of shape.

III. PROBLEM MODELING

First, a sector design problem should be explicitly defind. The problem description presented here is developed according to EUROCONTROL requirements and based on operational expertise of sector design [START_REF] Project | Dynamic airspace configuration[END_REF].

A. Problem description

Given a forecast air traffic demand, the airspace sectorization problem consists in searching a partition of a given airspace domain D into a set of N operationally workable sectors [s1, ... ,sn], so as to minimize some cost function. A sector design is a process which delineates shape of the sectors in order to optimize performance objectives and fulfill operational constraints. Moreover, sectors have to satisfy some geometrical and operational constraints in order to be accepted by ATC experts.

The quality of the airspace sectorization can be evaluated according to several kinds of criteria. In this work, the cost function includes the following criteria:

• The imbalance between the workload of the resulting sectors.

• The coordination workload.

• The number of flight re-entry events.

• The number of conflict points close to the sector borders.

• The number of short transits flight through sectors. In our model, sector shapes have also to satisfy the following constraints:

• An airspace sector must be a continuous portion of the airspace and should not be composed of disconnected blocks. • A sector shape should follow main traffic flows and preferably be a convex polygon. • A sector should span over several flight levels, but should not have too much different lateral shapes at each altitude layer.

• Shapes of sectors such as "stairs" or "balconies" should be restricted or avoided. Next step consists in modeling the problem using a mathematical abstraction which should be as faithful as possible. The main challenge, which researchers of sectorisation domain have to face, is the development of a relevant mathematical model of the airspace.

B. Airspace modeling

Let's consider a given airspace, represented as a 3D polygon. The airspace area is split into several altitude layers, each layer includes at least 5 Flight Levels (FL). The shape of this polygon can vary depending on the altitude level. A set of aircraft trajectories that are crossing this area is known as well. Aircraft trajectories are computed using flight plans. For the purpose of the airspace sectorisation, traffic data are usually taken just for several peak hours of the day(s), when the workload is the highest.

Our model is based on a discretization of the 3D airspace into hexagonal or square cells, with a size less than 5nm (in vertical direction < 5 FL). The aim of the discretization of the airspace using grid-cells is to simplify the problem and to reduce the computational cost. We need to determine the distribution of the traffic complexity i.e., the distribution of the ATC workload in 3D space using a known traffic data. Instead of working with a list of all trajectories, for each grid cell the aggregated workload is computed. For the same reason of simplification, each trajectory instead of being represented as a list of samples is represented as a list of cells with a time line.

The metric of the ATC workload that is used in this work is based on two metrics: flights crossing time and a conflict count. The crossing time cumulated for all aircraft inside the airspace volume is multiplied by the time required by the controller to monitor one aircraft per minute flown in the area (e.g. 3 seconds Having the workload associated with each grid cell, it is possible now to aggregate cells into elementary sectors. However, computational cost required for the cells aggregation process will be high and shapes of resulting sectors may not be satisfying (non-convex). Instead, we propose to reduce the number of cells by aggregating them into bigger cells, using Voronoi diagram [START_REF] Klein | Voronoi diagrams and delaunay triangulations[END_REF], which have a shape of convex polygons.

C. Preparing airspace blocks for sector building process

The traffic is not equally distributed in the airspace, therefore, areas, where the traffic load is low, should be divided on cells with a bigger size. On the other hand, in areas with high traffic, cells should be smaller, in order to be more flexibly combined during the sector design process. To reach this goal, we propose to create a mosaic of cells using k-means clustering algorithm and Voronoi Diagram. The size of a cell, created by the algorithm, will depend on the level of the traffic complexity associated with such a cell.

Having the set of grid cells with their associated workload, the objective of the k-means clustering algorithm, is to group those cells into bigger cells (Voronoi cells), with the size that varies depending on the workload in this area. To reach this goal, grid cells are first projected on the 2D plane corresponding to the ground (see Fig. 1). The workload of each projected cell is then computed as a sum of all cells that have the same ground index, i.e. same horizontal coordinates. In the clustering process we use only loaded cells (with workload > 0). We compute centers of a Voronoi cells using the k-means clustering algorithm, as geometrical barycenters of loaded grid cells (see Fig. 2). Based on the positions of computed geometrical barycenters, each grid cell is aggregated to its nearest center, designing a Voronoi diagram represented in Fig. 2. As a matter of fact, this clustering process indirectly ensures that the main flows and the crossing point between trajectories will be located in the middle of the new cells. The Voronoi diagram is built in 2D and then extended in the third dimension as shown in Fig. 3, leading to a set of airspace building blocks that covers all the given airspace. Building blocks do not change their shape depending on the layer, however the workload of blocks, is different on each altitude layer.

D. State space modeling

The state space represents a set of parameters of the system upon which we may act in order to optimize one (or more) objective(s). Examination of the properties of the state space helps us to choose a suitable optimization method.

First, we characterize data that will be used as an input of the sector design algorithm. During the optimization process we should be able to evaluate the workload of each sector built from a set of blocks. We should also be able to check if blocks belonging to the same sector are connected. In order to do that, we build a 3D graph (see Fig. 4), in which each node represents the center of the building block and each link represents the relation is neighbor with between two blocks. Nodes and links of the graph are loaded with weights. Nodes are loaded with cumulated complexity of the associated grid cells and links with an air traffic flow i.e. the number of aircraft passing from one block to another one. Each link also carries the number of conflicts that are close to the border between two neighboring blocks. Weights of nodes and links are computed separately for each altitude layer. The constructed 3D graph is only used during the evaluation of the results, and not in a process of Once the 3D graph is built, the traffic data should be modeled in order to be able to evaluate re-entries and short transits criteria during the sector design process. To compute the number of re-entries events, we need to check if any trajectory enters twice the same sector. In the same manner we compute the short transits: for each trajectory we register the time that the aircraft has spent in the sector. In order to compute this in an optimized way, we propose to summarize each aircraft trajectory by the list of blocks, crossed by this aircraft with registered entering and exit time (see Fig. 5). Based on this list of blocks, it is easy to check if an aircraft enters twice the same sector and if it stays too shortly in it. Now, we briefly describe how elementary sectors are built during the optimization process. First, we consider positions of the N centers of blocks in the airspace as shown in Fig. 6. Those positions are included in the state space. Sectors are constructed from blocks using sector centers, which are computed during the optimization process. One sector can occupy different number of layers and can be built from different number of blocks at each layer. The sectorization process starts from associating each block to its nearest sector center at each layer (see Fig. 6).

Block centers and sector centers enable the two dimensional The intervals set covers all range of altitude layers(see Fig. 7).

E. Connectivity Constraint

To ensure that sectors are composed of connected blocks, we run a test to check if sectors are connected or disconnected using the modeled 3D graph just after sectors delineation. We have developed a graph coloring algorithm which is applied on our 3D graph in order to highlight disconnections between parts of resulting sectors. After the aggregation process, each node is associated with one of the sectors, so that for each sector it is possible to know the exact number of nodes included in it. Then for each sector, we first take one of its nodes in one layer and associate it with a color accordingly. Then, using known neighborhood of this node we propagate its color to each neighbor node, if it belongs to the same sector (color is propagated in other layers as well). This step is repeated for each new colored node. At the same time we compute the number of nodes that receive the same color. This number is then compared with the actual number of nodes inside the sector, and if those two numbers are different we indicate a disconnection.

F. Objective function

The objective function as well as the constraints included in our model are designed according to EUROCONTROL requirements and developed jointly with the operational experts. Six criteria have been included in our objective function for evaluation of a solution. The first criterion measures the level of the workload imbalance among sectors. The workload imbalance of the sector can be modeled by the following formula :

δ(k) = |w(k) -W K | W K (1)
where W = K k=1 w(k) is the capacity, K is the number of sectors and w(k) is the workload of the sector k.

The capacity is equal to an average value of the workload and is computed as a total workload of the airspace divided by the desired number of sectors. Then, the total workload imbalance of all sectors is given by:

y 1 = ∆ = K k=1 (δ(k)) 2 K (2)
The second criterion measures the coordination workload between neighboring components. When two neighboring blocks belong to different sectors on a considered layer, the traffic flow between them is cut by the sector border, as a result, the coordination workload is increasing. The total flow cut between cells is computed as follows :

F T = z=N Z z=0 l=|L| l=0 f z l (3)
where N z is the total number of altitude layers, |L| is the total number of 2D links in the graph and f z l is the flow crossing the link l in the altitude layer z.

Then, the total flow cut is given by:

F c = l, z|O(l z ) ∈ s k D(l z ) / ∈ s k f z l ( 4
)
where O(l z ) represents the origin and D(l z ) represents the destination of the link l in the altitude layer z and s k represents the sector k. Finally, the four following criteria are computed: the number of re-entries events (y 3 ), the number of short transits inside each sector (y 4 ), the number of conflicts located too close to the borders of sectors (y 5 ) and the the number of balconies in each sector (y 6 ). It is relatively easy to compute efficiently the number of re-entries y 3 and the number of aircraft with short transit time inside one sector y 4 using trajectories that are represented by its associated list of blocks with entering and exit times. The same concerns the computation of the number of conflicts close to the sectors borders y 5 . It is computed almost the same way as we have computed the flow cut, but using the second value of links weight.

All those criteria are normalized in order to have values ∈ {0, 1} and aggregated into one objective function :

y = α 1 .y 1 + α 2 .y 2 + α 3 .y 3 + α 4 .y 4 + α 5 .y 5 + α 6 .y 6 (5)

IV. APPLICATION OF EAS TO THE SECTOR DESIGN

PROBLEM

Based on the airspace model described above, the sectorization problem is simplified to a task of finding centers of the sectors. The complexity of this problem is linked to the number of blocks N b , the number of elementary sectors N s and also to the number of altitude layers N l . The number of combinations for grouping such N b blocks multiplied by N l into N s blocks is given by the second Stirling number [START_REF] Graham | Concrete Mathematics. Addis-onWesley[END_REF].

In our work, we consider that the number of initial blocks is more then 100 and the number of layers is bigger then 2, so the number of possible combinations can become extremely high. This makes impossible the application of the mathematical programming, instead it is more realistic to choose algorithms based on ordered and targeted random search. Typically, this type of problems falls under the category of NP-hard problems and stochastic optimization is a good candidate to address it. Moreover, this problem can have several different optimal solutions, due to the different possible symmetries in the topological space. Thus, one must be able to find most of them, as they have to be evaluated and refined by experts. EAs maintain and improve a population of numerous state variables according to their fitness and are able to find several solutions. On the other hand, EAs would be a best choice if we would like to extended a developed model to multi-objective. EAs appear to be faster then other methods, such as, for example, a simulated annealing, applied to our problem. Thus, EAs is relevant to solve the sector design problem.

A. Coding the chromosome

EAs [START_REF] Davis | Handbook of Genetic Algorithms[END_REF], [START_REF] Michalewicz | Genetic algorithms + Data Structures = Evolution Programs[END_REF] use techniques inspired by evolutionary biology such as inheritance, mutation, natural selection, and recombination (or crossover) to find an approximate solution of the optimization problem. An individual (a solution of the problem), is represented by a list of parameters, called chromosome. The chromosome used in our algorithm is defined as a set of sector centers and has the following structure : The initial population of solutions is generated randomly. First, coordinates of sectors are generated randomly and then, altitude layer intervals are generated for each sector center. In order to generate covering of the full altitude layer range we use a set of randomly generated N s -1 markers (represented by min and max altitude layer), sorted in ascending order as shown in Fig. 8. A marker i is specified by its minimum altitude layer M min i and its maximum altitude layer M max i . In Fig. 8, a construction process of altitude intervals is described. In this figure, five sectors are generated. For designing the associated altitude intervals, four markers are used and ranked by maximum altitude layer (M max i ). The first altitude interval I 1 starts from the lowest layer 1 and ends at M max

x 1 x 2 ... x i ... x

B. Sector building process

After generating initial chromosome, we build sectors using coordinates of centers of blocks. Each block (node) is aggregated to its nearest sector center in the considered altitude level. We can aggregate the node only to the center that locates on the same level with it.

After creating the first population, each solution is evaluated, and a value of fitness is returned by a fitness function. This initial population undergo a selection process that identifies the best solutions, which then constitute an intermediate population. Then, three following recombination operators are applied to individuals of the intermediate population : nothing, crossover, or mutation. The associated probability of application are respectively (1 -p c -p m )), p c and p m . These processes ultimately result in the next population of chromosomes P OP (k + 1) that is different from the initial generation. This generational process is repeated until a termination condition is reached.

Several different crossover operators have been developed, which can be divided on strong and weak operators. Crossover results into two new child chromosomes, which are added to the next population. Chromosomes of two parents are mixed between each other during crossover. However, mutation operators have shown to be more efficient in a solution search process. The purpose of the mutation in EAs is to allow the algorithm to avoid local minimum by preventing the population of chromosomes from becoming too similar to each other, thus slowing or even stopping evolution. First strong mutation operators are applied in order to obtain a wide range of results, which after some generations will narrow to the stack of near optimum solutions. Then, weak mutation operators are applied in order to obtain final results.

V. SIMULATIONS AND RESULTS

After the modeling and algorithm descriptions above, this section presents results of the sectors design algorithm applied to Maastricht UAC (Amsterdam UTA and Northern part of Hannover UIR).

A. Scenarios description

Two scenarios have been used to test the algorithm. In each scenario we are using different values of the main parameters. Results are obtained using free route simulated trajectories, which provide a sample of full free route trajectories for the 11th of July 2014 crossing Maastricht/Amsterdam Airspace (EDYYDUTA).

The reference scenario, to which the algorithm will be compared to, is the sector configuration proposed by ICO tool (Improved Configuration Optimizer). This tool computes the optimum sequence of sector configurations for a given traffic day on the basis of existing elementary sectors. For the considered time period, 19:00-20:00, the sectors proposed by ICO is the configuration 5.5.1, composed of 5 sectors. The ICO tool is implemented within NEST simulator, the Network Strategic Tool developed by EUROCONTROL.

Two solutions scenario were obtained using the algorithm, run with the parameters presented in table I. This table shows that the algorithm shall design for both scenario 5 sectors based on the weights of 6 criteria that have been presented in the objective function description section and displayed in the table from line 2 to 7. The last line indicates that the algorithm uses 4 layers to design the sectors vertically.

B. Results Analysis

Sectors design algorithm has been implemented in C++ within the ASTAAC tool [START_REF]Nest[END_REF]. The results obtained for the first scenario are presented in table II and Fig. 9,10.

The results allow assessing the quality of the designed sectors based on the criteria of workload balancing, avoiding entryconflicts, number of the re-entries and short-crossing flights in order to design the most acceptable sectorisation from the operational viewpoints and also the optimum sectorisation with regards to sectors overload.

The comparison using similar criteria with the reference scenario (see in table II and Fig. 11,[START_REF] Degtyarev | Solution of sectorization problems for an air traffic management area. ii. development of sectorization algorithms[END_REF] shows that the solution ing results regarding entry-conflicts, re-entries, short-crossing flights criteria, while sectors workload balancing is considerably deteriorated. This means that the algorithm is very sensitive to the parameters values and can be adapted to provide different sectors shape with different sectorisation performance, depending on the requirements and operational preferences.

VI. CONCLUSION AND NEXT STEPS

The modeling approach and algorithm solution presented in this paper have been tested and compared to existing sectorisation. The provided results demonstrate that the proposed sector design algorithm is able to provide very satisfying sectorisation with regards to sector load balancing, as well as to the number of entry-conflicts, the number of re-entering and short-crossing flights criteria. Even though operational expertise is still needed to validate the workability and acceptability of the designed sectors, the algorithm is able to offer a multitude of automated design options using different parameters values that the users can calibrate according to their own business needs and operational working preferences.

Fig. 1 .

 1 Fig. 1. 2D Projection of air traffic on the grid

Fig. 2 .Fig. 3 .

 23 Fig. 2. Voronoi cells construction. Projections of the centers of loaded cells are shown with points and the associated cluster centers are shown with crosses

Fig. 4 .Fig. 5 .

 45 Fig. 4. A 3D graph, for which each node represents a building block (center of the Voronoi cell) and each link represents the connection between two nodes on the same level

Fig. 6 .Fig. 7 .

 67 Fig. 6. Sectors building process. Each block center is aggregated to its nearest sectors center 0 max layer I1

1 = 5 1 = 2

 1512 , the second interval starts at M min and ends at M max 2 = 6 and etc. Using those generated altitude intervals that fully cover range of layers, we can partition the airspace into sectors as requested by the operational constraint presented in the previous section.

Fig. 8 .

 8 Fig. 8. In this figure, 5 sectors are generated. For layer 1, all nodes are associated to sector 1, for layer 2, all nodes are shared between sector 1 and sector 3, etc...

Fig. 14 .

 14 Fig. 14. Trajectories crossing designed sectors: in top view sector 5 (blue), sector 3 (brown), sector 4 (light green)

  Ns y 1 y 2 ... y i ... y Ns Ext 1min Ext 2min ... Ext imin ... Ext Ns-1 min Ext 1max Ext 2max ... Ext imax ... Ext Ns-1 max Here, the first table represents coordinates of sector centers and the second table contains the associated vertical extension of each sector center.

ACKNOWLEDGMENT

We would like to thank Nicolas BOULIN from the NEST team for his permanent support with the simulation tools and also Russell GARNHAM who provided valuable inputs, as operational expert, for the specification of the algorithm.

1 offers a much more balanced workload (expressed in seconds of work). The solution for the first scenario includes one entryconflict (sector 4), which is acceptable. The number of short crossings is higher for the solution scenario, however this mainly derives from the fact that sectors are constructed from smaller cells. Smoothing of the borders will remove some of those short transits through the designed sectors. In terms of shape and size of the sectors, first, lateral shapes of the designed sectors show some similarities with the reference sectors, main differences are with DFLs (Division Flight Level) selected by the algorithm. Secondly, a comment regarding the reference sectors: whilst the volumes exist, they would not be configured with different DFLs, as such this reference scenario does not exist. This could lead to the conclusion that the designed sectors with the selected DFLs would show even greater improvement over a really existing scenario. The difference in size of the designed sectors (sector 1 and 2) DFL 245-365 would indicate that conflicts and/or traffic are truly unevenly distributed.

While the solution for the scenario 1 seems to provide better results than the reference scenario, Fig. 13 shows that a large amount of trajectories are close to a boundary of the designed sector 1 (pink one). This is not ideal but this criterion has not been specified as part of the parameters of the algorithm and consequently it could not be taken into account. Nevertheless, solution for the scenario 2 (Fig. 15), which uses the same parameters as for the scenario 1, except the weight of workload balancing criterion, offers another design of the sectors which avoids trajectories along the sector boundaries(in Fig. 14 sector number 5 in blue).

Solution for the scenario 2 (see table IV) maintains satisfy-