Omar Et-Targuy

Ahlame Begdouri

Salem Benferhat

Carole Delenne

Syntactic computation of Fagin-Halpern conditioning in possibility theory

Conditioning plays an important role in revising uncertain information in light of new evidence. This work focuses on the study of Fagin and Halpern (FH-)conditioning in the context where uncertain information is represented by weighted or possibilistic belief bases. Weighted belief bases are extensions of classical logic belief bases where a weight or degree of belief is associated with each propositional logic formula. This paper proposes a characterization of a syntactic computation of the revision of weighted belief bases (in the light of new information) which is in full agreement with the semantics of the FHconditioning of possibilistic distributions. We show that the size of the revised belief base is linear with respect to the size of the initial base and that the computational complexity amounts to performing O(log 2 (n)) calls to the propositional logic satisfiability tests, where n is the number of different degrees of certainty used in the initial belief base.

Introduction

Belief revision [START_REF] Gärdenfors | Belief Revision[END_REF][START_REF] Schwind | On computational aspects of iterated belief change[END_REF] is an important problem in knowledge representation and artificial intelligence. It consists in revising plausible beliefs of an agent in the light of new information, often considered to be completely certain and reliable. If the new information to be inserted is consistent with the a priori beliefs, then the revision comes down to simply add this information to the agent's beliefs. The problem arises when this new information contradicts a priori beliefs. In this case, the agent must decide which information to ignore or replace with other weaker, less informative and less precise information.

Within the framework of uncertainty theories, the process of belief revision is materialized by the notion of conditioning. Agents' beliefs are modeled by uncertainty distributions µ (probability distribution, mass function [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Aldrich | Glenn shafer -A short biography[END_REF], possibility distribution [START_REF] Dubois | Possibility Theory and Its Applications: Where Do We Stand?[END_REF], ordinal conditional function OCF [START_REF] Spohn | Ordinal conditional functions: A dynamic theory of epistemic states[END_REF][START_REF] Spohn | The Laws of Belief -Ranking Theory and Its Philosophical Applications[END_REF], etc.) which associate to each element of the universe of discourse (in our context, a set of propositional logic interpretations) a degree of plausibility.

In probability theory, Bayesian conditioning is widely used, especially in Bayesian networks, for the propagation of beliefs in the presence of new observations. R. Piskac and A. Voronkov (eds.), LPAR 2023 (EPiC Series in Computing, vol. 94), pp. [164][165][166][167][168][169][170][171][172][173][174][175][176][177][178][179][180] For belief functions, Dempster's rule of conditioning [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Jirousek | On conditional belief functions in the dempster-shafer theory[END_REF] remains the reference operator for the revision of uncertain information.

In possibility theory, conditioning is defined in two different approaches, depending on how the uncertainty degrees are interpreted [START_REF] Dubois | Possibility Theory and Its Applications: Where Do We Stand?[END_REF]. The first definition is the so-called product-based possibilistic conditioning which makes full use of the uncertainty interval [0, 1]. The second definition is called min-based possibilistic conditioning where only the relative order between uncertain information matters.

These standard conditioning operators (probabilistic Bayesian conditioning, Dempster's rule of conditioning, possibilistic min-based and product-based conditionings) have been very well studied in the literature, both from representational and computational points of view.

Another form of conditioning, called Fagin and Halpern conditioning (noted FH-conditioning in the following), is however little considered in the literature, in particular from a computational point of view. This conditioning was introduced in the framework of belief functions theory in [START_REF] Fagin | A new approach to updating beliefs[END_REF]. FH-conditioning allows to obtain a better characterization of the conditioned belief function than Dempster's in the context of belief functions being interpreted as lower and upper probabilities, induced by a particular family of probability distributions (see also [START_REF] Thierry Denoeux | Representations of Uncertainty in AI: Beyond Probability and Possibility[END_REF] for a discussion whether FH-conditioning should be considered as a revision or prediction operator). Besides, still within the framework of the theory of belief functions, other theoretical justifications of FH-conditioning have been proposed in [START_REF] Dezert | Total belief theorem and conditional belief functions[END_REF][START_REF] Meester | A new look at conditional probability with belief functions[END_REF] and recent work have illustrated their use for object detection in the context of autonomous vehicles [START_REF] Lalintha | Efficient computation of conditionals in the dempster-shafer belief theoretic framework[END_REF].

In the context of possibility theory, FH-conditioning has been approached only from a semantic point of view [START_REF] Dubois | Bayesian conditioning in possibility theory[END_REF] and there is no work (to the best of our knowledge) that treats this conditioning from the point of view of syntactic representation of uncertain beliefs. In this paper, we are interested in addressing this shortcoming by studying FH-conditioning in a framework where uncertain beliefs are represented by sets of weighted propositional logical formulas. In possibility theory, the available uncertain information is represented by a so-called possibilistic belief base, denoted by Σ in the following. This weighted belief base is composed of a set of pairs (ϕ i , α i ) where ϕ i is a propositional logic formula, and α i is a minimum degree of certainty (more precisely a degree of necessity in the sense of the possibility theory) associated with ϕ i .

The question considered in this paper is how to revise a possibilistic weighted base Σ, in the light of a new totally certain information (denoted in this paper by (ψ, 1), where ψ is a propositional logic formula) while being in full agreement with the possibilistic semantics of FH-conditioning. To achieve this goal, we first propose an equivalent syntactic reformulation of the semantic definition of FH-conditioning as a sequence of three transformation operations of possibility distributions. For each of these semantic transformation operations, we propose their equivalent characterisation on the weighted belief bases. At the end of the third operation, we show that the final belief base obtained corresponds exactly to the application of FHconditioning on weighted belief bases. We provide at the end of the paper the spatial and temporal complexity analysis of the syntactic computation of FH-conditioning. We show that the size of the revised belief base is linear with respect to the size of the initial base. Moreover, the complexity of computing the FH-conditioning, from the weighted belief bases, comes down to the complexity of computing the degree of certainty of the new information ψ from the initial base Σ, which is done in log 2 (n) calls to a satisfiability test of a set of propositional formulas (SAT).

The rest of the paper is organized as follows. Section 2 recalls possibilistic logic and presents weighted belief bases and their semantics. Section 3 introduces the notion of FH-conditioning from a semantic point of view. Section 4 contains the computation of the syntactic revision of the weighted belief bases. The last section concludes the paper.

A brief review of possibilistic logic

Possibilistic logic [START_REF] Lang | Possibilistic Logic: Complexity and Algorithms[END_REF][START_REF] Dubois | Handbook of logic in artificial intelligence and logic programming, tome 3: Nonmonotonic reasoning and uncertain reasoning, chapitre possibilistic logic[END_REF] is a simple extension of a propositional logic. At the syntactical level, instead of considering that formulas of the propositional belief base have the same level of priority, we associate to each formula a degree which reflects its level of priority with respect to the other formulas in the belief base. The result is called a possibilistic belief base. The possibilistic logic semantics is also an extension of the one of propositional logic, which partitions the set of interpretations in two parts: the models and counter-models of the belief base. In possibilistic logic, we get a more refined partition, called a possibility distribution, where the counter-models of lower priority information will be preferred to counter-models of higher priority information. The notions of consistency and inference of propositional logic become gradual in possibilistic logic and give respectively the notions of possibility and necessity measures. Possibilistic logic ahas a connection with modal logic with points in common, especially on the duality of necessity and possibility, and differences; in particular possibilistic logic is gradual and nonmonotonic while modal logic is non-gradual and monotonic (see [START_REF] Banerjee | On the relation between possibilistic logic and modal logics of belief and knowledge[END_REF] for a more details). Possibility theory and possibilistic logic have very close links with Conditional Ordinal Functions (OCF), also called ranking functions, introduced by Spohn [START_REF] Spohn | Ordinal conditional functions: A dynamic theory of epistemic states[END_REF][START_REF] Spohn | The Laws of Belief -Ranking Theory and Its Philosophical Applications[END_REF]. OCFs are models widely used to represent the epistemic states of agents and to define belief revision methods.

In the following, we consider a finite propositional language L whose formulas are denoted by Greek letters (except for Ω and ω). Ω is the finite set of interpretations of L and ω an element of Ω. We denote by |= the satisfaction relation of propositional logic.

Possibility distributions

A possibility distribution π is a mapping from the set of interpretations Ω to the interval [0, 1]. π(ω) represents the degree of consistency (or compatibility) of the interpretation ω with the available knowledge. By convention:

• π(ω) = 1 means that it is entirely possible for ω to be the real world.

• π(ω) = 0 means that ω is certainly not the real world.

• π(ω 1 ) > π(ω 2 ) simply means that ω 1 is a preferred candidate than ω 2 for being the real state of the world.

From a possibility distribution π, we can define the degree of consistency (or possibility) and the degree of certainty (or of necessity) of a formula ϕ:

• Π(ϕ) = max{π(ω)|ω |= ϕ} evaluates to what extend ϕ is consistent with the available knowledge expressed by π.

• N (ϕ) = 1 -Π(¬ϕ) is used to measure to what extent a proposition ϕ is entailed by the knowledge expressed by π.

A possibility distribution π is said to be normalized if there exists an interpretation which is completely possible (i.e. ∃ω ∈ Ω|π(ω) = 1).

Possibilistic belief bases

At a syntactic level, uncertain information is represented by a prioritized or weighted propositional logic knowledge bases, called possibilistic belief bases. A possibilistic belief base is a compact representation of a possibility distribution. Indeed, it is represented by a finite set of weighted formulas (the higher the weight, the more certain the formula) Σ = {(ϕ i , α i ), i = 1, ..., n}, where ϕ i is an element of L, and α i ∈]0, 1] is the weight, considered as a lower bound of the degree of necessity N (ϕ i ). Note that formulas with α i = 0 are note explicitly represented in the belief base; namely only beliefs which are somewhat accepted by the agent are explicitly represented in the possibilistic belief base.

