Goals: 1)Understanding of network flow techniques as applied to undirected graph

Question

Goals:

1)Understanding of network flow techniques as applied to undirected graphs.

2)Understanding of minimum cuts, which are particularly easy to obtain from most Ford-Fulkerson code. For push/relabel code you will need to traverse unsaturated edges from the source in the final residual network to determine S.

3)Understanding of cut-trees, a compact representation for cut information regardless of the chosen source and sink. For

small instances, this will be easy to check by inspection.

Requirements:

1. Write a C/C++ program to determine a cut tree for an undirected graph:

The input graph may be treated simply as a symmetric directed graph, i.e. each input edge must be represented in both directions. The provided input graphs are guaranteed to be connected. (If not, then some calls to the network flow routine would have a maxflow of zero.)

In the output cut tree, the smallest capacity on the unique path between vertices s and t gives the capacity of the minimum cut when s and t are used as the source and sink for a network flow algorithm.

You will need maxflow code that allows arbitrary vertices as the source and sink.

2. The input will be formatted as:

The first line will have two values, n and m, giving the numbers of vertices and edges. n will not exceed 3000. m will not exceed 10000.

The next m lines will each contain three integers. The first two, the vertices incident to an edge, will be in the range 0 . . . n - 1. They must be different and the file will not contain parallel edges. The third value will be a positive capacity no larger than 10000. (As an undirected graph, each line corresponds to a pair of symmetric edges.)

The input will be a connected graph.

3. The output from your program should go to standard output, not a file:

The number of output lines will be n - 1.

Each line will have the two vertices incident to an an edge in the computed cut tree, followed by its capacity.

Explanation / Answer

// File Name: CutTreeUndirectedGraph.cpp
#include<iostream>
#include <list>
#define NIL -1
using namespace std;

// Class MyGraph definition
class MyGraph
{
// Private data member for number of vertices
int Ver;
// Pointer array for of adjacency lists
list<int> *adj;
// Function find Bridges in DFS tree rooted with vertex
void cutOpt(int v, bool visited[], int disc[], int low[], int parent[]);
public:
// Parameterized constructor
MyGraph(int V);
// Function to add edges to the graph
void connectEdges(int v, int w);
// Prints the cut trees
void print();
};// End of class

// Definition of parameterized constructor
MyGraph::MyGraph(int V)
{
Ver = V;
// Dynamically allocates memory
adj = new list<int> [V];
}// End of parameterized constructor

// Function to connect edges
void MyGraph::connectEdges(int v, int w)
{
// Creates an adjacency list
adj[v].push_back(w);
adj[w].push_back(v);
}// End of function

// Function find Bridges in DFS tree rooted with vertex
void MyGraph::cutOpt(int u, bool visitedNode[], int discNode[], int lowNode[], int parentNode[])
{
static int times = 0;

// To store the current visited status of a node. Marks the current node to true for visited
visitedNode[u] = true;

// Initialize discovery time and low value
discNode[u] = lowNode[u] = ++times;

// Iterator to go through all vertices adjacent to this
list<int>::iterator it;
for (it = adj[u].begin(); it != adj[u].end(); ++it)
{
// v is current adjacent of u
int v = *it;

// If v is not visited yet, then recur for it
if (!visitedNode[v])
{
parentNode[v] = u;
// Recursively call the function
cutOpt(v, visitedNode, discNode, lowNode, parentNode);

// Check if the subtree rooted with v has a connection to one of the ancestors of u
lowNode[u] = min(lowNode[u], lowNode[v]);

// If the lowest vertex reachable from subtree under v is below u in DFS tree, then u-v is a bridge
if (lowNode[v] > discNode[u])
cout << u << " " << v << endl;
}// End of if condition

// Update low value of u for parent function calls.
else if (v != parentNode[u])
lowNode[u] = min(lowNode[u], discNode[v]);
}// End of for loop
}// End of function

// Function is DFS based, to find all bridges. It calls recursive function cutOpt()
void MyGraph::print()
{
// Mark all the vertices as not visited
bool *visitedNode = new bool[Ver];
int *discNode = new int[Ver];
int *lowNode = new int[Ver];
int *parentNode = new int[Ver];

// Initialize parent and visited arrays
for (int i = 0; i < Ver; i++)
{
parentNode[i] = NIL;
visitedNode[i] = false;
}// End of for loop

// Call the recursive helper function to find Bridges in DFS tree rooted with vertex 'c'
for (int c = 0; c < Ver; c++)
if (visitedNode[c] == false)
// Calls the function to find the cut
cutOpt(c, visitedNode, discNode, lowNode, parentNode);
}// End of function

// Driver program to test above function
int main()
{
// To store number of vertices, number of edges, connection points
int n, m, v1, v2;
// Accepts number of vertices
cout<<" Enter number of vertices (less than 3000)";
cin>>n;
// Accepts number of edges
cout<<" Enter number of edges (less than 10000)";
cin>>m;
// Creates an object of MyGraph using parameterized constructor
MyGraph g1(n);
cout<<" Enter the the vertices incident to an edge: ";
// Loops till number of edges
for(int x = 0; x < m; x++)
{
cout<<" Enter edge "<<(x + 1)<<": ";
// Loops till valid edges connect value
do
{
// Accepts values of edge points
cin>>v1>>v2;
// Checks for negative
if(v1 < 0 || v2 < 0)
cout<<" Cannot be negative. Please re enter.";
// Otherwise checks for greater value than the number of vertices
else if(v1 > n || v2 > n)
cout<<" Cannot exceed number of vertices. Please re enter.";
// Otherwise valid data
else
break;
}while(1); // End of do - while loop
g1.connectEdges(v1, v2);
}// End of for loop
// Create graphs given in above diagrams
cout << " Bridges in first graph ";
// Calls the function to print
g1.print();

return 0;
}// End of main function

Sample Output:

Enter number of vertices (less than 3000)7

Enter number of edges (less than 10000)9

Enter the the vertices incident to an edge:
Enter edge 1: 0 1

Enter edge 2: 1 4

Enter edge 3: 4 5

Enter edge 4: 1 2

Enter edge 5: 3 5

Enter edge 6: 2 0

Enter edge 7: 1 6

Enter edge 8: 1 3

Enter edge 9: 12 6

Cannot exceed number of vertices. Please re enter.1 4

Bridges in first graph
1 6

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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