/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * 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 <lemon/smart_graph.h>
#include <lemon/list_graph.h>
#include <lemon/graph_reader.h>
#include <lemon/graph_utils.h>
#include <lemon/error.h>

#include "test_tools.h"

using namespace std;
using namespace lemon;

void graph_copy_test() {
  const int nn = 10;

  SmartGraph source;
  SmartGraph::NodeMap<int> snm(source);
  SmartGraph::EdgeMap<int> sem(source);
  SmartGraph::Node sn = INVALID;
  SmartGraph::Edge se = INVALID;

  std::vector<SmartGraph::Node> snv;
  for (int i = 0; i < nn; ++i) {
    SmartGraph::Node node = source.addNode();
    snv.push_back(node);
    snm[node] = i * i;
    if (i == 0) sn = node;
  }

  for (int i = 0; i < nn; ++i) {
    for (int j = 0; j < nn; ++j) {
      SmartGraph::Edge edge = source.addEdge(snv[i], snv[j]);
      sem[edge] = i + j * j;
      if (i == 0 && j == 0) se = edge;
    }
  }

  ListGraph target;
  ListGraph::NodeMap<int> tnm(target);
  ListGraph::EdgeMap<int> tem(target);
  ListGraph::Node tn;
  ListGraph::Edge te;

  SmartGraph::NodeMap<ListGraph::Node> nr(source);
  SmartGraph::EdgeMap<ListGraph::Edge> er(source);

  ListGraph::NodeMap<SmartGraph::Node> ncr(target);
  ListGraph::EdgeMap<SmartGraph::Edge> ecr(target);

  GraphCopy<ListGraph, SmartGraph>(target, source).
    nodeMap(tnm, snm).edgeMap(tem, sem).
    nodeRef(nr).edgeRef(er).
    nodeCrossRef(ncr).edgeCrossRef(ecr).
    node(tn, sn).edge(te, se).run();

  for (SmartGraph::NodeIt it(source); it != INVALID; ++it) {
    check(ncr[nr[it]] == it, "Wrong copy.");
    check(snm[it] == tnm[nr[it]], "Wrong copy.");
  }

  for (SmartGraph::EdgeIt it(source); it != INVALID; ++it) {
    check(ecr[er[it]] == it, "Wrong copy.");
    check(sem[it] == tem[er[it]], "Wrong copy.");
    check(nr[source.source(it)] == 
                 target.source(er[it]), "Wrong copy.");
    check(nr[source.target(it)] == 
                 target.target(er[it]), "Wrong copy.");
  }

  for (ListGraph::NodeIt it(target); it != INVALID; ++it) {
    check(nr[ncr[it]] == it, "Wrong copy.");
  }

  for (ListGraph::EdgeIt it(target); it != INVALID; ++it) {
    check(er[ecr[it]] == it, "Wrong copy.");
  }
  check(tn == nr[sn], "Wrong copy.");
  check(te == er[se], "Wrong copy.");
}

