import DataStructures.*;
import Supporting.*;
import Exceptions.*;
import java.util.StringTokenizer;
import Supporting.Comparable;
import java.io.*;

// Graph class interface: evaluate shortest paths
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS**********************
// void addEdges( String source, String dest, int cost )
//                      --> Add additional edge
// boolean processRequest( BufferedReader in )
//                      --> Run a bunch of shortest path algs
// ******************ERRORS*********************************
// Some error checking is performed to make sure graph is ok,
// parameters to processRequest represent vertices in the graph,
// and to make sure graph satisfies properties needed by each algorithm

/**
 * This class represents the basic
 * item in the adjacency list.
 */
class Edge
{
                      // First vertex in edge is implicit
    public int dest;  // Second vertex in edge
    public int cost;  // Edge cost

    public Edge( int d, int c )
    {
        dest = d;
        cost = c;
    }
}


/**
 * This class represents the basic item
 * stored for each vertex.
 */
class Vertex
{
    String name;   // The real name
    List   adj;    // The adjacency list

    int dist;      // Cost (after running algorithm)
    int prev;      // Previous vertex on shortest path
    int scratch;   // Extra variable for use in algorithm

    Vertex( String nm )
    {
        name = nm;                // Share name in hash table
        adj  = new LinkedList( ); // Make a new list
    }
}


/**
 * This class represents the basic entry
 * in the vertex dictionary.
 * It implements the Hashable interface by providing
 * hash and equals.
 */
class HashItem implements Hashable
{
    public String name;   /* The real name */
    public int    rank;   /* The assigned number */

    public HashItem( )
    {
        this( null );
    }

    public HashItem( String nm )
    {
        name = nm;
    }

    public int hash( int tableSize )
    {
        return ProbingHashTable.hash( name, tableSize );
    }

    public boolean equals( Object rhs )
    {
        return name.equals( ((HashItem) rhs).name );
    }
}


/**
 * Object stored in the priority queue
 * for Dijkstra's algorithm
 */
class Path implements Comparable
{
    int dest;    // W
    int cost;    // D(W)

    static Path negInf = new Path( );  // Sentinel

    Path( )
    {
        this( 0 );
    }

    Path( int d )
    {
        this( d, 0 );
    }

    Path( int d, int c )
    {
        dest = d;
        cost = c;
    }

    public boolean lessThan( Comparable rhs )
    {
        return cost < ( (Path) rhs ).cost;
    }

    public int compares( Comparable rhs )
    {
        return cost < ( (Path) rhs ).cost ? -1 :
               cost > ( (Path) rhs ).cost ? 1 : 0;
    }
}

/**
 * Graph class: evaluate shortest paths.
 */
public class Graph
{
    public Graph( )
    {
        numVertices = 0;
        table       = new Vertex[ INIT_TABLE_SIZE ];
        vertexMap   = new QuadraticProbingTable( );
    }

    /**
     * Add the edge ( source, dest, cost ) to the graph.
     */
    public void addEdge( String source, String dest, int cost )
    {
        addInternalEdge( addNode( source ), addNode( dest ), cost );
    }

    /**
     * Process a request; return false if end of file.
     */
    public boolean processRequest( BufferedReader in )
    {
        String sourceName, destName;
        HashItem source = new HashItem( );
        HashItem dest   = new HashItem( );

        try
        {
            System.out.println( "Enter start node:" );
            if( ( sourceName = in.readLine( ) ) == null )
                return false;
            System.out.println( "Enter destination node:" );
            if( ( destName = in.readLine( ) ) == null )
                return false;
        }
        catch( IOException e )
        {
            System.out.println( "Error: " + e  );
            return false;
        }

        try
        {
            source.name = sourceName;
            source = (HashItem) ( vertexMap.find( source ) );
            dest.name = destName;
            dest = (HashItem) ( vertexMap.find( dest ) );

            unweighted( source.rank );
            printPath( dest.rank );

            if( dijkstra( source.rank ) )
                printPath( dest.rank );
            else
                System.out.println( "Dijkstra fails - neg edge" );

            if( dijkstraPair( source.rank ) )
                printPath( dest.rank );
            else
                System.out.println( "Dijkstra fails - neg edge" );

            if( negative( source.rank ) )
                printPath( dest.rank );
            else
                System.out.println( "Negative fails - neg cycle" );

            if( acyclic( source.rank ) )
                printPath( dest.rank );
            else
                System.out.println( "Acyclic fails - cycle" );
        }
        catch( ItemNotFound e )
          { System.err.println( "Vertex not in graph" ); }
        return true;
    }

