Inclusion d'intervalles entiers et structure de donnée

[SpiceGuid]

Si je considère :

• l'ensemble des intervalles d'entiers, comme par exemple les intervalles [2,5] et [3,4]
• la relation d'inclusion ⊆ est une relation réflexive, antisymétrique et transitive, c'est une relation d'ordre partiel dans l'ensemble des intervalles d'entiers
• quelle structure de données correspond à cet ordre partiel, comment puis-je la caractériser

Ce que je veux dire c'est qu'un arbre binaire correspond à un ordre total (sur les entiers).
Avec l'inclusion d'intervalles d'entiers je peux construire (à coup sûr) toutes les structures arborescentes.
J'arrive aussi à construire quelques treillis (lattice), par exemple le treillis :

Code :

1
2
3
4
5
6
   [1,5]
  /     \
[1,4]  [2,5]
  \     /
   [2,4]

J'arrive également à construire quelques graphes dirigés, par exemple le digraphe :

Code :

1
2
3
4
5
6
   [1,5]  [2,6]
  /     \ /
[1,4]  [2,5]
  \     /
   [2,4]

D'une manière plus générale j'aimerais bien savoir quelle est précisément la structure de donnée engendrée par cet ordre partiel.
L'ensemble des graphes dirigés acycliques ?
Un sous-ensemble des graphes dirigés acycliques ? Mais alors lequel ?

Sachant que ce que je recherche au bout du compte c'est un algorithme qui, étant donnée une structure, soit capable de l'étiqueter avec des intervalles d'entiers. Chaque sommet ayant son étiquette unique dans toute la structure.

(normalement c'est une question pour le forum Algorithmes , mais c'est aussi bien ici, vous ne trouvez pas ?)

[gorgonite]

As-tu regardé du côté des implantations de domaines abstraits numériques sur les intervalles d'entiers ?
(interproc/apron est en OCaml par exemple)

plus précisément https://gforge.inria.fr/scm/viewvc.p...ox/?root=apron

[gasche]

Je pense qu'on peut décomposer la question "les ensembles finis d'intervalles sont-ils en correspondance avec tous les graphes dirigés acycliques" en deux parties:

(1) les ensembles finis d'intervalles sont-ils en correspondant avec tous les ordres partiels ?
(2) les ordres partiels sont-ils en correspondance avec tous les graphes dirigés acycliques ?

