Ford Fulkerson Algorithm error

[Trice]

I want to make 10 guided, weighted random graph with 100 peakd and 250 edged. (Now just 1 graph with 10 peakd and 20 edges)
The errors are in the FF algorithm and in the Path_Finder and maybe in min function from graph class.
The problem is : I don't know how to implement the FF algorihm to work on my graph. First, i got an vector overload error. And then, i don't know what is the problem.
Here is the code :

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <locale>
#include <time.h>
#include <fstream>
#include <string>
#include <ctime>
#include <queue>
//Graph class
//One edge data

struct edgestruct
{
	int peak_id;
	int weight;
	int capacity = 0;
};


class Graph
{
public:
	std::vector<std::vector<edgestruct*>> graph;


	//= operator for graphgenerate
	Graph& operator=(std::vector<std::vector<edgestruct*>> graph)
	{
		this->graph = graph;
		return *this;
	}

	//Operator [] for index, what gave back an edge vector
	std::vector<edgestruct*> operator[] (int index) {
		return this->graph[index];
	}

	//Funcions
	Graph openfromfile(std::ifstream&);
	int min();

};


//Open one graph from file
Graph Graph::openfromfile(std::ifstream& input_file)
{
	std::string line;
	while (line != ";")
	{
		//Read one line
		std::getline(input_file, line);

		//Read one edge from the line
		if (line != ";")
		{
			std::vector<edgestruct*> edges;
			graph.push_back(edges);
			int line_index = 0;
			while (line_index < line.size())
			{
				std::string edge;
				if (line != ";")
				{
					while (line[line_index] != ' ')
						edge.push_back(line[line_index++]);
				}
				line_index++;
				//read the edge and get where point to
				int edge_index = 0;
				std::string peak;
				std::string weight;
				if (edge != "")
				{
					while (edge[edge_index] != '/')
						peak.push_back(edge[edge_index++]);
					edge_index++;
					while (edge_index < edge.size())
						weight.push_back(edge[edge_index++]);
				}

				//If we got the edge and the peak, then store it
				if (peak != "")
				{
					edgestruct* curr_edge;
					curr_edge = new edgestruct;
					curr_edge->peak_id = std::stoi(peak);
					curr_edge->weight = std::stoi(weight);
					graph[graph.size() - 1].push_back(curr_edge);
				}
			}
		}
	}
	return *this;
};

//minimum function for the smallset capacity
int Graph::min()
{
	int min = INT_MAX;
	for (int i = 0; i < graph.size(); i++)
	{
		for (int j = 0; j < graph[i].size(); j++)
		{
			//if the weight-current capacity smaller then minimum, be the min
			if (graph[i][j]->weight - graph[i][j]->capacity < min)
			{
				min = graph[i][j]->weight - graph[i][j]->capacity;
			}
		}
	}
	return min;
}
//End of the graph class

//give back a true, if exist a path between s and t, save the path
bool Path_Finder(Graph rGraph, int s, int t, std::vector<int> parent)
{
	bool visited[250];
	memset(visited, 0, sizeof(visited));
	std::queue <int> q;
	q.push(s);
	visited[s] = true;
	parent[s] = -1;
	int u;
	while (!q.empty())
	{
		u = q.front();
		q.pop();

		for (int v = 0; v<rGraph.graph.size(); v++)
		{
			if (visited[v] == false && rGraph.graph[u][v] > 0)
			{
				q.push(v);
				parent.push_back(u);
				visited[v] = true;
			}
		}
	}
	return (visited[t] == true);
}
//Ford Fulkerson algorithm
int Ford_Fulkerson(Graph g, int s, int t)
{
	int u, v;
	Graph rGraph;
	for (u = 0; u < g.graph.size(); u++)
		for (v = 0; v < g.graph[u].size(); v++)
			rGraph[u][v] = g.graph[u][v];

	std::vector<int> parent;
	int Maximum_Flow = 0;
	while (Path_Finder(rGraph, s, t, parent))
	{
		int path_flow = INT_MAX;
		//Search for the smallest capacity
		for (v = t; v != s; v = parent[v])
		{
			u = parent[v];
			path_flow = rGraph.min();
		}
		//increase or decrease capacity in the path's edges
		for (v = t; v != s; v = parent[v])
		{
			u = parent[v];
			rGraph[u][v] -= path_flow;
			rGraph[v][u] += path_flow;
		}
		//inclrease the maxmum flow
		Maximum_Flow += path_flow;
	}
	return Maximum_Flow;
}


