Cédric Teyton

Jean-Rémy Falleri

Xavier Blanc

Mining Library Migration Graphs

Software systems intensively depend on external libraries, chosen at conception time. However, relevance of any library irremediably changes during projects and/or library life cycle. As a consequence, projects developers must periodically reconsider the libraries they depend on, and must think about library migration. When they want to migrate their libraries, they then have to identify candidate libraries that offer similar facilities and thus can substitute to each other. They also have to compare candidates to choose the one that best fits their needs. Finding a relevant library replacement is a well known tedious and time-consuming task. In this paper, we propose an approach that identifies sets of similar libraries and that produces what we call library migration graphs that show how existing projects have performed migrations among them. These graphs, constructed from the observation of a large number of software projects, ease the discovery and selection of library replacements.

I. INTRODUCTION

Almost all software projects depend on external libraries that provide useful technical facilities. Examples of such libraries are JUnit for unit testing or Log4J for logging. The relevance of a library for a given project irremediably changes during the project and/or the library life cycle. As a consequence, projects developers must periodically reconsider the libraries they depend on, and must think about library migration when the libraries they depend on are not updated, or when competing ones appear with more features or better performances for instance.

Even if library migrations are not so frequent in project life cycle, we observed that they do exist. By looking at the source code repository of several thousands of open-source software projects, the migrations we observed fall into the following categories:

• Convenience, as expressed by these developers: "changed from MySQL to HSQLDB, so that it can be built on any machine" 1 and "changed JTA dependency to use geronimo spec to avoid having to download and install JTA manually" 2 . • Outdated: "switched to using Google Guava library instead of older collections library" 3 . • Incompatibilities: "Added Slf4j in favor of Commonslogging to avoid conflict with Hibernate Validator" 4 or "port logging to slf4j (commons-logging has classloader issues)" Whatever the category, developers that are looking for replacement libraries can currently only use general purpose search engine, such as Google. For example, developers that want to migrate from the Commons-logging library would probably query Google with "logging library Java". Such a query returns many technical websites that provide partial, incomplete and out-of-date answers of libraries to migrate to. Therefore, to not end up in a tedious and time-consuming process, there is a need for an approach that helps to find adequate candidate libraries to migrate to, which is the purpose of this paper.

Library migration raises two main issues. The first one consists in identifying libraries that offer similar facilities and thus can substitute to each other. The second one consists to provide comparison criteria to help developers to choose the ideal library to migrate to. For example, if a project wants to migrate from Log4J, it may consider SLF4J or Commons Logging as they both address logging, and SLF4J may be preferred as many more projects have chosen SLF4J rather that Commons-Logging.

In this paper, we propose to address these two issues by analysing large corpus of software projects to see how their dependencies evolve in order to exhibit common behaviours. We assume that if we observe that a large number of projects migrate from Log4J to SLF4J, it is then relevant for every project using Log4J to consider SLF4J as a good candidate to migrate to. We base our analysis on modern software project management tools that ease specification and maintenance of software dependencies. Whatever the tool, Maven 6 , Apache Ivy 7 , or Gradle 8 for instance, their principles are quite the same. Each project defines its dependencies with other projects in a configuration file. The tool then checks the dependencies during the life cycle of the project (compilation, testing, deployment, etc.). Thanks to such configuration files, which make dependencies explicit, we can analyse how library migrations are performed by projects, with the intent to exhibit common migration rules. Such an analysis is even more simple when the build management tools propose a central repository that stores all configuration files of all projects, which is the case at least for Maven.

Our contribution is twofold. First, we propose a mining approach that exhibits migration rules and that can be applied to any tool that manages library dependencies. Our approach computes what we call migration graphs that exhibits categories of similar libraries with relationships representing how often migrations have been performed between them. Second, we present the result of our mining approach applied to the Apache Maven 9 project management system. This result presents several categories such as logging, data base and XML analysis. We have compared our migration graphs with usage trends of libraries in order to show that they add valuable information.

The remainder of this paper is structured as follows. Section II explains our process to mine library dependencies in order to generate library migration graphs. Section III presents a case study of our approach on the projects located on the major Maven repository. Section IV exposes the migration graphs extracted during the case study. Section V discusses the limitations of our approach. Section VI presents the related work, while Section VII uncovers the future work and concludes.

II. APPROACH

In this section, we first present the abstract model we define to represent evolving software projects. Based on this model, we present the algorithm we use to extract what we call migration rules that abstract library migrations performed by projects. Finally, we present what we call migration graphs that express categories of similar libraries and that highlight library migration flow.

A. Dependency Model

In order to be independent of any project management tool, we propose to abstract the data needed to perform our analysis in what we call a dependency model. This model is very simple as it only contains the set of analysed projects, their list of revisions and, for each revision the associated set of dependencies. More formally, P is the set of software projects of the model (we consider that a library is a project too). Each project p ∈ P has an associated totally ordered set R p of project revisions. This set is sorted chronologically according to the revision dates. For a project revision r ∈ R p , we define d(r) : R p → P(P ) the set of its dependencies.

Let us illustrate our model with an example. We assume six projects, two development projects (P A and P B ) and four libraries (JUnit, JMock, Log4J and SLF4J). Based on this model, for a given revision r i , we introduce rem(r i ) = d(r i-1 ) \ d(r i ) and add(r i ) = d(r i ) \ d(r i-1 ) that give respectively the added and removed dependencies at a given revision with respect to the previous revision.

With our example, we can see that rem(P 3 A ) = {Log4J} and add(P 3 A ) = {SLF4J}. These two sets will help us to identify library migrations performed at a given revision.

B. Mining library migration rules

A project performs a library migration when it exchanges one of its dependent library by another one. Such migration includes two libraries with different names, and thus discards library upgrades. Therefore, if a project updates a dependency from JUnit 3.8 to JUnit 4.8, this is not considered as a migration in our approach. More formally, we define a library migration rule m ∈ M as a couple (s, t) ∈ P 2 with s = t. s is the old library (source) and t is the new library (target). A migration rule denotes the removal of s in favour of t. Note that we assume that migration rules are one to one rules. We do not consider cases where one or several libraries are replaced by one or more libraries. Thus, n:m migration rules are not discussed in this paper.

To extract migration rules, we apply a straightforward algorithm that iterates on revisions of a set of software projects (see Algorithm 1). For each revision, our algorithm looks at the dependencies that have been removed and added. It then creates a candidate migration rule for each element of the Cartesian product of the removed and added dependencies. The removed (resp. added) dependencies are the source (resp. target) of the candidate migration rules.

Once candidate migration rules have been created, we filter out candidates that are not relevant according to a scoring function. To that extent, we define the function r(m) : M → P( p∈P R p ), that returns for a given rule m the set of revisions that target the rule. We introduce the confidence conf(m) : M → R as the minimum value between |r(m)| |{(s,x)∈M }| and |r(m)| |{(x,t)∈M }| , where m = (s, t), where (s, x) with x ∈ P that denotes any rule r ∈ M having s as a source, and where (x, t) that denotes any rule r ∈ M having t as a target.

With our example, the Cartesian product returns the rules

m 1 = (JUnit,JMock), m 2 = (JUnit,Log4J), m 3 = (Log4J,SLF4J) and m 4 = (JMock,JUnit). Moreover r(m 1 ) = {P 2 A }, r(m 2 ) = {P 2 A }, r(m 3 ) = {P 3 A } and r(m 4 ) = {P 2 B }.
Since there are two rules having JUnit as source and one rule having JMock as target, conf(m 1 ) = min( 1 2 , 1 1 ) = 0.5. Similarly, conf(m 2 ) = 0.5, conf(m 3 ) = 1 and conf(m 4 ) = 1. If we set a threshold of confidence of 1, only the rules m 3 and m 4 are filtered in.

As our filter may return false positives, candidate rules are manually checked. The goal of this manual check is to build the set E of expert rules, which are the rules that correspond to correct migrations. To help this manual step, we propose a pseudo automatic analysis of description mes-Algorithm 1 Our migration rules mining algorithm for all p ∈ P do for i = 2 → size(R p ) do