    /**
     * A main routine that:
     * 1. Prompts for a file containing edges;
     * 2. Forms the graph;
     * 3. Repeatedly prompts for two vertices and
     *    runs shortest path algorithms.
     * The data file is a sequence of lines of the format
     *    source destination cost.
     */
    public static void main( String [ ] args )
    {
            // Get the file
        System.out.println( "Enter graph file:" );
        BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
        FileReader fin;
        String fileName= "";

        try
        {
            fileName = in.readLine( );
            fin = new FileReader( fileName );
        }
        catch( Exception e )
        {
            System.err.println( e );
            return;
        }


        BufferedReader graphFile = new BufferedReader( fin );
        Graph g = new Graph( );

            // Read the edges and insert
        try
        {
            String line;
            while( ( line = graphFile.readLine( ) ) != null )
            {
                StringTokenizer st = new StringTokenizer( line );

                try
                {
                    if( st.countTokens( ) != 3 )
                        throw new Exception( );
                    String source  = st.nextToken( );
                    String dest    = st.nextToken( );
                    int cost = Integer.parseInt( st.nextToken( ) );
                    g.addEdge( source, dest, cost );
                }
                catch( Exception e )
                  { System.err.println( "Error: " + line ); }
             }
         }
         catch( Exception e )
           { System.err.println( "Error: " + e ); }

         while( g.processRequest( in ) )
             ;
    }

    private static final int INIT_TABLE_SIZE = 50;
    private static final int NULL_VERTEX     = -1;
    private static final int INFINITY        = 2147483647 / 3;

    private HashTable vertexMap;    // Gets internal #
    private Vertex [ ] table;       // The table array
    private int       numVertices;  // Current # vertices read

    /**
     * Double the table array; usual stuff.
     */
    private void doubleTableArray( )
    {
        Vertex[ ] oldArray = table;
        table = new Vertex[ oldArray.length * 2 ];
        for( int i = 0; i < oldArray.length; i++ )
            table[ i ] = oldArray[ i ];
    }

    /**
     * If vertexName is an already seen vertex, return its
     * internal number. Otherwise add it as a new vertex,
     * and return its new internal number.
     */
    private int addNode( String vertexName )
    {
        HashItem hashV = new HashItem( vertexName );
        HashItem result;

        try
        {
            result = (HashItem) vertexMap.find( hashV );
            return result.rank;
        }
        catch( ItemNotFound e )
        {
            // Newly seen vertex
            hashV.rank = numVertices;
            hashV.name = new String( vertexName );
            vertexMap.insert( hashV );

            if( numVertices == table.length )
                doubleTableArray( );
            table[ numVertices ] = new Vertex( hashV.name );
            return numVertices++;
        }
    }

    /**
     * Add an edge given internal numbers of its vertices.
     */
    private void addInternalEdge( int source, int dest, int cost )
    {
        ListItr p = new LinkedListItr( table[ source ].adj );
        try
          { p.insert( new Edge( dest, cost ) ); }
        catch( ItemNotFound e ) { }   // Cannot happen
    }

    /**
     * Initialize the table.
     */
    private void clearData( )
    {
        for( int i = 0; i < numVertices; i++ )
        {
            table[ i ].dist = INFINITY;
            table[ i ].prev = NULL_VERTEX;
            table[ i ].scratch = 0;
        }
    }

    /**
     * Recursively print the shortest path to DestNode
     * (specified by its internal number)
     * printPath is the driver routine
     */
    private void printPathRec( int destNode )
    {
        if( table[ destNode ].prev != NULL_VERTEX )
        {
            printPathRec( table[ destNode ].prev );
            System.out.print( " to " );
        }
        System.out.print( table[ destNode ].name );
    }

    /**
     * Driver routine to handle unreachables and print total
     * cost. It calls recursive routine to print shortest path
     * to destNode after a shortest path algorithm has run.
     */
    private void printPath( int destNode )
    {
        if( table[ destNode ].dist == INFINITY )
            System.out.println( table[ destNode ].name +
                                " is unreachable" );
        else
        {
            printPathRec( destNode );
            System.out.println( " (cost is " +
                                table[ destNode ].dist + ")" );
        }
        System.out.println( );
    }


        // Various shortest path algorithms that
        // require an internal number for start-up

