dijkstra.java

Dijkstra algorithm in Java.

/*
 * Dijkstra.java
 *
 * Created on May 31, 2007, 10:51 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package termproject_dijkstra;

/**
 *
 * @author Peto
 */

import java.io.*;
import java.awt.*;


public class Dijkstra 
{
    public Node m_pStart;
     
    /** Creates a new instance of Dijkstra */
    public Dijkstra() {
        m_pStart = null;
    }
 
  
    // Load EdgesList from a file
    // Format: - delimited by 1 space ~ " "
    // NODE EDGE_NODE1 WEIGHT1 EDGE_NODE2 WEIGHT2 ...
    // NODE2...
    // For eache EDGE_NODE there is NODE
    // returns status message
    public String LoadNodes(String sFileName)
    {

        try
        {
            int     i=0,
                    j=0,
                    xBase = GlobalVars.nodeRad,
                    yBase = GlobalVars.nodeRad;
            Node node,nodeNeighbor;
            char c;
            String sLine;
            String sNodeName;
            int iLine=0,              // ith line in file
                iLen,
                iWeight,
                iOffsetStart,       // Node's name start index in the line
                iOffsetEnd;         // Node's name end index in the line
            
            RandomAccessFile in = new RandomAccessFile(sFileName,"r");
       
            // Add dummy node to avoid handling inserting 1 node
            m_pStart = new Node("xxx",GlobalVars.iINFINITY);
                                
            try
            {
                 // Add nodes
                 while (true)        // Breaks on EOF excepion
                {
                    iLine++;
                  
                    sLine = in.readLine() + " ";
                    // EOF ?
                    if(sLine.compareTo("null ")==0)
                        break;
                    
                    iOffsetStart = 0;
                    iOffsetEnd = sLine.indexOf(" ",iOffsetStart+1);
                    
                    if (iOffsetEnd-iOffsetStart<1)
                    {
                        return "Error reading Node at "+iLine+":"+iOffsetStart;
                    }   
                    
                    sNodeName = sLine.substring(iOffsetStart,iOffsetEnd);
                   
                    if ((node = m_pStart.GetNode(sNodeName))==null)
                    {
                        node = new Node(sNodeName,GlobalVars.iINFINITY);
                        node.m_xyPos[0] = xBase + i*GlobalVars.nodeOffset[0] + (j%2)*GlobalVars.nodeOffset[0]/3;
                        node.m_xyPos[1] = yBase + j*GlobalVars.nodeOffset[1];
                        if (j==3)
                            i+=4;
                        j=++j % 4;
                        
                        m_pStart.Push(node);
                        
                    }

                    iLen = sLine.length();
                    //
                    // Add neighbours
                    //
                    while(iOffsetEnd < iLen-1)
                    {
                        // Load up EdgeNode's name
                        iOffsetStart=iOffsetEnd+1;
                        iOffsetEnd = sLine.indexOf(" ",iOffsetStart+1);
                        if (iOffsetEnd-iOffsetStart<1)
                        {
                            return "Error reading EdgeNode at "+iLine+":"+iOffsetStart;
                        }   
                        sNodeName = sLine.substring(iOffsetStart,iOffsetEnd);
                    
                        // Load up Edge's weight
                        iOffsetStart = iOffsetEnd+1;
                        iOffsetEnd = sLine.indexOf(" ",iOffsetStart+1);
                        if (iOffsetEnd-iOffsetStart<1)
                        {
                            return "Error reading Weight at "+iLine+":"+iOffsetStart;
                        }   
                        iWeight = Integer.parseInt(sLine.substring(iOffsetStart,iOffsetEnd));                           
                        
                        // Add node if it hasn't been yet created
                        if ((nodeNeighbor = m_pStart.GetNode(sNodeName))==null)
                        {
                            nodeNeighbor = new Node(sNodeName,GlobalVars.iINFINITY);
                            nodeNeighbor.m_xyPos[0] = xBase + i*GlobalVars.nodeOffset[0] + (j%2)*GlobalVars.nodeOffset[0]/2;
                            nodeNeighbor.m_xyPos[1] = yBase + j*GlobalVars.nodeOffset[1];
                            if (j==3)
                                i+=1;
                            j=++j % 4;
                           
                            m_pStart.Push(nodeNeighbor);
                        }
                        
                        // Add edge
                        node.PushNeighbor(nodeNeighbor,iWeight);
                    }
                }
            }
            catch (IOException e)
            {}
            
            // Remove dummy node
            m_pStart = m_pStart.m_next;         
        }
        catch(FileNotFoundException  e)
        {
            return "File haven't been found: "+sFileName;
        }
        return "Graph loaded";
    }
    
    // Sets all nodes' distance to infinity
    public void SetAllNodesDistToInfinity()
    {
        Node helper = m_pStart;
        
        while (helper != null)
        {
            helper.m_iDist = GlobalVars.iINFINITY;
            helper = helper.m_next;
        }
    
    }
    
    // Updates nodes' '
    public void ShortestPaths(String sStartNode)
    {
       
        // Set all to infinity and start node to 0
        SetAllNodesDistToInfinity();
        Node node = m_pStart.GetNode(sStartNode);
        if (node == null)
        {
            System.out.println("ShortestPaths: starting node wasn't found!");
            return;
        }
        node.m_iDist = 0;
        
        // Fill up priorityqueue
        PriorityQueueNode PQ = new PriorityQueueNode();
        node = m_pStart;
        while(node!=null)
        {
            PQ.Push(node);
            node = node.m_next;            
        }
        
        ResetPaths();
        
        
        PriorityQueueNodeElement elem;
        int iDist1, iDist2, iWeight;
        ListEdgesElement edge;
        ListEdges listEdges;
        // Relax edges
        while(((elem = PQ.Pop())!= null) && elem.m_pNode.m_iDist < GlobalVars.iINFINITY)
        {
            // Each edge
            node = elem.GetNode();
            iDist1 =  node.m_iDist;
            listEdges =  node.m_listNeighbours;
            listEdges.InitTraversing();
           
            while((edge=listEdges.GetAndMove())!=null)
            {
                if (edge.m_pNode.m_iDist > iDist1 + edge.m_iWeight )
                {
                    edge.m_pNode.m_iDist = iDist1 + edge.m_iWeight;
                    edge.m_pNode.m_pathFrom = node;
                    PQ.ReMap(edge.m_pNode);
                }
            }
        }
    }
    
    // Reset found paths to null
    private void ResetPaths()
    {
        Node node = m_pStart;
        
        while (node != null)
        {
            node.m_pathFrom = null;
            node = node.m_next;
        }
    }
    
    public void Draw(Graphics g,float fxInc,float fyInc)
    {
        Node node = m_pStart;
        while(node!=null)
        {
            node.DrawEdges(g,fxInc,fyInc);
            node = node.m_next;
        }
        
        node = m_pStart;
        while(node!=null)
        {
            node.DrawNode(g,fxInc,fyInc);
            node = node.m_next;
        }
        
    
    }
    
    // Pops node from the list
    public Node PopNode(String sNodeName)
    {
        Node prevNode;
        Node curNode=m_pStart;
     
        if (m_pStart != null && (m_pStart.m_sName.compareTo(sNodeName))==0)
        {
            m_pStart = m_pStart.m_next;
        }
        else
        {
            prevNode = curNode;
            curNode = curNode.m_next;
            while(curNode!=null)
            {
                if (curNode.m_sName.compareTo(sNodeName)==0)
                {
                    prevNode.m_next = curNode.m_next;
                    break;              
                }
                prevNode = curNode;
                curNode = curNode.m_next;
            }
        }
        return curNode;
    }
    
}