# Manuel de &rocs;

Tomaz
Canabrava
tomaz.canabrava@gmail.com
Andreas
Cord-Landwehr
cordlandwehr@googlemail.com
Antoine
Balestrat

    merkil33@gmail.com

Traduction française
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
02-12-2012
1.8.0 &kde; 4.10
&FDLNotice;

&rocs; est un outil d'affichage pour la théorie des graphes pour KDE.

KDE
kdeedu
mathématiques
math
graphes
sommet
arête

## Introduction

Ce chapitre fournit un aperçu des fonctionnalités essentielles et du processus de &rocs;. Pour le lecteur très pressé qui veut utiliser immédiatement &rocs;, il est conseillé au moins de lire et d'utiliser comme référence lors de l'écriture d'algorithmes.

### Objectifs, public visé et processus

&rocs; est un EDI de théorie des graphes pour toute personne intéressée par la création et l'analyse des algorithmes de graphes. Ceci inclut explicitement

- conférenciers qui veulent présenter des algorithmes à leurs élèves,

- aux élèves qui souhaitent comprendre et voir comment leurs algorithmes fonctionnent,

- et toute personne qui est intéressée dans les structures de données et les algorithmes.

Pour ces utilisateurs, &rocs; dispose d'un éditeur de structure de données simple d'utilisation pour en créer, d'un puissant moteur de langage de scripts pour exécuter les algorithmes, ainsi de nombreux outils d'aide pour vos simulations et vos expériences.

Pour utiliser &rocs;, la méthode standard est de commencer par la création d'un graphe avec l'éditeur visuel de graphes. Vous pouvez le faire, soit à la main, en ajoutant des éléments de données et en les reliant, ou en utilisant l'une du générateur de structures de données (si disponible pour le moteur sélectionné de structures de données). Les générateurs de structures de données peuvent être trouvés dans Document de graphe Outils Générer le graphe. Ensuite, vous pouvez associer des valeurs aux éléments de la structure de données, soit à la main ou en utilisant Document de graphe Outils Associer des valeurs. Enfin, vous pouvez écrire votre algorithme en Javascript et l'exécuter avec la structure de données nouvellement créée. Toutes les modifications que votre algorithme effectue sur la structure de données seront visibles directement dans l'éditeur visuel de graphe.

Une capture d'écran de &rocs;.
Une capture d'écran de &rocs;.

### &rocs; pour les nuls

Cette section fournit un aperçu synthétique des éléments essentiels de &rocs;. Les notions importantes concernant les structures de données, les moteurs de structures de données et les types d'éléments sont expliquées. La compréhension de ces concepts est utile pour comprendre comment créer et modifier ces structures de données dans &rocs;.

En général, &rocs; fonctionne avec des projets : lors du lancement de &rocs;, un projet vide est créé et vous pouvez le remplacer en chargeant ou important un autre projet. Dans les faits, un projet lui même consiste en des documents de graphe et des scripts.

#### Moteurs pour les documents de graphe et de structures de données