int main()
{
	setlocale(LC_ALL, "hun");
	srand((unsigned)time(NULL));
	//Read the graph from the file
	std::vector<Graph> graphs;
	std::ifstream input_file("graphs.txt");
	while (!input_file.eof())
	{
		Graph graf;
		graf.openfromfile(input_file);
		graphs.push_back(graf);
	}
	input_file.close();
	for (int i = 0; i < graphs.size(); i++)
	{
		std::cout << i + 1 << ". graph\nthe maximum flow is: " << Ford_Fulkerson(graphs[i], 0, 99) << std::endl << std::endl;
	}
	return 0;
}

Here is the graph(text format):
0. 2/9
1. 4/5 7/6
2.
3. 6/6
4. 2/3 5/3 5/1 7/6 3/3
5. 6/3 7/8 4/7
6. 4/3 3/3
7. 8/7 1/8 0/7 2/9
8.
9. 7/1 3/3
;
And here is the graph:
https://imgur.com/d261jYK

[lastchance]

@trice,
Your code is almost unreadable, partly because the comments are in Hungarian (despite most of the variable names being in English), but mostly because you haven't used code tags.

Please
(1) Repost a simpler code and either type in the code tags or select it and use the <> button in the formatting menu.
(2) Post a SIMPLER code - yes, simpler! There is no point trying to debug TEN HUGE AND RANDOMLY GENERATED graphs when you have the facility to read a SMALL FIXED one from file. Make sure you supply this graph file as well. Ideally it can be sourced from something with a known solution.
(3) Please remove from the code all non-standard extensions like conio.h and _getch().
(4) STATE what sort of error you are getting. Is it not compiling? Does it crash? Does it simply produce the wrong answer? You haven't told us.

A very brief inspection of your FF algorithm and path finder routines suggests that your path finder routine needs to return the vector<int> parent, whereas it won't because you have passed by value and not by reference. You would probably also have to clear it every time that you ran the path finder.

[Trice]

@lastchance
I hope, i did what you want. I can't make it simpler than this. I tried to translate the comments. I wrote the error in the top. I already make the Dijkstra algorithm and work fine, so the graph is good.
The main problem is, i don't know what to do now. I try a lot of things.

I don't know how to search in my graph class for every exist path (or just some of them).

I want to get the capacity, then if the edge is opposite directed, then decrease, else increase it by this value.

I need to examine the existed path. If the capacity is 0, then finish, else search for an other path. (2 same path is not allowed)
I hope, you can help me.

[lastchance]

@Trice, yes I do know how the Ford-Fulkerson algorithm works, and for flow in fluid networks it can be useful to me too.

(1) Please remove all generation of large random graphs and JUST read from a simple file. Create (outside of your program) a SMALL, SIMPLE graph in graph.txt and then we will be able to test it. PLEASE SUPPLY THAT FILE.

You do NOT, repeat NOT, need a whole array of separate graphs.

(2) Until you supply such a graph I'm not going to test it. However, I can see that on line 223 you are calling pathFinder and you are expecting to get back an updated vector<int> parent. This will not happen because on line 186 your definition of vector<int> parent ensures that it is passed by VALUE and not by REFERENCE. The calling routine will not see the updated version created in pathFinder.

Please simplify your code in main so that it just reads in ONE SMALL existing graph from an existing text file, not confuses things by generating lots of graphs.

Please also put any amended code BELOW this post or things are going to get confusing.

[Trice]

