Romain Pascual
email: romain.pascual@centralesupelec.fr

Pascale Le Gall

Agnès Arnould

Hakim Belhaouari

Topological consistency preservation with graph transformation schemes

Keywords: DPO graph transformation, Rule schemes, Combinatorial maps, Consistency preservation, Topology-based geometric modeling

come

Introduction

Graphs are widely used for modeling issues, for instance, as data structures for geometric modeling. Geometric modeling allows for the creation and manipulation of n-dimensional objects. When geometric objects are represented with graphs, their modifications can be formalized with graph transformations. This paper focuses on the double-pushout approach to graph transformations [START_REF] Ehrig | Graphs, Typed Graphs, and the Gluing Construction[END_REF] to specify topology-based geometric modeling operations.

Geometric modeling encompasses computer-aided design and manufacturing with applications across mechanical engineering, animated movies, video games, geology, and architecture. Numerous methods for the representation of geometric objects use a subdivided representation of objects. Objects can be divided according to application-domain properties, e.g., a segmentation based on a field value, or topological properties, i.e., a subdivision of a polyhedron into faces, edges, and vertices. Optimized data structures can be conceived depending on the subdivision structural properties (e.g., all faces are triangles) and the domain-related computations. For instance, triangle soup is a commonly used model for rendering virtual views because graphic processors are optimized to render triangular primitives [START_REF] Marschner | Fundamentals of Computer Graphics[END_REF]Chapter 12]. In animation, articulated objects are represented using a hierarchical structure of the object parts (called skeleton or rig) and a surface (typically a mesh) associated with each bone of the skeleton. To animate an articulated object, one can animate the skeleton and render the surface mesh on a set of poses [START_REF] Baran | Automatic rigging and animation of 3D characters[END_REF].

In topology-based geometric modeling, information is added to a polygonal representation of objects to encode the topological relations between object sub-parts. These topological relations describe adjacency and incidence between the topological cells (vertices, edges, faces, and volumes). Constraints on the topological relations ensure the soundness of the object's geometry, e.g., angles are correctly formed, vertices are incident to edges that are, in turn, incident to faces. Since modifications of a well-formed object should produce an equally well-formed object, graph transformations should preserve these consistency properties. In graph transformations, property preservation is a commonly studied problem; here, we study it for graphs related to a specific application domain, geometric modeling.

Polygon soups and meshes of animated rigs emphasize the external surface to ease rendering. In topologicalbased geometric modeling, we are interested in both the outer and the complete internal structure of objects. Indeed, inner parts play a key role in applications where volumetric properties are essential: geology [START_REF] Perrin | Shared earth modeling: knowledge driven solutions for building and managing subsurface 3D geological models[END_REF], architectural buildings [START_REF] Horna | Consistency constraints and 3D building reconstruction[END_REF], or physical simulation [START_REF] Wu | Physically-based Simulation of Cuts in Deformable Bodies: A Survey[END_REF][START_REF] Ben Salah | A Modular Approach Based on Graph Transformation to Simulate Tearing and Fractures on Various Mechanical Models[END_REF]. Edge-based data structure [START_REF] Campagna | Directed Edges-A Scalable Representation for Triangle Meshes[END_REF] is undoubtedly the most widely used model in topology-based geometric modeling, exploited in the open-source modeler Blender [START_REF] Weiler | Edge-Based Data Structures for Solid Modeling in Curved-Surface Environments[END_REF]. These models are equivalent to the more formal n-dimensional maps [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]. In the literature, n-dimensional maps are called combinatorial maps. In this article, we follow the terminology given in [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF] and call them oriented maps. We will use the expression 'combinatorial maps' as a generic term that encapsulates several models (such as oriented maps, generalized maps, hypermaps, chains of maps).

Combinatorial maps are often considered, from an algebraic perspective, as a collection of permutations on a set of atomic elements. The study of combinatorial maps comes from the field of combinatorics to represent cell decompositions of a surface [START_REF] Vince | Combinatorial maps[END_REF]. These maps are also used to draw graphs on a given surface, exploiting the combinatorial properties of the underlying graph, e.g., Euler's formula, and topological maps have been defined as graphs embedded in a surface [START_REF] Lando | Constellations, coverings, and maps[END_REF]. Among combinatorial map models, generalized maps and oriented maps are the most popular [START_REF] Lienhardt | Subdivisions of N-dimensional Spaces and N-dimensional Generalized Maps[END_REF].

In a graph-based fashion, both generalized maps and oriented maps are encoded as graphs whose arcs are labeled on an alphabet of dimensions that describes topological relations between the object cells. Previous works [START_REF] Poudret | Topology-based geometric modelling for biological cellular processes[END_REF] have already represented generalized maps as graphs and formalized geometric operations as DPO rewriting. DPO rules were extended to meta-rules [START_REF] Poudret | Graph transformation for topology modelling[END_REF] in a generator of geometric modelers called Jerboa [START_REF] Belhaouari | Jerboa: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF]. Traditionally, geometric modeling operations are defined generically to modify cells regardless of their size (e.g., number of faces constituting a volume). Meta-rules abstract topological cells thanks to variables. These variables can be instantiated with a particular cell to give rise to classical DPO graph transformations. In [START_REF] Poudret | Graph transformation for topology modelling[END_REF], sufficient conditions for consistency preservation of generalized maps were given for DPO transformations and meta-rules. Thus, the instantiation of a meta-rule with a given cell provides a graph transformation preserving the object consistency.

These pioneering works have demonstrated that graph transformations can be used advantageously to design topology-based geometric modelers in the context of generalized maps. This well-established model is highly regular, allowing for reasoning on the manipulation of subdivided objects. For instance, formal proofs with the Coq system have been studied in [START_REF] Dehlinger | Formal specification and proofs for the topology and classification of combinatorial surfaces[END_REF] with the help of generalized maps. Compared to generalized maps, oriented maps present the main advantage of a compact representation of objects to the detriment of regularity in dimension, making reasoning more difficult. Oriented maps are supported by efficient implementations such as the CGoGN library [START_REF] Kraemer | CGoGN: n-dimensional Meshes with Combinatorial Maps[END_REF] and are usually favored for industrial applications.

In this paper, we explore both generalized maps and oriented maps to promote graph transformations in the geometric modeling community. Compared with our previous work [START_REF] Poudret | Topology-based geometric modelling for biological cellular processes[END_REF][START_REF] Poudret | Graph transformation for topology modelling[END_REF], we no longer use variables and fully formulate rule schemes in terms of graph theory. We also study the constraint on the topological relations in a broader way so that the rules are no longer tuned for the generalized map model. To offer a unified framework, we have identified three topological constraints which, combined in different ways, define both generalized maps and oriented maps. As a consequence, the graphs under study are graphs subject to simple constraints.

Since DPO rewriting describes local modifications, we consider local definitions of the topological constraints, namely at the scale of nodes and arcs. Moreover, we split the constraints to study their preservation independently. Nonetheless, as a generic expression of topological operations is still required, we enrich the standard DPO approach with a pullback construction. More precisely, rule schemes depict transformations duplicated for each node of a graph, called pattern graph. Rule schemes and their instantiation with pattern graphs via the categorical product provide a framework to design generic operations. From a graph transformation perspective, we turn local DPO-based transformations into global product-based transformations.

The main contribution of this paper is the first framework based on graph transformations to express classical topological operations on both generalized and oriented maps. This framework results from the following realizations:

• Generalized maps and oriented maps are defined via three topological constraints: the incident arcs constraint, the non-orientation constraint, and the cycle constraint.

• Preservation of topological constraints in the context of DPO graph transformations is ensured by necessary and sufficient conditions.

• DPO graph transformations are generalized with rule schemes. Modifications expressed by rule schemes are essentially substitutions of successive arcs selected by their labeling. Rule scheme instantiation is defined using a product with a pattern graph extracted from the graph to be modified.

• Instantiation of rule schemes is guaranteed to result in DPO rules satisfying conditions for preserving topological constraints. This guarantee is obtained by sufficient conditions.

The article is organized as follows. The theoretical background of labeled graphs and their transformations is presented in Sections 2. We recall the DPO approach to graph transformations as a mechanism for local operations and show how the categorical product can express global operations. We provide contextualization elements in Section 3, introducing formal issues arising from the use of graph transformations in geometric modeling. In particular, we give graph-based definitions of generalized and oriented maps. We develop, in Section 4, the condition for preserving the incident arcs constraint in the DPO framework. The discussion is broadened to encompass the other two constraints (non-orientation and cycles) in Section 5. The results presented in Sections 4 and 5 ensure consistent rewriting of G-maps and O-maps with DPO transformations. In Section 6, we introduce rule schemes to facilitate the design of generic topological operations, as well as the instantiation mechanism using a product with a pattern graph extracted from the combinatorial graph under modification. The preservation of each of the topological constraints is successively studied in the three following sections (Sections 7, 8, and 9) by referring to the conditions of preservation on the DPO graph transformations resulting from their instantiation on a combinatorial graph. Application to topological-based geometric modeling is the subject of Section 10 with illustration on generalized and oriented maps. We also provide algorithms for the static verification of O-map and G-map consistency. In Section 11, we compare our approach to other constructions that preserve properties in graph transformations. Finally, concluding remarks are given in Section 12.

Graph transformations in the category of labeled graphs

In this section, we recall the main constructions of the category of edge-labeled graphs and the semantics of DPO rewriting. We show how the categorical product can generalize DPO rewriting.

Category of labeled graphs

We assume that the main notions from the category Graph are known. We advise the reading of [START_REF] König | A Tutorial on Graph Transformation[END_REF] for an introduction to graph transformations and [START_REF] Ehrig | Graphs, Typed Graphs, and the Gluing Construction[END_REF] for the complete construction of this category, with the corresponding constructions of pullbacks, pushouts, and pushout complements.

A graph is a collection of nodes and arcs that link two nodes, and information is added using labels. Such graphs are called labeled graphs. For our needs, we only consider labels on arcs and use totally labeled graphs.

Definition 1 (Labeled Graphs and Labeled Graph Morphisms). Let Σ be a finite set of labels. A graph labeled on Σ, or Σ-graph, G = (V G , E G , s G ,t G , l G ) is defined by two finite sets V G of nodes and E G of arcs, source and target functions s G ,t G : E G → V G and a label function l G : E G → Σ.

A Σ-graph morphism m : G → H consists of two functions m V : V G → V H and m E : E G → E H that preserve sources, targets and labels, i.e., such that s H

• m E = m v • s G , t H • m E = m v • t G , and l H • m E = l G .
A Σ-graph morphism is a mono if both m V and m E are injective and it is an inclusion if m V (x) = x for all x ∈ V G , and m E (x) = x for all x ∈ E G . If m is a mono, it is written m : G → H. The category having Σ-labeled graphs as objects and Σ-graph morphisms as arrows is written Σ-Graph.

We will use the following notation simplifications throughout the paper. When there is no ambiguity on the graph, the index G is omitted and G is denoted by G = (V, E, s,t, l). We identify arcs in the graph using their labels: an arc e labeled by i in Σ is an i-arc. We identify a morphism m = (m V , m E ) : G → H with its component-wise functions and omit the subscripts V and E: we write m(x) regardless of whether x is a node or an arc of G.

The category Σ-Graph is an elementary topos [START_REF] Vigna | A Guided Tour in the Topos of Graphs[END_REF] meaning it behaves essentially like the category of sets and functions. Weaker properties, such as adhesivity [START_REF] Lack | Adhesive Categories[END_REF] and the existence of initial and terminal graphs are enough for our needs.

The terminal element 1 Σ of the category Σ-Graph is the graph with a single node and an i-loop for every possible label i in Σ. The universal property of terminal elements ensures that given a Σ-graph P the morphism ! P : P → 1 Σ is uniquely defined. The morphism sends all nodes of P onto the single node of 1 Σ . Similarly, it sends all arcs of P onto the loop of 1 Σ with the same label.

Because Σ-Graph is an adhesive category, it admits pullbacks and pushouts along monomorphisms. In particular, pullbacks on the terminal element are uniquely defined (by the universal property of terminal elements) and yield products. For any two Σ-graphs P and Π, the pullback of the cospan P

! P -→ 1 Σ ! Π
← -Π is the product of P and Π in the category Σ-Graph:

P × Σ Π Π P 1 Σ ! Π ! P
In the following, Σ will be viewed as an alphabet, i.e., as a set of atomic elements called letters. A word on Σ is a finite sequence of letters from Σ. The empty word ε is the word with no letter. The set of words on Σ is denoted by Σ * . A word w on an alphabet Σ is of length n in N, denoted by |w| = n, if it is a sequence of n letters. The k-th (0 < k ≤ |w|) letter of w is denoted by w (k) . The concatenation of two words u and v from Σ * is the word uv of length |u| + |v| such that (uv) (k) = u (k) for all 0 < k ≤ |u| and (uv) (|u|+k) = v (k) for all 0 < k ≤ |v|.

Let G = (V G , E G , s G ,t G , l G ) be a Σ-graph.
A path is a sequence e 1 . . . e n of arcs such that t G (e k ) = s G (e k+1 ) for all 1 ≤ k < n. If s G (e 1 ) = t G (e n ) then the path is a cycle. A path e 1 . . . e n is a w-path if e k is a w (k) -arc for every 1 ≤ k ≤ n. If the path is a cycle, then it is a w-cycle. A w-path p = e 1 . . . e n can be denoted by s(e 1 )

w t(e n )

when we are only interested in the source, target and label of the path. An arc e ∈ E is said to be incident to the nodes s(e) and t(e). The arc e is non-oriented if it has a reverse arc e ∈ E, i.e., there exists an arc e such that s(e ) = t(e), t(e ) = s(e) and l(e) = l(e ). When the reverse arc is unique, we write e = e -1 .

Graph transformations using double pushouts

In an adhesive category, DPO rewriting exploits spans of monomorphisms as rules to ensure determinism and reversibility of the transformations [START_REF] Lack | Adhesive Categories[END_REF].

Definition 2 (Rule). A rule r is a span L ← K → R of monomorphisms.
L, R, and K are respectively called the left-hand side, right-hand side, and interface (or kernel) of the rule. The application of a rule r to a graph G consists of three steps: match L within G, delete the matched elements that do not belong to K, and add elements of R not in K. Matching the left-hand side of a rule within a graph is subject to the gluing condition [START_REF] Lack | Adhesive Categories[END_REF] that states the existence of a pushout complement. Definition 3 (Match). Let r = L ← K → R be a rule. A match for r is a morphism m : L → G. The match m : L → G satisfies the gluing condition for r if there exists a pushout complement of K → L → G. Monic matches do not lessen the expressiveness of the rewriting system [START_REF] Habel | Double-pushout graph transformation revisited[END_REF] but allow for explicit counting when deleting nodes or edges. Such matches also reduce the gluing condition to the dangling condition [START_REF] Ehrig | Tutorial introduction to the algebraic approach of graph grammars based on double and single pushouts[END_REF]: no node of m(L) \ m(K) is source or target of an arc in G \ m(L). In the sequel, we will assume that the following assumption holds. Example 1 (Direct Derivation). Relabeling an i-arc into a j-arc can be achieved by the rule depicted in the top span of Figure 1. The rule has two nodes in its left-hand side, right-hand side, and interface, an arc with the label to be modified in L, the relabeled arc in R, and no arc in K. The rule application is obtained via the match sending the node a to the node v, the node b to the node x and the i-arc between a and b to the i-arc between v and x. The i-arc is relabeled by j. We will study the preservation of constraints related to the graphs of geometric modeling. To simplify notations in the verification process, we use rules where the monomorphisms are inclusions. The interface K contains all elements common to L and R. For such rules, we only specify L and R because K can be retrieved as the (component-wise set) intersection of L and R. From now on, we will consider rules satisfying the following hypothesis.

Assumption 2. The interface K of the rule is the (component-wise set) intersection L ∩ R. Such rules are written L R, and their two monomorphisms are inclusions.

Graph transformations using DPO rewriting are helpful when trying to apply local transformations. Such transformations require isolating a part of the graph in order to modify it. This isolation forbids the application of the same modification uniformly to a subgraph. For instance, DPO rewriting does not provide a way to relabel all arcs of a given dimension for a cell without specifying its topology (e.g., the size of the cell). We aim at generalizing transformations to encode modeling operations regardless of the underlying topology. For this purpose, we need special operations such as relabeling or deleting all arcs sharing the same label. These operations can be designed using products.

Graph modifications using products

DPO rewriting models transformations based on deletion and creation of structure, allowing for a straightforward definition of graph modifications in a preservative framework. However, DPO rewriting is ill-suited should the initial graph elements be cloned or specifications on their incident arcs be made. On the other hand, Node-Labeled-Controlled grammars [START_REF] Engelfriet | Node replacement graph grammars[END_REF] inherently allow copying, merging, or deleting parts of the graph. Bauderon provided a categorical definition of this approach [START_REF] Bauderon | A uniform approach to graph rewriting: The pullback approach[END_REF] to simultaneously apply various modifications at different spots in a graph with a single mathematical operation, defined by a pullback. This paper will use the DPO rewriting to transform geometric objects (represented as graphs) and a pullbackbased generalization to express cloning and transformations on a global scale. This construction offers a simple yet sufficient construction for our invariant-preserving framework.

Example 2 (Product Construction). Consider the transformation depicted in Figure 2 where Σ = {1, 2}. In this example, Π has two nodes, x and y and three arcs. The 2-loop on x in Π and the 2-loop on a in P yield a 2-loop on (x, a) in P × Σ Π. Similarly, the 1-arc from y to x in Π and the 1-arc from b to c in P produce a 1-arc from (y, b) to (x, c) in P × Σ Π. Note that the 2-arc in P can not be matched with an arc of source y in Π. Thus, there is no 2-arc of source (y, a), (y, b) or (y, c) in P × Σ Π.

Arc deletion. We will consider the nodes of Π as different copies of the graph P. Thus, loops on the nodes of Π define the operation to be carried out on the arcs of P. We can use a product construction similar to Example 2 to delete all the i-arcs for a label i ∈ Σ. This deletion is achieved as the product of P with Π = ∆ i , the graph having only one node and |Σ| -1 loops labeled d for every d in Σ \ {i}. Such an operation is illustrated in Figure 3 where all the 2-arcs of P are deleted.

Arc relabeling. In the case of relabeling, P is the graph in which we want to relabel arcs, whereas Π stores the relabeling. Let us consider Σ = {i, i , j, j , k, d} and assume we want to systematically relabel i into j, i into j , keep k unchanged and delete d, meaning carry out these operations on all arcs of the corresponding labels. This global operation can be encoded with a relabeling function defined by the set of pairs {(i, j), (i , j ), (k, k)}. More generally, a relabeling operation is defined by a set of pairs R = {(i, j) | i ∈ Σ, j ∈ Σ} such that for any i in Σ, there is at most one j in Σ satisfying (i, j) ∈ R. Such a set will be called a relabeling set. A letter i in Σ such that (i, i) is in R is a label left unchanged by the relabeling. Conversely, a letter i in Σ such that for all j in Σ, (i, j) is not in R is a label deleted by the relabeling. As R is a subset of Σ 2 , the product is expressed in the category Σ 2 -Graph. The Σ-graph P to be renamed must be converted into a labeled graph with labels in Σ 2 . We will consider all the possible renamings, i.e., for each arc i, we will replace it with as many arcs as possible labeled with pairs of the form (i, j) with j in Σ. Moving back and forth between the two categories is achieved with functors. The embedding functor E Σ : Σ-Graph → (Σ 2 )-Graph transforms an i-arc (i ∈ Σ) into |Σ| arcs labeled (i, j) for each j ∈ Σ, making each relabeling possible. The projecting functor π Σ : (Σ 2 )-Graph → Σ-Graph keeps the relabeled part of arc labels. Formally, the embedding and projecting functors are defined as follows:

