tutorial

Informations

• Publié par: Nezog
• Nombre de lectures: 19
• Langue: Français

Extrait

Tutorial de la biblioth`eque de graphes
Mathieu Rondeau, [e-mail]
22 octobre 20031Table 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Chapitre 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;
18
19
20 allValues[n1 = graph.CreateNode()] = 1.0;
21 allValues[n2 = = 2.0;
22
23 allValues[p01 = graph.CreatePort()] = 0.1;
24 allValues[p11 = graph.CreatePort(n1)] = 1.1;
25 allValues[p12 =1)] = 1.2;26 allValues[p21 = graph.CreatePort(n2)] = 2.1;
27
28
29 graph.CreatePort();
30
31
32 allValues[l0111 = graph.CreateLink(p01,p11)] = 1.11;
33 allValues[l1221 =(p12,p21)] = 12.21;
34
35
36
37 DISPLAY_EXPR(n1->opposite(l0111));
38 DISPLAY_EXPR(n2->opposite(l1221));
39
40
41 DISPLAY_EXPR(n1);
42 DISPLAY_EXPR(p11);
43 DISPLAY_EXPR(l1221);
44
45
46 DISPLAY_EXPR(p12->node);
47 DISPLAY_EXPR(p12->link);
48 DISPLAY_EXPR(l1221->second);
49
50
51 PAUSE("All nodes");
52 AllNodesPath<MyGraph> allNodes(graph);
53 DISPLAY_EXPR(*ni);
54 }}
55 PAUSE("All ports");
56 AllPortsPath<MyGraph> allPorts(graph);
57 {for (AllPortsPath<MyGraph>::const_iterator pi = allPorts.begin(); pi != allPorts.end(); pi++) {
58 DISPLAY_EXPR(*pi);
59 }}
60 PAUSE("All free ports");
61 ExternalPortsPath<MyGraph> freePorts(graph);
62 {for (ExternalPortsPath<MyGraph>::const_iterator fpi = freePorts.begin(); fpi != freePorts.end(); fp
63 i++) {
64 DISPLAY_EXPR(*fpi);
65 }}
66 PAUSE("All links");
67 AllLinksPath<MyGraph> allLinks(graph);
68 {for (AllLinksPath<MyGraph>::const_iterator li = allLinks.begin(); li != allLinks.end(); li++) {
69 DISPLAY_EXPR(*li);
70 }}
71 PAUSE("All ports of n1");
72 PortsOfNodePath<MyGraph> portsOfNode1(graph,n1);
73 {for (PortsOfNodePath<MyGraph>::const_iterator pn1i = portsOfNode1.begin(); pn1i != portsOfNode1.end
74 (); pn1i++) {
75 }}
76 PAUSE("All ports of n2");
77 portsOfNode2(graph,n2);
78 {foronst_iterator pn2i = portsOfNode2.begin(); pn2i != portsOfNode2.end
79 (); pn2i++) {
80 }}
81 PAUSE("All links of n1");
82 LinksOfNodePath<MyGraph> linksOfNode(graph,n1);
83 {for (LinksOfNodePath<MyGraph>::const_iterator ln1i = linksOfNode.begin(); ln1i != linksOfNode.end()
84 ; ln1i++) {
85 }}
486 PAUSE("Links from n1");
87 DirectLinksOfNodePath<MyGraph> linksFromNode(graph,n1);
88 {for (DirectLinksOfNodePath<MyGraph>::const_iterator lfn1i = linksFromNode.begin(); lfn1i != linksFr
89 omNode.end(); lfn1i++) {
90 DISPLAY_EXPR(*lfn1i);
91 }}
92 PAUSE("Links to n1");
93 IndirectLinksOfNodePath<MyGraph> linksToNode(graph,n1);
94 {for (IndirectLinksOfNodePath<MyGraph>::const_iterator ltn1i = linksToNode.begin(); ltn1i != linksTo
95 Node.end(); ltn1i++) {
96 DISPLAY_EXPR(*ltn1i);
97 }}
98 PAUSE("All neighbours of n1");
99 NodesOfNodePath<MyGraph> neighboursOfN1(graph,n1);
100 {for (NodesOfNodePath<MyGraph>::const_iterator nn1i = neighboursOfN1.begin(); nn1i != neighboursOfN1
101 .end(); nn1i++) {
102 }}
103 PAUSE("Direct neighbours of n1");
104 DirectNodesOfNodePath<MyGraph> dNeighboursOfN1(graph,n1);
105 {for (DirectNodesOfNodePath<MyGraph>::const_iterator dnn1i = dNeighboursOfN1.begin(); dnn1i != dNeig
106 hboursOfN1.end(); dnn1i++) {
107 DISPLAY_EXPR(*dnn1i);
108 }}
109 PAUSE("Indirect neighbours of n1");
110 IndirectNodesOfNodePath<MyGraph> iNeighboursOfN1(graph,n1);
111 {for (IndirectNodesOfNodePath<MyGraph>::const_iterator inn1i = iNeighboursOfN1.begin(); inn1i != iNe
112 ighboursOfN1.end(); inn1i++) {
113 DISPLAY_EXPR(*inn1i);
114 }}
115 PAUSE("All neighbours of n2");
116 NodesOfNodePath<MyGraph> neighboursOfN2(graph,n2);
117 {for (NodesOfNodePath<MyGraph>::const_iterator nn2i = neighboursOfN2.begin(); nn2i != neighboursOfN2
118 .end(); nn2i++) {
119 }}
120 PAUSE("Direct neighbours of n2");
121 DirectNodesOfNodePath<MyGraph> dNeighboursOfN2(graph,n2);
122 {for (DirectNodesOfNodePath<MyGraph>::const_iterator dnn2i = dNeighboursOfN2.begin(); dnn2i != dNeig
123 hboursOfN2.end(); dnn2i++) {
124 DISPLAY_EXPR(*dnn2i);
125 }}
126 PAUSE("Indirect neighbours of n2");
127 IndirectNodesOfNodePath<MyGraph> iNeighboursOfN2(graph,n2);
128 {for (IndirectNodesOfNodePath<MyGraph>::const_iterator inn2i = iNeighboursOfN2.begin(); inn2i != iNe
129 ighboursOfN2.end(); inn2i++) {
130 DISPLAY_EXPR(*inn2i);
131 }}
132
133 MapSubGraphStruct fsgs(graph);
134 fsgs.include_Node[n1] = true;
135 fsgs.include_Node[n2] =
136 fsgs.include_Port[p12] = true;
137 fsgs.include_Port[p21] =
138 fsgs.include_Link[l1221] = true;
139 PAUSE("All sub nodes");
140 AllNodesPath<MapSubGraphStruct > allSubNodes(fsgs);
141 {for (AllNodesPath<MapSubGraphStruct>::const_iterator ni = allSubNodes.begin(); ni != allSubNodes.en
142 d(); ni++) {
143 }}
144 PAUSE("All sub links of n1");
145 LinksOfNodePath<MapSubGraphStruct> subLinksOfNode(fsgs,n1);
5146 {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 On d´eclare un graphe simple.
Ligne 6 On d´eclare une cl´e de nœud n . C’est en fait un pointeur d’un type particulier. Ce1
pointeurunefoisallou´eecontiendradesinformationspropresaunœud.Onsertdel’adresse
de ce pointeur comme une cl´e unique une fois qu’il aura ´et´e cr´e´e via l’op´erateur new.
Ligne 7 On d´eclare une seconde cl´e de nœud n .2
Ligne 10 On d´eclare la cl´e de port p . Comme les cl´es de nœuds, les cl´es de port contiennent01
des informations comme le nœud d’appartenance. On se sert de l’adresse du pointeur
comme d’une cl´e unique.
Ligne 11 On d´eclare la cl´e de port p .11
Ligne 12 On d´eclare la cl´e de port p .12
Ligne 13 On d´eclare la cl´e de port p .21
Ligne 16 On d´eclare la cl´e de lien l . Comme les cl´es de nœuds et de ports, les cl´es de liens0111
sont des pointeurs qui contiennent des informations comme le d´ebut et la fin du lien sous
la forme de cl´e de port. L’adresse du lien sert de cl´e unique.
Ligne 17 On d´eclare la cl´e de lien l1221
Ligne 20 On cr´ee tout d’abord le nœud n . La m´ethode de graphe CreateNode fait appel a`1
l’op´erateur new qui cr´ee l’adresse unique de n dont on se sert comme cl´e. Cette cl´e sert1
`a atteindre une donn´ee de type r´eelle sous la forme d’une map entre l’adresse de n et la1
valeur r´eelle 1.0.
Ligne 21 On cr´ee la cl´e de nœud n et on associe a` cette cl´e la valeur 2.0.2
Ligne 23 On cr´ee le port libre p . Le port est dit libre car il n’appartient a` aucun nœud. A01
l’adresse de ce port on associe la valeur 0.1.
Ligne 24 On cr´ee le port p qui appartient au nœud n . On lui associe la valeur 1.1.11 1
Ligne 25 On cr´ee le port p qui appartient au nœud n . On lui associe la valeur 1.2.12 1
Ligne 26 On cr´ee le port p qui appartient au nœud n . On lui associe la valeur 2.1.21 2
Ligne 29 On cr´ee un port libre sans retenir la cl