/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <string>
#include <iostream>

#include <lemon/concept/path.h>
#include <lemon/concept/graph.h>

#include <lemon/path.h>
#include <lemon/list_graph.h>

#include "test_tools.h"

using namespace std;
using namespace lemon;

void check_concepts() {
  checkConcept<concept::Path<concept::Graph>, 
    concept::Path<concept::Graph> >();
  checkConcept<concept::Path<concept::Graph>, 
    Path<concept::Graph> >();
  checkConcept<concept::Path<ListGraph>, Path<ListGraph> >();
}

int main() {
  check_concepts();
  
  ListGraph g;
  
  ListGraph::Node n1 = g.addNode();
  ListGraph::Node n2 = g.addNode();
  ListGraph::Node n3 = g.addNode();
  ListGraph::Node n4 = g.addNode();
  ListGraph::Node n5 = g.addNode();
 
  ListGraph::Edge e1 = g.addEdge(n1, n2);
  ListGraph::Edge e2 = g.addEdge(n2, n3);
  ListGraph::Edge e3 = g.addEdge(n3, n4);
  ListGraph::Edge e4 = g.addEdge(n4, n5);
  ListGraph::Edge e5 = g.addEdge(n5, n1);

  {
    Path<ListGraph> p(g);

    check(p.empty(), "Wrong Path");
    check(p.length() == 0, "Wrong Path");
    
    {
      Path<ListGraph>::Builder b(p);
      b.setStartNode(n3);
      b.commit();
    }

    check(!p.empty(), "Wrong Path");
    check(p.length() == 0, "Wrong Path");
    check(p.source() == n3, "Wrong Path");
    check(p.target() == n3, "Wrong Path");

    {
      Path<ListGraph>::Builder b(p);
      b.pushBack(e3);
      b.pushBack(e4);
      b.pushFront(e2);
      b.commit();
    }

    check(!p.empty(), "Wrong Path");
    check(p.length() == 3, "Wrong Path");
    check(p.source() == n2, "Wrong Path");
    check(p.target() == n5, "Wrong Path");
    
    {
      Path<ListGraph>::NodeIt it(p);
      check((ListGraph::Node)it == n2, "Wrong Path"); ++it;
      check((ListGraph::Node)it == n3, "Wrong Path"); ++it;
      check((ListGraph::Node)it == n4, "Wrong Path"); ++it;
      check((ListGraph::Node)it == n5, "Wrong Path"); ++it;
      check((ListGraph::Node)it == INVALID, "Wrong Path");
    }

    {
      Path<ListGraph>::EdgeIt it(p);
      check((ListGraph::Edge)it == e2, "Wrong Path"); ++it;
      check((ListGraph::Edge)it == e3, "Wrong Path"); ++it;
      check((ListGraph::Edge)it == e4, "Wrong Path"); ++it;
      check((ListGraph::Edge)it == INVALID, "Wrong Path");
    }
    
  }
  
  return 0;
}