import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.lang.*;
import java.util.*;

public class GraphFrame extends JFrame {
    JPanel contentPane;
    JPanel jPanel1 = new JPanel();
    JTextField FileInput = new JTextField();
    JButton BrowseButton = new JButton();
    JFileChooser Chooser = new JFileChooser();
    JLabel FileInputLabel = new JLabel();
    JButton BiconnButton = new JButton();
    JButton TopSortButton = new JButton();
    JButton ConnButton = new JButton();
    JButton CycleButton = new JButton();
    JLabel QuestionLabel = new JLabel();
    JButton QuitButton = new JButton();
    JScrollPane jScrollPane1 = new JScrollPane();
    JTextArea Display = new JTextArea();
    String GraphType;
    int NumberOfNodes;
    Integer EdgeTo;
    Double Weight;
    LinkedList [] EdgeList;
    LinkedList BackEdges=new LinkedList();
    LinkedList TreeEdges=new LinkedList();
    LinkedList FinishingNums=new LinkedList();
    int [] CutPoints;
    boolean undirected = true;
    boolean cycle = true;
    boolean connected = true;
    boolean browse = false;
    int N;
    int [] dfsNum;
    int [] backNum;
    double w;
    LinkedList MSTEdges=new LinkedList();
    File ChosenFile;