Definition 5 (Embedding and Projecting Functors). Let us consider a finite alphabet Σ.

The embedding functor E Σ : Σ-Graph → (Σ 2 )-Graph transforms:

• A graph G = (V, E G , s G ,t G , l G ) into a graph G = (V, E G , s G ,t G , l G )
such that for every i-arc e of E G with i in Σ, for all j ∈ Σ, there exists an (i, j)-arc in E G with the same source and target, written e ( j) .

• A morphism m = (m V , m E ) : F → G into a morphism m = (m V , m E ) : F → G such that for every e F in E F , for every j in Σ, m E (e ( j)
F ) is the arc m E (e F ) ( j) .

The projecting functor π Σ : (Σ 2 )-Graph → Σ-Graph transforms:

• A graph G = (V, E, s,t, l G ) into a graph G = (V, E, s,t, l G
) such that l G only keeps the second part of the label from l G .

• A morphism m = (m V , m E ) : F → G into a morphism m = (m V , m E ) : F → G such that if an (i, j)
-arc e F is sent to e G by m E then the j-arc e F built on e F is sent to the j-arc e G built on e G .

The projecting functor π Σ is the projection inherited from π 2 on the product Set × Set. Let us consider the relabeling defined by relabeling set R. The construction works as follows :

1. Embed P in the category Σ 2 -Graph to get E Σ (P). 2. Construct the product E Σ (P) × Σ 2 Π R , where Π R is the relabeling graph having only one node, and a loop labeled (i, j) for each pair (i, j) in the relabeling set R. Example 3 (Relabeling with Products). Assume we want to relabel all the 2-arcs of a graph into 3-arcs, as shown in Figure 4. First, we apply the embedding functor from {1, 2, 3}-Graph to {1, 2, 3} 2 -Graph : from each arc, three arcs are built, having 1, 2 and 3 as second label. Then, we construct the product with the relabeling graph (written Π in the figure). Arcs in red will give rise to relabeled arcs at the end of the transformation. Arcs in blue are the arcs left unchanged. Arcs in black are unused in the product. The relabeling set is R(1, 3) = {(1, 1), (2, 3), (3, 3)} and yields the graph that consists of a single node and three arcs, each specifying the relabeling of one letter: 2 is relabeled 3 whereas 1 and 3 are left unchanged. The product construction only keeps the arcs that match the relabeling. Lastly, the projecting functor erases the first label on the arcs, and we obtain the desired relabeling.

Apply the projecting functor π

Σ to E Σ (P) × Σ 2 Π R .
Before providing details on the graph formalism used in geometric modeling, we want to point out that DPOand product-based transformations are intended to serve different purposes. We will exploit DPO rewriting as a generic tool to carry out modifications on the underlying object. We will utilize the product mechanism as a general construction to achieve modifications as higher-level rules. Graph transformations using products provide a framework for the parallel generalization of rewriting rules without postponing the parallelization to the application time. In particular, we will use the product construction to generalize relabeling. By definition, the product construction is symmetrical in P and Π. However, we will distinguish between P and Π in the transformation. P will serve as a pattern to embed the graph structure, whereas Π will sketch the desired modifications. The generalization of transformations with pullbacks (see Section 6) will appear as the cornerstone of our approach, satisfying our need for static verification at rule-design time.

Geometric modeling

In this section, we will introduce G-maps and O-maps as edge-labeled graphs with constraints and use these denominations in the remaining part of the paper. We first introduce geometrical modeling and its formal issues. In this context, we use the terminology given in [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF] and call combinatorial maps the family that encompasses oriented and generalized maps, among other models. In the literature, the term 'combinatorial maps' has mostly been used to refer to the specific model of oriented maps.

In solid modeling and computer-aided design, many modelers rely on a boundary representation of objects, or B-rep. This method represents a solid as a collection of connected surface elements. These elements define the boundary between the interior of the volume and its exterior. B-rep modelers use different data structures to encode the topological relations of the surface elements, such as winged-edges, half-edges, or quad-edges. In [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF], the author shows that such data structures can be formalized as oriented maps. In [START_REF] Kraemer | Extension of half-edges for the representation of multiresolution subdivision surfaces[END_REF], the authors provide a complete conversion from half-edges to 2D oriented maps.

Combinatorial maps present two main advantages. The formalism allows defining objects in any dimension (1D, 2D, 3D, etc.). The definition of a generalized (resp. oriented) map is only parametrized by the maximal dimension. The aforementioned topological data structures are dedicated to specific dimensions and target application domains. The formal definition of combinatorial maps allows us to consider objects from any application domain thanks to its cell decomposition. The atomic elements of the decomposition are called darts and encoded by the nodes in a graph-based approach. Nodes are linked by arcs that describe neighboring relations between two cells.

The second main asset comes from the explicit expression of consistency constraints. These constraints state how the darts can be linked so that the modeled object is a quasi-manifold. Compared to the edges data structures, these constraints are defined within the model rather than hard-coded in the data structure and associated operations. Therefore, we can reason on these constraints. For this exact justification, combinatorial maps have proven fruitful to structure knowledge in [START_REF] Paulus | Virtual cutting of deformable objects based on efficient topological operations[END_REF][START_REF] Untereiner | CPH: a compact representation for hierarchical meshes generated by primal refinement[END_REF][START_REF] Ben Salah | A Modular Approach Based on Graph Transformation to Simulate Tearing and Fractures on Various Mechanical Models[END_REF][START_REF] Damiand | Merge-and-simplify operation for compact combinatorial pyramid definition[END_REF]. Hypermaps, a generalization of oriented maps with hypergraphs, were used to derive a Coq proof of the discrete form of the Jordan Curve theorem in [START_REF] Dufourd | An Intuitionistic Proof of a Discrete Form of the Jordan Curve Theorem Formalized in Coq with Combinatorial Hypermaps[END_REF].

The algebraic definition of oriented maps is not homogeneous in dimension. A new model, called generalized maps, was defined handling the 0 dimension to bypass this limitation [START_REF] Lienhardt | Subdivisions of N-dimensional Spaces and N-dimensional Generalized Maps[END_REF]. As a result, orientation is lost, and the number of darts is doubled. From the algebraic definitions given in [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF], G-maps correspond to open generalized maps, whereas O-maps correspond to closed oriented maps. Combinatorial maps are usually defined as topological relations on a set of darts. Considering the darts as graph nodes and the topological relations as graph arcs, we derive graph-based definitions of generalized maps and oriented maps. Consistency properties of the topological relations yield constraints on the graph that have been studied for the model of generalized maps [START_REF] Poudret | Graph transformation for topology modelling[END_REF]. We aim at extending this study to the more popular model of oriented maps. Once oriented and generalized maps are defined from a graph perspective, their transformations can be designed using graph transformations. In DPO rewriting, the rule interface contains the parts matched and preserved by the rule, which encodes some neighborhood of the modified part of the graph. Conditions on rules for consistency preservation were provided in [START_REF] Poudret | Graph transformation for topology modelling[END_REF] for the restricted case of generalized maps. These conditions led to the definition of a generic topological-based geometric modeler in [START_REF] Bellet | Designing a Topological Modeler Kernel: A Rule-Based Approach[END_REF] based on G-maps. Although the modeler can be used to apply modification on an object, its foremost interest is the rule editor. Geometric modeling operations can be conceived and written as a simple rule. Orbit variables were introduced to generalize rules to an orbit. Intuitively, an orbit is a subgraph induced by a subset of arc labels and allowed to retrieve topological cells in a generalized map. The orbit variables sanctioned the use in geometric modeling as the operation became independent of the underlying topology. At that point, the possibility to deal with domain-related information (called embeddings) was the main bottleneck of the approach. The introduction of I-labeled graph in [START_REF] Bellet | Rule-based transformations for geometric modeling[END_REF] solved this issue and defined DPO rewriting for graphs where nodes are labeled by a family of labels. Jerboa [START_REF] Belhaouari | Jerboa: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF] offers a graphical rule editor along with a syntax checker that guarantees the consistency of G-map rules (both for the topological aspect and the omission of geometric aspect). In [START_REF] Bellet | Geometric modeling: Consistency preservation using twolayered variable substitutions[END_REF] we solved geometrical consistency by statically detecting embedding computation equivalence on nodes of the same orbit.

We recall the topological constraints in Section 3.1 and provide a graph-based definition of generalized maps and oriented maps in Section 3.2. We discuss the formalization of modeling operations as graph transformation rules in Section 3.3 and the need for consistency preservation in Section 3.4.

Topological constraints

For our concerns, we will consider three kinds of label sets: dimensions, words, and pairs, which we will respectively use to model neighboring relations, paths in topological models, and modifications to be applied to graphs. We give names to each kind of graph to convey their respective usage.

We will use the category D-Graph where D is a finite set of integers, e.g, D = [ [START_REF] Ehrig | Graphs, Typed Graphs, and the Gluing Construction[END_REF][START_REF] Perrin | Shared earth modeling: knowledge driven solutions for building and managing subsurface 3D geological models[END_REF]], the set of integers between 1 and 4 (included). As integers describe the neighboring relations in topological models, we call topological graph any graph labeled with integers from D.

Definition 6 (Topological Graph). Let D be a finite set of integers, called dimension set. A D-topological graph is a graph from the category D-Graph.

The set D will also be used as an alphabet for more structured sets. We will consider categories W-Graph where W is a finite subset of D * . Intuitively, arc labels in such graphs describe paths in an underlying graph. For instance, in Figure 5b, the red arc labeled 13 can be interpreted as the 13-path in the graph of Figure 5a. We will call pattern graph any graph labeled with words from W. Since a function f from a set E to a set F can be defined by a set of pairs (x, y) in E × F with f (x) = y, we will use graphs labeled with pairs in E × F to encode graph transformations involving the use of such functions. More precisely, we will use functions from path labels to arc labels, that is, functions from W to D. We call graph scheme any graph labeled with pairs from (W, D). Definition 8 (Graph Scheme). Let D be a finite set of integers, and let W be a finite subset of D * . A (W, D)-graph scheme is a graph from the category (W × D)-Graph.

We consider three properties, also called topological constraints, defined locally on labeled graphs:

Definition 9 (Topological Constraints). Let G = (V G , E G , s G ,t G , l G
) be a Σ-labeled graph, v be a node of V G , and i and j be two labels of Σ. The node v satisfies • The incident arcs constraint I G (i) if v is the source of a unique i-arc and the target of a unique i-arc.

• The non-orientation constraint O G (i) if the i-arcs incident to v are non-oriented.

• The cycle constraint C G (i, j) if v is the source of an i ji j-cycle.

These constraints can be extended to a subset of labels I ⊆ Σ (or pairs of labels J ⊆ Σ 2 for the cycle constraint) and a subset of nodes V ⊆ V . We say G satisfies the constraint I V ,G (I), O V ,G (I), or C V ,G (J) whenever each node in V satisfies the corresponding constraint. If V = V , we simply say G satisfies I G (I), O G (I), or C G (J). Note that the incident arcs constraint guarantees the existence and uniqueness of a path given a sequence of labels, which will massively simplify the study of consistency for the cycle constraint. Indeed, if a graph satisfies the incident arcs constraint for two dimensions, then the order of the dimensions does not matter when considering the cycle constraint at the whole graph scale.

Lemma 1. Let G be a D-topological graph and i, j two dimensions in D. Suppose that G satisfies I G ({i, j}), then G satisfies C G (i, j) if and only if G satisfies C G ( j, i).

Proof. The lemma holds trivially from the incident arcs constraint.

Graph-based definitions of combinatorial maps

The incident arcs constraint allows us to unambiguously consider arcs based on their label and source (or target). This feature will prove helpful to generalize graph transformations. Therefore, we call a combinatorial graph any topological graph that satisfies the incident arcs constraint on every dimension. We define O-maps and G-maps based on combinatorial graphs.

Definition 10 (Combinatorial Graphs, Generalized Maps, and Oriented Maps). Let D be a finite subset of N and let D +2 denotes the set of pairs (i, j) ∈ D 2 such that i + 2 ≤ j.

A D-topological graph is a D-combinatorial graph if it satisfies the incident arcs condition I G (D).

An n-dimensional generalized map, or n-G-map is a [[0, n]]-combinatorial graph satisfying O G ([[0, n]]) and C G ([[0, n]] +2 ). An n-dimensional oriented map, or n-O-map is a [[1, n]]-combinatorial graph satisfying O G ([[2, n]]), and C G ([[1, n]] +2 ).
It is possible to define other models of [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF] by twisting the constraints. For instance, a closed generalized map can be defined as a G-map where no arc is a loop. An open oriented map can be defined by relaxing the incident arcs condition on the maximal dimension n to "every node v is the source of, at most, one n-arc and the target of, at most, one n-arc". Similarly, the dual model of oriented maps (open or closed) can be obtained by enforcing the non-orientation condition on the minimal dimension 1 but removing it on the maximal dimension n.

The study done in [START_REF] Poudret | Graph transformation for topology modelling[END_REF] covered G-maps, which is here extended to cover O-maps, and one could extend it to the other models. We chose to keep the study simple by narrowing the scope to these two models as they are the more regular ones, which simplifies the automatization of the transformation mechanism. Example 5 (G-map and O-map). Let us illustrate both models with the example of Figure 7. In this figure, as it will be in the whole paper, non-oriented arcs are either represented as a line or as a double-oriented arrow. The modeled object (on the left-hand side) consists of a triangle on top of a square in 2D. The corresponding 2-O-map consists of three cycles of 1-arcs for the two faces plus the outer one. The 1-arcs are oriented according to the orientation provided, orienting each face. The 2-arcs link faces along edges. The 2-G-map associated with the same model is given on the right-hand side. In a G-map, a face consists of an alternation of 0-arcs and 1-arcs. Note that the outer face is not represented in a G-map, and outer nodes are the source of 2-loops.

We can intuitively reconstruct G-maps and O-maps from the object decomposition into cells.

Example 6 (Object Decomposition). The representations of the object of Figure 7 as 2-G-map and 2-O-map result from the decomposition into decreasing dimensions. In the case of G-maps, we consider the object open, i.e., as the two faces A and B of Figure 8a. First, the object is split into faces sharing an edge with 2-links, in blue on Figure 8b. Likewise, the faces are decomposed into edges via 1-links, in red on Figure 8c. Finally, edges are dissociated with 0-links, in black on Figure 8d. The resulting nodes are the nodes of the Gmap, and the dimensional relations are the arcs of the G-map. The decomposition is similar for the model of O-maps, as illustrated in Figure 9. O-maps represent closed-oriented objects. Therefore, in Figure 9a, the faces A and B are oriented, and the outer face C is added. All faces have the same orientation. Thus, an edge shared between two faces is oriented in opposite directions in each face. For instance, the edge between faces A and B is oriented from left to right in the face A and from right to left in the face B. In the decomposition process, we first split the faces along their joint edges, as illustrated in Figure 9b. Then, edges are separated via 1-links. The decomposition stops at this step and provides the graph of Figure 9c. The nodes of this graph correspond to darts that intuitively represent parts of the edges from the initial object.

Modeling operations as graph transformations

Given that G-maps and O-maps are defined as graphs, the modeling operations can be formalized as graph transformations. For instance, the operation depicted in Figure 10 subdivides the face on the left to derive the four faces on the right. This example is a specific instance of quad subdivision dedicated to refining the topological structure of meshes [START_REF] Bommes | Quad-Mesh Generation and Processing: A Survey[END_REF]. This operation adds new vertices at the center of the face and the middle of each edge. An edge links the face center and the midpoint of the original edges.

The recursive subdivision into decreasing cell dimension yields the operation depicted by the G-maps of Figure 11a, for the object of Figure 10. The initial square face is represented by 8 nodes that are preserved by the transformation. The four 1-arcs and 2-arcs are also preserved while the 0-arcs are removed. The midpoints, the face center, and the linking edges are added. Based on the status of the element (added, preserved, and deleted), we determine possible rules for the operation. The rule in Figure 11b appears inconvenient because it does not specify that the matched element should be included in the same face. The rule in Figure 11c might seem like the most general, but it does not match the whole edges of the initial face. If the rule were applied to a non-isolated face, the half-edges in the surrounding faces would not be split. Finally, the rule in Figure 11d will never break the model consistency but is only applicable to isolated faces. From a purely algorithmic perspective, the quad subdivision operation can be defined without restriction to (non-)isolated faces. Besides, the rules presented here only apply to faces with four vertices, while the geometric modeling operation is applicable on any face regardless of the number of edges. In previous works, we used topological variables to perform this generalization. The topological variables allowed matching a subgraph induced by a set of dimensions. This subgraph could be copied, and the arcs could be relabeled. Arcs could be added between copies, meaning that each node of one copy of the subgraph would be linked to its alter ego in another copy. Such subgraphs are called orbits [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF], and the definition varies between oriented and generalized maps. From an algebraic perspective, orbits in oriented maps require composing the underlying permutations on nodes. From a graph perspective, orbits in O-maps require considering paths in the underlying graph. From this single modification, our approach based on dimension relabeling did not provide a convenient solution. As illustrated in Figure 12a, the quad subdivision of a face in a G-map setting can be decomposed into various copies of the initial face where the initial arcs are relabeled. The corresponding transformation is given in Figure 12b in an O-map setting. In Figure 12, nodes are colored and named based on the copy of the initial subgraph (from the left-hand side). For instance, in the right-hand side of the rule of Figure 12a, the nodes c1, c2, . . . c8 belong the same copy of the initial subgraph corresponding to the nodes a1, a2, . . . a8. Similarly, nodes bi and di (1 ≤ i ≤ 8) describe two other copies of the initial subgraph. On the contrary, nodes b8, c8 and d8 belong to different copies. The number indicates the initial node of a copy node. As such, nodes b8, c8 and d8 are copies of the node a8. Rules with topological variables allowed arcs that either link nodes between a single copy, such as nodes c1 and c8 or nodes a5 and a6, or link different copies of the same node, such as nodes c8 and d8 or nodes a4 and b4. These variables are not expressive enough to generalize the rule for O-map depicted in Figure 12b because node b1 is linked to node c2. The regularity of the model still provides ways to describe the operation homogeneously. For example, one can notice that each node bi is linked to the node c(i + 1 mod 4). We will use path labels to encode these links. The extraction of paths to create new arcs proved challenging and resulted in one of the main novelties presented in this paper. As a final note, we want to highlight the size of graphs used in practice. In Figure 13, the character consists of 12587 vertices, 12585 faces and a single connected component. The 3D character is represented by its boundary surface, i.e., a 2D manifold. The G-map decomposition produces 100680 nodes and 302040 arcs in 2D (Figure 13), while the O-map decomposition yields 50340 nodes and 100680 arcs (not drawn). We will see in Section 10 that the rule scheme for each model has one node in the left-hand side and four nodes in the right-hand side, regardless of the object size. The possibility to express operations as rules independent from the object size is an essential asset in geometric modeling as the objects are usually huge. The quad subdivision depicted in Figure 13 has been realized with Jerboa [START_REF] Belhaouari | Jerboa: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF] with G-maps. We can see two ranges of faces on the detailed views that correspond to the front and the rear parts of the character since it is cylindrical.

Consistency preservation in modeling operations

Since G-map and O-map definitions are based on topological constraints, transformations on the underlying graph need to preserve these constraints. These topological constraints are elementary (incident arcs, nonorientation, and cycle); thus, we can study the conditions for their preservation sequentially and separately for DPO-based transformations and product-based transformations. Superimposing the corresponding conditions will ensure the preservation of the model consistency. In the remaining part of the paper, we will use the denomination consistency preservation to refer to either constraint, depending on context.