r i = R p [i] R = rem(r i ) A = add(r i ) for all r ∈ R do for all a ∈ A do m ← (r, a) M ← M ∪ m r (
m) ← r(m) ∪ r i end for end for end for end for sages attached to commit performed while a library migration occurs. Looking at such messages may provide confidence to the truth of migration rules. For instance, a commit message associated to revision a3 saying that the library Log4J has been replaced by SLF4J provides confidence for the migration rule m 3 =(Log4J,SLF4J). In our example, we consider that both m 3 and m 4 have been confirmed to be correct (E = {m 3 , m 4 }).

As a last step, we add to E the rules from M that have been incorrectly filtered out, but can be deduced from the rules of E by applying transitivity and symmetry. This step, called rules augmentation, is described in Algorithm 2. On our example, Algorithm 2 adds (JUnit,JMock) in E. Finally E = {m 1 , m 3 , m 4 }.

Algorithm 2 Rules augmentation

for all m = (s, t) ∈ M \ E do if ((s, y) ∈ E ∨ (y, s) ∈ E, y = s) and ((y, t) ∈ E ∨ (t, y) ∈ E) then E = E ∪ m else if ((t, y) ∈ E ∨ (y, t) ∈ E, z = t) and ((z, s) ∈ E ∨ (s, z) ∈ E) then E = E ∪ m else if (t, s) ∈ E then E = E ∪ m end if end for

C. Building migration graphs

After having identified migration rules, we compute what we call a migration graph. The nodes of this graph are projects that have been either source or target of at least one migration rule. Nodes of a migration graph are then library projects that have been migrated. A directed arc exists between two nodes if there is at least a migration rule between the two nodes. To indicate the flow of migration between the different libraries, the arcs are labelled using r(m) (an arc m = (s, t) is labelled with |r(m)|).

JUnit

JMock 1 1

Fig. 1: A category of our example

To extract categories of similar libraries, we compute the connected components on the migration graph. Each connected component is a category, whose software projects of the category are the union of the projects contained in the connected component. An example of category is shown in Figure 1. This category shows that JUnit and JMock are similar and that projects have performed migration in the two sides.

III. CASE STUDY : MAVEN CENTRAL REPOSITORY

For practical reasons, we have realized our case study on projects managed under Maven because 1) it has a centralized repository system of almost 40 000 projects 2) there is a webbased REST API enabling to easily retrieve information from this repository.

A. Extracting dependencies from Maven

Maven is a build and dependencies management system for Java software projects. Each project managed by Maven requires a so-called POM (Project Object Model) XML file that contains three mandatory tags: a groupId that defines the group owning the project, an artifactId that is the unique name of the project under the groupId, and a version number. POM file also contains a dependencies tag where a set of dependencies can be specified, each one by the groupId of the dependency, its artifactId and optionally its version. Figure 2 shows an excerpt of the POM file of JUnit in its 4.10 version.

Project dependencies are stored on a Maven repository. These dependencies are Maven projects as well, and have therefore a POM file as well. The Maven Central Repository10 (MCR) is the official Maven repository. It serves over 70 millions downloads every week 11 . It is a relevant data source for our case study for two reasons: 1) the set of projects located on the MCR is large and 2) the dependencies are specified with consistency and can be easily retrieved across projects, which allows us to concentrate on extracting the migration rules.

We now detail how we instantiate our model from the data present on the MCR. First of all, P is the set of projects located on the MCR. A project p ∈ P is identified as an element groupId:artifactId according to the tags included in its POM file. Each project p has an associated set R p containing all its versions. This set is ordered using the versioning scheme used by Maven12 applied on the tag. To obtain a list of dependencies d(r), r ∈ R p , we investigate the dependencies section of the POM file. It contains several dependency tags, from which we extract the groupId and artifactId tags. This process is illustrated in Figure 2.

<project>

B. Filters to improve rule generation

Within Maven, a same project can exist under several identities, whereas it should be perceived as a unique one. For example, one project can make use of either junit or junit-dep, with both referring to the junit project. In our opinion, if a project updates its dependency junit to junit-dep, it is not relevant to consider this as a migration rule. Also, the project hsqldb can be found under both groupId org.hsqldb and hsqldb. If a project decides to change only the groupId of a dependency, we should not consider it as a migration. This situation can lead to the case where two different rules exist but with a similar semantic. For example, (org.hsqldb:hsqldb,com.h2database:h2) and (hsqldb:hsqldb,com.h2database:h2) should be merged as a unique rule.

To tackle these issues, we propose a four-step process to finally produce migration rule :

1) We apply a post-processing step after the computation of the sets rem(r i ) and add(r i ). Its objective is to remove from these sets the projects that fall into the previous situations. Our solution is to consider only the artifactId of the projects from rem(r i ) and add(r i ), regardless the groupId. 2) For each element p that both belongs to rem(r i ) and add(r i ), we remove p from those two sets. From now, projects dependencies are only seen with their artifactId. 3) We detect the similar remaining elements from these two sets that must be discarded from the analysis.

To that purpose, we compute T p the set of tokens appearing in the artifactId of a project p. For instance T p = {junit,dep} for junit-dep. The segmentation is done using non-alphanumeric characters and Camel-Case. Then p and p ′ are removed from resp. rem(r i ) and add(r i ) iff p ∈ rem(r i ) and p ′ ∈ add(r i ) with T p ∩ T p ′ = ∅. 4) The Cartesian product can now compute the migration rules.

An example of this straightforward process is detailed in Figure 3. This example highlights the removal of misleading migration rules. For instance, thanks to our process, the rule (junit:junit-dep) is not returned.

As a last point, we introduce |g(m)| as the set of distinct groupIds of projects on which m ∈ M has been observed. This value intervenes as it may happen that several sub-projects within a similar groupId perform the same migration. This can be due to a lack of modularity in the project organization. It results that, if a migration rule is observed in 10 sub-projects simultaneously, its score is increased of 10 as well. However, we think that such situation bias the actual score of a migration rule. We therefore decide to compute the value |g(m)| since it is a better indicator than |r(m)| to estimate the popularity of a migration rule. For instance if r(m

) = {g 1 :a 1 , g 1 :b 2 , g 2 :c 1 }, g(m) = {g 1 , g 2 }.
In the remainder of the article, we use |g(m)| instead of |r(m)| to evaluate the popularity of a migration rule.

C. Results

The MCR provides a Web REST API to ease the access to the projects it contains. We have used this API to setup an automatic process and to collect 38588 projects and 310571 projects releases. Looking for every p ∈ P and their associated R p on the repository took about 2 hours. Mining every associated POM file takes about 35 hours. Computing the rules from every successive couple of set of dependencies d(r1), d(r2) takes 2 minutes. Before filtering, we obtain a list of 925 migration rules that constitute the set M .

Among the generated 925 rules, we need to filter the incorrect rules as much as possible to reduce the manual work when building the expert rules E that we finally deliver. To that purpose, we first use the previously introduced g(m). We include in E only rules having a value |g(m)| ≥ 2. The idea behind this statement is that a migration rule gains confidence if it has been observed on several unrelated projects, here at least 2. This filter builds a subset M ′ ∈ M of 385 rules.

We decide to retain only rules that have a sufficient confidence value conf(m). We therefore introduce a threshold of confidence value t c that must be fixed. In order to optimize the threshold t c , we run our tool against the previously computed set M ′ with different values for t c . Then we manually rate the migration rules found, either as correct or wrong. We aim at maximizing the number of true positives while reducing as much as possible the number of false positives. Results are reported in Figure 4. Note that manually reviewing a rule is usually an easy task as it only requires to look at the websites of the projects to see if they target the same domain. Nevertheless, it is possible that a few false positive were not removed due to a misunderstanding of the libraries features. The whole task of removing the false positives took about 2 hours for rating the 385 rules.

According to the results reported in Figure 4, we choose to set t c to 0.06 so that we achieve a precision of 0.67, containing 57 correct rules and 27 incorrect rules. Using the 57 correct rules, we apply the rule augmentation technique described in Algorithm 2. This technique managed to extend E from 57 to 80 rules. This set of 80 rules is the definitive set of expert migration rules E.

D. Valuable information from commits logs

