// Amin Y. Teymorian
// 26 July 2005

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

//----------------------------------------------------------------------
//
//  GN - a class that defines an applet that has the ability to display
//       G(n) graphs (as described by V. Levenshtein and V. Tonchev)
//       on the screen
//
//----------------------------------------------------------------------

public class GN extends JApplet implements ActionListener
{
    // properties
    private JLabel title = new JLabel("G(n) Graph Generator",SwingConstants.CENTER);
    private JLabel info = new JLabel("n = ",SwingConstants.RIGHT);
    private JTextField field = new JTextField(8);
    private Graph graph = new Graph();

    //
    //  init - a method that does initialization of window
    //

    public void init()
    {
	    // set up window
	    Container window = getContentPane();
	    window.setBackground(Color.white);
	    window.setLayout(new BorderLayout());

	    title.setOpaque(true);
	    title.setForeground(Color.black);

	    graph.setBackground(Color.white);
	    graph.setPreferredSize(new Dimension(420,420));
	
	    JPanel input = new JPanel();
	
	    input.setLayout(new FlowLayout());
	    input.add(info);
	    field.addActionListener(this);
	    input.add(field);
	
	    JPanel display = new JPanel();
	    display.setLayout(new BorderLayout());
	    display.add(input,BorderLayout.NORTH);
    	display.add(graph,BorderLayout.CENTER);
	
	    window.add(title,BorderLayout.NORTH);
    	window.add(display,BorderLayout.CENTER);
	
    } // end of init method

    //
    //  actionPerformed - a method that listens for events
    //

    public void actionPerformed(ActionEvent event)
    {
	    if (event.getSource() == field)
	    {
            try
            {
                int n = Integer.parseInt(field.getText());
                graph.compute(n);
            }
            catch (NumberFormatException e)
            {
                graph.compute(0);
            }
  	    }

    } // end of actionPerformed method

} // end of GN class

//----------------------------------------------------------------------
//
//  Graph - a class that defines a graph object
//
//----------------------------------------------------------------------

class Graph extends JPanel
{
    // properties
    private int nv = 0;
    private int [] pos;
    private int [] edges;
    private double inc;

    private int radius = 4;
    private int scale = 200;
    private int shift = 25;

    private int type = 0;
    private int ec = 0;
    
    //
    //  paintComponent - a method that draws the graph on the screen
    //
    