@lastchance
I make a simplier graph. 10 peak and 20 edges. I deleted the graph generation and saving from the code. I uploaded an image from the graph and write the text version of it.
This is the type of graph what i have to work with.

[lastchance]

@Trice, please make changes BELOW, not to previous posts - it makes all replies confusing.

Your example graph is still too complex - you also appear to have multiple pipes (e.g. 4 to 5) and directions(?) - is this intended?

Reduce your graphs to a SINGLE graph, not an array of them.



Some glaring errors:
Ford_Fulkerson(graphs[i], 0, 99)
You haven't got this many vertices in your example.


bool Path_Finder(Graph rGraph, int s, int t, std::vector<int> parent)
You should pass parent by REFERENCE (with a &), not by VALUE.
You also need parent.clear() at the start here.

			rGraph[u][v] -= path_flow;
			rGraph[v][u] += path_flow;

Surely these updates are the wrong way round?

[Trice]

@lastchance
This graph is the simpliest what i can make for my problem. In the 4->5 weight:1 and 4->5 weight:3 is allowed. I have to work with a multigraph. It is not wrong. I repair the errors, what you wrote.

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <locale>
#include <time.h>
#include <fstream>
#include <string>
#include <ctime>
#include <queue>
//Graph class
//One edge data

struct edgestruct
{
	int peak_id;
	int weight;
	int capacity = 0;
};


class Graph
{
public:
	std::vector<std::vector<edgestruct*>> graph;


	//= operator for graphgenerate
	Graph& operator=(std::vector<std::vector<edgestruct*>> graph)
	{
		this->graph = graph;
		return *this;
	}

	//Operator [] for index, what gave back an edge vector
	std::vector<edgestruct*> operator[] (int index) {
		return this->graph[index];
	}

	//Funcions
	Graph openfromfile(std::ifstream&);
	int min();

};


//Open one graph from file
Graph Graph::openfromfile(std::ifstream& input_file)
{
	std::string line;
	while (line != ";")
	{
		//Read one line
		std::getline(input_file, line);

		//Read one edge from the line
		if (line != ";")
		{
			std::vector<edgestruct*> edges;
			graph.push_back(edges);
			int line_index = 0;
			while (line_index < line.size())
			{
				std::string edge;
				if (line != ";")
				{
					while (line[line_index] != ' ')
						edge.push_back(line[line_index++]);
				}
				line_index++;
				//read the edge and get where point to
				int edge_index = 0;
				std::string peak;
				std::string weight;
				if (edge != "")
				{
					while (edge[edge_index] != '/')
						peak.push_back(edge[edge_index++]);
					edge_index++;
					while (edge_index < edge.size())
						weight.push_back(edge[edge_index++]);
				}

				//If we got the edge and the peak, then store it
				if (peak != "")
				{
					edgestruct* curr_edge;
					curr_edge = new edgestruct;
					curr_edge->peak_id = std::stoi(peak);
					curr_edge->weight = std::stoi(weight);
					graph[graph.size() - 1].push_back(curr_edge);
				}
			}
		}
	}
	return *this;
};

//minimum function for the smallset capacity
int Graph::min()
{
	int min = INT_MAX;
	for (int i = 0; i < graph.size(); i++)
	{
		for (int j = 0; j < graph[i].size(); j++)
		{
			//if the weight-current capacity smaller then minimum, be the min
			if (graph[i][j]->weight - graph[i][j]->capacity < min)
			{
				min = graph[i][j]->weight - graph[i][j]->capacity;
			}
		}
	}
	return min;
}
//End of the graph class

