graph.java

dijkstra algorithm, need complile and building to jar file and run it.

package dijkstra;
import java.awt.Color;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Point;

import static dijkstra.Constants.MAX;
import static dijkstra.Constants.MAXNODES;

public class Graph
{
    // basic graph information
    Point node[] = new Point[ MAX ]; // node

    int weight[][] = new int[ MAX ][ MAX ]; // weight of arrow

    Point arrow[][] = new Point[ MAX ][ MAX ]; // current position of arrowhead

    Point startPoint[][] = new Point[ MAX ][ MAX ]; // start and

    Point endPoint[][] = new Point[ MAX ][ MAX ]; // end point of arrow

    private float dir_x[][] = new float[ MAX ][ MAX ]; // direction of arrow

    private float dir_y[][] = new float[ MAX ][ MAX ]; // direction of arrow

    // graph information while running algorithm

    boolean algorithmEdge[][] = new boolean[ MAX ][ MAX ];

    int dist[] = new int[ MAX ];

    int finalDist[] = new int[ MAX ];

    Color colorNode[] = new Color[ MAX ];

    
    int startgraph = 0; // start of graph

    public void init()
    {
        for( int i = 0; i < MAXNODES; i++ )
        {

            colorNode[ i ] = Color.gray;

            for( int j = 0; j < MAXNODES; j++ )

                algorithmEdge[ i ][ j ] = false;

        }

        colorNode[ startgraph ] = Color.blue;

    }

    public void clear()
    {

        // removes graph from screen

        startgraph = 0;

        init();

        for( int i = 0; i < MAXNODES; i++ )
        {
            node[ i ] = new Point( 0, 0 );
            for( int j = 0; j < MAXNODES; j++ )
                weight[ i ][ j ] = 0;
        }
    }

    public void initAlgorithmGraph()
    {

        for( int i = 0; i < MAXNODES; i++ )
        {

            dist[ i ] = -1;

            finalDist[ i ] = -1;

            for( int j = 0; j < MAXNODES; j++ )

                algorithmEdge[ i ][ j ] = false;

        }

        dist[ startgraph ] = 0;

        finalDist[ startgraph ] = 0;

    }

    public void initSampleData( int w, int h, int numNodes )
    {
        for( int i = 0; i < MAXNODES; i++ )
        {

            node[ i ] = new Point( 0, 0 );

            for( int j = 0; j < MAXNODES; j++ )

                weight[ i ][ j ] = 0;

        }

        node[ 0 ] = new Point( w, h );
        node[ 1 ] = new Point( 3 * w, h );
        node[ 2 ] = new Point( 5 * w, h );

        node[ 3 ] = new Point( w, 4 * h );
        node[ 4 ] = new Point( 3 * w, 4 * h );
        node[ 5 ] = new Point( 5 * w, 4 * h );

        node[ 6 ] = new Point( w, 7 * h );
        node[ 7 ] = new Point( 3 * w, 7 * h );
        node[ 8 ] = new Point( 5 * w, 7 * h );

        node[ 9 ] = new Point( 7 * w, 4 * h );

        weight[ 0 ][ 1 ] = 14;
        weight[ 0 ][ 3 ] = 11;

        weight[ 1 ][ 0 ] = 74;
        weight[ 1 ][ 2 ] = 26;
        weight[ 1 ][ 4 ] = 12;

        weight[ 2 ][ 5 ] = 64;
        weight[ 2 ][ 1 ] = 12;
        weight[ 2 ][ 9 ] = 17;

        weight[ 3 ][ 4 ] = 32;
        weight[ 3 ][ 6 ] = 22;

        weight[ 4 ][ 3 ] = 64;
        weight[ 4 ][ 5 ] = 76;
        weight[ 4 ][ 7 ] = 32;

        weight[ 5 ][ 8 ] = 11;
        weight[ 5 ][ 9 ] = 26;

        weight[ 6 ][ 7 ] = 10;
        weight[ 6 ][ 3 ] = 12;

        weight[ 7 ][ 6 ] = 21;
        weight[ 7 ][ 8 ] = 72;

        weight[ 8 ][ 5 ] = 31;
        weight[ 8 ][ 9 ] = 7;
        weight[ 8 ][ 7 ] = 18;

        weight[ 9 ][ 5 ] = 8;

        for( int i = 0; i < numNodes; i++ )

            for( int j = 0; j < numNodes; j++ )

                if( weight[ i ][ j ] > 0 )

                    arrowUpdate( i, j, weight[ i ][ j ] );

    }

