/*

     This file is part of Combean.

     Combean is free software; you can redistribute it and/or modify

     it under the terms of the GNU General Public License as published by

     the Free Software Foundation; either version 2 of the License, or

     (at your option) any later version.

     Combean is distributed in the hope that it will be useful,

     but WITHOUT ANY WARRANTY; without even the implied warranty of

     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

     GNU General Public License for more details.

     You should have received a copy of the GNU General Public License

     along with Combean; if not, write to the Free Software

     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

 */

 /*

  * Created on 10.04.2005

  *

  */

 package net.sourceforge.combean.test.graph.alg.spath;

 import net.sourceforge.combean.interfaces.graph.NodeIterator;

 import net.sourceforge.combean.interfaces.graph.alg.spath.SingleSourceShortestPathWithNegCycleDetectionAlg;

 import net.sourceforge.combean.interfaces.graph.containers.FixedPath;

 /**

  * @author schickin

  *

  */

 public class GraphWithNegativeCycleFixture

 extends AbstractGraphWithEdgeWeightsFixture {

     // graph taken from "Network Flows", Ahuja/Magnanti/Orlin, p. 110

     //

     //              2

     //    ----> 2 -----> 4 -----

     //    |     ^*       |     |

     //  4 |     | \      |     | 3

     //    |     |  \   1 |     *

     //    0   2 |   \    |     5

     //    |     | -4 \   |     ^

     //  6 |     |     \  |     |

     //    |     |      \ *     | 7

     //    ----> 1 -----> 3 -----

     //              2

     //

     // The shortest path from 1 to 3 is: (1, 3, 5, 6) with length 4+2+3=9

     //

     private static int[][] edgesWithWeights = {

             {0, 2, 4},

             {0, 1, 6},

             {1, 2, 2},

             {1, 3, 2},

             {3, 2,-4},

             {2, 4, 2},

             {3, 5, 7},

             {4, 3, 1},

             {4, 5, 3}

     };

     private static int[] cycleNodes = {2,4,3,2,4,3};

     /**

      * constructor

      */

     public GraphWithNegativeCycleFixture() throws Exception {

         super(6, edgesWithWeights);

     }

     public final void checkNegativeCycleDetection(

             SingleSourceShortestPathWithNegCycleDetectionAlg<Double> alg) {

         runShortestPathAlg(alg);

         boolean negCycleFound = alg.hasNegativeCycle();

         assertTrue(negCycleFound);

         FixedPath cycle = alg.getNegativeCycle();

         assertNotNull(cycle);

         int idxOfFirstNodeInCycle =

             this.constructG.getNodeNumber(cycle.getFirstNode());

         int startNodeIdx = -1;

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

             if (cycleNodes[i] == idxOfFirstNodeInCycle) {

                 startNodeIdx = i;

                 break;

             }

         }

         assertTrue("first node of cycle with number " + idxOfFirstNodeInCycle +

                 " must belong to cyclenodes array",

                 -1 != startNodeIdx);

         NodeIterator itCycle = cycle.getNodeIterator();

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

             assertTrue("cycle may not end prematurely", itCycle.hasNext());

             int currNodeNum = this.constructG.getNodeNumber(itCycle.next());

             assertEquals(cycleNodes[startNodeIdx + i], currNodeNum);

         }

         assertFalse("cycle may not have additional nodes", itCycle.hasNext());

     }

 }