Un document de graphe représente le contenu d'un espace vide dans l'éditeur visuel de graphe. En fait, un document de graphe peut contenir plusieurs structures de données à la fois mais qu'un seul moteur de structures de données. Les moteurs de structures de données sont présents pour plusieurs types de graphe (graphes généraux, listes chaînées, arborescences) et fournissent pour les types de graphes spécifiques des fonctionnalités additionnelles. Cela peut être le positionnement automatique des éléments, des ensembles d'icônes spéciales ou des ensembles étendus de fonctions de scripts à utiliser dans vos algorithmes. Pour plus de détails, veuillez consulter la section correspondante du manuel. Il est possible de changer de moteur de structure de données pour un document de graphe, cependant, des informations peuvent être perdues (&pex; des arêtes en cercle dans un graphe standard ne seront pas transférées dans une arborescence si vous changez pour un moteur d'arborescence).

Les documents de graphe représentent aussi la base pour la définition des types de pointeurs et des types de données.

#### Structures de données

Les structures de données sont la base de tout travail dans &rocs;. Vous pouvez ajouter en ajouter une ou plusieurs dans un document de graphe, ajouter des éléments de données (noeuds, données) et des pointeurs vers elles, ainsi que les modifier par des scripts. Pour cela, chaque structure de données possède son nom unique qui peut être utilisé par vos scripts. Par suite de votre choix pour le moteur de structure de données actuel, il se peut que vous ne puissiez pas modifier arbitrairement les structures de données (&pex; une arborescence ne peut jamais contenir un cycle). Le moteur de structure de données est fixé par celui associé au document de graphe correspondant qui contient la structure de données.

#### Types de pointeurs

A partir des types de base, vous pouvez définir des types différents de pointeurs pouvant être utilisés dans vos structures de données. En particulier, un type de pointeur peut obtenir une disposition individuelle (essentiellement une couleur) et il est facile de ne manipuler que des pointeurs d'un type spécifique à partir de vos scripts. Les cas d'utilisation typique des pointeur peut être d'implémenter des méta-arêtes dans votre structures de données qui affichent les relations entre les éléments de données (&pex; afficher les communications intéressantes). Mais aussi, si vos scripts devront identifier des types spécifiques d'arêtes (&pex; des liens dans une arborescence ou des arêtes sécantes pour un algorithme de recherche en profondeur d'abord), les types de pointeurs peuvent être une façon élégante de le faire.

#### Types de données

Dans de nombreux problèmes de structures de données, un ensemble d'éléments de données devraient être rassemblés par groupes de différents types (&pex; problèmes de regroupement ou problèmes de couverture). Ou, il est utile pour l'exécution d'un algorithme de définir un type d'élément de données pour exprimer un type spécifique (&pex; recherche en largeur). Pour de tels cas d'utilisation, vous pouvez définir des types de données. Chaque type de données possède sa propre icône et tous les types de données peuvent être facilement accessibles à partir de vos scripts.

#### Propriétés dynamiques

Tout élément et pointeur de données peuvent avoir de nombreuses propriétés. Certaines d'entre elles existent par défaut à partir du moteur de structure de données. Pour plus de détails, veuillez consulter la documentation sur le moteur de structure de données. Pour ajouter des propriétés supplémentaires à des éléments ou des pointeurs de données, vous pouvez leur ajouter des propriétés dynamiques. Chacune d'entre elles est identifiée par son nom et peut contenir n'importe quelle valeur lui étant associée. Le nom doit commencer par une lettre (a-z ou A-Z) et peut contenir uniquement des lettres, des nombres et des « _ ». Si vous tentez d'utiliser d'autres caractères non valables dans le nom de propriété, la propriété ne sera pas modifiée.

Pour ajouter des propriétés dynamiques, utilisez les boîtes de dialogue Propriétés de données et Propriétés de pointeurs à partir des menus contextuels pour les éléments respectifs ou les fonctions de scripts comme expliqué en .

Vous pouvez aussi utiliser des scripts. Vous avez juste besoin d'utiliser `add_property` avec le nom et la valeur de votre propriété. Après cela, vous pouvez utiliser la méthode « propertyName » pour le noeud / pointeur pour définir / obtenir leurs valeurs.

Voici un exemple de comment utiliser les propriétés dynamiques avec le moteur de structures de données « Graphe ».

    nodes = myGraph.list_nodes()
    for (var i = 0 ; i < nodes.length ; ++i ){
        nodes[i].add_property("MyProperty", 0)
    }
    nodes[0].MyProperty = 2
    nodes[1].MyProperty = nodes[0].MyProperty + 2

### Tutoriel

Dans cette section, un exemple de projet est créé pour explorer quelques unes des fonctions les plus importantes de &rocs;. L'objectif est de créer un graphe et un script qui réalisent un algorithme d'approximation de niveau 2 pour le problème trajet minimum par tous les sommets. Ce problème consiste à trouver un sous-ensemble de noeuds de graphe C de taille minimale de façon que chaque noeud du graphe soit connecté à au moins un noeud dans C. Il est connu comme étant « NP-hard ». L'exemple veut illustrer comment trouver une approximation de niveau 2 en trouvant une correspondance dans le graphe donné. Dans la suite, les termes communs pour les algorithmes de graphes seront utilisés : le graphe est la structure de données, les noeuds sont les éléments de données et les arêtes sont les pointeurs).

Notre objectif est d'afficher la correspondance entre la couverture des sommets correspondante et minimale. Pour cela, il faut spécifier deux types de pointeurs, un pour afficher les arêtes qui correspondent et un pour afficher les arêtes ordinaires, ainsi que deux types de données qui seront utilisés pour distinguer les noeuds contenus dans C et ceux qui ne le sont pas.

#### Générer un graphe

Pour le moteur de structures de données « graphe », &rocs; est livré avec un outil d'aide qui peut générer des graphes. Il faut aller dans Document de graphe Outils Générer le graphe. Un graphe «Graphe aléatoire » est généré avec 30 noeuds, 90 arêtes et une valeur d'initialisation « seed » de 1 (Cette valeur permet de démarrer le générateur aléatoire de graphe : l'utilisation de la même valeur plusieurs fois produit des graphes identiques et reproductibles). Enfin, le nom du graphe est modifié via le panneau de la structure de données et `test-graphe` est appelé.

#### Créer des types

Le bouton de propriétés de document est utilisé dans le panneau de structure de données pour ouvrir la boîte de dialogue pour les types de données et de pointeurs du document de graphe courant. Pour les types de données, un nouveau type nommé « C » est ajouté qui reçoit automatiquement l'identifiant `1`. Pour ce type, l'image de serveur est sélectionnée comme icône. De plus, la page de type de pointeur est choisie et un nouveau type de pointeur nommé « correspondant » est ajouté. Celui ci prend automatiquement l'identifiant `1`. La couleur bleue est choisie.

#### L'algorithme

Enfin, il reste à implémenter l'algorithme d'approximation. Pour cela, l'implémentation suivante est utilisée :

    var E = test-graphe.list_edges() ; // ensembles des arêtes non traitées
    var C = new Array() ;            // arêtes qui correspondent
    while (E.length
    > 0) {
        var e = E[0] ;        // sélection de la première arête e={u,v}
        var u = e.start() ;
        var v = e.end() ;
        e.set_type(1) ;        // indique que l'arête est une arête qui correspond
        E.shift() ;            // supprime e (i.e., E[0]) de la liste des arêtes
        C.push(u) ;            // ajoute u à C
        C.push(v) ;            // ajoute v à C

        // marque u,v comme des noeuds de C
        u.set_type(1) ;
        v.set_type(1) ;

        // supprime de E toutes les arêtes  arrivant sur u or v
        var adjacent = u.adj_edges() ;
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]) ;  // trouve l'index
            if (index!=-1) {
                E.splice(index, 1) ; // le supprime si vraiment trouvé
            }
        }
        var adjacent = v.adj_edges() ;
        for (var i=0 ; i < adjacent.length ; i++) {
            var index = E.indexOf(adjacent[i]) ;  // trouve l'indice
            if (index!=-1) {
                E.splice(index, 1) ;  // le supprime si vraiment trouvé
            }
        }
    }
    output("Le trajet par tous les sommets contient " + C.length + " noeuds.") ;