As stated previously, we had to manually assign as either correct or wrong each migration rule found. Basically, one can search quickly over the internet the validity of the migration. But we consider that the developers are also willing to check the reasons why developers previously performed a migration. In a second time, they want to obtain additional information that support them to perform a migration.

To that purpose, we chose to mine commits logs of a wide set of Java open source projects. The idea is to look for commit logs that match both the source and the target of a given migration rule. Then, the results expose existing commit logs that explicit the migration and/or an associated justification. We arbitrarily selected from four open-source platforms, 5340 projects from Google Code14 , 16000 from SourceForge15 , 12308 from Github16 and 1063 from Apache17 . We have collected the commits log of total of 34688 projects, resulting in around 3,9M of commit messages.

We provide on the web page 18 a search engine that returns a list of commits that can be relevant for the recommendation. To show that this tool can provide assistance for developers when they deal with migration rules, we explicit in Table III an excerpt of commits of interest for Logging and Database facilities. These migrations are discussed in Section IV.

To make sure about the invalidity of a migration rule, the absence of relevant results in the search engine is a solid argument. However, those messages must be used for indications only. There is no guarantee that a sound migration rule will match necessarily at least one meaningful commit log. The set of projects in the database has been chosen arbitrarily with no assumption about the quality of the registered commit logs. However, users are likely to find at least few results against a true migration rule.

Logging

• "logger api changed from sfl4j-log4j to logback-classic" • "change logging system from using log4j directly to using commons-logging" • "changed to use commons-logging instead of log4j directly" • "moved ordi from log4j to slf4j-api to be more easily embeddable" • "replaced commons-logging with slf4j-log4j12"

• "say goodbye log4j. welcome slf4j-simple"

• "loggers should be of type org.slf4j not logback-classic"

Database

• "replace h2 w/hsqldb 2.0 for now"

• "changed database from mysql to hsqldb 2"

• "changed default database from mysql to derby" • "use derby instead of h2 database"

• "removed derby in favour of hsqldb"

• "move sql changes from h2 to mysql engine" TABLE III: Commit logs for assistance in rule validation (7 commits log for logging utilities and 6 for database facilities)

IV. EXPLOITATION OF THE RESULTS

A. Analysis of the migration graphs

In this section we analyse the migration graphs extracted in Section III, and discuss the results we obtained regarding library migration. We compare the conclusion drawn from the graphs with the one that could be drawn from the plot of the evolution of the use of the libraries (this information is computed from the MCR). We show that our migration graphs offer an interesting complement of information and allow to detect interesting libraries which do not really stand out from the evolution plots. Then, we detail four visual patterns that help reading our migration graphs.

For sake of place, we present the analysis of five migration graphs attached to three domains : logging, database and XML. Those categories appear to be among the most utility libraries used in software projects. We have used JUNG 19 to draw them. As explained in Section III, we used |g(m)| instead of |r(m)| to label the arcs. Moreover, in the figures the size of the arcs is proportional to |g(m)|. Finally, the number of users of a library is indicated using the color of its node. A dark node indicates that the library is heavily used while a white node indicates that it has only few users. This number of users is relative to the library uses of a category, and is not related to the total number of projects we study.

1) Logging: Figure 5 shows a migration graph of libraries targeting the logging domain, containing 9 libraries. We can notice that a significant number of migrations go from Commons-logging 20 (80 departures) and Log4J 21 (34). Inversely, the library SLF4J 22 appears to be a leader and is 19 http://jung.sourceforge.net/ 20 http://commons.apache.org/logging/ 21 http://logging.apache.org/log4j/ 22 http://www.slf4j.org/ Fig. 5: Migration graphs for Logging libraries the target of a high number of migrations. This is even more significant considering that SLF4J library is declined in several sub-libraries that appear in the graph with different nodes (e.g., slf4j-simple). Also, by computing the score of its respective ingoing edges, it turns out that 30 groupIds have migrated to LOGBack23 and only 2 times from, targeting SLF4J. This may be an indication that projects that migrate to LOGBack are globally satisfied. Using this graph, we could recommend to the developers to consider dropping the Commons-logging and Log4J libraries, and to replace them by SLF4J or LOGBack.

On the web pages of these two libraries we can read "The logback-classic module can be assimilated to a significantly improved version of log4j" and "The Simple Logging Facade for Java or (SLF4J) serves as a simple facade or abstraction for various logging frameworks, e.g. java.util.logging, log4j and logback, allowing the end user to plug in the desired logging framework at deployment time". It clearly seems that they aim to replace logging libraries such as Commons-logging and Log4J.

Figure 6 shows the evolution of the use of the four mostused logging libraries. In this figure, we can notice that SLF4J stands out from the other ones, which strengthens the conclusion drawn from the migration graph. However, LOGBack does not appear as particularly interesting and would probably not be seriously considered using only this plot.

2) Database: Within the database category, we observe several balanced migrations between HSQLDB24 , Derby25 , and MySQL26 . We also notice that 6 groupIds have migrated from HSQLDB to H227 , and nobody did migrate from H2. By looking to this graph, we could recommend to the projects to seriously consider using H2. By looking on the web page of H2, it seems that it has more features28 than its competitors, and very good performances 29 . Interestingly, we did perform a migration from HSQLDB to H2 in one of our own software projects30 when seeing these figures, with a significant gain in features and performances.

In contradiction to our approach, Figure 8 presents a classic evolution of the use of the database libraries. We can observe that MySQL interest is a bit slowing down, and that HSQLDB stands as the leader. Using only this plot, the H2 library would not arise as interesting since it has less users than its competitors.

3) XML: Figure 9 shows the three migration graphs that can be attached to the XML domain. XMLBeans31 looks like an emerging library as it underwent a migration from within . By looking to their websites, we did not understand the reason for this migration, although we have evidence in the SVN commit logs that it is not a false positive. xml-apis is preferred to xmlParsersAPI. By looking in the Maven repository, we noticed that in fact it is the same library, that was not eliminated by our text-mining techniques. Nevertheless, xmlParsersAPI is the outdated one. Finally, SJSXP and Woodstox33 (wstx) are two STAX-compliant XML processors. As there are few users of SJSXP, and as some of them are migrating to Woodstox, the later seems to be the library of choice in for STAX compliant parsers. This intuition is strengthened when looking at Figure 10, which shows that wstx is the largest used STAX-compliant XML found with our migration rules.

B. Visual Patterns

To assist the analysis of a migration graph, we propose four visual patterns that can be quickly observed. These patterns allow to characterize some specific migrations. First, the Gold Rush pattern is observed when a library has many input migrations and few output ones. This clearly means that many projects migrate to this one. We believe this library has certainly more advantages than the other ones. As a consequence, the Gold Rush pattern can be used as a choice criteria to choose the right library to migrate to. On the contrary, we would not recommend projects that match the target of the exodus pattern, such as commons-logging. The Pong pattern refers to a bi-directional migration, that does not promote a project more than an other. The Challenger denotes a recent but promising candidate, as it has been adopted widely in a short period of time.

Table IV briefly summarizes these patterns. For each pattern, it explains how to observe the pattern, and provides an advice for developers that think about migrating their libraries.

V. LIMITS AND DISCUSSION

In this section, we discuss several important insights we gathered by performing our study.

Frequency of migrations: With regards to the data generated during the case study, we observe that library migrations happen along software life cycle. On the other hand, this phenomenon is not that frequent if we relate it to the total number of projects. It supports the idea that a large set of data is definitively necessary for a study similar to ours.

False positives: Even though we show confidence when we claim that two libraries can be employed for the same usage, the limited number of rules (80) classifies only a small part of the projects contained in the MCR that can be used as third-party libraries. However, more true rules are available in the initial set of 925 rules E, but except using a manual review, it seems hard to automatize a filter for them. Indeed, we observed many times in the low-ranked rules the rare rule syndrome: relevant rules appearing only once or twice. Recovering these rules would probably require additional information sources such as code source or documentation analysis. Also, a post-processing could be used to refine migration rules found using a software categorization technique, such as MudaBlue [START_REF] Kawaguchi | Mudablue: an automatic categorization system for open source repositories[END_REF]. This could potentially eliminate a significant range of false positives.

