Write code that finds a maximum flow in a directed graph, using the Ford-Fulkers

Question

Write code that finds a maximum flow in a directed graph, using the Ford-Fulkerson
algorithm on capacities given as matrix
void maximum flow(int n, int s, int t, int *capacity, int *flow)
Your function has the following arguments:
- n: the number of vertices of the graph,
- s: the start vertex,
- t: the target vertex
- capacity: the matrix of edge capacities.
- flow: the matrix used to return the maximum ?ow.
The vertices are numbered from 0 to n-1, so s and t are numbers in that range. ca-
pacity, flow are a pointers to n

Explanation / Answer

int Ford_Fulkelson(Vertex**& neighborMatrix, Node*& list, int source, int terminal, const int& n) { int flowOverall =0 ; int min = 0; do { min = INFINITY; searchAugmentation(neighborMatrix, list, source,terminal,min,n); flowOverall += min; }while(min); return flowOverall; } void searchAugmentation( Vertex**& neighborMatrix, Node*& list, int source, int terminal, int& min, const int& n) { int* ancient; int* color; pListIt Q; ancient = (int*) malloc ((n+1)*sizeof(int)); color = (int*) malloc ((n+1)*sizeof(int)); memset(ancient, 0, (n+1)*sizeof(int) ); memset(color , WHITE , (n+1)*sizeof(int) ); color[source] = GRAY; ancient[source] = 0; Q = NULL; // put source into the queue Q = (pListIt) malloc ( sizeof( ListIt)); Q->value = source; Q->p_next = NULL; int u = 0, v = 0; pListIt at; pListIt endQSe; while(Q) { u = Q->value; for( at = list[u].neighbors; at; at = at->p_next) { v = at->value; if (color[v] == WHITE) { if (neighborMatrix[u][v].capacity != -1 && neighborMatrix[u][v].flowValue p_next;endQSe = endQSe->p_next); // put v into the queue endQSe->p_next = (pListIt) malloc ( sizeof( ListIt)); endQSe->p_next->value = v; endQSe->p_next->p_next = NULL; } else { if (neighborMatrix[v][u].capacity != -1 && neighborMatrix[v][u].flowValue > 0) { color[v] = GRAY; ancient[v] = -u; if (v ==terminal) { improvement(neighborMatrix, terminal,ancient,min); free(ancient); free(color); return; } // find the end of Q for(endQSe = Q; endQSe->p_next;endQSe = endQSe->p_next); // put v into the queue endQSe->p_next = (pListIt) malloc ( sizeof( ListIt)); endQSe->p_next->value = v; endQSe->p_next->p_next = NULL; } } } } //delete first item -> we visited all of its neighbors endQSe = Q; Q = Q->p_next; free(endQSe); color[u] = BLACK; // paint it black } min = 0; // no improvement found, clean and return free(ancient); free(color); } void improvement(Vertex**& adiacentMatrix, int currentVertex, int*& ancient, int& minimal ) { int vertexAt = 0; if (ancient[currentVertex] < 0) { vertexAt = -ancient[currentVertex]; if (minimal > adiacentMatrix[currentVertex][vertexAt].flowValue) { minimal = adiacentMatrix[currentVertex][vertexAt].flowValue; } improvement(adiacentMatrix, vertexAt, ancient, minimal); adiacentMatrix[currentVertex][vertexAt].flowValue -= minimal; } else { if (ancient[currentVertex] > 0 ) { vertexAt = ancient[currentVertex]; if (minimal > (adiacentMatrix[vertexAt][currentVertex].capacity - adiacentMatrix[vertexAt][currentVertex].flowValue )) { minimal = adiacentMatrix[vertexAt][currentVertex].capacity - adiacentMatrix[vertexAt][currentVertex].flowValue; } improvement(adiacentMatrix, vertexAt, ancient, minimal); adiacentMatrix[vertexAt][currentVertex].flowValue += minimal; } } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.