//give back a true, if exist a path between s and t, save the path
bool Path_Finder(Graph rGraph, int s, int t, std::vector<int>& parent)
{
	bool visited[250];
	memset(visited, 0, sizeof(visited));
	std::queue <int> q;
	q.push(s);
	visited[s] = true;
	parent[s] = -1;
	int u;
	while (!q.empty())
	{
		u = q.front();
		q.pop();

		for (int v = 0; v<rGraph.graph.size(); v++)
		{
			if (visited[v] == false && rGraph.graph[u][v] > 0)
			{
				q.push(v);
				parent.push_back(u);
				visited[v] = true;
			}
		}
	}
	return (visited[t] == true);
}
//Ford Fulkerson algorithm
int Ford_Fulkerson(Graph g, int s, int t)
{
	int u, v;
	Graph rGraph;
	rGraph=g.graph;

	std::vector<int> parent;
	int Maximum_Flow = 0;
	while (Path_Finder(rGraph, s, t, parent))
	{
		int path_flow = INT_MAX;
		//Search for the smallest capacity
		for (v = t; v != s; v = parent[v])
		{
			u = parent[v];
			path_flow = rGraph.min();
		}
		//increase or decrease capacity in the path's edges
		for (v = t; v != s; v = parent[v])
		{
			u = parent[v];
                        parent.clear();
			rGraph[u][v] -= path_flow;
			rGraph[v][u] += path_flow;
		}
		//inclrease the maxmum flow
		Maximum_Flow += path_flow;
	}
	return Maximum_Flow;
}


int main()
{
	setlocale(LC_ALL, "hun");
	srand((unsigned)time(NULL));
	//Read the graph from the file
	std::vector<Graph> graphs;
	std::ifstream input_file("graphs.txt");
	while (!input_file.eof())
	{
		Graph graf;
		graf.openfromfile(input_file);
		graphs.push_back(graf);
	}
	input_file.close();
	for (int i = 0; i < graphs.size(); i++)
	{
		std::cout << i + 1 << ". graph\nthe maximum flow is: " << Ford_Fulkerson(graphs[i], 0, 9) << std::endl << std::endl;
	}
	return 0;
}

Here is the graph(graphs.txt):
2/9
4/5 7/6

6/6
2/3 5/3 5/1 7/6 3/3
6/3 7/8 4/7
4/3 3/3
8/7 1/8 0/7 2/9

7/1 3/3
;
And here is the graph:
https://imgur.com/d261jYK

[lastchance]

Hello @Trice,

I'm not sure how you deal with a multigraph. If it's any use, here is my own version of the Ford-Fulkerson algorithm. At the end I have hard-coded the example from
https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/
because it is a directed graph with a known maximum-flow solution.

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>
#include <limits>
using namespace std;


const double LARGE = numeric_limits<double>::max();


//======================================================================


template <typename Container> void print( string text, const Container &C )    // General-purpose print routine
{
   cout << text;
   for ( auto e : C ) cout << e << "  ";
   cout << '\n';
}


//=====================================================================


template <typename T> T error( string text, T value )      // Used for error-reporting
{
   cout << text << '\n';
   return value;
}


//=====================================================================


struct Edge                                                
{
   int v;                                                  // Adjacent vertex
   double wt;                                              // POSSIBLE flow TO that vertex
   double flow;                                            // CURRENT flow TO that vertex (-ve means FROM)
};


//======================================================================


struct Graph
{
   int nvert;                                           
   vector< vector<Edge> > adj;                       

   Graph( int n = 0 );
   void addEdge( int i, int j, double wt = 1.0, bool directed = false );
   void read( istream &in, bool directed = false );
   void print( ostream &out = cout );                   
   map < pair<int,int>, Edge* > edgePointers();         
};


Graph::Graph( int n )
{
   nvert = n;
   adj = vector< vector<Edge> >( n );
}


void Graph::addEdge( int i, int j, double w, bool directed )
{
   int mx = max( i, j );
   if ( mx >= nvert ) { nvert = mx + 1;   adj.resize( nvert ); }

   adj[i].push_back( { j, w, 0.0 } );
   if ( !directed ) adj[j].push_back( { i, w, 0.0 } );
}


void Graph::read( istream &in, bool directed )
{
   int i, j;
   double wt;
   while ( in >> i >> j >> wt ) addEdge( i, j, wt, directed );
}