#### Exécuter l'algorithme

Enfin, l'algorithme doit être exécuter. Pour cela, l'exécution peut être lancée par le bouton Exécuter dans le tableau de bord des scripts.

## L'interface utilisateur de &rocs;

### Éléments principaux de l'interface utilisateur

L'interface utilisateur est divisée en plusieurs parties distinctes, comme le montre la capture d'écran ci-dessous.

Éléments de l'interface de &rocs;.
Éléments de l'interface de &rocs;.

Sélecteur de document

  Dans cette barre de menu de haut niveau, vous devez sélectionner le document courant et la structure de données. La création et la suppression de structures de données comme l'accès à leurs propriétés sont aussi possibles ici.

Éditeur visuel de graphe

  Ceci est l'espace vide où les structures de données peuvent être créées et modifiées. Faites un clic droit dans cet espace sur des éléments de données ou des pointeurs pour ouvrir les menus contextuels. Vous pouvez utiliser les outils à partir de la Barre d'outils pour l'éditeur visuel de graphe pour modifier les éléments dans l'espace vide de l'éditeur visuel de graphe.

Barre de l'éditeur visuel de graphe

  Cette barre d'outils regroupe tous les outils pour l'éditeur visuel de graphe. Utilisez l'outil Ajouter des données ou Ajouter une connexion respectivement pour créer de nouveaux éléments ou pour connecter des éléments. Les nouveaux éléments de données sont ajoutés dans la structure de données actuellement sélectionnée dans le Sélecteur de documents. Veuillez noter que Ajouter des données ou Ajouter une connexion possèdent tous les deux des menus contextuels pour sélectionner le type associé aux éléments à créer. Pour plus de détails, veuillez consulter .

Panneau latéral

  Sur la droite, vous pouvez trouver le panneau latéral qui fournit plusieurs outils pour votre processus :

  - Types d'éléments : ce composant graphique vous donne un accès direct aux pointeurs disponibles et au types de données.

  - Journal : chaque projet possède son propre journal qui peut être utilisé pour, &pex; consigner les tâches, les résultats et les observations.

  - Documentation : pour obtenir un accès direct au manuel et en même temps à la documentation sur les scripts, vous pouvez ouvrir ce composant graphique.

Éditeur de script

  Dans cet éditeur de texte, vous pouvez écrire des algorithmes comme expliqué en . Vous pouvez travailler sur plusieurs algorithmes en même temps en utilisant plusieurs onglets. Un symbole en forme de disque apparaît sur l'onglet si le script a produit des changements non enregistrés.