We will give necessary and sufficient conditions to preserve the topological constraints on a local scale in topological graphs. Note that the non-orientation property was not a concern for generalized maps. Imposing that all graphs be non-oriented was sufficient to preserve the non-orientation constraint [START_REF] Poudret | Graph transformation for topology modelling[END_REF]. With the introduction of combinatorial maps, the study needs to be more general. This study leads us to provide a weaker yet sufficient condition for preserving the non-orientation constraint. For the incident arcs condition, the proof of the consistency preservation remains an extrapolation of the one given in [START_REF] Poudret | Graph transformation for topology modelling[END_REF].

The incident arcs property is the cornerstone of the model. This property provides a framework that is rich enough to define interesting abstractions of graph transformations via rule schemes using products. Since the operations are performed using direct transformations from DPO rewriting, conditions on rules need to be lifted to rule schemes. Lifting the conditions from DPO rules to rule schemes is relatively straightforward for the conditions of incident arcs (Section 7) and non-orientation (Section 8). However, the extension of the cycle condition for rules comes with additional constructions to deal with possible orientation for dimensions (Section 9).

Necessary and sufficient condition for incident arcs preservation in DPO rewriting

In Section 3.1, we presented the three topological constraints (incident arcs, non-orientation and cycles). We now study conditions on rules to explain how a graph can be modified while preserving its consistency. We want to ensure consistency at the rule level to provide feedback to the rule designer. In particular, our only assumption on the match morphism concerns its injectivity. We strive to establish conditions that can be statically checked on the rules without hindering their applicability.

Consistency preservation has been studied in previous work [START_REF] Poudret | Graph transformation for topology modelling[END_REF][START_REF] Bellet | Geometric modeling: Consistency preservation using twolayered variable substitutions[END_REF], but only sufficient conditions were given. As a result, the syntax analyzer [START_REF] Bellet | Designing a Topological Modeler Kernel: A Rule-Based Approach[END_REF][START_REF] Belhaouari | Jerboa: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF] would raise false negatives and consider valid rules as inconsistent. In this section, we provide necessary and sufficient conditions for the preservation of the incident arcs constraint. The approach developed in this section exploits a set-theory formalism and can be used as a reference for the discussion of Section 11 regarding consistency preservation in other frameworks. Combinatorial graphs play a key role in our framework and will prove essential for the study conducted in Section 5 on the remaining two constraints.

The weak incident arcs condition states that preserved nodes should retain their incidence to a dimension, and added nodes should satisfy the incident arcs constraint.

Definition 11 (Weak Incident Arcs Condition). A rule r = L R satisfies the weak incident arcs condition I r (i)-weak if it satisfies the two following sub-conditions :

1. Any preserved node of L ∩ R is the source (resp. target) of an i-arc in L if and only if it is the source (resp. target) of an i-arc in R.

R satisfies

I (V R \V L ),R (i), i.e.
, any added node of V R \V L is the source of a unique i-arc and the target of a unique i-arc in R.

When this condition is fulfilled, the derivation yields a graph satisfying the incident arcs constraint.

Theorem 1 (Incident Arcs Preservation). Let r = L R be a rule in the category of D-graphs.

The rule r satisfies the weak incident arcs condition I r (i)-weak if and only if for all matches m : L → G on a D-graph satisfying I G (i), the result graph H of the direct derivation G ⇒ r,m H satisfies the incident arcs constraint I H (i).

Proof. The first part of this proof (⇒) has been shown in [START_REF] Poudret | Graph transformation for topology modelling[END_REF]. Intuitively, regardless of whether preserved nodes are the source of an arc in L (i.e., whether the arc is matched), sub-condition 1 ensures the same status in R, yielding an arc in H. Similarly, sub-condition 2 guarantees the property for added nodes.

(⇐). Suppose the result graph H of the direct derivation G ⇒ r,m H satisfies the incident arcs constraint I H (i), for all matches m : L → G on a D-graph satisfying I G (i). Consider such a graph H and m the mono R → H.

Sub-condition 1 of the weak incident arcs condition.

Let v be a preserved node of L ∩ R that is the source of an i-arc e in L. Then m(v) is the source of m(e) in G. Suppose this arc is deleted by the application of the rule (otherwise e is in R). However, H satisfies I H (i) so there exists an i-arc e H in H of source m (v). This arc is not in G because m(v) is the source of only one i-arc in G. Thus, an arc e exists in R such that m (e ) = e H . By construction the source of e is v. Therefore v is the source of an i-arc in R. The construction holds when taking v as the target of e or inverting L and R. Hence, any preserved node of L ∩ R is the source (resp. target) of an i-arc in L if and only if it is the source (resp. target) of an i-arc in R.

Sub-condition 2 of the weak incident arcs condition.

Let v be an added node in

V R \V L . Then m (v) is an added node in H. Since H satisfies I H (i), then an i-arc e H of source m (v) exists in H. Since v is not in L ∩ R, any incident arc of v comes from R, i.e.
, there exists e in R such that m (e) = e H and s R (e) = v. Because e H is unique, so is e. Thus, v is the source of a unique i-arc in R. The proof holds when replacing source by target and R satisfies

I (V R \V L ),R (i).
Thereafter r satisfies the weak incident arcs condition I r (i)-weak.

Example 7 (Incident Arcs Preservation). Consider the rule in Figure 14, where the black elements are both in L and R, thus in the interface. The rule satisfies the weak incident arcs condition for the dimension 2. Indeed, interface nodes b and d are the source of a unique 2-arc in both sides, whereas nodes a and c are the target of a unique 2-arc in both sides. The added node e satisfies the incident arcs constraint for the dimension 2 as it is the source (resp. target) of a unique 2-arc. An example of DPO transformation depicted for this rule is given in constraint for the dimension 2. As we can see, the nodes in G, not matched by the rule, keep their incident arcs while matched nodes are held with the same incidences in R. Thus, the direct derivation yields a graph satisfying the incident arcs constraint for the dimension 2. The dangling condition is usually a critical concern [START_REF] Ehrig | Tutorial introduction to the algebraic approach of graph grammars based on double and single pushouts[END_REF][START_REF] Ehrig | Graphs, Typed Graphs, and the Gluing Construction[END_REF] in the DPO approach to graph transformations. As shown in [START_REF] Poudret | Graph transformation for topology modelling[END_REF], the gluing condition can be statically checked on the rule when applied to combinatorial graphs: a match m : L → G for a rule r = L R, where G is a D-combinatorial graph, satisfies the dangling condition if and only if L satisfies I (V L \V R ),L (D). We extend the weak incident arcs condition to incorporate the dangling condition aggregating in the incident arcs condition.

Fact 1. For a D-rule applied to a D-combinatorial graph, the dangling condition on the match is equivalent to the incident arcs constraint on the left-hand side of the rule, restricted to the deleted elements (proved in [START_REF] Poudret | Graph transformation for topology modelling[END_REF]).

Definition 12 (Combinatorial Rule).

A rule r = L R satisfies the incident arcs condition I r (D) if it satisfies the weak incident arcs condition I r (D)-weak and L satisfies

I (V L \V R ),L (D). Then, r is called a D-combinatorial rule.
Combinatorial graphs and rules play a crucial role in our framework as the incident arcs constraint guarantees the existence and uniqueness of arcs given a label (and a source node). The remaining part of this article relies heavily on this constraint, and we will consider (unless stated otherwise) that the following assumptions hold. Assumption 3. Graphs under modification belong to the category of combinatorial graphs. This category is the full subcategory of D-Graph whose objects are the D-combinatorial graphs. Rules are combinatorial rules, transforming a combinatorial graph into a combinatorial graph.

Consistency preservation in DPO rewriting for combinatorial graphs

With the benefit of the incident arcs constraint and condition, we now present necessary and sufficient conditions to preserve both the non-orientation constraint and the cycle constraint. A watchful reader will notice that we could impose a less restrictive constraint. Indeed the incident arcs constraint and condition for a dimension i are enough to deal with the non-orientation property on this same dimension. Similarly, the incident arcs constraint for the dimensions i and j are sufficient for the cycle property on these same dimensions.

Non-orientation preservation

The non-orientation preservation boils down to only having oriented arcs in the interface L ∩ R.

Definition 13 (Non-Orientation Condition

). A D-combinatorial rule r = L R satisfies the non-orientation condition O r (i) if any deleted (resp. added) i-arc of E L \ E R (resp. E R \ E L ) has a unique reverse i-arc that is also deleted (resp. added), i.e., in E L \ E R (resp. E R \ E L ).
We now give the corresponding theorem. Let m : L → G be a match on a D-combinatorial graph satisfying O G (i), H be the result of the direct derivation G ⇒ r,m H, m be the comatch R → H, and v H be a node in V H . Suppose e H is an i-arc incident to v H . Let us show that e H has a unique reverse i-arc in H. . Therefore e G is in H where it is the reverse arc of e H .

1. If e H ∈ H \ m (R) then e H ∈ G \ m(L).
Thereafter H satisfies the non-orientation constraint O H (i).

(⇐). Suppose for all matches m : L → G on a D-combinatorial graph satisfying O G (i), the graph H, result of the direct derivation G ⇒ r,m H, satisfies the non-orientation constraint O H (i).

Let m be the morphism R → H, which is a mono by construction of DPO rewriting and consider an added arc e of E R \ E L . Then, there exists e H in H such that m (e) = e H .

Because H satisfies O H (i), e H has a reverse arc e H in H. Since e is not in L, e H is not in G. Because G satisfies O G (i), e H is not in G (otherwise e H would also be in G). Thus, e H is an added arc in H. By injectivity of m there exists a unique i-arcs e in R such that m (e ) = e H . Then e and e are reversed arcs of E R \ E L in R. The proof holds by reversing the roles of H and G, as well as R and L.

Thereafter r satisfies the non-orientation condition O r (i).

Example 8 (Non-Orientation Preservation). The rule from Figure 14 also satisfies the non-orientation condition for the dimension 3: there is no deletion (in L \ R) of a 3-arc without its reverse, the 3-arc added (in R \ L) is a loop. As we can see, the only oriented 3-arc in the rule belongs to the interface L ∩ R. The graph G in the bottom left corner of Figure 15 satisfies the non-orientation constraint for the dimension 3. Thus, the direct derivation yields a graph satisfying the non-orientation constraint for the dimension 3.

Dealing with the cycle constraint

Finally, the cycle constraint needs a comparable condition on transformation rules to acknowledge the rules that guarantee consistency. The main issue when dealing with the cycle constraint is the description of neighboring elements. The preservation of the first two topological constraints considered arcs always incident to matched nodes. Since rules may only partially match cycles, we discuss constructions and properties that will help us define a necessary and sufficient condition to preserve the cycle constraint.

Recall from Lemma 1 that the order of the dimensions for the cycle constraints does not matter in a combinatorial graph when considering the constraint on the whole graph. First, since the cycle constraint characterizes cycles of length 4, if there is an i ji-path or a ji j-path in L, we can add the missing arc to make a cycle. In other words, if there is an i ji-path p in the left-hand side L of a rule r and we apply r to a graph G that satisfies C G (i, j) via the match morphism m : L → G then there is a j-arc of source m(t(p)) and target m(s(p)) in G. If not already in the rule interface, this j-arc can be added to L ∩ R without modifying the result of the direct transformation G ⇒ r,m H. For instance, we can add the missing j-arcs to the rule of Figure 16a and get the rule of Figure 16b. The application of either rule results in the same graph. However, it is easier to use the latter construction because it clarifies the cycles in the rule. Consequentially, when considering the cycle constraint in a rule, we first impose the completion of every i ji-path and ji j-path (in L and R). We call this operation the i j-completion of the rule and assume that every rule is i j-completed. Assumption 4. Every rule is i j-completed.

Rule completion

Alternating paths

Given a rule r and a match m : L → G, an i ji j-cycle in G is split into (possibly empty) elements of G \ m(L), m(L ∩ R), and m(L \ R). The elements of G \ m(L) are not matched by the rule and are left unchanged by the rule. The elements of m(L ∩ R) belong to the rule interface and are not modified. Therefore, the only part that raises concern consists of the elements in m(L \ R). If we guarantee that for each path in m(L \ R) coming from the cycle, a similar path exists in m (R \ L), by concatenation with elements of m (R ∩ L) and elements of H \ m (R), we reconstruct a cycle in H.

Example 9 (Intuition for Cycle Preservation). Figure 17, where all arcs are considered non-orientated, illustrates a rule that deletes a 3-arc between nodes c and e, and essentially exchanges the roles of c and e between the top 1212-cycle and the bottom cycle. In the right-hand side of the rule, nodes a, b, d and e belongs to a cycle. The question is whether the images of c, f , and h also belong to a cycle in H. As we can see, there is a 12-path from f to h in both L and R. Thus, the image of the path in G belongs to a cycle in G. Therefore, the unmatched part can be concatenated with the image of the path from R. As a result, we get back the cycle in H. This example provides intuition to preserve cycles with rules, explained more thoroughly in this section. Formally, elements in L that can be matched to an i ji j-cycle in G are paths labeled by a word on the alphabet {i, j} such that two consecutive letters are distinct. We call (i, j)-alternating such paths. We want to ensure that if L contains an (i, j)-alternating path with all arcs in E L \ E R , R also has an (i, j)-alternating path with the same source, target, and label. What we want to consider are only the longest paths. Since L may contain cycles with all arcs in E L \ E R , we need to enforce non-overlapping conditions to consider maximal elements. We say a path overlaps if it contains an arc twice (note that it may include a node several times). We will try to preserve paths to guarantee the preservation of the cycle constraint on combinatorial graphs. We call optimal paths such paths. Definition 14 (Optimal Path). Let r = L R be a D-combinatorial rule. We say the path p = v s v t is (i, j)-optimal in L (resp. in R) if it satisfies the following properties:

• The path p is an (i, j)-alternating path (i.e., path labeled by a word on the alphabet {i, j} such that two consecutive letters are distinct).

• All arcs of p are deleted arcs of E L \ E R (resp. added arcs of E R \ E L ).

• The path p does not overlap.

• The path p is maximal (with repect to the inclusion of paths) between paths that satisfy the first 3 properties.

• The path p does not belong to an i ji j-cycle in L (resp. in R).

Example 10 (Optimal Path). Consider the left-hand side of the rule from Figure 17. The 1212-cycle adcb forms a (1, 2)-alternating path. This path is non-overlapping and maximal. However, it is not optimal as it contains interface arcs (the arc between a and d and the one between b and a). Restricted to the 21-path dcb, it is still not optimal as it is part of an i ji j-cycle. The 132-path bceh is labeled with three distinct dimensions. Therefore it is not an alternating path, and a fortiori not an optimal path. Conversely, the 131-path f ecb is a maximal non-overlapping (1, 3)-alternating path. As it contains only deleted arcs and is not part of a 1313-cycle, the path is (1, 3)-optimal.

Note that any optimal path satisfies the following straightforward property: if p = v s v t is an (i, j)-optimal path in a D-combinatorial rule r = L R, then v s and v t are distinct interface nodes of L ∩ R.

Consider again the 1212-cycle of source f in the graph G from Figure 17. The cycle can be divided into an optimal path from f to h (the red 12-path going through e) and a path from h to f in G \ m(L) (the black 12-path going through g). For any optimal path that is not a cycle in L, we impose a path with the same source, target, and label in R and call coherent such paths.

Definition 15 (Coherence). Let r = L R be a D-combinatorial rule. An optimal path in L (resp. in R) is coherent with an optimal path in R (resp. in L) if they share the same source, target, and label. An optimal path in r is coherent if it admits a unique, coherent optimal path in the other side of the rule.

To guarantee that a combinatorial rule preserves the cycle constraint, we impose that every optimal path is coherent.

Definition 16 (Cycle Condition).

A D-combinatorial rule r = L R satisfies the cycle condition C r (i, j) if it satisfies the following sub-conditions:

1. Any (i, j)-optimal path in r is coherent. 2. Any preserved node of L ∩ R that is the source of an i-arc (resp. j-arc) in E L \ E R is the source of an i-arc (resp. j-arc) in R that either belongs to an i ji j-cycle or to an (i, j)-optimal path. 3. Any added node of V R \V L is the source of an i-arc (resp. j-arc) in R that either belongs to an i ji j-cycle or to an (i, j)-optimal path.

Note that, in a D-combinatorial rule r that satisfies the cycle condition C r (i, j), there can be no (i, j)-optimal path that consists of a single arc. Indeed, such an arc would have to be a coherent optimal path and therefore in L ∩ R, which contradicts the optimality of the path.

Example 11 (Cycle Condition). One can easily verify that the rule from Figure 17 satisfies the cycle condition of Definition 16. We provide more examples in Figure 18, where arcs are still considered non-oriented, interface elements are drawn in black, and added or deleted elements are drawn in red. For instance, the rule of Figure 18a transforms two 1212-cycles, where the 2-arcs are loops, into a single 1212-cycle on four nodes. In L, each node is the source of an i ji j-cycle, L admits no (1, 2)-optimal path. Note that R does not add any (1, 2)-optimal path. All nodes have their incident 2-arcs in L deleted but are the source of a 2-arc that belongs to a cycle in R. In the rule of Figure 18b, L consists of two (1, 2)-optimal paths. The path abc is coherent in L as there is also a (1, 2)-optimal path between a and c in R. Similarly, the path de f is coherent in L. All nodes of L are interface nodes with deleted 1-arcs and 2-arcs. Nodes a, c, d e, and f are the source of arcs that belong to an optimal path. Node b is the source of a 1-arc and a 2-arc that belong to a 1212-cycle in R. Likewise, the added nodes h, i, and j are the sources of a 1-arc and a 2-arc that belong to a 1212-cycle in R. Finally, an added node can also be the source of an arc that belongs to optimal paths, such as node g.

Preserving the cycle constraint

Before detailing the theorem for cycle preservation, we will provide a preliminary result on the size of optimal paths in a coherent rule.

Lemma 2. Let r = L R be an i j-completed rule such that for all matches m : L → G on a D-combinatorial graph satisfying C G (i, j), the resulting graph H of the direct derivation G ⇒ r,m H satisfies the cycle constraint C H (i, j). Then any (i, j)-optimal path in L is of size 2.

Proof. Suppose an (i, j)-optimal path exists in L with elements in L \ R of size 1. Without loss of generality, we can suppose there is an i-arc e 1 of source v s and target v t in L such that v s is the target of no j-arc and v t is the source of no j-arc. When matched to G, the i ji j-cycle contains m(e 1 ) and an (i, j)-alternating path p = m(v t ) ji j m(v s ) with all arcs in G \ m(L). Below, the arc in m(L \ R) is displayed in red whereas arcs in G \ m(L) are drawn in blue.

Therefore p is also in H. Since H satisfies the cycle constraint C H (i, j), p can be extended to an i ji j-cycle with an i-arc of source m (v s ) and target m (v t ). As r is a D-combinatorial rule and H is a D-combinatorial graph, this i-arc is in m (R), which contradicts that e 1 is in L \ R.

Furthermore, an (i, j)-optimal path can not be of size greater than 4 as there exists no (i, j)-alternating path of size greater than 4 without duplicate arcs in a D-combinatorial graph satisfying C G (i, j). The i j-completion of the rule prevents it from being of size 3. Finally, the definition of optimality prevents it from being of size 4.

Therefore, any optimal path is of size 2.

Exploiting this characterization, we show that the cycle condition on a combinatorial rule is necessary and sufficient to guarantee that its application on a combinatorial graph satisfying the cycle constraint results in a graph that also satisfies the cycle constraint.

