Statistics
| Branch: | Revision:

root / src / sim / ctopology.cc @ fbe00e73

History | View | Annotate | Download (10.4 KB)

1
//=========================================================================
2
//  CTOPOLOGY.CC - part of
3
//
4
//                  OMNeT++/OMNEST
5
//           Discrete System Simulation in C++
6
//
7
//   Member functions of
8
//     cTopology : network topology to find shortest paths etc.
9
//
10
//  Author: Andras Varga
11
//
12
//=========================================================================
13

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

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

    
22
#include <stdio.h>
23
#include <string.h>
24
#include <stdarg.h>
25
#include <deque>
26
#include <algorithm>
27
#include <sstream>
28
#include "ctopology.h"
29
#include "cpar.h"
30
#include "globals.h"
31
#include "cexception.h"
32
#include "cproperty.h"
33
#include "patternmatcher.h"
34

    
35
#ifdef WITH_PARSIM
36
#include "ccommbuffer.h"
37
#endif
38

    
39
USING_NAMESPACE
40

    
41
Register_Class(cTopology);
42

    
43

    
44
cTopology::LinkIn *cTopology::Node::getLinkIn(int i)
45
{
46
    if (i<0 || i>=num_in_links)
47
        throw cRuntimeError("cTopology::Node::getLinkIn: invalid link index %d", i);
48
    return (cTopology::LinkIn *)in_links[i];
49
}
50

    
51
cTopology::LinkOut *cTopology::Node::getLinkOut(int i)
52
{
53
    if (i<0 || i>=num_out_links)
54
        throw cRuntimeError("cTopology::Node::getLinkOut: invalid index %d", i);
55
    return (cTopology::LinkOut *)(out_links+i);
56
}
57

    
58
//----
59

    
60
cTopology::cTopology(const char *name) : cOwnedObject(name)
61
{
62
    num_nodes = 0;
63
    nodev = NULL;
64
}
65

    
66
cTopology::cTopology(const cTopology& topo) : cOwnedObject()
67
{
68
    nodev = NULL;
69
    setName(topo.getName());
70
    cTopology::operator=(topo);
71
}
72

    
73
cTopology::~cTopology()
74
{
75
    clear();
76
}
77

    
78
std::string cTopology::info() const
79
{
80
    std::stringstream out;
81
    out << "n=" << num_nodes;
82
    return out.str();
83
}
84

    
85
void cTopology::parsimPack(cCommBuffer *buffer)
86
{
87
    throw cRuntimeError(this,"parsimPack() not implemented");
88
}
89

    
90
void cTopology::parsimUnpack(cCommBuffer *buffer)
91
{
92
    throw cRuntimeError(this,"parsimUnpack() not implemented");
93
}
94

    
95
cTopology& cTopology::operator=(const cTopology&)
96
{
97
    throw cRuntimeError(this,"operator= not implemented yet");
98
}
99

    
100
void cTopology::clear()
101
{
102
    for (int i=0; i<num_nodes; i++)
103
    {
104
        delete [] nodev[i].in_links;
105
        delete [] nodev[i].out_links;
106
    }
107
    delete [] nodev;
108

    
109
    num_nodes = 0;
110
    nodev = NULL;
111
}
112

    
113
//---
114

    
115
static bool selectByModulePath(cModule *mod, void *data)
116
{
117
    // actually, this is selectByModuleFullPathPattern()
118
    const std::vector<std::string>& v = *(const std::vector<std::string> *)data;
119
    std::string path = mod->getFullPath();
120
    for (int i=0; i<(int)v.size(); i++)
121
        if (PatternMatcher(v[i].c_str(), true, true, true).matches(path.c_str()))
122
            return true;
123
    return false;
124
}
125

    
126
static bool selectByNedTypeName(cModule *mod, void *data)
127
{
128
    const std::vector<std::string>& v = *(const std::vector<std::string> *)data;
129
    return std::find(v.begin(), v.end(), mod->getNedTypeName()) != v.end();
130
}
131

    
132
static bool selectByProperty(cModule *mod, void *data)
133
{
134
    struct ParamData {const char *name; const char *value;};
135
    ParamData *d = (ParamData *)data;
136
    cProperty *prop = mod->getProperties()->get(d->name);
137
    if (!prop)
138
        return false;
139
    const char *value = prop->getValue(cProperty::DEFAULTKEY, 0);
140
    if (d->value)
141
        return opp_strcmp(value, d->value)==0;
142
    else
143
        return opp_strcmp(value, "false")!=0;
144
}
145

    
146
static bool selectByParameter(cModule *mod, void *data)
147
{
148
    struct PropertyData{const char *name; const char *value;};
149
    PropertyData *d = (PropertyData *)data;
150
    return mod->hasPar(d->name) && (d->value==NULL || mod->par(d->name).str()==std::string(d->value));
151
}
152

    
153
//---
154

    
155
void cTopology::extractByModulePath(const std::vector<std::string>& fullPathPatterns)
156
{
157
    extractFromNetwork(selectByModulePath, (void *)&fullPathPatterns);
158
}
159

    
160
void cTopology::extractByNedTypeName(const std::vector<std::string>& nedTypeNames)
161
{
162
    extractFromNetwork(selectByNedTypeName, (void *)&nedTypeNames);
163
}
164

    
165
void cTopology::extractByProperty(const char *propertyName, const char *value)
166
{
167
    struct {const char *name; const char *value;} data = {propertyName, value};
168
    extractFromNetwork(selectByProperty, (void *)&data);
169
}
170

    
171
void cTopology::extractByParameter(const char *paramName, const char *paramValue)
172
{
173
    struct {const char *name; const char *value;} data = {paramName, paramValue};
174
    extractFromNetwork(selectByParameter, (void *)&data);
175
}
176

    
177
//---
178

    
179
static bool selectByPredicate(cModule *mod, void *data)
180
{
181
    cTopology::Predicate *predicate = (cTopology::Predicate *)data;
182
    return predicate->matches(mod);
183
}
184

    
185
void cTopology::extractFromNetwork(Predicate *predicate)
186
{
187
    extractFromNetwork(selectByPredicate, (void *)predicate);
188
}
189

    
190
void cTopology::extractFromNetwork(bool (*selfunc)(cModule *,void *), void *data)
191
{
192
    clear();
193

    
194
    Node *temp_nodev = new Node[simulation.getLastModuleId()];
195

    
196
    // Loop through all modules and find those which have the required
197
    // parameter with the (optionally) required value.
198
    int k=0;
199
    for (int mod_id=0; mod_id<=simulation.getLastModuleId(); mod_id++)
200
    {
201
        cModule *mod = simulation.getModule(mod_id);
202
        if (mod && selfunc(mod,data))
203
        {
204
            // ith module is OK, insert into nodev[]
205
            temp_nodev[k].module_id = mod_id;
206
            temp_nodev[k].wgt = 0;
207
            temp_nodev[k].enabl = true;
208

    
209
            // init auxiliary variables
210
            temp_nodev[k].known = 0;
211
            temp_nodev[k].dist = INFINITY;
212
            temp_nodev[k].out_path = NULL;
213

    
214
            // create in_links[] arrays (big enough...)
215
            temp_nodev[k].num_in_links = 0;
216
            temp_nodev[k].in_links = new cTopology::Link *[mod->gateCount()];
217

    
218
            k++;
219
        }
220
    }
221
    num_nodes = k;
222

    
223
    nodev = new Node[num_nodes];
224
    memcpy(nodev, temp_nodev, num_nodes*sizeof(Node));
225
    delete [] temp_nodev;
226

    
227
    // Discover out neighbors too.
228
    for (int k=0; k<num_nodes; k++)
229
    {
230
        // Loop through all its gates and find those which come
231
        // from or go to modules included in the topology.
232

    
233
        cModule *mod = simulation.getModule(nodev[k].module_id);
234
        cTopology::Link *temp_out_links = new cTopology::Link[mod->gateCount()];
235

    
236
        int n_out=0;
237
        for (cModule::GateIterator i(mod); !i.end(); i++)
238
        {
239
            cGate *gate = i();
240
            if (gate->getType()!=cGate::OUTPUT)
241
                continue;
242

    
243
            // follow path
244
            cGate *src_gate = gate;
245
            do {
246
                gate = gate->getNextGate();
247
            }
248
            while(gate && !selfunc(gate->getOwnerModule(),data));
249

    
250
            // if we arrived at a module in the topology, record it.
251
            if (gate)
252
            {
253
                temp_out_links[n_out].src_node = nodev+k;
254
                temp_out_links[n_out].src_gate = src_gate->getId();
255
                temp_out_links[n_out].dest_node = getNodeFor(gate->getOwnerModule());
256
                temp_out_links[n_out].dest_gate = gate->getId();
257
                temp_out_links[n_out].wgt = 1.0;
258
                temp_out_links[n_out].enabl = true;
259
                n_out++;
260
            }
261
        }
262
        nodev[k].num_out_links = n_out;
263

    
264
        nodev[k].out_links = new cTopology::Link[n_out];
265
        memcpy(nodev[k].out_links, temp_out_links, n_out*sizeof(cTopology::Link));
266
        delete [] temp_out_links;
267
    }
268

    
269
    // fill in_links[] arrays
270
    for (int k=0; k<num_nodes; k++)
271
    {
272
        for (int l=0; l<nodev[k].num_out_links; l++)
273
        {
274
            cTopology::Link *link = &nodev[k].out_links[l];
275
            link->dest_node->in_links[link->dest_node->num_in_links++] = link;
276
        }
277
    }
278
}
279

    
280
cTopology::Node *cTopology::getNode(int i)
281
{
282
    if (i<0 || i>=num_nodes)
283
        throw cRuntimeError(this,"invalid node index %d",i);
284
    return nodev+i;
285
}
286

    
287
cTopology::Node *cTopology::getNodeFor(cModule *mod)
288
{
289
    // binary search can be done because nodev[] is ordered
290

    
291
    int lo, up, index;
292
    for ( lo=0, up=num_nodes, index=(lo+up)/2;
293
          lo<index;
294
          index=(lo+up)/2 )
295
    {
296
        // cycle invariant: nodev[lo].mod_id <= mod->getId() < nodev[up].mod_id
297
        if (mod->getId() < nodev[index].module_id)
298
             up = index;
299
        else
300
             lo = index;
301
    }
302
    return (mod->getId() == nodev[index].module_id) ? nodev+index : NULL;
303
}
304

    
305
void cTopology::calculateUnweightedSingleShortestPathsTo(Node *_target)
306
{
307
    // multiple paths not supported :-(
308

    
309
    if (!_target)
310
        throw cRuntimeError(this,"..ShortestPathTo(): target node is NULL");
311
    target = _target;
312

    
313
    for (int i=0; i<num_nodes; i++)
314
    {
315
       nodev[i].known = false;   // not really needed for unweighted
316
       nodev[i].dist = INFINITY;
317
       nodev[i].out_path = NULL;
318
    }
319
    target->dist = 0;
320

    
321
    std::deque<Node*> q;
322

    
323
    q.push_back(target);
324

    
325
    while (!q.empty())
326
    {
327
       Node *v = q.front();
328
       q.pop_front();
329

    
330
       // for each w adjacent to v...
331
       for (int i=0; i<v->num_in_links; i++)
332
       {
333
           if (!(v->in_links[i]->enabl)) continue;
334

    
335
           Node *w = v->in_links[i]->src_node;
336
           if (!w->enabl) continue;
337

    
338
           if (w->dist == INFINITY)
339
           {
340
               w->dist = v->dist + 1;
341
               w->out_path = v->in_links[i];
342
               q.push_back(w);
343
           }
344
       }
345
    }
346
}
347

    
348

    
349
/* to be adapted:
350
void cTopology::weightedSingleShortestPathsTo(Node *_target)
351
{
352
    if (!_target)
353
        throw cRuntimeError(this,"..ShortestPathTo(): target node is NULL");
354

355
    target = _target;
356

357
    void Dijstra( Table t)
358

359
    Vertex v,w;
360

361
    for (;;)
362
    {
363
       v = smallest unknown distance vertex; // priority queue-val!
364
                                             // az unknown-ok vannak benne
365
                                             // priority q = pl. binary heap
366
       if (v == NO_VERTEX) break;
367

368
       t[v].known = true;                    // delete_min()
369
       for (each w adjacent to v)
370
       {
371
           if (!t[v].known  &&  t[v].dist+C(w,v) < t[w].dist)
372
           {
373
               decrease( t[w].dist  to  t[v].dist+C(w,v); // decrease_key!
374
                  // belekavar a prio q-ba!
375
                  // megoldas lehet, hogy nem vesszuk ki a sorbol,
376
                  // hanem meg egyszer betesszuk
377
                  // ekkor fent a delete_min()-ne'l kell vadaszni unknown-okra!
378
               t[w].path = v;
379
           }
380
       }
381
    }
382
}
383
*/