Possibilistic belief bases are compact representations of possibility distributions. Indeed, one can associate with any possibilistic belief base Σ a possibility distribution, denoted by π Σ . Recall that the degree of possibility of an interpretation is its degree of compatibility or consistency with the belief base. Consider the case where a possibilistic belief base contains a single formula {(ϕ, α)}. If an interpretation ω satisfies the formula ϕ then this interpretation is completely consistent with ϕ, hence π Σ (ω) = 1. If a given interpretation ω does not satisfy the formula ϕ then π Σ (ω) must be such that the greater the degree of certainty α of ϕ, less π Σ (ω) is considered possible. In particular, if ϕ is completely certain, i.e. α = 1, then ω is completely impossible, i.e. π Σ (ω) = 0.

More generally, if Σ contains more than one formula then interpretations satisfying all beliefs will have the greatest degree of possibility, i.e. 1, and the other interpretations will be ranked with respect to the belief of greater weight that they falsify. More formally: Definition 1. The possibility distribution associated with a possibistic belief base Σ is defined, for all ω ∈ Ω by [START_REF] Dubois | Handbook of logic in artificial intelligence and logic programming, tome 3: Nonmonotonic reasoning and uncertain reasoning, chapitre possibilistic logic[END_REF]:

π Σ (ω) = 1 if ∀(ϕ i , α i ) ∈ Σ, ω |= ϕ i 1 -max{α i : (ϕ i , α i ) ∈ Σ, ω ̸ |= ϕ i } otherwise (1)
It is easy to check that the possibility distribution π Σ is normalized if and only if the set of the non-weighted propositional logic formulas obtained from Σ, i.e. {ϕ i : (ϕ i , α i ) ∈ Σ}, is consistent in the sense of propositional logic.

In the following, we will use the following academic example to illustrate the different notions of the paper: Example 1. Let Σ = {(¬q ∨ s, 0.66), (q ∨ ¬s, 0.70), (¬q ∨ ¬r, 0.15), (q ∨ s, 0.35)} be a possibilistic belief base. Table 1 gives the possibility distribution associated with Σ using Equation 1.

The interpretation q¬rs, qr is the most preferred one since it is the only one which is consistent with Σ. Hence, their possibility degree is 1. The interpretation qrs gets the possibility degree 0.85, because it falsifies the least certain belief in Σ; namely (¬q ∨ ¬r, 0.15). The two following interpretations ¬qr¬s and ¬q¬r¬s get the possibility degree 0.65, because they falsify (q∨s, 0.35). Then the next more plausible interpretations are qr¬s and q¬r¬s. Finally, the least preferred interpretations are ¬qrs and ¬q¬rs, as they falsify the highest belief in Σ, namely (q ∨ ¬s, 0.70).

q r s π Σ (ω) 1 1 1 0.85 1 1 0 0.34 1 0 1 1 1 0 0 0.34 0 1 1 0.3 0 1 0 0.65 0 0 1 0.3 0 0 0 0.65
Table 1: The possibility distribution associated with Σ

Semantic definition of Fagin-Halpern conditioning

This section concerns the problem of beliefs changes, in possibility theory, which is an important topic in artificial intelligence and in the information systems for managing the dynamics of beliefs. At the semantic level, the revision of a possibility distribution π consists in changing the plausibility order between the interpretations in order to give priority to new information, denoted ψ. This revision process is obtained thanks to the notion of conditioning which transforms a distribution of possibility a priori π and a certain information ψ into a new possibility distribution (a posteriori) denoted by π(.|ψ).

The possibility distribution π(.|ψ) must be normalised or consistent (i.e., ∃ω ∈ Ω such that π(ω | ψ) = 1)) and where the new information ψ should be completely certain (i.e., ∀ω ∈ Ω such that ω falsifies ψ, we have π(ω | ψ) = 0)). Besides, the new revised possibility distribution π(.|ψ) must not change the relative order between the models of ψ (i.e., ∀ω ∈ Ω and ∀ω ′ ∈ Ω such that ω |= ψ and

ω ′ |= ψ, if π(ω) ≥ π(ω ′ ) then π(ω | ψ) ≥ π(ω ′ | ψ)).
Even if in this paper we use the minimum and the maximum operators (particular cases of t-norms and t-conorms), this work mainly deals with uncertainty and the case of vague or fuzzy information [START_REF] Zadeh | Fuzzy logic-a personal perspective[END_REF] is not treated in this paper.

Clearly, there are different ways to define π(. | ψ) (e.g., [START_REF] Bouchon-Meunier | Independence and possibilistic conditioning[END_REF]). Two main definitions have been proposed within the framework of possibility theory (e.g., [START_REF] Dubois | Possibilistic logic: a retrospective and prospective view[END_REF]). The first definition, called min-based possibilistic conditioning, consists in i) setting the countermodels of ψ (the new information) to 0, ii) setting the best models of ψ to 1, and iii) letting the degrees of possibility of the other models of ψ unchanged. The second definition, called product-based possibilistic conditioning, consists in i) setting the countermodels of ψ (the new information) to 0, and ii) proportionally shifting the degrees of possibility of the models of ψ up to to obtain a normalized conditional possibility distribution. These two definitions are formally described as follows (when Π(ϕ) > 0):

• Minimum-based conditioning: π(ω | m ψ) =      1, if π(ω) = Π(ψ) and ω |= ψ π(ω), if π(ω) < Π(ψ) and ω |= ψ 0, if ω ̸ |= ψ (2) q r s π Σ (ω | F H q ∨ ¬r ∨ s) 1 1 1 0.85 1 1 0 0.493 1 0 1 1 1 0 0 0.493 0 1 1 0.462 0 1 0 0 0 0 1 0.462 0 0 0 0.65
Table 2: FH-conditioning of the possibility distribution of Example 1

• Product-based conditioning:

