Project

General

Profile

Statistics
| Branch: | Revision:

root / include / ctopology.h @ c87b95b0

History | View | Annotate | Download (15.5 KB)

1
//==========================================================================
2
//  CTOPOLOGY.H - part of
3
//                     OMNeT++/OMNEST
4
//            Discrete System Simulation in C++
5
//
6
//
7
//  Declaration of the following classes:
8
//     cTopology : network topology to find shortest paths etc.
9
//
10
//==========================================================================
11

    
12
/*--------------------------------------------------------------*
13
  Copyright (C) 1992-2008 Andras Varga
14
  Copyright (C) 2006-2008 OpenSim Ltd.
15

16
  This file is distributed WITHOUT ANY WARRANTY. See the file
17
  `license' for details on this and other legal matters.
18
*--------------------------------------------------------------*/
19

    
20
#ifndef __CTOPOLOGY_H
21
#define __CTOPOLOGY_H
22

    
23
#include <string>
24
#include <vector>
25
#include "cownedobject.h"
26
#include "csimulation.h"
27
#include "cmodule.h"
28
#include "cgate.h"
29

    
30
NAMESPACE_BEGIN
31

    
32
class cPar;
33

    
34
// not all compilers define INFINITY (gcc does)
35
#ifndef INFINITY
36
#define INFINITY HUGE_VAL
37
#endif
38

    
39
/**
40
 * Routing support. The cTopology class was designed primarily to support
41
 * routing in telecommunication or multiprocessor networks.
42
 *
43
 * A cTopology object stores an abstract representation of the network
44
 * in graph form:
45
 * <UL>
46
 *   <LI> each cTopology node corresponds to a module (simple or compound), and
47
 *   <LI> each cTopology edge corresponds to a link or series of connecting links.
48
 * </UL>
49
 *
50
 * You can specify which modules (either simple or compound) you want to
51
 * include in the graph. The graph will include all connections among the
52
 * selected modules. In the graph, all nodes are at the same level, there is
53
 * no submodule nesting. Connections which span across compound module
54
 * boundaries are also represented as one graph edge. Graph edges are directed,
55
 * just as module gates are.
56
 *
57
 * @ingroup SimSupport
58
 * @see cTopology::Node, cTopology::Link, cTopology::LinkIn, cTopology::LinkOut
59
 */
