Critical node problem: Hello could I get help with this problem? I am having iss
ID: 3833334 • Letter: C
Question
Critical node problem: Hello could I get help with this problem? I am having issues implementing this into java.
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.
Sample input/output: cnp.n cnp. out 7112 12 34 13 14 24 34 35 36 46 56 57 67 123444566677 711123334556Explanation / Answer
boolean[] visited = new boolean[26];
int[] count = new int[26];
Queue<Character> q = new LinkedList<Character>();
q.offer(s);
visited[s - 'A'] = true;
count[s -'A'] = 1;
while(! q.isEmpty())
{
char tmp = q.poll();
for(char x : getAdjacentVertices(tmp))
{
int indics = x - 'A';
if(! visited[indics])
{
q.offer(x);
visited[x - 'A'] = true;
count[indics] = count[ tmp - 'A'] + 1;
}
else
{
count[indics] = count[ tmp - 'A'] + 1;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.