void ugraph_copy_test() {
  const int nn = 10;

  SmartUGraph source;
  SmartUGraph::NodeMap<int> snm(source);
  SmartUGraph::EdgeMap<int> sem(source);
  SmartUGraph::UEdgeMap<int> suem(source);
  SmartUGraph::Node sn = INVALID;
  SmartUGraph::Edge se = INVALID;
  SmartUGraph::UEdge sue = INVALID;

  std::vector<SmartUGraph::Node> snv;
  for (int i = 0; i < nn; ++i) {
    SmartUGraph::Node node = source.addNode();
    snv.push_back(node);
    snm[node] = i * i;
    if (i == 0) sn = node;
  }

  for (int i = 0; i < nn; ++i) {
    for (int j = 0; j < nn; ++j) {
      SmartUGraph::UEdge edge = source.addEdge(snv[i], snv[j]);
      suem[edge] = i * i + j * j;
      sem[source.direct(edge, true)] = i + j * j;
      sem[source.direct(edge, false)] = i * i + j;
      if (i == 0 && j == 0) se = source.direct(edge, true);
      if (i == 0 && j == 0) sue = edge;
    }
  }
  
  ListUGraph target;
  ListUGraph::NodeMap<int> tnm(target);
  ListUGraph::EdgeMap<int> tem(target);
  ListUGraph::UEdgeMap<int> tuem(target);
  ListUGraph::Node tn;
  ListUGraph::Edge te;
  ListUGraph::UEdge tue;

  SmartUGraph::NodeMap<ListUGraph::Node> nr(source);
  SmartUGraph::EdgeMap<ListUGraph::Edge> er(source);
  SmartUGraph::UEdgeMap<ListUGraph::UEdge> uer(source);

  ListUGraph::NodeMap<SmartUGraph::Node> ncr(target);
  ListUGraph::EdgeMap<SmartUGraph::Edge> ecr(target);
  ListUGraph::UEdgeMap<SmartUGraph::UEdge> uecr(target);

  UGraphCopy<ListUGraph, SmartUGraph>(target, source).
    nodeMap(tnm, snm).edgeMap(tem, sem).uEdgeMap(tuem, suem).
    nodeRef(nr).edgeRef(er).uEdgeRef(uer).
    nodeCrossRef(ncr).edgeCrossRef(ecr).uEdgeCrossRef(uecr).
    node(tn, sn).edge(te, se).uEdge(tue, sue).run();

  for (SmartUGraph::NodeIt it(source); it != INVALID; ++it) {
    check(ncr[nr[it]] == it, "Wrong copy.");
    check(snm[it] == tnm[nr[it]], "Wrong copy.");
  }

  for (SmartUGraph::EdgeIt it(source); it != INVALID; ++it) {
    check(ecr[er[it]] == it, "Wrong copy.");
    check(sem[it] == tem[er[it]], "Wrong copy.");
    check(nr[source.source(it)] == 
                 target.source(er[it]), "Wrong copy.");
    check(nr[source.target(it)] == 
                 target.target(er[it]), "Wrong copy.");
  }

  for (SmartUGraph::UEdgeIt it(source); it != INVALID; ++it) {
    check(uecr[uer[it]] == it, "Wrong copy.");
    check(suem[it] == tuem[uer[it]], "Wrong copy.");
    check(nr[source.source(it)] == target.source(uer[it]) ||
                 nr[source.source(it)] == target.target(uer[it]), 
                 "Wrong copy.");
    check(nr[source.target(it)] == target.source(uer[it]) ||
                 nr[source.target(it)] == target.target(uer[it]), 
                 "Wrong copy.");
    check((source.source(it) != source.target(it)) ==
                 (target.source(uer[it]) != target.target(uer[it])), 
                 "Wrong copy.");
  }

  for (ListUGraph::NodeIt it(target); it != INVALID; ++it) {
    check(nr[ncr[it]] == it, "Wrong copy.");
  }

  for (ListUGraph::EdgeIt it(target); it != INVALID; ++it) {
    check(er[ecr[it]] == it, "Wrong copy.");
  }
  for (ListUGraph::UEdgeIt it(target); it != INVALID; ++it) {
    check(uer[uecr[it]] == it, "Wrong copy.");
  }
  check(tn == nr[sn], "Wrong copy.");
  check(te == er[se], "Wrong copy.");
  check(tue == uer[sue], "Wrong copy.");
}