Sortie du script

  Dans cette zone de texte, sont affichés soit les informations de débogage ou la sortie du script correspondant à votre algorithme, selon les paramètres définis en haut du composant graphique. Si le script rencontre une erreur, la sortie de débogage est automatiquement sélectionnée.

Contrôles

  Vous pouvez trouver ici les contrôles pour l'exécution de scripts. Vous pouvez exécuter le script actuellement ouvert dans l'éditeur de script en appuyant sur Exécuter . Durant l'exécution du script, il est possible de le stopper en appuyant sur le bouton Stop. Veuillez noter que l'exécutionPas à pas ne s'arrête que sur des mots clé spécifiques (voir ).

### Barres d'outils

Il y a plusieurs barres d'outils dans l'éditeur visuel de graphe qui vous permettent d'accéder aux fonctions en un seul clic. Par défaut, les barres d'outils suivantes sont affichées :

- Barre principale

- Barre d'alignement

#### Barre principale

La Barre principale est constituée des actions suivantes. Cliquer sur une action signifie que le curseur de votre souris applique cette action dans l'éditeur visuel de graphe :

- Déplacer : pour sélectionner des éléments, soit cliquez sur un espace vide, maintenez le bouton de la souris enfoncé et dessinez un rectangle qui contient des éléments de données et/ou des pointeurs pour les sélectionner ou soit cliquez directement sur un élément non encore sélectionné pour le sélectionner. Si vous cliquez sur un élément sélectionné ou sur plusieurs, en maintenant le bouton de la souris enfoncé, et en vous déplaçant autour, vous pouvez déplacer ces éléments.

- Ajouter des données : cliquez sur une position arbitraire dans un espace libre de l'éditeur visuel de graphe pour créer un nouvel élément de données qui appartient à la structure de données actuellement sélectionnée. En maintenant le pointeur de souris enfoncé sur le bouton, un menu contextuel apparaîtra à partir duquel vous pourrez sélectionner le type de données associé aux éléments de données nouvellement créés (uniquement si des types de données différentes existent).

- Ajouter une liaison : cliquez sur un élément de données, maintenez le bouton de la souris enfoncé et dessinez une ligne reliant un autre élément de données vers lequel le pointeur / arête devra se terminer. Cette action n'est réussie que si le graphe actuel permet d'ajout de cette arête (&cad; dans un graphe non orienté, vous ne pouvez pas ajouter des arêtes multiples entre deux éléments de données). En maintenant le pointeur de souris enfoncé sur le bouton, un menu contextuel apparaît à partir duquel le pointeur de type des pointeurs nouvellement créés peut être sélectionné (uniquement si différents pointeurs de type existent).

- Supprimer : cliquez sur un élément pour le supprimer. Si vous supprimez un sommet, toutes les arêtes adjacentes le seront aussi.

- Zoom : cliquez sur l'espace vide, maintenez le &BGS; enfoncé puis dessinez un rectangle. Un zoom sera fait dans l'espace vide sur la zone sélectionnée. Utilisez la molette de la souris pour faire aussi bien un zoom avant ou arrière. Un double clic avec le &BGS; fera revenir au zoom initial.

#### Barre d'alignement

Vous pouvez aussi afficher la Barre d'alignement. Sélectionner une action depuis cette barre a un effet direct sur les sommets sélectionnés :

- Haut : aligne les éléments de données par rapport à la position verticale de l'élément de données le plus haut. Cela affecte seulement les positions verticales.

- Centré : aligne les éléments de données par rapport à la position verticale donnée à partir du centre des positions verticales de tous les éléments de données sélectionnés. Cela affecte seulement les positions verticales.

- Bas : aligne les éléments de données par rapport à la position verticale de l'élément de données le plus bas. Cela affecte seulement les positions verticales.

- Gauche : aligne les éléments de données par rapport à la position horizontale de l'élément de données le plus à droite. Cela affecte seulement les positions horizontales.

- Centre : aligne les éléments de données par rapport à la position horizontale de l'élément de données le plus à droite. Cela affecte seulement les positions horizontales.

- Droite : aligne les éléments de données par rapport à la position horizontale de l'élément de données le plus à droite. Cela affecte seulement les positions horizontales.

- Cercle : aligne les éléments de données sur un cercle de diamètre égal à la distance maximale des éléments de données. Ceux-ci sont positionnés dans le même ordre que donné par la vue réalisée à partir du centre de gravité de ces éléments de données.

- Minimiser les arêtes sécantes : ré-organiser les éléments de données sélectionnés pour limiter le nom d'arêtes sécantes (application de l'algorithme de Fruchterman-Reingold).

