Can I get some help in creating these methods: void makeBackwardNet() and void b

Question

Can I get some help in creating these methods: void makeBackwardNet() and void backwardReach(). Here is my following code:

// decomposes a directed network into strongly connected components

// Usage: java NS3B outNeighbors-file

import java.io.*;

import java.util.*;

public class NS3B{

int N = 0; // number of vertices/nodes

ArrayList<String> labels = new ArrayList<String>(); // node labels

ArrayList<HashSet<Integer>> outNeighbors = new ArrayList<HashSet<Integer>>();

ArrayList<HashSet<Integer>> inNeighbors = new ArrayList<HashSet<Integer>>();

int[] components = null;  

HashSet<Integer> forward = new HashSet<Integer>();

HashSet<Integer> backward = new HashSet<Integer>();

int numberOfSCCs = 0;

void readNet(String filename){ // fill outNeighbors and N

Scanner in = null;

try {

in = new Scanner(new File(filename));

} catch (FileNotFoundException e){

System.err.println(filename + " not found");

System.exit(1);

}

while (in.hasNextLine()){

String[] terms = in.nextLine().split(" ");

labels.add(terms[0]);

HashSet<Integer> hset = new HashSet<Integer>();

for (int j = 1; j < terms.length; j++) hset.add(Integer.parseInt(terms[j]));

outNeighbors.add(hset);

}

in.close();

N = labels.size();

}

void makeBackwardNet(){ // make inNeighbors from outNeighbors, need your code

for (int i = 0; i < N; i++) inNeighbors.add(new HashSet<Integer>()); // all empty

// your code to fill them

}

void forwardReach(int v){ // all nodes reachable from v

forward.add(v); // the result is in forward

for (int j: outNeighbors.get(v))

if (components[j] < 0 && !forward.contains(j)) forwardReach(j);

}

void backwardReach(int v){ // all nodes that can reach v

backward.add(v); // the result is in backward

// your code to fill the set "backward"

}

void findSCCs(){ // only report those with more than one node

components = new int[N];

for (int i = 0; i < N; i++) components[i] = -1;

forward.clear(); backward.clear();

for (int i = 0; i < N; i++) if (components[i] == -1){

forward.clear(); backward.clear();

forwardReach(i); backwardReach(i);

forward.retainAll(backward); // intersection in forward

int size = forward.size(); // size of the latest SCC

if (size > 1) System.out.println(numberOfSCCs + " " + forward.size());

for (int j: forward) components[j] = numberOfSCCs;

numberOfSCCs++;

}

}

public static void main(String[] args){

if (args.length < 1){ System.err.println("Usage: java NS3B neighbors-file");

return; }

NS3B ns3 = new NS3B();

ns3.readNet(args[0]);  

ns3.makeBackwardNet();

ns3.findSCCs();

}

}

Explanation / Answer

Solution:

Please note below are the following two functions asked. Please note since the format for input is not provided so, the program could not be run.

package aug9;

// decomposes a directed network into strongly connected components

// Usage: java NS3B outNeighbors-file

import java.io.*;

import java.util.*;

public class NS3B{

int N = 0; // number of vertices/nodes

ArrayList<String> labels = new ArrayList<String>(); // node labels

ArrayList<HashSet<Integer>> outNeighbors = new ArrayList<HashSet<Integer>>();

ArrayList<HashSet<Integer>> inNeighbors = new ArrayList<HashSet<Integer>>();

int[] components = null;  

HashSet<Integer> forward = new HashSet<Integer>();

HashSet<Integer> backward = new HashSet<Integer>();

int numberOfSCCs = 0;

void readNet(String filename){ // fill outNeighbors and N

Scanner in = null;

try {

in = new Scanner(new File(filename));

} catch (FileNotFoundException e){

System.err.println(filename + " not found");

System.exit(1);

}

while (in.hasNextLine()){

String[] terms = in.nextLine().split(" ");

labels.add(terms[0]);

HashSet<Integer> hset = new HashSet<Integer>();

for (int j = 1; j < terms.length; j++) hset.add(Integer.parseInt(terms[j]));

outNeighbors.add(hset);

}

in.close();

N = labels.size();

}

void makeBackwardNet(){ // make inNeighbors from outNeighbors, need your code

for (int i = 0; i < N; i++) inNeighbors.add(new HashSet<Integer>()); // all empty

// your code to fill them

for (int i = 0; i < N; i++) inNeighbors.add(outNeighbors.get(i));

}

void forwardReach(int v){ // all nodes reachable from v

forward.add(v); // the result is in forward

for (int j: outNeighbors.get(v))

if (components[j] < 0 && !forward.contains(j)) forwardReach(j);

}

void backwardReach(int v){ // all nodes that can reach v

backward.add(v); // the result is in backward

// your code to fill the set "backward"

for (int i: inNeighbors.get(v))

if (components[i] < 0 && !backward.contains(i)) {

backwardReach(i);

}

}

void findSCCs(){ // only report those with more than one node

components = new int[N];

for (int i = 0; i < N; i++) components[i] = -1;

forward.clear(); backward.clear();

for (int i = 0; i < N; i++) if (components[i] == -1){

forward.clear(); backward.clear();

forwardReach(i); backwardReach(i);

forward.retainAll(backward); // intersection in forward

int size = forward.size(); // size of the latest SCC

if (size > 1) System.out.println(numberOfSCCs + " " + forward.size());

for (int j: forward) components[j] = numberOfSCCs;

numberOfSCCs++;

}

}

public static void main(String[] args){

if (args.length < 1){ System.err.println("Usage: java NS3B neighbors-file");

return; }

NS3B ns3 = new NS3B();

ns3.readNet(args[0]);  

ns3.makeBackwardNet();

ns3.findSCCs();

}

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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