9. Placement algorithms

Placement algorithms allow non-geographic Cartesian coordinates (i.j) to be assigned to each node in the graph, making their graphic representation possible.

There are two main categories of algorithms. The former use oriented graphs (GO) for which the edges have a precise sense of course (the edges are then called arcs), while the latter consider that the edges are not oriented (GNO).

This results in a different graphical organization, with the root node for oriented graphs generally positioned at the top of the graph, while it is in a central position (but not always) for non-oriented graphs.

The examples produced from the algorithms described below were all generated from the same source dataset representing a fiber-to-the-home (FTTH) distribution (tree) network.

Le nœud source fourni à l'algorithme (SRO-018-201) n'est pas le véritable nœud racine de l'arbre (NRO-82-026) ce qui permet d'illustrer certaines différences entre les algorithmes exploitant des graphes orientés (GO) et ceux exploitant des graphes non orientés (GNO).

Jeu de données source des exemples :

• in Sqlite format

• in GraphML format

1-Tree on grid

Cet algorithme permet de positionner les nœuds d'un arbre sur une grille. L'identifiant du nœud racine doit être fourni et sert d'origine au dessin de l'arbre. Sinon, le premier noeud du graphe est utilisé comme noeud racine. Le graphe est considéré comme non orienté, tous les nœuds sont donc représentés quel que soit le nœud racine. C'est cet algorithme qui est utilisé par GraphLayouterForExcel.

Source : Veremes

Exemple :
Exemple de représentation avec Algorithme n°1

2-Circulaire

Cet algorithme permet de positionner les nœuds d'un graphe quelconque sur un cercle. Le nœud racine est positionné en haut du cercle. Le graphe est considéré comme non orienté, tous les nœuds sont donc représentés quel que soit le nœud racine.

Source : Veremes

Exemple :
Exemple de représentation avec Algorithme n°2

3-Circulaire Centre

Cet algorithme permet de positionner les nœuds d'un graphe quelconque sur un cercle. Le nœud racine est positionné au centre du cercle. Le graphe est considéré comme non orienté, tous les nœuds sont donc représentés quel que soit le nœud racine.

Source : Veremes

Exemple :
Exemple de représentation avec Algorithme n°3

4-Dot

Cet algorithme permet de positionner les nœuds d'un graphe orienté sous une forme arborescente. Le nœud racine est présenté en haut du graphe.

Source: Graphviz(see detailed documentation)

Exemple :
Exemple de représentation avec Algorithme n°4

5-Circulaire

Cet algorithme permet de positionner les nœuds d'un graphe quelconque sur un cercle. Le nœud racine est positionné en haut du cercle. Le graphe est considéré comme orienté, seul le nœud racine et les nœuds en aval du nœud sont représentés. Par rapport à l'algorithme 2-Circulaire qui donne un résutat comparable, 5-Circulaire minimise la longueur totale des arêtes en positionnant les noeuds de manière pertinente sur le cercle.

Source : Veremes

Exemple :
Exemple de représentation avec Algorithme n°5

6-Circulaire Centre

Cet algorithme permet de positionner les nœuds d'un graphe quelconque sur un cercle. Le nœud racine est positionné au centre du cercle. Le graphe est considéré comme orienté, seul le nœud racine et les nœuds en aval du nœud sont représentés. Par rapport à l'algorithme 3-Circulaire Centre qui donne un résutat comparable, 6-Circulaire Centre minimise la longueur totale des arêtes en positionnant les noeuds de manière pertinente sur le cercle.

Source : Veremes

Exemple :
Exemple de représentation avec Algorithme n°6

7-Radial

Cet algorithme permet de positionner les nœuds d'un graphe quelconque sur un ensemble de cercles concentriques. Le nœud racine est positionné au centre du graphe. Le graphe est considéré comme orienté, seul le nœud racine et les nœuds en aval du nœud sont représentés.

Source : Veremes

Exemple :
Exemple de représentation avec Algorithme n°7

8-Neato

Cet algorithme permet de positionner les nœuds d'un graphe non orienté quelconque. Le nœud racine est positionné au centre du graphe.

Source : Graphviz - Documentation

Exemple :
Exemple de représentation avec Algorithme n°8

9-Twopi (radial)

Cet algorithme permet de positionner les nœuds d'un graphe quelconque sur un ensemble de cercles concentriques. Le nœud racine est positionné au centre du graphe.

Source : Graphviz - Documentation

Exemple :
Exemple de représentation avec Algorithme n°9

10-Circo (circulaire)

Cet algorithme permet de positionner les nœuds d'un graphe quelconque selon un ensemble de cercles. Le nœud racine est positionné au centre du graphe. Le graphe est considéré comme orienté, seul le nœud racine et les nœuds en aval du nœud sont représentés.

Source : Graphviz - Documentation

Exemple :
Exemple de représentation avec Algorithme n°10

11-FDP

Cet algorithme permet de positionner les nœuds d'un graphe non orienté quelconque. Le nœud racine est positionné au centre du graphe.

Source: Graphviz - Documentation

Exemple :
Exemple de représentation avec Algorithme n°11

12-SFDP

Algorithme proche de FDP mais adapté à de larges jeux de données.

Source: Graphviz - Documentation

Exemple :
Exemple de représentation avec Algorithme n°12