### Travailler avec des documents de graphes

Un projet &rocs; contient un ou plusieurs documents de graphe qui peuvent être modifiés avec l'éditeur visuel de graphe. De plus, chaque document peut contenir un nombre arbitraire de structures de données. Toutes les structures de données du document utilisent ici le même moteur de structures de données. Cette section expliquera comment passer d'un document à un autre et comment en créer de nouveaux.

#### La barre de sélecteur de document

La barre de sélecteur de documents est utilisée pour sélectionner le document courant de graphe et plus tard la structure de données courante. L'utilisation de l'éditeur visuel de graphe pour créer des éléments de structures de données ajoutera automatiquement ces éléments nouvellement créés à la structure de données courante. De plus, cette barre fournit un accès direct à la suppression ou la création de nouvelles structures de données à l'intérieur du document courant.

- Nouveau : cette action créé une nouvelles structure de données en utilisant une règle automatique de nommage fournie par le moteur de structure de données. La structure de données créée est ajoutée dans le document de graphe actuellement sélectionné.

- Supprimer : cette action supprime la structure de données actuellement sélectionnée dans le sélecteur de structure de données pour le document courant.

- Propriétés de la structure de données : ouvre une boîte de dialogue donnant accès aux propriétés de la structure de données.

- Propriétés de document : ouvre une boîte de dialogue donnant accès aux propriétés de document aussi bien qu'aux types de données et de pointeurs du document.

La barre principale d'outils.
La barre de sélecteur de documents.

#### Créer et importer des documents de graphe

Pour créer un nouveau document de graphe ou pour en ajouter un au projet, utilisez Projet Nouveau document de graphe ou Projet Importer un graphe &rocs;.

## Écriture et exécution d'algorithmes dans &rocs;

&rocs; utilise en interne un moteur de langage de scripts « QtScript », qui est un moteur spécifique JavaScript. Cela signifie que tous les algorithmes que vous développez, doivent utiliser JavaScript. Le comment JavaScript fonctionne et comment écrire du code JavaScript ne sont pas traités dans ce manuel. Ainsi, ne sera expliqué que l'accès aux structures de données, aux éléments de données et aux pointeurs vers vos structures de données à partir du moteur de langage de scripts. Puisque vous n'utilisez jamais d'objets standards de structures de données mais uniquement un seul qui est fourni par le moteur de structure de données actuellement utilisé, la fonctionnalité de structure de données est étendue par le moteur associé et vous devriez prendre connaissance de la fonctionnalité spécifique. En particulier, les moteurs de structures de données utilisent des termes communs selon leurs domaines ( noeuds et arêtes dans les graphes, feuilles et racines dans les arborescences, etc. )

Il est important de savoir que les modifications faites par le moteur de langage de scripts sont directement reportées dans les propriétés de l'espace vide de l'éditeur visuel de graphe. Par conséquent, les scripts modifient en réalité les structures de données.

### Les éléments basiques de structures de données

Chaque moteur fournit un ensemble particulier de fonctions et de propriétés pour ses structures de données et leurs éléments. Mais, aussi, chaque moteur fournir les propriétés et les fonctions qui sont définies pour la structure de base de données standard. Par conséquent, tout ce qui est expliqué dans ces sections sont valables pour tout type de moteur de structure de données.

#### Propriétés basiques de structures de données

Les structures de données sont identifiées par leurs noms. Si vous avez créé une structure de données avec le nom `test-graphe`, alors, vous pouvez y accéder simplement la référençant par son identifiant. Par exemple, si vous voulez obtenir un tableau contenant tous les éléments de données dans une structure de données particulière, vous pouvez écrire `test-graphe.list_nodes() ;` dans le script.

##### Propriétés et fonctions basiques de structures de données

Chaque structure de données `test-graphe` possède les propriétés suivantes qui peuvent être lues ou écrites par `test-graphe.property` :

    nom de chaîne // identification de la structure de données

#### Propriétés et fonctions basiques des éléments de données

Chaque élément de données possède les propriétés suivantes qui peuvent être lues ou écrites :

    double x      // coordonnée en x de la position courante
        double y      // coordonnée en y de la position courant
        double width  // taille
        string value  // valeur
        int id        // identifiant unique pour l'élément de données
        string name   // nom
        string color  // couleur en hexa-décimal

De plus, chaque propriété dynamique d'un élément de données peut être adressée par son nom.

