分类： C/C++
2008-10-02 19:06:21
源代码如下：
/*
* Graph Algorithm: 有流量上下界的最大流和最小流
* by billjeff
* 2007/Aug/12
*/
#include
#include
#include
using namespace std ;
#define file_io
#define debug
class Graph {
private:
const static int MAXNODE = 100 ;
struct node{
float lower ;
float upper ;
} ;
struct networkNode{
float l, u ; // max volmun, min volumn ;
float curr ; // current volumn ;
} ;
node _matrix[MAXNODE][MAXNODE] ; // Graph edge volumn array, if one edge's lower < 0
// there is no edge from i to j ;
float _newMatrix[MAXNODE+2][MAXNODE+2] ; // store new graph ;
networkNode _flowMatrix[MAXNODE+1][MAXNODE+2] ; // for ford-fulckson algorithm
int _s, _t ; // start and end point ;
int _nodeNum, _edgeNum ;
bool _isFlowExisted ; // return value of isFlowAvailable() ;
protected:
void graphAdjust(){
// put another two nodes into the graph and re-arrange the volumn of edges;
// _nodeNum+1 as new start node, _nodeNum+2 as new end node ;
int tempNodeNum = _nodeNum+2 ;
float tempVol, tempVolSum ;
for ( int i = 0 ; i < tempNodeNum ; ++i )
for ( int j = 0 ; j < tempNodeNum ; ++j ){
if ( i == _nodeNum && j < _nodeNum ){ // new start to other old nodes
tempVolSum = 0 ;
for ( int k = 0 ; k < _nodeNum ; ++k ){
tempVol = _matrix[k][j].lower ;
if ( tempVol != -1 )
tempVolSum += tempVol ;
}
_newMatrix[i][j] = tempVolSum ;
}
else
if ( j == _nodeNum+1 && i < _nodeNum ){
tempVolSum = 0 ;
for ( int k = 0 ; k < _nodeNum ; ++k ){
tempVol = _matrix[i][k].lower ;
if ( tempVol != -1 )
tempVolSum += tempVol ;
}
_newMatrix[i][j] = tempVolSum ;
}
else
if ( i < _nodeNum && j < _nodeNum ){
tempVol = _matrix[i][j].lower ;
_newMatrix[i][j] = ((tempVol == -1) ? -1 : (_matrix[i][j].upper-tempVol)) ;
}
else
_newMatrix[i][j] = -1 ;
}
//_s = _nodeNum ;
//_t = _s+1 ;
_newMatrix[_s][_t] = numeric_limits
_newMatrix[_t][_s] = _newMatrix[_s][_t] ;
return ;
}
void graphAdjust2(){ // 根据已经求出的扩展图的最大流，去掉附加节点和边
float tempFlow ;
for ( int i = 0 ; i < _nodeNum ; ++i )
for ( int j = 0 ; j < _nodeNum ; ++j ){
tempFlow = _matrix[i][j].lower ;
if ( tempFlow != -1 ){
_flowMatrix[i][j].l += tempFlow ;
_flowMatrix[i][j].curr += tempFlow ;
_flowMatrix[i][j].u += tempFlow ;
}
}
if ( _matrix[_s][_t].lower != -1 ){
_flowMatrix[_s][_t].l = _matrix[_s][_t].lower ;
_flowMatrix[_s][_t].u = _matrix[_s][_t].upper ;
_flowMatrix[_s][_t].curr += _matrix[_s][_t].upper-_matrix[_s][_t].lower ;
}
else{
_flowMatrix[_s][_t].l = -1 ;
_flowMatrix[_s][_t].u = -1 ;
_flowMatrix[_s][_t].curr = 0 ;
}
if ( _matrix[_t][_s].lower != -1 ){
_flowMatrix[_t][_s].l = _matrix[_t][_s].lower ;
_flowMatrix[_t][_s].u = _matrix[_t][_s].upper ;
_flowMatrix[_t][_s].curr += _matrix[_t][_s].upper-_matrix[_t][_s].lower ;
}
else{
_flowMatrix[_t][_s].l = -1 ;
_flowMatrix[_t][_s].u = -1 ;
_flowMatrix[_t][_s].curr = -0 ;
}
}
int check( bool *c, int *p, int num ){
for( int i = 0 ; i < num ; ++i )
if ( (!c[i]) && (p[i] != (MAXNODE+3)) )
return i ;
return -1 ;
}
bool ford( int s, int t, int num, float &a, int *p ){
bool checked[MAXNODE] ;
//int max = numeric_limits
memset( checked, 0, MAXNODE ) ;
for ( int i = 0 ; i < num ; ++i )
p[i] = MAXNODE+3 ;
p[s] = s ;
int flag = 0 ;
while ( true ){
flag = check( checked, p, num ) ;
#ifdef debug1
cout << "s = " << s << ", t = " << t << ", flag = " << flag << endl ;
cout << p[flag] << " " << checked[flag] << endl ;
cout << ( !checked[flag] && (p[flag] != (MAXNODE+3)) ) << endl ;
#endif
if ( flag == t || flag == -1 )
break ;
for ( int i = 0 ; i < num ; ++i )
if ( (p[i] == (MAXNODE+3)) && (_flowMatrix[flag][i].u != -1 || _flowMatrix[i][flag].u != -1) ){
#ifdef debug1
if ( i == 0 ){
cout << "i=0->" << p[i] << endl ;
cout << _flowMatrix[flag][i].u << " " << _flowMatrix[flag][i].u << " " << _flowMatrix[flag][i].curr << endl ;
cout << _flowMatrix[i][flag].u << " " << _flowMatrix[i][flag].l << " " << _flowMatrix[i][flag].curr << endl ;
}
#endif
if ( _flowMatrix[flag][i].u != -1 && _flowMatrix[flag][i].u > _flowMatrix[flag][i].curr ){
p[i] = flag ;
#ifdef debug1
cout << "flag = " << flag << ", i = " << i << endl ;
#endif
}
if ( _flowMatrix[i][flag].u != -1 && _flowMatrix[i][flag].l < _flowMatrix[i][flag].curr ){
p[i] = -flag ;
#ifdef debug1
cout << "-flag = " << flag << ", i = " << i << endl ;
#endif
}
}
checked[flag] = true ;
}
if ( flag != t ) // do not reach the terminal node
return false ;
a = numeric_limits
int pc = abs(p[t]), c = t ;
float vol ;
#ifdef debug1
for( int i = 0 ; i < num ; ++i )
cout << p[i] << " " ;
cout << endl ;
#endif
while ( c != s ){
#ifdef debug1
cout << c << endl ;
#endif
if ( p[c] < 0 ) {
vol = _flowMatrix[c][pc].curr - _flowMatrix[c][pc].l ;
}
else
vol = _flowMatrix[pc][c].u - _flowMatrix[pc][c].curr ;
a = (a>vol) ? vol : a ;
c = pc ;
pc = abs(p[c]) ;
}
#ifdef debug1
cout << "a = " << a << endl ;
#endif
return true ;
}
void fulkerson( int s, int t, float a, int *p ){
int c = t ;
int pc = abs(p[c]) ;
while ( c != s ){
if ( p[c] < 0 )
_flowMatrix[c][pc].curr -= a ;
else
_flowMatrix[pc][c].curr += a ;
c = pc ;
pc = abs(p[c]) ;
}
return ;
}
void ford_fulkerson( int s, int t, int num ){
float amount ;
int p[MAXNODE] ;
while ( ford( s, t, num, amount, p ) )
fulkerson( s, t, amount, p ) ;
}
public:
Graph() : _isFlowExisted(false){
}
void readGraph(){
cout << "Enter the number of nodes: " ;
cin >> _nodeNum ;
cout << "Enter the start node and end node: " ;
cin >> _s >> _t ;
--_s ; --_t ;
for ( int i = 0 ; i < _nodeNum ; ++i )
for ( int j = 0 ; j < _nodeNum ; ++j )
_matrix[i][j].lower = -1 ;
// input format: edge's start node, end node, lower, upper ;
cout << "Enter the number of edges: " ;
cin >> _edgeNum ;
for ( int i = 0 ; i < _edgeNum ; ++i ){
int s, t ;
cin >> s >> t ;
--s ; --t ;
if ( s < 0 || s >= _nodeNum || t < 0 || t >= _nodeNum ){
cout << "Error! Invalid input data!" << endl ;
exit(1) ;
}
cin >> _matrix[s][t].lower >> _matrix[s][t].upper ;
}
return ;
}
bool isFlowAvailable(){ // judge that whether there is a available flow route;
int tempNodeNum = _nodeNum + 2 ;
for ( int i = 0 ; i < tempNodeNum ; ++i )
for ( int j = 0 ; j < tempNodeNum ; ++j ){
_flowMatrix[i][j].l = 0 ;
_flowMatrix[i][j].u = _newMatrix[i][j] ;
_flowMatrix[i][j].curr = 0 ;
}
ford_fulkerson( _nodeNum, _nodeNum+1, _nodeNum+2 ) ;
bool flag = true ;
for ( int i = 0 ; i < _nodeNum ; ++i )
if ( _flowMatrix[_nodeNum][i].l > 0 && _flowMatrix[_nodeNum][i].u != _flowMatrix[_nodeNum][i].curr ){
flag = false ;
break ;
}
return flag ;
}
void maxFlow(){
if ( !isFlowAvailable() ){
cout << "There is no available flow existed!" << endl ;
return ;
}
graphAdjust2() ;
#ifdef debug1
cout << "In maxFlow().. After adjusting.." << endl ;
for ( int i = 0 ; i < _nodeNum ; ++i )
for ( int j = 0 ; j < _nodeNum ; ++j )
cout << i <<"->" << j <<": " << "base-" << _flowMatrix[i][j].l << ", max-"
<< _flowMatrix[i][j].u << ", curr-" << _flowMatrix[i][j].curr << endl ;
cout << "---------" << endl ;
#endif
ford_fulkerson( _s, _t, _nodeNum ) ;
return ;
}
void minFlow(){ // get the minmum flow
if ( !isFlowAvailable() ){
cout << "There is no available flow existed!" << endl ;
return ;
}
graphAdjust2() ;
ford_fulkerson( _t, _s, _nodeNum ) ;
return ;
}
void printGraph(){
cout << "Start and end node: " ;
cout << _s << " " << _t << endl ;
cout << "Graph edges' info: " << endl ;
for ( int i = 0 ; i < _nodeNum ; ++i )
for ( int j = 0 ; j < _nodeNum ; ++j ){
if ( _matrix[i][j].lower != -1 ){
cout << _matrix[i][j].lower << " " << _matrix[i][j].upper ;
cout << endl ;
}
}
cout << "\nAfter Adjusting..." << endl ;
graphAdjust() ;
#define _matrix _newMatrix
//_nodeNum += 2 ;
cout << "Start and end node: " ;
cout << _nodeNum << " " << _nodeNum+1 << endl ;
cout << "Graph edges' info: " << endl ;
for ( int i = 0 ; i < _nodeNum+2 ; ++i ){
for ( int j = 0 ; j < _nodeNum+2 ; ++j ){
cout << _matrix[i][j] << " " ;
}
cout << endl ;
}
//_nodeNum -= 2 ;
cout << "After Ford-Fulkerson Algorithm..." << endl ;
cout << (isFlowAvailable()? "Yes" : "No") << endl ;
for ( int i = 0 ; i < _nodeNum+2 ; ++i )
for ( int j = 0 ; j < _nodeNum+2 ; ++j )
cout << i <<"->" << j <<": " << "base-" << _flowMatrix[i][j].l << ", max-"
<< _flowMatrix[i][j].u << ", curr-" << _flowMatrix[i][j].curr << endl ;
cout << "---------" << endl ;
/*
cout << "After maxFlow()..." << endl ;
maxFlow() ;
for ( int i = 0 ; i < _nodeNum ; ++i )
for ( int j = 0 ; j < _nodeNum ; ++j )
cout << i <<"->" << j <<": " << "base-" << _flowMatrix[i][j].l << ", max-"
<< _flowMatrix[i][j].u << ", curr-" << _flowMatrix[i][j].curr << endl ;
cout << "---------" << endl ;
*/
cout << "After minFlow()..." << endl ;
minFlow() ;
for ( int i = 0 ; i < _nodeNum ; ++i )
for ( int j = 0 ; j < _nodeNum ; ++j )
cout << i <<"->" << j <<": " << "base-" << _flowMatrix[i][j].l << ", max-"
<< _flowMatrix[i][j].u << ", curr-" << _flowMatrix[i][j].curr << endl ;
cout << "---------" << endl ;
//return ;
return ;
}
} ;
int main( void ){
#ifdef file_io
freopen( "in.txt", "r", stdin ) ;
freopen( "out.txt", "w", stdout ) ;
#endif
Graph g ;
g.readGraph() ;
g.printGraph() ;
#ifdef file_io
fclose( stdin ) ;
fclose( stdout ) ;
#endif
return 0 ;
}
一组测试数据如下：
6
1 6
8
1 2 1 3
1 3 0 10
2 4 5 7
3 5 2 8
4 3 1 3
4 6 3 5
5 2 2 4
5 6 2 6
按上面代码输出如下：
Enter the number of nodes: Enter the start node and end node: Enter the number of edges: Start and end node: 0 5
Graph edges' info:
1 3
0 10
5 7
2 8
1 3
3 5
2 4
2 6
After Adjusting...
Start and end node: 6 7
Graph edges' info:
-1 2 10 -1 -1 3.40282e+038 -1 1
-1 -1 -1 2 -1 -1 -1 5
-1 -1 -1 -1 6 -1 -1 2
-1 -1 2 -1 -1 2 -1 4
-1 2 -1 -1 -1 4 -1 4
3.40282e+038 -1 -1 -1 -1 -1 -1 0
0 3 1 5 2 5 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
After Ford-Fulkerson Algorithm...
Yes
0->0: base-0, max--1, curr-0
0->1: base-0, max-2, curr-2
0->2: base-0, max-10, curr-2
0->3: base-0, max--1, curr-0
0->4: base-0, max--1, curr-0
0->5: base-0, max-3.40282e+038, curr-0
0->6: base-0, max--1, curr-0
0->7: base-0, max-1, curr-1
1->0: base-0, max--1, curr-0
1->1: base-0, max--1, curr-0
1->2: base-0, max--1, curr-0
1->3: base-0, max-2, curr-0
1->4: base-0, max--1, curr-0
1->5: base-0, max--1, curr-0
1->6: base-0, max--1, curr-0
1->7: base-0, max-5, curr-5
2->0: base-0, max--1, curr-0
2->1: base-0, max--1, curr-0
2->2: base-0, max--1, curr-0
2->3: base-0, max--1, curr-0
2->4: base-0, max-6, curr-2
2->5: base-0, max--1, curr-0
2->6: base-0, max--1, curr-0
2->7: base-0, max-2, curr-2
3->0: base-0, max--1, curr-0
3->1: base-0, max--1, curr-0
3->2: base-0, max-2, curr-1
3->3: base-0, max--1, curr-0
3->4: base-0, max--1, curr-0
3->5: base-0, max-2, curr-0
3->6: base-0, max--1, curr-0
3->7: base-0, max-4, curr-4
4->0: base-0, max--1, curr-0
4->1: base-0, max-2, curr-0
4->2: base-0, max--1, curr-0
4->3: base-0, max--1, curr-0
4->4: base-0, max--1, curr-0
4->5: base-0, max-4, curr-0
4->6: base-0, max--1, curr-0
4->7: base-0, max-4, curr-4
5->0: base-0, max-3.40282e+038, curr-5
5->1: base-0, max--1, curr-0
5->2: base-0, max--1, curr-0
5->3: base-0, max--1, curr-0
5->4: base-0, max--1, curr-0
5->5: base-0, max--1, curr-0
5->6: base-0, max--1, curr-0
5->7: base-0, max-0, curr-0
6->0: base-0, max-0, curr-0
6->1: base-0, max-3, curr-3
6->2: base-0, max-1, curr-1
6->3: base-0, max-5, curr-5
6->4: base-0, max-2, curr-2
6->5: base-0, max-5, curr-5
6->6: base-0, max--1, curr-0
6->7: base-0, max--1, curr-0
7->0: base-0, max--1, curr-0
7->1: base-0, max--1, curr-0
7->2: base-0, max--1, curr-0
7->3: base-0, max--1, curr-0
7->4: base-0, max--1, curr-0
7->5: base-0, max--1, curr-0
7->6: base-0, max--1, curr-0
7->7: base-0, max--1, curr-0
---------
After minFlow()...
0->0: base-0, max--1, curr-0
0->1: base-1, max-3, curr-3
0->2: base-0, max-10, curr-2
0->3: base-0, max--1, curr-0
0->4: base-0, max--1, curr-0
0->5: base--1, max--1, curr-0
1->0: base-0, max--1, curr-0
1->1: base-0, max--1, curr-0
1->2: base-0, max--1, curr-0
1->3: base-5, max-7, curr-5
1->4: base-0, max--1, curr-0
1->5: base-0, max--1, curr-0
2->0: base-0, max--1, curr-0
2->1: base-0, max--1, curr-0
2->2: base-0, max--1, curr-0
2->3: base-0, max--1, curr-0
2->4: base-2, max-8, curr-4
2->5: base-0, max--1, curr-0
3->0: base-0, max--1, curr-0
3->1: base-0, max--1, curr-0
3->2: base-1, max-3, curr-2
3->3: base-0, max--1, curr-0
3->4: base-0, max--1, curr-0
3->5: base-3, max-5, curr-3
4->0: base-0, max--1, curr-0
4->1: base-2, max-4, curr-2
4->2: base-0, max--1, curr-0
4->3: base-0, max--1, curr-0
4->4: base-0, max--1, curr-0
4->5: base-2, max-6, curr-2
5->0: base--1, max--1, curr-0
5->1: base-0, max--1, curr-0
5->2: base-0, max--1, curr-0
5->3: base-0, max--1, curr-0
5->4: base-0, max--1, curr-0
5->5: base-0, max--1, curr-0
---------