Theorem 3 (Cycle Preservation). Let r = L R be a D-combinatorial rule.

The rule r satisfies the cycle condition C r (i, j) if and only if for all matches m : L → G on a D-combinatorial graph satisfying C G (i, j), the graph H, result of the direct derivation G ⇒ r,m H satisfies the cycle constraint C H (i, j).

Proof. Given a match m : L → G on a D-combinatorial graph satisfying C G (i, j), let m denote the morphism R → H, which is a mono by construction.

(⇒). Suppose r satisfies the cycle condition C r (i, j). Consider m : L → G a match on a D-combinatorial graph G satisfying C G (i, j), and H the result of the direct derivation G ⇒ r,m H. Let v H be a node of H. • All arcs from the cycle in p = m(v s ) w m(v t ) are in G \ m(L).

1. Suppose that v H ∈ H \ m (R), then v H is a node of G. Thus, v H is the source of an i ji j-cycle in G since G satisfies C G (i, j). (
• Node v H belongs to p. Since v H is in G \ m(L), its incident arcs cannot be in m(L) and p is a path, the size of which is at least 2. If w completes w to get a cycle, the remaining part of the cycle is a path m(v t )

w m(v s ), which is the image of an (i, j)-alternating path in L. This (i, j)-alternating path consists of interface arcs and optimal paths. Since any optimal path is coherent according to sub-condition 1, there is a similar path in m (R). Either way, their concatenation with m

(v s ) w m (v t ) is an i ji j-cycle of source v H in H. 2. Otherwise, v H is in m (R). Denote v the node in R such that m (v) = v H . (a) Suppose v is a node of L ∩ R and v is not the source of an i-arc in L. Since v belongs to L ∩ R, v H is a node of G. As G satisfies C G (i, j
), v H is the source of an i ji j-cycle in G. From that point, the proof is similar to cases 1a and 1b depending on whether the cycle is partially matched.

(b) Otherwise, assume v is a node of L ∩ R, but v is the source of an i-arc in L. Since r is a combinatorial rule, v is the source of an i-arc in R. Sub-condition 2 guarantees that this i-arc either belongs to an i ji j-cycle or to an (i, j)-optimal path in R. In the former case, the image by m of the cycle yields an i ji j-cycle of source v H in H. In the latter, let p = v s w v t be the (i, j)-optimal path in R. By sub-condition 1, p is coherent and there exists an (i, j)-optimal path p = v s w v t in L. Without loss of generality, assume that the first arc of p is labeled by i. Since G satisfies C G (i, j), m(v s ) is the source of an i ji j-cycle in G and the first part of this cycle is m(p ). The remaining arcs of the cycle can be subdivided into elements of G \ m(L) left unchanged by the rule, interface arcs of m(L ∩ R) preserved by the rule, and (i, j)-optimal paths. Any such optimal path is coherent from sub-condition 1 and yields a similar optimal path in R.

Their concatenation with m (p) is a cycle. When considering it with v H instead of m(v s ), it is an i ji j-cycle of source v H in H. (c) If v is a node of R \ L, the proof is similar to case 2b, exploiting sub-condition 3 instead of sub- condition 2.
Thereafter H satisfies the cycle constraint C H (i, j).

(⇐). Suppose for all matches m : L → G on a D-combinatorial graph satisfying C G (i, j), the result H of the direct derivation G ⇒ r,m H satisfies the cycle constraint C H (i, j).

Sub-condition 1 of the cycle condition

Suppose there is an (i, j)-optimal path v s w v t in L. By optimality, v s = v t . According to Lemma 2, the path is of size 2. The path m(v s w v t ) belongs to an i ji j-cycle in G because G satisfies C G (i, j). The two arcs that define the path m(v t ) w m(v s ) are in G \ m(L \ R). Thus, they are in H, where they belong to an i ji j-cycle. The incident arcs condition guarantees that the path m (v t ) w m (v s ) comes entirely from R \ L and is a maximal non-overlapping path. Since the path contains two arcs and have distinct endpoints, it cannot overlap. Therefore it is the (i, j)-optimal path in R coherent with v s w v t .

Suppose there is an (i, j)-optimal path p = v s w v t in R and consider the cycle completion of the path in H.

It yields elements in G that belong to a cycle with arcs or vertices from m(L). Elements on this alternating path are in m(L \ R) by hypothesis on p. According to Lemma 2, the path is of size 2. The incident arcs constraint on G ensures that it is an optimal path coherent with p.

Sub-condition 2 of the cycle condition

Consider a preserved node v of L ∩ R that is the source of an i-arc in L \ R. Because r is a combinatorial rule, sub-condition 1 of the weak incident arcs condition I G (i) guarantees that v is also the source i-arc in R \ L (this arc can not be in L ∩ R because v is already the source of an i-arc in L \ R).

Let v H be the image of v by m , i.e., v H = m (v). Since H satisfies C H (i, j), v H is the source of an i ji j-cycle in H. Depending on whether the whole cycle is present in R, v is the source of an i-arc in R that belongs either to an i ji j-cycle or to an (i, j)-optimal path. The proof holds for a j-arc.

Sub-condition 3 of the cycle condition

Consider an added node v of R \ L. Because r is a combinatorial rule, sub-condition 2 of the weak incident arcs condition I G (i) guarantees that v is the source i-arc in R. Similar to the proof of sub-condition 2, this arc belongs either to an i ji j-cycle or to an (i, j)-optimal path. The proof holds for a j-arc.

Thereafter r satisfies the cycle condition C r (i, j).

Theorem 3 is stronger than the theorems presented in previous work for the preservation of the cycle constraint. We also want to point out that Theorems 1, 2, and 3 express consistency preservation as simple syntactic conditions on the rule. Intuitively, such conditions are possible because of our specific framework, namely D-combinatorial graphs, which is highly regular.

Rule schemes using product

As we have seen in Section 2.3, products offer a simple way to apply transformations, such as arc deletion or arc relabeling, on a global scale. Taking benefit from our specific graphs, we will use the product as a mechanism to generalize transformations of D-combinatorial graphs in the context of the DPO approach.

Our product-based generalization of DPO rewriting will allow us to define a large family of operations on combinatorial graphs taking advantage of their regularity with respect to the dimensions of D. In Section 6.1, we provide more details about pattern graphs introduced in Section 3.1. Pattern graphs carry words of dimensions as labels on their arcs and enable us to select subgraphs to be modified in the combinatorial graphs. In Section 6.2, we define graph scheme as a way to encompass a transformation to be applied globally on a graph. We call instantiation of a graph scheme the operation (relying on a graph product) that modifies a pattern graph based on a graph scheme. We also define rule schemes as spans in the category of graph schemes. Similarly, we can instantiate a rule scheme by instantiating each of its graph schemes with the same pattern graph. Since we can instantiate a rule scheme with any pattern graph (assuming the right set of labels), rule schemes are rule abstractions, encoding infinitely many possible rewriting. Finally, in Section 6.3, we will discuss the mechanisms involved in the application of rule schemes.

Global extraction of paths

In a D-combinatorial graph, every node is the source of a unique arc for each dimension in D. Therefore, given a word w on D, every node is the source of a unique w-path. In the relabeling operation defined in Section 2.3, we used pairs of the form (i, j) to rename a label i into j. Here, we will consider, more generally, pairs of the form (w, i) to create an i-labeled arc between the source and the target of a w-path.

The uniqueness of source and target per dimension makes it possible to build paths by following arcs forward or backward. Thus, for a dimension i, we introduce the notation i to indicate that, from a given node v, the next node in the path is the unique node v , source of the i-arc whose target is v. We accordingly extend the labeling alphabet of the graphs:

The conjugation is extended to words on D

* such that the conjugate of w (1) . . . w (n) is w (n) . . . w [START_REF] Ehrig | Graphs, Typed Graphs, and the Gluing Construction[END_REF] .

Conjugation allows us to broaden the definition of a path in the case of D-combinatorial graphs. For a D-combinatorial graph G = (V, E, s,t, l), we introduce the conjugate D-combinatorial graph G = (V, E ∪ E, s,t, l), with E = {e | e ∈ E}. The functions s, t and l on arcs in E are the corresponding functions of G, i.e., for e ∈ E, s(e) = s(e), t(e) = t(e) and l(e) = l(e). On arcs in E, the functions s, t and l rely on the inversion of the underlying arcs, i.e., for e ∈ E, s(e) = t(e), t(e) = s(e) and l(e) = l(e). From now on, for w in D * , w-paths of a D-combinatorial graph will implicitly refer to the w-paths defined on its conjugate version. In short, such w-paths are well-defined, and their target always exists because a node in G is the source and target of a unique i-arc for each dimension i in D:

Fact 2. The incident arcs constraint guarantees the existence and uniqueness (up to the starting node) of paths labeled by a sequence of conjugate dimensions.

In order to build rule schemes as an abstraction of rules, labels on the conjugate alphabet will be used to encode the reconnection between nodes in the graph that supports the instantiation. We extend the definition of pattern graph (from Section 3.1 to graphs labeled over subsets of D * . Figure 19 Intuitively, labeling arcs with paths offers greater freedom to characterize modified parts of the graphs and create arcs from such complex paths. In general, any pattern graph can be used to instantiate a rule scheme. In practice, pattern graphs will be extracted from the graph modified by the application of the rule scheme. We will discuss in Section 6.3 how to derive pattern graphs from a combinatorial graph. In the sequel, W is a finite set of words of D * .

Rule schemes

Following the idea given in Section 2.3 of representing a graph modification with a product, we use a graph to represent the modification to be carried out on the pattern graph. Since pattern graphs belong to the category W-Graph and we are trying to build objects from the category D-Graph, the modification will rely on a function from W to D. Therefore, the product is expressed in the category of graph scheme. The construction is similar to the relabeling operation, with the functors E Σ and π Σ replaced by:

• An embedding functor E D : W-Graph → (W × D)-Graph that transforms the arcs labeled by a word w in W into a set of |D| arcs labeled (w, d), for all d ∈ D.

• A projecting functor π D : (W × D)-Graph → D-Graph that only keeps the second part of the arc labels.

To ease certain proofs and constructions, we will also consider the projecting functor π W : (W × D)-Graph → W-Graph that only keeps the first part of the arc labels.

The instantiation ι(Π, P) of a (W, D)-graph scheme Π along a W-pattern graph P is similar to the relabeling operation given in Section 2.3. The instantiation is achieved as follows :

1. Embed P in the category of (W × D)-graphs to get E D (P). 2. Construct the product E D (P) × (W×D) Π. 3. Apply the projecting functor π D to E D (P) × (W×D) Π and get ι(Π, P), the instantiation of Π along P :

ι(Π, P) = π D (E D (P) × (W×D) Π).
This construction is summarized by the following commutative diagram:

ι(Π, P) E D (P) × Π Π P E D (P) 1 W×D π D ! Π E D ! E D (P)
where the square is a pullback, and double arrows represent functors.

Example 12 (Instanciation of a Graph Scheme). Let us take back the pattern graph from Figure 19, which is displayed at the bottom left corner in Figure 20 (graph P). As depicted in Figure 20, the pattern graph is first embedded in the category ({21, 21, ε}, {1, 2})-Graph to give the graph E D (P), placed just above. The Definition 18 (Rule Scheme). A (W, D)-rule scheme S = L R, is a rule in the category of (W, D)-graph schemes. The core of the rule scheme S is the projection of S in the category D-Graph:

π D (S ) = π D (L) π D (R).
Note that the core of a rule scheme is the rule built by deleting the labels part on W. For instance, the rule of Figure 21b is the core of the rule scheme from Figure 21a. To apply a rule scheme to a graph, we instantiate each graph of the rule thanks to a product with the same pattern graph. The definition of rule scheme instantiation is well-founded.

Proof. Since the pattern graph P and the rule schemes are defined on the same set of words W, the products are well-defined.

Example 13 (Instantiation of a Rule Scheme). Figure 22 shows the instantiation of the rule scheme from Figure 21a with the pattern graph of Figure 19. Note that the instantiation of the graph scheme in Figure 20 is the instantiation of the right-hand side of the rule and that we do not detail the instantiation of the left-hand side.

We now explain how the instantiation of a rule scheme can be used to obtain a rule that is applicable to a combinatorial graph.

Application of rule schemes

The application of a rule scheme S to a D-combinatorial graph G is done in a series of steps. First, a pattern graph P = (V P , E P , s P ,t P , l P ) for S is built from G. This construction essentially relies on the replacement of G by its W-transitive closure. The idea is to replace any path v v in G labeled by a word w of W by an arc e ∈ E P such that s P (e) = v, t P (e) = v and l P (e) = w. Formally, the construction is achieved using a functor. Definition 20 (Pattern Functor). Let D be a finite set of dimensions and W a finite set of words in D * .

The W-pattern functor is the functor P : D-Graph → W-Graph from D-combinatorial graphs to W-pattern graphs defined as follows:

• For a D-combinatorial graph G, the W-pattern graph P(G) has the same nodes as G and, for w ∈ W, a w-arc of source v 1 and target v 2 whenever there is a w-path v 1 w v 2 in G.

• For a D-combinatorial graph morphism m : G → F, the W-graph morphism P(m) : P(G) → P(F) has the same node morphism as m and an edge morphism that sends the unique w-arc of source v in P(G) to the unique w-arc of source v in P(F).

Proof. Let G be a D-combinatorial graph, then for all v in v G and all w ∈ W, there exists a unique path p of source v and labeled w in G. Therefore, the functor is well-defined on objects. Furthermore, the uniqueness of w-path in G yields uniqueness of w-arcs in P(G), for each node of G. Thus, the functor is well-defined on morphisms. To be able to apply a rule scheme on a graph G , we still need to ensure that the instantiation of the left-hand side of the rule scheme produces a graph that can be matched in G . Therefore we will now make precise the two following points:

• A selection mechanism should specify what part of the P(G ) will be used as the pattern graph.

• A method should specify how to construct the match from the instantiated rule.

Let us first deal with the selection mechanism and assume we want to apply the transformation to a topological cell in an object modeled by a graph G , i.e., a maximal subgraph built using a subset of the labeling alphabet. We may not know all the nodes in the graph affected by the transformation, but we know for sure that the nodes corresponding to the cell are concerned. If we specify one node that must be in the transformed part of the graph, then the transformed part is the subgraph of P(G ) containing the node and all nodes reachable to and from this node. Formally, let us define P v (for a node v in G ) as the maximal subgraph of P(G ) such that v is in P v and, for all arcs e such that s(e) or t(e) is in P v , then e, s(e), and t(e) are in P v . For all nodes v in G , there is a unique graph P v and a unique inclusion p v : P v → P(G ).

Example 14 (Pattern Functor). Consider the combinatorial graph depicted in Figure 23a. The application of the W-pattern functor for W = {ε, 21, 21} yields the W-graph of Figure 23b. The 3-arcs are discarded. Each node is the source of an ε-loop, the 21 and 21-paths are turned into arcs. The application of the pattern functor results in three strongly connected components. The left one corresponds to P g and P h , the middle one to P a , P b , P c and P d , and the right one to P e and P f . Note that the middle one corresponds to the pattern graph of Figure 19. For each node v from G , the pattern graph P v is unique. Given a graph scheme L from a rule scheme S , the product of the embedded pattern graph E D (P v ) and L is also unique. Therefore, given a node v from G , the instantiation ι(L, P v ) is unique. However, node v from P v may have been duplicated in the product construction. Indeed, node v yields as many nodes in the product as nodes in L. Nevertheless, if we identify a node v L among the nodes of L that we call a hook, the product yields a unique node (v, v L ).

Let us assume that the maximal subgraph of ι(L, P v ) containing the node (v, v L ) is actually ι(L, P v ), i.e., ι(L, P v ) is connected. If there is a mono ι(L, P v ) → G mapping (v, v L ) to v, then the morphism is unique. This uniqueness comes from the incident arcs condition verified by G . Indeed, each arc incident to (v, v L ) can only be sent to the unique arc incident to v with the same label. The mapping of the arcs incident to (v, v L ) provides a mapping of the nodes adjacent to (v, v L ). There is a unique way to propagate this mapping and we get the uniqueness on m : ι(L,

P v ) → G such that m((v, v L )) = v.
Example 15 (Construction of the Match). If we identify y as a hook in the left hand side of the rule scheme of Figure 22, then the node (y, a) is uniquely defined in the instantiated rule of the same figure. As we can see, there is a unique mono ι(L, P a ) → G (where G is the combinatorial graph of Figure 23a) that maps (y, a) to a. It is the mono that maps (y, a) to a, (y, b) to b, (y, c) to c, (y, d) to d and the arcs accordingly. The morphism is depicted by the grey dashed arrows in Figure 24.

Note that if ι(L, P v ) is not connected, there might not be uniqueness of the mono ι(L, P v ) → G . For instance, if two distinct components of ι(L, P v ) are isomorphic, we can exchange their image and get another mono. This limit can be bypassed whenever the partition arises from L. In this case, if we identify one hook pair (v, v L ) per component of L such that all the corresponding pattern graph P v 's are isomorphic, we restore the uniqueness of the mono. Note that the construction of the pattern graph guarantees that it is connected. The embedding functor construction ensures every arc incident to each node of L is associated with a unique arc in E D (P v ). Therefore, the specification of hook pairs is sufficient to guarantee the uniqueness of match, should it exist. In this case, the local propagation exploiting the incident arcs property provides an algorithm to build the match.

As the instantiation mechanism is rather general, it can produce rules that may not be applicable in some cases. We could impose conditions on the labels used in the rule scheme, but we may unnecessarily restrict our framework expressiveness. Therefore, we believe it is up to the user to check on examples that any written rule corresponds to the desired operation. We have discussed how we can apply a rule scheme to a combinatorial graph; let us now wrap up the whole process. To apply a (W, D)-rule scheme S to a D-combinatorial graph G , we first extracted a pattern graph P from G . This pattern graph P is built in two steps: the application of the W-pattern functor and the choice of inclusions p v : P v → P(G ) (i.e., the choice of a node v in V G for each hook in L) to specify where the operation should be done. With this pattern graph, we instantiate the (W, D)-rule scheme to get a D-rule. Thanks to the hook nodes in L, we construct the unique mono m : ι(S , P) → G and finally realize the direct derivation G ⇒ ι(S ,P),m H . An example of the complete pipeline is given in Figure 25 where both the hook node in the rule scheme and the chosen node in the combinatorial graph are filled in green. The transformation in the graph is put forward by the red coloring.

The complete construction can be summarized by the following commutative diagram:

1 W×D E D (P v ) L • K R P v E D (P v ) × L • E D (P v ) × K E D (P v ) × R P(G ) ι(L • , P v ) ι(K, P v ) ι(R, P v ) G D H ! E D (Pv) ! L • ! K ! R p v E D π D π D π D m P
where L • means that L has a hook per connected component. The top span L • ← K → R is the rule scheme. The second span P v × L • ← P v × K → P v × R is obtained by the product with P v (a subgraph of the embedding of G ). The third span is obtained with the projecting functor and yields the last span by standard DPO-rewriting.

As a final remark, let us point out that the set of words W has been given a priori for the rule scheme and the pattern graph. As of now, a W is just a superset of all words used to label a given W-pattern graph or the (W, D)-graph schemes of a rule scheme. In the following three sections, we will impose conditions on W to lift the condition for the preservation of our three elementary constraints. Nonetheless, the choice of W inherently comes from the transformation that we want to describe through the rule scheme.

Incident arcs consistency in rule schemes

We now lift the incident arcs condition from D-combinatorial rules to rule schemes. Since rule instantiations are essentially defined through a product, it is natural that each of the two members of the product should be subject to conditions to ensure that the resulting instantiation fulfills the intended incident arcs condition. Therefore, we will start by defining a first condition for the pattern graphs and a second one for the rule schemes. Afterward, we will show that, under such hypotheses, the instantiation of a consistent rule scheme via a consistent pattern graph yields combinatorial rules.

Definition 21 (Incident Arcs Constraint for Pattern Graphs). A W-pattern graph P = (V P , E P , s P ,t P , l P ) satisfies the incident arcs constraint I P (W) if every node v in V P is the source of a unique w-arc and the target of a unique w-arc for each word in W.

Note that when the pattern graph P is defined as a maximal subgraph of a D-combinatorial graph G generated from a given node and the words of W, P trivially satisfies the incident arcs constraint for pattern graphs I P (W). For instance, the pattern graph from Section 6 (see Figure 19) satisfies the incident arcs constraint for pattern graph on the set of words {ε, 21, 21}. Let us point out that the incident arcs constraint on pattern graphs guarantees that when building a product using such a pattern graph, all arcs of a graph scheme have a corresponding arc for each node in the embedded pattern graph. Let us now introduce a counterpart condition for rule schemes: Definition 22 (Incident Arcs Condition for Rule Schemes). A (W, D)-rule scheme S = L R satisfies the incident arcs condition I S (i) for a dimension i in D if the core π D (S ) of S satisfies the incident arcs condition I π D (S ) (i). If the core π D (S ) of S is a D-combinatorial rule, S is said to be a (W, D)-combinatorial rule scheme.

In other words, a (W, D)-rule scheme S satisfies I S (i) for a dimension i in D if :

1. Any preserved node of π D (L ∩ R) is the source (resp. target) of an i-arc in π D (L) if and only if it is the source (resp. target) of an i-arc in π D (R).

2. π D (L) satisfies I (V L \V R ),π D (L) (i). 3. π D (R) satisfies I (V R \V L ),π D (R) (i).
Let us recall that the first two sub-conditions concern the weak-incident arcs conditions, while the last one is equivalent to the dangling arc condition (also called gluing condition).

Example 16 (Incident Arcs Condition for Rule Schemes). The rule scheme from the previous section (see Figure 21a) satisfies I S ({1, 2}). The core of the rule scheme is given in Figure 21b. Node y belongs to the interface. It is the source of a 1-loop in L. It is also the source and target of an i-arc in R. Thus, the first sub-condition holds. There is no deleted nod. The added node x is the source of a 2-loop and the source and target of a 1-arc. Thus the second and the third sud-conditions also hold. In the end, the rule scheme is a {ε, 21, 21}, {1, 2})-combinatorial rule scheme.

Theorem 4 (Lifting the Incident Arcs Condition to Rule Schemes). Let i be a dimension in D and S = L R be a (W, D)-rule scheme.

The rule scheme S satisfies incident arcs condition I S (i) if and only if for all W-pattern graph P that satisfies the incident arcs constraint I P (W), the scheme instantiation ι(S , P) satisfies the incident arcs condition I ι(S ,P) (i).

Proof. Let S = L R be a (W, D)-rule scheme and i ∈ D be a dimension.

(⇒). Assume that the core π D (S ) of S satisfies the incident arcs condition I π D (S ) (i). Consider a W-pattern graph P that satisfies the incident arcs constraint I P (W).

Let K = L ∩ R be the interface of the rule scheme, p k be the morphism E D (P) × (W×D) K → E D (P), p r be the morphism E D (P) × (W×D) R → E D (P), k p be the morphism E D (P) × (W×D) K → K, r p be the morphism E D (P) × (W×D) R → R, such that the morphisms come from the following products:

E D (P) × (W×D) K E D (P) × (W×D) R K E D (P) R k p p k p r r p
Sub-condition 1 of the weak incident arcs condition.

Let v be a preserved node of ι(K, P). Thus, v is a preserved node of E D (P) × (W×D) K and there are two nodes a in E D (P) and u in K such that p k (v) = a and k p (v) = u. If v is the source of an i-arc in ι(L, P) then there is a word w in W such that v is the source of an arc labeled (w, i) in E D (P) × (W×D) L. By construction of the product, there is an arc of source a in E D (P) and an arc of source u in L both labeled (w, i). Since π D (S ) satisfies the incident arcs condition I π D (S ) (D), there is a word w in W such that u is the source of an arc labeled (w , i) in R. Since P satisfies the incident arcs constraint I P (W), the embedding functor E W ensures the existence of an arc labeled (w , i) in E D (P) of source a. Therefore, v is the source of an arc labeled (w , i) in E D (P) × (W×D) R, transformed into an i-arc in ι(R, P) by the projecting functor.

The proof holds for the target of an i-arc in ι(L, P) and for the source or target of an i-arc in ι(R, P). Thereafter, any preserved node of ι(K, P) is the source (resp. target) of an i-arc in ι(L, P) if and only if it is the source (resp. target) of an i-arc in ι(R, P). Sub-condition 2 of the weak incident arcs condition.

Let v be an added node of ι(R, P) \ ι(K, P). Thus, v is a node of E D (P) × (W×D) R \ E D (P) × (W×D) K and there are two nodes a in E D (P) and u in R \ K such that p r (v) = a and r p (v) = u. Since π D (S ) satisfies the incident arcs condition I π D (S ) (D), u is the source of a unique i-arc in π D (R). This i-arc yields an arc labeled (w, i), for a word in w in W, that is the only arc in R of source u having i as the second part of its label. Since P satisfies the incident arcs constraint I P (W), the embedding functor E W ensures the existence and uniqueness of a (w, i)-arc of source a. Therefore, there is an arc labeled (w, i) of source v in E D (P) × (W×D) R and it is the only arc of source v having i as the second part of its label. This arc is transformed into an i-arc in ι(R, P) by the projecting functor. Thus, there is a unique i-arc of source v in ι(R, P).

The proof holds for an i-arc of target v. Thereafter, any added node of ι(R, P) \ ι(K, P) is the source (resp. target) of a unique i-arc and ι(S , P) satisfies sub-condition 2 of the weak incident arcs condition.

Dangling condition.

The proof for a node deleted from ι(L, P) \ ι(K, P) is the same as the proof for a node added in ι(R, P) \ ι(K, P).

Thereafter, ι(S , P) satisfies the incident arcs condition I ι(S ,P) (D).

(⇐).

Assume that for all W-pattern graph P that satisfies the incident arcs constraint I P (W), the scheme instantiation ι(S , P) satisfies the incident arcs condition I ι(S ,P) (D).

In particular, consider the terminal graph 1 W . Then ι(S , 1 W ) is the core π D (S ) of S . Thus π D (S ) satisfies the incident arcs condition I π D (S ) (i).

Thereafter, the rule scheme S satisfies incident arcs condition I S (i).

Provided that pattern graphs and rule schemes satisfy certain conditions, which can be verified by direct static analysis, then Theorem 4 states that all rules obtained by instantiation verify the incident arcs conditions.

Example 17 (Lifting the Incident Arcs Condition to Rule Schemes). The rule scheme from Figure 21 is a {ε, 21, 21}, {1, 2})-combinatorial rule scheme. Its instantiation with the pattern graph of Figure 19 yields the rule of Figure 22, which satisfies the incident arcs condition for the dimensions 1 and 2.