Chaque objet d'élément de données fournit les méthodes suivantes :

    int type() ;                         //  type de la donnée pour l'élément de données
        int set_type(int) ;                  // défini le type de la donnée pour l'élément de données
        void add_property(string name,      // ajoute une propriété dynamique à l'élément de données avec le nom et la valeur spécifié
                          string value) ;
        array adj_data() ;                   // liste des données adjacentes
        array adj_pointers() ;               // liste des pointeurs adjacents
        array input_pointers() ;             // liste des pointeurs en entrée
        array output_pointers() ;            // liste des pointeurs en sortie
        array loop_pointers() ;              // liste des pointeurs formant une boucle
        array connected_pointers(target) ;   // listes  des pointers pointant sur la « cible »
        void  remove() ;                     // supprime cet élément de données

#### Propriétés et fonction basiques de pointeur

Chaque pointeur possède les propriétés suivantes qui peuvent être lues ou écrites :

    string color  // couleur en hexa-décimal
        string value  // valeur
        string name   // nom
        double width  // largeur
        string style  // valeur parmi : pointillé, tiret, tiret-pointillé, pleine

De plus, chaque propriété dynamique d'un pointeur peut être adressée par son nom.

Chaque objet de pointeur fournit les méthodes suivantes :

    int type() ;                         // type de pointeur de pointeur
        int set_type(int) ;                  // définit le type de pointeur de pointeur
        void add_property(string name,      // ajoute une propriété dynamique  à l'élément de données avec le nom et la valeur spécifié
                          string value) ;
        node start() ;                       // noeud de début du pointeur
        node end() ;                         // noeud cible du pointeur
        void remove() ;                      // supprime ce pointer

### Le moteur de graphe

#### Propriétés et fonctions du graphe

##### Propriétés spécifiques du moteur de graphe

La boîte de dialogue pour les propriétés de la structure de données donne accès à la configuration des paramètres spécifiques au moteur de graphe. A cet endroit là, avec Type de graphe, vous pouvez sélectionnez le type de graphe. La signification de ces types est la suivante :

- Graphe : graphe pour lequel les même arêtes (sauf les points de départ et de fin) ne peuvent exister en plusieurs exemplaires.

- Multi-graphe : graphe pour lequel les même arêtes (sauf les points de départ et de fin) peuvent exister en plusieurs exemplaires.

##### La structure de graphe

Pour un objet donné de structure de données de type « Graphe », vous pouvez utiliser les fonctions associées suivantes :

    array list_nodes() ;                   // liste de tous les noeuds du graphe
        array list_nodes(int type) ;           // liste de tous les noeuds du graphe d'un type donné
        array list_edges() ;                   // liste de toutes les arêtes du graphe
        array list_edges(int type) ;           // liste de toutes les arêtes du graphe d'un type donné
        node add_node(name) ;                  // ajoute un nouveau noeud et le retourne
        edge add_edge(node from, node to) ;    // ajoute une nouvelle arête de « from » à « to » et la retourne
        array overlay_edges(int overlayID) ;   // liste de toutes les arêtes  d'un circuit donné
        edge add_overlay_edge(node from,
                              node to,
                              int overlayID) ; // ajoute une arête d'un type de pointeur donné dans un circuit spécifique

##### Noeuds de graphe

Pour un objet donné de structure de données de type « graphe », vous pouvez utiliser les fonctions associées suivantes sur les noeuds du graphe en addition aux propriétés fournies par les éléments de données :

    array adj_nodes() ;                    // listes de tous les noeuds  adjacents
        array adj_edges() ;                    // liste de toutes les arêtes connectées
        array input_edges() ;                  // liste des arêtes en entrée
        array output_edges() ;                 // liste des arêtes en sortie
        array loop_edges() ;                   // liste  de toutes les arêtes arrivant sur le noeud
        array connected_edges(node target) ;   // toutes arêtes qui  connecte cenoeud au noeud « target »

##### Arêtes de graphe

Pour des arêtes particulières de structure de données de type « graphe », seules les propriétés standards de la structure de données sont disponibles.

#### Algorithmes de structure de graphe

Le moteur de graphe fournit certaines fonctions spéciales qui peuvent être utilisées à partir du moteur d'écriture de scripts.

Calcul du trajet le plus court

  Calcule le trajet le plus court entre les noeuds début et fin. Les deux noeuds doivent appartenir au même graphe. Ce calcul tient compte du fait que le graphe soit orienté ou non orienté.

          tableau dijkstra-trajet-le-plus-cour noeud débutnoeudfin

Longueur du trajet la plus courte

  Calcule le trajet le plus court entre les sommets début et fin en passant par tous les autres noeuds du graphe. Ce calcul tient compte du fait que le graphe soit orienté ou non orienté.

          tableaudistances noeuddébut

### Le moteur pour les listes chaînées

#### Propriétés et fonctions pour les listes chaînées