La réponse à la question (2) est "non" ou "presque" : on peut obtenir
un ordre partiel depuis un DAG en prenant son espace de chemins,
encore appelé "reachability relation": u≤v s'il y a un chemin de
u à v. Ça revient à prendre la fermeture transitive du DAG. Mais il
y a plusieurs DAG différents avec la même fermeture transitive
(ajouter l'arrête a→c au DAG a→b→c). Cela veut dire que dans un DAG il
y a "plus d'information" que dans un ordre partiel. Pour récupérer
l'équivalence il faut considérer seulement certains DAG, soit ceux qui
sont fermés par transitivité, soit au contraire (comme dans
tes exemples) le graphe réduit en retirant les arrêtes "inutiles" – il
se trouve qu'il existe un unique graphe réduit :
http://en.wikipedia.org/wiki/Transitive_reduction .

Je ne suis pas sûr pour la réponse à la question (1), mais je
soupçonne que la question est encore "non". Les ensembles finis
d'ensembles ordonnés par inclusion sont suffisant pour décrire tous
les ordres partiels, mais intuitivement je dirais que les ensembles
d'intervalles ne suffisent pas, à cause de propriété de contiguïté.

[gasche]

Après une recherche fatigante de contres-exemples frappants (mais la flemme de sortir un papier et un crayon), une petite recherche dans la littérature confirme que la réponse à la question (1) est non.

Un article de 1941 (Dushnik and Miller) définit une notion de "dimension" sur un poset (le plus petit nombre d'ordres totaux dont il est l'intersection) et prouve dans la foulée qu'il existe des graphes de dimension arbitraire, et que les graphes de dimension au plus 2 sont exactement ceux représentables par un graphe d'inclusion d'intervalles (entiers ou non, peut importe):

http://www.jstor.org/stable/2371374?origin=crossref

Un article plus récent (Tom Madej, 2002) définit un "interval number" sur un poset comme le plus petit nombre k tel que le poset est représentable comme un graphe d'inclusion d'unions d'au plus k intervalles (donc ton cas correspond à k=1), et montre encore une fois qu'il existe des graphes à l'"inverval number" arbitraire (mais k=2 suffit pour pas mal de graphes raisonnables).

http://www.sciencedirect.com/science...12365X9190014S

Pour finir, un exemple concret:

Code :

1
2
3
4
5
6
7
8
9
10
       A
      / \ 
     /   \
    /  A' \
   v  / \  \
   B /   \ C
   |/     \|
   vv     vv
   B'     C'

Supposons par l'absurde qu'on peut plonger ce graphe dans un graphe
d'intervalles. On a des bornes qui vérifient les relations ci-dessous:

Code :

1
2
3
4
5
a₁ ≤ b₁ ≤ b'₁ ≤ b'₂ ≤ b₂ ≤ a₂
a₁ ≤ c₁ ≤ c'₁ ≤ c'₂ ≤ c₂ ≤ a₂
    a'₁ ≤ b'₁ ≤ b'₂ ≤ a'₂
    a'₁ ≤ c'₁ ≤ c'₂ ≤ a'₂

On peut supposer sans perte de généralité que b₂ ≤ c₁ (sinon inverser
B et C) et donc b'₂ ≤ c'₁.

Comme B n'est pas sous A' on a b₁ < a'₁ ou b₂ > a'₂; mais comme C'
n'est pas sous B on a b₂ ≤ c'₂ ≤ a'₂, donc b₁ < a'₁, donc a₁ < a'₁.

Symétriquement (C n'est pas sous A', mais B' n'est pas sous C) on peut
conclure a₂ > a'₂.

Mais alors on a a₁ < a'₁ ≤ a'₂ < a₂, donc A' doit être sous A, ce qui
est contradictoire avec la structure du graphe.

[SpiceGuid]

Envoyé par gorgonite

As-tu regardé du côté des implantations de domaines abstraits numériques sur les intervalles d'entiers ?
(interproc/apron est en OCaml par exemple)

plus précisément https://gforge.inria.fr/scm/viewvc.p...ox/?root=apron

Merci. Hop, TortoiseSVN, checkout ....

J'ai d'abord regardé POMAP ocaml-pomap

Puis ensuite j'ai cherché des papiers sur les algos d'encodage, surtout les DAG et les demi-treillis supérieurs (je vous fais une sorte de best-of) :
Near Optimal Hierarchical Encoding of Types
Interval Comparisons and Lattice Operations based on the Interval Overlapping Relation
A fast algorithm for building lattices
An Algorithm for Minimal Insertion in a Type Lattice
Efficient Implementation of Lattice Operations

[SpiceGuid]

gasche

Pour la partie (2) de la question j'aurais du préciser que je ne m'intéresse qu'aux graphes réduits (une fois retirées les arrêtes "inutiles").

Pour la partie (1) je te remercie de m'avoir donné quelques pistes pour caractériser l'expressivité de l'inclusion d'intervalles (même si je n'ai pas accès aux documents mentionnés).

Quant aux treillis (lattice) j'imagine que la réponse est toute aussi négative car sinon... la vie serait trop facile... et puis ça se saurait (désolé pour la nullité de mes arguments ).

[gasche]

Si au lieu d'intervalles tu t'autorisais à manipuler des unions d'intervalles (ce qui revient à manipuler des ensembles d'entiers sous la forme de DIET sets) tu récupèrerais les ordres partiels arbitraires.

Est-ce que tu peux nous en dire plus sur ce que tu essaies de faire ? C'est par simple curiosité, parce que là "je cherche une structure que je ne connais pas pour pouvoir implémenter des trucs dessus avec des intervalles" je ne vois pas où tu veux en venir. Tu cites des papiers sur le (sous-)typage, la question vient de là ?

[gorgonite]

Envoyé par SpiceGuid

Quant aux treillis (lattice) j'imagine que la réponse est toute aussi négative car sinon... la vie serait trop facile... et puis ça se saurait (désolé pour la nullité de mes arguments ).

tout dépend ce que tu veux... les treillis ont des caractéristiques très intéressantes, ce qui les rend si utiles.
Par exemple dans le cadre de l'interprétation abstraite... il est a priori indispensable d'être entre des domaines partiellement ordonnés (souvent des ensembles, tu verras le mot poset), mais sur des treillis on obtient pas mal de choses plus rapidement, comme l’existence d'une limite dans un calcul de point fixe, une combinaison plus facile etc. (regardes le livre de Nielson & Nielson & Hankin)

[SpiceGuid]

Envoyé par gasche

Tu cites des papiers sur le (sous-)typage, la question vient de là ?

Oui, la question du sous-typage est ma motivation.

Actuellement ERic ne supporte qu'un seul super-type (hyperonyme) par concept, et je voudrais passer à plusieurs (multiples hyperonymes, comme dans Generalized Upper Model 2.0) :

• Sans trop sacrifier la performance, actuellement j'ai une hiérarchie de concepts et donc le sous-typage (la comparaison de 2 concepts) se fait en temps constant (chaque concept est associé à un intervalle, je n'ai qu'à tester l'inclusion).
• Actuellement je peux ajouter des concepts à la volée parce que le re-calcul des intervalles se fait en temps linéaire (un simple parcours en profondeur de la hiérarchie), j'aimerais bien conserver la définition incrémentale de ma taxonomie de concepts.
• Les demi-treillis supérieurs (et les arbres) ont ceci de plus intéressant (par rapport aux DAGs) que la plus petite borne supérieur (least upper bound) de 2 concepts est unique. L'intérêt c'est que ça permet le calcul d'une unique plus petite généralisation de 2 graphes entités/relations. En passant par le produit catégorique de deux graphes. Dans la catégorie où les objets sont les graphes et où les flèches sont les homorphismes de graphe.

Évidemment, dès que j'aurai trouvé une solution (ou un bon compromis) pour le sous-typage des concepts je l'appliquerai également au sous-typage des relations.