π(ω | p ψ) = π(ω) Π(ψ) , if ω |= ψ 0, otherwise (3)
There is an alternative to these two definitions which has been very little explored in possibility theory. This is the conditioning proposed by Fagin and Halpern [START_REF] Fagin | A new approach to updating beliefs[END_REF] and introduced within the framework of belief functions. This definition of conditioning, which we will denote hereinafter by FH-conditioning, has been adapted to possibility theory and was directly defined on possibility measures (instead of possibility distributions) as follows [START_REF] Dubois | Bayesian conditioning in possibility theory[END_REF]):

Π(ϕ | F H ψ) = Π(ϕ ∧ ψ) Π(ϕ ∧ ψ) + N (¬ϕ ∧ ψ) (4)
We recall that in the above equation N (ϕ) = 1 -Π(¬ϕ). Now, if we restrict the definitions Π(. | F H ψ) to interpretations, we get the definition of FH-conditioning defined on possibility distributions [START_REF] Dubois | Bayesian conditioning in possibility theory[END_REF]. Definition 2. Let π be a possibility distribution and let ψ be a propositional logic formula. Then the FH-conditioning of π by ψ, denoted by π(. | F H ψ), is given by the following equation:

∀ω ∈ Ω, π(ω | F H ψ) = max π(ω), π(ω) π(ω)+N (ψ) if ω |= ψ 0 if ω ̸ |= ψ (5)
Where again we recall that

N (ϕ) = 1 -Π(¬ϕ), with Π(ψ) = max{π Σ (ω) : ω ∈ Ω and ω |= ψ}.
In the rest of the paper, and when there is no ambiguity, we will simply use π(. | ψ) instead of π(. | F H ψ). Let us continue our example.

Example 2. Let us apply the possibilistic FH-conditioning at the semantic level to the possibility distribution π Σ given in the example 1 by the new piece of information q ∨ ¬r ∨ s. Table 2 gives the FH-conditioned possibility distribution.

Let us explain the result of FH-conditioning with the input propositional logic formula q ∨ ¬r ∨ s. The interpretation ¬qr¬s is not model of q ∨ ¬r ∨ s. Therefore, its conditional possibility degree is equal 0. The others interpretations are models of q∨¬r∨s. Therefore, after conditioning, their possibility degree will be equal to max π(ω),

π(ω) π(ω)+N (ψ) .

Syntactic counterpart of possibilistic Fagin-Halpern conditioning

There is a clear interest in FH-conditioning for the revision of uncertain information within the framework of belief functions theory, both at the theoretical level and at the level of applications.

In the framework of possibility theory, the very few works that exist (e.g., [START_REF] Dubois | Bayesian conditioning in possibility theory[END_REF]) mainly concern semantic definitions of FH-conditioning (e.g., defined on the set of interpretations of propositional logic) or on discussions whether the FH-conditioning is a revision operator, or a prediction operator or what is called a focusing operator (see [START_REF] Dubois | Focusing vs. belief revision: A fundamental distinction when dealing with generic knowledge[END_REF] and [START_REF] Thierry Denoeux | Representations of Uncertainty in AI: Beyond Probability and Possibility[END_REF] for more details).

However, unlike min-based and product-based conditioning (and also their hybrid version [START_REF] Benferhat | Syntactic computation of hybrid possibilistic conditioning under uncertain inputs[END_REF]) which have been well studied in the literature, there is no work (to the best of our knowledge) that deals with syntactic computation of possibilistic FH-conditioning applied on possibilistic belief bases.

Defining a syntactic FH-conditioning, i.e. at the level of possibilistic knowledge bases, has clear computational advantages over an application of FH-conditioning at the semantic level, since obviously the size of the set interpretations is exponential with respect to the number of propositional symbols of the used language.

Figure 1 summarizes the purpose of this section and is explained as follows:

• Inputs of our syntactic FH-conditioning computation are:

a possibilistic belief base Σ; and a totally certain new piece of information (ψ, 1) that must be taken into account.

• Let π Σ be the possibility distribution associated with Σ using Equation 1.

• Let π Σ (.|ψ) be the conditional possibility distribution, resulting from the semantic application of FH-conditioning on π Σ after the integration of the new computing (ψ, 1) using the Equation 5.

• Our goal is to compute, from Σ and the totally certain information (ψ, 1), a new possibilistic belief base, denoted Σ F H , such that:

∀ω ∈ Ω, π Σ F H (ω) = π Σ (ω | ψ). (6)
where π Σ F H is the possibility distribution associated with Σ F H using the equation 1.

The satisfaction of Equation 6 is necessary for having a syntactic computation that fully agrees with the semantic definition of FH-conditioning in possibility theory.

The following subsection first gives an equivalent decomposition of the definition of FHconditioning into three elementary steps of transforming possibility distributions. Then, we give the syntactic counterpart of each of these three steps; before finally putting together all the syntactical computations to achieve the objective of this section.

Possibilistic FH-conditioning in three main steps

The computation of the syntactic counterpart of Equation 5 is not straightforward. We are therefore going to describe it progressively in an alternative form by breaking down the semantic definition of FH-conditioning (given by Equation 5) into three elementary steps of modification of possibility distributions.

Let π Σ be the initial possibility distribution associated with the initial possibilistic belief base Σ (using Equation 1). Let (ψ, 1) be the new piece of information that should be taken into account. We define the three steps as follows:

• Step 1: shifting the initial possibility distribution. This step mainly consists of shifting each possibility degree π Σ (ω) by integrating the necessity degree associated with the new information. The result of this modification of the initial possibility distribution is simply denoted π 1 and is formally defined as follows:

π 1 (ω) = π Σ (ω) π Σ (ω) + N (ψ)
,

where we recall that N (ψ) = max{π Σ (ω) : ω ∈ Ω and ω |= ψ}.

• Step 2: combining possibility distributions. This second step consists in combining with the maximum operator, the result of the possibility distribution of step 1 with the initial possibility distribution π Σ .

The possibility distribution obtained at this stage is again simply denoted by π 2 and is defined as follows: π 2 (ω) = max(π Σ (ω), π 1 (ω)).

•

Step 3: integrating new information. This third and final step consists simply of integrating the new information (ψ, 1) into the possibility distribution obtained in step 2. For this, we simply encode the new information (ψ, 1) by a binary possibility distribution, where only possibility degree 1 (totally possible) and possibility degree 0 (totally impossible) are used. The possibility degree 1 is associated with models of ψ while the possibility degree 0 is associated with its countermodels.

The possibility distribution obtained in step 3 is again simply denoted by π 3 and is defined as:

π 3 (ω) = min(π 2 (ω), π ψ (ω)),
where,

π ψ (ω) = 1, ω |= ψ, 0, otherwise.
It is not difficult to show, that at the end of the third step, the final obtained possibility distribution is exactly that resulting from applying FH-conditioning on π Σ with (ψ, 1) and given by Equation 5; i.e. we have:

∀ω ∈ Ω, π 3 (ω) = π(ω | F H ψ).
Thus, finding the syntactic counterpart of Equation 5 is equivalent to finding the syntactic counterpart of π 3 .

The following three subsections give the syntactic counterparts of the possibility distributions obtained at each of the three steps described above (Subsection 4.1).

Syntactic computation of Step 1: shifting the initial possibility distribution

We begin by giving the syntactic counterpart of the possibility distribution obtained in Step 1 and denoted by π 1 . Proposition 1 provides a possibilistic belief base, denoted by Σ 1 , which compactly encodes the distribution π 1 . More precisely, the resulting possibilistic belief base Σ 1 is composed of two parts. The first part, denoted in Proposition 1 by Σ 11 , consists in modifying the possibility degrees associated with each of the formulas of the initial base Σ, in order to reflect the shift made in this step 1 on the initial possibility distribution. The second part is composed of a single formula, which is a weighted contradiction, that expresses the fact that π 1 can be sub-normalized (i.e. there can be no interpretation ω, such as π 1 (ω) = 1)). We will see in the computation of the possibilistic belief base associated with the Step 2 that this sub-normalization will be lifted and the result obtained at this step 2 is always normalized and consistent.