Validation of the migration graphs: We did not perform an empirical validation of our migration graphs with developers. For the future, we plan to propose such graphs to developers and ask them to evaluate the usefulness of our recommendations.

Bi-directional patterns: A migration rule classified as Pong according to Table IV may reveal a situation where several projects migrate back and forth between two libraries. Currently, our approach does not correlate migration with time, but it could provide an useful additional indicator.

Impact of time: The mining of the migration rules is sensitive to the time. Indeed "recent" migrations necessarily have a lower score than the ones that took place over a long time period. Anyway it is not hard to overcome this issue by setting a threshold on the release date of the project release taken in consideration.

Incremental mining: It is possible to refresh the results of our mining approach periodically. Moreover it is possible to take advantage of the manual review of the rules to eliminate many false positives in the subsequent analyses. Indeed, if an expert rules exists among the candidates of a rule, it is possible to remove them from the candidates. Also, if a manually filtered rule is extracted, it is possible to not increment its score.

VI. RELATED WORK

Research work related to our concern falls in the domain of API migration and evolution.

Library categorization: Research has been done on software project categorization to allow searching for similar software. This problem is usually resolved by computing similarity score based on specific attributes, such as keyword identifiers as MudeBlue [START_REF] Kawaguchi | Mudablue: an automatic categorization system for open source repositories[END_REF] does or API calls [START_REF] Mcmillan | Categorizing software applications for maintenance[END_REF]. Those techniques require either the source code or the binaries versions of a set of libraries to compute similarity scores among them. Regarding our concern, the main limitation of such a work is that there is no guarantee than one library can be used instead of another one. For example, two software that perform XML operations could be seen as similar even if their intended usage is not.

Large-scale API usage: Mileva et al. have observed evolution of dependencies on 250 Apache projects along 2 years to mine usage of API versions [START_REF] Mileva | Mining trends of library usage[END_REF]. The study shows the usage trends of different versions of a same project. It also was interested in cases where clients switched back to a previous version of a library. We reused the idea of usage trends in Section IV. While it offers valuable information, we have shown that several interesting libraries cannot be identified with just this piece of information.

Lämmel et al. propose a large-scale study on AST-based API-usage over a large set of open-source projects [START_REF] Lämmel | Large-scale, ast-based api-usage analysis of open-source java projects[END_REF] . Their work provides an insight on how a specific API is globally used by client projects. In particular, they categorize whether NAME TARGET DESCRIPTION EXAMPLE

Gold Rush

Library A library has many input migrations and few output ones. Developers should consider migrating to it.

SLF4J-API

Exodus

Library A library has many output migrations and few input ones. Developers should consider to stop using it.

COMMONS-LOGGING

Challenger

Library A library that is the target of a significant number of migrations originating from the most used library. Developers should consider migrating to it.

H2

Pong Migration Bi-directional migration rules with similar occurrences, no conclusion can be drawn from this pattern.

(HSQLDB,DERBY) API Wrapping: During a library migration, the API-level challenge is to transform the code so that it becomes compliant with the new library. This domain aims at answering the question "How to replace a library X with Y ?". Bartolomei et Al. have addressed this problem and studied the design of API Wrappers, which are objects that adapt and delegate the previous source code instructions towards the new API [START_REF] Tonelli Bartolomei | Study of an api migration for two xml apis[END_REF], [START_REF] Tonelli Bartolomei | Swing to swt and back: Patterns for api migration by wrapping[END_REF]. The mappings are manually identified and their concern is to design such wrapper in order to obtain a compliant version of the new source code. Our approach is useful for such a problem as it identifies which libraries are source and target of migrations. It can then be used as a source of validation for the wrapper. Our approach does not study this particular aspect of research, but can help to identify projects that performed a particular migration.

API Upgrade: The problem of updating a library has also been studied in the literature. A challenge w.r.t. to library usage is to provide relevant snippets of code source according to the programmer's context. We distinguish two main techniques to that extent. The first one mines code that already performed an update. For instance, Schafer et Al. [START_REF] Schäfer | Mining framework usage changes from instantiation code[END_REF] examined code instantiations of two versions of a framework. This code is included with the release as test or example code. Also, SemDiff [START_REF] Dagenais | Recommending adaptive changes for framework evolution[END_REF] is a client-server connected to a framework source code repository that mines the changes and recommends modifications for a client migration. The second variety of approach requires only internal code of two API versions and applies origin analysis techniques. Hence, a graph-based representation of the code based on dependencies allows for element matchings from the two versions. Some promising results have been achieved in this area [START_REF] Wu | Aura: a hybrid approach to identify framework evolution[END_REF] [START_REF] Nguyen | A graph-based approach to api usage adaptation[END_REF]. Whatever the technique, our approach can be used as a mass source of data to get real library migrations and to get references of real projects that do have performed migrations. Such a mass of data can be used to validate the proposed approaches.

Language migration: Zhong et al. proposed a Mining API Mapping approach that detects relations from two versions of an API written in different languages [START_REF] Zhong | Mining api mapping for language migration[END_REF]. The idea is to get client-code from the two versions and to build a transformation graph that represents the API-usage migration from one language to another. Zheng et al. propose a crosslibrary recommendation tool based on Web queries [START_REF] Zheng | Cross-library api recommendation using web search engines[END_REF]. The idea is to inquire Web search engines and to mine results proposed from the query. One example of query could be "HashMap C#" when looking for the equivalent for standard Java HashMap for C#. The results are computed one by one and candidates are ranked by relevance, mainly according to their frequency of appearance. For the moment this work provides only preliminary results and queries proposed are of a coarse grain. Also, it strongly lies on Web search engines such as Google, and requires manual query writing, which can highly influence the results. Regarding our approach, this work can be used to merge equivalent libraries and then to improve library migration graphs.

VII. CONCLUSION AND FUTURE WORK

In this paper we address the issues raised by library migration, which is a mandatory task during the life cycle of any project that depends on open source libraries. When a project has to replace one of the libraries it depends on, two issues have to be addressed. First, all libraries that provide similar facilities have to be identified. Second, the substitute candidate that fits the project's needs has to be chosen among the identified libraries.

To face these two issues we propose a mining process that is based on library dependencies and their evolutions. We provide what we call migration graphs that show categories of similar libraries and that exhibit how projects migrate between them. Thanks to these graphs, one can quickly identifies which libraries are candidates to migrate to and how many projects have chosen them to migrate from.

As a validation, we have applied our process on the Maven Central Repository that tracks the dependencies of a large number of projects. We have generated migration graphs for the different categories of libraries. For sake of place, we have presented only graphs that correspond to the logging, database and XML categories. Those graphs present libraries of these technical domains and clearly show which are the preferred libraries to migrate to. A deep analysis of these graphs show the insights they provide for library migration in comparison to classical measures such as usage trends.

The work presented in this paper uncovered the fact that library migration is not a frequent phenomenon through open source software life cycle. In our opinion, this is mainly due to two points. First, the cost of performing the migration by updating the project source code base. Second, the lack of existing build automation tools to propose migration recommendations. This raises the developers level of uncertainty to assess the benefits of choosing a new library for their project.

As a further work, we first plan to apply our process on other sources of data. In particular, we can extend our study to the entire open source software world, similar to large-scale repositories mining approaches proposed with SourcererDB [?] or SeCOLD [?]. Moreover, tuning our approach the commit granularity level of version control systems would allow to target more precisely migration rules.

We plan to apply our study to other dependencies management systems, to show that the proposed approach can be generalized. For instance, Ubuntu packages 34 offer a convenient way to access their list of dependencies. As packages evolve across Ubuntu versions, we should reproduce our experiment on such system. Such a study should lead to package migration graphs that would show migrations of packages along Ubuntu releases.

Finally, we plan to use our approach to assist developers while they migrate their code to become compliant with a new library. As our approach identifies existing projects that already did the migration task, we plan to analyse the source code of these projects before and after the migration in order to detect migration patterns. Such patterns abstract refactoring actions that must be performed to be compliant with the new library. The goal is then to automatically apply them in new projects that are migrating.

Fig. 2 :

 2 Fig. 2: An excerpt of JUNIT 4.10 POM file

Fig. 6 :Fig. 7 :

 67 Fig. 6: Evolution of the use of the logging libraries