    /**
     * Compute the unweighted shortest path.
     */
    private void unweighted( int startNode )
    {
        int v, w;
        Queue q = new QueueAr( );

        clearData( );
        table[ startNode ].dist = 0;
        q.enqueue( new Integer( startNode ) );

        try
        {
            while( !q.isEmpty( ) )
            {
                v = ( (Integer) q.dequeue( ) ).intValue( );
                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    if( table[ w ].dist == INFINITY )
                    {
                        table[ w ].dist = table[ v ].dist + 1;
                        table[ w ].prev = v;
                        q.enqueue( new Integer( w ) );
                    }
                }
            }
        }
        catch( Underflow e ) { }   // Cannot happen
    }

    /**
     * Dijkstra's Algorithm using binary heap.
     * Return false if negative edge detected.
     */
    private boolean dijkstra( int startNode )
    {
        int v, w;
        PriorityQueue pq = new BinaryHeap( Path.negInf );
        Path vrec;

        clearData( );
        table[ startNode ].dist = 0;
        pq.insert( new Path( startNode, 0 ) );

        try
        {
            for( int nodesSeen = 0; nodesSeen < numVertices; nodesSeen++ )
            {
                do
                {
                    if( pq.isEmpty( ) )
                        return true;
                    vrec = (Path) pq.deleteMin( );
                } while( table[ vrec.dest ].scratch != 0 );

                v = vrec.dest;
                table[ v ].scratch = 1;

                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    int cvw = ( (Edge) p.retrieve( ) ).cost;

                    if( cvw < 0 )
                        return false;

                    if( table[ w ].dist > table[ v ].dist + cvw )
                    {
                        table[ w ].dist = table[ v ].dist + cvw;
                        table[ w ].prev = v;
                        pq.insert( new Path( w, table[ w ].dist ) );
                    }
                }
            }
        }
        catch( Underflow e ) { }   // This cannot happen

        return true;
    }

    /**
     * Dijkstra's Algorithm using pairing heap
     * Return false if negative edges detected.
     */
    private boolean dijkstraPair( int startNode )
    {
        int v, w;
        PairHeap pq = new PairHeap( );
        Path vrec;
        PairNode [ ] heapPositions = new PairNode[ numVertices ];

        clearData( );
        for( int i = 0; i < numVertices; i++ )
            heapPositions[ i ] = null;

        table[ startNode ].dist = 0;
        pq.insert( new Path( startNode, 0 ) );

        try
        {
            while( !pq.isEmpty( ) )
            {
                vrec = (Path) pq.deleteMin( );
                v = vrec.dest;

                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    int cvw = ( (Edge) p.retrieve( ) ).cost;

                    if( cvw < 0 )
                        return false;

                    if( table[ w ].dist > table[ v ].dist + cvw )
                    {
                        table[ w ].dist = table[ v ].dist + cvw;
                        table[ w ].prev = v;

                        Path newVal = new Path( w, table[ w ].dist );
                        if( heapPositions[ w ] == null )
                            heapPositions[ w ] = pq.addItem( newVal );
                        else
                            pq.decreaseKey( heapPositions[ w ], newVal );
                    }
                }
            }
        }
        catch( Exception e ) { }   // This cannot happen 

        return true;
    }

    /**
     * Run shortest path algorithm;
     * Negative edge weights are allowed.
     * Return false if negative cycle is detected
     */
    private boolean negative( int startNode )
    {
        int v, w;
        Queue q = new QueueAr( );
        int cvw;

        clearData( );
        table[ startNode ].dist = 0;
        q.enqueue( new Integer( startNode ) );
        table[ startNode ].scratch++;

        try
        {
            while( !q.isEmpty( ) )
            {
                v = ( (Integer) q.dequeue( ) ).intValue( );

                if( table[ v ].scratch++ > 2 * numVertices )
                    return false;

                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    cvw = ( (Edge) p.retrieve( ) ).cost;
                    if( table[ w ].dist > table[ v ].dist + cvw )
                    {
                        table[ w ].dist = table[ v ].dist + cvw;
                        table[ w ].prev = v;

                        // Enqueue only if not already on queue
                        if( table[ w ].scratch++ % 2 == 0 )
                            q.enqueue( new Integer( w ) );
                        else
                            table[ w ].scratch--;
                    }
                }
            }
        }
        catch( Underflow e ) { }   // Cannot happen

        return true;
    }


    /**
     * Run shortest path algorithm;
     * Linear-time algorithm, works only for acyclic graphs.
     * Return false if cycle is detected
     */
    private boolean acyclic( int startNode )
    {
        int v, w, iterations = 0;
        Queue q = new QueueAr( );

        clearData( );
        table[ startNode ].dist = 0;

        try
        {
            // Compute the indegrees
            for( v = 0; v < numVertices; v++ )
            {
                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                    table[ ( (Edge) p.retrieve( ) ).dest ].scratch++;
            }

            // Enqueue vertices of indegree zero
            for( v = 0; v < numVertices; v++ )
                if( table[ v ].scratch == 0 )
                    q.enqueue( new Integer( v ) );

            for( iterations = 0; !q.isEmpty( ); iterations++ )
            {
                v = ( (Integer) q.dequeue( ) ).intValue( );

                ListItr p = new LinkedListItr( table[ v ].adj );
                for( ; p.isInList( ); p.advance( ) )
                {
                    w = ( (Edge) p.retrieve( ) ).dest;
                    if( --table[ w ].scratch == 0 )
                        q.enqueue( new Integer( w ) );

                    if( table[ v ].dist == INFINITY )
                        continue;

                    int cvw = ( (Edge) p.retrieve( ) ).cost;
                    if( table[ w ].dist > table[ v ].dist + cvw )
                    {
                        table[ w ].dist = table[ v ].dist + cvw;
                        table[ w ].prev = v;
                    }
                }
            }
        }
        catch( Underflow e ) { }    // Cannot happen

        return iterations == numVertices;
    }
}