The precise result of the computation of the possibilistic belief base associated with the possibility distribution of step 1 is given in the following Proposition 1.

Proposition 1. Let Σ = {(ϕ i , α i ), i = 1, ..., n} be the initial belief base. Let (ψ, 1) be the new piece of information. Let

Σ 1 = {(⊥, 1 - 1 1+N (ψ) )} ∪ Σ 11 be a belief base obtained from Σ, with Σ 11 = {(ϕ i , 1 - 1-αi 1-αi+N (ψ) ), (ϕ i , α i ) ∈ Σ}.
Then, ∀ω ∈ Ω, we have:

π Σ1 (ω) = π 1 (ω) = π Σ (ω) π Σ (ω) + N (ψ) , (7)
where π Σ1 (ω) is the possibility distribution associated with Σ 1 and π 1 is the possibility distribution obtained at Step 1 described in subsection 4.1.

Proof. Let ω ∈ Ω. There are two cases to consider:

1. ω is a model of all formulas of Σ. Namely, π Σ (ω) = 1. In this case, ω is also a model of all formulas of Σ 1 . Therefore:

π Σ1 (ω) = 1 -(1 - 1 1 + N (ψ) ) = π Σ (ω) π Σ (ω) + N (ψ)
.

2. ω falsifies at least a weighted formula from Σ. This also means that ω falsifies at least a weighted formula from Σ 1 . In this case:

π Σ1 (ω) = min{1 -(1 - 1 1 + N (ψ) ), π Σ11 (ω)} = min{ 1 1 + N (ψ) , π Σ11 (ω)} = π Σ11 (ω).
Indeed, π Σ11 (ω) is necessarily of the form

1-αi 1-αi+N (ψ) for some (ϕ i , 1 - 1-αi 1-αi+N (ψ) ) in Σ 11 . And we have 1-αi 1-αi+N (ψ) < 1 1+N (ψ) (we recall that α i > 0)
. Now, we develop the expression associated with π Σ1 :

π Σ1 (ω) = π Σ11 (ω) = min{1 -[1 - 1 -α i 1 -α i + N (ψ) ] : (ϕ i , 1 - 1 -α i 1 -α i + N (ψ) ) ∈ Σ 11 and ω ̸ |= ϕ i } = min{ 1 -α i 1 -α i + N (ψ) : (ϕ i , 1 - 1 -α i 1 -α i + N (ψ) ) ∈ Σ 11 and ω ̸ |= ϕ i } = min{1 -α i : (ϕ i , α i ) ∈ Σ and ω ̸ |= ϕ i } min{1 -α i + N (ψ) : (ϕ i , 1 - 1-αi 1-αi+N (ψ) ) ∈ Σ 11 and ω ̸ |= ϕ i } = π Σ (ω) π Σ (ω) + N (ψ)
.

The following example 3 illustrates the computation of the possibilistic belief base given in the Proposition 1 on our running example.

Example 3. Let us consider the possibility distribution π Σ (ω) of Example 1. Let ψ = q ∨ ¬r ∨ s be the new piece of information. Note that from Table 1, Π(¬q ∧ r ∧ ¬s) = 0.65. Hence, N (q ∨ ¬r ∨ s) = 0.35 The following table gives the values of:

π 1 (ω) = πΣ(ω) πΣ(ω)+N (q∨¬r∨s) .
Let us compute the belief base Σ 1 associated with π 1 .

q r s π 1 (ω) 1 1 1 0.708 1 1 0 0.493 1 0 1 0.74 1 0 0 0.493 0 1 1 0.462 0 1 0 0.65 0 0 1 0.462 0 0 0 0.65
Table 3: The possibility distribution π 1 (ω)

From Proposition 1, the general form of Σ 1 is:

Σ 1 = {(⊥, 1 - 1 1+N (ψ) )} ∪ Σ 11 , with Σ 11 = {(ϕ i , 1 - 1-αi 1-αi+N (ψ) ), (ϕ i , α i ) ∈ Σ}.
Replacing ψ by q ∨ ¬r ∨ s, we get: Σ 1 = {⊥, 0.26} ∪ {(¬q ∨ s, 0.507), (q ∨ ¬s, 0.538), (¬q ∨ ¬r, 0.292), (q ∨ s, 0.35)}. One can easily check that if we compute the possibility distribution π Σ1 associated with the possibilitic belief base Σ 1 , using Equation 1, we get exactly the one given in the above table, which means that ∀ω ∈ Ω, π Σ1 (ω) = π 1 (ω).

Syntactic computation of Step 2: combining possibility distributions

We now present the syntactic computation of Step 2. It consists of the computation of a possibilistic belief base, which we will denote Σ 2 , whose associated distribution is equal to that obtained from step 2 and denoted by π 2 . We recall that π 2 is the maximum of π 1 and the possibility distribution π Σ associated with the initial belief base Σ. There exists in the literature (e.g., [START_REF] Benferhat | Merging uncertain knowledge bases in a possibilistic logic framework[END_REF]) a characterization of the combination by the maximum operator. However, such a characterization would yield a resultant possibilistic belief base of size equal to the product of the two sizes of the belief bases to be combined (in our case in

O(| Σ |)×(| Σ 1 |)), where | Σ | (respectively | Σ 1 |
) is the number of weighted formulas in Σ (respectively in Σ 1 )). Proposition 2 gives a better spatial complexity result. Indeed, we show that the resulting base, associated with the syntactic combination based on the maximun of π 1 and π Σ , is of linear size with respect to those of the possibilistic belief bases to be combined; and more precisely in

O(max(| Σ |), | Σ 1 |))).
Besides, as π Σ is normalized then trivially the distribution π 2 (defined as being the maximum of the distributions π Σ and π 1 ) is also normalized. As a result, the weighted contradiction formula that was present in the resulting possibilistic belief base of step 1, will no longer be present in the belief base obtained at the end of step 2. In summary, the computation of the possibilistic belief base associated with the possibility distribution of stage 2 is given in the following Proposition 2.

Proposition 2.

• Let Σ = {(ϕ i , α i ), i = 1, ..., n} be the initial belief base and ψ be the new piece of information.

• Let Σ 1 be the belief base obtained from proposition 1; namely,

Σ 1 = {(⊥, 1-1 1+N (ψ) )}∪Σ 11 , with Σ 11 = {(ϕ i , 1 - 1-αi 1-αi+N (ψ) ), (ϕ i , α i ) ∈ Σ}. • Let Σ 2 = {(ϕ i , min(α i , 1 - 1-αi 1-αi+N (ψ) )), (ϕ i , α i ) ∈ Σ} be a belief base obtained from Σ.
Then, ∀ω ∈ Ω, we have:

π Σ2 (ω) = π 2 (ω) = max (π Σ (ω), π Σ1 (ω)) = max π Σ (ω), π Σ (ω) π Σ (ω) + N (ψ)
,

where π Σ , π Σ1 and π Σ2 denote the possibility distributions associated with the belief 's bases Σ, Σ 1 and Σ 2 respectively. The distribution π 2 is the one obtained at Step 2 and described in subsection 4.1.

Proof. Let ω ∈ Ω. There are two cases to consider:

1. ω is a model of all formulas of Σ. Namely, π Σ (ω) = 1. In this case:

π Σ1 (ω) = 1 1 + N (ψ)
, and π Σ2 (ω) = 1.

Therefore, we indeed have:

π Σ2 (ω) = max (π Σ (ω), π Σ1 (ω)) = 1.
2. ω falsifies at least a weighted formula from Σ. For sake of simplicity, we note:

• π, π 1 , and π 2 instead of π Σ , π Σ1 , and π Σ2 .