    public void arrowUpdate( int p1, int p2, int w )
    {

        // make a new arrow from node p1 to p2 with weight w, or change

        // the weight of the existing arrow to w, calculate the resulting

        // position of the arrowhead

        int dx, dy;

        float l;

        weight[ p1 ][ p2 ] = w;

        // direction line between p1 and p2

        dx = node[ p2 ].x - node[ p1 ].x;

        dy = node[ p2 ].y - node[ p1 ].y;

        // distance between p1 and p2

        l = (float)(Math.sqrt( (float)(dx * dx + dy * dy) ));

        dir_x[ p1 ][ p2 ] = dx / l;

        dir_y[ p1 ][ p2 ] = dy / l;

        // calculate the start and endpoints of the arrow,

        // adjust startpoints if there also is an arrow from p2 to p1

        if( weight[ p2 ][ p1 ] > 0 )
        {

            startPoint[ p1 ][ p2 ] = new Point( (int)(node[ p1 ].x - 5 * dir_y[ p1 ][ p2 ]),

            (int)(node[ p1 ].y + 5 * dir_x[ p1 ][ p2 ]) );

            endPoint[ p1 ][ p2 ] = new Point( (int)(node[ p2 ].x - 5 * dir_y[ p1 ][ p2 ]),

            (int)(node[ p2 ].y + 5 * dir_x[ p1 ][ p2 ]) );

        }

        else
        {

            startPoint[ p1 ][ p2 ] = new Point( node[ p1 ].x, node[ p1 ].y );

            endPoint[ p1 ][ p2 ] = new Point( node[ p2 ].x, node[ p2 ].y );

        }

        // range for arrowhead is not all the way to the start/endpoints

        int diff_x = (int)(Math.abs( 20 * dir_x[ p1 ][ p2 ] ));

        int diff_y = (int)(Math.abs( 20 * dir_y[ p1 ][ p2 ] ));

        // calculate new x-position arrowhead

        if( startPoint[ p1 ][ p2 ].x > endPoint[ p1 ][ p2 ].x )
        {

            arrow[ p1 ][ p2 ] = new Point( endPoint[ p1 ][ p2 ].x + diff_x +

            (Math.abs( endPoint[ p1 ][ p2 ].x - startPoint[ p1 ][ p2 ].x ) - 2 * diff_x) *

            (100 - w) / 100, 0 );

        }

        else
        {

            arrow[ p1 ][ p2 ] = new Point( startPoint[ p1 ][ p2 ].x + diff_x +

            (Math.abs( endPoint[ p1 ][ p2 ].x - startPoint[ p1 ][ p2 ].x ) - 2 * diff_x) *

            w / 100, 0 );

        }

        // calculate new y-position arrowhead

        if( startPoint[ p1 ][ p2 ].y > endPoint[ p1 ][ p2 ].y )
        {

            arrow[ p1 ][ p2 ].y = endPoint[ p1 ][ p2 ].y + diff_y +

            (Math.abs( endPoint[ p1 ][ p2 ].y - startPoint[ p1 ][ p2 ].y ) - 2 * diff_y) *

            (100 - w) / 100;

        }

        else
        {

            arrow[ p1 ][ p2 ].y = startPoint[ p1 ][ p2 ].y + diff_y +

            (Math.abs( endPoint[ p1 ][ p2 ].y - startPoint[ p1 ][ p2 ].y ) - 2 * diff_y) *

            w / 100;

        }

    }