    public void paintComponent(Graphics g)
    {
	    // call in super class
	    super.paintComponent(g);

	    // draw each vertex w/ label
	    for (int i=0; i<nv; i++)
	    {
	        g.setColor(Color.blue);
	        g.fillOval(pos[2*i]-radius,pos[2*i+1]-radius,2*radius,2*radius);
	        g.setColor(Color.black);
	        g.drawString((i+1)+"",pos[2*i]-4*radius,pos[2*i+1]+4*radius);
	    }

	    // draw each edge from a to b
	    g.setColor(Color.orange);

	    // initialize edge vertices
        int a = 0;
	    int b = 0;
	    
        // draw edges for even n
        if ((type == 0) && (nv != 0))
        {
            for (int i=0; i<ec; i++)
            {
                a = edges[3*i];
                b = edges[3*i+1];

                // is it a self-loop?
	            if (a == b)
	            {
		            // draw loop
		            g.drawOval(pos[2*a-2]-15,pos[2*a-1]-30,30,30);

		            // draw tip
		            int tt = 8;
		            int th = 10;
		            int tl = (int) Math.sqrt(Math.pow(th,2)-Math.pow(tt,2));
		    
		            Polygon tip = new Polygon();
		            tip.addPoint(pos[2*a-2],pos[2*a-1]);
		            tip.addPoint(pos[2*a-2]-tt,pos[2*a-1]-tl);
		            tip.addPoint(pos[2*a-2]-tt,pos[2*a-1]+tl);
		            g.fillPolygon(tip);
	            }

                // it's not a self-loop?
	            else
	            {
                    // when there is no multiplicity
                    if (edges[3*i+2] == 1)
                    {
		                // draw line
		                int p1x = pos[2*a-2];
		                int p1y = pos[2*a-1];
		                int p2x = pos[2*b-2];
		                int p2y = pos[2*b-1];
		                g.drawLine(p1x,p1y,p2x,p2y);
		
		                // draw tip		        
                        double tt = 8.0;
		                double th = 10.0;
		                double tl = Math.sqrt(Math.pow(th,2) - Math.pow(tt,2));
                
                        int dx = p2x - p1x;
		                int dy = p2y - p1y;
		                double d = Math.sqrt(Math.pow(dx,2) + Math.pow(dy,2));
                
		                int o1x = (int)(( (d - tt) / d) * dx - (tl / d) * dy);
		                int o1y = (int)(( (d - tt) / d) * dy + (tl / d) * dx);
		                int o2x = (int)(( (d - tt) / d) * dx + (tl / d) * dy);
		                int o2y = (int)(( (d - tt) / d) * dy - (tl / d) * dx);

		                int p3x = p1x + o1x;
		                int p3y = p1y + o1y;
		                int p4x = p1x + o2x;
		                int p4y = p1y + o2y;
		
		                Polygon tip = new Polygon();
		                tip.addPoint(p2x,p2y);
		                tip.addPoint(p3x,p3y);
		                tip.addPoint(p4x,p4y);
		                g.fillPolygon(tip);
                    }

                    // there is multiplicity
                    else
                    {
                        // get the start point
                        int p1x = pos[2*a-2];
		                int p1y = pos[2*a-1];

                        // get the end point
		                int p2x = pos[2*b-2];
		                int p2y = pos[2*b-1]; 
                        
                        int dx   = p2x - p1x;
		                int dy   = p2y - p1y;
		                double d = Math.sqrt(Math.pow(dx,2) + Math.pow(dy,2));
		        
                        double tt = d/2;
		                double th = tt+2;
		                double tl = Math.sqrt(Math.pow(th,2) - Math.pow(tt,2));

                        int o1x = (int)(( (d - tt) / d) * dx - (tl / d) * dy);
		                int o1y = (int)(( (d - tt) / d) * dy + (tl / d) * dx);
		                int o2x = (int)(( (d - tt) / d) * dx + (tl / d) * dy);
		                int o2y = (int)(( (d - tt) / d) * dy - (tl / d) * dx);
                        
                        // the 1/2 way point to the end point
		                int p3x = p1x + o1x;
		                int p3y = p1y + o1y;

                        // the other 1/2 way point to the end pint
		                int p4x = p1x + o2x;
		                int p4y = p1y + o2y;

                        dx = p2x - p3x;
                        dy = p2y - p3y;
                        d  = Math.sqrt(Math.pow(dx,2) + Math.pow(dy,2));

                        tt = 8.0;
                        th = 10.0;
                        tl = Math.sqrt(Math.pow(th,2) - Math.pow(tt,2));

                        o1x = (int)(( (d - tt) / d) * dx - (tl / d) * dy);
		                o1y = (int)(( (d - tt) / d) * dy + (tl / d) * dx);
		                o2x = (int)(( (d - tt) / d) * dx + (tl / d) * dy);
		                o2y = (int)(( (d - tt) / d) * dy - (tl / d) * dx);
                        
                        // the first set of tip points,
                        // excluding the end point
                        int p5x = p3x + o1x;
		                int p5y = p3y + o1y;
		                int p6x = p3x + o2x;
		                int p6y = p3y + o2y;
                        
                        // line from start to 1/2 way point
                        g.drawLine(p1x,p1y,p3x,p3y);

                        // line from 1/2 way to end point
                        g.drawLine(p3x,p3y,p2x,p2y);
                        
                        // draw the first tip
                        Polygon tip = new Polygon();
		                tip.addPoint(p2x,p2y);
		                tip.addPoint(p5x,p5y);
		                tip.addPoint(p6x,p6y);
		                g.fillPolygon(tip);
                        

                        dx = p2x - p4x;
                        dy = p2y - p4y;
                        d  = Math.sqrt(Math.pow(dx,2) + Math.pow(dy,2));

                        tt = 8.0;   // side a
                        th = 10.0;  // side c
                        tl = Math.sqrt(Math.pow(th,2) - Math.pow(tt,2));

                        o1x = (int)(( (d - tt) / d) * dx - (tl / d) * dy);
		                o1y = (int)(( (d - tt) / d) * dy + (tl / d) * dx);
		                o2x = (int)(( (d - tt) / d) * dx + (tl / d) * dy);
		                o2y = (int)(( (d - tt) / d) * dy - (tl / d) * dx);

                        // the second set of tip points,
                        // excluding the end point
                        int p7x = p4x + o1x;
		                int p7y = p4y + o1y;
		                int p8x = p4x + o2x;
		                int p8y = p4y + o2y;
                        
                        // draw line from start to other 1/2 way point
                        g.drawLine(p1x,p1y,p4x,p4y);

                        // draw line from other 1/2 way point to end point
                        g.drawLine(p4x,p4y,p2x,p2y);
                        
                        // draw the second tip
                        tip = new Polygon();
		                tip.addPoint(p2x,p2y);
		                tip.addPoint(p7x,p7y);
		                tip.addPoint(p8x,p8y);
		                g.fillPolygon(tip);
                    }
	            }          
            }  // end ec loop
        }

        // draw edges for odd n
        else
        {      
	        for (int i=0; i<nv; i++)
	        {
	            a = edges[2*i];
	            b = edges[2*i+1];

                // is it a self-loop?
	            if (a == b)
	            {
		            // draw loop
		            g.drawOval(pos[2*a-2]-15,pos[2*a-1]-30,30,30);

		            // draw tip
		            int tt = 8;
		            int th = 10;
		            int tl = (int) Math.sqrt(Math.pow(th,2)-Math.pow(tt,2));
		    
		            Polygon tip = new Polygon();
		            tip.addPoint(pos[2*a-2],pos[2*a-1]);
		            tip.addPoint(pos[2*a-2]-tt,pos[2*a-1]-tl);
		            tip.addPoint(pos[2*a-2]-tt,pos[2*a-1]+tl);
		            g.fillPolygon(tip);
		
	            }

                // it's not a self-loop?
	            else
	            {	
		            // draw line
		            int p1x = pos[2*a-2];
		            int p1y = pos[2*a-1];
		            int p2x = pos[2*b-2];
		            int p2y = pos[2*b-1];
		            g.drawLine(p1x,p1y,p2x,p2y);
		
		            // draw tip		        
                    double tt = 8.0;
		            double th = 10.0;
		            double tl = Math.sqrt(Math.pow(th,2) - Math.pow(tt,2));
                
                    int dx = p2x - p1x;
		            int dy = p2y - p1y;
		            double d = Math.sqrt(Math.pow(dx,2) + Math.pow(dy,2));
                    
                    // calculate offsets
		            int o1x = (int)(( (d - tt) / d) * dx - (tl / d) * dy);
		            int o1y = (int)(( (d - tt) / d) * dy + (tl / d) * dx);
		            int o2x = (int)(( (d - tt) / d) * dx + (tl / d) * dy);
		            int o2y = (int)(( (d - tt) / d) * dy - (tl / d) * dx);

		            int p3x = p1x + o1x;
		            int p3y = p1y + o1y;
		            int p4x = p1x + o2x;
		            int p4y = p1y + o2y;
		
		            Polygon tip = new Polygon();
		            tip.addPoint(p2x,p2y);
		            tip.addPoint(p3x,p3y);
		            tip.addPoint(p4x,p4y);
		            g.fillPolygon(tip);
	            }
	        }  // end nv loop
        }
    } // end of paintComponent method