• β i instead of 1 - 1-αi 1-αi+N (ψ) .
• m the number of formulas from Σ (resp Σ 1 ) falsified by ω. Note that, by construction, Σ and Σ 1 contain exactly the same formulas. However, they differ on the weights associated with these formulas. Hence, m is the same for both Σ and Σ 1 .

• {α 1 , ..., α m } and {β 1 , ..., β m } be the sets of weights associated with falsified formulas in Σ and Σ 2 respectively.

By definition, we have for all ω ∈ Ω:

π 2 (ω) = min{1 -min(α i , β i ) : (ϕ i , α i ) ∈ Σ and (ϕ i , min(α i , β i )) ∈ Σ 2 } = min{max(1 -α i , 1 -β i ) : i = 1, ..., m}.
(for sake of simplicity, we avoid repeting (ϕ i , α i ) ∈ Σ)

By distributing min over the max, we obtain:

π 2 (ω) = max{min{x 1 , ..., x m } : x i ∈ {1 -α i , 1 -β i }, i = 1, ..., m}
Note that when all x ′ i s are respectively equal to (1-α i ) ′ s then: min{x i , ..., x m } = min{1α 1 , ..., 1 -α k , ..., 1 -α m } = 1 -α k = π(ω), for some k ∈ {1, ..., m}.

Similarly, when all x ′ i s are respectively equal to (1-β i ) ′ s then: min{x i , ..., x m } = min{1β 1 , ..., 1 -β t , ..., 1 -β m } = 1 -β t = π 1 (ω), for some t ∈ {1, ..., m}.

For the other cases, some x ′ i s are equal to (1 -α i ) while others x ′ i s are equal to (1 -β i ), then we have three cases to consider: (a) min{x 1 , ..., x m } = 1 -α y for some y ∈ {1, ..., m} and α y ̸ = α k . Then x k = 1 -α k = π(ω), and π 1 (ω) ≥ min{x 1 , ..., x m }.

(b) min{x 1 , ..., x m } = 1 -β z for some z ∈ {1, ..., m} and β z ̸ = β t . Then x t = 1 -α t = π(ω), and π(ω) ≥ min{x 1 , ..., x m }.

(c) min{x 1 , ..., x m } = 1 -α y = 1 -α k = π(ω), or min{x 1 , ..., x m } = 1 -β z = 1 -β k = π 1 (ω).
Then trivially, max(π(ω), π 1 (ω) ≥ min{x 1 , ..., x m }).

Therefore for any combination min{x 1 , ..., x m } where there exist some x ′ i s equal to (1α i ) ′ s and also some x ′ j s equal to (1 -β i ) ′ s we have: π(ω) ≥ {x 1 , ..., x m } and π 1 (ω) ≥ {x 1 , ..., x m }.

Therefore:

π 2 (ω) = max{min{x 1 , ..., x m } : x ∈ {1 -α i , 1 -β i }, i = 1, ..., m} = max{π(ω), π 1 (ω)}.
Note that in Proposition 2, if a given ω ∈ Ω is a model of all formulas of Σ, Σ1 (ω) = 1 1+N (ψ) . However, for inteptretation ω ∈ Ω that are not models of some formulas of Σ, π Σ1 (ω) = Let us compute, using Proposition 2, the belief base:

(ω) = max (π Σ (ω), π 1 (ω)). q r s π Σ (ω) π 1 (ω) π 2 (ω) 1
Σ 2 = {(ϕ i , min(α i , 1 - 1-αi 1-αi+N (ψ) )
), (ϕ i , α i ) ∈ Σ} for the new piece of information ψ = q ∨ ¬r ∨ s. We have: Σ 2 = {(¬q ∨ s, min(0.66, 0.507)), (q ∨ ¬s, min(0.7, 0.538)), (¬q ∨ ¬r, min(0.15, 0.292)), (q ∨ s, min(0.35, 0.35))} = {(¬q ∨ s, 0.507), (q ∨ ¬s, 0.538, (¬q ∨ ¬r, 0.15), (q ∨ s, 0.35)}.

Finally, one can check that computing the possibility distribution π Σ2 (ω) for the belief base Σ 2 , using Equation 1, leads exactly to the one of the above table, which means that ∀ω ∈ Ω, π Σ2 (ω) = π 2 (ω).

Syntactic computation of Step 3: integrating new information

The last step consists in integrating, in the possibility distribution obtained in step 2, the fact that the new information ψ is totally certain. The computation of the syntactic counterpart of this step is immediate as it simply amounts to adding to the possibilistic belief base, resulting from step 2, the weighted formula (ψ, 1). More specifically, we have: Proposition 3. Let Σ = {(ϕ i , α i ), i = 1, ..., n} be the initial belief base. Let ψ be a new piece of information. Let Σ 2 be the belief base obtained from proposition 2. Let Σ 3 = Σ 2 ∪ {(ψ, 1)} . Then, ∀ω ∈ Ω:

π Σ3 (ω) = π Σ2 (ω), if ω |= ψ, 0, otherwise. (8)
Proof. The proof is immediate using the definition of a possibility distribution associated with a belief base. Indeed, let ω be an interpretation. If ω is not model of of ψ, then π Σ (ω) = 0 as it falsifies a fully certain formula (ψ, 1). If ω is a model of ψ, then trivially π 3 (ω) = π 2 (ω).

To sum up, propositions 1-3 allow us to provide the syntactic counterpart of the possibilistic Fagin-Halpern conditioning defined by the equation 5. The final possibilistic belief base is summarized by:

Σ F H = {(ψ, 1)} ∪ {(ϕ i , min(α i , 1 - 1 -α i 1 -α i + N (ψ) )), (ϕ i , α i ) ∈ Σ}. (9)
Our last example confirms that the final computation of the possibilistic belief base at the end of Step 3 represents the FH-conditioning defined on the initial distribution π Σ .

Example 5. Let us consider the possibility distribution π 2 (ω) of Example 4. Recall that the new piece of information is ψ = q ∨ ¬r ∨ s. The following table gives the values of π 3 (ω) = min(π 2 (ω), π ψ (ω)), where we recall that:

π ψ (ω) = 1, ω |= ψ 0, otherwise
Using Equation 9, we get: Σ F H = {(q ∨ ¬r ∨ s, 1)} ∪ {(¬q ∨ s, 0.507), (q ∨ ¬s, 0.538), (¬q ∨ ¬r, 0.15), (q ∨ s, 0.35)}.

q r s π 2 (ω) π ψ (ω) π 3 (ω) 1
Finally, one can check that computing the possibility distribution π Σ F H associated with the belief base Σ F H , using Equation 1, gives exactly the same distribution given in the table above. This result is also identical to the possibility distribution given in Example 2 when applying the semantic FH-conditioning with ψ = q ∨ ¬r ∨ s.

We finish this section by giving the complexity results. It is easy to check from Equation 9that the spatial complexity is linear with respect to the size of the initial base Σ and more precisely the size of the final belief base is in O(| Σ |). This very good result is obtained thanks to the decomposition of the FH-conditioning into three elementary operations. Indeed, as explained in subsection 4.2, a direct application of existing results in the literature (e.g., [START_REF] Benferhat | Merging uncertain knowledge bases in a possibilistic logic framework[END_REF]) regarding Step 2 (the max-based combination of possibility distributions) would generate a quadratic spatial complexity with respect to the size of the initial belief base (i.e., in O(| Σ | 2 )). Regarding time complexity, the difficult task in Equation 9 is the computation of the degree of necessity N (ψ) from the initial base. The complexity of reasoning in possibilistic logic has been well studied in the literature (e.g., [START_REF] Lang | Possibilistic Logic: Complexity and Algorithms[END_REF]). The degree N (ψ) is equal to the highest degree α i such that {ϕ i |(ϕ i , α j ) ∈ Σ and α i ≥ α j } is consistent and infers ψ, where the notions of inference and consistency are those of propositional logic. If such a degree does not exist then N (ψ) = 0. If we note n the number of different degrees in the possibilistic belief base Σ, then it is easy to provide a dichotomous search algorithm for calculating this largest weight α i in log 2 (n) calls to the propositional logic satisfiability test.

Conclusion

The contribution of this paper concerns the question of the revision of uncertain information. We focused on Fagin and Halpern conditioning adapted to possibility theory. In particular, we have proposed a method which makes it possible to calculate the result of possibilistic FH-conditioning of a weighted base in order to take into account uncertain information. We have shown that our syntactic computation is in full agreement with the semantics given by FH-conditioning on possibility distributions. This syntactic computation was done without additional cost compared to the two other forms of possibilistic conditioning (min-based and product-based conditionings). Finally, we showed that the spatial complexity of the conditioned belief base is linear with respect to the size of the initial belief base. The Fagin and Halpern conditioning was defined in the framework of belief functions. Possibility theory can be interpreted as a particular case of belief functions when the focal elements (ie the elements that have a non-zero mass) are nested (also called consonant belief functions). A future work is to see to what extent our syntactic results can be extended to belief functions, in particular when the latter are represented in a compact way by graphical models.

Figure 1 :

 1 Figure 1: The aim of this section

  πΣ(ω) πΣ(ω)+N (ψ) . The following Example 4 illustrates Proposition 2.

Example 4 .

 4 Let us consider the possibility distributions π Σ (ω) and π 1 (ω) of the examples 1 and 3 respectively. Let ψ = q∨¬r∨s be the new piece of information. Rcall that N (q∨¬r∨s) = 0.35.

  Table 4 gives the values of π 2

Table 4 :

 4 The possibility distribution π 2 (ω)

Table 5 :

 5 The possibility distribution π 3 (ω)

Acknowledgements:

This research has received support from the European Union's Horizon research and innovation programme under the MSCA-SE (Marie Sk lodowska-Curie Actions Staff Exchange) grant agreement 101086252; Call: HORIZON-MSCA-2021-SE-01; Project title: STARWARS (STormwA-teR and WastewAteR networkS heterogeneous data AI-driven management). This research has also received support from the French national project ANR (Agence Nationale de la Recherche) CROQUIS (Collecte, représentation, complétion, fusion et interrogation de données hétérogènes et incertaines de réseaux d'eaux urbains) and from the ANR project EXPIDA (EXplainable and parsimonious Preference models to get the most out of Inconsistent DAtabases), grant number ANR-22-CE23-0017.


