Routing support. More...

#include <Topology.h>

Inheritance diagram for inet::Topology:

Classes
class	Link
	Supporting class for Topology, represents a link in the graph. More...

class	LinkIn
	Supporting class for Topology. More...

class	LinkOut
	Supporting class for Topology. More...

class	Node
	Supporting class for Topology, represents a node in the graph. More...

class	Predicate
	Base class for selector objects used in extract...() methods of Topology. More...

Public Member Functions
Constructors, destructor, assignment
	Topology (const char *name=nullptr)
	Constructor. More...

	Topology (const Topology &topo)
	Copy constructor. More...

virtual	~Topology ()
	Destructor. More...

Topology &	operator= (const Topology &topo)
	Assignment operator. More...

Redefined cObject member functions.
virtual Topology *	dup () const override
	Creates and returns an exact copy of this object. More...

virtual std::string	info () const override
	Produces a one-line description of the object's contents. More...

virtual void	parsimPack (cCommBuffer *buffer) const override
	Serializes the object into an MPI send buffer. More...

virtual void	parsimUnpack (cCommBuffer *buffer) override
	Deserializes the object from an MPI receive buffer Used by the simulation kernel for parallel execution. More...

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.
void	extractFromNetwork (bool(selfunc)(cModule , void ), void userdata=nullptr)
	Extracts model topology by a user-defined criteria. More...

void	extractFromNetwork (Predicate *predicate)
	The type safe, object-oriented equivalent of extractFromNetwork(selfunc, userdata). More...

void	extractByModulePath (const std::vector< std::string > &fullPathPatterns)
	Extracts model topology by module full path. More...

void	extractByNedTypeName (const std::vector< std::string > &nedTypeNames)
	Extracts model topology by the fully qualified NED type name of the modules. More...

void	extractByProperty (const char propertyName, const char value=nullptr)
	Extracts model topology by a module property. More...

void	extractByParameter (const char paramName, const char paramValue=nullptr)
	Extracts model topology by a module parameter. More...

void	clear ()
	Deletes the topology stored in the object. More...

Manipulating the graph.
int	addNode (Node *node)
	Adds the given node to the graph. More...

void	deleteNode (Node *node)
	Removes the given node from the graph, together with all of its links. More...

void	addLink (Link link, Node srcNode, Node *destNode)
	TODO Note: also serves as reconnectLink() More...

void	addLink (Link link, cGate srcGate, cGate *destGate)
	TODO Note: also serves as reconnectLink() More...

void	deleteLink (Link *link)
	Removes the given link from the graph. More...

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.
int	getNumNodes () const
	Returns the number of nodes in the graph. More...

Node *	getNode (int i)
	Returns pointer to the ith node in the graph. More...

Node *	getNodeFor (cModule *mod)
	Returns the graph node which corresponds to the given module in the network. More...

Algorithms to find shortest paths.
void	calculateUnweightedSingleShortestPathsTo (Node *target)
	Apply the Dijkstra algorithm to find all shortest paths to the given graph node. More...

void	calculateWeightedSingleShortestPathsTo (Node *target)
	Apply the Dijkstra algorithm to find all shortest paths to the given graph node. More...

Node *	getTargetNode () const
	Returns the node that was passed to the most recently called shortest path finding function. More...

Protected Member Functions
void	unlinkFromSourceNode (Link *link)

void	unlinkFromDestNode (Link *link)

virtual Node *	createNode (cModule *module)
	Node factory. More...

virtual Link *	createLink ()
	Link factory. More...

Static Protected Member Functions
static bool	lessByModuleId (Node a, Node b)

static bool	isModuleIdLess (Node *a, int moduleId)

Protected Attributes
std::vector< Node * >	nodes

Node *	target

Detailed Description

Routing support.

The Topology class was designed primarily to support routing in telecommunication or multiprocessor networks.

A Topology object stores an abstract representation of the network in graph form:

each Topology node corresponds to a module (simple or compound), and
each Topology edge corresponds to a link or series of connecting links.

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 is 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.

See also: Topology::Node, Topology::Link, Topology::LinkIn, Topology::LinkOut

Constructor & Destructor Documentation

inet::Topology::Topology ( const char * name = nullptr )

explicit

Constructor.

                                    : cOwnedObject(name)
 {
     target = nullptr;
 }

inet::Topology::Topology ( const Topology & topo )