    /**Construct the frame*/
    public GraphFrame() {
	enableEvents(AWTEvent.WINDOW_EVENT_MASK);
	try {
	    jbInit();
	}
	catch(Exception e) {
	    e.printStackTrace();
	}
    }
    /**Component initialization*/
    private void jbInit() throws Exception  {
       	contentPane = (JPanel) this.getContentPane();
	contentPane.setLayout(null);
	this.setResizable(false);
	this.setSize(new Dimension(560, 555));
	this.setTitle("<-Graph Analyzer->");
	jPanel1.setBackground(SystemColor.desktop);
	jPanel1.setBorder(BorderFactory.createEtchedBorder());
	jPanel1.setBounds(new Rectangle(7, 8, 522, 539));
	jPanel1.setLayout(null);
	FileInput.setBackground(Color.white);
    FileInput.setBounds(new Rectangle(300, 298, 200, 24));
    FileInput.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        FileInput_actionPerformed(e);
      }
    });
	BrowseButton.setToolTipText("Click to browse files");
	BrowseButton.setText("Browse");
	BrowseButton.setBounds(new Rectangle(314, 334, 77, 27));
	BrowseButton.addActionListener(new java.awt.event.ActionListener() {
	    public void actionPerformed(ActionEvent e) {
		BrowseButton_actionPerformed(e);
	    }
	});
	FileInputLabel.setForeground(Color.orange);
    FileInputLabel.setText("Enter Filename or Click Browse");
	FileInputLabel.setBounds(new Rectangle(312, 272, 198, 16));
	BiconnButton.setBounds(new Rectangle(340, 182, 122, 28));
	BiconnButton.addActionListener(new java.awt.event.ActionListener() {
	    public void actionPerformed(ActionEvent e) {
		BiconnButton_actionPerformed(e);
	    }
	});
	BiconnButton.setEnabled(false);
    BiconnButton.setToolTipText("Please Choose A File To Analyze");
	BiconnButton.setText("Biconnected?");
	TopSortButton.setEnabled(false);
    TopSortButton.setToolTipText("Please Choose A File To Analyze");
	TopSortButton.setText("Topsort Order?");
	TopSortButton.setBounds(new Rectangle(340, 238, 122, 28));
	TopSortButton.addActionListener(new java.awt.event.ActionListener() {
	    public void actionPerformed(ActionEvent e) {
		TopSortButton_actionPerformed(e);
	    }
	});
	ConnButton.setEnabled(false);
    ConnButton.setToolTipText("Please Choose A File To Analyze");
	ConnButton.setText("Connected?");
	ConnButton.setBounds(new Rectangle(340, 210, 122, 28));
	ConnButton.addActionListener(new java.awt.event.ActionListener() {
	    public void actionPerformed(ActionEvent e) {
		ConnButton_actionPerformed(e);
	    }
	});
	CycleButton.setEnabled(false);
    CycleButton.setToolTipText("Please Choose A File To Analyze");
	CycleButton.setText("Cycle?");
	CycleButton.setBounds(new Rectangle(340, 153, 122, 28));
	CycleButton.addActionListener(new java.awt.event.ActionListener() {
	    public void actionPerformed(ActionEvent e) {
		CycleButton_actionPerformed(e);
	    }
	});
	QuestionLabel.setForeground(Color.orange);
    QuestionLabel.setHorizontalAlignment(SwingConstants.CENTER);
	QuestionLabel.setText("Choose A Question");
	QuestionLabel.setBounds(new Rectangle(337, 107, 122, 47));
	QuitButton.addActionListener(new java.awt.event.ActionListener() {
	    public void actionPerformed(ActionEvent e) {
		QuitButton_actionPerformed(e);
	    }
	});
	QuitButton.setBounds(new Rectangle(393, 334, 77, 27));
	QuitButton.setToolTipText("Exit Program");
	QuitButton.setText("Quit");
	jScrollPane1.setBounds(new Rectangle(12, 10, 273, 497));
	Display.setLineWrap(true);
    Display.setText("Welcome To Graph Analyzer \n");
    Display.append("Please Choose A File To Analyze");
    Display.setLineWrap(false);
    Display.setBackground(Color.white);
    Display.setEditable(false);
    contentPane.add(jPanel1, null);
	jPanel1.add(jScrollPane1, null);
	jPanel1.add(FileInput, null);
	jPanel1.add(BrowseButton, null);
	jPanel1.add(QuitButton, null);
    jPanel1.add(CycleButton, null);
    jPanel1.add(BiconnButton, null);
    jPanel1.add(ConnButton, null);
    jPanel1.add(TopSortButton, null);
    jPanel1.add(FileInputLabel, null);
    jPanel1.add(QuestionLabel, null);
	jScrollPane1.getViewport().add(Display, null);
    }
    /**Overridden so we can exit when window is closed*/
    protected void processWindowEvent(WindowEvent e) {
	super.processWindowEvent(e);
	if (e.getID() == WindowEvent.WINDOW_CLOSING) {
	    System.exit(0);
	}
    }

    void BrowseButton_actionPerformed(ActionEvent e) {

        browse = true;
	GetFile();
    }

     void FileInput_actionPerformed(ActionEvent e) {

        browse = false;
        GetFile();

     }

    void QuitButton_actionPerformed(ActionEvent e) {

	System.exit(1);
    }

    void CycleButton_actionPerformed(ActionEvent e) {

	Display.setText("");
	DFS();
	Display.append("Tree Edges"+"\n");
	for(int i=0;i<TreeEdges.size();i++)

                Display.append(((Vertex)((Edge)TreeEdges.get(i)).getHe()).getNum()+","+((Vertex)((Edge)TreeEdges.get(i)).getShe()).getNum()+"\n");
	Display.append("Back Edges"+"\n");
	for(int n=0;n<BackEdges.size();n++)
	    Display.append(((Vertex)((Edge)BackEdges.get(n)).getHe()).getNum()+","+((Vertex)((Edge)BackEdges.get(n)).getShe()).getNum()+"\n");
	if(BackEdges.size()>0)
	    Display.append("There exists a cycle");
    }
    void BiconnButton_actionPerformed(ActionEvent e) {
	Display.setText("");
        if(undirected==false)
	    Display.append("Please Choose An Undirected Graph \n");
	else{
	    DFS();
	    boolean b = false;
            for(int i=1; i<=NumberOfNodes; i++){
              if(CutPoints[i]==1)
	          b = true;
            }
            if(b==false)
	    Display.append("No cutpoints, Graph is biconnected"+"\n");

            else{
              Display.append("Cutpoints:"+"\n");
              for(int i=1; i<=NumberOfNodes; i++){
              if(CutPoints[i]==1)
                Display.append(i+"\n");
              }
        }
	}
    }

    void ConnButton_actionPerformed(ActionEvent e) {
	Display.setText("");
        DFS();
	for(int i=1;i<=NumberOfNodes;i++){
	    if (dfsNum[i]==0)
		connected=false;
	}
	if(connected==false){
	    Display.append("The graph is unconnected, no MST"+"\n");
	    return;
	}

        if(undirected==false){
	    Display.append("Please Choose An Undirected Graph"+"\n");
            return;
        }

        Display.append("The graph is connected"+"\n");
	MSTEdges.clear();
	Prims();
	Display.append("MST Edges: \n");
	for(int i=0;i<MSTEdges.size();i++)
	    Display.append(((Vertex)((Edge)MSTEdges.get(i)).getHe()).getNum()+","+((Vertex)((Edge)MSTEdges.get(i)).getShe()).getNum()+"\n");
	Double d = new Double(w);
	Display.append("Total Weight: " + d.toString());


    }

    void TopSortButton_actionPerformed(ActionEvent e) {
        Display.setText("");

        DFS();
        if(BackEdges.size()==0)
          cycle = false;
        if((undirected == false)&&(cycle == false)){
          Display.append("Topsort Order: " +"\n");
          int q = FinishingNums.size()-1;
          for(int i=q; i>=0; i--){
            Display.append(((Vertex)FinishingNums.get(i)).getNum() + "\n");
          }
        }
        else{
          Display.append("No TopSort Available For This Graph \n" );
          Display.append("Please Choose another Graph or Button" );
        }
    }

    void DFS(){
	N = 0;
	for(int i=1; i<=NumberOfNodes; i++){
	    if (dfsNum[((Vertex)EdgeList[i].getFirst()).getNum()]==0)
		DFSFrom(((Vertex)EdgeList[i].getFirst()));
	}
    }

    void DFSFrom(Vertex index){

	int [] ParentOf=new int[NumberOfNodes+1];
	for(int i=0;i<=NumberOfNodes;i++)
	    ParentOf[i]=0;
	int [] Stack=new int[NumberOfNodes+1];
	Stack s = new Stack();
	for(int j=0;j<=NumberOfNodes;j++)
	    Stack[j]=0;
	N = N+1;
	int a=1;
        int [] avals = new int [NumberOfNodes+1];
	dfsNum[index.getNum()]=N;
	backNum[index.getNum()]=N;
	Stack[index.getNum()]=1;
	s.push(index);
	while(!s.empty()){

            while(a<EdgeList[((Vertex)s.peek()).getNum()].size()){


                if(dfsNum[(((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a))).getNum()] == 0){
		    Edge x = new Edge((Vertex)s.peek(),((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a)));
		    TreeEdges.add(x);

		    ParentOf[((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a)).getNum()]=((Vertex)s.peek()).getNum();
		    N++;
		    dfsNum[(((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a))).getNum()]=N;
		    backNum[(((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a))).getNum()]=N;


		    Stack[(((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a))).getNum()]=1;
		    avals[((Vertex)s.peek()).getNum()] = a;
                    s.push(((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a)));
		    a=1;
		}

		else{

		    Edge y = new Edge((Vertex)s.peek(),((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a)));
		    if ((ParentOf[((Vertex)s.peek()).getNum()]!=((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a)).getNum())&&Stack[(((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a))).getNum()]==1)
			{

			    BackEdges.add(y);

			    if(dfsNum[((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a)).getNum()]<backNum[((Vertex)s.peek()).getNum()]){

                                int x=dfsNum[((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a)).getNum()];

				backNum[((Vertex)s.peek()).getNum()]=x;
			    }
			}


		    a=a+2;
		}

            }




	    Stack[((Vertex)s.peek()).getNum()]=0;
	    Vertex temp = (Vertex)s.pop();
	    FinishingNums.add(temp);
            if(!s.empty())
		a = avals[((Vertex)s.peek()).getNum()]+2;
            if((!s.empty()) && (((Vertex)s.peek()).getNum() != index.getNum())){
		if(backNum[temp.getNum()]<backNum[((Vertex)s.peek()).getNum()]){
		    int x=backNum[temp.getNum()];
		    backNum[((Vertex)s.peek()).getNum()]=x;
		}
		if(backNum[temp.getNum()]>=dfsNum[((Vertex)s.peek()).getNum()])
		    CutPoints[((Vertex)s.peek()).getNum()]=1;


            }


	}

    }



    void Prims(){
	double [] status=new double[NumberOfNodes+1];
	int [] marked=new int[NumberOfNodes+1];
	int [] parent=new int[NumberOfNodes+1];
	int count=NumberOfNodes-2;
	w = 0;
        double tempweight = Double.MAX_VALUE;
        Vertex tempvertex = new Vertex();
        Vertex tparent = new Vertex();

	Stack s=new Stack();

	for(int i=0;i<=NumberOfNodes;i++)
	    status[i]= Double.MAX_VALUE;
	for(int n=0;n<=NumberOfNodes;n++)
	    marked[n]=0;
	for(int x=0;x<=NumberOfNodes;x++)
	    parent[x]=0;
	marked[((Vertex)EdgeList[1].get(0)).getNum()]=1;
	status[((Vertex)EdgeList[1].get(0)).getNum()]=0;
	s.push(((Vertex)EdgeList[1].get(0)));
	while(count>=0){
	    for(int a=1;a<EdgeList[((Vertex)s.peek()).getNum()].size();a=a+2){

                Vertex u = ((Vertex)s.peek());
                Vertex v = (((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a)));
                Vertex weight = (((Vertex)EdgeList[((Vertex)s.peek()).getNum()].get(a+1)));

                if((marked[v.getNum()]==0) && (weight.getNumD()<status[v.getNum()])){

                        status[v.getNum()] = weight.getNumD();
                        parent[v.getNum()]=u.getNum();

                  if(weight.getNumD() < tempweight){
                    tempweight = weight.getNumD();
                    tparent = u;
                    tempvertex = v;
                  }
                }
                else{
                    for(int i = 1; i<=NumberOfNodes; i++){
                      if(marked[i] == 0 && status[i]<tempweight){
                          tempweight = status[i];
                          tempvertex = ((Vertex)EdgeList[i].getFirst());
                          int x = parent[i];
                          tparent = ((Vertex)EdgeList[x].getFirst());
                      }
                    }
                }
	    }



            Edge x = new Edge(tparent, tempvertex);
            MSTEdges.add(x);
            w = w+tempweight;
	    marked[tempvertex.getNum()] = 1;
            s.push(tempvertex);

            count --;
            tempweight = Double.MAX_VALUE;



	}
    }

    public void ClearAll(){
	BackEdges.clear();
	TreeEdges.clear();
        FinishingNums.clear();


    }

  public void GetFile(){

        ClearAll();
        Display.setText("");

        if(browse==true){
          int result = Chooser.showOpenDialog(null);
	  ChosenFile = Chooser.getSelectedFile();
	  if(result == JFileChooser.APPROVE_OPTION){
	      FileInput.setText(ChosenFile.getName());
              Display.append("Analyzing " +ChosenFile.getAbsolutePath() + "\n");
          }
          if(result == JFileChooser.CANCEL_OPTION){
              DisableButtons();
              Display.setLineWrap(true);
              Display.setText("Welcome To Graph Analyzer \n");
              Display.append("Please Choose A File To Analyze");
              Display.setLineWrap(false);
              return;
          }
        }
        else{

            File tempF = new File(File.separator);
            String path = tempF.getAbsolutePath();
            Display.append("Analyzing " +path + FileInput.getText() + "\n");
            ChosenFile = new File(path + FileInput.getText());
        }
	try{
		EnableButtons();
                FileReader filereader = new FileReader(ChosenFile);
		BufferedReader br = new BufferedReader(filereader);

		GraphType = br.readLine();
		if(GraphType.compareTo("undirected")==0)
		    undirected = true;
		else
		    undirected = false;
		Display.append(GraphType+ "\n");

		String TempIntString = br.readLine();
		NumberOfNodes = Integer.parseInt(TempIntString);
		Display.append(NumberOfNodes + "\n");
		EdgeList = new LinkedList [NumberOfNodes+1];
		CutPoints = new int [NumberOfNodes+1];
                for(int i=0;i<=NumberOfNodes;i++)
		  EdgeList[i]=new LinkedList();

		for(int i=1;i<=NumberOfNodes;i++){
		    Vertex x=new Vertex(i);
		    EdgeList[i].add(x);
		}
		 dfsNum=new int[NumberOfNodes+1];
		 for(int i=0;i<=NumberOfNodes;i++)
		     dfsNum[i]=0;
		 backNum=new int[NumberOfNodes+1];
		 for(int i=0;i<=NumberOfNodes;i++)
		     backNum[i]=0;

		int index;
		int nodeto;
		String instring;
		Vertex v, v1, v2, e1, e2, e3;
		double weight;



		while((instring = br.readLine()) != null){

		    StringTokenizer st = new StringTokenizer(instring);
		    String temp = st.nextToken();
		    index = Integer.parseInt(temp);
		    String temp1 = st.nextToken();
		    nodeto = Integer.parseInt(temp1);
		    String temp2 = st.nextToken();
		    weight = Double.parseDouble(temp2);
		    v= new Vertex(index);
		    v1= new Vertex(nodeto);
		    v2= new Vertex(weight);

		    EdgeList[v.getNum()].add(v1);
		    EdgeList[v.getNum()].add(v2);
		    if(undirected){

			EdgeList[v1.getNum()].add(v);
			EdgeList[v1.getNum()].add(v2);
		    }

		}

		Display.append("Building Adjacency Lists: \n");
                for(int i=1;i<=NumberOfNodes;i++){
		    Display.append(instring);
		    Display.append("Adding: " +((Vertex)EdgeList[i].getFirst()).getNum()
		                  + " , " +((Vertex)EdgeList[i].getLast()).getNumD()+"\n");
		}
		filereader.close();

	    }catch(FileNotFoundException f){
		Display.append(f.getMessage() + "\n");
                Display.append("Please Browse To Choose A File");
                System.err.println(f.getMessage());
                DisableButtons();

	    }catch(IOException io){
		System.err.println(io.getMessage());
                Display.append("Please Browse To Choose A File");
                DisableButtons();
	    }
  }

  public void EnableButtons(){

    BiconnButton.setEnabled(true);
    TopSortButton.setEnabled(true);
    ConnButton.setEnabled(true);
    CycleButton.setEnabled(true);
    BiconnButton.setToolTipText("Is this graph biconnected?");
    TopSortButton.setToolTipText("What is the topsort order of this graph");
    ConnButton.setToolTipText("Is this graph connected?");
    CycleButton.setToolTipText("Does this graph have a cycle?");
  }

  public void DisableButtons(){
    BiconnButton.setEnabled(false);
    TopSortButton.setEnabled(false);
    ConnButton.setEnabled(false);
    CycleButton.setEnabled(false);
    BiconnButton.setToolTipText("Enter Filename or Click Browse");
    TopSortButton.setToolTipText("Enter Filename or Click Browse");
    ConnButton.setToolTipText("Enter Filename or Click Browse");
    CycleButton.setToolTipText("Enter Filename or Click Browse");
  }
}