Regrouper les arêtes d'un graphe

Bonjour à tous,

Je me retrouve dans une situation délicate où je possède ce style de données :

Code:

---

1 2 3 4 5 6

id chaîne 1 1-2-3 2 3-4-5 3 12-13-14 4 14-15-16

---

J'ai besoin de savoir que 1 et 2 appartiennent à la même chaîne et 3 et 4 à une autre chaîne.

On peut considérer les fonctions min(chaîne) et max(chaîne) pour obtenir respectivement le 1er et dernier élément.

En résultat ça devrait ressembler à ceci :

Code:

---

1 2 3 4 5 6

num_group id_chaîne 1 1 1 2 2 3 2 4

---

Comment puis-je m'y prendre ?

Merci,

A bientôt

Bonjour,


Je part du principe que vous êtes en version postgresql 9.X.
Je part aussi du principe que vos chaine n'ont pas de trou à l'intérieur d'elle même.

Déjà vous avez un problème de modélisation.

On ne doit jamais mettre plusieurs informations dans une même colonne.

Vu les limitations de postgresql, on va partir sur une vue qui remettra un peut d'ordre :

Code:

---

1 2 3 4

create view tmp as select id, min(chaine) as ch_start, max(chaine) as ch_end from ma_table

---

Ensuite on fait une requete recursive + utilisation d'une fonction de fenetrage pour récuperer les groupes :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

with recursive rec_tmp (id, ch_start, ch_end, id_pere, niveau) as ( select id, ch_start, ch_end, id, 0 from tmp a where not exists (select 1 from tmp b where a.id <> b.id and a.ch_start = b.ch_end) union all select b.id, b.ch_start, b.ch_end, a.id, a.niveau + 1 from rec_tmp a inner join tmp b on a.ch_end = b.ch_start ) select id, dense_rank() over(order by id_pere) as grp from rec_tmp

---

D'accord avec punkoff quant aux pré-requis, et à la réserve sur la modélisation.
Autre pré-requis : il ne faut pas de chaines chevauchantes, par exemple "3-4-5" et "4-5-6" contiennent toutes les 2 "4-5"

Citation:

---

Envoyé par mister3957

Bonjour à tous,

Je me retrouve dans une situation délicate où je possède ce style de données :

Code:

---

1 2 3 4 5 6

id chaîne 1 1-2-3 2 3-4-5 3 12-13-14 4 14-15-16

---

---

Quel est le but de votre système ? Car si c'est pour définir des graphes au sens "réseau" du terme, vous pourriez sans doute utiliser PostGIS !

A +

Bonjour,

Merci pour vos réponses.

@SQLpro

Oui j'ai simplifié l'énonce du problème pour se concentrer sur le fond sans polluer, mais j'utilise bien Postgis. J'ai une table avec des rues, en réalité des segments de rue, ce qui fait qu'une rue peut avoir 80 / 100 lignes dans cette table.

A côté j'ai un script SQL chargé du géocodage. Le souci se produit au moment où je retrouve la rue (donc un segment de rue) et que je cherche le numéro. Si je ne groupe pas les segments, ça cherchera le numéro de rue attribué à ce segment et non au groupe qui possède ce segment.

D'un point de vue métier, il arrivera des cas où je chercherai le numéro 842 et où ça trouvera le numéro 3 comme "le plus proche" car ça cherchera sur le segment trouvé et non sur la rue entière.

Il faut donc grouper ces segments par connexion, nom et limite géographique mais ça je m'en chargerai pour mettre les WHERE correspondants.

@escartefigue

Apparemment deux segments ne se superposent pas, donc pas de problème là dessus.

@punkoff

En reprenant tes suggestions, j'ai fait ceci :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

CREATE OR REPLACE VIEW tmp AS SELECT r.*, St_X(St_StartPoint(geometry)) AS x1, St_Y(St_StartPoint(geometry)) AS y1, St_X(St_EndPoint(geometry)) AS x2, St_Y(St_EndPoint(geometry)) AS y2 FROM rues r;   WITH RECURSIVE rec_tmp (id, x1, y1, x2, y2, id_pere, niveau, name) AS ( SELECT id, x1, y1, x2, y2, id, 0, name FROM tmp a WHERE NOT EXISTS (SELECT 1 FROM tmp b WHERE a.id <> b.id AND a.x1 = b.x2 AND a.y1 = b.y2) AND lower(name) = 'avenue de dunkerque' UNION ( SELECT b.id, a.x1, a.y1, b.x2, b.y2, a.id, a.niveau + 1, a.name FROM rec_tmp a INNER JOIN tmp b ON a.x1 = b.x2 AND a.y1 = b.y2 AND lower(a.name) = 'avenue de dunkerque' ) ) SELECT *, dense_rank() OVER(ORDER BY id_pere) AS grp FROM rec_tmp;