Copy constructor.

                                        : cOwnedObject(topo)
 {
     throw cRuntimeError(this, "copy ctor not implemented yet");
 }

inet::Topology::~Topology ( )

virtual

Destructor.

Reimplemented in inet::NetworkConfiguratorBase::Topology.

 {
     clear();
 }

Member Function Documentation

void inet::Topology::addLink	(	Link *	link,
		Node *	srcNode,
		Node *	destNode
	)

TODO Note: also serves as reconnectLink()

Referenced by inet::NetworkConfiguratorBase::extractTopology().

 {
     // remove from graph if it's already in
     if (link->srcNode)
         unlinkFromSourceNode(link);
     if (link->destNode)
         unlinkFromDestNode(link);
 
     // insert
     if (link->srcNode != srcNode)
         link->srcGateId = -1;
     if (link->destNode != destNode)
         link->destGateId = -1;
     link->srcNode = srcNode;
     link->destNode = destNode;
     srcNode->outLinks.push_back(link);
     destNode->inLinks.push_back(link);
 }

void inet::Topology::addLink	(	Link *	link,
		cGate *	srcGate,
		cGate *	destGate
	)

TODO Note: also serves as reconnectLink()

 {
     // remove from graph if it's already in
     if (link->srcNode)
         unlinkFromSourceNode(link);
     if (link->destNode)
         unlinkFromDestNode(link);
 
     // insert
     Node *srcNode = getNodeFor(srcGate->getOwnerModule());
     Node *destNode = getNodeFor(destGate->getOwnerModule());
     if (!srcNode)
         throw cRuntimeError("cTopology::addLink: module of source gate \"%s\" is not in the graph", srcGate->getFullPath().c_str());
     if (!destNode)
         throw cRuntimeError("cTopology::addLink: module of destination gate \"%s\" is not in the graph", destGate->getFullPath().c_str());
     link->srcNode = srcNode;
     link->destNode = destNode;
     link->srcGateId = srcGate->getId();
     link->destGateId = destGate->getId();
     srcNode->outLinks.push_back(link);
     destNode->inLinks.push_back(link);
 }

int inet::Topology::addNode ( Node * node )

Adds the given node to the graph.

Returns the index of the new graph node (see getNode(int)). Indices of existing graph nodes may change.

 {
     if (node->moduleId == -1) {
         // elements without module ID are stored at the end
         nodes.push_back(node);
         return nodes.size() - 1;
     }
     else {
         // must find an insertion point because nodes[] is ordered by module ID
         auto it = std::lower_bound(nodes.begin(), nodes.end(), node, lessByModuleId);
         it = nodes.insert(it, node);
         return it - nodes.begin();
     }
 }