Fig. 8 :Fig. 9 :

 89 Fig. 8: Evolution of the use of the database libraries

Fig. 10 :

 10 Fig. 10: Evolution of the use of stax-compliants libraries

  5

1 http://code.google.com/p/jlibs/source/detail?r=955 2 http://code.google.com/p/mybatis/source/detail?r=1996 3 http://code.google.com/p/google-gson/source/detail?r=619 4 http://code.google.com/p/sventon/source/detail?r=1681 5 http://code.google.com/p/dyuproject/source/detail?r=668

Table I

 I

	presents this dependency model with revisions of
	P A : (P 1 A , P 2 A , P 3 A ) and of P B : (P 1 B , P 2 B ), associated with their
	corresponding dependencies.

TABLE I :

 I Example of projects with their revisions and their dependencies

  Table II shows the 15 most observed migrations. The whole set E is available online 13 .

		rem(i)
		org.eclipse.jdt:junit org.slf4j:slf4j-api org.hsqldb:hsqldb			junit slf4j-api hsqldb		junit slf4j-api	3 Token-based filter	4 Cartesian product
		add(i)		1 Keep only artefactId	2 Remove duplicates	(slf4j-api,log4j)
		junit:junit-dep log4j:log4j hsqldb:hsqldb			junit-dep log4j hsqldb		junit-dep log4j
								junit and junit-dep
								must be removed
	Fig. 3: Maven-specific filter to improve rule generation. From two sets of 3 dependencies, only one rule is kept after the
	cartesian product.
		140
							False Positive
							True Positive
		120
		100
	Rules found	60 80
		40
		20
		0
		0.04	0.05	0.06	0.07	0.08	0.09	0.1
				Threshold
		Fig. 4: Precision evaluation on t c variations
				Rule
		Source				Target		|g(m)|
		commons-logging			slf4j-api	44
		commons-logging			slf4j-log4j12	21
		junit				testng		20
		google-collections		guava		16
		servletapi				servlet-api	13
		testng				junit		13
		slf4j-log4j12			logback-classic	13
		log4j				slf4j-api	11
		log4j				logback-classic	11
		xbean				xmlbeans		10
		commons-logging			slf4j-simple	8
		hsqldb				h2		6
		gfprobe-provider-client	management-api	6
		commons-logging			log4j		5
		js				rhino		5
		xmlParserAPIs			xml-apis		5

TABLE II :

 II The 15 most observed migrations from E Computing the rule association graph leads to 34 connected components which means that we found 34 categories.

TABLE IV :

 IV Visual patterns observed in the migration graphs the client calls the API (library-like usage) or if it inherits from it (framework-like usage). It may be interesting to integrate such an information in our library migration graph as some libraries may be better than other ones depending of client usage.

http://maven.apache.org/

http://ant.apache.org/ivy/

http://www.gradle.org/

http://search.maven.org/

http://www.sonatype.com/people/2010/12/now-available-centraldownload-statistics-for-oss-projects/

[START_REF] Zheng | Cross-library api recommendation using web search engines[END_REF] http://docs.codehaus.org/display/MAVEN/Versioning

http://code.google.com/

http://sourceforge.net/

www.github.com

http://svn.apache.org/repos/asf/

http://logback.qos.ch/

http://hsqldb.org/

http://db.apache.org/derby/

http://www.mysql.com/

http://www.h2database.com/html/main.html

http://www.h2database.com/html/features.html

http://www.h2database.com/html/performance.html

http://harmony.googlecode.com

http://xmlbeans.apache.org/ 2006 2007 2008 2009 2010 2011 2012

http://www.xbeans.org/

http://woodstox.codehaus.org/


Dominique Attali

Ulrich Bauer

Olivier Devillers

Marc Glisse

André Lieutier
email: andre.lieutier@3ds.commailto

Homological reconstruction and simplification in R 3

Keywords: Topological persistence, homological simplification, isosurface simplification, NPcompleteness Persistance topologique, simplification homologique, simplification d'iso-surfaces, NPcomplétude

