Pierre-Yves Koenig
email: pierre-yves.koenig@labri.fr

Faraz Zaidi
email: faraz.zaidi@labri.fr

Daniel Archambault
email: daniel.archambault@inria.fr

Interactive Searching and Visualization of Patterns in Attributed Graphs

Keywords: H, 5, 0 [Information Systems]: Information Interfaces and Presentation-General G, 2, 2 [Mathematics of Computing]: Discrete Mathematics-Graph Algorithms

Searching for patterns in graphs and visualizing the search results is an active area of research with numerous applications. With the continual growth of database size, querying these databases often results in multiple solutions. Text-based systems present search results as a list, and going over all solutions can be tedious. In this paper, we present an interactive visualization system that helps users find patterns in graphs and visualizes the search results. The user draws a source pattern and labels it with attributes. Based on these attributes and connectivity constraints, simplified subgraphs are generated, containing all the possible solutions. The system is quite generic and capable of searching patterns and approximate solutions in a variety of data sets.

INTRODUCTION

The problem of searching information in databases has been addressed by many researchers. Representing these search results in a compact form is an important area of research. In case where the query is not precise and an approximate solution is required, the number of solutions returned can be large. Using traditional List-based Result Visualization systems can hinder the efficiency of choosing an appropriate solution. As an alternative to the listbased systems, another way to represent solutions is to use a graphical representation of the search results. As argued by North and North [START_REF] North | An information exploration and visualization approach for direct manipulation of databases[END_REF], a visualization system can facilitate and empower users to perform more complex information retrieval tasks. Moreover, many real world systems can be modeled as graphs, for example, Social Networks [START_REF] Wasserman | Social Network Analysis: Methods and Applications[END_REF], Metabolic Networks [START_REF] Jeong | Largescale organization of metabolic networks[END_REF], and Transport Networks [START_REF] Rozenblat | Continental integration in multilevel approach of world air transportation[END_REF]. A more natural way to search for information in these networks is to draw a pattern where the drawing corresponds directly to the query.

Several approaches exist to search for information in these networks. The most common is through a database query language. As an example, consider an airline network, where the nodes of the graph are airports and edges represent direct flights [START_REF] Rozenblat | Continental integration in multilevel approach of world air transportation[END_REF]. This graph can have multiple edges where an edge represents a unique flight on a particular date and time. Attributes are associated with the nodes and edges of the graph and could include information such as airline, flight date, departure time, flight duration, and the cost of the ticket. Attributes associated to nodes of the graph could include country and region. The attribute region represents the subcontinents like eastern and western Europe.

