Tutorial de la bibliothèque de graphes

Description

Tutorial de la biblioth`eque de graphes
Mathieu Rondeau, [e-mail]
22 octobre 20031Table des mati`eres
1 Tutorial 3
1.1 Graphe et parcours de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Tutorial 11
2.1 Cr´eation d’un graphe hi´erarchique . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Cr´ d’un graphe hi´erarchique r´ecurif . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Utilisation de sous mod`eles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Chapitre 1
Tutorial
Les sections qui suivent pr´esentent diff´erents exemples d’utilisation de la librairie de graphe.
Tous les codes se trouvent dans le r´epertoire :
– Pole/demos/graph
Des projets visual C++, gcc et CodeWarrior sont disponibles :
– Visual C++ : SimpleG.dsp et HierarG.dsp dans le r´epertoire des fichiers.
– gcc : Pas encore disponible.
– CodeWarrior:ImporterGraphTest.mcp.xmldansler´epertoirePole/CW xml/projects/demo/
1.1 Graphe et parcours de graphe
– Pole/demos/graph/SimpleG.cpp
Un graphe doit pouvoir ˆetre cr´e´e par l’ajour de nœuds, de ports et de liens. Une fois cela
fait, il faut pouvoir parcourir ces structures de multiples mani`eres. Cette exemple pr´esente la
cr´eation d’un graphe et l’ensemble des m´ethodes de parcours de constituants du graphe.
1 void test_basics(void)
2 {
3 MyGraph graph;
4
5
6 MyGraph::InternalNodeId n1;
7 n2;
8
9
10 MyGraph::InternalPortId p01;
11 p11;
12 p12;
13 p21;
14
15
16 MyGraph::InternalLinkId l0111;
17 l1221 ...

Sujets

• Mo'vez Lang
• L'Itinéraire (ensemble)
• Clio
• Graphe complet
• Imagerie scolaire
• Hawker Siddeley Harrier

Informations

• Publié par: Enji
• Nombre de lectures: 142
• Langue: Français

Extrait

Tutorial

de

Mathieu

la

biblioth`eque

Rondeau,

22

de

graphes

[e-mail]

octobre

2003

1

Table d ti` es ma eres

1

2

Tutorial 1.1 Graphe et parcours de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Tutorial 2.1Cr´eationd’ungraphehi´archique . . . . . . . . . . . . . . . . . . . . . . . . . . er 2.2Cr´eationd’ungraphehie´rarchiquere´curif . . . . . . . . . . . . . . . . . . . . . . 2.3Utilisationdesousmod`eles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3

11 11 16 17

Chapitre 1

Tutorial

Lessectionsquisuiventpr´esententdiff´erentsexemplesd’utilisationdelalibrairiedegraphe. Touslescodessetrouventdansler´epertoire: – Pole/demos/graph Des projets visual C++, gcc et CodeWarrior sont disponibles : –VisualC++:SimpleG.dspetHierarG.dspdansler´epertoiredesfichiers. – gcc : Pas encore disponible. – CodeWarrior : Importer GraphTest.mcp.xml dans l ´ rtoire Pole/CW xml/projects/demo/ e repe

1.1 Graphe et parcours de graphe – Pole/demos/graph/SimpleG.cpp Ungraphedoitpouvoireˆtrecre´´eparl’ajourdenœuds,deportsetdeliens.Unefoiscela fait,ilfautpouvoirparcourircesstructuresdemultiplesmanie`res.Cetteexemplepr´esentela ´eationd’ungraphetl’ensembledesm´ethodesdeparcoursdeconstituantsdugraphe. cr e 1 void te _ s(vo ) st basic id 2 { 3 MyGraph graph; 4 5 6 MyGraph::InternalNodeId n1; 7 MyGraph::InternalNodeId n2; 8 9 10 MyGraph::InternalPortId p01; 11 MyGraph::InternalPortId p11; 12 MyGraph::InternalPortId p12; 13 MyGraph::InternalPortId p21; 14 15 16 MyGraph::InternalLinkId l0111; 17 MyGraph::InternalLinkId l1221; 18 19 20 allValues[n1 = graph.CreateNode()] = 1.0; 21 allValues[n2 = graph.CreateNode()] = 2.0; 22 23 allValues[p01 = graph.CreatePort()] = 0.1; 24 allValues[p11 = graph.CreatePort(n1)] = 1.1; 25 allValues[p12 = graph.CreatePort(n1)] = 1.2;

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

allValues[p21 = graph.CreatePort(n2)] = 2.1;

graph.CreatePort();

allValues[l0111 = graph.CreateLink(p01,p11)] = 1.11; allValues[l1221 = graph.CreateLink(p12,p21)] = 12.21;

DISPLAY_EXPR(n1->opposite(l0111)); DISPLAY_EXPR(n2->opposite(l1221));

DISPLAY_EXPR(n1); DISPLAY_EXPR(p11); _ R(l1221); DISPLAY EXP

DISPLAY_EXPR(p12->node); DISPLAY_EXPR(p12->link); _ XP (l1221->second); DISPLAY E R

PAUSE("All nodes"); AllNodesPath<MyGraph> allNodes(graph); _EXPR(*ni); DISPLAY }} PAUSE("All ports"); AllPortsPath<MyGraph> allPorts(graph); {for (AllPortsPath<MyGraph>::const_iterator pi = allPorts.begin(); pi != allPorts.end(); pi++) { _ DISPLAY EXPR(*pi); }} PAUSE("All free ports"); ExternalPortsPath<MyGraph> freePorts(graph); {for (ExternalPortsPath<MyGraph>::const_iterator fpi = freePorts.begin(); fpi != freePorts.end(); fp i++) { DISPLAY_EXPR(*fpi); }} PAUSE("All links"); AllLinksPath<MyGraph> allLinks(graph); {for (AllLinksPath<MyGraph>::const_iterator li = allLinks.begin(); li != allLinks.end(); li++) { DISPLAY_EXPR(*li); }} PAUSE("All ports of n1"); PortsOfNodePath<MyGraph> portsOfNode1(graph,n1); {for (PortsOfNodePath<MyGraph>::const_iterator pn1i = portsOfNode1.begin(); pn1i != portsOfNode1.end (); pn1i++) { }} PAUSE("All ports of n2"); PortsOfNodePath<MyGraph> portsOfNode2(graph,n2); {for (PortsOfNodePath<MyGraph>::const_iterator pn2i = portsOfNode2.begin(); pn2i != portsOfNode2.end (); pn2i++) { }} PAUSE("All links of n1"); LinksOfNodePath<MyGraph> linksOfNode(graph,n1); {for (LinksOfNodePath<MyGraph>::const_iterator ln1i = linksOfNode.begin(); ln1i != linksOfNode.end() ; ln1i++) { }}