We consider the problem of deciding whether the persistent homology group of a simplicial pair (K, L) can be realized as the homology H * (X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in R 3 . As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S 3 within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-complete.

Introduction

In this paper, we establish NP-completeness of a variety of related problems that ask for an object in R 3 with a prescribed homology.

In the most basic setting, we have a point cloud in R d that samples a shape and want to retrieve information on the sampled shape. There exists a whole spectrum of possibilities regarding the type of sought information. At the coarsest level, we can content ourselves with the homology groups which record the "holes" of a given dimension, hereafter referred to as homological features (connected components, cycles, cavities and so on). At a finer level, we may be interested in building an approximation of the shape, reflecting as accurately as possible both its geometry and topology. The standard way is to construct a simplicial complex using the data points as vertices, such as for instance the α-complex, the Rips complex or the Čech complex [11 11, 10 10]. All three constructions have in common to depend upon a scale parameter α and to get bigger as α increases. In the ideal case, we expect the complex to have the right homology for some suitable value of α [18 18, 7 7, 5 5, 1 1]. Unfortunately, depending on the sampling, it may happen that such a value of α does not exist. Nonetheless, we might still be able to infer the true homology of the shape hidden in the noisy data using persistent homology [13 13, 8 8, 6 6]. Given two scale parameters α 1 and α 2 , the persistent homology groups record the homological features that persist from α 1 to α 2 . Under very weak hypotheses, we know that the persistent homology is precisely that of the sampled shape. The persistent homology can be computed efficiently (i.e., in polynomial time).

A natural question is then to ask for a complex that carries the persistent homology: given a complex K and a subcomplex L, can we find a subcomplex of K that contains L and whose homological features are precisely those common to L and K? Our answer is that sometimes we cannot, and deciding whether we can is NP-complete. This answer was first given in the general case by Attali and Lieutier [2 2], who posed the restriction to complexes embedded in R 3 as an open problem. We resolve this problem by proving NP-completeness even for complexes embedded in R 3 . Note that in R 2 a solution always exists and can be computed in polynomial time. The above problem concentrates on building a complex whose homology matches perfectly the persistent homology of L into K: all the homological noise has been removed. We call such an object a homological reconstruction. However, when it does not exist, it is still relevant to look for a complex nested between L and K and whose homology is as close as possible to the persistent homology of L into K: as much noise as possible has been removed. We call such a complex a homological simplification and prove that finding one is also an NP-hard problem.

In the field of visualization and image analysis, another common setting consists in describing a shape through a continuous function f : R d → R instead of a point cloud in R d . For instance, a medical image may be a collection of density measurements over a grid of 3D points and is best modeled as a continuous map over a certain domain of R 3 . In the ideal case, the shape is a sublevel set of the function, f -1 (-∞, t]. Unfortunately, noise can plague the data. As the parameter t increases, sublevel sets inflate and we can track the evolution of their homology. Features that appear and disappear quickly are considered topological noise, and we can consider the common features of two sublevel sets as those of a denoised sublevel set. The question now becomes: can we find another cleaner function, close enough to the original one, whose sublevel set has the denoised homology, i.e., a sublevel set reconstruction? Again, in R 2 such a denoised function always exists and can be found in polynomial time [3 3], while in R 3 the problem does not always have a solution. The corresponding optimization problem asks for a sublevel set simplification, i.e., a function close to the original one that minimizes the number of homological features of the sublevel set. Often, one is also interested in the homology of a level set, f -1 (t). We show how it can be related to the (persistent) homology of sublevel sets,and consider the corresponding level set reconstruction/simplification problems.

Further in this direction, Edelsbrunner et al. introduced the well group [14 14, 4 4] as a denoised version of the homology group of a level set. Again, we can ask whether one can find a realization of the well group, i.e., a cleaner function whose level set has the same homology as the well group? Figure 1: Left: Example of a simplicial pair (K, L) having no homological reconstruction. Right: Example of a simplicial pair having a homological reconstruction as a subspace, but not as a subcomplex.

We shall see in this paper that all of these related problems are NP-hard, as a consequence of the NP-completeness of the homological reconstruction problem.

Background and notations

We are only concerned with topological spaces that are triangulable by a finite simplicial complex, so simplicial and singular homology are isomorphic and we make no distinction between the two. In particular, we use the simplicial versions of the Excision and Mayer-Vietoris sequence theorems, which have less restrictive assumptions than their singular counterparts. If K is an abstract simplicial complex, we denote by |K| its geometric realization. Throughout this article, we consider homology with coefficients in an arbitrary field F, so the homology groups are finite-dimensional F-vector spaces and there is no torsion. Note that for simplicial complexes K embedded in R 3 , this is in fact not a restriction, since due to the absence of torsion in R 3 the Betti numbers are independent of the choice of coefficients [15 15, §3.3].

Given a topological space K, we write H * (K) = i H i (K) for the direct sum of homology groups in all dimensions, and β(K) = i≥0 β i (K) for the total Betti number. If (K, L) is a pair of topological spaces L ⊂ K, the inclusion L → K induces a homomorphism H * (L) → H * (K), which is denoted by H * (L → K). The rank of this map is the persistent Betti number of the inclusion L → K and is denoted by β(L → K) = rank H * (L → K); the image im H * (L → K) is a persistent homology group.

A piecewise linear function on a topological space K is a continuous function f : K → R such that there exists a finite triangulation of K on which f is simplexwise linear.

2 Homological reconstruction of simplicial pairs Lemma 1. Consider a triple of topological spaces L ⊂ X ⊂ K with finite Betti numbers. Then

β(X) ≥ β(L → K).
This property suggests the following definition:

Definition 1 (Homological reconstruction). Consider a triple of topological spaces L ⊂ X ⊂ K with finite Betti numbers. Then X is called a homological reconstruction of the pair (K, L) if β(X) = β(L → K).
We will often omit "homological" since there is no ambiguity in this paper. An equivalent condition for X being a reconstruction is that H * (L → X) is surjective and H * (X → K) is injective, as defined in [2 2]. Not every pair (K, L) admits a reconstruction; a simple counterexample is shown in Fig. 1 1. The use of topological spaces in the definition (as opposed to simplicial complexes) is motivated by the following observation. Let (K, L) be a simplicial pair. Then there might be a reconstruction of (|K|, |L|), but not as a subcomplex of K. An example is shown in Fig. 1 1.

Inria

NP-completeness of homological reconstruction

We now focus our attention on spaces that are geometric realizations of finite simplicial complexes embedded in R 3 .

Theorem 1. The following problem is NP-complete: Given as input a simplicial pair (K, L) embedded in R 3 , decide whether there exists a reconstruction X of (|K|, |L|). The problem is also NP-complete if X is required to be a subcomplex of K.

Proof. We prove this by reduction from 3-SAT. Recall that a Boolean formula Φ is in 3CNF if it is a conjunction of several clauses, each of which is a disjunction of three literals, a literal being either a variable or its negation. Given a 3CNF formula Φ, we construct a simplicial pair (K Φ , L Φ ) embedded in R 3 and prove that (|K Φ |, |L Φ |) has a reconstruction (as a subcomplex of K Φ ) if and only if Φ has a satisfying assignment (see Lemmas 2 2 and 3 3 below).

For this, we associate to the 3CNF formula Φ a simplicial pair (K Φ , L Φ ) in such a way that any reconstruction X of (K Φ , L Φ ) has a trivial homology, i.e.,

β d (X) = β d (|L Φ | → |K Φ |) =        1 if d = 0, 0 otherwise.
This means that X has a single connected component, no loops, and no cavities. X has to fill all loops or cavities in L Φ and has to connect the different connected components of L Φ by adding to L Φ portions of K Φ without creating any new loops or cavities. In the figures, red represents the subcomplex L Φ .

The variable gadget. The variable gadget is a simplicial pair (V i , W i ) as depicted in Fig. 2 2, left. The simplicial complex V i contains 4 edges forming a cycle. The two red edges belong to W i , but not the two blue ones. One of the blue edges will be called True i and the other one will be called False i . The key property of this construction is that any reconstruction of the pair (|V i |, |W i |) cannot contain both edges True i and False i , for otherwise they would create a 1-cycle together with the red ones. This property will allow us to match the presence of the edge True i to a true assignment of the variable v i .

The clause gadget. The clause gadget is a simplicial pair (C j , D j ) as depicted in Fig. 2 2, right. The simplicial complex D j contains a cycle ABCDE. The cycle is closed with two surfaces in C j (thereafter referred to as the lower hemisphere and the disk) thereby creating a cavity. Furthermore, the complex D j contains an arc that ends inside the disk. Whenever we fill the cycle ABCDE with the disk, this connects the two endpoints of the arc, thus creating a new cycle, which we close twice in C j by a left hemisphere and a right hemisphere. Consider one bold edge in the interior of each hemisphere, which is where the clause gadget will connect to the variable gadgets.

True i False i A B C D E F G H
The key property of this clause gadget is that at least one of the 3 bold edges must be present in any reconstruction X of the pair (|C j |, |D j |). Indeed, the cycle ABCDE in X must be filled up. If it is filled by the lower hemisphere, we are done. If it is filled by the disk, we have a new cycle EFGH in X which in turn must be killed either by the left or by the right hemisphere. In any case, X contains at least one of the hemispheres and thus one of the three bold edges.

(¬t ∨ u ∨ v) (t ∨ ¬v ∨ ¬w) (¬u ∨ ¬v ∨ w) t u v w

Inria

Correspondence with a formula. Given a 3CNF formula Φ with n clauses c 1 , . . . , c n and m variables v 1 . . . , v m , we construct a 2-dimensional pair (K Φ , L Φ ) as follows. For each variable v i we take a copy (V i , W i ) of the variable gadget. For each clause c j , we take a copy (C j , D j ) of the clause gadget; for each literal ev i of c j , we identify one of the bold edges of C j to False i if e is a negation and True i otherwise. See Fig. 3 3 for an example.

First notice that β 2 (L Φ ) = 0 (i.e., L Φ has no cavities). Second, we can assume that β 0 (K Φ ) = 1 (i.e., K Φ is connected). Indeed, if K Φ is disconnected, it means that the 3SAT problem (and the reconstruction problem) can be decomposed into 2 independent subproblems with disjoint sets of variables, which can be solved separately. Last, β 1 (L Φ → K Φ ) = 0 (i.e., the cycles in L Φ are boundaries in K Φ ). Indeed, the only 1-cycles in L Φ are the 1-cycles ABCDE in each D j , and they are filled in K Φ . This means that we are looking for a reconstruction with trivial homology.

From a reconstruction to a satisfying assignment. Let X be a homological reconstruction of the pair (|K Φ |, |L Φ |). We do not assume that X is the geometric realization of some subcomplex of K Φ . Assign to each variable v i the value true if the edge True i is contained in X, and false otherwise. For each clause gadget (C j , D j ), at least one bold edge is contained in X. If this edge corresponds to a positive literal v i , this means that True i is in X, v i is true and the clause is satisfied. If the edge corresponds to a negative literal ¬v i , this implies that False i is in X. True i is thus not in X, so v i was assigned false and the clause is satisfied. We have thus shown that the assignment of the variables makes the formula evaluate to true:

Lemma 2. If (|K Φ |, |L Φ |) has a homological reconstruction, then Φ has a satisfying assignment.
From a satisfying assignment to a reconstruction. Given a satisfying assignment for the formula Φ, we construct a subcomplex X ⊂ K Φ such that |X| is a reconstruction of (|K Φ |, |L Φ |). We start with X = L Φ and add to X a selected set of simplices from K Φ . For each clause c j , we pick one literal that evaluates to true and close the cycle in the clause gadget complex D j correspondingly. If the literal corresponds to the bold edge of the lower hemisphere, we add this hemisphere. Otherwise, we add the disk and the hemisphere that contains the bold edge corresponding to the selected literal.

The only 2-cycles in K Φ are in the clause gadgets. As we did not create any 2-cycle in X, it follows that β 2 (X) = 0. By construction, filling the clause gadgets never introduced both True i and False i in X. Indeed, it could only introduce True i if v i was assigned the value true and False i if it was assigned the value false. Therefore, the 1-cycle in the variable gadgets do not appear in X. Also, for each clause gadget, we filled the ABCDE 1-cycle, and whenever we created an extra EFGH 1-cycle by adding the disk, we immediately filled it with the left or right hemisphere. Now we only need to check that the construction did not create any "non-local" 1-cycles. Since for each clause we have only used one of the literals which evaluate to true, the only contact a clause gadget in X has with the rest of X is through a single bold edge, and the clause gadget can be collapsed to that edge. After collapsing all clause gadgets, all that remains are disconnected variable gadgets with at most 3 edges each, and so β 1 (X) = 0. We finally add to X just enough edges from K Φ so that it becomes connected, without creating any extra cycles in the process. This is possible since we assumed that K Φ is connected. Thus we have β 0 (X) = 1. We conclude:

Lemma 3. If Φ has a satisfying assignment, then there is a subcomplex X of K Φ such that |X| is a homological reconstruction of (|K Φ |, |L Φ |).
Embedding. Later, we have to consider not only an embedding of K Φ , but also a triangulation of its complement. The following fact will be useful: Lemma 4. There is a triangulation of S 3 with size polynomial in the size of K Φ and having K Φ as a subcomplex.

(¬t ∨ u ∨ v) (t ∨ ¬v ∨ ¬w) (¬u ∨ ¬v ∨ w)
Figure 4: Example of 3-SAT reduction using a 3D grid embedding.

Proof. First, referring to Fig. 3 3, it is clear that K Φ can be embedded in R 3 . Indeed, we can align the clause gadgets and the variable gadgets along two lines parallel to the coordinate axes and make each clause gadget look like a small body with three long tentacles that connect to the variable gadgets.

We can subdivide the space by first projecting K Φ onto a plane orthogonal to the line carrying the variable gadgets. We get a polygonal region whose complement can easily be triangulated inside a bounding box without adding any new vertex or edge. Extending each triangle in the direction of the projection, we get a collection of tubes whose interiors do not intersect K Φ . Thus, the tubes can easy be triangulated while respecting K Φ to obtain a polynomial size triangulation of a bounding box of the construction, which can trivially be extended to a polynomial size triangulation of S 3 .

We want to remark that a similar construction can be realized even if we restrict edges and faces of L and K to be edges and faces of a 3D grid (see Fig. 4 4). This means that a variant of Theorem 1 1 can also be shown for cubical complexes arising from 3D image data.

Corollary 1. The homological simplification problem is NP-hard: Given as input a simplicial pair (K, L) embedded in R 3 , find a complex X minimizing β(X) subject to L ⊂ X ⊂ K. Proof. To determine if a reconstruction exists, we can first find a complex X minimizing β(X) subject to L ⊂ X ⊂ K. We then only need to check if its Betti number matches the lower bound β(L → K).

Reconstruction and simplification of level and sublevel sets

Given a real-valued function f , we write F t for the t-level set f -1 (t), F ≤t for the (closed) t-sublevel set f -1 ((-∞, t]), and F <t for the open t-sublevel set f -1 ((-∞, t)). In this paper we shall only consider real-valued piecewise linear functions. Note that level and sublevel sets of a simplexwise linear function on a simplicial complex K are not necessarily subcomplexes of K, but subcomplexes of an appropriate subdivision of K. Moreover, we have the following property: 16 16, 17 17]). Let f be a simplexwise linear function on a simplicial complex K. Let K(t) be the induced subcomplex of K on {v ∈ vert K : f (v) ≤ t}. Then K(t) is homotopy equivalent to the sublevel set F ≤t . If t f (v) for all v ∈ vert K, then K(t) is also homotopy equivalent to the open sublevel set F <t . Definition 2 (Sublevel set reconstruction). Let f , g be piecewise linear functions and consider real parameters t and δ. The function g is called a sublevel set (t, δ)-reconstruction of f if gf ∞ ≤ δ and G ≤t is a reconstruction of the pair