domain: info sde

text:
Omar Et-Targuy

Ahlame Begdouri

Salem Benferhat

Carole Delenne

Thanh-Nghi Do

Truong-Thanh Ma

A Graph-Based Approach for Representing Wastewater Networks from GIS Data: Ensuring Connectivity and Consistency

Keywords: Wastewater networks, Graph-based representation, Connectivity

HAL is

Introduction

Efficient wastewater management plays a vital role in ensuring public health and environmental sustainability. Geographic Information Systems (GIS) have become a popular tool for managing and analyzing geographic data associated with wastewater networks. However, the traditional approach of storing each component in separate databases can result in inconsistencies and inaccuracies, especially when it comes to representing the connections between these components.

In reality, wastewater networks are interconnected systems where various components work together to transport wastewater from its source to treatment plants. For example, manholes serve as access points to the pipes, facilitating maintenance and inspection activities. These connections between different components are crucial for the proper functioning of the network.

In GIS, each component of the wastewater network is typically stored in its own database, e.g. manholes in one database and pipes in another. While this approach allows for efficient management of individual components, it lacks the ability to capture and represent the connections between them. As a result, over time, as updates and modifications are made to the network, the databases become unsynchronized, leading to a loss of the true connectivity and relationships between the components.

To address the challenges associated with representing wastewater networks, a comprehensive and integrated approach is needed. A graph-based representation proves to be highly effective in capturing the interconnected nature of the network. By treating each component, such as manholes, pumps and structures as nodes, and representing the connections between them as edges which represents pipes in wastewater networks, The Graph-Based Representation is a versatile method adept at illustrating data interrelationships in diverse domains. In [START_REF] Fall | Spatial Graphs: Principles and Applications for Habitat Connectivity[END_REF], a pioneering graph-based spatial approach is introduced, employing Minimum Planar Graphs from Delaunay triangulations to assess habitat connectivity effectively. This innovation facilitates wildlife habitat network analysis and visualization, aiding in conservation decisions. In [START_REF] Sonawane | Graph based representation and analysis of text document: A survey of techniques[END_REF], the authors conduct a systematic survey of graph-based text representation, highlighting its superiority over the bag-of-words model in capturing structural and semantic information. The use of graph-based representation leads to enhanced performance in information retrieval, term weighting and ranking across various text applications. Additionally, in [START_REF] Maugey | Graph-based representation for multiview image geometry[END_REF], a novel graphbased approach for multiview image representation is proposed. This method utilizes graph connections to describe pixel proximity in 3D space, achieving a compact and controllable representation that is well-suited for coding and reconstructing multiple views. In [START_REF] Liu | A knowledge graph-based data representation approach for IIoT-enabled cognitive manufacturing[END_REF], a knowledge graph-based data representation is proposed for Industrial Internet of Things enabled manufacturing. [START_REF] Zhou | Static-dynamic global graph representation for pedestrian trajectory prediction[END_REF] presents a global graph for modeling social interactions among pedestrians.

The paper is organized as follows. In Section 2, an overview of wastewater networks data is provided, and the limitations of representing them in a SIG using the traditional separate databases approach are discussed. Section 3 presents the graph-based algorithm, which transforms the GIS representation into a interconnected graph-based representation. In Section 4, experiments and results from applying the graph-based algorithm to real-world wastewater networks data are presented, with a focus on highlighting the algorithm's advantages and limitations. Finally, Section 5 concludes the paper by summarizing the benefits of the graph-based representation and its implications for wastewater network management.

Wastewater networks in GIS

Wastewater networks comprise a variety of interconnected components (see Figure 1) that collectively ensure the efficient and safe transportation of wastewater from its sources to treatment plants. Some of the essential components of wastewater networks include:

-Pipes: sewer pipes are the primary components of a wastewater network.

They are used to transport wastewater from its source, such as residential, commercial or industrial buildings, to the treatment plants.

-Manholes: manholes are access points in the wastewater network that allow for maintenance and inspection activities. They are usually constructed at regular intervals along the sewer pipes. Manholes provide entry points for workers to access the sewer pipes and perform tasks like cleaning, repairs and inspections. -Pumps: pumps are used to increase the pressure and flow of wastewater, especially in areas where gravity flow is not possible. -Fittings: fittings are used to connect and join different sections of sewer pipes in wastewater networks. One characteristic of wastewater network data is the geographical information associated with each component, representing its position on the Earth. To store, visualize and manage this spatial data, a Geographic Information System (GIS) is commonly employed. A GIS allows for the integration, analysis and interpretation of spatial data within the context of wastewater network management.

In the context of wastewater networks, two primary geometries are used to represent the network components in GIS (see Figure 1). The first geometry is the point geometry, which represents specific locations such as manholes, structures, pumps and other components. The second geometry is the line geometry, which represents the pipes that form the network infrastructure.

In addition to the geographical information, each component in the wastewater network is also characterized by attribute information. These attributes provide additional details and characteristics of the components, such as pipe diameter, material, flow capacity and other relevant data.

In a GIS system, the data related to each component of the wastewater network is typically stored in separate databases, as illustrated in Figure 1. Each component, such as pipes, manholes, pumps, fittings and structures, has its own database, allowing for easy management and analysis of the data.

However, in reality, these components are interconnected and have spatial relationships with each other; e.g, manholes serve as access points to pipes, and pumps are connected to specific pipes within the network. Therefore, it is crucial to establish and maintain the appropriate connections between these components.