4

86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145

PAUSE("Links from n1"); DirectLinksOfNodePath<MyGraph> linksFromNode(graph,n1); {for (DirectLinksOfNodePath<MyGraph>::const_iterator lfn1i = linksFromNode.begin(); lfn1i != linksFr omNode.end(); lfn1i++) { DISPLAY_EXPR(*lfn1i); }} PAUSE("Links to n1"); IndirectLinksOfNodePath<MyGraph> linksToNode(graph,n1); {for (IndirectLinksOfNodePath<MyGraph>::const_iterator ltn1i = linksToNode.begin(); ltn1i != linksTo Node.end(); ltn1i++) { _ DISPLAY EXPR(*ltn1i); }} PAUSE("All neighbours of n1"); NodesOfNodePath<MyGraph> neighboursOfN1(graph,n1); {for (NodesOfNodePath<MyGraph>::co _ ator nn1i = neighboursOfN1.begin(); nn1i != neighboursOfN1 nst iter .end(); nn1i++) { }} PAUSE("Direct neighbours of n1"); DirectNodesOfNodePath<MyGraph> dNeighboursOfN1(graph,n1); {for (DirectNodesOfNodePath<MyGraph>::const_iterator dnn1i = dNeighboursOfN1.begin(); dnn1i != dNeig hboursOfN1.end(); dnn1i++) { _ XPR(*dnn1i); DISPLAY E }} PAUSE("Indirect neighbours of n1"); IndirectNodesOfNodePath<MyGraph> iNeighboursOfN1(graph,n1); {for (IndirectNodesOfNodePath<MyGraph>::const_iterator inn1i = iNeighboursOfN1.begin(); inn1i != iNe ighboursOfN1.end(); inn1i++) { DISPLAY_EXPR(*inn1i); }} PAUSE("All neighbours of n2"); NodesOfNodePath<MyGraph> neighboursOfN2(graph,n2); {for (NodesOfNodePath<MyGraph>::const_iterator nn2i = neighboursOfN2.begin(); nn2i != neighboursOfN2 .end(); nn2i++) { }} PAUSE("Direct neighbours of n2"); DirectNodesOfNodePath<MyGraph> dNeighboursOfN2(graph,n2); {for (DirectNodesOfNodePath<MyGraph>::const_iterator dnn2i = dNeighboursOfN2.begin(); dnn2i != dNeig hboursOfN2.end(); dnn2i++) { DISPLAY_EXPR(*dnn2i); }} PAUSE("Indirect neighbours of n2"); IndirectNodesOfNodePath<MyGraph> iNeighboursOfN2(graph,n2); {for (IndirectNodesOfNodePath<MyGraph>::co _ ator inn2i = iNeighboursOfN2.begin(); inn2i != iNe nst iter ighboursOfN2.end(); inn2i++) { _ PR(* i); DISPLAY EX inn2 }} MapSubGraphStruct fsgs(graph); fsgs.include_Node[n1] = true; fsgs.include_Node[n2] = true; fsgs.include_Port[p12] = true; fsgs.include_Port[p21] = true; fsgs.include_Link[l1221] = true; PAUSE("All sub nodes"); AllNodesPath<MapSubGraphStruct > allSubNodes(fsgs); {for (AllNodesPath<MapSubGraphStruct>::const_iterator ni = allSubNodes.begin(); ni != allSubNodes.en d(); ni++) { }} PAUSE("All sub links of n1"); LinksOfNodePath<MapSubGraphStruct> subLinksOfNode(fsgs,n1);