Likewise, we will study constraints on pattern graphs and conditions on rule schemes for the non-orientation and cycle properties.

Non-orientation consistency in rule schemes

By analogy with the extension of the incident arcs condition, we study the condition of non-orientation. First, we give a constraint on pattern graphs and a condition on the rule schemes such that scheme instantiation produces a rule that satisfies the non-orientation condition.

Definition 23 (Non-Orientation Constraint for Pattern Graphs). A W-pattern graph P satisfies the non-orientation constraint O P (W) if for every w in W, w is also in W and every w-arc in P admits a reverse w-arc.

If the pattern graph P is built on a D-combinatorial graph G that satisfies the non-orientation constraint O G (D), then P trivially satisfies the non-orientation constraint for pattern graphs O P (W). For instance, the pattern graph from Section 6 (see Figure 19) satisfies the non-orientation constraint for pattern graph on the set of words {ε, 21, 21}. The non-orientation constraint on pattern graphs ensures that, for all words w in W, arcs labeled w and w in the graph scheme yields arcs and reverse arcs in the product construction.

Definition 24 (Non-Orientation Condition for Rule Schemes). A (W, D)-rule scheme S = L R satisfies the non-orientation condition O S (i) for a dimension i in D if :

• The core π D (S ) of S satisfies the non-orientation condition O π D (S ) (i).

• For any arcs e and e in S such that1 l π D (S ) (π D (e)) = l π D (S ) (π D (e )) = i and e is the reverse arc of e in π D (S ), then l π W (S ) (π W (e)) is the conjugate of l π W (S ) (π W (e )).

Example 18 (Non-Orientation Condition for Rule Schemes). The rule scheme given in Section 6 in Figure 21a satisfies the non-orientation condition O S (1). Indeed, its core rule (see Figure 21b) contains a 1-loop in L and two reverse i-arcs in R. The 1-arcs in the right hand side of the core rule are (1, ε)-arcs in the rule scheme, thus the parts of the label on W are conjugate words.

Theorem 5 (Lifting the Non-orientation Condition to Rule Schemes). Let i be a dimension in D and S = L R be a (W, D)-combinatorial rule scheme.

The rule scheme S satisfies the non-orientation condition O S (i) if and only if for all W-pattern graph P that satisfies both the incident arcs constraint I P (W) and the non-orientation constraint O P (W), the scheme instantiation ι(S , P) satisfies the non-orientation condition O ι(S ,P) (i).

Proof. Let i be a dimension D and S = L R be a (W, D)-combinatorial rule scheme.

(⇒). Assume that the rule scheme S satisfies the two sub-conditions and consider a W-pattern graph P that satisfies I P (W) and O P (W).

Without loss of generality, let us consider the case of ι(L, P) \ ι(R, P). Since π D (S ) satisfies O π D (S ) (i) and I π D (S ) (D), L \ R always contains an arc and its reverse. Theses arcs have conjugate words on the first part of their label. Because P satisfies O P (W), the product pairs these arcs with reverse arcs of π D (E D (P)). Thus, the product creates reverse arcs in ι(L, P).

Thereafter, ι(S , P) satisfies O ι(S ,P) (i).

(⇐).

Assume that for all W-pattern graph P that satisfies I P (W) and O P (W), the scheme instantiation ι(S , P) satisfies the non-orientation condition O ι(S ,P) (i). Similar to the proof of theorem 4, the terminal graph 1 W gives us the condition on the core of S .

For the second condition, consider an i-arc e in S such that π D (e) is an arc constrained by O π D (S ) (i). Note that since S is a (W, D)-combinatorial rule scheme, the reverse arc of π D (e) is unique (theorem 4). Let us assume that l π W (S ) (π W (e)) = w. Again, we build a scheme instantiation for S using a particular graph.

Intuitively, G w is composed of 3 occurrences of S W\{w,w} glued together with a www-cycle, like this : Formally1 , let G w = (V w , E w , s w ,t w , l w ) be the graph such that : • For any 1 ≤ k ≤ 3, for any w ∈ W, l w (e k,w ) = w .

