Mailing list archive (omnetpp-l at omnetpp.org)
[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[omnetpp] Fwd: Weighted Single Shortest Path in OMNET
---------- Forwarded message ----------
From: Pasquale Gurzi' <pgurzi at xxx>
Date: 2008/6/3
Subject: Re: Weighted Single Shortest Path in OMNET
To: Alper Toku <alpertoku at xxx>
Hi Alper.
I have implemented only the weightedSingleShortestPathsTo function by
modifying the cTopo.cc and cTopo.h files of Omnetpp.
To fix the problem I used a weight on the channel instead of the link.
To use my function you have to add a parameter called "weight" to the any
channel and than the weightedSingleShortestPathsTo() function will extract
the weight of the link from this parameter instead to use setWeight() and
getWeight() function.
cChannel *chan = yourChannel
cPar &weight = chan->addPar("weight");
weight = yourWeight;
In attachment you can find the two files.
To use this you have to copy cTopo.cc in omnetpp/src/sim and cTopo.h in
omnetpp/include.
than you have to recompile omnetpp.
If you have some comments please let me know
2008/6/1 Alper Toku <alpertoku at xxx>:
>
>
> Hi Pasquale,
>
>
>
> I am studying for my masters degree at Middle East Technical University in
> Ankara, Turkey. In OMNET manual in ctopology class, it is mentioned that in
> the future shortest path algorithms like "unweightedMultiShortestPathsTo",
> "weightedSingleShortestPathsTo" and "weightedMultiShortestPathsTo" will be
> implemented. I tried to develop these algorithms on my own but I
> couldn't succeed it.
>
> I saw your post in OMNET++ Community Site. In 4 Jan 2008, you mentioned
> about a similar problem like mine. I wondered if anyone helped you about
> this problem or have you found your own solution?
> I hope you can help me about this issue...
> Thank you...
>
>
>
--
Pasquale Gurzi'
--
Pasquale Gurzi'
//=========================================================================
// CTOPO.CC - part of
//
// OMNeT++/OMNEST
// Discrete System Simulation in C++
//
// Member functions of
// cTopology : network topology to find shortest paths etc.
//
// Author: Andras Varga
//
//=========================================================================
/*--------------------------------------------------------------*
Copyright (C) 1992-2005 Andras Varga
This file is distributed WITHOUT ANY WARRANTY. See the file
`license' for details on this and other legal matters.
*--------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdarg.h>
#include "macros.h"
#include "cmodule.h"
#include "cgate.h"
#include "cpar.h"
#include "cllist.h"
#include "ctopo.h"
#include "cexception.h"
#ifdef WITH_PARSIM
#include "ccommbuffer.h"
#endif
//=== Registration
Register_Class(cTopology);
//==========================================================================
cTopology::LinkIn *cTopology::Node::in(int i)
{
if (i<0 || i>=num_in_links)
throw new cRuntimeError("cTopology::Node: invalid in() index %d",i);
return (cTopology::LinkIn *)in_links[i];
}
cTopology::LinkOut *cTopology::Node::out(int i)
{
if (i<0 || i>=num_out_links)
throw new cRuntimeError("cTopology::Node: invalid out() index %d",i);
return (cTopology::LinkOut *)(out_links+i);
}
//==========================================================================
//=== cTopology - member functions
cTopology::cTopology(const char *name) : cObject(name)
{
num_nodes = 0;
nodev = NULL;
}
cTopology::cTopology(const cTopology& topo) : cObject()
{
nodev = NULL;
setName(topo.name());
cTopology::operator=(topo);
}
cTopology::~cTopology()
{
clear();
}
std::string cTopology::info() const
{
std::stringstream out;
out << "n=" << num_nodes;
return out.str();
}
void cTopology::netPack(cCommBuffer *buffer)
{
throw new cRuntimeError(this,"netPack() not implemented");
}
void cTopology::netUnpack(cCommBuffer *buffer)
{
throw new cRuntimeError(this,"netUnpack() not implemented");
}
cTopology& cTopology::operator=(const cTopology&)
{
throw new cRuntimeError(this,"operator= not implemented yet");
}
void cTopology::clear()
{
for (int i=0; i<num_nodes; i++)
{
delete [] nodev[i].in_links;
delete [] nodev[i].out_links;
}
delete [] nodev;
num_nodes = 0;
nodev = NULL;
}
static int selectByParameter(cModule *mod, void *data)
{
struct sTmp {const char *parname; cPar *value;};
sTmp *d = (sTmp *)data;
if (!mod || mod->findPar(d->parname)<0) return 0;
if (d->value && !mod->par(d->parname).equalsTo(d->value)) return 0;
return 1;
}
void cTopology::extractByParameter(const char *parname, cPar *value)
{
struct {const char *p; cPar *v;} data = {parname, value};
extractFromNetwork( selectByParameter, (void *)&data );
}
static int selectByModuleType(cModule *mod, void *data)
{
for (const char **d = (const char **)data; *d; d++)
if (strcmp(mod->className(),*d)==0)
return 1;
return 0;
}
void cTopology::extractByModuleType(const char *type1,...)
{
// parse arg list into null-terminated char *[] array
int n = 0;
va_list va;
va_start(va,type1);
while (va_arg(va, char *)!=NULL) n++;
va_end(va);
char **types = new char *[n+2];
int k=0;
types[k++] = const_cast<char *>(type1);
va_start(va,type1);
while ((types[k++]=va_arg(va, char *))!=NULL);
va_end(va);
extractFromNetwork(selectByModuleType, (void *)types);
delete [] types;
}
void cTopology::extractByModuleType(const char **types)
{
extractFromNetwork(selectByModuleType, (void *)types);
}
void cTopology::extractByModuleType(const std::vector<std::string> v)
{
const char **types = new const char *[v.size()+1];
for (unsigned int i=0; i<v.size(); i++)
types[i] = v[i].c_str();
types[v.size()] = NULL;
extractFromNetwork(selectByModuleType, (void *)types);
delete [] types;
}
void cTopology::extractFromNetwork(int (*selfunc)(cModule *,void *), void *data)
{
clear();
int mod_id, gate_id;
Node *temp_nodev = new Node[simulation.lastModuleId()];
// Loop through all modules and find those which have the required
// parameter with the (optionally) required value.
int k=0;
for (mod_id=0; mod_id<=simulation.lastModuleId(); mod_id++)
{
cModule *mod = simulation.module(mod_id);
if (mod && selfunc(mod,data))
{
// ith module is OK, insert into nodev[]
temp_nodev[k].module_id = mod_id;
temp_nodev[k].wgt = 0;
temp_nodev[k].enabl = true;
// init auxiliary variables
temp_nodev[k].known = 0;
temp_nodev[k].dist = INFINITY;
temp_nodev[k].out_path = NULL;
// create in_links[] arrays (big enough...)
temp_nodev[k].num_in_links = 0;
temp_nodev[k].in_links = new cTopology::Link *[mod->gates()];
k++;
}
}
num_nodes = k;
nodev = new Node[num_nodes];
memcpy(nodev,temp_nodev,num_nodes*sizeof(Node));
delete [] temp_nodev;
// Discover out neighbors too.
for (k=0; k<num_nodes; k++)
{
// Loop through all its gates and find those which come
// from or go to modules included in the topology.
cModule *mod = simulation.module(nodev[k].module_id);
cTopology::Link *temp_out_links = new cTopology::Link[mod->gates()];
int n_out=0;
for (gate_id=0; gate_id<mod->gates(); gate_id++)
{
cGate *gate = mod->gate(gate_id);
if (!gate || gate->type()!='O') continue;
// follow path
do {
gate = gate->toGate();
}
while(gate && !selfunc(gate->ownerModule(),data));
// if we arrived in a module in the topology, record it.
if (gate)
{
/////////////////////////////NEW, for the weightedShortestPath.//////////////////////////////////////////////////////////
//the Link has the same waight of the channel
double weight;
cGate *g = mod->gate(gate_id);
if(g->channel()->hasPar("weight"))
weight = g->channel()->par("weight");
else
weight = 1.0;
/////////////////////////////////////////////////////////////////////////////////////////////////////////
temp_out_links[n_out].src_node = nodev+k;
temp_out_links[n_out].src_gate = gate_id;
temp_out_links[n_out].dest_node = nodeFor(gate->ownerModule());
temp_out_links[n_out].dest_gate = gate->id();
temp_out_links[n_out].wgt = weight;
temp_out_links[n_out].enabl = true;
n_out++;
}
}
nodev[k].num_out_links = n_out;
nodev[k].out_links = new cTopology::Link[n_out];
memcpy(nodev[k].out_links,temp_out_links,n_out*sizeof(cTopology::Link));
delete [] temp_out_links;
}
// fill in_links[] arrays
for (k=0; k<num_nodes; k++)
{
for (int l=0; l<nodev[k].num_out_links; l++)
{
cTopology::Link *link = &nodev[k].out_links[l];
link->dest_node->in_links[link->dest_node->num_in_links++] = link;
}
}
}
cTopology::Node *cTopology::node(int i)
{
if (i<0 || i>=num_nodes)
throw new cRuntimeError(this,"invalid node index %d",i);
return nodev+i;
}
cTopology::Node *cTopology::nodeFor(cModule *mod)
{
// binary search can be done because nodev[] is ordered
int lo, up, index;
for ( lo=0, up=num_nodes, index=(lo+up)/2;
lo<index;
index=(lo+up)/2 )
{
// cycle invariant: nodev[lo].mod_id <= mod->id() < nodev[up].mod_id
if (mod->id() < nodev[index].module_id)
up = index;
else
lo = index;
}
return (mod->id() == nodev[index].module_id) ? nodev+index : NULL;
}
void cTopology::unweightedSingleShortestPathsTo(Node *_target)
{
// multiple paths not supported :-(
if (!_target)
throw new cRuntimeError(this,"..ShortestPathTo(): target node is NULL");
target = _target;
for (int i=0; i<num_nodes; i++)
{
nodev[i].known = false; // not really needed for unweighted
nodev[i].dist = INFINITY;
nodev[i].out_path = NULL;
}
target->dist = 0;
cLinkedList q;
q.insert( target );
while (!q.empty())
{
Node *v = (Node *) q.pop();
// for each w adjacent to v...
for (int i=0; i<v->num_in_links; i++)
{
if (!(v->in_links[i]->enabl)) continue;
Node *w = v->in_links[i]->src_node;
if (!(w->enabl)) continue;
if (w->dist == INFINITY)
{
w->dist = v->dist + 1;
w->out_path = v->in_links[i];
q.insert( w );
}
}
}
}
void cTopology::weightedSingleShortestPathsTo(Node *_target)
{
// arranged with weigths on the channels instead of the link :-)
// multiple paths not supported :-(
if (!_target)
throw new cRuntimeError(this,"..ShortestPathTo(): target node is NULL");
target = _target;
for (int i=0; i<num_nodes; i++)
{
nodev[i].known = false; // not really needed for unweighted
nodev[i].dist = INFINITY;
nodev[i].out_path = NULL;
}
target->dist = 0;
cLinkedList q;
q.insert( target );
while (!q.empty())
{
Node *v = (Node *) q.pop();
// for each w adjacent to v...
for (int i=0; i<v->num_in_links; i++)
{
if (!(v->in_links[i]->enabl)) continue;
Node *w = v->in_links[i]->src_node;
if (!(w->enabl)) continue;
if (w->dist == INFINITY || w->dist > v->dist + v->in_links[i]->wgt)
{
w->dist = v->dist + v->in_links[i]->wgt; // That is the difference
w->out_path = v->in_links[i];
q.insert( w );
}
}
}
}
//==========================================================================
// CTOPO.H - part of
// OMNeT++/OMNEST
// Discrete System Simulation in C++
//
//
// Declaration of the following classes:
// cTopology : network topology to find shortest paths etc.
//
//==========================================================================
/*--------------------------------------------------------------*
Copyright (C) 1992-2005 Andras Varga
This file is distributed WITHOUT ANY WARRANTY. See the file
`license' for details on this and other legal matters.
*--------------------------------------------------------------*/
#ifndef __CTOPO_H
#define __CTOPO_H
#ifdef _MSC_VER
// disable "identifier was truncated to '255' characters in the debug information" warnings
#pragma warning(disable:4786)
#endif
#include <string>
#include <vector>
#include "cobject.h"
#include "cchannel.h"
class cPar;
#ifndef INFINITY
#define INFINITY HUGE_VAL
#endif
/**
* Routing support. The cTopology class was designed primarily to support
* routing in telecommunication or multiprocessor networks.
*
* A cTopology object stores an abstract representation of the network
* in graph form:
* <UL>
* <LI> each cTopology node corresponds to a module (simple or compound), and
* <LI> each cTopology edge corresponds to a link or series of connecting links.
* </UL>
*
* You can specify which modules (either simple or compound) you want to
* include in the graph. The graph will include all connections among the
* selected modules. In the graph, all nodes are at the same level, there's
* no submodule nesting. Connections which span across compound module
* boundaries are also represented as one graph edge. Graph edges are directed,
* just as module gates are.
*
* @ingroup SimSupport
* @see cTopology::Node, cTopology::Link, cTopology::LinkIn, cTopology::LinkOut
*/
class SIM_API cTopology : public cObject
{
public:
class Link;
class LinkIn;
class LinkOut;
/**
* Supporting class for cTopology, represents a node in the graph.
*/
class SIM_API Node
{
friend class cTopology;
private:
int module_id;
double wgt;
bool enabl;
int num_in_links;
Link **in_links;
int num_out_links;
Link *out_links;
// variables used by the shortest-path algorithms
bool known;
double dist;
Link *out_path;
public:
/** @name Node attributes: weight, enabled state, correspondence to modules. */
//@{
/**
* Returns the ID of the network module to which this node corresponds.
*/
int moduleId() const {return module_id;}
/**
* Returns the pointer to the network module to which this node corresponds.
*/
cModule *module() const {return &simulation[module_id];}
/**
* Returns the weight of this node. Weight is used with the
* weighted shortest path finder methods of cTopology.
*/
double weight() const {return wgt;}
/**
* Sets the weight of this node. Weight is used with the
* weighted shortest path finder methods of cTopology.
*/
void setWeight(double d) {wgt=d;}
/**
* Returns true of this node is enabled. This has significance
* with the shortest path finder methods of cTopology.
*/
bool enabled() const {return enabl;}
/**
* Enable this node. This has significance with the shortest path
* finder methods of cTopology.
*/
void enable() {enabl=true;}
/**
* Disable this node. This has significance with the shortest path
* finder methods of cTopology.
*/
void disable() {enabl=false;}
//@}
/** @name Node connectivity. */
//@{
/**
* Returns the number of incoming links to this graph node.
*/
int inLinks() const {return num_in_links;}
/**
* Returns ith incoming link of graph node.
*/
LinkIn *in(int i);
/**
* Returns the number of outgoing links from this graph node.
*/
int outLinks() const {return num_out_links;}
/**
* Returns ith outgoing link of graph node.
*/
LinkOut *out(int i);
//@}
/** @name Result of shortest path extraction. */
//@{
/**
* Returns the distance of this node to the target node.
*/
double distanceToTarget() const {return dist;}
/**
* Returns the number of shortest paths towards the target node.
* (There might be several paths with the same lengths.)
*/
int paths() const {return out_path?1:0;}
/**
* Returns the next link in the ith shortest paths towards the
* target node. (There might be several paths with the same
* lengths.)
*/
LinkOut *path(int) const {return (LinkOut *)out_path;}
//@}
};
/**
* Supporting class for cTopology, represents a link in the graph.
*/
class SIM_API Link
{
friend class cTopology;
protected:
Node *src_node;
int src_gate;
Node *dest_node;
int dest_gate;
double wgt;
bool enabl;
public:
/**
* Returns the weight of this link. Weight is used with the
* weighted shortest path finder methods of cTopology.
*/
double weight() const {return wgt;}
/**
* Sets the weight of this link. Weight is used with the
* weighted shortest path finder methods of cTopology.
*/
void setWeight(double d) {wgt=d;}
/**
* Returns true of this link is enabled. This has significance
* with the shortest path finder methods of cTopology.
*/
bool enabled() const {return enabl;}
/**
* Enables this link. This has significance with the shortest path
* finder methods of cTopology.
*/
void enable() {enabl=true;}
/**
* Disables this link. This has significance with the shortest path
* finder methods of cTopology.
*/
void disable() {enabl=false;}
};
/**
* Supporting class for cTopology.
*
* While navigating the graph stored in a cTopology, Node's methods return
* LinkIn and LinkOut objects, which are 'aliases' to Link objects.
* LinkIn and LinkOut provide convenience functions that return the
* 'local' and 'remote' end of the connection when traversing the topology.
*/
class SIM_API LinkIn : public Link
{
public:
/**
* Returns the node at the remote end of this connection.
*
* Note: There's no corresponding localNode() method: the local node of
* this connection is the Node object whose method returned
* this LinkIn object.
*/
Node *remoteNode() const {return src_node;}
/**
* Returns the gate ID at the remote end of this connection.
*/
int remoteGateId() const {return src_gate;}
/**
* Returns the gate ID at the local end of this connection.
*/
int localGateId() const {return dest_gate;}
/**
* Returns the gate at the remote end of this connection.
*/
cGate *remoteGate() const {return src_node->module()->gate(src_gate);}
/**
* Returns the gate at the local end of this connection.
*/
cGate *localGate() const {return dest_node->module()->gate(dest_gate);}
};
/**
* Supporting class for cTopology.
*
* While navigating the graph stored in a cTopology, Node's methods return
* LinkIn and LinkOut objects, which are 'aliases' to Link objects.
* LinkIn and LinkOut provide convenience functions that return the
* 'local' and 'remote' end of the connection when traversing the topology.
*/
class SIM_API LinkOut : public Link
{
public:
/**
* Returns the node at the remote end of this connection.
*
* Note: There's no corresponding localNode() method: the local node of
* this connection is the Node object whose method returned
* this LinkIn object.
*/
Node *remoteNode() const {return dest_node;}
/**
* Returns the gate ID at the remote end of this connection.
*/
int remoteGateId() const {return dest_gate;}
/**
* Returns the gate ID at the local end of this connection.
*/
int localGateId() const {return src_gate;}
/**
* Returns the gate at the remote end of this connection.
*/
cGate *remoteGate() const {return dest_node->module()->gate(dest_gate);}
/**
* Returns the gate at the local end of this connection.
*/
cGate *localGate() const {return src_node->module()->gate(src_gate);}
};
protected:
int num_nodes;
Node *nodev;
Node *target;
public:
/** @name Constructors, destructor, assignment */
//@{
/**
* Constructor.
*/
explicit cTopology(const char *name=NULL);
/**
* Copy constructor.
*/
cTopology(const cTopology& topo);
/**
* Destructor.
*/
virtual ~cTopology();
/**
* Assignment operator. The name member doesn't get copied; see cObject's operator=() for more details.
*/
cTopology& operator=(const cTopology& topo);
//@}
/** @name Redefined cObject member functions. */
//@{
/**
* Creates and returns an exact copy of this object.
* See cObject for more details.
*/
virtual cPolymorphic *dup() const {return new cTopology(*this);}
/**
* Produces a one-line description of object contents into the buffer passed as argument.
* See cObject for more details.
*/
virtual std::string info() const;
/**
* Serializes the object into a PVM or MPI send buffer.
* Used by the simulation kernel for parallel execution.
* See cObject for more details.
*/
virtual void netPack(cCommBuffer *buffer);
/**
* Deserializes the object from a PVM or MPI receive buffer
* Used by the simulation kernel for parallel execution.
* See cObject for more details.
*/
virtual void netUnpack(cCommBuffer *buffer);
//@}
/** @name Extracting the topology from a network.
*
* extract...() functions build topology from the model.
* User can select which modules to include. All connections
* between those modules will be in the topology. Connections can
* cross compound module boundaries.
*/
//@{
/**
* Extracts model topology by a user-defined criteria. Includes into the graph
* modules for which the passed selfunc() returns nonzero. The userdata
* parameter may take any value you like, and it is passed back to selfunc()
* in its second argument.
*/
void extractFromNetwork(int (*selfunc)(cModule *,void *), void *userdata=NULL);
/**
* Extracts model topology by module type (classnames). Includes into
* the graph all modules whose className() is one of the strings
* listed as arguments. The argument list must be terminated by a NULL
* pointer. Example:
*
* <pre>
* cTopology topo;
* topo.extractByModuleType("Host", "Router", NULL);
* </pre>
*/
void extractByModuleType(const char *type1,...);
/**
* Extracts model topology by module type (classnames). Includes into
* the graph all modules whose className() is one of the class names in
* in the 'types' argument. 'types' is a vector of char* pointers,
* terminated by a NULL pointer.
*/
void extractByModuleType(const char **types);
/**
* Extracts model topology by module type (classnames). Includes into
* the graph all modules whose className() is one of the class names in
* in the 'types' argument.
*/
void extractByModuleType(const std::vector<std::string> types);
/**
* Extracts model topology by parameter value. Includes into the graph
* modules which have a parameter with the given name and (optionally)
* the given value.
*/
void extractByParameter(const char *parname, cPar *value=NULL);
/**
* Deletes the topology stored in the object.
*/
void clear();
//@}
/** @name Functions to examine topology by hand.
*
* Users also need to rely on Node and Link member functions
* to explore the graph stored in the object.
*/
//@{
/**
* Returns the number of nodes in the graph.
*/
int nodes() const {return num_nodes;}
/**
* Returns pointer to the ith node in the graph. Node's methods
* can be used to further examine the node's connectivity, etc.
*/
Node *node(int i);
/**
* Returns the graph node which corresponds to the given module in the
* network. If no graph node corresponds to the module, the method returns
* NULL. This method assumes that the topology corresponds to the
* network, that is, it was probably created with one of the
* extract...() functions.
*/
Node *nodeFor(cModule *mod);
//@}
/** @name Algorithms to find shortest paths. */
/*
* To be implemented:
* - void unweightedMultiShortestPathsTo(Node *target);
* - void weightedSingleShortestPathsTo(Node *target);
* - void weightedMultiShortestPathsTo(Node *target);
*/
//@{
/**
* Apply the Dijkstra algorithm to find all shortest paths to the given
* graph node. The paths found can be extracted via Node's methods.
*/
void weightedSingleShortestPathsTo(Node *target);
void unweightedSingleShortestPathsTo(Node *target);
/**
* Returns the node that was passed to the most recently called
* shortest path finding function.
*/
Node *targetNode() const {return target;}
//@}
};
#endif
_______________________________________________
OMNeT++ Mailing List
options: http://lists.omnetpp.org/mailman/listinfo/omnetpp-l
archive: http://www.omnetpp.org/listarchive/index.php
Home |
Main Index |
Thread Index