(Test whether a graph is connected) Write a program that reads a graph from a fi

Question

(Test whether a graph is connected) Write a program that reads a graph from a file and determines whether the graph is connected. The first line in the file contains a number that indicates the number of vertices (n). The vertices are labeled as 0, 1, . . . , n-1. Each subsequent line, with the format u v1 v2 . . ., describes edges (u, v1), (u, v2), and so on. Figure 30.21 gives the examples of two files for their corresponding graphs. Figure 30.21 The vertices and edges of a graph can be stored in a file. Your program should prompt the user to enter the name of the file, then it should read data from the file, create an instance g of UnweightedGraph, invoke g.printEdges() to display all edges, and invoke dfs() to obtain an instance tree of AbstractGraph.Tree. If tree.getNumberOfVerticesFound() is the same as the number of vertices in the graph, the graph is connected. Here is a sample run of the program:

Explanation / Answer

A graph consists of vertices and edges that connect vertices. Write a program that reads a graph from a file and displays it on a panel. The first line in the file contains a number that indicates the number of vertices (n). The vertices are labeled as 0, 1, ..., n-1. Each subsequent line, with the format u x y v1, v2, ..., describes that the vertex u is located at position (x, y) with edges (u, v1), (u, v2), etc. Your program prompts the user to enter the name of the file, reads data from the file, and displays the graph on a panel.

Example File:
6
0 30 30 1 2
1 90 30 0 3
2 30 90 0 3 4
3 90 90 1 2 4 5
4 30 150 2 3 5
5 90 150 3 4
Analysis:

A graph is a mathematical structure with vertices and edges that connect the vertices. A graph is a very useful tool for modeling real-world problems. This project is to display the graph. The information for the graph is stored in a file. The number of the vertices n is stored in the first line of the file. The vertices are labeled 0, 1, 2, ..., n-1. The format of each subsequent line is u x y v1, v2, ..., which describes vertex u at location (x, y) and u is connected to vertices v1, v2, etc.

Program:

import java.util.*;
import java.lang.*;
import java.io.*;
import java.awt.Graphics;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Exercise extends JFrame {

    public static void main(String[] args) throws FileNotFoundException {

    Scanner input = new Scanner(System.in);
    System.out.print("Enter a file name: ");
    File file = new File(input.nextLine());

    if (!file.exists())
    {
        System.out.println("File does not exist");
        System.exit(0);
    }

    System.out.print("Enter two vertices (integer indexes): ");
    int vertex1 = input.nextInt();
    int vertex2 = input.nextInt();

    Scanner inFile = new Scanner(file);
    // Read the number of vertices
    String s = inFile.nextLine();
    int numberOfVertices = Integer.parseInt(s);
    System.out.println("The number of vertices is " + numberOfVertices);

    List<WeightedEdge> list = new ArrayList<WeightedEdge>();

    while (inFile.hasNext())
    {
        String [] tokens = null;
        s = inFile.nextLine();
        String[] triplet = s.split("[\|]");
            //this will always overwrite tokens
            //And triplet has 4 positions (0,1,2,3) so you cant just have int u,v and w
            /*
        for (String i : triplet){
            tokens = i.split("[,]");
        }
            */

        int u = Integer.parseInt(tokens[0].trim());
        int v = Integer.parseInt(tokens[1].trim());
        int w = Integer.parseInt(tokens[2].trim());

       }
   }
}

class GraphView extends JPanel {
     private int position;
    private int edge;
    //construct a graphview object
    public GraphView() {
    }
    //construct a graphview object with specified position and edge
    public GraphView(int position, int edge) {
    }
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
       Scanner scan = new Scanner(new File("myFile.txt"));   // scanner to read file
       String line = scan.nextLine();                        // read first line
       int nbLine = Integer.parseInt(line);                  // get number of lines
       ArrayList<int[]> al = new ArrayList<int[]|();       
       for(int i = 0; i < nbLine; i++) {                     // read each line
           line = scan.nextLine();
            String[] token = line.split(" ");                  // split each number into different String
           int[] points = new int[token.length - 1];          // prepare array of int[] - 1
            for(int j = 1; j < token.lenght; j++)              // skip first one
             points[j-1] - Integer.parseInt(token[j]);       // store as int
            al.add(points);                                    // save in ArrayList
       }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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