• V w = {v 1 , v 2 , v 3 }. • E w = {e 1,w , e 1,
G w satisfies I P (W) and O P (W). In ι(S , G w ), e yields 3 arcs e 1 , e 2 , and e 3 labeled (w, i) and such that, for k = 1, 2 or 3:

s ι(S ,G w ) (e k ) = (v k , s S (e)), t ι(S ,G w ) (e k ) = (v k+1 ,t S (e)).
Because the scheme instantiation ι(S , G w ) satisfies the non-orientation condition O ι(S ,G w ) (i), the arcs e 1 , e 2 , and e 3 admit reverse arcs e -1

1 , e -1 2 , and e -1 3 . By construction of the product, they correspond to a (w, i)-arc in S . Call it a. Since π D (S ) satisfies O π D (S ) (i), π D (a) is a reverse arc of π D (e).

By unicity, l π W (S ) (π W (e)) is the conjugate of l π W (S ) (π W (a)) and a = e -1 . Thereafter, the rule scheme S satisfies the non-orientation condition O S (i).

Example 19 (Lifting the Non-orientation Condition to Rule Schemes). The rule scheme of Figure 21 satisfies the O S (1) while the pattern graph of Figure 19 satisfies O P ({ε, 21, 21}). Thus, the instantiated rule of Figure 22 satifies the non-orientation condition for D-rules O r (1).

We are left with the study of the cycle property for rule schemes.

Cycles consistency in rule schemes

Lifting the incident arcs condition and the non-orientation condition from rules to rule schemes was pretty straightforward. However, extrapolating the cycle condition relies on verifying whether a cycle in the scheme will be instantiated into a cycle. The three sub-conditions of the cycle condition for an instantiated rule relate to the arcs in ι(S , P). The issue is thus to be able to verify if a cycle in L or R yields a cycle in E D (P) × (W×D) L or E D (P) × (W×D) R without any prior knowledge on P. Intuitively, a pattern graph and a graph scheme can then be seen as two orthogonal spaces: a path containing only moves in the graph scheme stays on the same node from the pattern graph point of view and reciprocally. Thus, we understand that a path in the product of two graphs is a cycle if and only if it is a cycle in both graphs.

Global constraints on combinatorial graphs

The possibility of oriented arcs complicates the identification of cycles at the level of the rule scheme. To bypass this difficulty, we broaden the local study to a global one and fully state the conditions on all the dimensions. First, we split the dimension set D between the oriented dimensions O and the non-oriented dimension N so that 1 In the sequel, we will consider D ⊆ N, split into D = O N, and E ⊆ {(i, j) ∈ D 2 | i < j} as the set of exchangeable dimensions.

Path equivalence in combinatorial graphs

In this section, we will introduce a rewriting system on D * . For a complete study of string rewriting systems, we advise the reading of the first two chapters of [START_REF] Book | String-Rewriting Systems[END_REF]. Let us recall that a set A together with a binary relation -→ on A define an abstract reduction system (A, -→).

+

-→ is the transitive closure of -→ and * -→ is the reflexive and transitive closure of -→. An abstract reduction system is confluent whenever two elements obtained from the same ancestor have a common descendant. The system is noetherian if it contains no infinite reduction chain. A string rewriting system on an alphabet Σ is a binary relation on Σ * and defines a reduction system via sub-string rewriting.

The conjugate rewriting system for N and E is:

R N,E = {(i i, ε) | i ∈ D} ∪ {( ji, i j) | (i, j) ∈ (N ∪ O) 2 ∪ (N ∪ O) 2 , ( i , j ) ∈ E}.
Let us point out that R N,E is noetherian, but, for N > 1, R N,E is not confluent. The conjugate rewriting system encapsulates path reduction only based on their label. A word can be reduced to another if both words label paths with the same endpoints. The first part of the set definition of R N,E states that a possible simplification is the removal of two consecutive conjugate labels. When the label is in N, the simplification corresponds to the traversal of an arc and its reverse. When the label is in O, an arc is traveled back and forth. The second part of the set definition classifies which two consecutive dimensions can be inverted, exploiting the cycle constraint on the underlying graph. Lemma 3. For two words w and w in D * , we denote P(w, w ) the following property: For any combinatorial graph G satisfying O G (N) and C G (E), if there is a path v s w v t then there is a path v s w v t .

Let w and w be two words of D * . Then we have :

w * - → R N,E w ⇒ P(w, w ) Proof. Let G be a D-combinatorial graph satisfying O G (N) and C G (E)
, and let v be a node of G. Let us show the result of the lemma by induction on the number of steps in the reduction.

If there are no steps, w = w , and the result is trivial. Otherwise there exists a sequence of reduction:

w = w 0 - → R N,E w 1 - → R N,E w 2 - → R N,E . . . - → R N,E w k = w
for some k ≥ 1. Suppose there is a path v s w v t in G.

• If the reduction from w to w 1 is of the form (i i, ε) (with i in D), there exists w p and w s in D * such that w = w p i i w s and w 1 = w p w s . Let v be the target of the w p -path starting at v s . Since v satisfies I v (i), there exists a node v and an i-arc e such that s(e) = v and t(e) = v . Besides G satisfies O G (N). If i is in N then e admits a reverse i-arc e , otherwise i corresponds to the reverse traversal of e. Either way, i i is a cycle and the target of the i i path of source v is v. Therefore the target of the w p path of source v is v s . We can remove the i i-cycle and the target of the w p w s -path of source v s is v t .

The case where i belongs to N and is a non oriented dimension is illustrated in the following figure:

The case where i belongs to O and is an oriented dimension is illustrated in the following figure:

• If the reduction from w to w 1 is of the form ( ji, ji) (with (i, j) in E), there exists w p and w s in D * such that w = w p jiw s and w 1 = w p i j w s . Let v be the target of the w p -path starting at v s , and v be the target of the ji-path starting at v. Because the w-path starting at v s has v t for target, the target of the w s -path from v is v t . Since G satisfies C G (E), v is the source of a ji ji-cycle. By unicity of the i and j arcs, the cycle contains v , yielding a ji-path from v to v. The reverse traversal of this path is an ji-path from v to v . Therefore, the target of the i j-path starting at v is v and we can conclude that the target of the path labeled w = w p i j w s starting at v s is v t .

The most generic case with both i and j being oriented is illustrated in the following figure:

By induction, since

w 1 * - → R N,E w k = w , there is a path v s w v t in G.
Note that the essential part of this lemma is about the possibility of switching two dimensions, which is a lot simpler without oriented dimensions. From this lemma, we can derive straightforward corollaries:

1. If w * ← → R N,E w then, in any combinatorial graph G satisfying O G (N) and C G (E), there is a path v s w v t if
and only if there is a path v s w v t .

If w

* - → R N,E ε, then, in any combinatorial graph G satisfying O G (N) and C G (E), a w-path is a cycle.
3. These results extends1 to words ŵ and ŵ in W * , we consider the flatten word in D * to use the reduction system.

Preservation of consistency in rule schemes

The result of Lemma 3 can also be extended to W-pattern graphs obtained via the W-pattern functor on D-combinatorial graphs. A word ŵ in W * labels a path v s v t in a W-pattern graph P if and only if the flatten word labels a path v s v t in the underlying D-combinatorial graph G. Indeed the W-pattern functor extracts a subset of the node set of G and turns w-paths (for w in W) into w-arcs. Therefore, we can reduce flatten words of W * using R N,E and consider paths in P.

Definition 25 (Cycle Constraint for Pattern Graphs). A W-pattern graph P satisfies the cycle constraint C P (N, E) if it is coherent with R N,E : for all words w, w in W * , w can be rewritten as w by R N,E implies that for any w-path v s w v t in P, there is a w -path v s w v t in P.

The cycle constraint for pattern graphs is quite restrictive. Yet, if the pattern graph P is built on a Dcombinatorial graph that satisfies O G (N) and C G (E), then P satisfies the cycle constraint for pattern graphs C P (N, E) as a consequence of Lemma 3.

For instance, the pattern graph given in Figure 19 (see Section 6) satisfies the non-orientation constraint for the set of exchangeable dimensions {(1, 2)} and {1} as the set of non-oriented dimensions. Example 20 (Intuition for Cycle Preservation in Rule Schemes). Similar to the incident arcs and the nonorientation properties, we force the core of the rule to satisfy the cycle condition for D-rules. Consider the rule given in Figure 26a. It satisfies C r (1, 2) since the two 12-paths are coherent, and each node is the source of an optimal path. The two rules from Figure 26b and 26d have the previous D-rule as core rule. We consider their instantiation with the pattern graph given in Figure 26c. The instantiation of the first rule scheme (see Figure 26b) is given in Figure 27a. The coherent optimal paths in the core of the rule do not yield coherent paths in the instantiated rule. During the instantiation process, the product of the graph scheme with the embedded pattern graph creates an arc between nodes in the Cartesian product of the node sets whenever there is an arc with the same label in both graphs. Indeed, arcs in the pattern graph stand for paths in the underlying combinatorial graph. Thus, the W-part of the label in the graphs of the rule scheme indirectly represents the path in the combinatorial graph where we will apply the rule scheme. In the instantiated rule's left-hand side, we can find a 12-optimal path from (x, a) to (y, c), but we cannot find a coherent path in the right-hand side. Essentially the W-parts of the label misfit and provide different paths. Indeed the path abc in L (of Figure 26b) has 1 for W-label whereas the path aec in R has 11 for W-label. From Lemma 3, we know that we can prevent this from happening if we force coherent paths to have their W-part of label congruent for * ← → R N,E . To ensure the coherence of optimal paths, we extend the definition to rule schemes.

Definition 26 (Coherence of Optimal Path in Rule Schemes). Let S = L R be a (W, D)-combinatorial rule scheme. Two optimal paths p and p of π D (S ) are coherent in S if p and p are coherent in π D (S ) and

l π W (S ) (π W (p)) * ← → R N,E l π W (S ) (π W (p )).
Example 21 (Coherence of Optimal Path in Rule Schemes). The rule scheme of Figure 26d has coherent optimal paths. For instance, the 12-path abc has 1 for W-label in L whereas the 12-path aec has 11 1 * -→ R / 0,{(1,2)} 1 for W-label in R. Similarly, the paths de f (in L) and db f (in R) have 1 for W-label. The instantiated rule of Figure 27b preserves the coherence of optimal paths. For example, the optimal path (x, a)(x, b)(y, c) in L is coherent with the optimal path (x, a)(z, e)(y, c) in R. Likewise, the optimal path (y, d)(z, e)(z, f ) in L is coherent with the optimal path (y, d)(y, b)(z, f ) in R.

The cycle constraint on pattern graphs ensures that cycles from graph schemes will be associated with cycles in the embedded pattern graph, yielding cycles in the instantiated rule. • S is coherent with R N,E , i.e.:

-For any (i, j) in E, any coherent (i, j)-optimal path of π D (S ) is coherent in S .

-For any (i, j) in E, any concatenated word w labeling a cycle in π W (S ) corresponding to an i ji j-cycle in π D (S ) can be reduced to ε using R N,E . If the rule scheme S satisfies the cycle condition C S (E), then for all W-pattern graph P that satisfies I P (W), and C P (N, E), the scheme instantiation ι(S , P) satisfies the cycle condition C ι(S ,P) (E).

Proof. Let S = L R be a (W, D)-combinatorial rule scheme satisfying the non-orientation condition O S (N).

42

Let (i, j) ∈ E be a pair of dimension, p l be the morphism E D (P) × (W×D) L → E D (P), p r be the morphism E D (P)× (W×D) R → E D (P), l p be the morphism E D (P)× (W×D) L → L, r p be the morphism E D (P)× (W×D) R → R, such that the morphisms come from the following products:

E D (P) × (W×D) L E D (P) × (W×D) R L E D (P) R l p p l p r r p
Sub-condition 1 of the cycle condition.

Let p = v s v t be (i, j)-optimal path in π D (ι(L, P)). And denote p ι(L,P) the corresponding path in ι(L, P). Thus, v s and v t are nodes of E D (P) × (W×D) (L ∩ R) and there exist nodes a s , a t in E D (P) and u s ,

u t in L ∩ R such that p r (v s ) = a s , r p (v s ) = u s , p r (v t ) = a t and r p (v t ) = u t .
By construction of the product, the (i, j)-optimal path p yields two specific paths. One is an (i, j)-alternating path p P in π D (E D (P)), from a s to a t with the same label. The other is (i, j)-optimal path p π D (L) in π D (L), from u s to u t with the same label.

Because the core π D (S ) of S satisfies the cycle condition C π D (S ) (E), p π D (L) is coherent and there is an (i, j)-optimal path p π D (R) from u s to u t with the same label in π D (R). The paths in E D (P) and R create an (i, j)alternating path p in π D (ι(R, P)). By hypothesis on S , p ι(L,P) is coherent in S . Thus,

l π W (S ) (π W (p)) * ← → R N,E l π W (S ) (π W (p )). Because P satisfies C P (N, E) p is a path from v s to v t .
Since p π D (L) is optimal, the path p only contains added arcs and does not overlap. Besides, this path is maximal (if not it would be included in a path obtained from R, meaning p π D (L) was not coherent). Similarly, it cannot belong to a cycle, as such a cycle would come from R. Therefore p is optimal in π D (ι(R, P)) and coherent with p.

The reverse proof holds by symmetry and the scheme instantiation ι(S , P) satisfies sub-condition 1 of Definition 16.

Sub-condition 2 of the cycle condition.

Let v be a preserved node of (ι(L, P)) ∩ (ι(R, P)) that is the source of an i-arc in π D (ι(L, P)) \ π D (ι(R, P)). Therefore, there exist a node a in E D (P) and a node u in K such that p r (v) = a and r p (v) = u. By construction of the product, the existence of an i-arc of source v in π D (ι(L, P)) \ π D (ι(R, P)) means there is an i-arc in π D (E D (P)) of source a and an i-arc in π D (L) of source u. Since the core π D (S ) of S satisfies the cycle condition C π D (S ) (E), the i-arc in R either belongs to an i ji j-cycle or to an (i, j)-optimal path.

• Assume that the i-arc belongs to an (i, j)-optimal path. Because P satisfies I P (W), the (i, j)-optimal path in π D (R) can be associated with an (i, j)-alternating path of source a in E D (P). Similar to the proof for sub-condition 1, the paths in E D (P) and R yield an (i, j)-optimal path in ι(R, P).

• Otherwise, the i-arc extends to an i ji j-cycle. The concatenated word w in π W (R), corresponding to the cycle, can be reduced to ε using R N,E . Because P satisfies C P (N, E), w labels a cycle in P and thus in π W (E D (P)). The product construction keeps this cycle and π D (v) is the source of an i ji j-cycle in π D (E D (P) × (W×D) R).

Thus, the scheme instantiation ι(S , P) satisfy sub-condition 2 of Definition 16.

Sub-condition 3 of the cycle condition.

The proof is similar to sub-condition 2.

Thereafter, ι(S , P) satisfies C ι(S ,P) (E).

Note that Lemma 3 provides a formal characterization to describe which rule schemes always instantiate into consistent rules. Although the rewriting system is a valuable characterization, it is not confluent, and we would need a reduction strategy to use it in practice.

Combinatorial maps

Preservation of consistency for combinatorial maps

Recall that an n-G-map is a totally labeled

[[0, n]]-topological graph satisfying O G ([[0, n]]), I G ([[0, n]]), and C G ([[0, n]] +2 ) where [[0, n]] +2 denotes the dimensions i, j ∈ [[0, n]] such that i + 2 ≤ j. From Theorems 1, 2, and 3, if a rule r in the category of [[0, n]]-Graphs satisfies O r ([[0, n]]), I r ([[0, n]]) and C r ([[0, n]] +2 ), then the result graph H of the direct derivation G ⇒ r,m H is an n-G-map. Similarly, if a rule r satisfies O r ([[2, n]]), I r ([[1, n]]) and C r ([[1, n]] +2 ) then the graph H result of the direct derivation G ⇒ r,m H where G is an n-O-map is also an n-O-map.
Graph transformations built on production rules satisfying the appropriate conditions yield derivations preserving the topological constraints of the considered model. When extending rules to rule schemes, the verifications are lifted to the rule scheme level (Theorems 4, 5, and 6). In particular, the result from Theorem 4 ensures the dangling condition can be checked independently of the combinatorial map on which the rule scheme is applied.

G-maps and O-maps are defined by slightly different constraints, namely the orientation of the 1-arcs for the O-maps. These constraints yield different conditions for the preservation of the topological consistency when applying rule-based graph transformations. When trying to transpose the conditions to rule schemes, we need to cope with dimension conjugation. In the model of G-maps, the whole set D of dimensions is non-oriented, such that N = D and O = / 0. With N equals to D, the construction of rule schemes is drastically simplified, and we can do away with dimension conjugation. In the case of O-maps, D is split into N = D \ {1} and O = {1} meaning that we actually need to take care of the conjugation condition from Theorem 6.

When applying a rule scheme to an n-G-map or n-O-map, the pattern graph built during the application process inherits properties from the map. For instance, consider an n-G-map G. Thus any pattern graph P built on G with a set of words W satisfies the consistency constraint for pattern graphs I As a consequence, we can certify that a rule preserves the model's constraints. We provide algorithms to check this preservation similarly to Jerboa's syntactic analyzer. Jerboa's rule editor assumes a set-based representation of graphs: a graph is described as a set of nodes and a set of arcs. We can access nodes or arcs using their names or looping over the corresponding set and assume that the set of dimensions D is fixed.

The function providing all cycles of a graph can be obtained with a union-find strategy. Start with paths that consist of arcs labeled i and j and unify them recursively whenever one is the source of the other and the dimensions alternate. When the construction stops, the set of paths is pruned to keep only the cycles.

A rule L R consists of two graphs L = (V L , E L ) and R = (V R , E R ) where the preserved elements have the same nodes in both sides. Thus we can check if a node or an arc is preserved. Besides, we compute optimal paths for one side of a rule scheme. The function to compute optimal paths is similar to the construction of cycles, only considering non-preserved arcs. The obtained set of paths should also be pruned, in this case, to eliminate paths that are sub-paths of cycles. Since the rewriting system R N,E is noetherian, the set of normal forms for a word is finite and computable. However, because R N,E is not necessarily confluent, we may need to compute the complete collection of normal forms to check whether a word reduces to ε, or whether two words are congruent. In practice, the words on arcs are usually of length smaller than 2 or 3, and the concatenation along the path nearly always yields words of size at most 6 to 10. For simplicity, we denote N F R N,E (w) the set of normal forms for a word w from D * for the rewriting system R N,E .

The verification should first run Algorithm 1, then Algorithm 2 and Algorithm 3 as the last two algorithms assume that the input rule scheme satisfies the incident arcs condition. The algorithms only check for one dimension (resp. pair of dimension for the cycle condition) and, therefore, should be run on all dimensions relevant to the model. In Algorithm 1, we check the condition I S (i) for a rule scheme S and a dimension i from Definition 22. Lines 6 to 10, ensures that a preserved node is the source (resp. target) of an i-arc in the left-hand side if and only if it is the source (resp. target) of an i-arc in the right-hand side. Lines 13 to 17 ascertain that each added node is the source (resp. target) of an i-arc, i.e., π D (R) satisfies I (V R \V L ),π D (R) (i). Similarly, line 12 certifies that each deleted node is the source (resp. target) of an i-arc, i.e., π D (L) satisfies I (V L \V R ),π D (L) (i). This last sub-condition yields the dangling condition on the instantiated rule, which guarantees applicability (provided that an instantiation is possible).

foreach v ∈ V R do 14 if v ∈ V L then // Added node 15 S R ← {e ∈ E R | s R (e) = v and l π D (R) (e) = i} 16 T R ← {e ∈ E R | t R (e) = v and l π D (R) (e) = i}
In Algorithm 2, we check the condition O S (i) for a rule scheme S and a dimension i from Definition 24. This condition boils down to only having oriented arcs in the interface, where the definition of reverse arc is extended to encompass the conjugation of the W part of the label. In line 4, we construct the set of possible reverse arcs. The first three boolean conditions s L (e ) = t L (e), t L (e ) = s L (e), and l π D (L) (e ) = i ensure that the arcs are reverse arcs in the core π D (S ). These boolean conditions tackle the first sub-condition of Definition 24. The last boolean condition states that the reverse arcs in the core have conjugate labels, according to the second sub-condition of Definition 24. When we find one, we make sure that both have the same status (deleted or preserves) at lines 5 to 10. Otherwise, i.e., when the arc is oriented, we check whether it is preserved at line 12.

Algorithm 2: Check non orientation consistency for a dimension i. In Algorithm 3, we check the condition C S (i, j) for a rule scheme S and a pair of dimensions (i, j) from Definition 27. The condition is obtained from the condition for instantiated rules on the core of the scheme and an extension with the rewriting system. The sub-condition on the core (see Definition 16) is verified by lines 8 (path coherence), lines 24 to 27 and 30 to 32 (preserved nodes), lines 29 to 32 (added nodes). The extension with the rewriting system to coherence with R N,E is covered by lines 10 to 15 (path coherence) and lines 17 to 20 (cycles reduction to ε).

In Section 3, we talked about the quad subdivision operation dedicated to mesh refinement. The rule scheme of Figure 29 describes the subdivision operation for G-maps, while the one of Figure 30 illustrates it for O-maps.

Example 23 (Consistency verification of the quad subdivision operation for a 2-G-map (Figure 29)). The rule scheme S G is a ({ε, 0, 1, 2}, {0, 1, 2})-rule schemes. It satisfies I S G ({0, 1, 2}) since the preserved node a has incident non-oriented 0-, 1-, and 2-arcs in both L and R while added nodes b, c, and d have incident arcs for each dimension in {0, 1, 2}. All arcs are non-oriented and the only arcs with W label different from ε are loops. Thus, S G also satisfies O S G ({0, 1, 2}). Finally, S G also satisfies C S G ({(0, 2)}) because all nodes are sources of i ji j-cycles whose W label reduces to ε via R {0,1,2},{(0,2)} . For instance, the cycle (ε, 0)(2, 2)(ε, 0)(2, 2) of source a corresponds to a 0202 cycle. The {ε, 0, 1, 2}-part of the label is ε2ε2 = 22. Since 2 is non oriented, (22, ε) is a rewriting rule of R {0,1,2},{(0,2)} and the label reduces to ε. The execution of Algorithms 1, 2, and 3 The quad subdivision of the character presented at the beginning of the paper was realized with Jerboa. Jerboa [START_REF] Belhaouari | Jerboa: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF] is a generator of geometric modelers based on the work from [START_REF] Poudret | Topology-based geometric modelling for biological cellular processes[END_REF] and [START_REF] Poudret | Graph transformation for topology modelling[END_REF] for the framework of G-maps. This platform allows for the prototyping of dedicated modelers. In its current iteration, Jerboa supports the definition of modeler kernels using G-maps in any dimension. The rules are specified using variables [START_REF] Bellet | Designing a Topological Modeler Kernel: A Rule-Based Approach[END_REF] that can be simulated in our framework. Nodes of the rule with variables correspond to the nodes of the rule scheme. Any i-arc between nodes of the rules with variables is replaced by a (ε, i)-arc. A relabeling of a dimension i into a dimension j in a node variable yields a (i, j)-loop. Thus, we can write the rule scheme of Figure 29 in Jerboa (with a slightly different syntax). The currently implemented syntactic analyzer uses more restrictive conditions to preserve the model's consistency but will still consider the rule scheme consistent.

Example 25 (Rule scheme instantiation for the quad subdivision operation). The left-hand side of S G (Figure 29) contains a single node and arcs labeled (i, i) for each dimension i in {0, 1, 2}. Therefore, the instantiation with any pattern graph obtained via the {ε, 0, 1, 2}-pattern functor on a 2-G-map yields a graph equal (up to isomorphism) to the initial 2-G-map. The rule scheme instantiates into a rule that is always applicable. In practice, the selection mechanism of Section 6.3 makes the scheme rule applicable on a connected component. Thus, the instantiation left-hand-side of the rule scheme S G that contains a single node and three arcs produces a DPO-rule whose left-hand side contains 100680 nodes and 302040 arcs. Since the right-hand side of the scheme rule contains four nodes and 12 arcs (counting the non-oriented arcs as two arcs), the right-hand side of the instantiated DPO-rule contains 402720 nodes and 1208160 arcs. In practice, the application of such a scheme rule can be parallelized to speed up the computation time [START_REF] Bourquat | Transparent parallelization of enrichment operations in geometric modeling[END_REF]. Likewise, the left-hand side of S O (Figure 29) contains a single node and arcs labeled (i, i) for each dimension i in {1, 2}. For the same reasons, the instantiation on a pattern graph obtained by the associated functor will always yield a complete connected component in any 2-O-map. Therefore, the instantiated rule is always applicable.

The rule scheme S O of Figure 30 has non-loop arcs labels with (w, 2) where w is different from ε. Such a rule scheme is currently not supported in Jerboa (neither in the rule editor nor in the generic viewer that allows application of operations to objects).

Application example in topology-based geometric modeling

As explained in Section 3, n-G-maps and n-O-maps represent n-dimensional, or nD, objects. Topology-based modeling structures object by their cell subdivision and the adjacency relations between these cells. This subdivision represents the topological structure of the object. Any other type of information (e.g., the geometric shape) is called an embedding and attached to an orbit. Therefore, any modeling operation is defined by a topological transformation (e.g., subdivide a face) and an embedding transformation (e.g., translate a point). In this paper, we have only considered topological transformations.

(1) Although the work presented in this paper focuses on scheme rules dedicated to formalizing modeling operations, we also want to discuss the application of operations in the context of modeling an object. Modeled objects result from complex successive applications of several operations. Let us take the example of modeling a simplified house from Figure 31. From a square face, a pyramid is constructed by applying a cone extrusion operation. Topologically speaking, this operation creates as many faces as there are edges in the starting face (four edges in this case). All those faces are sewn along the starting face on a single point to create a cone. In a second step, all edges of the created volume are rounded, i.e., replaced by faces. Finally, the base of the house is constructed by applying an extrusion to the base square.

In geometric modeling, the most widespread practice consists of defining each operation algebraically before implementing it. The consistency preservation is hardly verified and comes with an expensive additional programming cost. Conversely, our approach takes care of operation genericity with the categorical product and the consistency preservation with the conditions on rules and rule schemes.

Let us use the whole pipeline of Figure 31 to illustrate operations. We will provide certain in 2D and others in 3D for both models. 2D operations only modify the outer surface on an object, making them easier to read and understand, whereas 3D operations also change the inner parts of objects.

Cone extrusion. The cone extrusion adds a new topological vertex and a triangular face for each edge of the original face. In 2D, this operation is restrained to only be applicable to isolated faces, i.e., faces that belong to a non-volume. We build the new vertex as the dual of the original face. Each vertex of the original face is linked to this dual vertex, resulting in triangular faces.

