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 Link
s
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++;
}
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.