/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * 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 <cstdlib>

#include <ctime>

#include <lemon/random.h>

#include <lemon/graph_utils.h>

#include <lemon/list_graph.h>

#include <lemon/smart_graph.h>

#include "graph_test.h"

#include "test_tools.h"

using namespace lemon;

template <typename Digraph>

void checkFindArcs() {

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  {

    Digraph digraph;

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

      digraph.addNode();

    }

    DescriptorMap<Digraph, Node> nodes(digraph);

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

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

      int src = rnd[invNodes.size()];

      int trg = rnd[invNodes.size()];

      digraph.addArc(invNodes[src], invNodes[trg]);

    }

    typename Digraph::template ArcMap<bool> found(digraph, false);

    DescriptorMap<Digraph, Arc> arcs(digraph);

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

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

        for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {

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

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

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

          found[con] = true;

        }

      }

    }

    for (ArcIt it(digraph); it != INVALID; ++it) {

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

    }

  }

  {

    int num = 5;

    Digraph fg;

    std::vector<Node> nodes;

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

      nodes.push_back(fg.addNode());

    }

    for (int i = 0; i < num * num; ++i) {

      fg.addArc(nodes[i / num], nodes[i % num]);

    }

    check(countNodes(fg) == num, "Wrong node number.");

    check(countArcs(fg) == num*num, "Wrong arc number.");

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

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

        ConArcIt<Digraph> con(fg, src, trg);

        check(con != INVALID, "There is no connecting arc.");

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

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

        check(++con == INVALID, "There is more connecting arc.");

      }

    }

    ArcLookUp<Digraph> al1(fg);

    DynArcLookUp<Digraph> al2(fg);

    AllArcLookUp<Digraph> al3(fg);

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

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

        Arc con1 = al1(src, trg);

        Arc con2 = al2(src, trg);

        Arc con3 = al3(src, trg);

        Arc con4 = findArc(fg, src, trg);

        check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.")

        check(con1 != INVALID, "There is no connecting arc.");

        check(fg.source(con1) == src, "Wrong source.");

        check(fg.target(con1) == trg, "Wrong target.");

        check(al3(src, trg, con3) == INVALID, "There is more connecting arc.");

        check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc.");

      }

    }

  }

}

template <typename Graph>

void checkFindEdges() {

  TEMPLATE_GRAPH_TYPEDEFS(Graph);

  Graph graph;

  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 = rnd[invNodes.size()];

    int trg = rnd[invNodes.size()];

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

  }

  typename Graph::template EdgeMap<int> found(graph, 0);

  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.u(con) == src && graph.v(con) == trg) ||

               (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes.");

        ++found[con];

        check(found[con] <= 2, "The edge found more than twice.");

      }

    }

  }

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

    check( (graph.u(it) != graph.v(it) && found[it] == 2) ||

           (graph.u(it) == graph.v(it) && found[it] == 1),

           "The edge is not found correctly.");

  }

}

template <class Digraph>

void checkDeg()

{

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  const int nodeNum = 10;

  const int arcNum = 100;

  Digraph digraph;

  InDegMap<Digraph> inDeg(digraph);

  OutDegMap<Digraph> outDeg(digraph);

  std::vector<Node> nodes(nodeNum);

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

    nodes[i] = digraph.addNode();

  }

  std::vector<Arc> arcs(arcNum);

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

    arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);

  }

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

    check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 

          "Wrong in degree map");

  }

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

    check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 

          "Wrong out degree map");

  }

}

template <class Digraph>

void checkSnapDeg()

{

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Digraph g;

  Node n1=g.addNode();

  Node n2=g.addNode();

  InDegMap<Digraph> ind(g);

  g.addArc(n1,n2);

  typename Digraph::Snapshot snap(g);

  OutDegMap<Digraph> outd(g);

  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");

  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");

  g.addArc(n1,n2);

  g.addArc(n2,n1);

  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");

  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");

  snap.restore();

  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");

  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");

}

int main() {

  // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp

  checkFindArcs<ListDigraph>();

  checkFindArcs<SmartDigraph>();

  checkFindEdges<ListGraph>();

  checkFindEdges<SmartGraph>();

  // Checking In/OutDegMap (and Snapshot feature)

  checkDeg<ListDigraph>();

  checkDeg<SmartDigraph>();

  checkSnapDeg<ListDigraph>();

  checkSnapDeg<SmartDigraph>();

  return 0;

}