As the amount of wastewater network data grows, it becomes increasingly important to update the nodes and pipes that represent these networks in the GIS. However, ensuring that these databases are properly synchronized with each other is challenging. Inconsistencies and inaccuracies in the representation of the wastewater network arise when the connections between the components are not accurately captured or updated. For example, Figure 2 illustrates some of the issues that can arise with this type of representation. In the figure, there are nodes that are not connected to any pipes, which is impossible in reality. Additionally, in some cases there are pipes that doesn't have a node at one of its extremities or both. There are many other potential problems that arise when the nodes and pipes of a wastewater network are not properly synchronized.

To address these issues, a graph-based representation can be employed. This representation ensures connectivity between different network components and eliminates inconsistencies. By using a graph structure, nodes representing manholes, structures, pumps and other components can be connected by edges representing pipes. This graph-based approach accurately reflects the interconnected nature of the wastewater network. Additionally, the graph-based representation helps to complete data by addressing missing nodes in the GIS representation, ensuring a more comprehensive view of the wastewater network. Moreover, the graph-based representation retains all information from the GIS representation, enabling the generation of GIS representations whenever needed. It also facilitates the integration of new information into the graph, making it a flexible and scalable solution for wastewater network management.

Fig. 2: Inconsistencies between databases

In the following section, the details of the graph-based representation and its benefits in maintaining the connectivity and integrity of wastewater network data will be presented. The algorithm begins by extracting the intersections between each pipe in the pipes database and the nodes in the nodes database. This ensures that the connections between pipes and nodes are accurately identified. After detecting the intersections, the resulting nodes are connected or inserted into the graph. During this step, verification is performed to determine if the extremities of each pipe have intersections. If no intersections are found, dummy nodes are added to ensure connectivity within the graph, with edges representing the pipes.

Our graph-based representation

Overall, the output of this process is a graph-based representation that accurately depicts the relationships between the pipes and nodes in the wastewater network.

Formal representation

The algorithm takes the pipes and nodes databases as inputs. These inputs can be formally represented as follows:

-The Pipes Database P D is a collection of line geometries that represent sewer pipes P D = {p 1 , ..., p i , ..., p k }. Each pipe p i is identified by a unique identifier i, and the total number of pipes in the database is denoted by k. -The Nodes Database N D is a collection of point geometries that includes all the point type components: manholes, structures, pumps, fittings, accessories and treatment plants N D = {n 1 , ..., n j , ..., n m }. Each element n j has an attribute type, allowing us to identify the type of component. Each node n j is identified by a unique identifier i, and the total number of nodes is denoted by m.

The algorithm generates a graph denoted as G = (V, E) as its final output, where:

-V is a finite set of nodes that contains elements from N D and dummy nodes that will be added to ensure connectivity and complete missing nodes. -E ⊆ V × V is a finite set of edges that represents connections between two nodes, indicating that these connections correspond to the pipes from P D. Each edge in the graph represents the relationship between two nodes, reflecting the pipes that connect them in the wastewater network representation.

Proposal algorithm

The graph construction algorithm (Algorithm 1) initializes an empty graph G with sets of nodes V and edges E. It iterates over each pipe p i in the pipes database P D. For each pipe p i , the algorithm follows these steps:

Algorithm 1 Graph Construction 1: procedure GraphConstruction(P D, N D, Distance) 2: V, E ← {}, {} 3: G ← (V, E) 4: for i = 1 to k do 5:
Buf f er ← CreateBuf f er(pi, Distance) 6:

Intersections ← ExtractIntersections(N D, Buf f er) 7:

Ext1 ← RandomExtrimity(pi) 8:

SortedInter ← DistanceAndSort(Intersections, Ext1) 9:

SortedInter ← AddDummyN odes(SortedInter) 10:

G ← ConnectionT oGraph(SortedInter, G) 11:

return G

Step 1: Create a buffer. In GIS a "buffer zone" is defined by an area around a geographic feature that contains every points within a specified distance from that feature. In this step, a buffer is created around each pipe p i by applying a distance that accounts for the physical dimensions of the pipe and any potential shifting of the nodes that are near to the pipe. For example, in Figure 4, the blue line represents the pipe, and a buffer is created around it using a distance. The resulting yellow buffer represents the extended region around the pipe that encompasses its potential location within the given distance. Step 2: Extract Intersections. In a real-world of wastewater networks, pipes are connected to nodes. This step aims to detect intersections between the buffer created around the pipe p i and the nodes databases N D, to identify their connections.

The result is a set of nodes that must be connected to the corresponding pipe. For example, in Figure 5, the intersection between the buffer of pipe 11415 and the N D is detected, resulting in a set of nodes denoted as Intersections = {41132, 41142, 41140}. These nodes represent the set of nodes that must be connected to the pipe p i , which is the pipe 11415 in this example.

Step 3: Calculate Distances and Sort Intersections. In this step of the algorithm, the Euclidean distance is calculated between one of the pipe's extremity Extr1 and each of the nodes intersecting the buffer (see algorithm 2). The Euclidean distance is the straight-line distance between two points in a twodimensional space; it is suitable for cases where the distances between points are relatively small on surface Earth, which is the case in our situation with nodes that are near to each other in a wastewater network.

Using Euclidean distance, the proximity of each intersection node to one of the extremities of the pipe, labeled as Extr1, can be determined. Sorting the intersection nodes based on their distances allows us to establish a logical order that reflects their positions relatively to the pipe's extremities. This step is essential for checking the intersections with the extremities of the pipe. distances ← {} 3:

Algorithm 2 Calculate Euclidean Distance and Sort Intersections

for node in Intersections do 4:

x, y ← coordinates of node 5:

distance ← (x -Extr1.x) 2 + (y -Extr1.y) 2 6:

Append distance to distances 7:

SortedInter ← Sort intersections based on distances 8:

return SortedInter

Step 4: Add dummy nodes. This step is crucial for ensuring the connectivity of wastewater networks (see algorithm 3). To construct graphs based on the intersections, it is essential to have a node near to each extremity of the pipe p i . However, this condition is not always satisfied. It can occur that the set of intersections is empty (|SortedInter| = 0 in algorithm 3), or that certain nodes are present but not located at the extremities of the pipe p i .

In such scenarios, it becomes necessary to add dummy nodes to the extremities of the pipe. These dummy nodes serve as virtual representations of the missing nodes, facilitating the connection of the pipe to the overall wastewater network.

Fig. 6: Example of a pipe with only one node intersecting the buffer area in manholes database, thus one missing extremity.

In Figure 6, it can be observed that there is only one node inside the buffer around pipe number 13360, which is near one extremity of the pipe. However, there is no node near the other extremity. To maintain connectivity with other Algorithm 3 Adding Dummy Nodes 1: procedure AddDummyNodes(SortedInter, pi, T hreshold) 2:

Ext1 ← the first extremity of pi 3:

Ext2 ← the second extremity of pi 4:

if |SortedInter| = 0 then 5:

SortedInter ← AddF irst(T ype = Dummy, coord = (Ext1.x, Ext1.y)) 6:

SortedInter ← AddLast(T ype = Dummy, coord = (Ext2.x, Ext2.y)) 7:

else SortedInter ← AddF irst(T ype = Dummy, coord = (Ext1.x, Ext1.y)) 23:

if EuclideanDistance(lastN ode, Ext2.x, Ext2.y) > T hreshold then 24:

SortedInter ← AddLast(T ype = Dummy, coord = (Ext2.x, Ext2.y)) 25:

return SortedInter pipes, a dummy node is necessary for the missing extremity. The introduction of this dummy node serves the purpose of ensuring the connection of the pipe with the remainder of the network while preserving the integrity of the wastewater flow representation.