In a 2-G-map, isolated faces are represented by orbits on the dimensions 0, 1, and 2, where 2-arcs are loops. The left-hand side of the rule scheme depicted in Figure 32a encodes such an orbit. The (0, 0)-loops (resp. The rule scheme from Figure 37 is more complicated than its counterpart in the G-map model. Nonetheless, a formal description of the operation is precious to fulfill the need of the geometric modeling community, more likely to use the model of O-maps. Besides, consistency constraints on rule schemes help its writing. If one were to implement this topological operation in a programming language, it would result in a lot more development and debugging efforts.

We described a few operations in 2D and 3D for the models of G-maps and O-maps. Such topological operations, characteristics of geometric modelers, can easily be checked against the conditions provided previously in the article with the algorithms presented at the beginning of the Section.

Related works

Graph transformations were introduced to generalize Chomsky grammars to non-linear structures [START_REF] Ehrig | Introduction to the algebraic theory of graph grammars (a survey)[END_REF]. The algebraic approach to graph transformations uses production rules where the left-hand side and the right-hand side are graphs. The rules are applied using constructions from the theory of categories, namely single-pushout or double-pushout [START_REF] Ehrig | Tutorial introduction to the algebraic approach of graph grammars based on double and single pushouts[END_REF]. Formalizations based on graph transformations have been successfully achieved in many areas across computer science, such as database design [START_REF] Gyssens | A graph-oriented object database model[END_REF], concurrent and distributed systems [START_REF] Ehrig | Handbook of Graph Grammars and Computing by Graph Transformation: Concurrency, Parallelism, and Distribution[END_REF], software engineering [START_REF] Baresi | Tutorial Introduction to Graph Transformation: A Software Engineering Perspective[END_REF], IT landscape modeling [START_REF] Haeusler | ChronoSphere: a graph-based EMF model repository for IT landscape models[END_REF]. Essentially, graph transformations provide a safe framework to study the preservation of domain-related properties.

Sometimes, graph transformations do not allow for encapsulating a model or a theory completely. For instance, formal issues from a graph-based approach to geometric modeling cannot be solved directly with graph transformations. In such cases, the standard approach is to extend graph rewriting. To our knowledge, there are essentially two possibilities to conduct this extension: extend the category of graphs or extend the rewriting mechanism. Once the model is correctly defined within the adequate framework, the preservation of domain-related properties might still need to be answered. Application conditions [START_REF] Ehrig | Graph Grammars with Application Conditions[END_REF] provide the most common approach for consistency preservation, as they provide conditions to prohibit a rule from being applicable if its application would violate a given constraint.

In this section, we review extensions of graph rewriting, their use for consistency preservation, and, finally, some applications of graph transformations to geometric modeling. Note that application conditions are solely discussed as a means for consistency preservation.

Rewriting in different categories

The first solution to extend graph transformations replaces the category of graphs with a more general one. Such a replacement allows for the rewriting of objects that are not directly expressed as graphs. The most straightforward addition is that of labels (on nodes, arcs, or both), resulting in the category of labeled graphs. Labeled graphs can be further structured with the help of a type graph that describes relations on arcs and nodes based on their label. Type graphs are used to slice the category of labeled graphs, leading to particular typed-graph categories [START_REF] Corradini | Graph processes[END_REF]. Other kinds of high-level structures have also been used to replace graphs, such as hypergraphs or attributed graphs [START_REF] Löwe | An algebraic framework for the transformation of attributed graphs[END_REF][START_REF] Ehrig | Graphs, Typed Graphs, and the Gluing Construction[END_REF]. In each of these generalizations, the rewriting process is expressed as a single-pushout or double-pushout in the appropriate categories. Instead of considering a new category in which rewriting is proven to be well-defined, another approach is to study minimal properties, ensuring that graph-like transformations are well-defined. This line of research led to high-level replacement (HLR) systems and grammars [START_REF] Ehrig | From graph grammars to high level replacement systems[END_REF], adhesive categories [START_REF] Lack | Adhesive Categories[END_REF], adhesive HLR categories [START_REF] Ehrig | Adhesive High-Level Replacement Categories and Systems[END_REF]. Recently, a rewriting framework for abstract graphs (or objects from a topos) has been investigated in [START_REF] Corradini | Rewriting Abstract Structures: Materialization Explained Categorically[END_REF] to cover several previous works [START_REF] Bauer | Static Analysis of Dynamic Communication Systems by Partner Abstraction[END_REF][START_REF] Rensink | Neighbourhood Abstraction in GROOVE -Tool Paper[END_REF][START_REF] Steenken | Sound and Complete Abstract Graph Transformation[END_REF][START_REF] Backes | Analysis of Infinite-State Graph Transformation Systems by Cluster Abstraction[END_REF]. A first requirement is that (DPO) rewriting is well defined. Furthermore, the rewriting needs to meet certain requirements to be of practical interest. These requirements include well-known properties of rewriting systems, such as the local Church-Rosser, parallelism, concurrency, and amalgamation theorems [START_REF] Heckel | Confluence of Typed Attributed Graph Transformation Systems[END_REF][START_REF] Lack | Adhesive Categories[END_REF][START_REF] Ehrig | Adhesive High-Level Replacement Categories and Systems[END_REF].

We believe that replacing the category of edge-labeled graphs with a category tailored to our models might not be practical. We could have considered the category of G-maps (or O-maps) or the less specific category of D-combinatorial graphs. However, the left-hand and right-hand sides of rules would then belong to the category of D-combinatorial graphs. Production rules would always need to modify the complete connected component because of the incident arc constraint. In [START_REF] Habel | Relabelling in Graph Transformation[END_REF], the authors explain how to achieve relabeling of totally labeled graphs with rules expressed using the category of partially labeled graphs. Their approach allowed for relabeling a node even if all its incident arcs were not matched. Similarly, we modify D-combinatorial graphs with rules that are not expressed in the category of D-combinatorial graphs. In [START_REF] Habel | Relabelling in Graph Transformation[END_REF], the authors add two conditions on rules to ensure that the result of the derivation is totally labeled. Likewise, we provided conditions on rules (in Section 4) to guarantee that we derive D-combinatorial graphs. Essentially, despite the rule being expressed in the category of D-graphs, we presented conditions certifying that the result of the direct derivation belongs to the category of D-combinatorial graphs (more generally, the category of G-maps or O-maps). In Section 3, we discussed the possible generalization of the quad subdivision from a face to a surface, independent of the context and the underlying topology. This operation aims at subdividing surfaces for mesh refining. Each face of the mesh has to be subdivided. Since we are considering rewriting in the category of edge-labeled graphs, one could iteratively apply the operation on each face of the surface. Unfortunately, this approach would provide incorrect results as the subdivision of one face increased the number of edges on the surrounding faces, as explained in Example 26. Similarly, one could try to apply the operation on every face simultaneously. This approach is not conceivable because of the concurrent modification of edges.

In the sense of graph transformations, the transformations are neither sequentially nor parallel independent [START_REF] Ehrig | Introduction to the algebraic theory of graph grammars (a survey)[END_REF][START_REF] Ehrig | Graphs, Typed Graphs, and the Gluing Construction[END_REF][START_REF] Ehrig | M-adhesive transformation systems with nested application conditions. Part 1: parallelism, concurrency and amalgamation[END_REF]. Parallel-dependent transformations can be amalgamated to a transformation thanks to the amalgamation rule [START_REF] Boehm | Amalgamation of graph transformations: A synchronization mechanism[END_REF][START_REF] Ehrig | M-adhesive transformation systems with nested application conditions. Part 1: parallelism, concurrency and amalgamation[END_REF]. The computation of the amalgamation rule is done based on the transformations and principally used as a synchronization mechanism [START_REF] Taentzer | Amalgamated graph transformations and their use for specifying AGG -an algebraic graph grammar system[END_REF][START_REF] Rensink | Repotting the Geraniums: On Nested Graph Transformation Rules[END_REF]. Likewise, sequentially-dependent transformations can be reduced to a single transformation using the concurrency rule [START_REF] Ehrig | Parallelism and concurrency of graph manipulations[END_REF][START_REF] Ehrig | M-adhesive transformation systems with nested application conditions. Part 1: parallelism, concurrency and amalgamation[END_REF]. One way to use these results would be to decompose a transformation into simpler transformations (and use the results to aggregate these simple transformations into more complex ones). For instance, one could have built a transformation for one node and then applied it to each node of the topological cell. Such a solution would fulfill the needs of a geometric modeler, i.e., specifying modeling operations that do not depend on the underlying topology of the object under modification. Nevertheless, this solution would be ill-suited as we need to link elements that belong to copies of different nodes from the topological cell (see Section 3.3). Besides, one considering oriented maps, we need to link different copies of different nodes (which led us to introduce path-related abstraction in the product construction). Indeed, the amalgamation and concurrency theorems focus on graph transformation systems, although we are interested in providing a rule editor with compact and straightforward operations. Were the subdivision rule to be computed as the amalgamated rule, it would have to be recomputed for each application. Instead, we want to generalize the transformations to abstract a part of the object's topology. The preservation of the model consistency can therefore be checked once, at design time, on the generalized rule. Nonetheless, such results could be a real asset for our framework at the level of rule schemes, i.e., to apply them systematically with a particular purpose. For example, these results would allow the application of several modeling operations simultaneously and, perhaps, even compose our scheme rules.

Example 26 (Invalid sequential application of the quad subdivision). A sequential application of the face subdivision application is shown in Figure 38. This sequence of operations is incorrect. Indeed, the edge between the yellow and green faces is split twice. First, when the yellow face is subdivided (Figure 38b), thus yielding two edges. Second, when these two new edges are split again, and the green face is subdivided. As a result, three vertices are added instead of one.

Different kind of rewriting

Our approach is closer to the second solution to extend graph transformations: twisting the rewriting mechanism. Several constructions with implicit or explicit pullbacks have been defined to enrich DPO rewriting with cloning. For instance, the Sesqui-Pushout approach [START_REF] Corradini | Sesqui-pushout rewriting[END_REF] uses a final pullback complement as the left square in the rewriting step. The AGREE approach [START_REF] Corradini | Algebraic graph rewriting with controlled embedding[END_REF] relies on a morphism from the host graph to an enriched version of the left-hand side of the rule to specify how edges should be transformed. The Pullback-Pushout (PB-PO) approach [START_REF] Corradini | The PBPO graph transformation approach[END_REF] extends AGREE, capitalizing on two spans (intuitively two rules). The host graph is put in between the two spans of the left-hand side, yielding 4 commuting squares, one being a pullback and another being a pushout.

In AGREE [START_REF] Corradini | Algebraic graph rewriting with controlled embedding[END_REF], rules are local if they do not modify the strict complement of the left-hand side of the rule L in the host graph G. Therefore, even if cloning and merging are allowed, it can only occur in the image of L in G and the arcs incident to nodes in this image. The strict complement is defined as a pullback complement but can intuitively be understood as the biggest subgraph of G that contains no element from the image of L. Similarly, the PB-PO [START_REF] Corradini | The PBPO graph transformation approach[END_REF] approach can affect any element in the host graph G. This more general approach offers a more general definition of locality. This locality depends on a subgraph Γ of the left-hand side of the bottom span of the rule. Intuitively, a transformation is Γ-preserving if the transformation preserves this sub-object. However, the properties we want to preserve do not easily fit in either AGREE or PB-PO.

Our construction of product-based generalization of DPO via rule scheme can be seen as an attempt to combine enrichment with cloning and a categorical approach to relabeling. A categorical construction of relabeling in the DPO approach has already been realized in [START_REF] Schneider | Changing Labels in the Double-Pushout Approach Can Be Treated Categorically[END_REF]. The authors control the ambiguity of label changes by epi-mono factorization and the use of least-upper-bound on the set of solutions. The incident arcs constraint of D-combinatorial graphs removes that ambiguity. The relabeling only occurs on arcs in our specific framework while being entirely determined by the arc label. In that sense, arc relabeling coincides with a function on the label set. We showed that pair labels on arcs could encode such relabeling. The relabeling function is simulated by an embedding functor into the category where arcs are labeled with pairs, a product in this category, and a projecting functor back onto the category where arcs have a single label. Cloning and relabeling for G-maps have always been achieved in previous works [START_REF] Poudret | Topology-based geometric modelling for biological cellular processes[END_REF][START_REF] Poudret | Graph transformation for topology modelling[END_REF]. To deal with O-maps, we also need to consider paths. The navigational logic presented in [START_REF] Lambers | Towards a Navigational Logic for Graphical Structures[END_REF][START_REF] Navarro | A navigational logic for reasoning about graph properties[END_REF] allows reasoning about paths in a graph. However, this approach does not inherently support relabeling.

Consistency preservation in graph transformations

Twisting the rewriting mechanism allows for studying consistency preservation. For instance, application conditions hinder rule applicability, ensuring that the transformation of a well-formed object yields an equally well-formed object.

In general, such conditions are based on the existence (positive application condition) or non-existence (negative application condition, or NAC) of a given subgraph in the host graph. If this (non-)existence is fulfilled, the production rule can adequately be applied. As shown in [START_REF] Habel | Graph Grammars with Negative Application Conditions[END_REF], a colimit of the positive application conditions yields a rule applicable in the same context with only negative application conditions. Such conditions have proven helpful in many cases but too restrictive in others. They were extended to nested application conditions (or nested conditions) in [START_REF] Habel | Correctness of high-level transformation systems relative to nested conditions[END_REF] and shown to be expressively equivalent to first-order graph formulas, fulfilling the requirements presented in [START_REF] Rensink | Representing First-Order Logic Using Graphs[END_REF]. In [START_REF] Ehrig | M-adhesive transformation systems with nested application conditions. Part 1: parallelism, concurrency and amalgamation[END_REF], standard results were proven for rules with nested conditions. In particular, Local-Church Rosser, Parallelism, Concurrency, and Amalgamation theorems hold for rules with nested conditions in M -adhesive categories (a weaker form of adhesivity restricted to a subclass of monomorphisms). Application conditions offer mechanisms to repair a rule (with or without condition) if its application to a graph satisfying a constraint does not preserve the constraint. One solution is to declare the rule inapplicable whenever its application would result in an ill-formed graph.

Thanks to static analysis of rules with nested application conditions, one can derive correct transformation systems.

A first solution is to demonstrate that the output satisfies a postcondition, provided the input satisfies a precondition, and construct a weakest precondition relative to the postcondition. The proof that the precondition implies the weakest precondition yields the correctness of the program [START_REF] Dijkstra | A Discipline of Programming[END_REF]. The construction of weakest preconditions of a rule relative to a postcondition is discussed in [START_REF] Habel | Correctness of high-level transformation systems relative to nested conditions[END_REF] for nested application conditions; it uses shifts of conditions over rules and morphisms. Although each transformation and each condition are finite (i.e., are finite conjunction of conditions, each one being finitely nested), the actual complexity is never discussed. In particular, the resulting conditions showed as examples in [START_REF] Habel | Correctness of high-level transformation systems relative to nested conditions[END_REF] or in [START_REF] Ehrig | M-adhesive transformation systems with nested application conditions. Part 1: parallelism, concurrency and amalgamation[END_REF] seem to suggest that the complexity of the transformation is equivalent to the power set of the initial condition. Indeed, the shift over morphism considers all epimorphisms with the same domain. By duality, these epimorphisms essentially represent the category of sub-objects. Once the weakest precondition is obtained, one still has to show that the precondition on the graph implies the weakest precondition of the rule relative to the postcondition. Since nested conditions are equivalent to first-order formulas on graphs, this verification can be delegated to a solver. Following the work of [START_REF] Becker | Symbolic invariant verification for systems with dynamic structural adaptation[END_REF][START_REF] Becker | Iterative Development of Consistency-Preserving Rule-Based Refactorings[END_REF][START_REF] Dyck | Inductive Invariant Checking with Partial Negative Application Conditions[END_REF] (handling a subset of nested constraints), the solver can be used as a tool to build counterexamples. In these works, invariants are checked during the evolution of a system based on a set of rules, while we are interested in generic rules that are sure to preserve the consistency of the model.

Another well-known method to check the correctness of a program with respect to a precondition and a postcondition is to provide a proof system and show its soundness with respect to the operational semantics [START_REF] Hoare | An axiomatic basis for computer programming[END_REF]. In [START_REF] Poskitt | Hoare-Style Verification of Graph Programs[END_REF], the authors provide partial correctness of graph programs in the graph programming language GP [START_REF] Plump | The Graph Programming Language GP[END_REF] and show soundness with respect to the operational semantics of the language.

In [START_REF] Kosiol | Constructing Constraint-Preserving Interaction Schemes in Adhesive Categories[END_REF], the authors developed an approach to bypass the loss of applicability of rules with application conditions. The authors guarantee that a constraint holds by construction after transformation. Their idea is to transform the rule into a multi-rule to fix every possible way it could introduce a violation. The formalization is done in adhesive categories for rules that only create structures and constraints1 of the form ∀(P, ∃C) where P is a sub-object of C. The authors provide sufficient conditions for correctness. Note that their approach is not directly transposable for our purposes since our rules may delete structures, and we need to express uniqueness as a constraint. However, a rule (without condition) that can sometimes result in a well-formed graph and sometimes result in an ill-formed graph would be considered invalid in geometric modeling. In other words, a rule is valid if whenever there is a match from the left-hand side of the rule to a well-formed graph, the rule is both applicable and result in an equally well-formed graph. Let us consider the example of the gluing condition. It states that a rule is applicable whenever the match and the left morphism of the rule admits a pushout complement. When rewriting graphs, the conditions can be reduced to the dangling condition that essentially ensures that no unmatched arc loses its source or target. In the framework of nested application conditions, the gluing condition can be defined as a condition on the left-hand side of the rule. Thus, when the condition is not fulfilled, the rule is inapplicable. In our framework, the gluing condition can be checked on the rule (Fact 1). If L satisfies I (V L \V R ),L (D), we are guaranteed that any match to a D-combinatorial admits a pushout complement. Since we enriched DPO rewriting with a functorial approach and product construction, we needed to lift the consistency preservation from DPO-based rules to product-based rules. However, to our knowledge, there is no shift construction of nested application conditions for functors. As seen in Section 10, our very specific class of graphs (D-combinatorial graphs) support verification by static analysis, which essentially resides in a graph traversal. Thus, every possible instantiation of a given rule scheme creates a consistency preserving production rule.

Our approach is similar to the one developed in [START_REF] Biermann | Formal foundation of consistent EMF model transformations by algebraic graph transformation[END_REF] about consistent model transformations. In this article, the authors tackle consistency preservation in the ECLIPSE Modeling Framework (EMF). They provide a formalization of EMF model transformations that preserve EMF consistency (containment relations) with typed attributed graph transformations. This formalization revolves around six ad hoc conditions that define allowed transformations.

Graph transformations applied to topology-based geometric modeling

Numerous generic tools exploit the sound formalism of graphs transformations, such as PROGRES [START_REF] Schürr | Graph grammar engineering with PROGRES[END_REF], AGG [START_REF] Taentzer | AGG: A Graph Transformation Environment for Modeling and Validation of Software[END_REF], Groove [START_REF] Rensink | The GROOVE Simulator: A Tool for State Space Generation[END_REF], and GrGen.NET [START_REF] Geiß | GrGen: A Fast SPO-Based Graph Rewriting Tool[END_REF]. Graph transformations modify structures at a low level, making rules self-contained and applicable with a single rule application engine. A single rule application engine minimizes development and debugging needs and enables the development of dedicated tools, such as Fujaba [START_REF] Nickel | The FUJABA environment[END_REF] to refactor code, DiaGen [START_REF] Minas | DiaGen: a generator for diagram editors providing direct manipulation and execution of diagrams[END_REF] to edit diagrams, GReTL [START_REF] Ebert | GReTL: an extensible, operational, graph-based transformation language[END_REF] to manipulate metamodels, or Gremlin [START_REF] Rodriguez | The Gremlin graph traversal machine and language[END_REF] to query graph databases.

In computer graphics as well, formalizations have been accomplished with graph transformations. For instance, graph grammars were used for 2D shapes classification [START_REF] You | A Syntactic Approach to Shape Recognition Using Attributed Grammars[END_REF], plants multiscale modeling [START_REF] Ong | A graph model and grammar for multi-scale modelling using XL[END_REF], indoor scenes reconstruction [START_REF] Ikehata | Structured Indoor Modeling[END_REF], tunnels modeling process [START_REF] Vilgertshofer | Using graph rewriting methods for the semi-automatic generation of parametric infrastructure models[END_REF]. Previous works introduced a graph-based representation of G-maps for geometric modeling [START_REF] Poudret | Topology-based geometric modelling for biological cellular processes[END_REF] and used DPO graph transformations to design modeling operations [START_REF] Poudret | Graph transformation for topology modelling[END_REF]. In this article, we dealt with the topological part of geometric modeling. The representation of objects also relies on other data, such as vertex positions, edge curvature, or volume density. In topology-based geometric modeling, these data are referred to as embedding. In [START_REF] Bellet | Rule-based transformations for geometric modeling[END_REF], embeddings were defined as a family of node labels with appropriate consistency constraints and conditions. Since rules can modify both the topology and the embeddings of an object, conditions to preserve the embedding consistency in meta-rules were studied in [START_REF] Bellet | Geometric modeling: Consistency preservation using twolayered variable substitutions[END_REF]. In [START_REF] Poudret | Topology-based geometric modelling for biological cellular processes[END_REF], DPO rewriting was enriched with variables to construct meta-rules instantiated with a set-based operation similar to a pullback. In [START_REF] Poudret | Graph transformation for topology modelling[END_REF], sufficient consistency preservation conditions were introduced for DPO transformations, and only the incident arcs condition was lifted to meta-rules.

Jerboa [START_REF] Belhaouari | Jerboa: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF] has been developed, based on the work from [START_REF] Poudret | Topology-based geometric modelling for biological cellular processes[END_REF] and [START_REF] Poudret | Graph transformation for topology modelling[END_REF]. This platform allows for the prototyping of dedicated modelers for G-maps. To design a modeler with Jerboa, one has to specify the dimensions of the objects (2D, 3D, 4D), the embeddings (position, curvature, density), and the rule-based transformations. Jerboa has been successively used for several modelers: one dedicated to architecture [START_REF] Cardot | Persistent naming based on graph transformation rules to reevaluate parametric specification[END_REF], one for the simulation of plant growth [START_REF] Bohl | Modeling fruits and their internal structure using parametric 3gmap l-systems[END_REF], and another one for the analysis of soils in geology [START_REF] Gauthier | Développement d'un langage de programmation dédié à la modélisation géométrique à base topologique, application à la reconstruction de modèles géologiques 3D, These de doctorat[END_REF]. In its current iteration, Jerboa supports the definition of modeler kernels using G-maps in any dimension. In this paper, we replaced the topological variables of [START_REF] Bellet | Designing a Topological Modeler Kernel: A Rule-Based Approach[END_REF] with a product construction. The new approach has a more substantial relationship with categorical concepts thanks to graph products, terminal graphs, and functors. Our scheme rules subsume previous works and allow us to deal with the more popular model of O-maps. Therefore, an evolution of Jerboa seems conceivable to support both G-maps and O-maps, as well as the product construction of rule schemes.