Proposition 1 ([
(F ≤t+δ , F ≤t-δ ), i.e., β(G ≤t ) = β(F ≤t-δ → F ≤t+δ ). Inria Note that F ≤t-δ ⊆ G ≤t ⊆ F ≤t+δ , so that β(G ≤t ) ≥ β(F ≤t-δ → F ≤t+δ ).
A sublevel set (t, δ)-reconstruction is thus also a minimizer of β(G ≤t ).

NP-completeness of sublevel set reconstruction

Theorem 2. The sublevel set reconstruction problem is NP-complete: Given as input a piecewise linear function f on a simplicial complex embedded in R 3 and parameters t and δ, decide whether there exists a sublevel set (t, δ)-reconstruction g of f . The problem is also NP-complete if g is required to be simplexwise linear.

Proof. We proceed by reduction from the previous section. Let (K, L) = (K Φ , L Φ ) be a simplicial pair defined by a 3-SAT instance Φ. We construct an instance of the level set simplification problem by defining a simplexwise linear function f : | sd K| → R on the barycentric subdivision of K via its values on the vertices of sd K (recall that a vertex σ of sd K is a simplex of K). Let

f : σ →        -2 if σ ∈ L, 0 otherwise. (1)
Note that for every function g with gf ∞ ≤ 1, the 0-sublevel set G ≤0 contains L and is contained in K.

We show that the following propositions are equivalent:

g : σ →              -2 if σ ∈ L, -1 if σ ∈ X \ L, 1 if σ ∈ K \ X. (2)
We have gf ∞ = 1. By Proposition 1 1, the sublevel set G ≤0 is homotopy equivalent to |X| and hence is a reconstruction of the pair (|K|, |L|) (F ≤1 , F ≤-1 ). Finally, (c) =⇒ (d) is trivial and (d) =⇒ (a) follows directly with G ≤0 as a reconstruction of (F ≤1 , F ≤-1 ) (|K|, |L|).

Corollary 2. The sublevel set simplification problem is NP-hard: Given as input a simplexwise linear function f on a simplicial complex embedded in R 3 and parameters t and δ, find a simplexwise linear function g minimizing β(G ≤t ) subject to gf ∞ ≤ δ.

Proof. To determine if f has a sublevel set (t, δ)-reconstruction, we can first find a simplexwise linear minimizer of β(G ≤t ). We then only need to check if β(G ≤t ) matches the lower bound β(F ≤t-δ → F ≤t+δ ), which can be done in time polynomial in the size of K.

Betti numbers of level sets and sublevel sets

The Betti numbers of level and sublevel sets are related by the following formula:

Lemma 5. Let f be a piecewise linear function on S n , n > 1, and let t ∈ int(im f ). Then

β d (F t ) = β d (F ≤t ) + β n-d-1 (F <t ).
Lemma 7. Let f and g be piecewise linear functions on S n , n > 1. Assume that t ± δ ∈ int(im f ) are regular values of f and t ∈ int(im g) is a regular value of g. Then g is a sublevel set (t, δ)-reconstruction of f if and only if g is a level set (t, δ)-reconstruction of f .

Proof. By hypothesis t ± δ are regular values of f and t is a regular value of g. Thus:

β(G t ) = 2β(G ≤t ), β(F ≤t-δ → F ≤t+δ ) + β(F <t-δ → F <t+δ ) = 2β(F ≤t-δ → F ≤t+δ ).
It follows that g is a sublevel set (t, δ)-reconstruction if and only if it is a level set (t, δ)-reconstruction.

Theorem 3. The sublevel set simplification problem is NP-complete: Given as input a simplexwise linear function on a triangulation of S 3 and parameters t and δ, decide whether there exists a level set (t, δ)-reconstruction g of f . The problem is also NP-complete if g is required to be simplexwise linear.

Proof. We reuse the same reduction as in Theorem 2 2. Since we need functions defined on the sphere, we triangulate the complement of K to obtain a triangulation S of the sphere with size polynomial in the size of K and K ⊂ S as in Lemma 4 4. We extend f from Eq. (1 1) to a simplexwise linear function f on | sd S |:

f : σ →        f (σ) if σ ∈ K, 2 otherwise.
We then prove that propositions (a)-(d) in the proof of Theorem 2 2 and (e), (f) below are equivalent.

(e) f has a simplexwise linear level set (0, 1)-reconstruction g. (f) f has a level set (0, 1)-reconstruction g.

We trivially have (e) =⇒ (f). Now we prove that (f) =⇒ (d). Proposition 1 1 implies that the values ±1 are regular values of f . By Lemma 6 6, the value 0 is a regular value of g. Lemma 7 7 then proves that g is a sublevel set reconstruction of f . Now let g be the restriction of g to K. Since the sublevel sets F ≤t and F ≤t are homotopy equivalent for t ≤ 1, and the sublevel sets G ≤t and G ≤t are homotopy equivalent for t ≤ 0, it follows that g is a sublevel set reconstruction of f .

Next we prove that (b) =⇒ (e). We extend g from Eq. ( 22) to g : | sd S | → R as above for f and notice that 0 is a regular value of g, which by Lemma 7 7 implies that g is a level set reconstruction.

Corollary 3. The level set simplification problem is NP-hard: Given a piecewise linear function f on S 3 and parameters t and δ, find a simplexwise linear function g minimizing β(G t ) subject to gf ∞ ≤ δ.

Proof. To determine if f has a level set (t, δ)-reconstruction, we can first find a minimizer of β(G t ). We then only need to check if β(G t ) matches the lower bound β(F ≤t-δ → F ≤t+δ ) + β(F <t-δ → F <t+δ ).

Realizations of well groups

We now discuss how the previous results relate to the concept of well groups, which were defined in [14 14] as a robust version of the homology group of a level set.

Let f : K → R be a piecewise linear function. For δ ≥ 0, the δ-well group of t ∈ R is defined as

W * ( f, t, δ) = g: g-f ∞ ≤δ im H * (G t → F [t-δ,t+δ] ),
where

F [a,b] = f -1 ([a, b]
). Intuitively, it captures the homology common to all perturbed level sets.

Clearly, the rank of the well group provides a lower bound on the Betti number of the t-level set of any g with gf ∞ ≤ δ. We say that the well group is realized by such a function

g if im H * (G t → F [t-δ,t+δ] ) = W * ( f, t, δ), or equivalently, if β(G t ) = rank W * ( f, t, δ).
As it turns out, the lower bound cannot always be achieved, and hence not every well group is realizable.

More generally, for an interval [a, b] we have

W * ( f, [a, b], δ) = g: g-f ∞ ≤δ im H * (G [a,b] → F [a-δ,b+δ] )
In fact [4 4], the well group is already given by the intersection of just two persistent homology groups: + β((K, F ≥a+δ ) → (K, F ≥a-δ )) β((F ≤b+δ , ∅) → (K, F ≥a-δ )).

W * ( f,

The well group of a level set

We now establish a close relation between a well group and the level set reconstruction problem: The second and forth terms in the formula of Theorem 4 4 vanish. To see this, note that t ± δ ∈ int(im f ) implies F ≤b±δ = F ≤t+ ±δ S n for small enough, and thus β n (F ≤b±δ ) = 0. Similarly, F ≥a±δ = F ≥t-±δ ∅ and thus β 0 (S n , F ≥a±δ ) = 0. Moreover, β d (S n ) = 0 for d {0, n}. Since the induced homomorphism H * ((F ≤b±δ , ∅) → (S n , F ≥a±δ )) factors as H * (F ≤b±δ ) → H * (S n ) → H * (S n , F ≥a±δ ), we have β((F ≤b±δ , ∅) → (S n , F ≥a±δ )) = 0.

Finally, by the duality theorem of extended persistence [9 9], we can rewrite the third term as

β d ((S n , F ≥a+δ ) → (S n , F ≥a-δ )) = β n-d (F ≤a-δ → F ≤a+δ ).
This yields rank W * ( f, t, δ) = β(F ≤t-δ → F ≤t+δ ) + β(F <t-δ → F <t+δ ).

Together with Theorem 3 3, we have: Corollary 4. The well group realization problem is NP-complete: Given a piecewise linear function f : |K| ⊆ S 3 → R and parameters t and δ, decide whether the well group W * ( f, t, δ) can be realized.

Inria

Figure 2 :

 2 Figure 2: Variable (left) and clause (right) gadgets for the reduction of homological reconstruction to 3-SAT.

Figure 3 :

 3 Figure 3: Embedding of the clause gadget with aligned hemispheres (top), and the simplicial pair (K Φ , L Φ ) generated in the reduction from the 3SAT instance (¬t ∧ u ∧ v) ∨ (t ∧ ¬v ∧ ¬w) ∨ (¬u ∧ ¬v ∧ w) (bottom left), with projection orthogonal to one of the coordinate axes (bottom right).

  (a) (|K|, |L|) has a reconstruction; (b) there exists a subcomplex X ⊂ K such that |X| is a reconstruction of (|K|, |L|); (c) f has a simplexwise linear sublevel set (0, 1)-reconstruction g. (d) f has a sublevel set (0, 1)-reconstruction g. First, (a) =⇒ (b) follows from Lemmas 2 2 and 3 3. To show (b) =⇒ (c), we define a simplexwise linear function g on | sd K| by its values on the vertices of sd K (the simplices of K):

  [a, b], δ) = im H * (F [a-δ,b-δ] → F [a-δ,b+δ] ) ∩ im H * (F [a+δ,b+δ] → F [a-δ,b+δ] ).The following formula expresses the rank of the well group in terms of persistent Betti numbers.Theorem 4 ([4 4]). Let f : K → R be a piecewise linear function and let a ≤ b and δ ∈ R be such that a ± δ, b ± δ are regular values of f . Thenrank W * ( f, [a, b], δ) = β(F ≤b-δ → F ≤b+δ ) β((F ≤b-δ , ∅) → (K, F ≥a+δ ))

Theorem 5 .

 5 Let f be a piecewise linear function on S n with t ± δ ∈ int(im f ). A piecewise linear function g realizes the well group W * ( f, t, δ) if and only if it is a level set (t, δ)-reconstruction of f . Proof. For every s ∈ R, there is > 0 such that all values in [s -, s) and in (s, s + ] are regular, and hence H * (F ≤s-) H * (F <s ) and H * (F ≤s+ ) H * (F ≤s ). Moreover, W * ( f, s, δ) W * ( f, [s -, s + ], δ). Choose such that the above holds for s = t ± δ. Let a = tand b = t + . Now a ± δ, b ± δ are regular values and we can apply Theorem 4 4.

RR n°8169

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgements This work was initiated during the 10 th McGill-INRIA Workshop on Computational Geometry at the Bellairs Research Institute. The authors wish to thank all the participants for creating a pleasant and stimulating atmosphere, in particular Nina Amenta for discussions leading to a first version of Theorem 1 1.

Proof. By exactness of the Mayer-Vietoris sequence [19 19, §4.6] for S n , F ≤t , and F ≥t , we have [12 12]

By Alexander duality [15 15, §3.3] and the duality of homology and cohomology with field coefficients [15 15, §3.1], we have

where H d denotes the dth reduced homology group. Recall that

We thus have

By combining Eqs. (3 3) and (4 4), we obtain the stated equality.

For all f, g with gf ∞ ≤ δ and t ± δ ∈ int(im f ) we have t ∈ int(im g) and thus by Lemmas 1 1 and 5 5

. This motivates the following definition: Definition 3 (Level set reconstruction). Let f , g be piecewise linear functions on S n and consider real parameters t and δ with t ± δ ∈ int(im f ). The function g is called a level set (t, δ)-

A level set (t, δ)-reconstruction is thus also a minimizer of β(G ≤t ).

NP-completeness of level set reconstruction

Definition 4. Let f be a piecewise linear function. A homological regular value of f is a number t ∈ R such that H * (F <t → F ≤t ) is an isomorphism.

We remark that for piecewise linear functions, this definition is equivalent to the one given in [8 8]. Lemma 6. Let f be a piecewise linear function on S n , n > 1. If t ± δ ∈ int(im f ) are regular values of f and g is a level set (t, δ)-reconstruction of f , then t is a regular value of g. Proof. By hypothesis t ± δ are regular values of f and hence

Since g is a level set reconstruction, by Lemma 5 5 we have

It follows that β(G <t ) = β(G ≤t ) = β(F ≤t-δ → F ≤t+δ ). Since

we conclude that H * (G <t → G ≤t ) is an isomorphism. Inria