    public void changeWeight( int x, int y, final int node1, final int node2 )
    {

        // changes the weight of an arrow (edge in the graph), when a user drags

        // the arrowhead over the edge connecting node node1 and node2.

        // direction of the arrow

        int diff_x = (int)(20 * dir_x[ node1 ][ node2 ]);

        int diff_y = (int)(20 * dir_y[ node1 ][ node2 ]);

        // depending on the arrow direction, follow the x, or the y

        // position of the mouse while the arrowhead is being dragged

        boolean follow_x = false;

        if( Math.abs( endPoint[ node1 ][ node2 ].x - startPoint[ node1 ][ node2 ].x ) >

        Math.abs( endPoint[ node1 ][ node2 ].y - startPoint[ node1 ][ node2 ].y ) )
        {

            follow_x = true;

        }

        // find the new position of the arrowhead, and calculate

        // the corresponding weight

        if( follow_x )
        {

            int hbound = Math.max( startPoint[ node1 ][ node2 ].x,

            endPoint[ node1 ][ node2 ].x ) - Math.abs( diff_x );

            int lbound = Math.min( startPoint[ node1 ][ node2 ].x,

            endPoint[ node1 ][ node2 ].x ) + Math.abs( diff_x );

            // arrow must stay between the nodes

            if( x < lbound )
            {
                arrow[ node1 ][ node2 ].x = lbound;
            }

            else if( x > hbound )
            {
                arrow[ node1 ][ node2 ].x = hbound;
            }

            else
                arrow[ node1 ][ node2 ].x = x;

            arrow[ node1 ][ node2 ].y =

            (arrow[ node1 ][ node2 ].x - startPoint[ node1 ][ node2 ].x) *

            (endPoint[ node1 ][ node2 ].y - startPoint[ node1 ][ node2 ].y) /

            (endPoint[ node1 ][ node2 ].x - startPoint[ node1 ][ node2 ].x) +

            startPoint[ node1 ][ node2 ].y;

            // new weight

            weight[ node1 ][ node2 ] =

            Math.abs( arrow[ node1 ][ node2 ].x - startPoint[ node1 ][ node2 ].x - diff_x ) *

            100 / (hbound - lbound);

        }

        // do the same if you follow y

        else
        {

            int hbound = Math.max( startPoint[ node1 ][ node2 ].y,

            endPoint[ node1 ][ node2 ].y ) - Math.abs( diff_y );

            int lbound = Math.min( startPoint[ node1 ][ node2 ].y,

            endPoint[ node1 ][ node2 ].y ) + Math.abs( diff_y );

            if( y < lbound )
            {
                arrow[ node1 ][ node2 ].y = lbound;
            }

            else if( y > hbound )
            {
                arrow[ node1 ][ node2 ].y = hbound;
            }

            else
                arrow[ node1 ][ node2 ].y = y;

            arrow[ node1 ][ node2 ].x =

            (arrow[ node1 ][ node2 ].y - startPoint[ node1 ][ node2 ].y) *

            (endPoint[ node1 ][ node2 ].x - startPoint[ node1 ][ node2 ].x) /

            (endPoint[ node1 ][ node2 ].y - startPoint[ node1 ][ node2 ].y) +

            startPoint[ node1 ][ node2 ].x;

            weight[ node1 ][ node2 ] =

            Math.abs( arrow[ node1 ][ node2 ].y - startPoint[ node1 ][ node2 ].y - diff_y ) *

            100 / (hbound - lbound);

        }

    }