void bpugraph_copy_test() {
  const int nn = 10;

  SmartBpUGraph source;
  SmartBpUGraph::ANodeMap<int> sanm(source);
  SmartBpUGraph::BNodeMap<int> sbnm(source);
  SmartBpUGraph::NodeMap<int> snm(source);
  SmartBpUGraph::EdgeMap<int> sem(source);
  SmartBpUGraph::UEdgeMap<int> suem(source);
  SmartBpUGraph::Node sn = INVALID;
  SmartBpUGraph::Edge se = INVALID;
  SmartBpUGraph::UEdge sue = INVALID;

  std::vector<SmartBpUGraph::Node> sanv;
  for (int i = 0; i < nn; ++i) {
    SmartBpUGraph::Node node = source.addANode();
    sanv.push_back(node);
    sanm[node] = i * i;
    snm[node] = i * i + i;
    if (i == 0) sn = node;
  }

  std::vector<SmartBpUGraph::Node> sbnv;
  for (int i = 0; i < nn; ++i) {
    SmartBpUGraph::Node node = source.addBNode();
    sbnv.push_back(node);
    sbnm[node] = i * i - i;
    snm[node] = i * i + i + 1;
  }

  for (int i = 0; i < nn; ++i) {
    for (int j = 0; j < nn; ++j) {
      SmartBpUGraph::UEdge edge = source.addEdge(sanv[i], sbnv[j]);
      suem[edge] = i * i + j * j;
      sem[source.direct(edge, true)] = i + j * j;
      sem[source.direct(edge, false)] = i * i + j;
      if (i == 0 && j == 0) se = source.direct(edge, true);
      if (i == 0 && j == 0) sue = edge;
    }
  }
  
  ListBpUGraph target;
  ListBpUGraph::ANodeMap<int> tanm(target);
  ListBpUGraph::BNodeMap<int> tbnm(target);
  ListBpUGraph::NodeMap<int> tnm(target);
  ListBpUGraph::EdgeMap<int> tem(target);
  ListBpUGraph::UEdgeMap<int> tuem(target);
  ListBpUGraph::Node tn;
  ListBpUGraph::Edge te;
  ListBpUGraph::UEdge tue;

  SmartBpUGraph::ANodeMap<ListBpUGraph::Node> anr(source);
  SmartBpUGraph::BNodeMap<ListBpUGraph::Node> bnr(source);
  SmartBpUGraph::NodeMap<ListBpUGraph::Node> nr(source);
  SmartBpUGraph::EdgeMap<ListBpUGraph::Edge> er(source);
  SmartBpUGraph::UEdgeMap<ListBpUGraph::UEdge> uer(source);

  ListBpUGraph::ANodeMap<SmartBpUGraph::Node> ancr(target);
  ListBpUGraph::BNodeMap<SmartBpUGraph::Node> bncr(target);
  ListBpUGraph::NodeMap<SmartBpUGraph::Node> ncr(target);
  ListBpUGraph::EdgeMap<SmartBpUGraph::Edge> ecr(target);
  ListBpUGraph::UEdgeMap<SmartBpUGraph::UEdge> uecr(target);

  BpUGraphCopy<ListBpUGraph, SmartBpUGraph>(target, source).
    aNodeMap(tanm, sanm).bNodeMap(tbnm, sbnm).nodeMap(tnm, snm).
    edgeMap(tem, sem).uEdgeMap(tuem, suem).
    aNodeRef(anr).bNodeRef(bnr).nodeRef(nr).edgeRef(er).uEdgeRef(uer).
    aNodeCrossRef(ancr).bNodeCrossRef(bncr).nodeCrossRef(ncr).
    edgeCrossRef(ecr).uEdgeCrossRef(uecr).
    node(tn, sn).edge(te, se).uEdge(tue, sue).run();

  for (SmartBpUGraph::ANodeIt it(source); it != INVALID; ++it) {
    check(nr[it] == anr[it], "Wrong copy.");
    check(ancr[anr[it]] == it, "Wrong copy.");
    check(sanm[it] == tanm[anr[it]], "Wrong copy.");
  }

  for (SmartBpUGraph::BNodeIt it(source); it != INVALID; ++it) {
    check(nr[it] == bnr[it], "Wrong copy.");
    check(bncr[bnr[it]] == it, "Wrong copy.");
    check(sbnm[it] == tbnm[bnr[it]], "Wrong copy.");
  }

  for (SmartBpUGraph::NodeIt it(source); it != INVALID; ++it) {
    check(ncr[nr[it]] == it, "Wrong copy.");
    check(snm[it] == tnm[nr[it]], "Wrong copy.");
  }

  for (SmartBpUGraph::EdgeIt it(source); it != INVALID; ++it) {
    check(ecr[er[it]] == it, "Wrong copy.");
    check(sem[it] == tem[er[it]], "Wrong copy.");
    check(nr[source.source(it)] == 
                 target.source(er[it]), "Wrong copy.");
    check(nr[source.target(it)] == 
                 target.target(er[it]), "Wrong copy.");
  }

  for (SmartBpUGraph::UEdgeIt it(source); it != INVALID; ++it) {
    check(uecr[uer[it]] == it, "Wrong copy.");
    check(suem[it] == tuem[uer[it]], "Wrong copy.");
    check(nr[source.aNode(it)] == 
                 target.aNode(uer[it]), "Wrong copy.");
    check(nr[source.bNode(it)] == 
                 target.bNode(uer[it]), "Wrong copy.");
  }

  for (ListBpUGraph::ANodeIt it(target); it != INVALID; ++it) {
    check(ancr[it] == ncr[it], "Wrong copy.");
    check(anr[ancr[it]] == it, "Wrong copy.");
  }

  for (ListBpUGraph::BNodeIt it(target); it != INVALID; ++it) {
    check(bncr[it] == ncr[it], "Wrong copy.");
    check(bnr[bncr[it]] == it, "Wrong copy.");
  }

  for (ListBpUGraph::NodeIt it(target); it != INVALID; ++it) {
    check(nr[ncr[it]] == it, "Wrong copy.");
  }

  for (ListBpUGraph::EdgeIt it(target); it != INVALID; ++it) {
    check(er[ecr[it]] == it, "Wrong copy.");
  }
  for (ListBpUGraph::UEdgeIt it(target); it != INVALID; ++it) {
    check(uer[uecr[it]] == it, "Wrong copy.");
  }
  check(tn == nr[sn], "Wrong copy.");
  check(te == er[se], "Wrong copy.");
  check(tue == uer[sue], "Wrong copy.");
}

int main() {
  graph_copy_test();
  ugraph_copy_test();
  bpugraph_copy_test();

  return 0; 
}