void Graph::print( ostream &out )
{
   for ( int i = 0; i < nvert; i++ )
   {
      out << "Vertex " << i << ":\n";
      for ( auto e : adj[i] ) 
      {
         out << " -> " << e.v
             << ":   " << e.wt 
             << "  ( " << e.flow << " )"
             << '\n';
      }
   }
}


map < pair<int,int>, Edge* > Graph::edgePointers()
{
   map< pair<int,int>, Edge* > ptr;
   for ( int i = 0; i < nvert; i++ )
   {
      for ( Edge &e : adj[i] ) ptr[{i,e.v}] = &e;
   }

// cout << "MAP:\n";
// for ( auto x : ptr ) cout << x.first.first << " - " << x.first.second << ":  " << (*x.second).wt << '\n';

   return ptr;
}


//=====================================================================


bool pathFinder( const Graph &g, int start, int finish, vector<int> &path )    // Find a path WITH CAPACITY
{                                                                              //    from start to finish
   path.clear();

   int N = g.nvert;
   if ( min( start, finish ) < 0 || max( start, finish ) >= N ) return error<bool>( "Invalid start/finish", false );

   queue<int> Q;
   vector<int> prev( N, -1 );
   Q.push( start );

   while ( !Q.empty() )
   {
      int n = Q.front();
      Q.pop();
      for ( Edge e : g.adj[n] )
      {
         if ( e.flow < e.wt && prev[e.v] < 0 )             // Added to tree if has capacity
         {                                                 //    and not previously accessed
            prev[e.v] = n;
            Q.push( e.v );
         }
      }
      if ( prev[finish] >= 0 ) break;                      // Found a path with capacity
   }
   if ( prev[finish] < 0 ) return false;                   // No path with capacity available


   // Create the path back to the source
   int num = finish;
   path.push_back( num );
   while ( num != start )
   {
      num = prev[num];
      path.push_back( num );
   }
   reverse( path.begin(), path.end() );

   return true;
}


//======================================================================


double FordFulkerson( Graph &g, int start, int finish )
{
   int N = g.nvert;

   if ( min( start, finish ) < 0 || max( start, finish ) >= N ) return error<double>( "Invalid start/finish", -1.0 );

   map< pair<int,int>, Edge* > ptr = g.edgePointers();
   vector<int> path;

   double flow = 0.0;
   while( pathFinder( g, start, finish, path ) )
   {
      double extra = LARGE;
      for ( int i = 0; i < path.size() - 1; i++ )
      {
         Edge e = *ptr[ { path[i], path[i+1] } ];
         extra = min( extra, e.wt - e.flow );         // Extra flow on this path is limited by smallest free capacity
      }
      flow += extra;
      for ( int i = 0; i < path.size() - 1; i++ )
      {
         Edge &e = *ptr[ { path[i], path[i+1] } ];   e.flow += extra;   // Add extra flow to this direction ...
         Edge &f = *ptr[ { path[i+1], path[i] } ];   f.flow -= extra;   // ... equivalent to negative in other direction
      }
   }

   return flow;
}


//======================================================================


int main()
{
   bool directed = true;     // true means directed arcs
                             // For directed arcs, capacity in BOTH directions must be specified,
                             //    even if one is 0
                             // For non-directed arcs, just give one direction; the other is automatic
   // Following example from:
   //    https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/
// ifstream in( "graph.txt" );                                  // read from file
   stringstream in( " 0    1   16            1    0    0 \n"    // or fake with stringstream
                    " 0    2   13            2    0    0 \n"
                    " 1    2   10            2    1    4 \n"
                    " 1    3   12            3    1    0 \n"
                    " 2    3    0            3    2    9 \n"
                    " 2    4   14            4    2    0 \n"
                    " 3    4    0            4    3    7 \n"
                    " 3    5   20            5    3    0 \n"
                    " 4    5    4            5    4    0 \n" );

   // Set up graph
   Graph g;
   g.read( in, directed );


   // Calculate maximum flow
   int start = 0, finish = 5;
// cout << "Input start, finish: ";   cin >> start >> finish;
   double flow = FordFulkerson( g, start, finish );
   cout << "\nTotal flow from " << start << " to " << finish << " is " << flow << "\n\n";
   g.print();
}

