c++algorithmomnet++

How to read value from `Link` between two nodes using omnet++


I'm trying to implement Ford Fulkerson algorithm in omnet++ using c++. I took the c++ class from this article but I couldn't read the values from the network which should come from Links

my class algorithm :

// C++ program for implementation of Ford Fulkerson algorithm
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;

// Number of vertices in given graph
#define V 6

class Node : public cSimpleModule
{
  protected:
    // The following redefined virtual function holds the algorithm.
    virtual void initialize();
    virtual void handleMessage(cMessage *msg);
};

Define_Module(Node);

void Node::initialize()
{
    // These values should come from Links
    int graph[V][V] = { {0, 16, 13, 0, 0, 0},
                            {0, 0, 10, 12, 0, 0},
                            {0, 4, 0, 0, 14, 0},
                            {0, 0, 9, 0, 0, 20},
                            {0, 0, 0, 7, 0, 4},
                            {0, 0, 0, 0, 0, 0}
                          };
    fordFulkerson(graph, 0, 5);
}

void Node::handleMessage(cMessage *msg)
{
    send(msg, "out");
}

/* Returns true if there is a path from source 's' to sink 't' in
  residual graph. Also fills parent[] to store the path */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
    // Create a visited array and mark all vertices as not visited
    bool visited[V];
    memset(visited, 0, sizeof(visited));

    // Create a queue, enqueue source vertex and mark source vertex
    // as visited
    queue <int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    // Standard BFS Loop
    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        for (int v=0; v<V; v++)
        {
            if (visited[v]==false && rGraph[u][v] > 0)
            {
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }

    // If we reached sink in BFS starting from source, then return
    // true, else false
    return (visited[t] == true);
}

// Returns tne maximum flow from s to t in the given graph
int fordFulkerson(int graph[V][V], int s, int t)
{
    int u, v;

    // Create a residual graph and fill the residual graph with
    // given capacities in the original graph as residual capacities
    // in residual graph
    int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates
                     // residual capacity of edge from i to j (if there
                     // is an edge. If rGraph[i][j] is 0, then there is not)
    for (u = 0; u < V; u++)
        for (v = 0; v < V; v++)
             rGraph[u][v] = graph[u][v];

    int parent[V];  // This array is filled by BFS and to store path

    int max_flow = 0;  // There is no flow initially

    // Augment the flow while tere is path from source to sink
    while (bfs(rGraph, s, t, parent))
    {
        // Find minimum residual capacity of the edhes along the
        // path filled by BFS. Or we can say find the maximum flow
        // through the path found.
        int path_flow = INT_MAX;
        for (v=t; v!=s; v=parent[v])
        {
            u = parent[v];
            path_flow = min(path_flow, rGraph[u][v]);
        }

        // update residual capacities of the edges and reverse edges
        // along the path
        for (v=t; v != s; v=parent[v])
        {
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
        }

        // Add path flow to overall flow
        max_flow += path_flow;
    }

    // Return the overall flow
    return max_flow;
}

Network :

/
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.
// 
// You should have received a copy of the GNU Lesser General Public License
// along with this program.  If not, see http://www.gnu.org/licenses/.
// 

import Node;

import Link;

//
// Generated network with random topology (6 nodes, 8 edges, seed=100).
//
network Network
{
    @display("bgb=478,329");
    submodules:
        S: Node {
            @display("p=19,87;is=s");
        }
        n1: Node {
            @display("p=130,142;is=s");
        }
        n2: Node {
            @display("p=130,36;is=s");
        }
        n3: Node {
            @display("p=262,142;is=s");
        }
        n4: Node {
            @display("p=262,36;is=s");
        }
        T: Node {
            @display("p=364,87;is=s");
        }
    connections:
        S.g++ <--> Link { @display("t=13"); cost = 13; } <--> n1.g++;
        S.g++ <--> Link {  cost = 16;@display("t=16"); } <--> n2.g++;
        n1.g++ <--> Link {  cost = 1;@display("t=1"); } <--> n2.g++;
        n1.g++ <--> Link {  cost = 14;@display("t=14"); } <--> n3.g++;
        n1.g++ <--> Link {  cost = 9;@display("t=9"); } <--> n4.g++;
        n2.g++ <--> Link {  cost = 12;@display("t=12"); } <--> n4.g++;
        n4.g++ <--> Link {  cost = 20;@display("t=20"); } <--> T.g++;
        n3.g++ <--> Link {  cost = 4;@display("t=4"); } <--> T.g++;
        n3.g++ <--> Link {  cost = 7;@display("t=7"); } <--> n4.g++;
}

enter image description here


Solution

  • It seems like you are using a custom module called Link as your channel, which you seem to have given a cost parameter. Getting to this cost parameter from a Node requires three steps:

    For getting which Link channels are connecting a Node to its neighbors, you need to first query the Node's Connections using the OMNeT++ API. See the section Accessing Gates and Connections in the user manual for details. For each connection, you can then get a pointer to the associated channel (your Link module) using the getChannel method.

    Using the pointer to your Link module, you can query the value of its parameters using OMNet++'s par() method.

    I see that you are also setting your Link modules' Display String (in particular, the t tag to annotate some text). See the user manual's chapter on Display Strings for information on how to read from (or write to) this tag.