---

J'ai filtré sur les "Avenues de Dunkerque" sans intégrer des restrictions géographiques, normalement ça devrait sortir une dizaine de groupe.

Ça fait 30 minutes que ça tourne, serais-je dans une récursion infinie ?

Merci à vous,

A bientôt

Re bonjour,

J'ai sous estimé les prérequis d'escartefigue et ai trouvé ce soucis là :

Pièce jointe 188675

Du coup chaque couple de segment entre ces deux points est parent l'un de l'autre et ça fait une récursion infinie.

Et je pense que pour des certains ronds point ça va poser le même problème.

La requête que j'ai employé est :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

CREATE OR REPLACE VIEW tmp AS SELECT r.*, St_X(St_StartPoint(geometry)) as x1, St_Y(St_StartPoint(geometry)) as y1, St_X(St_EndPoint(geometry)) as x2, St_Y(St_EndPoint(geometry)) as y2 FROM rues r WHERE r.name = 'Avenue de Dunkerque';   WITH RECURSIVE rec_tmp (id, x1, y1, x2, y2, id_pere, niveau) AS ( SELECT id, x1, y1, x2, y2, id, 0 FROM tmp a WHERE NOT EXISTS ( SELECT 1 FROM tmp b WHERE a.id <> b.id AND a.x1 = b.x2 AND a.y1 = b.y2 ) UNION ALL SELECT b.id, b.x1, b.y1, b.x2, b.y2, a.id, a.niveau + 1 FROM rec_tmp a INNER JOIN tmp b ON a.x2 = b.x1 AND a.y2 = b.y1 ) SELECT id, dense_rank() OVER(ORDER BY id_pere) AS grp FROM rec_tmp;

---

Est-ce que l'on peut contourner ce genre de cas ?

Merci à vous,

A bientôt

Les GPS font des calculs approximatifs de distance dans les segments basés sur la longueur du segment.
En gros :

• on persiste la longueur des segments dans une table annexe pour chaque segment identifié avec des n° de rue en début et en fin de chaque côté du segment
• on calcule une approximation de distance intermédiaire sur le segment.
• On positionne le point, sur le segment par rapport au début du segment.

Vous devriez venir à mon cours Orsys :
http://www.orsys.fr/formation-donnees-spatiales.asp
C'est exactement le TP que nous faisons avec les stagiaires !


A +

Citation:

---

Envoyé par mister3957

Est-ce que l'on peut contourner ce genre de cas ?

---

Oui, il suffit de rajouter le chemin dans la requête récursive sous forme d'un tableau de points et à chaque étape sedemander si l'on est pas déjà passé par ce point.

Mais au vu de votre graphe, c'est à sens unique sur chaque segment, donc, vous ne devriezpas avoir le problème si le modèle était correct et indiqauit que c'est un graphe orienté.

J'ai donné cet exemple il y a longtemps dans cet article :
http://sqlpro.developpez.com/cours/s...ursives/#LIV-B
Requête finale 28...

et vous trouverez plus d'info dans mon livre sur SQL ou un chapitre entier aborde les requêtes SIG :
Pièce jointe 188749


A +

Hello @SQLpro,

Parfois c'est orienté, parfois ça ne l'est pas.

L'exemple ci-dessus est orienté parce que c'est une avenue, mais des fois c'est une ruelle ou une rue assez simple (90% des cas) qui peut être pratiquée dans les deux sens.

Il faut sûrement rajouter du St_Collect quelque part. Dans certains cas on se retrouvera avec du LINESTRING, dans d'autres (comme celui évoqué ci dessus) avec du MULTILINESTRING mais pour la recherche du numéro ça serait transparent pour Postgis.

Toujours est-il que ça n'est pas forcément lié au comportement des GPS et peut-être un problème rencontré dans beaucoup d'autres domaines.

J'ai résolu mon problème métier en jouant avec ses règles, mais quand même... une belle requête bien placée qui fait ni plus, ni moins qu'un traitement complexe, ça fait toujours plaisir et ça serait très probablement plus performant même si ici les performances ne sont pas décisives. Et puis par curiosité quoi ;)