60
class SIM_API cTopology : public cOwnedObject
61
{
62
  public:
63
    class Link;
64
    class LinkIn;
65
    class LinkOut;
66

    
67
    /**
68
     * Supporting class for cTopology, represents a node in the graph.
69
     */
70
    class SIM_API Node
71
    {
72
        friend class cTopology;
73

    
74
      private:
75
        int module_id;
76
        double wgt;
77
        bool enabl;
78

    
79
        int num_in_links;
80
        Link **in_links;
81
        int num_out_links;
82
        Link *out_links;
83

    
84
        // variables used by the shortest-path algorithms
85
        bool known;
86
        double dist;
87
        Link *out_path;
88

    
89
      public:
90
        /** @name Node attributes: weight, enabled state, correspondence to modules. */
91
        //@{
92

    
93
        /**
94
         * Returns the ID of the network module to which this node corresponds.
95
         */
96
        int getModuleId() const  {return module_id;}
97

    
98
        /**
99
         * Returns the pointer to the network module to which this node corresponds.
100
         */
101
        cModule *getModule() const  {return simulation.getModule(module_id);}
102

    
103
        /**
104
         * Returns the weight of this node. Weight is used with the
105
         * weighted shortest path finder methods of cTopology.
106
         */
107
        double getWeight() const  {return wgt;}
108

    
109
        /**
110
         * Sets the weight of this node. Weight is used with the
111
         * weighted shortest path finder methods of cTopology.
112
         */
113
        void setWeight(double d)  {wgt=d;}
114

    
115
        /**
116
         * Returns true of this node is enabled. This has significance
117
         * with the shortest path finder methods of cTopology.
118
         */
119
        bool isEnabled() const  {return enabl;}
120

    
121
        /**
122
         * Enable this node. This has significance with the shortest path
123
         * finder methods of cTopology.
124
         */
125
        void enable()  {enabl=true;}
126

    
127
        /**
128
         * Disable this node. This has significance with the shortest path
129
         * finder methods of cTopology.
130
         */
131
        void disable()  {enabl=false;}
132
        //@}
133

    
134
        /** @name Node connectivity. */
135
        //@{
136

    
137
        /**
138
         * Returns the number of incoming links to this graph node.
139
         */
140
        int getNumInLinks() const  {return num_in_links;}
141

    
142
        /**
143
         * Returns ith incoming link of graph node.
144
         */
145
        LinkIn *getLinkIn(int i);
146

    
147
        /**
148
         * Returns the number of outgoing links from this graph node.
149
         */
150
        int getNumOutLinks() const  {return num_out_links;}
151

    
152
        /**
153
         * Returns ith outgoing link of graph node.
154
         */
155
        LinkOut *getLinkOut(int i);
156
        //@}
157

    
158
        /** @name Result of shortest path extraction. */
159
        //@{
160

    
161
        /**
162
         * Returns the distance of this node to the target node.
163
         */
164
        double getDistanceToTarget() const  {return dist;}
165

    
166
        /**
167
         * Returns the number of shortest paths towards the target node.
168
         * (There may be several paths with the same length.)
169
         */
170
        int getNumPaths() const  {return out_path?1:0;}
171

    
172
        /**
173
         * Returns the next link in the ith shortest paths towards the
174
         * target node. (There may be several paths with the same
175
         * length.)
176
         */
177
        LinkOut *getPath(int) const  {return (LinkOut *)out_path;}
178
        //@}
179
    };
180

    
181

    
182
    /**
183
     * Supporting class for cTopology, represents a link in the graph.
184
     */
185
    class SIM_API Link
186
    {
187
        friend class cTopology;
188

    
189
      protected:
190
        Node *src_node;
191
        int src_gate;
192
        Node *dest_node;
193
        int dest_gate;
194
        double wgt;
195
        bool enabl;
196

    
197
      public:
198
        /**
199
         * Returns the weight of this link. Weight is used with the
200
         * weighted shortest path finder methods of cTopology.
201
         */
202
        double getWeight() const  {return wgt;}
203

    
204
        /**
205
         * Sets the weight of this link. Weight is used with the
206
         * weighted shortest path finder methods of cTopology.
207
         */
208
        void setWeight(double d)  {wgt=d;}
209

    
210
        /**
211
         * Returns true of this link is enabled. This has significance
212
         * with the shortest path finder methods of cTopology.
213
         */
214
        bool isEnabled() const  {return enabl;}
215

    
216
        /**
217
         * Enables this link. This has significance with the shortest path
218
         * finder methods of cTopology.
219
         */
220
        void enable()  {enabl=true;}
221

    
222
        /**
223
         * Disables this link. This has significance with the shortest path
224
         * finder methods of cTopology.
225
         */
226
        void disable()  {enabl=false;}
227
    };
228

    
229

    
230
    /**
231
     * Supporting class for cTopology.
232
     *
233
     * While navigating the graph stored in a cTopology, Node's methods return
234
     * LinkIn and LinkOut objects, which are 'aliases' to Link objects.
235
     * LinkIn and LinkOut provide convenience functions that return the
236
     * 'local' and 'remote' end of the connection when traversing the topology.
237
     */
238
    class SIM_API LinkIn : public Link
239
    {
240
      public:
241
        /**
242
         * Returns the node at the remote end of this connection.
243
         *
244
         * Note: There is no corresponding localNode() method: the local node of
245
         * this connection is the Node object whose method returned
246
         * this LinkIn object.
247
         */
248
        Node *getRemoteNode() const  {return src_node;}
249

    
250
        /**
251
         * Returns the gate ID at the remote end of this connection.
252
         */
253
        int getRemoteGateId() const  {return src_gate;}
254

    
255
        /**
256
         * Returns the gate ID at the local end of this connection.
257
         */
258
        int getLocalGateId() const  {return dest_gate;}
259

    
260
        /**
261
         * Returns the gate at the remote end of this connection.
262
         */
263
        cGate *getRemoteGate() const  {return src_node->getModule()->gate(src_gate);}
264

    
265
        /**
266
         * Returns the gate at the local end of this connection.
267
         */
268
        cGate *getLocalGate() const  {return dest_node->getModule()->gate(dest_gate);}
269
    };
270

    
271

    
272
    /**
273
     * Supporting class for cTopology.
274
     *
275
     * While navigating the graph stored in a cTopology, Node's methods return
276
     * LinkIn and LinkOut objects, which are 'aliases' to Link objects.
277
     * LinkIn and LinkOut provide convenience functions that return the
278
     * 'local' and 'remote' end of the connection when traversing the topology.
279
     */
280
    class SIM_API LinkOut : public Link
281
    {
282
      public:
283
        /**
284
         * Returns the node at the remote end of this connection.
285
         *
286
         * Note: There is no corresponding localNode() method: the local node of
287
         * this connection is the Node object whose method returned
288
         * this LinkIn object.
289
         */
290
        Node *getRemoteNode() const  {return dest_node;}
291

    
292
        /**
293
         * Returns the gate ID at the remote end of this connection.
294
         */
295
        int getRemoteGateId() const  {return dest_gate;}
296

    
297
        /**
298
         * Returns the gate ID at the local end of this connection.
299
         */
300
        int getLocalGateId() const  {return src_gate;}
301

    
302
        /**
303
         * Returns the gate at the remote end of this connection.
304
         */
305
        cGate *getRemoteGate() const  {return dest_node->getModule()->gate(dest_gate);}
306

    
307
        /**
308
         * Returns the gate at the local end of this connection.
309
         */
310
        cGate *getLocalGate() const  {return src_node->getModule()->gate(src_gate);}
311
    };
312

    
313
    /**
314
     * Base class for selector objects used in extract...() methods of cTopology.
315
     * Redefine the matches() method to return whether the given module
316
     * should be included in the extracted topology or not.
317
     */
318
    class SIM_API Predicate
319
    {
320
      public:
321
        virtual ~Predicate() {}
322
        virtual bool matches(cModule *module) = 0;
323
    };
324

    
325
  protected:
326
    int num_nodes;
327
    Node *nodev;
328
    Node *target;
329

    
330
  public:
331
    /** @name Constructors, destructor, assignment */
332
    //@{
333

    
334
    /**
335
     * Constructor.
336
     */
337
    explicit cTopology(const char *name=NULL);
338

    
339
    /**
340
     * Copy constructor.
341
     */
342
    cTopology(const cTopology& topo);
343

    
344
    /**
345
     * Destructor.
346
     */
347
    virtual ~cTopology();
348

    
349
    /**
350
     * Assignment operator. The name member is not copied; see cNamedObject's operator=() for more details.
351
     */
352
    cTopology& operator=(const cTopology& topo);
353
    //@}
354

    
355
    /** @name Redefined cObject member functions. */
356
    //@{
357

    
358
    /**
359
     * Creates and returns an exact copy of this object.
360
     * See cObject for more details.
361
     */
362
    virtual cTopology *dup() const  {return new cTopology(*this);}
363

    
364
    /**
365
     * Produces a one-line description of the object's contents.
366
     * See cObject for more details.
367
     */
368
    virtual std::string info() const;
369

    
370
    /**
371
     * Serializes the object into an MPI send buffer.
372
     * Used by the simulation kernel for parallel execution.
373
     * See cObject for more details.
374
     */
375
    virtual void parsimPack(cCommBuffer *buffer);
376

    
377
    /**
378
     * Deserializes the object from an MPI receive buffer
379
     * Used by the simulation kernel for parallel execution.
380
     * See cObject for more details.
381
     */
382
    virtual void parsimUnpack(cCommBuffer *buffer);
383
    //@}
384

    
385
    /** @name Extracting the topology from a network.
386
     *
387
     * extract...() functions build topology from the model.
388
     * User can select which modules to include. All connections
389
     * between those modules will be in the topology. Connections can
390
     * cross compound module boundaries.
391
     */
392
    //@{
393

    
394
    /**
395
     * Extracts model topology by a user-defined criteria. Includes into the graph
396
     * modules for which the passed selfunc() returns nonzero. The userdata
397
     * parameter may take any value you like, and it is passed back to selfunc()
398
     * in its second argument.
399
     */
400
    void extractFromNetwork(bool (*selfunc)(cModule *,void *), void *userdata=NULL);
401

    
402
    /**
403
     * The type safe, object-oriented equivalent of extractFromNetwork(selfunc, userdata).
404
     */
405
    void extractFromNetwork(Predicate *predicate);
406

    
407
    /**
408
     * Extracts model topology by module full path. All modules whole getFullPath()
409
     * matches one of the patterns in given string vector will get included.
410
     * The patterns may contain wilcards in the same syntax as in ini files.
411
     *
412
     * An example:
413
     *
414
     * <tt>topo.extractByModulePath(cStringTokenizer("**.host[*] **.router*").asVector());</tt>
415
     */
416
    void extractByModulePath(const std::vector<std::string>& fullPathPatterns);
417

    
418
    /**
419
     * Extracts model topology by the fully qualified NED type name of the
420
     * modules. All modules whose getNedTypeName() is listed in the given string
421
     * vector will get included.
422
     *
423
     * Note: If you have all class names as a single, space-separated string,
424
     * you can use cStringTokenizer to turn it into a string vector:
425
     *
426
     * <tt>topo.extractByNedTypeName(cStringTokenizer("some.package.Host other.package.Router").asVector());</tt>
427
     */
428
    void extractByNedTypeName(const std::vector<std::string>& nedTypeNames);
429

    
430
    /**
431
     * Extracts model topology by a module property. All modules get included
432
     * that have a property with the given name and the given value
433
     * (more precisely, the first value of its default key being the specified
434
     * value). If value is NULL, the property's value may be anything except
435
     * "false" (i.e. the first value of the default key may not be "false").
436
     *
437
     * For example, <tt>topo.extractByProperty("node");</tt> would extract
438
     * all modules that contain the <tt>@node</tt> property, like the following
439
     * one:
440
     *
441
     * <pre>
442
     * module X {
443
     *     @node;
444
     * }
445
     * </pre>
446
     *
447
     */
448
    void extractByProperty(const char *propertyName, const char *value=NULL);
449

    
450
    /**
451
     * Extracts model topology by a module parameter. All modules get included
452
     * that have a parameter with the given name, and the parameter's str()
453
     * method returns the paramValue string. If paramValue is NULL, only the
454
     * parameter's existence is checked but not its value.
455
     */
456
    void extractByParameter(const char *paramName, const char *paramValue=NULL);
457

    
458
    /**
459
     * Deletes the topology stored in the object.
460
     */
461
    void clear();
462
    //@}
463

    
464
    /** @name Functions to examine topology by hand.
465
     *
466
     * Users also need to rely on Node and Link member functions
467
     * to explore the graph stored in the object.
468
     */
469
    //@{
470

    
471
    /**
472
     * Returns the number of nodes in the graph.
473
     */
474
    int getNumNodes() const  {return num_nodes;}
475

    
476
    /**
477
     * Returns pointer to the ith node in the graph. Node's methods
478
     * can be used to further examine the node's connectivity, etc.
479
     */
480
    Node *getNode(int i);
481

    
482
    /**
483
     * Returns the graph node which corresponds to the given module in the
484
     * network. If no graph node corresponds to the module, the method returns
485
     * NULL. This method assumes that the topology corresponds to the
486
     * network, that is, it was probably created with one of the
487
     * extract...() functions.
488
     */
489
    Node *getNodeFor(cModule *mod);
490
    //@}
491

    
492
    /** @name Algorithms to find shortest paths. */
493
    /*
494
     * To be implemented:
495
     *    -  void unweightedMultiShortestPathsTo(Node *target);
496
     *    -  void weightedSingleShortestPathsTo(Node *target);
497
     *    -  void weightedMultiShortestPathsTo(Node *target);
498
     */
499
    //@{
500

    
501
    /**
502
     * Apply the Dijkstra algorithm to find all shortest paths to the given
503
     * graph node. The paths found can be extracted via Node's methods.
504
     */
505
    void calculateUnweightedSingleShortestPathsTo(Node *target);
506

    
507
    /**
508
     * Returns the node that was passed to the most recently called
509
     * shortest path finding function.
510
     */
511
    Node *getTargetNode() const {return target;}
512
    //@}
513
};
514

    
515
NAMESPACE_END
516

    
517

    
518
#endif