void inet::Topology::calculateUnweightedSingleShortestPathsTo ( 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.

 {
     // multiple paths not supported :-(
 
     if (!_target)
         throw cRuntimeError(this, "..ShortestPathTo(): target node is nullptr");
     target = _target;
 
     for (auto & elem : nodes) {
         elem->dist = INFINITY;
         elem->outPath = nullptr;
     }
     target->dist = 0;
 
     std::deque<Node *> q;
 
     q.push_back(target);
 
     while (!q.empty()) {
         Node *v = q.front();
         q.pop_front();
 
         // for each w adjacent to v...
         for (int i = 0; i < (int)v->inLinks.size(); i++) {
             if (!v->inLinks[i]->enabled)
                 continue;
 
             Node *w = v->inLinks[i]->srcNode;
             if (!w->enabled)
                 continue;
 
             if (w->dist == INFINITY) {
                 w->dist = v->dist + 1;
                 w->outPath = v->inLinks[i];
                 q.push_back(w);
             }
         }
     }
 }

void inet::Topology::calculateWeightedSingleShortestPathsTo ( 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. Uses weights in nodes and links.

Referenced by inet::GenericNetworkConfigurator::addStaticRoutes(), and inet::IPv4NetworkConfigurator::addStaticRoutes().

 {
     if (!_target)
         throw cRuntimeError(this, "..ShortestPathTo(): target node is nullptr");
     target = _target;
 
     // clean path infos
     for (auto & elem : nodes) {
         elem->dist = INFINITY;
         elem->outPath = nullptr;
     }
 
     target->dist = 0;
 
     std::list<Node *> q;
 
     q.push_back(target);
 
     while (!q.empty()) {
         Node *dest = q.front();
         q.pop_front();
 
         ASSERT(dest->getWeight() >= 0.0);
 
         // for each w adjacent to v...
         for (int i = 0; i < dest->getNumInLinks(); i++) {
             if (!(dest->getLinkIn(i)->isEnabled()))
                 continue;
 
             Node *src = dest->getLinkIn(i)->getRemoteNode();
             if (!src->isEnabled())
                 continue;
 
             double linkWeight = dest->getLinkIn(i)->getWeight();
 
             // links with linkWeight == 0 might induce circles
             ASSERT(linkWeight > 0.0);
 
             double newdist = dest->dist + linkWeight;
             if (dest != target)
                 newdist += dest->getWeight(); // dest is not the target, uses weight of dest node as price of routing (infinity means dest node doesn't route between interfaces)
             if (newdist != INFINITY && src->dist > newdist) {    // it's a valid shorter path from src to target node
                 if (src->dist != INFINITY)
                     q.remove(src); // src is in the queue
                 src->dist = newdist;
                 src->outPath = dest->inLinks[i];
 
                 // insert src node to ordered list
                 auto it = q.begin();
                 for ( ; it != q.end(); ++it)
                     if ((*it)->dist > newdist)
                         break;
 
                 q.insert(it, src);
             }
         }
     }
 }

void inet::Topology::clear ( )

Deletes the topology stored in the object.

Referenced by inet::IPv4NetworkConfigurator::computeConfiguration(), extractFromNetwork(), and ~Topology().

 {
     for (auto & elem : nodes) {
         for (auto & _j : elem->outLinks)
             delete _j; // delete links from their source side
         delete elem;
     }
     nodes.clear();
 }

virtual Link* inet::Topology::createLink ( )

inlineprotectedvirtual

Link factory.

Reimplemented in inet::NetworkConfiguratorBase::Topology, and inet::L2NetworkConfigurator::L2Topology.

Referenced by extractFromNetwork().

577 { return new Link(); }

virtual Node* inet::Topology::createNode ( cModule * module )

inlineprotectedvirtual

Node factory.

Reimplemented in inet::NetworkConfiguratorBase::Topology, inet::L2NetworkConfigurator::L2Topology, and inet::IPv4NetworkConfigurator::Topology.

Referenced by extractFromNetwork().

572 { return new Node(module->getId()); }

void inet::Topology::deleteLink ( Link * link )

Removes the given link from the graph.

Indices of existing links in the source and destination nodes may change.

 {
     unlinkFromSourceNode(link);
     unlinkFromDestNode(link);
     delete link;
 }

void inet::Topology::deleteNode ( Node * node )

Removes the given node from the graph, together with all of its links.

Indices of existing graph nodes may change.

 {
     // remove outgoing links
     for (auto & elem : node->outLinks) {
         Link *link = elem;
         unlinkFromDestNode(link);
         delete link;
     }
     node->outLinks.clear();
 
     // remove incoming links
     for (auto & elem : node->inLinks) {
         Link *link = elem;
         unlinkFromSourceNode(link);
         delete link;
     }
     node->inLinks.clear();
 
     // remove from nodes[]
     auto it = find(nodes, node);
     ASSERT(it != nodes.end());
     nodes.erase(it);
 
     delete node;
 }

virtual Topology* inet::Topology::dup ( ) const

inlineoverridevirtual

Creates and returns an exact copy of this object.

See cObject for more details.

375 { return new Topology(*this); }

inet::Topology::Topology

Topology(const char *name=nullptr)

Constructor.

Definition: Topology.cc:49

void inet::Topology::extractByModulePath ( const std::vector< std::string > & fullPathPatterns )

Extracts model topology by module full path.

All modules whole getFullPath() matches one of the patterns in given string vector will get included. The patterns may contain wilcards in the same syntax as in ini files.

An example:

topo.extractByModulePath(cStringTokenizer("**.host[*] **.router*").asVector());

 {
     extractFromNetwork(selectByModulePath, (void *)&fullPathPatterns);
 }

void inet::Topology::extractByNedTypeName ( const std::vector< std::string > & nedTypeNames )

Extracts model topology by the fully qualified NED type name of the modules.

All modules whose getNedTypeName() is listed in the given string vector will get included.

Note: If you have all class names as a single, space-separated string, you can use cStringTokenizer to turn it into a string vector:

topo.extractByNedTypeName(cStringTokenizer("some.package.Host other.package.Router").asVector());

 {
     extractFromNetwork(selectByNedTypeName, (void *)&nedTypeNames);
 }

void inet::Topology::extractByParameter	(	const char *	paramName,
		const char *	paramValue = `nullptr`
	)

Extracts model topology by a module parameter.

All modules get included that have a parameter with the given name, and the parameter's str() method returns the paramValue string. If paramValue is nullptr, only the parameter's existence is checked but not its value.

 {
     struct
     {
         const char *name;
         const char *value;
     } data = {
         paramName, paramValue
     };
     extractFromNetwork(selectByParameter, (void *)&data);
 }

void inet::Topology::extractByProperty	(	const char *	propertyName,
		const char *	value = `nullptr`
	)

Extracts model topology by a module property.

All modules get included that have a property with the given name and the given value (more precisely, the first value of its default key being the specified value). If value is nullptr, the property's value may be anything except "false" (i.e. the first value of the default key may not be "false").

For example, topo.extractByProperty("networkNode"); would extract all modules that contain the @networkNode property, like the following one:

module X {
    @networkNode;
}

Referenced by inet::STPTester::depthFirstSearch(), inet::L2NetworkConfigurator::extractTopology(), and inet::NetworkConfiguratorBase::extractTopology().

 {
     struct
     {
         const char *name;
         const char *value;
     } data = {
         propertyName, value
     };
     extractFromNetwork(selectByProperty, (void *)&data);
 }

void inet::Topology::extractFromNetwork	(	bool()(cModule , void *)	selfunc,
		void *	userdata = `nullptr`
	)

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.

Referenced by extractByModulePath(), extractByNedTypeName(), extractByParameter(), extractByProperty(), and extractFromNetwork().

 {
     clear();
 
     // Loop through all modules and find those that satisfy the criteria
     for (int modId = 0; modId <= getSimulation()->getLastComponentId(); modId++)
     {
         cModule *module = getSimulation()->getModule(modId);
         if (module && predicate(module, data)) {
             Node *node = createNode(module);
             nodes.push_back(node);
         }
     }
 
     // Discover out neighbors too.
     for (auto & elem : nodes) {
         // Loop through all its gates and find those which come
         // from or go to modules included in the topology.
 
         Node *node = elem;
         cModule *mod = getSimulation()->getModule(node->moduleId);
 
         for (cModule::GateIterator i(mod); !i.end(); i++) {
             cGate *gate = *i;
             if (gate->getType() != cGate::OUTPUT)
                 continue;
 
             // follow path
             cGate *srcGate = gate;
             do {
                 gate = gate->getNextGate();
             } while (gate && !predicate(gate->getOwnerModule(), data));
 
             // if we arrived at a module in the topology, record it.
             if (gate) {
                 Link *link = createLink();
                 link->srcNode = node;
                 link->srcGateId = srcGate->getId();
                 link->destNode = getNodeFor(gate->getOwnerModule());
                 link->destGateId = gate->getId();
                 node->outLinks.push_back(link);
             }
         }
     }
 
     // fill inLinks vectors
     for (auto & elem : nodes) {
         for (auto & _l : elem->outLinks) {
             Topology::Link *link = _l;
             link->destNode->inLinks.push_back(link);
         }
     }
 }

void inet::Topology::extractFromNetwork ( Predicate * predicate )

The type safe, object-oriented equivalent of extractFromNetwork(selfunc, userdata).

 {
     extractFromNetwork(selectByPredicate, (void *)predicate);
 }

Topology::Node * inet::Topology::getNode ( int i )

Returns pointer to the ith node in the graph.

Node's methods can be used to further examine the node's connectivity, etc.

Referenced by inet::GenericNetworkConfigurator::addStaticRoutes(), inet::IPv4NetworkConfigurator::addStaticRoutes(), inet::IPv4NetworkConfigurator::configureAllInterfaces(), inet::IPv4NetworkConfigurator::configureAllRoutingTables(), inet::L2NetworkConfigurator::configureInterface(), inet::IPv4NetworkConfigurator::configureRoutingTable(), inet::STPTester::depthFirstSearch(), inet::IPv4NetworkConfigurator::dumpConfig(), inet::GenericNetworkConfigurator::dumpRoutes(), inet::IPv4NetworkConfigurator::dumpRoutes(), inet::NetworkConfiguratorBase::dumpTopology(), inet::L2NetworkConfigurator::extractTopology(), inet::NetworkConfiguratorBase::extractTopology(), inet::NetworkConfiguratorBase::extractWirelessNeighbors(), inet::IPv4NetworkConfigurator::readManualMulticastRouteConfiguration(), and inet::IPv4NetworkConfigurator::readManualRouteConfiguration().

 {
     if (i < 0 || i >= (int)nodes.size())
         throw cRuntimeError(this, "invalid node index %d", i);
     return nodes[i];
 }

Topology::Node * inet::Topology::getNodeFor ( cModule * mod )

Returns the graph node which corresponds to the given module in the network.

If no graph node corresponds to the module, the method returns nullptr. This method assumes that the topology corresponds to the network, that is, it was probably created with one of the extract...() functions.

Referenced by addLink(), and extractFromNetwork().

 {
     // binary search because nodes[] is ordered by module ID
     Node tmpNode(mod->getId());
     auto it = std::lower_bound(nodes.begin(), nodes.end(), &tmpNode, lessByModuleId);
 //TODO: this does not compile with VC9 (VC10 is OK): auto it = std::lower_bound(nodes.begin(), nodes.end(), mod->getId(), isModuleIdLess);
     return it == nodes.end() || (*it)->moduleId != mod->getId() ? nullptr : *it;
 }

int inet::Topology::getNumNodes ( ) const

inline

Returns the number of nodes in the graph.

522 { return nodes.size(); }

inet::Topology::nodes

std::vector< Node * > nodes

Definition: Topology.h:333

Node* inet::Topology::getTargetNode ( ) const

inline

Returns the node that was passed to the most recently called shortest path finding function.

565 { return target; }

inet::Topology::target

Node * target

Definition: Topology.h:334

std::string inet::Topology::info ( ) const

overridevirtual

Produces a one-line description of the object's contents.

See cObject for more details.

 {
     std::stringstream out;
     out << "n=" << nodes.size();
     return out.str();
 }

static bool inet::Topology::isModuleIdLess	(	Node *	a,
		int	moduleId
	)

inlinestaticprotected

338 { return (unsigned int)a->moduleId < (unsigned int)moduleId; }

static bool inet::Topology::lessByModuleId	(	Node *	a,
		Node *	b
	)

inlinestaticprotected

Referenced by addNode(), and getNodeFor().

337 { return (unsigned int)a->moduleId < (unsigned int)b->moduleId; }

inet::units::values::b

value< double, units::m > b

Definition: Units.h:1054

Topology & inet::Topology::operator= ( const Topology & topo )

Assignment operator.

The name member is not copied; see cNamedObject's operator=() for more details.

 {
     throw cRuntimeError(this, "operator= not implemented yet");
 }

void inet::Topology::parsimPack ( cCommBuffer * buffer ) const

overridevirtual

Serializes the object into an MPI send buffer.

Used by the simulation kernel for parallel execution. See cObject for more details.

 {
     throw cRuntimeError(this, "parsimPack() not implemented");
 }

void inet::Topology::parsimUnpack ( cCommBuffer * buffer )

overridevirtual

Deserializes the object from an MPI receive buffer Used by the simulation kernel for parallel execution.

See cObject for more details.

 {
     throw cRuntimeError(this, "parsimUnpack() not implemented");
 }

void inet::Topology::unlinkFromDestNode ( Link * link )

protected

Referenced by addLink(), deleteLink(), and deleteNode().

 {
     std::vector<Link *>& destInLinks = link->destNode->inLinks;
     auto it = find(destInLinks, link);
     ASSERT(it != destInLinks.end());
     destInLinks.erase(it);
 }

void inet::Topology::unlinkFromSourceNode ( Link * link )

protected

Referenced by addLink(), deleteLink(), and deleteNode().

 {
     std::vector<Link *>& srcOutLinks = link->srcNode->outLinks;
     auto it = find(srcOutLinks, link);
     ASSERT(it != srcOutLinks.end());
     srcOutLinks.erase(it);
 }

Member Data Documentation

std::vector<Node *> inet::Topology::nodes

protected

Referenced by addNode(), calculateUnweightedSingleShortestPathsTo(), calculateWeightedSingleShortestPathsTo(), clear(), deleteNode(), extractFromNetwork(), getNode(), getNodeFor(), and info().

Node* inet::Topology::target

protected

Referenced by calculateUnweightedSingleShortestPathsTo(), calculateWeightedSingleShortestPathsTo(), and Topology().

The documentation for this class was generated from the following files:

Classes

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation