pgRouting Manual (2.0.0)

Analytiques de graphe

«  Topologie de routage   ::   Contenu   ::   Requête personnalisée  »

Analytiques de graphe

Author:Stephen Woodbridge <>
Copyright:Stephen Woodbridge. The code source est distribué sous la licence MIT-X.


It is common to find problems with graphs that have not been constructed fully noded or in graphs with z-levels at intersection that have been entered incorrectly. An other problem is one way streets that have been entered in the wrong direction. We can not detect errors with respect to “ground” truth, but we can look for inconsistencies and some anomalies in a graph and report them for additional inspections.

We do not current have any visualization tools for these problems, but I have used mapserver to render the graph and highlight potential problem areas. Someone familiar with graphviz might contribute tools for generating images with that.

Analyser un graphe

With pgr_analyzeGraph the graph can be checked for errors. For example for table “mytab” that has “mytab_vertices_pgr” as the vertices table:

SELECT pgr_analyzeGraph('mytab', 0.000002);
NOTICE:  Performing checks, pelase wait...
NOTICE:  Analyzing for dead ends. Please wait...
NOTICE:  Analyzing for gaps. Please wait...
NOTICE:  Analyzing for isolated edges. Please wait...
NOTICE:  Analyzing for ring geometries. Please wait...
NOTICE:  Analyzing for intersections. Please wait...
NOTICE:                    Isolated segments: 158
NOTICE:                            Dead ends: 20028
NOTICE:  Potential gaps found near dead ends: 527
NOTICE:               Intersections detected: 2560
NOTICE:                      Ring geometries: 0
(1 row)

In the vertices table “mytab_vertices_pgr”:

  • Deadends are indentified by cnt=1
  • Potencial gap problems are identified with chk=1.
SELECT count(*) as deadends  FROM mytab_vertices_pgr WHERE cnt = 1;
 (1 row)

SELECT count(*) as gaps  FROM mytab_vertices_pgr WHERE chk = 1;
 (1 row)

For isolated road segments, for example, a segment where both ends are deadends. you can find these with the following query:

    FROM mytab a, mytab_vertices_pgr b, mytab_vertices_pgr c
    WHERE AND b.cnt=1 AND AND c.cnt=1;

Si vous voulez visualiser ceux-ci sur une image graphique, alors vous pouvez utiliser quelque chose comme mapserver pour rendre les arêtes et les sommets et le style basé sur cnt ou ils sont isolés, etc. Vous pouvez aussi faire cela avec un outil comme graphviz, ou geoserver ou autres outils similaires.

Analyser les routes à sens unique

pgr_analyzeOneway analyzes one way streets in a graph and identifies any flipped segments. Basically if you count the edges coming into a node and the edges exiting a node the number has to be greater than one.

Cette requête va ajouter deux colonnes à la table vertices_tmp ein int et eout int et la remplir avec les comptes appropriés. Après avoir exécuté ceci sur un graphe vous pouvez identifier les noeuds avec des problèmes potentiels avec la requête suivante.

Les règles sont définies comme un tableau de chaînes de caractères qui s’ils correspondent à la valeur col serait être comptée comme vraie pour la source ou cible sous ou en dehors de la condition.


Supposons que nous avons un tableau “st” des arêtes et une colonne à “sens unique” qui pourrait avoir des valeurs comme :

  • ‘FT’ - sens unique de la source au noeud cible.
  • ‘TF’ - sens unique de la cible au noeud source.
  • ‘B’ - route à deux voies.
  • ‘’ - champ vide, supposé à deux voies.
  • <NULL> - champ NULL, utiliser le flag two_way_if_null.

Ensuite nous pourrions former la requête suivante pour analyser les routes à sens unique pour les erreurs.

SELECT pgr_analyzeOneway('mytab',
            ARRAY['', 'B', 'TF'],
            ARRAY['', 'B', 'FT'],
            ARRAY['', 'B', 'FT'],
            ARRAY['', 'B', 'TF'],

-- now we can see the problem nodes
SELECT * FROM mytab_vertices_pgr WHERE ein=0 OR eout=0;

-- and the problem edges connected to those nodes
SELECT gid FROM mytab a, mytab_vertices_pgr b WHERE AND ein=0 OR eout=0
SELECT gid FROM mytab a, mytab_vertices_pgr b WHERE AND ein=0 OR eout=0;

Typically these problems are generated by a break in the network, the one way direction set wrong, maybe an error related to z-levels or a network that is not properly noded.

The above tools do not detect all network issues, but they will identify some common problems. There are other problems that are hard to detect because they are more global in nature like multiple disconnected networks. Think of an island with a road network that is not connected to the mainland network because the bridge or ferry routes are missing.

«  Topologie de routage   ::   Contenu   ::   Requête personnalisée  »