// From Lay Networks.com
import java.awt.*;
import java.io.PrintStream;

class GraphCanvas extends Canvas
    implements Runnable
{

    GraphCanvas(BellmanFord bellmanford)
    {
        node = new Point[21];
        weight = new int[21][21];
        arrow = new Point[21][21];
        startp = new Point[21][21];
        endp = new Point[21][21];
        dir_x = new float[21][21];
        dir_y = new float[21][21];
        sucr = new int[21][21];
        distance = new int[21][21];
        pdistance = new int[21][21];
        algedge = new boolean[21][21];
        dist = new int[21];
        finaldist = new int[21];
        colornode = new Color[21];
        changed = new boolean[21];
        numchanged = 0;
        neighbours = 0;
        step = 0;
        numnodes = 0;
        emptyspots = 0;
        startgraph = 0;
        thispoint = new Point(0, 0);
        oldpoint = new Point(0, 0);
        newarrow = false;
        movearrow = false;
        movestart = false;
        deletenode = false;
        movenode = false;
        performalg = false;
        clicked = false;
        roman = new Font("TimesRoman", 1, 12);
        helvetica = new Font("Helvetica", 1, 15);
        fmetrics = getFontMetrics(roman);
        h = fmetrics.getHeight() / 3;
        showstring = new String("");
        showtable = new String("");
        stepthrough = false;
        Locked = false;
        parent = bellmanford;
        init();
        algorithm = 1;
        setBackground(Color.white);
    }

    public void lock()
    {
        Locked = true;
    }

    public void unlock()
    {
        Locked = false;
    }

    public void start()
    {
        if(algrthm != null)
            algrthm.resume();
    }

    public void init()
    {
        for(int i = 0; i < 20; i++)
        {
            colornode[i] = Color.gray;
            for(int j = 0; j < 20; j++)
                algedge[i][j] = false;

        }

        colornode[startgraph] = Color.blue;
        performalg = false;
    }

    public void clear()
    {
        startgraph = 0;
        numnodes = 0;
        emptyspots = 0;
        init();
        for(int i = 0; i < 20; i++)
        {
            node[i] = new Point(0, 0);
            for(int j = 0; j < 20; j++)
                weight[i][j] = 0;

        }

        if(algrthm != null)
            algrthm.stop();
        parent.unlock();
        parent.routeTable.setDefault();
        parent.routeTable.resetAllColor();
        repaint();
    }

    public void reset()
    {
        init();
        if(algrthm != null)
            algrthm.stop();
        parent.unlock();
        for(int i = 0; i < numnodes; i++)
        {
            for(int j = 0; j < numnodes; j++)
            {
                distance[i][j] = weight[i][j];
                sucr[i][j] = j;
                parent.routeTable.setTable(i, j, distance[i][j], sucr[i][j]);
            }

        }

        parent.routeTable.resetAllColor();
        repaint();
    }

    public void runalg()
    {
        parent.lock();
        initalg();
        performalg = true;
        algrthm = new Thread(this);
        algrthm.start();
    }

    public void stepalg()
    {
        parent.lock();
        initalg();
        performalg = true;
        nextstep();
    }

    public void initalg()
    {
        init();
        for(int i = 0; i < 20; i++)
        {
            dist[i] = -1;
            finaldist[i] = -1;
            for(int j = 0; j < 20; j++)
                algedge[i][j] = false;

        }

        dist[startgraph] = 0;
        finaldist[startgraph] = 0;
        step = 0;
    }

    public void nextstep()
    {
        finaldist[minend] = mindist;
        algedge[minstart][minend] = true;
        colornode[minend] = Color.orange;
        step++;
        repaint();
    }

    public void stop()
    {
        if(algrthm != null)
            algrthm.suspend();
    }

    public void run()
    {
        for(int i = 0; i < numnodes - emptyspots; i++)
        {
            nextstep();
            try
            {
                GraphCanvas _tmp = this;
                Thread.sleep(2000L);
            }
            catch(InterruptedException interruptedexception) { }
        }

        algrthm = null;
    }

    public void showexample1()
    {
        clear();
        init();
        numnodes = 7;
        emptyspots = 0;
        for(int k = 0; k < 20; k++)
        {
            node[k] = new Point(0, 0);
            for(int l = 0; l < 20; l++)
                weight[k][l] = 0;

        }

        int i = size().width / 8;
        int j = size().height / 8;
        node[0] = new Point(i, 3 * j);
        node[1] = new Point(3 * i, j);
        node[2] = new Point(5 * i, 3 * j);
        node[3] = new Point(7 * i, 5 * j);
        node[4] = new Point(3 * i, 5 * j);
        node[5] = new Point(i, 7 * j);
        node[6] = new Point(5 * i, 7 * j);
        weight[0][1] = 1;
        weight[0][2] = 1;
        weight[0][4] = 1;
        weight[0][5] = 1;
        weight[1][2] = 1;
        weight[5][3] = 1;
        weight[5][6] = 1;
        weight[3][6] = 1;
        weight[1][0] = 1;
        weight[2][0] = 1;
        weight[4][0] = 1;
        weight[5][0] = 1;
        weight[2][1] = 1;
        weight[3][5] = 1;
        weight[6][5] = 1;
        weight[6][3] = 1;
        parent.routeTable.setDefault();
        for(int i1 = 0; i1 < numnodes; i1++)
        {
            for(int j1 = 0; j1 < numnodes; j1++)
            {
                distance[i1][j1] = weight[i1][j1];
                pdistance[i1][j1] = weight[i1][j1];
                sucr[i1][j1] = j1;
                if(weight[i1][j1] == 0)
                    sucr[i1][j1] = -1;
                parent.routeTable.setTable(i1, j1, distance[i1][j1], sucr[i1][j1]);
            }

        }

        for(int k1 = 0; k1 < numnodes; k1++)
        {
            for(int l1 = 0; l1 < numnodes; l1++)
                if(weight[k1][l1] > 0)
                    arrowupdate(k1, l1, weight[k1][l1]);

        }

        repaint();
    }

    public void showexample2()
    {
        clear();
        init();
        numnodes = 5;
        emptyspots = 0;
        for(int k = 0; k < 20; k++)
        {
            node[k] = new Point(0, 0);
            for(int l = 0; l < 20; l++)
                weight[k][l] = 0;

        }

        int i = size().width / 8;
        int j = size().height / 8;
        node[0] = new Point(i, 5 * j);
        node[1] = new Point(3 * i, 3 * j);
        node[2] = new Point(3 * i, 7 * j);
        node[3] = new Point(7 * i, 3 * j);
        node[4] = new Point(7 * i, 7 * j);
        weight[0][1] = 10;
        weight[0][2] = 10;
        weight[1][3] = 30;
        weight[1][4] = 10;
        weight[2][4] = 10;
        weight[3][4] = 10;
        weight[1][0] = 10;
        weight[2][0] = 10;
        weight[3][1] = 30;
        weight[4][1] = 10;
        weight[4][2] = 10;
        weight[4][3] = 10;
        parent.routeTable.setDefault();
        for(int i1 = 0; i1 < numnodes; i1++)
        {
            for(int j1 = 0; j1 < numnodes; j1++)
            {
                distance[i1][j1] = weight[i1][j1];
                pdistance[i1][j1] = weight[i1][j1];
                sucr[i1][j1] = j1;
                if(weight[i1][j1] == 0)
                    sucr[i1][j1] = -1;
                parent.routeTable.setTable(i1, j1, distance[i1][j1], sucr[i1][j1]);
            }

        }

        for(int k1 = 0; k1 < numnodes; k1++)
        {
            for(int l1 = 0; l1 < numnodes; l1++)
                if(weight[k1][l1] > 0)
                    arrowupdate(k1, l1, weight[k1][l1]);

        }

        repaint();
    }

    public void showexample3()
    {
        clear();
        init();
        numnodes = 6;
        emptyspots = 0;
        for(int k = 0; k < 20; k++)
        {
            node[k] = new Point(0, 0);
            for(int l = 0; l < 20; l++)
                weight[k][l] = 0;

        }

        int i = size().width / 8;
        int j = size().height / 8;
        node[0] = new Point(i, 3 * j);
        node[1] = new Point(3 * i, 5 * j);
        node[2] = new Point(5 * i, 3 * j);
        node[3] = new Point(i, 7 * j);
        node[4] = new Point(5 * i, 7 * j);
        node[5] = new Point(7 * i, 5 * j);
        weight[0][2] = 30;
        weight[2][0] = 30;
        weight[0][3] = 30;
        weight[3][0] = 30;
        weight[1][4] = 20;
        weight[4][1] = 20;
        weight[3][4] = 20;
        weight[4][3] = 20;
        weight[2][4] = 10;
        weight[4][2] = 10;
        weight[2][5] = 60;
        weight[5][2] = 60;
        parent.routeTable.setDefault();
        for(int i1 = 0; i1 < numnodes; i1++)
        {
            for(int j1 = 0; j1 < numnodes; j1++)
            {
                distance[i1][j1] = weight[i1][j1];
                pdistance[i1][j1] = weight[i1][j1];
                sucr[i1][j1] = j1;
                if(weight[i1][j1] == 0)
                    sucr[i1][j1] = -1;
                parent.routeTable.setTable(i1, j1, distance[i1][j1], sucr[i1][j1]);
            }

        }

        for(int k1 = 0; k1 < numnodes; k1++)
        {
            for(int l1 = 0; l1 < numnodes; l1++)
                if(weight[k1][l1] > 0)
                    arrowupdate(k1, l1, weight[k1][l1]);

        }

        repaint();
    }

    public boolean mouseDown(Event event, int i, int j)
    {
        if(Locked)
        {
            parent.documentation.doctext.showline("locked");
        } else
        {
            clicked = true;
            if(event.shiftDown())
            {
                if(nodehit(i, j, 26))
                {
                    oldpoint = node[hitnode];
                    node1 = hitnode;
                    movenode = true;
                }
            } else
            if(event.controlDown())
            {
                if(nodehit(i, j, 26))
                {
                    node1 = hitnode;
                    if(startgraph == node1)
                    {
                        movestart = true;
                        thispoint = new Point(i, j);
                        colornode[startgraph] = Color.gray;
                    } else
                    {
                        deletenode = true;
                    }
                }
            } else
            if(arrowhit(i, j, 5))
            {
                movearrow = true;
                repaint();
            } else
            if(nodehit(i, j, 26))
            {
                if(!newarrow)
                {
                    newarrow = true;
                    thispoint = new Point(i, j);
                    node1 = hitnode;
                }
            } else
            if(!nodehit(i, j, 50) && !arrowhit(i, j, 50))
            {
                if(emptyspots == 0)
                {
                    if(numnodes < 20)
                        node[numnodes++] = new Point(i, j);
                    else
                        parent.documentation.doctext.showline("maxnodes");
                } else
                {
                    int k;
                    for(k = 0; k < numnodes; k++)
                        if(node[k].x == -100)
                            break;

                    node[k] = new Point(i, j);
                    emptyspots--;
                }
            } else
            {
                parent.documentation.doctext.showline("toclose");
            }
            repaint();
        }
        return true;
    }

    public boolean mouseDrag(Event event, int i, int j)
    {
        if(!Locked && clicked)
            if(movenode)
            {
                node[node1] = new Point(i, j);
                for(int k = 0; k < numnodes; k++)
                {
                    if(weight[k][node1] > 0)
                        arrowupdate(k, node1, weight[k][node1]);
                    if(weight[node1][k] > 0)
                        arrowupdate(node1, k, weight[node1][k]);
                }

                repaint();
            } else
            if(movestart || newarrow)
            {
                thispoint = new Point(i, j);
                repaint();
            } else
            if(movearrow)
            {
                changeweight(i, j);
                repaint();
            }
        return true;
    }

    public boolean mouseUp(Event event, int i, int j)
    {
        if(!Locked && clicked)
        {
            if(movenode)
            {
                node[node1] = new Point(0, 0);
                if(nodehit(i, j, 50) || i < 0 || i > size().width || j < 0 || j > size().height)
                {
                    node[node1] = oldpoint;
                    parent.documentation.doctext.showline("toclose");
                } else
                {
                    node[node1] = new Point(i, j);
                }
                for(int k = 0; k < numnodes; k++)
                {
                    if(weight[k][node1] > 0)
                        arrowupdate(k, node1, weight[k][node1]);
                    if(weight[node1][k] > 0)
                        arrowupdate(node1, k, weight[node1][k]);
                }

                movenode = false;
            } else
            if(deletenode)
            {
                nodedelete();
                deletenode = false;
            } else
            if(newarrow)
            {
                newarrow = false;
                if(nodehit(i, j, 26))
                {
                    node2 = hitnode;
                    if(node1 != node2)
                    {
                        arrowupdate(node1, node2, 50);
                        if(weight[node2][node1] > 0)
                            arrowupdate(node2, node1, weight[node2][node1]);
                        parent.documentation.doctext.showline("change weights");
                    } else
                    {
                        System.out.println("zelfde");
                    }
                }
            } else
            if(movearrow)
            {
                movearrow = false;
                if(weight[node1][node2] > 0)
                    changeweight(i, j);
            } else
            if(movestart)
            {
                if(nodehit(i, j, 26))
                    startgraph = hitnode;
                colornode[startgraph] = Color.blue;
                movestart = false;
            }
            repaint();
        }
        return true;
    }

    public boolean nodehit(int i, int j, int k)
    {
        for(int l = 0; l < numnodes; l++)
            if((i - node[l].x) * (i - node[l].x) + (j - node[l].y) * (j - node[l].y) < k * k)
            {
                hitnode = l;
                return true;
            }

        return false;
    }

    public boolean arrowhit(int i, int j, int k)
    {
        for(int l = 0; l < numnodes; l++)
        {
            for(int i1 = 0; i1 < numnodes; i1++)
                if(weight[l][i1] > 0 && Math.pow(i - arrow[l][i1].x, 2D) + Math.pow(j - arrow[l][i1].y, 2D) < Math.pow(k, 2D))
                {
                    node1 = l;
                    node2 = i1;
                    return true;
                }

        }

        return false;
    }

    public void nodedelete()
    {
        node[node1] = new Point(-100, -100);
        for(int i = 0; i < numnodes; i++)
        {
            weight[node1][i] = 0;
            weight[i][node1] = 0;
        }

        emptyspots++;
    }

    public void changeweight(int i, int j)
    {
        int k = (int)(20F * dir_x[node1][node2]);
        int l = (int)(20F * dir_y[node1][node2]);
        boolean flag = false;
        if(Math.abs(endp[node1][node2].x - startp[node1][node2].x) > Math.abs(endp[node1][node2].y - startp[node1][node2].y))
            flag = true;
        if(flag)
        {
            int i1 = Math.max(startp[node1][node2].x, endp[node1][node2].x) - Math.abs(k);
            int k1 = Math.min(startp[node1][node2].x, endp[node1][node2].x) + Math.abs(k);
            if(i < k1)
                arrow[node1][node2].x = k1;
            else
            if(i > i1)
                arrow[node1][node2].x = i1;
            else
                arrow[node1][node2].x = i;
            arrow[node1][node2].y = ((arrow[node1][node2].x - startp[node1][node2].x) * (endp[node1][node2].y - startp[node1][node2].y)) / (endp[node1][node2].x - startp[node1][node2].x) + startp[node1][node2].y;
            weight[node1][node2] = (Math.abs(arrow[node1][node2].x - startp[node1][node2].x - k) * 100) / (i1 - k1);
        } else
        {
            int j1 = Math.max(startp[node1][node2].y, endp[node1][node2].y) - Math.abs(l);
            int l1 = Math.min(startp[node1][node2].y, endp[node1][node2].y) + Math.abs(l);
            if(j < l1)
                arrow[node1][node2].y = l1;
            else
            if(j > j1)
                arrow[node1][node2].y = j1;
            else
                arrow[node1][node2].y = j;
            arrow[node1][node2].x = ((arrow[node1][node2].y - startp[node1][node2].y) * (endp[node1][node2].x - startp[node1][node2].x)) / (endp[node1][node2].y - startp[node1][node2].y) + startp[node1][node2].x;
            weight[node1][node2] = (Math.abs(arrow[node1][node2].y - startp[node1][node2].y - l) * 100) / (j1 - l1);
        }
    }

    public void arrowupdate(int i, int j, int k)
    {
        weight[i][j] = k;
        int l = node[j].x - node[i].x;
        int i1 = node[j].y - node[i].y;
        float f = (float)Math.sqrt((float)(l * l + i1 * i1));
        dir_x[i][j] = (float)l / f;
        dir_y[i][j] = (float)i1 / f;
        if(weight[j][i] > 0)
        {
            startp[i][j] = new Point((int)((float)node[i].x - 5F * dir_y[i][j]), (int)((float)node[i].y + 5F * dir_x[i][j]));
            endp[i][j] = new Point((int)((float)node[j].x - 5F * dir_y[i][j]), (int)((float)node[j].y + 5F * dir_x[i][j]));
        } else
        {
            startp[i][j] = new Point(node[i].x, node[i].y);
            endp[i][j] = new Point(node[j].x, node[j].y);
        }
        int j1 = (int)Math.abs(20F * dir_x[i][j]);
        int k1 = (int)Math.abs(20F * dir_y[i][j]);
        if(startp[i][j].x > endp[i][j].x)
            arrow[i][j] = new Point(endp[i][j].x + j1 + ((Math.abs(endp[i][j].x - startp[i][j].x) - 2 * j1) * (100 - k)) / 100, 0);
        else
            arrow[i][j] = new Point(startp[i][j].x + j1 + ((Math.abs(endp[i][j].x - startp[i][j].x) - 2 * j1) * k) / 100, 0);
        if(startp[i][j].y > endp[i][j].y)
            arrow[i][j].y = endp[i][j].y + k1 + ((Math.abs(endp[i][j].y - startp[i][j].y) - 2 * k1) * (100 - k)) / 100;
        else
            arrow[i][j].y = startp[i][j].y + k1 + ((Math.abs(endp[i][j].y - startp[i][j].y) - 2 * k1) * k) / 100;
    }

    public String intToString(int i)
    {
        char c = (char)(97 + i);
        return "" + c;
    }

    public final synchronized void update(Graphics g)
    {
        Dimension dimension = size();
        if(offScreenImage == null || dimension.width != offScreenSize.width || dimension.height != offScreenSize.height)
        {
            offScreenImage = createImage(dimension.width, dimension.height);
            offScreenSize = dimension;
            offScreenGraphics = offScreenImage.getGraphics();
        }
        offScreenGraphics.setColor(Color.white);
        offScreenGraphics.fillRect(0, 0, dimension.width, dimension.height);
        paint(offScreenGraphics);
        g.drawImage(offScreenImage, 0, 0, null);
    }

    public void drawarrow(Graphics g, int i, int j)
    {
        int k = (int)(((float)arrow[i][j].x - 3F * dir_x[i][j]) + 6F * dir_y[i][j]);
        int l = (int)((float)arrow[i][j].x - 3F * dir_x[i][j] - 6F * dir_y[i][j]);
        int i1 = (int)((float)arrow[i][j].x + 6F * dir_x[i][j]);
        int j1 = (int)((float)arrow[i][j].y - 3F * dir_y[i][j] - 6F * dir_x[i][j]);
        int k1 = (int)(((float)arrow[i][j].y - 3F * dir_y[i][j]) + 6F * dir_x[i][j]);
        int l1 = (int)((float)arrow[i][j].y + 6F * dir_y[i][j]);
        int ai[] = {
            k, l, i1, k
        };
        int ai1[] = {
            j1, k1, l1, j1
        };
        if(algedge[i][j])
        {
            g.setColor(Color.orange);
            for(int i2 = 0; i2 < numnodes; i2++)
            {
                if(i2 != i && j != i2)
                    if(distance[i][i2] == 0 && distance[j][i2] != 0)
                    {
                        distance[i][i2] = distance[i][j] + distance[j][i2];
                        sucr[i][i2] = sucr[i][j];
                        parent.routeTable.setTable(i, i2, distance[i][i2], sucr[i][i2]);
                        if(i == startgraph)
                            parent.routeTable.setColor(i, i2, Color.yellow);
                    } else
                    if(distance[j][i2] == 0 && distance[i][i2] != 0)
                    {
                        distance[j][i2] = distance[j][i] + distance[i][i2];
                        sucr[j][i2] = sucr[j][i];
                        parent.routeTable.setTable(j, i2, distance[j][i2], sucr[j][i2]);
                        if(j == startgraph)
                            parent.routeTable.setColor(j, i2, Color.magenta);
                    } else
                    if(distance[i][i2] != 0 && distance[j][i2] != 0)
                        if(distance[j][i] + distance[i][i2] < distance[j][i2])
                        {
                            distance[j][i2] = distance[j][i] + distance[i][i2];
                            sucr[j][i2] = i;
                            parent.routeTable.setTable(j, i2, distance[j][i2], sucr[j][i2]);
                            if(j == startgraph)
                                parent.routeTable.setColor(j, i2, Color.green);
                        } else
                        if(distance[i][j] + distance[j][i2] < distance[i][i2])
                        {
                            distance[i][i2] = distance[i][j] + distance[j][i2];
                            sucr[i][i2] = j;
                            parent.routeTable.setTable(i, i2, distance[i][i2], sucr[i][i2]);
                            if(i == startgraph)
                                parent.routeTable.setColor(i, i2, Color.cyan);
                        }
                if(colornode[j] == Color.orange && colornode[i2] == Color.red && weight[j][i2] != 0)
                {
                    for(int j2 = 0; j2 < numnodes; j2++)
                        if(colornode[j2] == Color.orange && weight[j2][j] != 0)
                        {
                            distance[j2][i2] = weight[j2][j] + weight[j][i2];
                            sucr[j2][i2] = j;
                            parent.routeTable.setTable(j2, i2, distance[j2][i2], sucr[j2][i2]);
                            if(j2 == startgraph)
                                parent.routeTable.setColor(j2, i2, Color.white);
                        }

                }
                if(colornode[j] == Color.orange && colornode[i2] == Color.red && weight[i2][j] != 0)
                {
                    for(int k2 = 0; k2 < numnodes; k2++)
                        if(colornode[k2] == Color.orange && weight[j][k2] != 0)
                        {
                            distance[i2][k2] = weight[i2][j] + weight[j][k2];
                            sucr[i2][k2] = j;
                            parent.routeTable.setTable(i2, k2, distance[i2][k2], sucr[i2][k2]);
                            if(i2 == startgraph)
                                parent.routeTable.setColor(i2, k2, Color.white);
                        }

                }
                if(colornode[j] == Color.orange && colornode[i2] == Color.gray && weight[j][i2] != 0)
                {
                    for(int l2 = 0; l2 < numnodes; l2++)
                        if(colornode[l2] == Color.red && weight[i2][l2] != 0)
                        {
                            distance[j][l2] = weight[j][i2] + weight[i2][l2];
                            sucr[j][l2] = i2;
                            parent.routeTable.setTable(j, l2, distance[j][l2], sucr[j][l2]);
                            if(j == startgraph)
                                parent.routeTable.setColor(j, l2, Color.gray);
                            for(int k3 = 0; k3 < numnodes; k3++)
                                if(colornode[k3] == Color.orange && weight[k3][l2] != 0)
                                {
                                    distance[i2][k3] = weight[i2][l2] + weight[l2][k3];
                                    sucr[i2][k3] = l2;
                                    parent.routeTable.setTable(i2, k3, distance[i2][k3], sucr[i2][k3]);
                                    if(i2 == startgraph)
                                        parent.routeTable.setColor(i2, k3, Color.pink);
                                }

                        }

                }
                if(colornode[j] == Color.orange && colornode[i2] == Color.gray && weight[i2][j] != 0)
                {
                    for(int i3 = 0; i3 < numnodes; i3++)
                        if(colornode[i3] == Color.red && weight[i3][i2] != 0)
                        {
                            distance[i3][j] = weight[i3][i2] + weight[i2][j];
                            sucr[i3][j] = i2;
                            parent.routeTable.setTable(i3, j, distance[i3][j], sucr[i3][j]);
                            if(i3 == startgraph)
                                parent.routeTable.setColor(i3, j, Color.pink);
                            for(int l3 = 0; l3 < numnodes; l3++)
                                if(colornode[l3] == Color.orange && weight[i3][l3] != 0)
                                {
                                    distance[l3][i2] = weight[l3][i3] + weight[i3][i2];
                                    sucr[l3][i2] = i3;
                                    parent.routeTable.setTable(l3, i2, distance[l3][i2], sucr[l3][i2]);
                                    if(l3 == startgraph)
                                        parent.routeTable.setColor(l3, i2, Color.pink);
                                }

                        }

                }
            }

        }
        g.drawLine(startp[i][j].x, startp[i][j].y, endp[i][j].x, endp[i][j].y);
        g.fillPolygon(ai, ai1, 4);
        int j3 = (int)Math.abs(7F * dir_y[i][j]);
        int i4 = (int)Math.abs(7F * dir_x[i][j]);
        String s = new String("" + weight[i][j]);
        g.setColor(Color.black);
        if(startp[i][j].x > endp[i][j].x && startp[i][j].y >= endp[i][j].y)
            g.drawString(s, arrow[i][j].x + j3, arrow[i][j].y - i4);
        if(startp[i][j].x >= endp[i][j].x && startp[i][j].y < endp[i][j].y)
            g.drawString(s, arrow[i][j].x - fmetrics.stringWidth(s) - j3, arrow[i][j].y - i4);
        if(startp[i][j].x < endp[i][j].x && startp[i][j].y <= endp[i][j].y)
            g.drawString(s, arrow[i][j].x - fmetrics.stringWidth(s), arrow[i][j].y + fmetrics.getHeight());
        if(startp[i][j].x <= endp[i][j].x && startp[i][j].y > endp[i][j].y)
            g.drawString(s, arrow[i][j].x + j3, arrow[i][j].y + fmetrics.getHeight());
    }

    public void detailsBellman(Graphics g, int i, int j)
    {
        if(finaldist[i] != -1 && finaldist[j] == -1)
        {
            g.setColor(Color.red);
            if(i == startgraph)
                parent.routeTable.setColor(i, j, Color.red);
            if(dist[j] == -1 || dist[j] >= dist[i] + weight[i][j])
            {
                if(dist[i] + weight[i][j] < dist[j])
                {
                    changed[j] = true;
                    numchanged++;
                }
                dist[j] = dist[i] + weight[i][j];
                colornode[j] = Color.red;
                if(i != startgraph)
                {
                    parent.routeTable.setTable(startgraph, j, dist[j], i);
                    parent.routeTable.setColor(startgraph, j, Color.yellow);
                    parent.routeTable.setTable(j, startgraph, dist[j], i);
                    distance[startgraph][j] = dist[j];
                    sucr[startgraph][j] = j;
                    distance[j][startgraph] = dist[j];
                    sucr[j][startgraph] = j;
                } else
                if(i == startgraph)
                {
                    parent.routeTable.setTable(startgraph, j, dist[j], j);
                    parent.routeTable.setTable(j, startgraph, dist[j], i);
                    distance[i][j] = dist[j];
                    sucr[i][j] = j;
                    distance[j][i] = dist[j];
                    sucr[j][i] = j;
                }
                if(mindist == 0 || dist[j] < mindist)
                {
                    mindist = dist[j];
                    minstart = i;
                    minend = j;
                }
            }
        } else
        {
            g.setColor(Color.gray);
        }
    }

    public void endstepBellman(Graphics g)
    {
        for(int i = 0; i < numnodes; i++)
            if(node[i].x > 0 && dist[i] != -1)
            {
                String s = new String("" + dist[i]);
                g.drawString(s, node[i].x - fmetrics.stringWidth(s) / 2 - 1, node[i].y + h);
                if(finaldist[i] == -1)
                {
                    neighbours++;
                    if(neighbours != 1)
                        showstring = showstring + ", ";
                    showstring = showstring + intToString(i) + "=" + dist[i];
                }
            }

        showstring = showstring + ". ";
        if(step > 1 && numchanged > 0)
        {
            if(numchanged > 1)
                showstring = showstring + "Notice that the distances to ";
            else
                showstring = showstring + "Notice that the distance to ";
            for(int j = 0; j < numnodes; j++)
                if(changed[j])
                    showstring = showstring + intToString(j) + ", ";

            if(numchanged > 1)
                showstring = showstring + "have changed!\n";
            else
                showstring = showstring + "has changed!\n";
        } else
        {
            showstring = showstring + " ";
        }
        if(neighbours > 1)
        {
            showstring = showstring + "Node " + intToString(minend) + " has the minimum distance.\n";
            int k = 0;
            for(int l = 0; l < numnodes; l++)
                if(node[l].x > 0 && weight[l][minend] > 0 && finaldist[l] == -1)
                    k++;

            if(k > 0)
                showstring = showstring + "Any other path to " + intToString(minend) + " visits another red node, and will be longer than " + mindist + ".\n";
            else
                showstring = showstring + "There are no other arrows coming in to " + intToString(minend) + ".\n";
        } else
        {
            boolean flag = false;
            for(int i1 = 0; i1 < numnodes; i1++)
                if(node[i1].x > 0 && finaldist[i1] == -1 && weight[i1][minend] > 0)
                    flag = true;

            boolean flag1 = false;
            for(int j1 = 0; j1 < numnodes; j1++)
                if(node[j1].x > 0 && finaldist[j1] == -1 && weight[minend][j1] > 0)
                    flag1 = true;

            if(flag && flag1)
                showstring = showstring + "Since this node forms a 'bridge' to " + "the remaining nodes,\nall other paths to this node will be longer.\n";
            else
            if(flag && !flag1)
                showstring = showstring + "Remaining gray nodes are not reachable.\n";
            else
                showstring = showstring + "There are no other arrows coming in to " + intToString(minend) + ".\n";
        }
        showstring = showstring + "Node " + intToString(minend) + " will be colored orange to indicate " + mindist + " is the length of the shortest path to " + intToString(minend) + ".";
        parent.documentation.doctext.showline(showstring);
    }

    public void detailsalg(Graphics g, int i, int j)
    {
        if(algorithm == 1)
            detailsBellman(g, i, j);
    }

    public void endstepalg(Graphics g)
    {
        if(algorithm == 1)
            endstepBellman(g);
        if(performalg && mindist == 0)
        {
            if(algrthm != null)
                algrthm.stop();
            int i = 0;
            for(int j = 0; j < numnodes; j++)
                if(finaldist[j] > 0)
                    i++;

            if(i == 0)
                parent.documentation.doctext.showline("none");
            else
            if(i < numnodes - emptyspots - 1)
                parent.documentation.doctext.showline("some");
            else
                parent.documentation.doctext.showline("done");
        }
    }

    public void paint(Graphics g)
    {
        mindist = 0;
        minnode = 20;
        minstart = 20;
        minend = 20;
        for(int i = 0; i < 20; i++)
            changed[i] = false;

        numchanged = 0;
        neighbours = 0;
        g.setFont(roman);
        g.setColor(Color.black);
        if(step == 1)
            showstring = "Algorithm running: red arrows point to nodes reachable (immeidate neighbour)\nwithin 1 hop from  the inspected node (Blue node).\nThe distance from the start node to: ";
        else
            showstring = "Step " + step + ": Red arrows point to neighbour nodes that reachable from " + "\nneighbour of inspected node that already have a final distance." + "\nThe distance to: ";
        if(newarrow)
            g.drawLine(node[node1].x, node[node1].y, thispoint.x, thispoint.y);
        for(int j = 0; j < numnodes; j++)
        {
            for(int k = 0; k < numnodes; k++)
                if(weight[j][k] > 0)
                {
                    if(performalg)
                        detailsalg(g, j, k);
                    drawarrow(g, j, k);
                }

        }

        if(movearrow && weight[node1][node2] == 0)
        {
            drawarrow(g, node1, node2);
            g.drawLine(startp[node1][node2].x, startp[node1][node2].y, endp[node1][node2].x, endp[node1][node2].y);
        }
        for(int l = 0; l < numnodes; l++)
            if(node[l].x > 0)
            {
                g.setColor(colornode[l]);
                g.fillOval(node[l].x - 13, node[l].y - 13, 26, 26);
            }

        g.setColor(Color.blue);
        if(movestart)
            g.fillOval(thispoint.x - 13, thispoint.y - 13, 26, 26);
        g.setColor(Color.black);
        if(performalg)
            endstepalg(g);
        g.setFont(helvetica);
        for(int i1 = 0; i1 < numnodes; i1++)
            if(node[i1].x > 0)
            {
                g.setColor(Color.black);
                g.drawOval(node[i1].x - 13, node[i1].y - 13, 26, 26);
                g.setColor(Color.blue);
                g.drawString(intToString(i1), node[i1].x - 14, node[i1].y - 14);
            }

    }

    final int MAXNODES = 20;
    final int MAX = 21;
    final int NODESIZE = 26;
    final int NODERADIX = 13;
    final int BELLMAN = 1;
    Point node[];
    int weight[][];
    Point arrow[][];
    Point startp[][];
    Point endp[][];
    float dir_x[][];
    float dir_y[][];
    int sucr[][];
    int distance[][];
    int pdistance[][];
    boolean algedge[][];
    int dist[];
    int finaldist[];
    Color colornode[];
    boolean changed[];
    int numchanged;
    int neighbours;
    int step;
    int mindist;
    int minnode;
    int minstart;
    int minend;
    int numnodes;
    int emptyspots;
    int startgraph;
    int hitnode;
    int node1;
    int node2;
    Point thispoint;
    Point oldpoint;
    boolean newarrow;
    boolean movearrow;
    boolean movestart;
    boolean deletenode;
    boolean movenode;
    boolean performalg;
    boolean clicked;
    Font roman;
    Font helvetica;
    FontMetrics fmetrics;
    int h;
    private Image offScreenImage;
    private Graphics offScreenGraphics;
    private Dimension offScreenSize;
    Thread algrthm;
    int algorithm;
    String showstring;
    String showtable;
    boolean stepthrough;
    boolean Locked;
    BellmanFord parent;
}