5

146 {for (LinksOfNodePath<MapSubGraphStruct>::const_iterator ln1i = subLinksOfNode.begin(); ln1i != subL 147 inksOfNode.end(); ln1i++) { 148 DISPLAY_EXPR(*ln1i); 149 }} 150 PAUSE("All adjacent nodes of n1"); 151 NodesOfNodePath<MapSubGraphStruct> subNodesOfNode(fsgs,n1); 152 {for (NodesOfNodePath<MapSubGraphStruct>::const_iterator nn1i = subNodesOfNode.begin(); nn1i != subN 153 odesOfNode.end(); nn1i++) { 154 DISPLAY_EXPR(*nn1i); 155 }} 156 157 PAUSE("End of basics"); 158

Ligne 3 Onde´clareungraphesimple. Ligne 6 Onde´clareunecle´denœud n 1 . C’est en fait un pointeur d’un type particulier. Ce pointeurunefoisalloue´econtiendradesinformationspropresaunœud.Onsertdel’adresse decepointeurcommeunecle´uniqueunefoisqu’ilaurae´t´ecreevial’op´erateur new . ´´ Ligne 7 Onde´clareunesecondecl´edenœud n 2 . Ligne 10 Ond´eclarelacl´edeport p 01 .Commelescle´sdenœuds,lescl´esdeportcontiennent des informations comme le nœud d’appartenance. On se sert de l’adresse du pointeur commed’unecle´unique. Ligne 11 Onde´clarelacle´deport p 11 . Ligne 12 Ond´eclarelacle´deport p 12 . Ligne 13 Ond´eclarelacle´deport p 21 . Ligne 16 Ond´eclarelacl´edelien l 0111 .Commelescle´sdenœudsetdeports,lescle´sdeliens sontdespointeursquicontiennentdesinformationscommelede´butetlafinduliensous laformedecle´deport.L’adresseduliensertdecl´eunique. Ligne 17 Onde´clarelacle´delien l 1221 Ligne 20 Oncr´eetoutd’abordlenœud n 1 .Lame´thodedegraphe CreateNode faitappela` l’op´erateur new qui cree l’adresse unique de n 1 dontonsesertcommecl´e.Cettecle´sert ´ a`atteindreunedonn´eedetypere´ellesouslaformed’unemapentrel’adressede n 1 et la valeurr´eelle1.0. Ligne 21 Oncr´eelacl´edenœud n 2 etonassocie`acettecle´lavaleur2.0. Ligne 23 Oncr´eeleportlibre p 01 .Leportestditlibrecariln’appartienta`aucunnœud.A l’adresse de ce port on associe la valeur 0.1. Ligne 24 Oncr´eeleport p 11 qui appartient au nœud n 1 . On lui associe la valeur 1.1. Ligne 25 On ´e le port p 12 qui appartient au nœud n 1 . On lui associe la valeur 1.2. cre Ligne 26 Oncr´eeleport p 21 qui appartient au nœud n 2 . On lui associe la valeur 2.1. Ligne 29 Oncre´eunportlibresansretenirlacle´deportquiae´t´ecre´e´. Ligne 32 Oncr´eelelien l 1011 . Un lien est defini entre deux ports, ici p 01 et p 11 . On associ ` e a l’adresse(lacl´e)decelienlavaleur1.11. Ligne 33 Oncr´eelelien l 1221 entre les ports p 12 et p 21 et on lui associe la valeur 12.21. Ligne 37 Onutiliselame´thodedenœud opposite qui prend comme argument un lien. On obtientlenœudoppose´auliendecenœud.(Cepeutˆetreluimˆeme).Onaffichelavaleur du nœud.

6

Ligne 38 Onr´ecupe´relenœudoppose´aulien l 1221 par rapport au nœud n 2 . On affiche la valeur du nœud. Ligne 41 On affiche la valeur du nœud n 1 . Ligne 42 On affiche la valeur du port p 11 Ligne 43 On affiche la valeur du lien l 1221 Ligne 46 Onr´ecup´erelenœudquiposs`edeleport p 12 etonl’affichelavaleurre´elleassocie´e. Ligne 47 On r´ ´ l li i relie le port p 12 `aunautreportetonl’affichelavaleurre´elle ecupere e en qu associe´e. Ligne 48 onaffichelelavaleurassoci´eeaulien l 1221 . Ligne 52 Oncr´eeuncontaineurd’ite´rateurdenœud allNodes par rapport au graphe graph . Ce containeurvapermettredeconstruirel’it´erateurpermettantdeparcourirtouslesnœuds de graph .Onde´clarel’ite´rateurdenœudde graph , n i .Onvafaireparcourir`acetite´rateur l’ensembledesnœudsjusqu’`aatteindrel’ite´rateur allNodes.end() . Ligne 53 Onaffichelavaleurassocie´eaunœud ∗ n i . Ligne 56 Oncre´euncontaineurd’ite´rateurdeport allPorts par rapport au graphe graph. Ce containeurvapermettredeconstruirel’ite´rateurpermettantdeparcourirtouslesportsde graph . Ligne 57 Onde´clarel’ite´rateurdeportde graph , p i .Onvafaireparcourira`cetite´rateur l’ensembledesportsjusqu’a`atteindrel’ite´rateur allPorts.end() . Ligne 58 Onaffichelavaleurassocie´eauport ∗ p i . Ligne 61 Oncr´eeuncontaineurd’ite´rateurdeportlibre(n’appartenantpas`aunnœud) freePorts parrapportaugraphegraph.Cecontaineurvapermettredeconstruirel’ite´rateur permettant de parcourir tous les ports libres de graph . Lignes 62,63 Onde´clarel’it´erateurdeportlibrede graph , f p i .Onvafaireparcourir`acet it´erateurl’ensembledesportslibresjusqu’a`atteindrel’ite´rateur freePorts.end() . Ligne 64 Onaffichelavaleurassoci´eeaulien ∗ f p i . Ligne 67 Oncr´eeuncontaineurd’ite´rateurdeliens allLinks par rapport au graphe graph. Cecontaineurvapermettredeconstruirel’it´erateurpermettantdeparcourirtouslesliens de graph . Ligne 68 Ond´eclarel’ite´rateurdeportlibrede graph , l i .Onvafaireparcourir`acetite´rateur l’ensembledesliensjusqu’`aatteindrel’ite´rateur allLinks.end() . Ligne 69 Onaffichelavaleurassocie´eaulien ∗ l i . Ligne 72 Oncr´eeuncontaineurd’it´erateurdeportsdunœud n 1 portsofNode1 par rapport au graphegraph.Cecontaineurvapermettredeconstruirel’ite´rateurpermettantdeparcourir tous les ports du nœud n 1 de graph . Lignes 73,74 Ond´eclarel’ite´rateurdeportdunœud n 1 de graph , p n 1 i .Onvafaireparcourira` cetite´rateurl’ensembledesportsdunœud n 1 jusqu’`aatteindrel’ite´rateur portsOfNode1.end() . DISPLAYEXPR(*pn1i);//Onaffichelavaleurassoci´eeauport ∗ p n 1 i . Ligne 77 Oncr´eeuncontaineurd’it´erateurdeportsdunœud n 2 portsofNode2 par rapport au graphegraph.Cecontaineurvapermettredeconstruirel’ite´rateurpermettantdeparcourir tous les ports du nœud n 2 de graph .

7