##### La structure de liste chaînée

Pour un objet de structure de données de type « liste chaînée », vous pouvez appeler les fonctions de ce type suivantes :

    node begin() ;                           // fournit le noeud de tête de la liste chaînée
        setBegin(node begin) :                   // définit le noeud « début » comme le début de la liste et réordonne la liste
        createNode() ;                           // créer un nouveau noeud de la liste

##### Noeuds de liste chaînée

Pour un objet de structure de données de type « liste chaînée », vous pouvez utiliser les fonctions associées suivantes sur les noeuds de graphe en addition aux propriétés fournies par les éléments de données :

    node front() ;                           // retourne le prédécesseur du noeud

##### Arêtes de liste chaînée

Pour des arêtes de structure de données de type « liste chaînée », seules les propriétés standards de la structure de données sont disponibles.

### Le moteur pour arborescence

#### Propriétés et fonctions d'arborescence

##### Moteur pour arborescence

La boîte de dialogue des propriétés de structure de données vous permet de configurer les paramètres spécifiques pour le moteur de graphe. A cet endroit, la sélection du paramètre Afficher tous les pointeurs conduit à l'affichage de tous les pointeurs entre les noeuds de l'arborescence. S'il n'est pas sélectionné, les pointeurs multiples entre les même noeuds sont regroupés en un seul.

##### La structure d'arborescence

Pour un objet donné de structure de données de type « Arborescence », les propriétés suivantes peuvent être lues ou écrites :

    ShowAllPointers     // positionné à Vrai si affichage de toutes les arêtes, positionné à Faux si les arêtes multiples doivent être regroupées

Pour un objet donné de structure de données de type « Arborescence », vous pouvez appeler les fonctions associées suivantes :

    node add_data(string name) ;         // ajoute un noeud à l'arborescence avec un nom donné
        void set_root_node(node root) ;      // définit le noeud comme la racine de l'arborescence
        node root_node() ;                   // retourne la racine de l'arborescence

##### Noeuds d'arborescence

Pour un objet donné de noeud de type « Arborescence », les propriétés suivantes peuvent être lues ou écrites :

    int numberOfChilds                  // définit le nombre d'enfants (autorisés) pour ce noeud
        node left_child                     // lecture seule : noeud qui est le fils à gauche
        node right_child                    // lecture seule : noeud qui est le fils à droite
        node node_parent                    // lecture seule : noeud qui est le parent

Pour un objet donné de noeud de type « Arborescence », vous pouvez appeler les fonctions associées suivantes :

    node add_left_child(node child) ;    // ajoute un fils à gauche
        node add_right_child(node child) ;   // ajoute un fils à droite
        node add_child(node child, int i) ;  // ajoute un fils comme i ième fils du noeud
        node add_node_parent(node child) ;   // ajoute un parent (ne fonctionne que s'il a pas encore de parent défini)
        node left_child() ;                  // retourne le fils de gauche
        node right_child() ;                 // retourne le fils de droite
        node child_at(int i) ;               // return the i-th child of the node
        node node_parent() ;                 // retourne le noeud parent

##### Arêtes d'arborescence

Pour des arêtes particulières de structure de données de type « Arborescence », seules les propriétés standards de la structure de données sont disponibles.

### Contrôle de l'exécution de script

#### Inclure les fichiers

Vos documents de scripts peuvent inclure d'autres scripts. Ceci peut être utilise pour réduire la taille des documents de scripts et améliorer leur lisibilité. En utilisant Document de scripts Inclut potentiellement, vous pouvez obtenir une liste des fichiers de scripts déjà fournis avec &rocs; et qui pourraient être utilisés. Vous pouvez intégrer un fichier de script avec la commande suivante :

    include_script(string path) ;            // emplacement relatif ou absolu vers le fichier de script

#### Sortie du script

Durant l'exécution d'un algorithme, les sorties du débogage et du programme sont affichés dans la Sortie de débogage et de script. Si le moteur de langage de scripts détecte une erreur de syntaxe dans votre script, l'erreur est aussi affichée comme un message de débogage. Veuillez noter que tous les messages du programme sont aussi affichés sur la sortie de débogage (affiché comme du texte en gras).

Vous pouvez contrôler le texte qui est affiché par la sortie du script par les fonctions suivantes :

    output(string message) ;            // affiche le message comme une sortie du script
        debug(string message) ;             // affiche le message comme une sortie de débogage

#### Contrôle de l'exécution de script

Il y a différents modes d'exécution pour vos scripts.

Vous pouvez contrôler le texte qui est affiché par la sortie du script par les fonctions suivantes :

