cTopology::getNumPaths() always == 0

[Jeff Rossiter]

Hello,

I am trying to use cTopology::calculateUnweightedSingleShortestPathTo(Node *node) to find the shortest path between two nodes. I have previously worked on code which utilized the function and there were no issues. Now I am writing all new code and there are issues. The network I am simulating is more complex than the example I am about to present but when I thought it would be a good idea to get things working with a simple case first.

The problem is that the shortest path algorithm doesn't seem to find any paths. I have  each Device send a self message at the beginning of the simulation. Then in handleMessage I have cTopology extract the topology by module type "Device". Then for each remote Device I have cTopology calculate shortest path but when I check the number of paths it is always 0.

Just to make sure that everything is connected I tried to have the nodes duplicate received messages and then send them out on all outgoing gates. Messages make it from each node to each other node without problems.

My NED files:

simple Device
{
    gates:
        inout port[];
}

network OnlyDevices
{
    @display("bgb=327,187");
    submodules:
        device0: Device {
            @display("p=51,82");
            gates:
                port[1];
        }
        device1: Device {
            @display("p=151,82");
            gates:
                port[2];
        }
        device2: Device {
            @display("p=251,82");
            gates:
                port[1];
        }
    connections:
        device0.port[0] <--> device1.port[0];
        device1.port[1] <--> device2.port[0];
}

Here is Device.cc:

#include "Device.h"

Define_Module(Device);

void Device::initialize()
{
    scheduleAt(simTime(), new cMessage("start"));
}

void Device::handleMessage(cMessage *msg)
{
    std::vector<std::string> nedTypes;

    cTopology *topology = new cTopology("topo");

    nedTypes.push_back("Device");
    topology->extractByNedTypeName(nedTypes);

    int numNodes = topology->getNumNodes();

    EV << this->getParentModule()->getName() << "." << this->getName() << "\n";

    for (int i = 0; i < numNodes; i++) {
        cTopology::Node *node = topology->getNode(i);

        if (node->getModule() != this) {
            topology->calculateUnweightedSingleShortestPathsTo(node);

            EV << "  number of paths to "
               << node->getModule()->getParentModule()->getName()
               << "." << node->getModule()->getName() << ": "
               << node->getNumPaths() << "\n";
        }
    }
    delete topology;
}

Here is the simulation output:

Initializing module OnlyDevices, stage 0
Initializing module OnlyDevices.device0, stage 0
Initializing module OnlyDevices.device1, stage 0
Initializing module OnlyDevices.device2, stage 0
** Event #1  T=0  OnlyDevices.device0 (Device, id=2), on selfmsg `start' (cMessage, id=0)
OnlyDevices.device0
  number of paths to OnlyDevices.device1: 0
  number of paths to OnlyDevices.device2: 0
** Event #2  T=0  OnlyDevices.device1 (Device, id=3), on selfmsg `start' (cMessage, id=1)
OnlyDevices.device1
  number of paths to OnlyDevices.device0: 0
  number of paths to OnlyDevices.device2: 0
** Event #3  T=0  OnlyDevices.device2 (Device, id=4), on selfmsg `start' (cMessage, id=2)
OnlyDevices.device2
  number of paths to OnlyDevices.device0: 0
  number of paths to OnlyDevices.device1: 0
<!> No more events -- simulation ended at event #4, t=0.
** Calling finish() methods of modules

I don't know what I"m missing here. Thanks.

[Jeff Rossiter]

Problem solved. The node that getNumPaths is invoked on is the source node so my code is reporting the number of paths from the destination node to the destination node.

Here is the fixed Device::handleMessage:

void Device::handleMessage(cMessage *msg)
{
    std::vector<std::string> nedTypes;

    nedTypes.push_back("Device");

    cTopology *topo = new cTopology("topo");

    topo->extractByNedTypeName(nedTypes);

    int numNodes = topo->getNumNodes();

    cTopology::Node *sourceNode = topo->getNodeFor(this);

    for (int i = 0; i < numNodes; i++) {

        cTopology::Node *destNode = topo->getNode(i);
        cModule *destModule = destNode->getModule();

        topo->calculateUnweightedSingleShortestPathsTo(destNode);

        EV << "Number of paths from " << this->getName() << " to "
           << destModule->getName() << " = " << sourceNode->getNumPaths()
           << "\n";
    }

    delete topo;
}

Simulation output:

Initializing module OnlyDevices, stage 0
Initializing module OnlyDevices.device0, stage 0
Initializing module OnlyDevices.device1, stage 0
Initializing module OnlyDevices.device2, stage 0

Initializing module OnlyDevices.routeDiscoverer, stage 0

** Event #1  T=0  OnlyDevices.device0 (Device, id=2), on selfmsg `start' (cMessage, id=0)

Number of paths from device0 to device0 = 0
Number of paths from device0 to device1 = 1
Number of paths from device0 to device2 = 1

** Event #2  T=0  OnlyDevices.device1 (Device, id=3), on selfmsg `start' (cMessage, id=1)

Number of paths from device1 to device0 = 1
Number of paths from device1 to device1 = 0
Number of paths from device1 to device2 = 1

** Event #3  T=0  OnlyDevices.device2 (Device, id=4), on selfmsg `start' (cMessage, id=2)

Number of paths from device2 to device0 = 1
Number of paths from device2 to device1 = 1
Number of paths from device2 to device2 = 0

<!> No more events -- simulation ended at event #4, t=0.
** Calling finish() methods of modules

:)