package org.apache.commons.graph.shortestpath;

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

import static junit.framework.Assert.assertEquals;
import static org.apache.commons.graph.shortestpath.Dijkstra.findShortestPath;

import org.apache.commons.graph.Path;
import org.apache.commons.graph.model.BaseLabeledVertex;
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
import org.apache.commons.graph.model.InMemoryWeightedPath;
import org.junit.Test;

public final class DijkstraTestCase
{

    /**
     * Test Graph and Dijkstra's solution can be seen on
     * <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm>Wikipedia</a>
     */
    @Test
    public void findShortestPathAndVerify()
    {
        DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge> mutable =
            new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>();

        // building Graph

        BaseLabeledVertex one = new BaseLabeledVertex( "1" );
        BaseLabeledVertex two = new BaseLabeledVertex( "2" );
        BaseLabeledVertex three = new BaseLabeledVertex( "3" );
        BaseLabeledVertex four = new BaseLabeledVertex( "4" );
        BaseLabeledVertex five = new BaseLabeledVertex( "5" );
        BaseLabeledVertex six = new BaseLabeledVertex( "6" );

        mutable.addVertex( one );
        mutable.addVertex( two );
        mutable.addVertex( three );
        mutable.addVertex( four );
        mutable.addVertex( five );
        mutable.addVertex( six );

        mutable.addEdge( new BaseLabeledWeightedEdge( "", one, six, 14D ) );
        mutable.addEdge( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
        mutable.addEdge( new BaseLabeledWeightedEdge( "", one, two, 7D ) );

        mutable.addEdge( new BaseLabeledWeightedEdge( "", two, three, 10D ) );
        mutable.addEdge( new BaseLabeledWeightedEdge( "", two, four, 15D ) );

        mutable.addEdge( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
        mutable.addEdge( new BaseLabeledWeightedEdge( "", three, four, 11D ) );

        mutable.addEdge( new BaseLabeledWeightedEdge( "", four, five, 6D ) );
        mutable.addEdge( new BaseLabeledWeightedEdge( "", six, five, 9D ) );

        // expected path

        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, five );

        expected.addVertexInTail( three );
        expected.addVertexInTail( six );
        expected.addVertexInTail( five );

        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", six, five, 9D ) );

        // actual path

        Path<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = findShortestPath( mutable, one, five );

        // assert!

        assertEquals( expected, actual );
    }

}

@@ -1624,23 +1624,21 @@
 edEdge%3E 
-mutable
+graph
  =%0A     
@@ -2129,39 +2129,37 @@
 %226%22 );%0A%0A        
-mutable
+graph
 .addVertex( one 
@@ -2161,39 +2161,37 @@
  one );%0A        
-mutable
+graph
 .addVertex( two 
@@ -2193,39 +2193,37 @@
  two );%0A        
-mutable
+graph
 .addVertex( thre
@@ -2227,39 +2227,37 @@
 hree );%0A        
-mutable
+graph
 .addVertex( four
@@ -2260,39 +2260,37 @@
 four );%0A        
-mutable
+graph
 .addVertex( five
@@ -2297,31 +2297,29 @@
  );%0A        
-mutable
+graph
 .addVertex( 
@@ -2326,39 +2326,37 @@
 six );%0A%0A        
-mutable
+graph
 .addEdge( new Ba
@@ -2401,39 +2401,37 @@
 4D ) );%0A        
-mutable
+graph
 .addEdge( new Ba
@@ -2477,39 +2477,37 @@
 9D ) );%0A        
-mutable
+graph
 .addEdge( new Ba
@@ -2552,39 +2552,37 @@
 D ) );%0A%0A        
-mutable
+graph
 .addEdge( new Ba
@@ -2629,39 +2629,37 @@
 0D ) );%0A        
-mutable
+graph
 .addEdge( new Ba
@@ -2706,39 +2706,37 @@
 D ) );%0A%0A        
-mutable
+graph
 .addEdge( new Ba
@@ -2782,39 +2782,37 @@
 2D ) );%0A        
-mutable
+graph
 .addEdge( new Ba
@@ -2861,39 +2861,37 @@
 D ) );%0A%0A        
-mutable
+graph
 .addEdge( new Ba
@@ -2945,23 +2945,21 @@
         
-mutable
+graph
 .addEdge
@@ -3713,15 +3713,13 @@
 th( 
-mutable
+graph
 , on

properly renamed the graph variable name