A simple query on this database would be to look for all the flights possible from some city to another, say, Bordeaux to Milano. The user might choose to take indirect flights with not more than one stop over. Generating this query is quite simple and the results can easily be analyzed by a list-based system. On the other hand, if the user is a tourist, who wants to plan a trip to Europe and visit its important cities, the user might ask a question such as: Starting from Bordeaux, find me a tour of four European cities such that the trip lasts two weeks, a stop in Milano to visit a relative on a particular date, and the return flight brings me back to Bordeaux. The table of possible search results can be very large and writing such a query can be quite cumbersome. Figure 1 represents such a graphical pattern where nodes represent airports, and the label Europe is associated to each airport as an attribute of the node. The problem can also be modeled as a subgraph isomorphism [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF] problem. The goal is to search for a graph G 1 in a larger graph G 2 such that there exists a bijection between the vertex set of G 1 and G 2 . Although subgraph isomorphism is known to be NP-Complete [START_REF] Cook | The complexity of theorem-proving procedures[END_REF], algorithms exist to solve it in a reasonable amount of time on real world graphs with attributes [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. The strict definition of subgraph isomorphism requires that all edges be present in the mapping of vertex set of G 1 to vertex set of G 2 . Some researchers, however, relax this constraint. The goal of this inexact matching problem [START_REF] Shapiro | Structural descriptions and inexact matching[END_REF] becomes to find a graph that more or less matches the input graph. Moreover, due to the widespread use of graphs as models for representing data, the inexact graph matching problem has attracted lots of research activity [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF].

Another approach to solve this problem is to model it as a constraint satisfaction problems(CSP) [START_REF] Rudolf | Utilizing constraint satisfaction techniques for efficient graph pattern matching[END_REF][START_REF] Larrosa | Constraint satisfaction algorithms for graph pattern matching[END_REF]. Given a set of variables, a finite domain for each variable, and a set of constraints, CSP problems aim to find an assignment of values to the variables from the domain such that the assignment satisfies all the constraints. The graph matching problems has an analogy to CSP problems. The set of variables in CSPs can be considered as the nodes and edges in the graph along with their attributes. The constraints can be translated as restrictions on these nodes and edges. So, for example, a node of G 1 can be represented as a variable, the nodes in G 2 as the domain, and the connectivity between nodes in G 1 as restrictions applied to the variables.

Regardless of the search method used to solve the search problem, our focus is the formulation of the query and representation of the solutions. Instead of finding and enumerating all approximate isomorphisms, which can be costly, we present a visualization of simplified areas of the large graph that contains all of these inexact matches. The algorithm takes as input a graph pattern drawn manually by the user containing optional and required edges. The only restrictions we impose on this pattern is that the nodes must be a single, connected component after all optional edges are removed. Our system presents all solutions in a series of subgraph visualizations where the user can easily browse the different possible solutions to pick the most suitable.

Our primary contribution is an interactive system that can be used to help solve this inexact graph matching problem. Secondly, our system maps attributes using spatial position, color, and shape to reduce visual complexity and facilitate the reading of patterns in the graph. Finally, our interactive system does not enumerate over all patterns found in the graph or attempt to find a globally minimal solution. Instead, it presents the set of solutions in an interactive system that can be browsed and modified manually, thus reducing the overall execution time of the search process. Note that a database query might execute faster to return the search results but browsing hundreds of records can be difficult. Currently, the system is implemented as a set of searching algorithms on a graph, but the search process could be replaced by a database query to decrease query time. This approach remains out of scope of this paper as generating database queries from visual interfaces has been addressed by other researchers such as Madurapperuma et al [START_REF] Madurapperuma | Customisable visual query interface to a heterogeneous database environment: A meta-programming based approach[END_REF].

The next section contains the related work. In section 3, we formalize the problem and explain the different types of attributes and constraints. Section 4 presents the proposed system. Finally, we present different case studies in section 5 to show the effectiveness of the proposed system.

PREVIOUS AND RELATED WORK

Related work can be classified into four areas. Pattern recognition places an emphasis on subgraph topology while CSP problems place an emphasis on graph attributes. Research has also been undertaken in the visual analytics and the graph drawing community to help illustrate patterns in the context of graphs. Finally, some work has also been done on visual query interfaces for databases.

Pattern Recognition

Pattern recognition algorithms for inexact matching find solutions that are global minima, but they suffer from high computational requirements [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. Most of the algorithms are designed to calculate the matching cost on an explicit model of errors. These errors could be, for example, missing nodes or edges in the suggested solution. These models do not incorporate optional edges. Thus, allowing an indirect flight as an optional path to connect to a destination node even though a direct flight exists, would be difficult to input in this type of system.

Another approach to defining a matching cost is to use a set of graph edit operations, such as node insertion, and assign costs to each operation. The goal is to find the cheapest sequence of operations to match an input pattern [START_REF] Gao | A survey of graph edit distance[END_REF]. These methods require a cost function for optional edges, which may vary between problems and users. For example, a user may prefer direct flights. Thus, high costs would be associated with indirect flights. On the other hand, a user may want to spend less money, even if the stop over of a connection is very long.

The objective of our system is the same as a pattern recognition algorithm with the exception that optional edges are allowed. Additionally, we do not attempt to find a single optimal solution, but several solutions which can be browsed by a user through a visualization system. As we do not attempt to compute this optimal solution, we gain in terms of time complexity over these types of approaches. However, the essence of our approach shares many commonalities with approaches in this research area. Our system uses attributes and connectivity constraints to reduce the set of possible solutions. Since we have several attributes that can be defined on the graph, either locally on particular nodes/edges or on the position of the node in the target graph, we use them to eliminate nodes or edges from the set of possible solutions.

Constraint Satisfaction Problems

Another way to solve the given problem is through CSP approaches. The classical method for solving CSP problems is backtracking [START_REF] Kumar | Algorithms for constraint-satisfaction problems: A survey[END_REF]. This class of methods performs a depth-first search of the space of potential CSP solutions [START_REF] Shapiro | Encyclopedia of Artificial Intelligence[END_REF]. Despite the wide use of these methods, the time complexity for most nontrivial problems is exponential. Moreover, if CSP approaches are to be adapted to search for patterns in graphs, the node connectivity needs to be modeled as a constraint on pairs of nodes, further increasing the complexity of the backtracking method. Techniques such as arc consistency [START_REF] Mackworth | Consistency in networks of relations[END_REF] and k consistency [START_REF] Freuder | Backtrack-free and backtrack-bounded search[END_REF] can be used to reduce the number of solutions that these backtracking methods explore. However, the methods still remain computationally expensive.

These methods can be used to produce an optimal solution, subject to the constraints imposed by the user. However, mapping constraints to the edges that connect pairs of nodes in a graph is cumbersome, because each constraint must be declared separately for each attribute. As we do not attempt to find a globally minimal solution, our approach offers reduced computational complexity. Instead, the user can browse the solution space to select one or more inexact matches that conform to their needs.

Graph Pattern Visualization and Interactive Graph Mining

Research in the domain of interactive and visual graph mining is attracting lots of interest as data sets are rapidly growing in size. Systems like [START_REF] Rodrigues | GMine: A system for scalable, interactive graph visualization and mining[END_REF][START_REF] Singh | Visual mining of multimodal social networks at different abstraction levels[END_REF][START_REF] Simoff | Visual Data Mining -Theory, Techniques and Tools for Visual Analytics[END_REF] help users to visualize large size graphs, organize these graphs, and interact with them for mining purposes. These systems are not designed to address the inexact graph matching problem, and, thus, would require some customization to present solutions to these problems.

A number of contests have focused on the problem of finding graph patterns in a larger graph. The 2003 Graph Drawing Contest [START_REF] Brandenburg | Graph drawing contest report[END_REF] focused on how to display a smaller subgraph pattern, or graph motif, in the context of a larger graph. Two systems, both of which are described below, claimed a prize in the contest.

Holleis et al. [START_REF] Holleis | Drawing graphs within graphs: A contribution to the graph drawing contest 2003[END_REF] creates what they call a summary graph, similar to a quotient graph in the graph drawing and visualization literature, that presents the patterns found and their interconnections. Their system places each pattern found into its own node of the summary graph. Two nodes of the summary graph are connected if the patterns are connected. Each found pattern and the summary graph is drawn independently, presenting an overview of the motifs and how they are interrelated.

Klukas et al. [START_REF] Klukas | Graph pattern analysis with PatternGravisto[END_REF] describe an interactive system where the user draws a small graph pattern on a panel to the right of the screen. The pattern is found in the larger target graph and emphasized in context using spatial position and color. The emphasis via spatial position is accomplished through a modified force-directed algorithm.

In this contest, the example graphs were quite small, consisting of a few hundred nodes and edges. Additionally, the nodes and edges had relatively few attributes, consisting of one or two pieces of information at most. Our system differs from the solutions presented above, as we consider larger graphs with more attributes. Thus, showing context is more complicated without greater levels of simplification to the large graph. Additionally, we focus on approximate matching of edges attributing them as optional or required to handle the inexact graph matching problem.

The Social Network and Geospatial Challenge of the 2009 VAST Challenge [START_REF] Grinstein | The 2009 VAST challenge[END_REF] focused on finding a small pattern representing the communication between actors in an espionage organization in a larger graph. The fictitious scenario involved confirming a pattern of communication between the actors in the organization. These actors communicated using a social networking tool named Flitter. Many solutions to this task were submitted, including ours [START_REF] Simonetto | Solving the traffic and flitter challenges with tulip[END_REF], but most of these systems were tailored directly to the problem posed by the challenge committee and were not general systems. Also, attributes beyond topological information, such as geospatial constraints, were not really considered when finding the pattern. It was only afterward, when multiple solutions were found, that these constraints were applied by the participants as a post-process to filter the solution set.

Interactive Visual Query Generation

Research in the domain of generating queries for databases through visual interfaces has interested many researchers. The most important reason being that visual interfaces seem to be a more natural way for humans to query databases as compared to using some query language. The readers are recommended to refer to several papers on the topic [START_REF] Li | IFQ: A visual query interface for object-based image retrieval[END_REF][START_REF] Lin | Pic1: A visual database interface[END_REF][START_REF] Madurapperuma | A visual query interface for a customisable schema visualisation system[END_REF][START_REF] Madurapperuma | Customisable visual query interface to a heterogeneous database environment: A meta-programming based approach[END_REF] for further information. However, these papers generally do not focus on searching for approximate patterns in graphs.

PROBLEM FORMALIZATION

The input to the visualization system consists of two graphs. The source graph, G s = (N s , E s ), is the graph pattern sought by the user. The target graph, G t = (N t , E t ), is the graph in which the source graph will be found. Both the source and target graphs can be modeled as G = (N, E, A) consisting of:

• a finite set of nodes N.

• a finite set of edges E ⊆ N × N with loops and multiple edges.

• a finite set of attributes A associated with N and E, having a finite set of domain.

The source graph has an additional parameter T :

• type T , for each edge, which can take boolean values representing if the object is required or optional.

Required of the source graph are nodes and edges that must appear in the pattern. Optional edges of the source graph may be present in a solution, but do not eliminate the solution as a candidate. Any edge that is not present in G s may be present in G t , but it is filtered out by the system when presenting solutions. In our system, the sets T and A apply locally on the source graph. Each attribute value represents a unary constraint on either a node or an edge. As an example, in Figure 1, a node of the pattern must have the value Bordeaux (departure and arrival node). In our approach, we constrain our source graphs to consist of a single, connected component using only the elements of T labeled Required.

PROPOSED SYSTEM

The proposed system comprises of four steps as shown in Figure 2.

Each of these steps is explained in detail in the following sections.

Interactive Query Generator

The interactive query generator serves three main purposes. The first purpose is to enable the user to generate queries through a visual interface. The idea is to let the user draw a pattern of nodes and edges annotated with attributes. The second purpose is to allow the user to specify a visual encoding of attributes on nodes (like geographical position mapped to color) and the desired layout (position of nodes on the screen to create a mental map). This visual encoding is used to display various search results that can be further explored by the user. The third objective is the automatic extraction of node-connectivity constraints to determine how the nodes must be connected to each other defining the pattern to be searched. These constraints eventually help to reduce the number of candidate solutions of a given pattern.

The interactive query generator is a graph drawing tool, actually the Tulip software interface [START_REF] Auber | Tulip -a huge graph visualization framework[END_REF], allowing the user to draw a pattern. The user can further assign desired attribute values to the nodes and the edges. The interface of the query generator is shown in Figure 3. The visual encoding includes shape, position, and color and is used when presenting different possible solutions to the user. The next step is to extract constraints from the graph. We define two types of constraints on N and E of graph G s : connectivity constraints and attribute constraints. Connectivity constraints are imposed by the edges of source graph where they define how the nodes of this source graph must be connected to each other. For example, looking for an edge between two nodes is an example of a connectivity constraint. In the air traffic network, this edge might be a constraint that a direct flight must exist between two cities for the solution to be considered. Attribute constraints are the conditions defined on either edges or on nodes of G s . An attribute is required to have a certain value or be within a range of values. Continuing with our airport example, possible attributes for nodes are the city names, chosen as departure and arrival cities or ticket fares associated to edges representing particular flights. Connectivity and attribute constraints play an important role in reducing the number of possible solutions. The next section presents how our algorithm uses this information to find candidate solutions.

Constructing and Filtering Candidate Sets

Our solution involves creating a set of possible candidates for each node of the source graph, and then iteratively removing elements from these sets based on connectivity and attribute constraints. The interactive query generator. The interactive query generator is a graph drawing tool, actually the Tulip software interface [START_REF] Auber | Tulip -a huge graph visualization framework[END_REF], that allows the user to draw the pattern. The tool allows the user to specify node shapes, colors, and positions manually. These nodes are the nodes of G s , and the visual attributes assigned here will be used in the presentation of the solutions as described in section 4.3

Constructing Node Candidate Sets

In the first step of the algorithm, for each node in G s , we construct a set of candidate nodes from G t that fulfill all the attribute constraints of that particular node in G s . For example, as shown in Figure 1, the node labeled Bordeaux represents an attribute constraint where the nodes label should be Bordeaux. While constructing the candidate set for this node, only the nodes having this label will be retained. In this case, the airport labeled Bordeaux will be the only node in the first candidate set. Similarly, the candidate set for the node labeled Milano will contain only one node. The candidate sets for nodes labeled 1,2,3 will contain airports from the region Europe as in the given example, and this region constraint is the only attribute specified by the user for the nodes. Initializing the candidate sets requires O(|A||N s ||N t |) time in the worst case, as we need to check to see if every element of N t belongs to one of the candidate sets of N s and A is the number of attributes associated to node and/or edges. As |A| and |N s | are usually small, this step of the algorithm is fairly efficient.

Finding Patterns from S

The next step is to iteratively eliminate nodes from these candidate sets based on connectivity constraints. First we find a minimum spanning tree using Prim's algorithm from G s , considering only the nodes and edges attributed as required. As G S is constructed using only required edges, there must exist at least a spanning tree of G s composed entirely of required elements, which we call RT . In the tour example, RT would be a pass of the cycle. Continuing with the European tour example, the nodes and edges are required in this example. But it may be the case that the user might need to cut their trip short after Milano due to financial constraints. In this case, they might also be interested in return flights from Milano directly to Bordeaux. The edge representing this flight is an optional edge as the pattern searched does not necessarily require this edge, but the edge brings additional information to the user which might be useful. This optional edge would never be present in RT .

we select the candidate set with the smallest cardinality and call this set S, which in our current example, can be either Bordeaux or Milano as the candidate sets of both these nodes contain exactly one element. For each node in the smallest candidate set, we construct a subgraph as described below.

Starting from the root of RT , we perform a breadth-first search in G t to find all possible instances of RT . From each element of S, we look at the adjacent neighboring vertices in G s . All nodes that are part of a candidate set directly adjacent to a node in S are added to the subgraph associated with the node in S. We repeat the process for all the other nodes of RT . In the current example, if we start with the candidate set for the node Bordeaux, we look at the nodes adjacent to Bordeaux in the candidate set of node 1 (see Figure 7). The nodes that are not directly connected to Bordeaux, are removed from the candidate set of node 1. We continue for all nodes in the order defined by RT .

While considering the connectivity of nodes, we filter out edges that violate any attribute specified by the user on the edges. For example, if the user does not want to take a flight that costs more than some specified amount of money, the edge will not be considered. Returning to the example, when we look for nodes directly connected to Bordeaux in the candidate set of node 1, we only consider the edges that conform to all the attributes associated with the edges of G s .

As a result of this step, we obtain a subgraph of G t as shown in Figure 8. In this subgraph, for each node in G s , we have identified the possible candidate nodes from G t . A number of solutions can be extracted from this subgraph as all the possible routes are presented to the user. Recall that if the cardinality of set S is more than 1, we will obtain several subgraphs, each representing a set of possible solutions. The number of subgraphs generated for the three different data sets are mentioned in Figure 13

Filtering Solutions and Node Splitting

Once we obtain subgraphs containing sets of possible solutions, we filter by local connectivity and attribute constraints. For example, each node in Figure 7 It is possible to have a single node belonging to candidate sets of more than one node. An example is the city of Paris and Dublin in Figure 8 as both of them are connected to Bordeaux and are present in candidate sets 1 and 2. To handle the nodes that belong to more than one candidate set, we split the nodes such that we make multiple copies of the node. As a result of this step, each node belongs to a single candidate set. Splitting allows us to place nodes of the graph into multiple candidate sets. These candidate sets will be represented as metanodes, during candidate layout.

Candidate Layout

As mentioned previously, we do not iterate over all solutions to the subgraph isomorphism problem. Rather, we present a visualization where many solutions that originate from a single element of S can be visualized simultaneously. In order to facilitate visualization, we map the candidate sets to a layout that resembles the user generated input layout of G s . As an example, in Figure 4, all nodes of graph in Figure 4(a) are mapped to the layout in Figure 4(b) giving a final layout presented in Figure 4(c).

For each candidate set, we create a metanode. The diameter of this metanode is proportional to the number of elements present in its candidate set. We map the position of each metanode in this metagraph to the position of its corresponding node in G s that was determined by the user. The layout of this metagraph is uniformly scaled by a factor equal to the largest metanode diameter radius. Subsequently, we apply the algorithm of Dwyer et al [START_REF] Dwyer | Fast node overlap removal[END_REF] to ensure that no two metanodes overlap.

The algorithm places each node of the candidate set on the diameter of the metanode created in the previous step. Candidate edges span the gaps between metanodes. As we are free to choose the orientation of this diameter, we choose a line , as shown in Figure 5 and defined by the following equation:

= p + tv ⊥ ave (1)
where p is the position of the metanode and t is a scalar value. The vector v ⊥ ave is the vector perpendicular to v ave vector v ave is the average of the vectors between adjacent metanodes and the current one.

It can happen that |v ave | is zero. Figure 6 shows a typical case: v 1 is directly opposite to v 2 . We resolve this problem by simultaneously computing v ave : the average vector, but with a 180 degree rotation for any vector with a negative x-component. Let us denote this series of vectors v 1 . . . v n . Therefore, we are guaranteed that |v ave | is non-zero as all x-components are positive. Also, the orientation of v 1 is equally as good as v 1 this case, because it does not matter from which side of the row edges attach themselves. If v ave on average, more orthogonal to the vectors v 1 . . . v n , it is chosen instead of v ave for which occurs when:

n ∑ i=1 |v i • v ave | < n ∑ i=1 |v i • v ave | (2)
In this equation, all vectors of v 1 . . . v n along with the vectors v ave and v ave have been normalized.

When drawing the source graph, the user of the system can specify the color and shape of the nodes. Once the layout has been determined, polygons are added to the background of the layout for each candidate set. The shape and color of these polygons match The line is to be as perpendicular as possible to all incident edges from other metanodes in the drawing.

v 1 v 2 v 1
Figure 6: Incidents where |v ave | can be zero. In this case, many of the unit vectors are directly opposing vectors. We compute the mirror image of all vectors with a negative x-component as we do here for v 1 . The average of these vectors is non-zero since all x-components are positive. Also, the orientation is equally as good because it does not matter if edges from adjacent metanodes attach to nodes on the diameter from the left or right side of the line .

those chosen by the user as seen in Figure 4. The layout algorithm described above specifies the size and positions of these nodes.

CASE STUDIES

We present three case studies on different data sets. The layout algorithm, presented in section 4.3, places candidate nodes along diameters of circles positioned as close as possible to the input layout specified by the user. Also, the shape of the nodes is changed so that it has the same color and shape of the node in G s , allowcandidate sets to be identified. Only the edges that satisfy all edge constraints are drawn, and these edges span the space between metanodes. Figure 13 presents information about the data used and the execution of our algorithm. All of the case studies were executed on a 2.16GHz dual core Pentium IV with 2.0GB of memory, running Fedora Core 8 with a 2.6.26.8-57 kernel.

Airline

The air traffic network is a directed and highly multi-edge graph consisting of individual flights between cities in Europe. As there exists one edge per flight between two cities, many multiple edges can exist between two nodes. We have many attributes on the nodes and edges of this graph, including the departure and arrival time of the flight and the servicing airline company.

On this data set, we explore a number of possible tours around Europe. For example, tourists who want to visit important European cities in a limited time. Thus, they may be looking for a loop that connects several touristic cities, subject to some constraints. Maybe they need to visit a relative in Milano on a particular day. They may like to take a certain airline on some flights to maximize frequent flyer points. Additionally, they have constraints on departure and arrival times from their base city.

Our source graph, in this example, is a directed cycle of five nodes as shown in Figure 7. The data set does not have any dates so we assume that all flights are available on all days. The trip begins at Bordeaux where the first flight must take off after 9:35 in the morning. The destination of this flight, the green node at the top of the diagram, is unconstrained. On the next day, from the green node, we fly to Milano, the yellow hexagon in the diagram. We visit our relative for two days, and our third flight leaves after 21:00 to an unconstrained destination. Our fourth flight is to an unconstrained destination in Europe. Finally, the last flight is constrained to land at Bordeaux before 20:31, so that we are able to get back home before midnight. The first and last flight of our trip is constrained to be with a particular carrier, to earn some frequent flyer miles.

In Figure 8, we show the result of Airline. As we constrain the first node of the cycle to leave from Bordeaux, we only have a single candidate for this node. This situation is exactly the same for Milano. The leg of our trip can take us to a variety of cities, as shown in the upper, green node, including Porto, Dublin, and Barcelona. From each of these cities, we have a variety of flights to Milano. Destinations for the third city on our tour include Lisboa, Firenze, and Amsterdam. Then we have our fourth city followed by a flight home. These unconstrained airports contain ten and fifteen cities respectively. In many cases, the graph is constrained enough so that we can follow the individual cycles. Although edge occlusion does occur between the fourth and fifth cities of our trip, most the cycles are relatively easily read through visual inspection of the diagram.

Vast

In the 2009 VAST Challenge [START_REF] Grinstein | The 2009 VAST challenge[END_REF], contestants were asked to find a pattern in a large graph, subject to a variety of constraints. The nodes of this graph are users of Flitter, a fictitious social networking program, and edges exist between nodes if they communicate. The graph is simple and undirected. Once the contest was over, the ground truth was known, but the initial task was to find this solution based on the indices provided by the contest organizers.

In the given scenario, an employee leaked sensitive information from an embassy. In order to protect the identity of the employee's fearless leader, the information was redirected twice. The first level of indirection is through three handlers while the second level is through one or three middlemen. Figure 9 shows the pattern of communication with three middlemen.

The light brown box in the diagram is the employee. The employee communicates with three handlers which are the green circles. Each handler has a middleman, the light blue triangles. Finally, all three middleman connect to a fearless leader, the purple pentagon. Employees are constrained to have a degree between thirty-five and forty-five in G t . Handlers have a degree between twenty-seven and forty-three. The middleman has a degree of between zero and seven. Finally, the fearless leader has a degree greater one hundred. Geospatial constraints dictate that the fearless leader has to reside in the city Koul and the employee in Prouvnov.

The system returns nine subgraphs in total. Four of these subgraphs contain valid solutions and the remaining five are empty subgraphs because filtering eliminated all solutions. Figure 10 shows the solution many teams found in the contest. The algorithm started its traces into G t from the fearless leader @irvin. On the other side of the diagram, three possible candidates exist the employee @faradzev, @terekhov, and @usdin. These three candidates could communicate with eight possible handlers in the green circles. As all three handlers have identical constraints, each circle contains the same candidates. Finally, the handlers can communicate with seven different middlemen contained in the light blue triangles. All of these middlemen communicate with @irvin. Using this diagram, we can apply less precise constraints, such as a middleman must be located nearby the city of the fearless leader, to refine the solutions as given in the problem statement of the contest.

Movie

Movie is derived from the 2007 InfoVis Contest data set [START_REF] Kosara | IEEE InfoVis 2007 Contest: InfoVis goes to the movies[END_REF].

set consists of a list of movies, containing information such as the actors list, director, title, any Oscars won, and other information. From this data, we constructed an undirected, bipartite graph without multi-edges. Nodes in this graph are actors, directors, or movies. Movies are linked only to actors or directors and vice versa.

In Movie database, we test a theory about rising stars. In this theory, we have a famous actor, who has acted in many movies and won at least one Oscar. The actor works with a prolific director on at least one film. In this film, there are many actors who have acted in very few movies, but will get exposure from this work. A famous actor works on at least ten movies and has won at least one Oscar. A prolific director must have directed at least four movies. Movies are completely unconstrained. Rising stars have acted in at least two movies and at most five. In our query graph, Figure 11, the light blue pentagon is the famous actor and the green hexagon is the prolific director. The purple circle is a common, unconstrained movie between the two. Finally, the red pentagon is the rising star.

The query returns twenty-four subgraphs. Two are empty due to constraint filtering. Thus, twenty-two subgraphs contain at least one solution. In Figure 12, we show a solution. Here, Morgan Freeman is the famous actor. He worked on many films one of which was Million Dollar Baby with Clint Eastwood a director. Many actors and actresses may have gained exposure from working on this movie. This data set suggests that Brian F. O'Byrne and Jay Baruchel are two such actors. Two other projects with Morgan Freeman create other solutions in this data set.

DISCUSSION

Our approach seems to be fairly generic and works on a very wide range of data, as seen through our case studies in section 5. The system is able to visualize simple and multi-edge, directed and undirected, as well as attributed and weighted graphs. Also, as seen in Figure 13, the approach executes in less than twenty seconds for our case studies on a standard machine.

The approach proposed in the system seems to have good performance on some simple and interesting patterns. In our examples, the average number of times the constraint application loop was executed, loop in Figure 13, was at most 4. This value is quite far from the possible |N| 2 iterations that could take place. Additionally, |S| and the average number of nodes and edges in the subgraphs are relatively small as attribute filtering helped significantly. Also, it should be possible to use a database as a back end for our visualization system, which could increase searching speed. However, it is important to note that even if our problem requires a solution to subgraph isomorphism to be solved, we remain polynomial as we do not iterate over all patterns, but present them in a visualization.

Although not enumerating the patterns in the graph has the advantage of time complexity, if many solutions exist, visual clutter can occur. A good example is present in Figure 8 where two unconstrained sets of cities are linked at the bottom of the diagram. Currently, the system constraints state that there must exist a spanning tree of required edges. This spanning tree cannot allow for the choice of two or more alternative paths to reach a node. Our search algorithm is currently subject to this constraint, but our visualization algorithm would be able to handle results from this case. Further work would be required to address this limitation.

The system in its current state has some obvious limitations. The most important one is its scalability as the number of solutions increase, visualizing all of them at the same time becomes difficult. As shown in Figure 13, the Movie data set contains a large number of nodes and edges. Even though the source graph has only four nodes and three edges, the resultant graph can be large (Figure 12). As mentioned earlier, there exists an inverse relationship between the amount of information input to the system to the amount of information returned as a result. The more constraints we associate with the source graph, the more focused would be the search results and thus would be easier to visualize.

FUTURE WORK AND CONCLUSION

In this paper, we have presented a system to find and understand patterns in graphs. One of the strengths of the system is that it presents solutions to an inexact matching of a pattern where edges can be optional or required. The mapping of attributes to layout and color help reduce the visual complexity of the presented solutions. Finally, we provide an interactive system that allows users to explore sets of matches to a particular pattern and modify them manually. As a result, even when the source and target pairing approaches unconstrained subgraph isomorphism, our system is polynomial, because we do not iterate over the solutions to the problem. Rather, a visualization is used because humans can recognize patterns efficiently [START_REF] Ware | Information Visualization: Perception for Design[END_REF]. In future work, we would like to improve the performance of the filtering algorithms as we believe that the complexity can be reduced significantly. Also, it would be interesting to look at ways of reducing visual clutter of the edges present in our solution as in our constrained layout case, it may be possible to be more efficient. Several algorithms exist to reduce edge crossings, a few directly applicable approaches are discussed in Bauer and Brandes [START_REF] Baur | Multi-circular layout of micro/macro graphs[END_REF], and would remain an important topic for future work. Finally, formal user experimentation and testing, especially in terms of interactivity, would be needed to validate the approach.

Result

Figure 1 :

 1 Figure 1: Pattern for European Tour of four cities from Bordeaux and visiting Milano. Nodes are numerically labeled for reference.

Figure 2 :

 2 Figure2: Block diagram of the proposed system. The interactive query allows the user of the system to draw the source graph. Candidate set construction finds potential candidates in the target graph. Candidate layout draws the collection of solutions in a way that accentuates structures similar to the drawn source graphs and maps visual attributes. Finally, the solutions are presented to the user and they can be edited manually using the Tulip interface.

Figure 3 :

 3 Figure3: The interactive query generator. The interactive query generator is a graph drawing tool, actually the Tulip software interface[START_REF] Auber | Tulip -a huge graph visualization framework[END_REF], that allows the user to draw the pattern. The tool allows the user to specify node shapes, colors, and positions manually. These nodes are the nodes of G s , and the visual attributes assigned here will be used in the presentation of the solutions as described in section 4.3

Figure 4 :

 4 Figure 4: Mapping the graph to the user-created layout and encoding of G s to the candidates found by the system. (a) An example graph where nodes have been associated to several candidate sets. (b) The candidate graph drawn by the user. (c) Candidate graph mapped to the layout of G s . The shape and color of the nodes of G s are mapped to polygons situated behind the sets of nodes for easy identification

Figure 5 :

 5 Figure 5: Diagram showing how the diameter, where the nodes of a particular candidate set are placed, is chosen. All vectors to adjacent nodes are averaged to produce an average vector v ave . In this case, those vectors are v 1 , v 2 , and v 3 . The perpendicular to this vector is v ⊥ave . The point p, the position of the metanode, and v ⊥ ave are used to define the line which is the diameter on which the nodes are placed. The line is to be as perpendicular as possible to all incident edges from other metanodes in the drawing.

Figure 7 :

 7 Figure 7: G s for Airline where the user is looking for touristic cities in Europe and wants to pass through Milano to visit a relative.

Figure 8 :

 8 Figure 8: Results of the possible touristic destinations in Europe starting from, and returning to Bordeaux.

Figure 9 :

 9 Figure 9: G s for the Vast Challenge where the objective is find a similar pattern in the data set.

Figure 10 :

 10 Figure 10: One of the 9 possible subgraphs found with various possible solutions to the pattern searched for the Vast Challenge.

Figure 11 :

 11 Figure 11: G s for Movie where we want to discover rising stars in cinema.

Figure 12 :

 12 Figure 12: One of the possible 24 subgraphs returned as a result by the search for the Movie pattern where a number of up coming stars can be seen that have performed with famous actors and directors.

  where each subgraph contains several solutions. The breadth-first search of G t is the most expensive step as every node of |N t | can be a part of |N

s | candidate Thus, this step can take O(|S|(|N s ||N t | + |A||E t |)) time.

  As it is possible to remove a constant number of nodes from the candidate sets in each iteration on a particular subgraph, the loop can execute at most O(|N s ||N max |) times. Thus, in the worst case, this step can take O(|S||N s | 2 |N max | 2 + |S||N s | 2 |N max ||A||E max |) time. It is possible that |N t | = |N max |, but this would imply that nearly all nodes in G t are candidates in a subgraph of S, or that hardly any filtering occurred. Frequently, we have observed that |N t | >> |N max |. Also, |S| and |N s | are generally small.

must have at least degree two. Not only do the candidate nodes need this degree, but they also need to be connected to the right two candidate sets of G S . The algorithm begins by computing, for each node in G s , the required connections for all candidate sets. Next, for each node in each subgraph, the algorithm checks that it is adjacent to all sets required by G s . If it is not adjacent, then the node is removed from the candidate set for this subgraph. The process is repeated until no more nodes can be removed.

Let G max = (N max , E max ) be the largest subgraph in S.

  |S| |N max | |E max | |N ave | |E ave | loops time |N t | |E t | |A t | |N s | |E s | |A s | Figure 13: The graphs, queries, and execution time of our algorithm during the case studies. Result is the name of the case study. The values of |N t |, |E t |, and |A t | are the number of nodes, edges, and attributes in the target graph respectively. Similarly, the values |N s |, |E s |, and |A s | are the corresponding values in the source graph. |N max | and |E max | are the maximum number of nodes and edges in any subgraph of the result. |N ave | and |E ave | are the average number of nodes and edges in each subgraph produced by the system. The value of loops corresponds to the average number of times the first step of filtering, described in section 4.2.3, is executed. Time states the running time of the algorithm in seconds from the time the search is launched to computation of the final drawing.

			G t			G s
													sec
	Airline	250	25,953	23	5	5	4	1	41	1,499	41 1,499	2 20.1
	VAST	6, 016	29,888	4	8	9	1	9	57	69	13.8	18.0	4.22 0.82
	Movie Discovery 166,928 226,523	16	4	3	4 24	72	72	33.0	32.9	3 5.47


Benoit Cerutti

Guillaume Dubus

Gilles Henri

Gilles Henri High

S Boissier

M Heydari-Malayeri

R Samadi

D Valls-Gabaud

High-energy radiation from the relativistic jet of Cygnus X-3

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

Cygnus X-3 is an accreting high-mass X-ray binary with relativistic jets, i.e. a microquasar. This system is composed of a Wolf-Rayet star (see e.g. van Kerkwijk et al. 1996) and an unknown compact object, probably a black-hole, in a tight 4.8 hours orbit and is situated at about 7 kpc from Earth (Ling et al. 2009). The gamma-ray space Telescopes AGILE (Tavani et al. 2009) andFermi (Fermi LAT Collaboration et al. 2009) have detected gamma-ray flares at GeV energies in the direction of Cygnus X-3 (a new gamma-ray flare was recently reported, see Corbel & Hays 2010). This identification is firmly established since the orbital period of the system was found in the Fermi dataset. This is the first unambigous detection of a microquasar in high-energy gamma rays. The gamma-ray emission in Cygnus X-3 is transient and correlated with powerful radio flares, associated with the presence of a relativistic jet and episodes of major ejections in the system. This feature suggests that the gamma-ray emission originates from the jet. In this proceeding, we present a model for the gamma-ray modulation in Cygnus X-3 (Sect. 2, see Dubus et al. 2010b for more details). GeV photons could be absorbed by the soft X-rays emitted by an accretion disk around the compact object. We report also on our studies of the gamma-ray opacity in Cygnus X-3 and put constraints on the location of the gamma-ray source in the system (Sect. 3).

Gamma-ray modulation

The model

The model relies on simple assumptions. Energetic electron-positron pairs are located at a specific altitude H along the jet and symmetrically (with respect to the compact object) in the counter-jet. These acceleration sites could be related to recollimation shocks as observed in some AGN such as M87 (Stawarz et al. 2006), possibly produced by the interaction of the dense Wolf-Rayet star wind and the jet. This possibility seems to be corroborated by recent MHD simulations (see Perucho et al. 2010). Pairs are isotropic in the comoving frame and follow a power-law energy distribution. The total power injected into pairs is P e . The jet is relativistic (with a bulk velocity β = v/c > 0) and inclined in an arbitrary direction parameterized by the spherical angles φ j (polar angle) and θ j (azimuth angle). The orbit of the compact object is circular with a radius d = 3 × 10 11 cm. We define here the orbital phase φ such as φ ≡ 0.25 at superior conjunction and φ ≡ 0.75 at inferior conjunction.

SF2A 2010

The Wolf-Rayet star (effective temperature T ⋆ ∼ 10 5 K, stellar radius R ⋆ ∼ R ⊙ ) provides a high density of seed photons for inverse Compton scattering on the relativistic pairs injected in the jet (n ⋆ ≈ 10 14 ph cm -3 at the compact object location). Because of the relative position of the star with respect to the energetic pairs and the observer, the inverse Compton flux is orbital modulated. This is a natural explanation for the orbital modulation of the gamma-ray flux observed in Cygnus X-3. Other sources of soft radiation (e.g. accretion disk, CMB) can be excluded to account for the modulation, and could instead contribute to the DC component. In addition to anisotropic effects, the relativistic motion of the flow should be considered in the calculation of the Compton emissivity (Doppler-boosting effects, see Dubus et al. 2010a for technical details).

Results

We applied this model to Cygnus X-3 for two extreme orbital solutions as given in Szostek & Zdziarski (2008). In the first solution (orbit inclination i = 30 o ), the compact object is a 20 M ⊙ black hole orbiting a 50 M ⊙ Wolf-Rayet star. In the second solution (i = 70 o ), the system is composed of a 1.4 M ⊙ neutron star and a 5 M ⊙ star. In order to constrain the orientation of the jet, we carried out an exhaustive exploration of the space parameter. The theoretical solutions are compared with the Fermi lightcurve using a χ 2 test. The best fit solutions to observations are given by those minimizing the χ 2 . Many sets of parameters reproduce correctly the observed gamma-ray modulation. Fig. 1 shows one possible solution. Fig. 2 presents the full distribution of models leading to a good fit, i.e. contained in the 90% confidence region 1 .

It appears from this study that the jet should be inclined close to the line of sight. The jet is mildly relativistic (β < 0.9) and pairs should not be located within the system (0.5d < H < 10d). We favor a massive compact object in the system (i.e. a black hole) as the energy budget required to reproduce the GeV flux can be only a small fraction of the Eddington luminosity. This work reveals also that the gamma-ray modulation (amplitude and shape) is very sensitive to the polar angle θ j , i.e. if the jet precesses. The non-detection by COS B (Hermsen et al. 1987) and EGRET (Mori et al. 1997) may be the consequence of a non favorable orientation of the jet. The controversial results by SAS-2 (Lamb et al. 1977) might actually be a real detection.

1 In Dubus et al. (2010b), we implicitly assumed fast cooling such that Pe ≈ +∞ γ min Keγ -p e dγe/t ic where t ic ≈ 0.5(γe/10 3 ) -1 (R/d) 2 s is the inverse Compton cooling timescale at γ min = 10 3 (see §4). Unfortunately, the term (R/d) 2 was not properly taken into account in our calculation of the distribution of acceptable parameters. The corrected distribution allows for a greater range of solutions with electrons injected at a large distance from the compact object. The corrected Figure 3 is shown here on the left panel in Fig. 2. The parameters of the best fit model and our conclusions are unchanged. Fig. 2. Distribution of good fit models contained in the 90% confidence region of the χ 2 statistics for the black hole (left panel) and the neutron star orbital solutions (right panel), for the parameters of the jet β (top panels), H, φj, and θj (bottom panels). Filled regions correspond to a total power injected into pairs Pe < L edd (light gray), < 0.1 L edd (gray) and < 0.01 L edd (dark gray), where L edd is the Eddington luminosity.

3 Gamma-ray absorption

The model

High-energy photons of 100 MeV-1 GeV can be absorbed by ∼0.1-1 keV photons. In Cygnus X-3, the main source of soft X-rays could be provided by an accretion disk around the compact object. Following Zhang & Cheng (1997), we compute the gamma-ray opacity in the thermal radiation field emitted by a standard accretion disk (optically thick, geometrically thin) in Cygnus X-3. The inner radius of the disk R in is set at the last stable orbit. Assuming that the total luminosity of the disk is radiated in X-rays L disk ≈ L X ≈ 10 38 erg s -1 , the accretion rate is Ṁ ≈ 10 -8 M ⊙ yr -1 for the black hole solution. The source of gamma rays is assumed point-like and located above the disk at an altitude z. The disk is inclined at an angle ψ with respect to the observer.

Results

Fig. 3 presents the gamma-ray opacity map of a 1 GeV photon in the radiation field of the accretion disk in Cygnus X-3. Photons are injected on the revolution axis of the disk. Gamma-ray photons are highly absorbed if the source lies in a compact region around the compact object (z < 10-1000R in ). Similar maps were obtained by Sitarek & Bednarek (2010) in the context of AGN with an application to Centaurus A. In addition to the thermal component in soft X-rays, the spectrum of Cygnus X-3 exhibits also a non-thermal tail in hard X-rays (see e.g. Szostek et al. 2008). This component might be related to the emission from a hot corona of electrons above the accretion disk (see e.g. Coppi 1999). These photons could also contribute significantly to increase SF2A 2010 the gamma-ray opacity in the system at MeV and GeV energies. More theoretical endeavors are required in this direction. Fig. 3. This map gives the gamma-ray opacity exp (-τγγ ) as a function of the viewing angle ψ and the altitude of the source above a standard accretion disk z for a 1 GeV gamma-ray photon. The calculation is applied here to Cygnus X-3, for the black hole solution. The source is assumed to be along the axis of the disk. Black regions correspond to high opacity (τγγ ≫ 1) and bright regions to low opacity (τγγ ≪ 1). The inner and external radius of the accretion disk taken here are Rin = 10 7 cm and Rext = 10 11 cm. The white dashed line indicates z ≡ Rin and the black dotted line z ≡ d.

Conclusion

Doppler-boosted Compton emission from energetic pairs accelerated at a specific location far from the compact object, in an inclined and mildly relativistic jet explains convincingly the gamma-ray modulation in Cygnus X-3. The lack of absorption signature in the GeV emission implies the source is at least 10 8 -10 10 cm above the accretion disk. Microquasars provide a nearby and well constrained environment to study accretion-ejection mechanisms and acceleration processes in relativistic jets.

Fig. 1 .

 1 Fig. 1. High-energy gamma-ray flux (> 100 MeV) as a function of the orbital phase (two full orbits) for the black hole solution in Cygnus X-3. Example of a good fit solution of the theoretical model (blue solid line) to the folded Fermi lightcurve (data points). The contribution from the jet (red solid line) and the counter-jet (red dashed line) are shown for comparison. Set of parameters: β = 0.45, H = 3d, φj = 12 o , θj = 106 o and Pe = 10 38 erg s -1 .

Laboratoire d'Astrophysique de Grenoble, UMR 5571 CNRS, Université Joseph Fourier, BP 53, 38041 Grenoble, France c Société Francaise d'Astronomie et d'Astrophysique (SF2A)

Acknowledgements: This work was supported by the European Community via contract ERC-StG-200911.


Bart George
email: bart.george@univ-ubs.fr

Régis Fleurquin
email: regis.fleurquin@univ-ubs.fr

Salah Sadou
email: salah.sadou@univ-ubs.fr

A Component-Oriented Substitution Model

One of Software Engineering's main goals is to build complex applications in a simple way. For that, software components must be described by its functional and non-functional properties. Then, the problem is to know which component satisfies a specific need in a specific composition context, during software conception or maintenance. We state that this is a substitution problem in any of the two cases. From this statement, we propose a need-aware substitution model that takes into account functional and non-functional properties.

Introduction

Component-oriented programming should allow us to build a software like a puzzle whose parts would be units "subjects to composition by a third party" [START_REF] Szyperski | Component Software : Beyond Object-Oriented Programming[END_REF]. Examples of such units are COTS (Components-Off-The-Shelf ), which are commercial products from several constructors and origins. When one develops and maintains a component-based software, some problems occur, and we will notice two main ones: how to select, during conception of such a software, the most suitable component in order to satisfy an identified need ? And during a maintenance, if this need evolves, will the chosen component remain suitable, or shall we replace it ?

We think that these problems are related to a substitution problem. In fact, when one conceives or maintains an application, some needs appear. And to describe them, the designer or the maintainer can imagine ideal components. These are virtual components representing the best ones satisfying these specific needs. Then the problem is to find the concrete components which are the closest to the ideal ones. In other words, trying to compose or maintain components means trying to make concrete components substitute ideal ones.

However, composition doesn't concern only the functional aspect. Most components are "black boxes" which must describe not only functional, but also nonfunctional properties. As every software needs a certain quality, one can't think about composing components whose non-functional properties are unknown, and at the same time hope having its quality requirements satisfied anyway. This is why substitution must take functional and non-functional properties into account.

So, how to substitute ? Some may say we just have to use subtyping, as some object-oriented languages made it a general way of substitution. However, an ideal component describes more than general needs: it describes the application's context, a notion that is absent from objects. Let us explain what we mean by "context". If we take a need, modeled by an ideal component, we will try to find a concrete one to substitute it. Now, let us suppose that we already found a suitable component. We may need to check if there isn't another one better than the first one. However, trying to substitute the old candidate by a new one would be a mistake, because the key notion isn't the candidate, but the need it is supposed to satisfy. Plus, if this need changes, a former candidate may no longer remain suitable. So substitution of an ideal component by a concrete one is performed only into the context of the need modeled by the ideal component. This is why a candidate component can replace another one without any subtyping relation between them, as every candidate is compared only to the ideal component.

In this paper, we consider a generic component model and a quality model (section 2), and into this framework we define a component-oriented substitution model, including substitutability rules for every functional and non-functional element of our model (section 3). In order to illustrate the possibilities of such a model, we describe the different substitution cases during the life cycle using a short application example (section 4). Then, before concluding, we describe some related works (section 5).

Component and quality models

Definitions given in this paper are placed in the following framework: one component model, holding a type system such as Java for EJB, and one quality model such as ISO 9126 standard [12]. In this framework, we suppose the existence of metrics to measure non-functional properties (such as those defined in [START_REF] Washizaki | A metrics suite for measuring reusability of software components[END_REF]), so that our contribution will focus only on the substitution model definition.

The generic model

Our goal is not to give yet another definition of what a component is, or what non-functional properties are. It is to define a component-oriented substitution that we can apply on many existing component and quality models. That is why we prefer to give generic models, on which we can apply our substitution concepts.

The generic component model includes component artifacts, representing the component's architectural elements, which are common to most existing component models, and which have non-functional properties. As shown in figure 1, we chose to keep three kinds of component artifacts: components themselves, interfaces, and operations. A component contains provided and required interfaces, and interfaces contain operations. In the remaining of the paper, we refer to candidate component and substitutable component when the first one tries to substitute the second one. Their elements are called respectively candidate elements and substitutable elements. When we find the best candidate for the substitution, we say the substitutable component or element can be replaced by this candidate. Beside the component model, we define a generic quality model. Its elements are quality characteristics (such as those from ISO 9126 [12]), and metrics. We use existing metrics to evaluate and compare non-functional properties (see [START_REF] Goulao | Software components evaluation : an overview[END_REF] for a survey). But why metrics ? In the literature, several methods for defining and evaluating non-functional properties already exist (see [START_REF] Sadou | Quality of Service Support in Development of Distributed Systems[END_REF] for a survey). But such methods usually focus on one specific property, or family of properties, for example quality of service, which is only a part of the whole software quality. Metrics may be applied to many families of properties, and allow comparisons. This is why we think that in our case, metrics represent the best method for comparing different non-functional properties.

A component's quality properties are based on our generic quality model. We start by describing elements of this quality model in the next subsection, before introducing their link with the elements of the component model.

Elements of the quality model

This quality model is composed of two elements: quality characteristics which represent non-functional properties, and metrics, which measure these characteristics (see left part of Figure 1). For the remaining of this paper, we consider that a metric may measure several quality characteristics (as proposed in the IEEE standard 1061-1998 [START_REF]IEEE Standard for a Software Quality Metrics Methodology[END_REF]), but each characteristic is measured by only one metric. Elements of the quality model are defined as follows:

Quality characteristics: A quality characteristic, or simply characteristic, represents a given quality property, preferably a fine-grained attribute (such as latency), because of our statement that only one metric can measure such a characteristic.

Metrics: A metric holds a set of quality characteristics it measures. It also holds a set of artifact types on which it can be calculated (for example: {component, interface}), the result's type, and its unit. The metric's variance explains the relation between the metric's result and the evaluated quality characteristic. For example, if a metric calculates an execution time, the variance stipulates that the lower the value is, the better it is.

Two metric values are comparable only if they are from the same metric. So having two "comparable metric values" M 1 and M 0 means that we have the same metric M , and we try to compare the value of M on the candidate artifact A 1 with the value of M on the substitutable artifact A 0 . Having two comparable metric values M 1 and M 0 , we can check if M 1 is superior to M 0 according to the variance. For example, if the metric type is an integer representing the execution time in milliseconds, then its variance is decreasing. In this case, if M 1 is greater than M 0 according to integer comparison, M 1 is in fact inferior to M 0 according to M 's variance.

Non-functional specifications

A component artifact is linked to a quality element using a non-functional specification (noted NFS). An artifact may be related to several quality elements, so several NFSs belong to only one artifact. An NFS describes the effect of a quality characteristic on the artifact it belongs to, and uses the metric applied on the latter. Several NFSs of a same component artifact may share the same metric, but not the same characteristic.

In Figure 1, the resultValue attribute of an NFS is given by the metric's measurement on the artifact. In the case of an ideal component, this attribute value is given by the application's designer.

Two NFSs are comparable if the artifacts they belong to are of the same kind and comparable (see next subsection for comparison definitions), and if they refer to the same characteristic. Two NFSs are equal if they are comparable and their resultValue attributes are equal.

Artifacts

The main element of our generic component model is the artifact. All artifacts, whatever their kind is, have a quality field, which is a set of NFSs. Two artifacts' quality fields are comparable if, for each NFS of one quality field, there is at least one comparable NFS in the other quality field. Two quality fields are equal if for at least one NFS of one quality field, there is an equal NFS in the other quality field, and vice versa.

Let us now describe the different kinds of artifacts:

Operations. An interface's operation is defined by its signature, also called a type. An operation's type is defined by the set of its parameters' types (α 1 , ... , α n )1 and its result's type β.

It is noted (α 1 , ... , α n ) -→ β.
Two operations are comparable if their signatures are comparable. Two operation signatures T and U are comparable if they are equal modulo the renaming of the type names, or if there exists a type substitution relationship V so that V .T equals to U , or T equals to V U , modulo the renaming of the type names.

For example, α -→ α equals to β -→ β if we rename α by β, but α -→ α is not equal to β -→ γ.

And if we consider Java's Object type, signature Object -→ Object may be replaced by Integer -→ Integer if we let Integer substitute Object. It corresponds to Zaremski and Wing's exact and generalized signature matching for functions [START_REF] Zaremski | Signature matching : a tool for using software libraries[END_REF].

Two operations are equal if their signatures are equal modulo the renaming of the type names, and if their quality fields are equal.

Interfaces. A component's interface is defined by a set of operations.

A candidate provided interface P I 1 is comparable to a substitutable provided interface P I 0 if for each operation of P I 0 there exists a comparable operation in P I 1 . A candidate required interface RI 1 is comparable to a substitutable required interface RI 0 if for each operation of RI 1 , there exists a comparable operation in RI 0 . Two interfaces (provided or required) are equal if their quality fields are equal and if, for each operation of one interface, there exists an equal operation in the other interface, and vice versa.

Components. A software component is defined by a set of provided interfaces and a set of required interfaces.

A candidate component C 1 is comparable to a substitutable component C 0 if for each provided interface of C 0 there exists a comparable provided interface of C 1 , and for each required interface of C 1 , there exists a comparable required interface of C 0 . If C 1 is not comparable to C 0 , it can not pretend to substitute C 0 .

Our substitution model

For each NFS, we attach a weight (or comparison weight) noted Comparison S , and a penalty noted P enalty S (S being the NFS). These two values define the NFS's importance for the artifact it belongs to. The higher these two values are, the more important this NFS is, in the whole substitutable component. If a substitutable artifact owns an NFS and a candidate artifact owns a comparable one with a superior value, the candidate's chances increase proportionally with the comparison weight. Else, the penalty will be used to sanction this lack. A candidate component may also bring his own new NFSs that the substitutable component doesn't have. These new elements will be evaluated by the ideal component designer.

The substitution distance, or distance, is defined using these weights, penalties, and NFS' resultValues. This distance will inform on the substitutability of an NFS or an artifact. The best candidate for substitution is the one with the lowest distance. If the distance is negative, the candidate element can be considered as "better" (in terms of quality) than the substitutable one, according to the current context. If the distance is positive, then the candidate is worse. If the distance equals to 0, then the two compared elements are "equivalent" each to the other, but it doesn't mean that they are equal.

For each component, there is a maximal distance for substitution, fixed by its designer. Let us consider a component C 1 , a candidate for the substitution of another component C 0 . If the substitution distance between C 1 and C 0 is bigger than the maximal distance associated to C 0 , then C 1 will be rejected.

Substitution distance between artifacts

Here, we will define a calculus that will give the distance separating a candidate component C 1 from a substitutable component C 0 in a given context. This context is defined by the weight and the penalty allocated to the NFSs of C 0 's artifacts. So, before talking about distance between artifacts, let us present the distance between their quality fields.

We will suppose that there exists a relation M IN x∈E f (x), which selects an element x from the set E so that the function f (x) has the lowest value.

Distance between artifacts' quality fields. Let us consider a substitutable artifact A 0 , a comparable candidate one A 1 , and their quality fields (denoted Q A1 and Q A0 ). The substitution distance between these quality fields (denoted QD) is defined as follows:

QD(Q A1 , Q A0 ) = S0∈QA 0 QDSpec(Q A1 , S 0 ) -S1∈QA 1 QDBonus(S 1 , Q A0 )
with:

QDSpec(Q A1 , S 0 ) = Comparison S0 * (resultV alue S0 -V ariance resultV alue S1 ) if ∃ S 1 in A 1
that is comparable to S 0 ; else, P enalty S0 . and:

QF Bonus(S 1 , Q A0 ) = 0 if ∃ S 0 ∈ Q A0 that is comparable to S 1 ; else, a value
given by C 0 's designer.

To measure the distance between the quality fields, we try to find for each S 0 a comparable NFS S 1 in A 1 (there can be only one, as NFSs of a same artifact cannot share the same characteristic). Substituable NFSs without any comparable S 1 are taken into account through their penalty value P enalty S0 . Candidate NFSs without any comparable S 0 are taken into account through a value given by C 0 's designer.

resultV alue S0 -V ariance resultV alue S1 is a subtraction between resultV alue S0 and resultV alue S1 depending on their metric's variance. For example, if its type is integer or float and variance is increasing, the measurement will equal to: resultV alue S0 -resultV alue S1 . If variance is decreasing, it will equal to: resultV alue S1 -resultV alue S0 .

Distance between incomparable artifacts. If two artifacts are incomparable, there will not be any substitution distance measurement between them.

Distance between comparable operations. Let us consider a substitutable operation O 0 and a comparable candidate operation O 1 . The substitution distance between them (denoted OpD) is defined as follows:

OpD(O 1 , O 0 ) = QD(Q O1 , Q O0 )
As long as O 1 and O 0 are comparable, the distance between them is in fact the distance between their quality fields.

Distance between comparable provided interfaces. Let us consider a substitutable provided interface I 0 , a comparable candidate provided interface I 1 , and their sets of operations Ops I1 and Ops I0 . The substitution distance between I 1 and I 0 (denoted P ID) is defined as follows:

P ID(I 1 , I 0 ) = O0∈OpsI 0 M IN O1∈OpsI 1 OpD(O 1 , O 0 ) -O1∈OpsI 1 P OBonus(O 1 , I 0 ) + QD(Q I1 , Q I0 ) with: P OBonus(O 1 , I 0 ) = 0 if ∃ O 0 ∈ Ops I0 that is comparable to O 1 ; else, a value
given by C 0 's designer.

To measure the distance between the interfaces, we take into account only the lowest found distance for each O 0 . Candidate operations without any comparable O 0 are taken into account through a value given by C 0 's designer.

Distance between comparable required interfaces. Let us consider a substitutable required interface I 0 , a comparable candidate required interface I 1 , and their sets of operations Ops I1 and Ops I0 . The substitution distance between I 1 and I 0 (denoted RID) is defined as follows:

RID(I 1 , I 0 ) = -O0∈OpsI 0 M IN O1∈OpsI 1 OpD(O 1 , O 0 ) -O0∈OpsI 0 ROBonus(I 1 , O 0 ) -QD(Q I1 , Q I0 )
with:

ROBonus(I 1 , O 0 ) = 0 if ∃ O 1 ∈ Ops I1 that is comparable to O 0 ; else, a value
given by C 0 's designer.

The principle of distance between required interfaces is the same as for provided ones, except that it is symmetrical. For provided interfaces, it is better to have I 1 providing better quality than I 0 , whereas for required interfaces, it is better to have I 1 requiring less quality than I 0 .

Distance between comparable components. Let us consider a substitutable component C 0 , a comparable candidate component C 1 , their sets of provided interfaces P Int C1 and P Int C0 , and their sets of required interfaces RInt C1 and RInt C0 . The substitution distance between C 1 and C 0 (denoted CD) is defined as follows:

CD(C 1 , C 0 ) = P I0∈P IntC 0 M IN P I1∈P IntC 1 P ID(P I 1 , P I 0 ) + RI1∈RIntC 1 M IN RI0∈RIntC 0 RID(RI 1 , RI 0 ) -P I1∈P IntC 1 P IBonus(P I 1 , C 0 ) -RI0∈RIntC 0 RIBonus(C 1 , RI 0 ) + QD(Q C1 , Q C0 )
with: P IBonus(P I 1 , C 0 ) = 0 if ∃ P I 0 ∈ P Int C0 that is comparable to P I 1 ; else, a value given by C 0 's designer. and:

RIBonus(C 1 , RI 0 ) = 0 if ∃ RI 1 ∈ RInt C1
that is comparable to RI 0 ; else, a value given by C 0 's designer.

To measure the distance between the components, we take into account only the lowest found distance for each P I 0 and for each RI 1 . Candidate provided (resp. substitutable required) interfaces without any comparable P I 0 (resp. RI 1 ) are taken into account through a value given by C 0 's designer.

Substitution in practice

Now let us take the example of an application that requires a Digital Video ("DV") camera component, with an interface for video stream and another one for camera control. It must also conform to the DV standard. This video camera example is taken from [START_REF] Blair | Open Distributed Processing and Multimedia[END_REF].

Modeling an ideal component

The above requirements could be expressed by an ideal component called videoCamera. The latter contains a provided interface videoStream (with an operation outputV ideoF low), a provided interface cameraControl (with basic operations such as on, record and eject2 ), and a required interface DV F ormat (with an operation inputDV F low that asks for a DV tape).

The needs are not just about functional part, but also about non-functional properties and their respective importance. For example, we suppose that a high level of reliability for record and eject operations is required (so that the camera does not crash while recording, nor refuse to eject a video tape). We also assume that a high image quality, such as a 1 million pixels (1 MPixels) screen resolution, is required for videoStream interface. According to the quality model of Figure 2, we use the following characteristics: reliability and imageQuality. Their respective metrics are: M eanT imeT oF ailure (M T T F ) and screenResolution. Then we attach to the ideal component several NFSs. To each operation of the cameraControl interface, we attach an NFS using reliability characteristic (onReliability for on operation, recordReliability for record operation, and ejectReliability for eject operation). To videoStream interface, we attach the NFS cameraResolution, using the characteristic imageQuality.

Finally, the designer fixes expected resultV alues, weights and penalties for each NFS, and also fixes a maximal distance for the ideal component videoCamera. On Figure 3, we see that the expected value for cameraResolution is 1 million pixels, and the expected values for NFSs using reliability characteristic vary from operation to operation. The values required for recordReliability and ejectReliability are higher than those for onReliability. The penalties attached to cameraResolution, recordReliability and ejectReliability are very high in order to enforce candidate components to contain these NFSs. cameraResolution has a low comparison weight, which means that a big difference on the image quality is not very important. However, recordReliability and ejectReliability have higher weights, which means that a big difference on the reliability measurements of record and eject is very important. The maximal distance is fixed at a low level, so that the lack of one of these three NFSs in a candidate component will hardly be accepted.

Component lifecycle and substitution cases

Now that our ideal component is modeled, we can look for the best concrete candidate one to substitute it. Here are the different substitution cases: First composition. Trying to plug a component into an application (in order to satisfy a given need) means trying to make this concrete component substitute the ideal one (corresponding to this need). Let us take the video camera example. Now that we modeled an ideal camera component, we have to check which concrete camera is the best candidate to substitute it.

First, according to our substitution model, a candidate must meet all the functional requirements, i.e. it must have all the ideal component's provided services (interfaces and operations), and must not bring more required ones. Otherwise, it will be rejected even if it has a higher quality. For example, let us consider a V HSCamera component meeting all functional requirements, except one (it requires VHS tapes instead of DV ones). No matter its quality, we need a camera that requires only DV tapes, and this candidate adds a required interface, so it is rejected. Then, a candidate, like the f luidCamera component on Figure 4, may add new NFSs unanticipated by the ideal component designer. For example video flow's number of frames per second. That corresponds to the metric F P S (for Frames Per Second), which measures f lowP erf ormance and f lowQuality characteristics (all of them are shown in Figure 2). It may be interesting to have a new NFS using f lowQuality characteristic on the outputV ideoF low operation, but the candidate (f luidCamera) lacks an important NFS. The penalty is so high that it is rejected.

We can also have candidates providing at the same time some lower qualities, and other higher ones, than ideal component. In this case, a candidate component would rather have good "scores" in the most important NFSs. For example, let us take a candidate goodImageCamera which has an excellent image quality (2 million pixels instead of 1 million) and an average reliability (2.5 days instead of 3 for operations record and eject), while candidate reliableCamera shown in Figure 5 has an average image quality and an excellent reliability. We are not directly comparing them to find which one is "better" than the other. We are comparing each one of them, separately, with the ideal component, in order to find if it is an acceptable candidate. If we consider this ideal component, and the distance obtained for each one of the candidates, we can say that both are acceptable (distance with candidate goodImageCamera would equal to +15), but the reliableCamera is the best one.

Maintenance. The application now has its camera component, but it could have a "better" one. If the needs are the same, the ideal component that models them is exactly the same, but we can have new candidates. So we have to compare each one of them to this ideal component, ignoring the previous candidate. If the needs change, this implies that the ideal component changes too. Thus, we must compare each candidate (including previous accepted one) with the new ideal component. In both cases, we are back to the first composition schema.

Related work

We said in introduction that substitutability was a well-known problem in objectoriented languages which include typing [START_REF] Cardelli | Type systems[END_REF] and subtyping [START_REF] Liskov | A behavioral notion of subtyping[END_REF]. It is also an industrial problem, as referred in [START_REF] Van Ommering | Software reuse in product populations[END_REF], who asks how to make sure that changes on a component won't affect existing applications of a component, and try to answer by setting rules based on subtyping. It was tempting for us to base on subtyping too, in order to substitute components [START_REF] Seco | A basic model for typed components[END_REF]. But we took critics of typing [START_REF] Perry | Foundations for the study of software architecture[END_REF] and subtyping [START_REF] Szyperski | Component Software : Beyond Object-Oriented Programming[END_REF] into account. Especially the one which said that they were too rigid and too restrictive for componentware, and couldn't deal with context. This is why we preferred to try a more flexible approach.

Premysl Brada has explored the notions of deployment context and contextual substitutability [START_REF] Brada | Specification-Based Component Substituability and Revision Identification[END_REF]. A deployment context of a component is a subcomponent that contains the used part of its services (provided and required services that are bound to other components). So Brada's contextual substitutability consists in comparing a candidate component with this sub-component, rather than the whole one. Although these notions seem close to ours, we work at a different level. Brada's approach consists in finding an "architecture-aware" form of substitutability, his context concerns a concrete component, and depends on its deployment in global architecture. Our approach is rather "need-aware", and our context considers an ideal component (modeling a need) and a concrete one which could substitute it.

As we said, our substitution model was inspired by Zaremski and Wing's specification and signature matching for library components [START_REF] Zaremski | Signature matching : a tool for using software libraries[END_REF][START_REF] Zaremski | Specification matching of software components[END_REF]. Their matching takes into account some substitution schemes that subtyping doesn't include. We were close to this approach, but we went further, by taking context and non-functional properties into account, and applying our substitution rules on generic component models. Beside Zaremski's and Wing's approach, there are other notable works in software reuse and component retrieval [START_REF] Lucrédio | A survey on software components search and retrieval[END_REF]. For example, our notion of weights can be compared to Scott Henninger's tools [START_REF] Henninger | Constructing effective software reuse repositories[END_REF]. These tools parse a source code, extract "components" from several keywords, then put them into a library where a valued network between words and components is created. So, when we search a word or a component in this library, a weight is calculated for each component with the nodes' values, and the selected candidate is the one which has the biggest weight. Our approach is at a different level, because we search and select candidates, not from keywords, but from components' structure. It can be used in such retrieval mechanisms in order to refine component search, and create more trustable libraries.

For our quality generic model, we were inspired by quality standards like ISO-9126 [12] and metrics standards like IEEE-1061 [START_REF]IEEE Standard for a Software Quality Metrics Methodology[END_REF]. Example of existing metrics that could be used with our model can be found in [START_REF] Goulao | Software components evaluation : an overview[END_REF][START_REF] Washizaki | A metrics suite for measuring reusability of software components[END_REF]. But the quality part of our model can also be used with quality of service contracts languages (based on Antoine Beugnard's fourth level of component contracts [START_REF] Beugnard | Making components contract aware[END_REF]), such as the ones modeled in QML [START_REF] Frolund | Qml : A language for quality of service specification[END_REF] and QoSCL [START_REF] Defour | Extra-functional contract support in components[END_REF]. In particular, our concern about substituting non-functional properties can be compared to Jan Aagedal's CQML language [START_REF] Sadou | Quality of Service Support in Development of Distributed Systems[END_REF], that deals with the substitutability of QoS "profiles". However, contrary to CQML, which, like most QoS languages, doesn't take functional aspects into account, our model combines functional and non-functional ones. And while Aagedal separates primitive component substitutability and composite component one, we deal with contextual substitutability of two components, no matter their internal structure.

Conclusion and future work

We proposed a substitution model including several elements: i) a generic quality model, able to use existing quality metrics and QoS languages. ii) a generic component model, able to use existing research and industrial approaches. iii) a substitution distance, able measure the substitutability of a candidate component. We also introduced the notion of ideal component, that models functional and non-functional conceptual needs and takes composition context into account.

In our current framework, we chose to consider one component model using existing quality characteristics and metrics from one quality model. There are two reasons for such a limitation : i) in the actual research and industrial schemes, composition concerns mainly components that come from a same component model; ii) the problem of comparing components from different models is orthogonal to the substitution problem. Both can be treated separately.

Right now, we have a tool [START_REF] George | Substitute tool[END_REF] that allows us to check if a component can substitute another one according to our substitution distance measurement. This tool aims to help designers to find the best candidates for their needs.

Fig. 1 .

 1 Fig. 1. Our generic model

Fig. 2 .

 2 Fig. 2. Example of quality model.

Fig. 3 .

 3 Fig. 3. Example of ideal component: videoCamera.

Fig. 4 .

 4 Fig. 4. Example of rejected candidate: f luidCamera.

Fig. 5 .

 5 Fig. 5. Example of accepted : reliableCamera.

For reasons of simplicity, in the current version of our model we do not take into account parameters' order.

For simplicity and brevity reasons, we limit this provided interface to only three operations.