Total flow from 0 to 5 is 23

Vertex 0:
 -> 1:   16  ( 12 )
 -> 2:   13  ( 11 )
Vertex 1:
 -> 0:   0  ( -12 )
 -> 2:   10  ( 0 )
 -> 3:   12  ( 12 )
Vertex 2:
 -> 0:   0  ( -11 )
 -> 1:   4  ( 0 )
 -> 3:   0  ( 0 )
 -> 4:   14  ( 11 )
Vertex 3:
 -> 1:   0  ( -12 )
 -> 2:   9  ( 0 )
 -> 4:   0  ( -7 )
 -> 5:   20  ( 19 )
Vertex 4:
 -> 2:   0  ( -11 )
 -> 3:   7  ( 7 )
 -> 5:   4  ( 4 )
Vertex 5:
 -> 3:   0  ( -19 )
 -> 4:   0  ( -4 )

[lastchance]

Sorry, @Trice, but I'm really struggling to understand your graph structure.

I can now see that you have taken code directly from
https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/
and then tried to amend it to your own graph. The two are not very compatible. Also, your code is hard to use - I had to make changes to your code just to get it to read from file. I think you use pointers unnecessarily, too. Do you really need to use pointers here:
std::vector<std::vector<edgestruct*>> graph;

Line 160:
path_flow = rGraph.min();
is clearly not right here, but I can't honestly work out from your graph structure what should go here. You seem to be duplicating finding the minimum residual capacity: it can be done in this loop, not a separate function.


parent.push_back(u);
is wrong. I didn't fully understand what you were doing, so my earlier advice to make a call to parent.clear() would be wrong. However, you do need to set a size for vector<int> parent in Ford_Fulkerson(). The size whould be equal to the number of vertices, but since I don't understand your graph structure, you will have to do that.


Having read the GeeksForGeeks page I see now that rGraph is standing for residual capacity, so the updates did have the correct sign: I just didn't follow what they stood for when I alluded to that earlier.


Although I can see a way to a directed-graph version, I don't see that this algorithm is going to work very well with multiple arcs in the same direction between vertices. I can't work out from your graph read routine whether you are adding these together: if not, then you ought to.


I have added my own version of the FF algorithm in the preceding post. I hope that it may help. It includes an example from
https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/
and I strongly suggest that you use that as your simple test case, not your multigraph.


I suggest that you revise your graph structure. It is very difficult to follow. Also, if there are a large number of vertices then your connection/adjacency matrix will be huge, but sparse: very inefficient.

I'm afraid that I had to make changes to your code just to get it to read from file. Your input structure is also unnecessarily complex. You are also missing (at least) two headers.

Please try to debug your code by putting simple output lines in, so that you know (a) where you are; (b) what the values of variables are. Alternatively, use a debugger. It was taking me far too long just to progress a few lines to see where the next error was.

I strongly advise that you do not simply rip code from other sites and try to refactor it unless you understand the algorithm behind it. Also, TRY A SIMPLER TEST CASE.

[Trice]

@lastchance
Thank you for your code. I hope, it will help for me.
I have to use pointers, because then i can't write to file and read from files.
I understand the geekforgeeks version, but as you wrote, i was not able to amend it.
As i experienced, my graph generator is fast, because it is sparse, but yes, it's inefficient.

My main problem is with this algorithm:
I have to work with multigraphs, and i can generate it, but can't use the FF algorithm, because i only see it in simple graphs. But this is a problem, what i really want to solve.

I made my own minimum function, because the real one can't use my graph.
The parent made for save the paths, because if the function search for paths, it has to check, what visited already.

If you have a simpler way, to generate a multigraph for my problem, then i would be really gateful.