- Démarrer : exécute le script jusqu'à ce qu'il se termine.

- Arrêter : arrêter l'exécution du script (disponible uniquement si le script est en cours d'exécution).

- Pas à pas : exécute un script jusqu'à ce qu'un pas soit exécuté. Un pas s'arrête quand le script appelle la fonction `interrupt()` :

      interrupt() ;    // termine un pas

- Débogage : exécute un script dans le mode de débogage. Cela ouvre une fenêtre de dialogue QtScript pour débogage.

## Importer et Exporter

### Échanger des projets &rocs;

Les projets &rocs; peuvent être importés et exportés sous forme de fichiers d'archives `.tar.gz`. Ces archives peuvent servir pour s'échanger des projets. Les importations et exportations peuvent se faire respectivement avec Fichier Importer le project and Fichier Exporter le project.

### Importer et Exporter des documents de graphe

&rocs; prend en charge actuellement l'import et l'export pour les formats de fichier suivants :

- Fichiers DOT, aussi connus sous le nom de fichiers Graphviz

- Fichiers GML

- Fichiers au format de graphe Trivial

#### Format de fichier de graphe Trivial

Le Trivial Graph Format (TGF) est un format de fichier construit sur du texte simple pour décrire des graphes. Un fichier TGF consiste en une liste de définition de noeuds, qui fait correspondre des identifiants de noeuds à des étiquettes, suivie par une liste d'arêtes. Dans ce format, il n'est possible de n'avoir qu'un label par noeud et une valeur par arête. &rocs; interprète les graphes importés comme des graphes non dirigés. Les graphes exportés contiendront deux arêtes par connexion si les connexions sont bi-directionnelles.

##### Spécification de format

- Le fichier débute par une liste de noeuds (un noeud par ligne), suivi par une ligne avec uniquement le caractère « # », suivi par une liste d'arêtes (une arête par ligne).

- Un noeud consiste en un entier (identifiant), suivi par un espace et suivi par une chaîne arbitraire.

- Une arête consiste en deux entiers (identifiants) séparés par une espace, suivie par une espace, suivie par une chaîne arbitraire. Par hypothèse, l'arête dirigée va du premier identifiant vers le second.

##### Exemple

    1 noeud de départ
    2 transmetteur
    3 récepteur
    #
    1 2 bleu
    2 1 rouge
    2 3 vert

#### Langage DOT / Format de fichier de graphe Graphviz

Le langage DOT est un langage de description de graphe en texte brute qui permet à la fois une représentation correcte, lisible par un humain, de graphe et aussi, un traitement efficace par des programmes de mise en forme de graphes. DOT est le format de fichiers par défaut pour la suite d'affichage de graphes Graphviz. Mais, il est aussi largement utilisé par d'autres outils de graphe. Les extensions classiques des fichiers pour DOT sont .gv et .dot.

##### Fonctionnalités non prises en charge

&rocs; peut traiter tout fichier de graphe qui contient un graphe possédant une spécification en langage DOT http://www.graphviz.org/content/dot-language. La prise en charge des fonctionnalités du langage est complète, malgré les restrictions suivantes :

- sous-graphe : à cause de manques dans la notion de sous-graphe dans &rocs;, ceux-co ne sont importés que comme ensemble d'éléments et de connexion de données. En particulier, les connexions vers ou à partir de sous-graphes ne sont pas importés.

- Attributs &HTML; et &XML; : les attributs (comme les étiquettes) qui contiennent des syntaxes &HTML; ou &XML; sont lus tel quel. En particulier, aucune modification de polices et de styles n'est faite sur ces attributs.

##### Exemple

    digraph myGraph {
        a -> b -> c;
        b -> d;
    }

## Remerciements et licence

&rocs;

Copyright du programme :

- Copyright 2008 par Ugo Sangiori (ugorox AT gmail.com)

- Copyright 2008-2012 par Tomaz Canabrava (tcanabrava AT kde.org)

- Copyright 2008-2012 par Wagner Reck (wagner.reck AT gmail.com)

- Copyright 2011-2012 par Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

Copyright pour la documentation :

- Copyright 2009 pour la documentation par &Anne-Marie.Mahfouf; &Anne-Marie.Mahfouf.mail;

- Copyright 2009 pour la documentation par Tomaz Canabrava (tcanabrava AT kde.org)

- Copyright 2011-2012 pour la documentation par Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

Traduction française par &XavierBesnard;, Antoine Balestrat merkil33@gmail.com.

&underFDL; &underGPL;

## Installation

### Comment obtenir &rocs;

&install.intro.documentation;

### Compilation et installation

&install.compile.documentation;

&documentation.index;