    //
    //  compute - method that computes the graph
    //
    public void compute(int n)
    {
        // what type of graph is it?
        type = n%2;
        
        // generate graph for even n
        if ((n > 2) && (type == 0))
        {     
            nv = (n-1)/2;
            pos = new int[2*nv];
            edges = new int[6*nv];
            inc = (2*Math.PI)/nv;

            // initialize multiplicity portion of edges
            for (int i=2; i<(6*nv); i+=3)
            {
                edges[i] = 0;
            }
            
            // generate vertex position
            int offset = 0;
            
            for (int i=0; i<nv; i++)
            {
                pos[2*i] = shift + scale + (int)(scale*Math.cos(offset*inc));
	            pos[2*i+1] = shift + scale - (int)(scale*Math.sin(offset*inc));
                offset++;
            }

            // generate vertex edges
            
            // initialize edge vertices
            int a = 1;
            int b = 1;
            
            // initialize edge count
            ec = 0;

            for (int i=0; i<nv; i++)
            {
                // is it the vertex for the edge that only
                // loops back to itself
                if ((a == n/4) && (n%4 == 0))
                {
                    edges[ec*3]   = a;
                    edges[ec*3+1] = a;
                    edges[ec*3+2] = 1;
                    
                    ec++;
                }
                else
                {
                    // calculate b
                    b = Math.min(2*a,n-2*a);
                        
                    // if edge doesn't already exist
                    if (!edgeCheck(a,b))
                    {
                        edges[ec*3]   = a;
                        edges[ec*3+1] = b;
                        edges[ec*3+2] = 1;
                        ec++;
                    }

                    // calculate b again
                    b = n/2 - a;

                    // if edge doesn't already exist
                    if (!edgeCheck(a,b))
                    {
                        edges[ec*3]   = a;
                        edges[ec*3+1] = b;
                        edges[ec*3+2] = 1;
                        ec++;
                    }
                }
                
                // get the next vertex
                a++;
                
            }  // end of nv loop
        }
        
        // generate graph for odd n
        else if ((n > 2) && (type == 1))
        {
	        nv = (n-1)/2;
	        pos = new int[2*nv];
	        edges = new int[2*nv];
	        inc = (2*Math.PI)/nv;

	        // generate vertex position
	        int offset = 0;
	
	        for (int i=0; i<nv; i++)
	        {
	            pos[2*i] = shift + scale + (int)(scale*Math.cos(offset*inc));
	            pos[2*i+1] = shift + scale - (int)(scale*Math.sin(offset*inc));
                offset++;
	        }
	
	        // generate vertex edges
	        int a = 1;
	
	        for (int i=0; i<nv; i++)
	        {
	            edges[2*i] = a;
	            edges[2*i+1] = Math.min(2*a,n-2*a);
	            a++;
	        }
        }
        
        // don't generate any graph
        else
        {
            nv = 0;
        }

        // draw the graph
	    repaint();
	
    } // end of compute method

    //
    //  edgeCheck - private helper method to see if edge already exists
    //
    
    private boolean edgeCheck(int a, int b)
    {
        for (int i=0; i<ec; i++)
        {
            // if the edge already exists, just increase the
            // multiplicity
            if ((edges[3*i] == a) && (edges[3*i+1] == b))
            {
                edges[3*i+2]+=1;
                return true;
            }
        }

        return false;
    } // end of edgeCheck method

} // end of Graph class