/* -*- C++ -*-

 * test/graph_utils_test.h - Part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2005 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.

 *

 */

#ifndef LEMON_TEST_GRAPH_UTILS_TEST_H

#define LEMON_TEST_GRAPH_UTILS_TEST_H

#include "test_tools.h"

#include <cstdlib>

#include <ctime>

//! \ingroup misc

//! \file

//! \brief Test cases for graph utils.

namespace lemon {

  template <typename Graph>

  void checkGraphCounters() {

    const int num = 5;

    Graph graph;

    addPetersen(graph, num);

    bidirGraph(graph);

    check(countNodes(graph) == 2*num, "Wrong node number.");

    check(countEdges(graph) == 6*num, "Wrong edge number.");    

    for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {

      check(countOutEdges(graph, it) == 3, "Wrong out degree number.");

      check(countInEdges(graph, it) == 3, "Wrong in degree number.");

    }

  }

  template <typename Graph>

  void checkFindEdge() {

    typedef typename Graph::Node Node;

    typedef typename Graph::Edge Edge;

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::EdgeIt EdgeIt;

    Graph graph;

    srand(time(0));

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

      graph.addNode();

    }

    DescriptorMap<Graph, Node> nodes(graph);

    typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);

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

      int src = (int)(rand() / (RAND_MAX + 1.0) * invNodes.size());

      int trg = (int)(rand() / (RAND_MAX + 1.0) * invNodes.size());

      graph.addEdge(invNodes[src], invNodes[trg]);

    }

    typename Graph::template EdgeMap<bool> found(graph, false);

    DescriptorMap<Graph, Edge> edges(graph);

    for (NodeIt src(graph); src != INVALID; ++src) {

      for (NodeIt trg(graph); trg != INVALID; ++trg) {

	for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {

	  check(graph.source(con) == src, "Wrong source.");

	  check(graph.target(con) == trg, "Wrong target.");

	  check(found[con] == false, "The edge found already.");

	  found[con] = true;

	}

      }

    }

    for (EdgeIt it(graph); it != INVALID; ++it) {

      check(found[it] == true, "The edge is not found.");

    }

  }

} //namespace lemon

#endif