Pour simplifier (en dehors d'aspects GIS), j'ai cette requête :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

CREATE OR REPLACE VIEW tmp AS SELECT 1 as id, 1 as x1, 1 as y1, 2 as x2, 2 as y2 UNION SELECT 2, 2, 2, 5, 5 UNION SELECT 3, 5, 5, 8, 8 -- Un groupe allant de (1/1 à 8/8 via 2/2 et 5/5) UNION SELECT 4, 10, 10, 12, 12 UNION SELECT 5, 12, 12, 15, 15 UNION SELECT 6, 15, 15, 18, 18 -- Un groupe allant de (10/10 à 18/18 en passant par 12/12 et 15/15 UNION SELECT 7, 20, 32, 20, 32; -- Un rond point faisant une circulaire de 20/32 à 20/32 --> Récursion infinie, sans cette ligne ça passe super bien WITH RECURSIVE rec_tmp (id, x1, y1, x2, y2, id_pere, niveau) AS ( SELECT id, x1, y1, x2, y2, id, 0 FROM tmp a WHERE NOT EXISTS ( SELECT 1 FROM tmp b WHERE a.id <> b.id AND a.x1 = b.x2 AND a.y1 = b.y2 ) UNION ALL SELECT b.id, b.x1, b.y1, b.x2, b.y2, a.id, a.niveau + 1 FROM rec_tmp a INNER JOIN tmp b ON a.x2 = b.x1 AND a.y2 = b.y1 ) SELECT id, dense_rank() OVER(ORDER BY id_pere) AS grp FROM rec_tmp;

---

Merci pour ta réponse,

A bientôt

Bonjour,

Vous pourriez peut-être charger l'extension PgRouting http://pgrouting.org/ qui contient des algorithmes permettant de calculer les plus courts chemins (Johnson, Floyd-Warshall, Dijkstra).
Si vous ne voulez pas recourir à des bibliothèque GIS il existe des représentations classiques des données pour faire des parcours en profondeur/largeur à partir de la fermeture transitive d'un graphe (par exemple via des matrices d'adjacence, ou via deux tableaux permettant de reconstituer une liste d'adjacence, l'un avec les premiers successeurs de chaque sommets groupés les uns à la suite des autres, l'autre les indices auxquels on passe d'un sommet de départ à l'autre dans le premier tableau, qui devrait être facilement généréed'après la représentation de votre premier message)

J'ai aussi l'impression que ce que votre premier problème revient au calcul des composantes fortement connexes pour lequel il existe aussi des algorithmes classiques: https://fr.wikipedia.org/wiki/Compos...tement_connexe

Merci CetTer,

A vrai dire j'ai trouvé une solution mais qui n'a rien à voir avec la mise bout à bout des arrêtes du graphe et au final le géocodage en France prend entre 30 et 50 millisecondes ce qui est acceptable pour mes besoins.

Ça fait entre 20 et 33 géocodages par seconde, l'objectif est de 10 minimum pour ne pas dépasser 30 secondes pour 300 géocodages nécessaires (+ les temps réseau) sinon l'utilisateur va commencer à s'impatienter dans un contexte où il joue la montre chaque matin. Donc c'est raisonnable.

En revanche, bien que les performances et la pertinence soient au rendez-vous, je trouve cette solution moche, en tout cas j'ai comme un sentiment de bricolage, et je n'aime pas ça.

Et aussi par curiosité étant donné que lorsque je sèche sur quelque chose que j'adore manipuler, ça frustre et je sens que ça donne un challenge qui va pouvoir améliorer mes compétences.

Bonne approche de checker comment fonctionne pgRouting et de la reporter sous forme de requêtes, ou faire un algo SQL à partir des papiers scientifiques. Je pense que ça se traduirait en une procédure SQL assez vaste pour décomposer, sous décomposer puis regrouper. Pourquoi pas ;)

Merci beaucoup pour tes réponses.

Tu ne serais pas sur Lille par hasard ? J'ai besoin de profiles autour de ça courant 1er trimestre 2016 si tout va bien ;)

Vous avez des difficultés parce que votre modèle est incorrect.
Pour que votre modèle puisse être efficace il faut découper vos routes en segments qui ne seront que des linestring simple avec circulation monotone.
Pour chaque segment, vous devez donc avoir :

• sens de circulation : montant ou descendant ou mixte
• N° pair debut
• N° impair debut
• N° pair fin
• N° impair fin
• geo restreint au type LINESTRING par contrainte check : CHECK(ST_GeometryType(geo) = 'ST_Linestring')

+ une colonne calculée ou vue exposant la longueur du segment via ST_Lenght.

À partir de là, toutes vos requêtes vont devenir triviales.

Pour information, dans mon ouvrage sur SQL dont je vous ais montré la couverture, vous avez exactement le problème que vous exposé en exemple avec l'avenue Richard Wallace (esplanade centrale en partie) qui en plus est limitrophe à 3 communes différentes !

Pièce jointe 189026

A +