Question

Check the file: Questions.pdf

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Edge * Graph::Get_Edge(Node* n1, Node* n2)
{
for (int eit = 0; eit < Edges.size(); eit++) // Search trough all nodes
{
if ((Edges[eit]->n1 == n1) && (Edges[eit]->n2 == n2))
{
return Edges[eit];
}
}
return NULL;
}

// Get the node from index
Node * Graph::Get_Node(int s)
{
for (int i = 0; i < Nodes.size(); i++) // Search all nodes for index s
{
if (Nodes[i]->index == s)
{
return Nodes[i];
}
}
return NULL;
}

int Graph::Find_Augmenting_Path()
{
NULLBackedges(); // Set all backedges to NULL
queue<Node*> q; // Create a queue
q.push(Source); // Push source to queue
Source->bestflow = 1000000;// Set the flow to infinity
while (!q.empty()) // While there are elements in queue
{
Node *n = q.front(); // take the first element from queue
q.pop();
for (int i = 0; i < n->adj.size(); i++) // Check all edges of the node
{
Node *dest = n->adj[i]->n2; // Get the node to the edge points
if (dest->backedge == NULL) // Check if the node is already visited
{
Edge *e = Get_Edge(n, dest); // Get the connecting edge
if ((e != NULL) && ((e->capacity - e->residual) > 0)) // Check if there is capacity on the edge
{
dest->backedge = e; // add the edge to the path
dest->bestflow = min(n->bestflow, e->capacity - e->residual); // set the max flow on the path
if (dest == Sink) // check if sink is reached
{
//n->backedgeIndex = n->backedge->n1->index; // store the backedge index for printing
return Sink->bestflow;
}
q.push(dest); // push the destination node to the queue
}
}
}
}
return 0;
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Assisting Tutor

Related Homework Solutions

Big Data (530 words)
Homework Solution
$20.00
Big
Data
Algorithm
Input
Output
Complexity
Technical
Scientific
Theory
Performance
Criteria
Cost
Euclidean
Machine
Learning
Structured
Unstructured
Analytics
Business
Voronoi
NP-Hard
Partition
Clustering
Mean
Get help from a qualified tutor
Live Chats