    public void drawArrow( Graphics g, int i, int j, FontMetrics fmetrics )
    {

        // draw arrow between node i and node j

        int x1, x2, x3, y1, y2, y3;

        // calculate arrowhead

        x1 = (int)(arrow[ i ][ j ].x - 3 * dir_x[ i ][ j ] + 6 * dir_y[ i ][ j ]);

        x2 = (int)(arrow[ i ][ j ].x - 3 * dir_x[ i ][ j ] - 6 * dir_y[ i ][ j ]);

        x3 = (int)(arrow[ i ][ j ].x + 6 * dir_x[ i ][ j ]);

        y1 = (int)(arrow[ i ][ j ].y - 3 * dir_y[ i ][ j ] - 6 * dir_x[ i ][ j ]);

        y2 = (int)(arrow[ i ][ j ].y - 3 * dir_y[ i ][ j ] + 6 * dir_x[ i ][ j ]);

        y3 = (int)(arrow[ i ][ j ].y + 6 * dir_y[ i ][ j ]);

        int arrowhead_x[] = { x1, x2, x3, x1 };

        int arrowhead_y[] = { y1, y2, y3, y1 };

        // if edge already chosen by algorithm change color

        //System.out.println("algorithmEdge[ "+i+" ][ "+j+" ]="+algorithmEdge[ i ][ j ]);
        if( algorithmEdge[ i ][ j ] ){
        	//System.out.println("=============== algorithmEdge[ "+i+" ][ "+j+" ]="+algorithmEdge[ i ][ j ]);
            g.setColor( Color.orange );
        }

        // draw arrow

        g.drawLine( startPoint[ i ][ j ].x, startPoint[ i ][ j ].y, endPoint[ i ][ j ].x, endPoint[ i ][ j ].y );

        g.fillPolygon( arrowhead_x, arrowhead_y, 4 );

        // write weight of arrow at an appropriate position

        int dx = (int)(Math.abs( 7 * dir_y[ i ][ j ] ));

        int dy = (int)(Math.abs( 7 * dir_x[ i ][ j ] ));

        String str = new String( "" + weight[ i ][ j ] );

        g.setColor( Color.black );

        if( (startPoint[ i ][ j ].x > endPoint[ i ][ j ].x) && (startPoint[ i ][ j ].y >= endPoint[ i ][ j ].y) )

            g.drawString( str, arrow[ i ][ j ].x + dx, arrow[ i ][ j ].y - dy );

        if( (startPoint[ i ][ j ].x >= endPoint[ i ][ j ].x) && (startPoint[ i ][ j ].y < endPoint[ i ][ j ].y) )

            g.drawString( str, arrow[ i ][ j ].x - fmetrics.stringWidth( str ) - dx,

            arrow[ i ][ j ].y - dy );

        if( (startPoint[ i ][ j ].x < endPoint[ i ][ j ].x) && (startPoint[ i ][ j ].y <= endPoint[ i ][ j ].y) )

            g.drawString( str, arrow[ i ][ j ].x - fmetrics.stringWidth( str ),

            arrow[ i ][ j ].y + fmetrics.getHeight() );

        if( (startPoint[ i ][ j ].x <= endPoint[ i ][ j ].x) && (startPoint[ i ][ j ].y > endPoint[ i ][ j ].y) )

            g.drawString( str, arrow[ i ][ j ].x + dx,

            arrow[ i ][ j ].y + fmetrics.getHeight() );

    }

    public void nodedelete( int node1, int numnodes )
    {

        // delete a node and the arrows coming into/outof the node

        node[ node1 ] = new Point( -100, -100 );

        for( int j = 0; j < numnodes; j++ )
        {

            weight[ node1 ][ j ] = 0;

            weight[ j ][ node1 ] = 0;

        }

    }

    /**
     * move node and adjust arrows coming into/outof the node
     * 
     * @param node1
     * @param numnodes
     * @param x
     * @param y
     */
    public void adjustArrow( int node1, int numnodes, int x, int y )
    {
        node[ node1 ] = new Point( x, y );

        for( int i = 0; i < numnodes; i++ )
        {

            if( weight[ i ][ node1 ] > 0 )
            {

                arrowUpdate( i, node1, weight[ i ][ node1 ] );

            }

            if( weight[ node1 ][ i ] > 0 )
            {

                arrowUpdate( node1, i, weight[ node1 ][ i ] );

            }

        }
    }

}