Critical Node Problem: Could someone implement this as a java program with the s
ID: 3834429 • Letter: C
Question
Critical Node Problem:
Could someone implement this as a java program with the specified cnp.in and cnp.out files for me? I'll include the input file :
7 11 2
1 2
1 3
1 4
2 4
3 4
3 5
3 6
4 6
5 6
5 7
6 7
THIS IS WHAT THE INPUT FILE SHOULD LOOK LIKE, just needs to read this in and output to a cnp.out file
Could I please get help with this Critical Node problem?
Thank you
Given an undirected graph G = (V, E), for any subset of nodes S V we can construct a graph GS from G by removing all nodes in S together with their incident edges. In the critical node problem (CNP), we are given an integer 1 k |V | and need to find a subset S of size k such that the graph GS has the minimum pair-wise connectivity. Here pairwise connectivity of a graph is defined as the number of pairs of connected vertices in the graph.
Input: The file “cnp.in” includes multiples lines. The first line contains three integers 1 n 1000, 1 m 100000 and 1 k n that correspond to the number of nodes, edges, and the size of S. Each of the following m lines contain two integers u and v, separated by one space, to denote an edge from u to v. Nodes are numbered from 1 to n.
Output: The file “cnp.out” contains exactly 2 lines. The first line contains an integer P that is the minimum pairwise connectivity of GS. The second line contains exactly k integers which are the id of the nodes in S.
Explain of the output: After removing two nodes 3 and 4 and their incident edges from the graph, we obtain a graph GS with two connected components C1 = {1, 2} and C2 = {5, 6, 7}. The number of connected pairs in the component C1 and C2 are one and three, respectively. Thus the total number of connected pairs (pairwise-connectivity) is 4.
I. Your program in Java/C++ that solves the above problem following the above input/output format. A makefile and/or compiling instruction should be included if you have multiple source files. Your program should not take more than 5 minutes to terminate on any graph within the limits described in the Input section.
II. A report outline the results of your program on random graphs and different k values. The report should have at least two parts. In the first part, you fix k = 5 and run your program for graphs of sizes 50, 100,..., 500. In the second parts, you run your program on a random graph of size 100 and output the pairwise connectivity in GS when k = 5, 10, ..., 50. For each run, output the number of nodes, edges, the number k, and the pairwise connectivity of GS.
Explanation / Answer
#include<iostream>
#include <list>
#define NIL -1
using namespace std;
// A class that represents an undirected graph
class Graph
{
int V; // No. of vertices
list<int> *adj; // A dynamic array of adjacency lists
void bridgeUtil(int v, bool visited[], int disc[], int low[],
int parent[]);
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // to add an edge to graph
void bridge(); // prints all bridges
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v); // Note: the graph is undirected
}
// A recursive function that finds and prints bridges using
// DFS traversal
// u --> The vertex to be visited next
// visited[] --> keeps tract of visited vertices
// disc[] --> Stores discovery times of visited vertices
// parent[] --> Stores parent vertices in DFS tree
void Graph::bridgeUtil(int u, bool visited[], int disc[],
int low[], int parent[])
{
// A static variable is used for simplicity, we can
// avoid use of static variable by passing a pointer.
static int time = 0;
// Mark the current node as visited
visited[u] = true;
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
// Go through all vertices aadjacent to this
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = *i; // v is current adjacent of u
// If v is not visited yet, then recur for it
if (!visited[v])
{
parent[v] = u;
bridgeUtil(v, visited, disc, low, parent);
// Check if the subtree rooted with v has a
// connection to one of the ancestors of u
low[u] = min(low[u], low[v]);
// If the lowest vertex reachable from subtree
// under v is below u in DFS tree, then u-v
// is a bridge
if (low[v] > disc[u])
cout << u <<" " << v << endl;
}
// Update low value of u for parent function calls.
else if (v != parent[u])
low[u] = min(low[u], disc[v]);
}
}
// DFS based function to find all bridges. It uses recursive
// function bridgeUtil()
void Graph::bridge()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
int *disc = new int[V];
int *low = new int[V];
int *parent = new int[V];
// Initialize parent and visited arrays
for (int i = 0; i < V; i++)
{
parent[i] = NIL;
visited[i] = false;
}
// Call the recursive helper function to find Bridges
// in DFS tree rooted with vertex 'i'
for (int i = 0; i < V; i++)
if (visited[i] == false)
bridgeUtil(i, visited, disc, low, parent);
}
// Driver program to test above function
int main()
{
// Create graphs given in above diagrams
cout << " Bridges in first graph ";
Graph g1(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
g1.bridge();
cout << " Bridges in second graph ";
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.bridge();
cout << " Bridges in third graph ";
Graph g3(7);
g3.addEdge(0, 1);
g3.addEdge(1, 2);
g3.addEdge(2, 0);
g3.addEdge(1, 3);
g3.addEdge(1, 4);
g3.addEdge(1, 6);
g3.addEdge(3, 5);
g3.addEdge(4, 5);
g3.bridge();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.