Step 5: Connecting to the graph The final step involves connecting the sorted intersections into the graph. After completing the step 4, the sorted intersections set is guaranteed to have at least two nodes that must be connected to the extremities of the pipe p i . These nodes can either be from the original node set N D or dummy nodes that were added to ensure connectivity. In this step the algorithm 4 begins by selecting the first node in the set of sorted intersections as the source node and adds it to the set of vertices in the graph G. Next, the algorithm iterates through the remaining nodes in this set. For each node, it creates an edge between the current source node and the destination node. Each edge in the graph represents a pipe in wastewater networks.

In the illustrated example (Figure 7), the buffer zone created around pipe number 11415 is taken into consideration. This buffer intersects three nodes, Algorithm 4 Connecting to the graph

1: procedure ConnectionToGraph(SortedInter, G) 2:
sourceN ode ← first node in SortedInter 3:

V ← V ∪ {sourceN ode} 4:

for node in SortedInter excluding the first node do 5:

destinationN ode ← node 6:

E ← E ∪ {(sourceN ode, destinationN ode)} 7:

sourceN ode ← destinationN ode 8:

return G namely Intersections = {41142, 41132, 41140}. These nodes represent the necessary connections to be established with pipe 11415. Before establishing these connections, a sorting process is performed and intersections with pipe extremities are verified. In this case, the intersections adequately cover the extremities, thus avoiding the need to introduce dummy nodes. Consequently, the graph can be constructed appropriately by connecting the sorted nodes to pipe 11415. It can be observed that a single pipe can result in the creation of two edges in the graph, as evidenced here with edges (41142, 41132) and (41132, 41140), owing to the connection of the middle node numbered 41132 to the pipe. Fig. 7: Application of the algorithm: example with three nodes intersecting the buffer area including the pipe's extremities.

In the second example (Figure 8), involving pipe number 13360, a different situation arises. Only one intersection is found between this pipe and the nodes database, which happens to be located at one extremity. Unfortunately, no intersection exists at the other extremity. To ensure the proper connectivity of pipe 13360 within the graph, a dummy node with the label 107965 is introduced. This dummy node acts as a placeholder, allowing the inclusion of the missing extremity in the graph representation. Therefore, the resulting graph reflects the connection between node 39488 and the dummy node 107965, representing pipe 13360.

Fig. 8: Application of the algorithm: example with three nodes intersecting the buffer area including the pipe's extremities.

Experiments

The primary objective of our study is to develop a graph-based representation derived from GIS datasets of wastewater networks. As shown in Table 1, the results of experiments conducted on four distinct real datasets of wastewater networks are presented. These datasets all represent the same geographical zone but originate from different providers. Each dataset consists of multiple components, and for each of these datasets, both the traditional GIS representation, also known as the separate databases representation, and the innovative graph-based representation derived from the GIS representation are available. Additionally, the difference in the number of objects between the SIG and graph-based representations is presented. Concerning dataset 1, most of the components from the GIS representation are successfully preserved in the graph. However, there are very few components missing in the graph representation. This happens when the components are located at a considerable distance from the nearest pipes in the GIS representation, making it challenging to establish direct connections between them. Figure 2 provides a visual representation of this scenario, highlighting the manholes that are not in close proximity to any pipes. The algorithm ensures that each pipe in the GIS representation is represented as an edge in the graph-based representation. However, in certain cases, the number of edges in the graph may be less than the number of pipes in the GIS representation. This can happen when there are duplicated pipes in the GIS representation, where two pipes have the same extremities. In such cases, the algorithm inserts only one of these duplicated pipes into the graph, resulting in a difference in the number of edges. In Figure 9, it is evident that two pipes, namely 37974 and 16990, share the same extremities, specifically 32451 and 30017. As a result of removing these duplicated pipes during the graph-based representation, only one pipe with these extremities is inserted into the graph. This explains the negative difference in the number of edges compared to the pipes in the GIS representation for Dataset 1, where 21 duplicated pipes were encountered. 10, the GIS representation of the wastewater network is depicted, revealing the absence of nodes at the extremities of certain pipes. Without the presence of manholes or other components, it is challenging to establish a complete branch in the network. Hence, the addition of dummy nodes becomes necessary to ensure connectivity and complete the representation of the wastewater network data.

Indeed, the number of connected components in the resulting graphs is an important criterion for evaluating the accuracy of the graph-based representation. In real-world wastewater networks (see the Figure 11), it is common to In some cases, the disconnected components in the GIS representation may be the result of inserting errors or shifting errors during data collection or digitization processes. These errors can lead to gaps in the network representation, making it challenging to accurately assess the connectivity of the wastewater network. In the graph-based representation, one of the main goals is to identify and correct errors present in the GIS databases, which may lead to disconnected components in the resulting graph. The small threshold of 0.1 meter used for the buffer distance is designed to capture and address these errors of small shifting or inserting errors.

By applying this threshold, the algorithm can identify nodes that are close to the pipes in the GIS representations but may not have a direct connection due to minor inaccuracies in their positions. The buffer distance helps in identifying these nearby nodes and ensures that they are connected by inserting appropriate edges in the graph. As a result of this error correction process, the number of components in the resulting graph is often less than the number of components in the GIS representation (see Table 2). This reduction in the number of components indicates that the graph-based representation is successfully identifying and addressing the errors in the GIS representation, resulting in a more accurate and coherent representation of the wastewater network.

In Figure 12, an example of the graph-based representation of wastewater networks data is presented, where different colors of nodes symbolize specific types of components, with red indicating manholes. The edges represent the pipes, and their interconnections depict the real-world relationships found in wastewater networks. Furthermore, the graph-based representation retains all information about components from the GIS representation, encompassing both attribute and spatial details. This preservation enables us to generate GIS representations from the graph whenever required.

Conclusion

In this study, a graph-based approach for representing wastewater networks, derived from GIS datasets, has been proposed. Our graph-based representation accurately captures the interconnected nature of the network. By conducting experiments on real-world datasets, the efficiency and effectiveness of the method have been demonstrated. It showcases the ability to preserve most components from the GIS representation while resolving missing connections attributed to significant distances.

In future endeavors, our plans involve improving our graph-based representations by integrating water circulation within the pipes. This entails constructing oriented graph-based representations that reflect the flow direction and dynamics of wastewater through the network. Taking into account the directionality of pipes enables us to delve deeper into flow behavior analysis and optimize the network accordingly. Furthermore, since all the datasets we possess represent the same geographical zone, our objective is to explore the fusion of these oriented graphs. The fusion process will enable us to synthesize comprehensive representations that encompass the entire wastewater network for the given region.

Fig. 1 :

 1 Fig. 1: Example of wastewater networks in GIS representation.

Figure 3

 3 Figure 3 depicts the general process of constructing a graph-based representation for wastewater network data. The inputs comprise a database of pipes and databases of nodes, encompassing various components such as manholes, structures, pumps, fittings and more -all represented by node geometry.

Fig. 3 :

 3 Fig. 3: General process

Fig. 4 :

 4 Fig. 4: Create a buffer Fig. 5: Intersections detection

1 :

 1 procedure DistanceAndSort(Intersections, Extr1) 2:

Fig. 9 :

 9 Fig. 9: Duplicated pipes in GIS Fig. 10: Dummy nodes

Fig. 11 :

 11 Fig. 11: Components in GIS representation

Fig. 12 :

 12 Fig. 12: Graph-based representation of wastewater networks

Table 1 :

 1 From GIS to graph: Comparison of components number

	Components

Table 2 :

 2 Connected components

Acknowledgements This research has received support from the European Union's Horizon research and innovation programme under the MSCA-SE (Marie Skłodowska-Curie Actions Staff Exchange) grant agreement 101086252; Call: HORIZON-MSCA-2021-SE-01; Project title: STARWARS (STormwAteR and WastewAteR networkS heterogeneous data AI-driven management). This research has also received support from the French national project ANR (Agence Nationale de la Recherche) CROQUIS (Collecte, représentation, complétion, fusion et interrogation de données hétérogènes et incertaines de réseaux d'eaux urbains).