#include <fstream>
#include <ostream.h>
#include <ctime>
#include <stdio.h>
#include <ctype.h>
#include <strings.h>
/*/有用的函数/*/
#define min(x,y) (x)<(y)? (x):(y) ; // retour minimum
#define clrscr() system("cls");
/*/ 基本定义 /*/
typedef int dat_type; // data type pour capacite, flot, ...
//pour bfs
#define WHITE 0 // noeud non visite
#define GRAY 1 // noeud non visite mais attente enligne (dans queue)
#define BLACK 2 // noeud visite
//pour graph entre
int No_of_Node; // nombre des noeud
int No_of_Edge; // nombre des arcs
#ifndef INFINITY
#define INFINITY 0x7fff
#endif
//连接数据 开始
struct link // Structure pour adjacence lien (arcs)
{
dat_type capacity; // lien capacite
dat_type flow; // flot apres chaque fois augmenter
int node_name; // nom fin de lien
struct link *adj; // le prochain arcs
bool flag;
};
struct node_detail // Structure pour noeud
{
int node_name; // nom de noeud
int bfs_status,prev;// utilisation pour bfs, etat du noeud , noeud avant
struct link *adj; // prochain lien
};
typedef struct node_detail Vertex;
// 连接数据 结束\\
/*/ 图的连接接点信息/*/
Vertex *vertices;
/*/ 导入图的创建函数和BFS的队列函数/*/
#include "Queue.cpp" // queue class
#include "graph_lib.cpp"// graph randomisation
/*/函数原形/*/
struct link * find_edge(int from, int to);
int bfs(int start, int target);
double Ford_Fulkerson (int source, int sink);
bool read_input_file(char *filename);
void declare_adj_list();
void remove_adj_list();
int LayeredGraph(int s, int sink);
int Dinic(int v1, int v2);
int UpdatePath(int* S,int n,link **current);
/*/执行函数/*/
/* Find edge [from,to] dans adjacence liste.
- input: from, to noeud
- output: arcs dans le pointer de liste
*/
struct link * find_edge(int from, int to){
struct link *e_temp;
e_temp = vertices[from].adj;
//commence cherche dans lien liste [from,to]
while ((e_temp->node_name !=to) && (e_temp!=NULL))
e_temp = e_temp->adj;
return e_temp;
}
/* Breapth First Search (BFS) Traverser dans residu graphe.
- input: residu graphe. source, recepteur noeud
- output: + sortir path
stocker dans le adjacence liste
+ retour 'true' si trouve objet,sinon false
*/
//第二个问题
int bfs(int start, int target){
int i=1,j=0;
int vnode,v;
struct link *e_temp;
Queue qu; //create queue class
// Remettre tous noeuds en etat non visite
for(i=0;i<No_of_Node;i++)
vertices[i].bfs_status=WHITE;
//Commence traverse
qu.Add_Queue(start);
vertices[start].bfs_status=GRAY;
while(!qu.Queue_Empty()) // si queue vide, on terminer!
{ vnode = qu.Del_Queue();
vertices[vnode].bfs_status=BLACK; //noeud vnode sont visite
// Cherche tous adjacence WHITE noeud v de vnode
e_temp = vertices[vnode].adj;
while(e_temp!=NULL) {
v=e_temp->node_name;
// On just interesser arcs dans le RESIDU graphe a POSITIF RESIDU CAPACITE
//我们只是寻找在残留图中 容量没有满的边
if ( (vertices[v].bfs_status==WHITE) && (e_temp->capacity > e_temp->flow) ){
qu.Add_Queue(v);
vertices[v].bfs_status=GRAY; //noeud est attente dans queue
vertices[v].prev = vnode;
//Petite truc: Si on trouve recepteur, mettre BLACK et arrete
if (v==target){
vertices[target].bfs_status=BLACK;
qu.ClearAll(); //Supprimer Queue sur le memoire
break;
}
}
e_temp = e_temp->adj;
}
}
// Le couleur de final noeud est black, c'est a dire on trouve.
return (vertices[target].bfs_status==BLACK);
}
/* Main EDMONDS-KARP
- input: residu graphe. source, sink noeud
- output: retour Maximum flot
*/
double EDMONDS_KARP (int source, int sink) {
int u;
struct link *e_temp;
double max_flow = 0;
// idee: Si existe un augmenter path, accroitre le flot suivre le path.第三个问题
while (bfs(source,sink)) { //Cherche le plus court chemin
int increment = INFINITY;
u=sink;
while (u!=source){ //aller plus court chemin du sink a source
e_temp = find_edge(vertices[u].prev,u);
increment = min(increment, e_temp->capacity - e_temp->flow);
u = vertices[u].prev;
}
// Accroitre le flot suivre le PCC. 在最短路径上增加原有边的流量 第四个问题
u=sink;
while (u!=source){
e_temp = find_edge(vertices[u].prev,u);
e_temp->flow+= increment;
e_temp = find_edge(u,vertices[u].prev);
e_temp->flow-= increment;
u = vertices[u].prev; //continue jusqu'a source
}
max_flow += double(increment);
}//第五个问题
return max_flow;
}
void remove_adj_list(){
struct link *e_temp;
struct link *next_e;
for(int i=0;i<No_of_Node;i++){
e_temp = vertices[i].adj;
while (e_temp!=NULL){
next_e=e_temp->adj;
if (next_e!=NULL)
delete e_temp;
e_temp = next_e;
}
}
delete e_temp;
delete next_e;
delete vertices;
}
int LayeredGraph(int s,int sink)
{
int M[No_of_Node], S[No_of_Node], h, t, i, v, r;
link *e;
for (i = 0; i < No_of_Node; i++){
e = vertices[i].adj;
while (e != (link *) 0){
e->flag = FALSE;
e = e->adj;
}
M[i] = -1;
}
h = t = 0;
S[0] = s;
M[s] = 0;
while (h >= t){
v = S[t++];
e = vertices[v].adj;
while (e != (link *) 0){
r = e->capacity - e->flow;
if (r > 0){
if (M[e->node_name] == -1){
M[e->node_name] = M[v] + 1;
S[++h] = e->node_name;
e->flag = TRUE;
}
else if (M[e->node_name] == M[v] + 1)
e->flag = TRUE;
}
e = e->adj;
}
}
return M[sink] != -1;
}
int Dinic(int v1,int v2)
{
LayeredGraph(v1, v2);
int done, sp, v, i, S[No_of_Node], flow;
link *current[No_of_Node], *e;
for (i = 0; i < No_of_Node; i++)
current[i] = vertices[i].adj;
flow = 0;
sp = 0;
v = S[0] = v1;
done = FALSE;
while (done == FALSE){
e = current[v];//从起始点第一条边开始
while (e != (link *) 0 && (e->capacity == e->flow || e->flag == FALSE)){
e = current[v] = e->adj;//如果已经饱和
}
if (e == (link *) 0){//如果没有其他边
if (v == v1)
done = TRUE;
else {
v = S[--sp];
current[v] = current[v]->adj;
}
}
else {
S[++sp] = v = e->node_name;//等于边的下一接点
if (v == v2){
flow += UpdatePath(S, sp, current);
v = v1;
sp = 0;
}
}
}
return flow;
}
int UpdatePath(int *S,int n,link **current)
{
link *e;
int i, b;
i = 0;
b = INFINITY;
for (i = 0; i < n; i++){
e = current[S[i]];
b = ((e->capacity - e->flow )< b) ? e->capacity - e->flow : b;
}
for (i = 0; i < n; i++){
e = current[S[i]];
e->flow += b;
e= find_edge(e->node_name,S[i]);
e->flow-= b;
}
return b;
}
int main (int argc, char *argv[]) {
char *filename;
int NO_LOOP;
int maximum_flow=0,flow_dinic=0;
clock_t start,start2, elapsed,elapsed2; //pour temps
struct link *e_temp; //pour remettre flot chaque test
if (argc<4) {
cout << "\t do [N/T] [Fois de Repeter] [Nombre_des_noeuds] [Nombre_des_arcs]\n";
cout << " ----------------\nParametre:\n ----------------\n";
cout << "\tN: Entrez nombre des noeuds et nombre des arcs\n";
cout << "\tT: Entrez nom de fichier\n";
cout << " --------\n Exemple:\n --------\n";
cout << "\t do N 10 100 5000\n";
cout << "\t do T 10 exemple.txt\n\n";
return 0;
}
switch (toupper(*argv[1])){
case 'N':
if (argc!=5) {cout << "\nPas assez des parametre"; return 0;}
NO_LOOP=atoi(argv[2]);
No_of_Node=atoi(argv[3]);
No_of_Edge=atoi(argv[4]);
randomize_input(No_of_Node,No_of_Edge);
break;
case 'T':
NO_LOOP=atoi(argv[2]);
filename = argv[3];
read_input_file(filename);
break;
default:
cout << "Erreur de Entez";
break;
}
start = clock();
int m_size,size_dinic;
for (int m=0;m<NO_LOOP;m++){
//mettre tous les flot a 0
for (int i=0; i<No_of_Node;i++){
e_temp = ve