Conclusion

Towards defining topological operations on combinatorial maps, we studied three constraints on arc-labeled graphs: the incident arcs constraint, the non-orientation constraint, and the cycle constraint. We defined constraintpreserving DPO rules thanks to necessary and sufficient conditions allowing for rules to be statically checked. Thus, the study englobes both the G-map and the O-map models. To our knowledge, this is the first time that geometric modeling operations for O-maps are described using graph transformations.

Any framework dedicated to geometric modeling should be as unified as possible. Similar to certain implementations that allow several combinatorial models to coexist, this framework should encompass several combinatorial models. Hence, the unification of the G-maps and the O-maps in a single framework is already an exciting result to promote formal methods and, more specifically, graph transformations in geometric modeling.

We also enriched DPO rewriting for arc-labeled graphs with categorical constructions so that the designed rules are generic with respect to the underlying topology of the object. The extrapolation is based on functors to embed the transformation in a different category of labeled graphs. Then, we encode functions to describe how the operation should be carried out. Applying these functions is simulated with the categorical product to instantiate the more abstract rule schemes. We discussed how to unambiguously instantiate such rule schemes for a given combinatorial graph (and a fortiori for a given G-map or O-map). We also lifted the consistency conditions from DPO rules to rule schemes, although we lost the necessity of the cycle condition. We provided algorithms describing a static analyzer for consistency preservation. Finally, we gave a representative example of a pipeline for the modeling of a geometric object.

As a result of our new approach, closer to algebraic transformation formalism, we plan to extend the current version of the Jerboa platform. In order to be able to develop such a new platform, we will first need to provide conditions to preserve the embedding consistency, i.e., ensure that the transformation of a geometrically correct object yields an equally well-formed object.

Assumption 1 .

 1 Matches are monomorphisms.Matching the left-hand side L of a rule in a graph G is the first step towards the transformation of G. Still, we need to explain how to disconnect and reconnect graphs.Definition 4 (Direct Derivation). Let G and H be two graphs, r = L ← K → R and m : L → G a match for r. The rule r transforms G into H, if there is a diagram are pushouts. The direct derivation G ⇒ r,m H exists and is unique (up to isomorphism) if m satisfies the gluing condition. The morphism m : R → H is called the comatch of the derivation.

Figure 1 :

 1 Figure 1: DPO transformation for relabeling.

Figure 2 :

 2 Figure 2: Pullback using a terminal graph.

Figure 3 :

 3 Figure 3: Deletion of 2-arcs using a product in the category [[1, 3]]-Graph.

Figure 4 :

 4 Figure 4: Global relabeling with a product.

Definition 7 (

 7 Pattern Graph). Let D be a finite set of integers, and let W be a finite subset of D * . A W-pattern graph is a graph from the category W-Graph.

  (a) A [[1, 3]]-graph. (b) A {13, 2}-graph.

Figure 5 :

 5 Figure 5: Our main consideration for the label sets.

Figure 6 :

 6 Figure 6: A [[1, 3]]-graph.

Figure 7 :

 7 Figure 7: An object and its representation as a 2-O-map (middle) and a 2-G-map (right).

  Two faces sharing an edge.

  Decomposition along dimension 0 and resulting 2-G-map.

Figure 8 :

 8 Figure 8: Decomposition of an object and construction of the underlying G-map.

Figure 9 :

 9 Figure 9: Decomposition of an object and construction of the underlying O-map.

Figure 10 :

 10 Figure 10: Quad subdivision of a face.

  G-map decomposition of the face subdivided in Figure10. Maximal rule to obtain the transformation.

Figure 11 :

 11 Figure 11: Quad subdivision of a face as a graph transformation.

Figure 12 :

 12 Figure12: Generalization of the quad subdivision using copies and relabeling.

Figure 13 :

 13 Figure 13: Quad subdivision of a surface.

Figure 15 .Figure 14 :

 1514 Figure 14: A rule satisfying the incident arcs condition for the dimension 2.

Figure 15 :

 15 Figure 15: Incident arcs preservation.

Theorem 2 (

 2 Non-Orientation Preservation). Let r = L R be a D-combinatorial rule. The rule r satisfies the non-orientation condition O r (i) if and only if for all matches m : L → G on a D-combinatorial graph satisfying O G (i), the result graph H of the direct derivation G ⇒ r,m H satisfies the non-orientation constraint O H (i). Proof. Let r = L R be a D-combinatorial rule.(⇒). Suppose r satisfies the non-orientation condition O r (i).

  Thus, there exists e G ∈ G such that e G = e -1 H in G. (a) If e G ∈ G \ m(L), both arcs are left unchanged by r, i.e., e H and e G = e -1 H are in H. (b) Otherwise, there exists e in L such that m(e ) = e G . Because G is a combinatorial graph and e H is in G \ m(L), e is oriented in L. Since r satisfies O r (i), e is in L ∩ R. Therefore, m (e ) = e G = e -1 H in H, by injectivity of m . 2. Otherwise, e H ∈ m (R) and, by injectivity of m , there exists a unique e ∈ R such that m (e) = e H . (a) If e admits a reverse arc e in R, then m (e ) is the reverse arc of e H in H. (b) Otherwise, similarly to case 1b, e is an oriented arc of L ∩ R. The arc e cannot have a reverse arc in L, as this arc would be in E L \ E R and would break the non-orientation condition on r. Since e is in L, m(e) = e H . The non-orientation constraint in G yields an arc e G reverse of e H in G. This arc has no antecedent in L and belongs to G \ m(L)

Figure 16 :

 16 Figure 16: i j-completion of a rule: implicit arcs in an i ji j-cycle are added.

Figure 17 :

 17 Figure 17: A rule preserving the cycle constraint for the dimensions 1 and 2.

Figure 18 :

 18 Figure 18: Rules that satisfies the cycle condition C r (1, 2).

  a) If no arc of this cycle is in m(L \ R), then this cycle is left unchanged by the rule and v H is the source of the same i ji j-cycle in H. (b) Otherwise, certain parts of the cycle are in m(L \ R). Because v H is in G \ m(L), two nodes m(v s ) and m(v t ) satisfies : • Nodes m(v s ) and m(v t ) belong to the cycle. • Nodes m(v s ) and m(v t ) are in m(L ∩ R).

Definition 17 (

 17 Conjugate Dimensions). For any d ∈ D, we define the conjugate dimension d which yields the conjugate alphabet D = D ∪ {d | d ∈ D}.

  provides an example of a {ε, 21, 21}-pattern graph where nodes a, b, c and d are the sources of a singe ε-arc, a single 21-arc and a single 21-arc.

Figure 19 :

 19 Figure 19: A pattern graph.

  graph scheme Π is built on the graph from Figure2and depicted on the right. Arc labels are extended as follows: the 2-loop is turned into a (21, 2)-loop on x whereas the 1-arcs are replaced by (ε, 1)-arcs. The product E D (P) × (W×D Π of E D (P) and Π is shown in the center of the figure. Applying the projecting functor erases the first part of the labels and yields ι(Π, P) = π D (E D (P) × (W×D) Π), the top graph of Figure 20.

Figure 20 :

 20 Figure 20: Instantiation of a graph scheme.

Figure 21 :

 21 Figure 21: A ({21, ε}, {1, 2})-rule and its core.

Figure 22 :

 22 Figure 22: Instantiation of a rule scheme.

Figure 23 :

 23 Figure 23: A {1, 2, 3}-combinatorial graph (a) and its image by the {ε, 21, 21}-pattern functor (b).

Figure 24 :

 24 Figure 24: Mono from the instantiated left-hand side of the rule to the combinatorial graph.

Figure 25 :

 25 Scheme Instantiation

  w , e 2,w , e 2,w , e 3,w , e 3,w } ∪ E 1 ∪ E 2 ∪ E 3 where E k = {e k,w | w ∈ W \ {w, w}} for k = 1, 2 or 3. • s w (e k,w ) = v k , s w (e k,w ) = v k+1 , and s w (e ∈ E k ) = v k for k = 1, 2 or 3. • t w (e k,w ) = v k+1 , t w (e k,w ) = v k , and t w (e ∈ E k ) = v k for k = 1, 2 or 3.

  O N = D (meaning D = N O O). Furthermore, we denote d the integer value of d, ie d = d if d is in D and d = d if d is in O. Therefore, conjugation is a bijection on D * such that d = d for d in O and d = d for d in N.

Figure 26 :

 26 Figure 26: Two rule schemes with the same core and a pattern graph for instantiation.

Figure 27 :

 27 Figure 27: Instantiation of the rule schemes from Figure 26 with the pattern graph of Figure 26c.

Definition 27 (

 27 Cycle Condition for Rule Schemes). A (W, D)-combinatorial rule scheme S = L R satisfies the cycle condition C S (E) if : • The core π D (S ) of S satisfies the cycle condition C π D (S ) (E).

Figure 28 :

 28 Figure 28: A rule scheme satifying C S (1, 2).

  P (W), O P (W), and C P ([[0, n]], [[0, n]] +2 ). Therefore the instantiation of any rule scheme S that satisfies I S ([[0, n]]), O S ([[0, n]]), C S ([[0, n]] +2 ) yields a rule ι(S , P) that satisfies the conditions O ι(S ,P) ([[0, n]]), I ι(S ,P) ([[0, n]]) and C ι(S ,P) ([[0, n]] +2 ). Therefore any direct transformation on any instantiation of the rule scheme results in an n-G-map. Similarly, rule schemes satisfying the appropriate conditions yield instantiations that transform n-O-maps into n-O-maps.

Algorithm 1 : 2 consistent ← True 3 foreach v ∈ V L do 4 S

 1234 Check incident arcs consistency for a dimension i.Input: A rule scheme S = L R, and a dimension i of D. Output: True if the rule satisfies I S (i), False otherwise.1 Function check_incident_arcs(L,R,i): L ← {e ∈ E L | s L (e) = v and l π D (L) (e) = i} 5 T L ← {e ∈ E L | t L (e) = v and l π D (L) (e) = i} 6 if v ∈ V R then // Preserved node 7 consistent ← consistent and |S L | ≤ 1 and |T L | ≤ 1 // At most one incident arc 8 S R ← {e ∈ E R | s R (e) = v and l π D (R) (e) = i} 9 T R ← {e ∈ E R | t R (e) = v and l π D (R) (e) = i}10 consistent ← consistent and |S L | = |S R | and |T L | = |T R | // Same in both sides 11 else // Deleted node 12 consistent ← consistent and |S L | = 1 and |T L | = 1 // Look for a unique deleted arc

13

 13

17 consistent←

 17 consistent and |S R | = 1 and |T R | = 1 // Look for a unique added arc 18 return consistent

6 r 9 else// Deleted arc 10 consistent/ 14 ( 20 foreach v ∈ V R do 21 i_arc ← null 22 if v ∈ V L then // Preserved node 23 S 26 else// Added node 27 i_arc 28 P 29 consistent ← consistent and |P| = 0 30 (

 691014202122232627282930 Input: A combinatorial rule scheme S = L R, and a dimension i of D. Output: True if the rule satisfies O S (i), False otherwise. 1 Function check_non_orientation(L,R,i):2 consistent ← True 3 foreach e ∈ {e ∈ E L | l π D (L) (e) = i} do 4 I L ← {e ∈ E L | s L (e ) = tL (e) and t L (e ) = s L (e) and l π D (L) (e ) = i and l π W(L) (e ) = l π W(L) (e)} 5 if |I L | = 1 then // Found a reverse arc ← e ∈ I L 7 if e ∈ E R then // Preserved arc 8 consistent ← consistent and r ∈ E R // The reverse must be preserved too ← consistent and r ∈ E R // The reverse must be deleted too 11 else // No reverse arc 12 consistent ← consistent and e ∈ E R // The arc must be preserved 13 (. . .) idem (lines 3 to 12) for arcs in E R by considering functions s R , t R , l π D (R) , and l π W(R) , as well as switching the roles of E L and E R . consistent ← consistent and N p ∩ Nc = / 0 . . .) idem (lines 5 to 12) for paths in R // Check cycles 15 foreach p ∈ CyclesL do 16 consistent ← consistent and [|p| = 2 or |p| = 4] // Check cycle size 17 N ← N F R N,E (l π W (L) (p)) 18 consistent ← consistent and ε ∈ N // Reduction to the empty word 19 (. . .) idem (lines 14 to 17) for cycles in R // Check extension to path or cycle L ← {e ∈ E L | s L (e) = v and l π D (L) (e) = i} 24 if |S L | = 1 then 25 i_arc ← e ∈ E R such that s R (e) = v and l π D (R) (e) = i // Uniquely exists from Alg. 1 ← e ∈ E R such that s R (e) = v and l π D (R) (e) = i // Uniquely exists from Alg. 1 ← {p ∈ CyclesR ∪ PathsR | i_arc ∈ p} // Empty set if i_arc = null . . .) idem (lines 20 to 28) for dimension j 31 return consistent

Figure 29 :Figure 30 :

 2930 Figure 29: Quad subdivision operation: rule scheme S G for a 2-G-map.

Figure 31 :

 31 Figure 31: House modeling: (1) cone extrusion, (2) edge rounding, (3) face extrusion.

  (a) Rule scheme for the operation of face extrusion in 3-G-map. (b) 3-G-map obtained after extruding the face. (c) Corresponding object.

Figure 36 :

 36 Figure 36: Face extrusion.

Figure 37 :

 37 Figure 37: Rule scheme for the operation of face extrusion in a 3-O-map.

Figure 38 :

 38 Figure 38: Sequential application of the face subdivision operation.

Where l π D (S ) stands for l π D (L) , l π D (K) or l π D (R) (resp. l π W (S ) stands for l π W (L) , l π W (K) or l π W (R) ) depending on whether e ∈ L, e ∈ K or e ∈ R.

In the definition of G w , all the arithmetic operations are described modulo 3

Where A B is the disjoint union of the sets A and B.

A word ŵ in W * is understood as the concatenation of words from W. Thus, for such a word ŵ, there exists k ≥ 0 and w 1 , w

, . . . w k in W such that ŵ = w 1 w 2 . . . w k . Each w i (for 1 ≤ i ≤ k) is a word of W, i.e., a word with letters from D, such that w i = (w i ) (1) . . . (w i ) (l i ) . When flatten, ŵ is therefore equal to (w 1 ) (1) . . . (w 1 ) (l 1 ) (w 2 ) (1) . . . (w 2 ) (l 2 ) . . . (w k ) (1) . . . (w k ) (l k ) .

return consistent

In the sense of[START_REF] Kosiol | Constructing Constraint-Preserving Interaction Schemes in Adhesive Categories[END_REF], the notation ∀(P, ∃C) means that each occurrence of P lies within an occurrence of C

Algorithm 3: Check cycles consistency for a pair of dimensions (i, j).

Input: A combinatorial rule scheme S = L R, and two dimensions i and j of D. Output: True if the rule satisfies C S ({(i, j)}), False otherwise. 1 Function check_cycles(L,R,i, j):

// The set of normal forms of the label of p In a 2-O-map, an isolated face cannot be modeled as the model only supports volumes surrounded by closed surfaces. To bypass this limitation, we start with a flat volume made of two faces. This falt volume corresponds to an orbit on the dimensions 1 and 2, where the 1-arcs define two cycle graphs with reverse orientation. Such an orbit is illustrated by the left-hand side of the rule scheme in Figure 33a. Each of the reverse cycles is encoded by a node and its loop. The conjugated W-labels on the loops of nodes a and b depict the reverse orientation of the cycles. In the right-hand side of the rule scheme, the (ε, 1)(ε, 1)(ε, 1)-cycle acd correspond to the lateral faces while the (1, 2)-arc from node c to node d represents the link between the lateral faces. Figure 33b gives the corresponding instantiated rule on a square face.

Edge rounding. The rule scheme of Figure 34a describes the edge rounding of a surface in 2D. We can use it with Jerboa's generic viewer to transform the pyramid of Figure 35a into the object of Figure 35c. The corresponding 2-G-maps are respectively given in Figures 35b and35d.

The same operation is given for a 2-O-map with the rule scheme of Figure 34b where nodes b and c represent the face replacing the rounded edge, and node d corresponds to the face replacing the rounded vertex.

Face extrusion. Face extrusion is similar to cone extrusion but adds a dual face instead of a dual vertex. Each vertex from the initial face is linked to its copy in the dual face by an edge. Thereby, lateral faces are rectangles instead of triangles.

The rule scheme of Figure 36a describes face extrusion for a 3-G-map. Nodes b and g correspond to the face copies. The 3-arc between nodes a and b represents the link between the newly added volume and the original face. Nodes d and e along with their common (ε, 0)-arc correspond to the edges that link the two bases of the prism. Nodes c and f represent the edges of faces from the bases that belong to the lateral faces. This rule scheme is applied on the square face of the pyramid from Figure 35c (here considered in 3D), yielding the 3-G-map of Figure 36b. The final object is illustrated in Figure 36c.

In a 3-O-map, face extrusion corresponds to the rule schemes of Figure 37. Nodes a, b and c have been respectively filed in red, blue, and green to be more easily retrievable in the right-hand side. On the left-hand side, node a matches the face to be extruded in the original volume, node b the same face as a, but in the external