Read instructions carefully and write the code, please!! Functional Requirements

Question

Read instructions carefully and write the code, please!!

Functional Requirements Write a Java program (based on a graph traversal algorithm you've learned in this class) that, for a given undirected graph, outputs: (i) vertices of each connected component; (ii) a cycle or a message that the graph is acyclic (if there are more than one cycles in a graph, you are required to output just one of them) Your programs should take inputs from a file via the command line with the following structure in the input file. Each line of the input file represents a graph. The first number in a line species the number of vertices in the graph. Then pairs of vertices define the edges An example of an input file is as follows It specifies two graphs. The first graph has five vertices (1,2,3,4,5) and four edges. The second graph has four vertices (1,2,3,4) and three edges. Proper output should look (something) like: Graphl Two connected components: 1 2 3 4 5) Cycle detected: 3-4 -5-3 Graph2 One connected component: [123 4] The graph is acyclic You must test your programs on a nontrivial input file (with at least 3 graphs and each graph having 7-10 nodes). For the second problem, your test graphs should cover both cyclic and acyclic graphs. Your output should be formatted nicely so that it is easy to read Your program should use "good style". See the separate handout on style requirements for CS-203 programs. In particular, note that you should describe the algorithms you implement

Explanation / Answer

// Sample program to find connected components of undirected graph

package com.sanfoundry.graph;

import java.io.BufferedReader;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

class CCGraph

{

static final int MAXV = 100;

static final int MAXDEGREE = 50;

public int edges[][] = new int[MAXV + 1][MAXDEGREE];

public int degree[] = new int[MAXV + 1];

public int nvertices;

public int nedges;

CCGraph()

{

nvertices = nedges = 0;

for (int i = 1; i <= MAXV; i++)

degree[i] = 0;

}

void read_CCGraph(String gline)

{

boolean directed =false;

int x, y;

//Scanner sc = new Scanner(System.in);

//System.out.println("Enter the number of vertices: ");

nvertices = Character.getNumericValue(gline.charAt(0));

// System.out.println("Enter the number of edges: ");

String sub=gline.substring(2, gline.length());

String[] splited = sub.split("\s+");

int m = splited.length;

// System.out.println(nvertices+"---------- "+splited.toString());

for(String dd:splited)

{

x = Character.getNumericValue(dd.charAt(1));

y = Character.getNumericValue(dd.charAt(3));

insert_edge(x, y, true);

//System.out.println(dd);

}

  

//sc.close();

}

void insert_edge(int x, int y, boolean directed)

{

if (degree[x] > MAXDEGREE)

System.out.printf(

"Warning: insertion (%d, %d) exceeds max degree ", x, y);

edges[x][degree[x]] = y;

degree[x]++;

if (!directed)

insert_edge(y, x, true);

else

nedges++;

}

void print_CCGraph()

{

for (int i = 1; i <= nvertices; i++)

{

System.out.printf("%d: ", i);

for (int j = degree[i] - 1; j >= 0; j--)

System.out.printf(" %d", edges[i][j]);

System.out.printf(" ");

}

}

}

public class ConnectedComponents

{

static final int MAXV = 100;

static boolean processed[] = new boolean[MAXV];

static boolean discovered[] = new boolean[MAXV];

static int parent[] = new int[MAXV];

static HashMap<Integer,String> connNodes=new HashMap<Integer,String>();

static HashMap<Integer,Integer> connNodesCount=new HashMap<Integer,Integer>();

static void bfs(int c,CCGraph g, int start)

{

Queue<Integer> q = new LinkedList<Integer>();

int i, v;

q.offer(start);

discovered[start] = true;

while (!q.isEmpty())

{

v = q.remove();

process_vertex(c,v);

processed[v] = true;

for (i = g.degree[v] - 1; i >= 0; i--)

{

if (!discovered[g.edges[v][i]])

{

q.offer(g.edges[v][i]);

discovered[g.edges[v][i]] = true;

parent[g.edges[v][i]] = v;

}

}

}

}

static void initialize_search(CCGraph g)

{

for (int i = 1; i <= g.nvertices; i++)

{

processed[i] = discovered[i] = false;

parent[i] = -1;

}

}

static void process_vertex(int c,int v)

{

//System.out.printf(" %d", v);

String ex=connNodes.get(c);

  

String newEx=ex.concat(v+" ");

connNodes.put(c,newEx);

  

int i=connNodesCount.get(c)+1;

connNodesCount.put(c,i);

  

}

static void connected_components(CCGraph g,String gline)

{

System.out.println(gline);

String sub=gline.substring(2,gline.length());

String[] splited = sub.split("\s+");

int conntected=0;

int c;

initialize_search(g);

c = 0;

  

for (int i = 1; i <= g.nvertices; i++)

{

if (!discovered[i])

{

c++;

connNodes.put(c,"{ ");

connNodesCount.put(c,0);

//System.out.printf("Component %d:", c);

bfs(c,g, i);

String ex=connNodes.get(c);

  

String newEx=ex.concat("}");

connNodes.put(c,newEx);

System.out.print(connNodes.get(c));

if(connNodesCount.get(c)>2)

{

conntected=c;

}

// System.out.printf(" ");

}

}

  

if(conntected==0)

{

System.out.println("The Graph is acyclic");

}

else

{

System.out.println("Cycle Detected");

String ex1=connNodes.get(conntected);

String[] splited1 = ex1.split("\s+");

for(String dd:splited)

{

int a=0,b=0;

if(ex1.indexOf(String.valueOf(dd.charAt(1))) != -1){

a=1;

  

}

if(ex1.indexOf(String.valueOf(dd.charAt(3))) != -1){

b=1;

  

}

if(a==1 && b==1)

{

System.out.println(dd.charAt(1)+"-"+dd.charAt(3));

}

}

}

  

}

static public void main(String[] args) throws IOException

{

FileInputStream fis = null;

BufferedReader reader = null;

CCGraph g = new CCGraph();

int i=0;

if (0 < args.length) {

fis = new FileInputStream(args[0]);

reader = new BufferedReader(new InputStreamReader(fis));

} else {

System.err.println("Invalid arguments count:" + args.length);

System.exit(0);

}

String line = reader.readLine();

while(line != null){

System.out.println("Graph"+ ++i);

//System.out.println("Input "+line);

g.read_CCGraph(line);

connected_components(g,line);

System.out.println(" ");

line = reader.readLine();

//g.print_CCGraph();

  

}  

//  

//   

}

}

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

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