alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@139:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
deba@139:  *
deba@139:  * Copyright (C) 2003-2008
deba@139:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@139:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@139:  *
deba@139:  * Permission to use, modify and distribute this software is granted
deba@139:  * provided that this copyright notice appears in all copies. For
deba@139:  * precise terms see the accompanying LICENSE file.
deba@139:  *
deba@139:  * This software is provided "AS IS" with no warranty of any kind,
deba@139:  * express or implied, and with no claim as to its suitability for any
deba@139:  * purpose.
deba@139:  *
deba@139:  */
deba@139: 
kpeter@171: #include <cstdlib>
kpeter@171: #include <ctime>
deba@139: 
kpeter@171: #include <lemon/random.h>
deba@139: #include <lemon/list_graph.h>
deba@139: #include <lemon/smart_graph.h>
deba@220: #include <lemon/maps.h>
deba@139: 
kpeter@171: #include "graph_test.h"
deba@139: #include "test_tools.h"
deba@139: 
deba@139: using namespace lemon;
deba@139: 
kpeter@171: template <typename Digraph>
kpeter@171: void checkFindArcs() {
kpeter@171:   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171: 
kpeter@171:   {
kpeter@171:     Digraph digraph;
alpar@324:     typename Digraph::template NodeMap<int> nodes(digraph);
alpar@324:     std::vector<Node> invNodes;
kpeter@171:     for (int i = 0; i < 10; ++i) {
alpar@324:       invNodes.push_back(digraph.addNode());
alpar@324:       nodes[invNodes.back()]=invNodes.size()-1;
kpeter@171:     }
kpeter@171:     for (int i = 0; i < 100; ++i) {
kpeter@171:       int src = rnd[invNodes.size()];
kpeter@171:       int trg = rnd[invNodes.size()];
kpeter@171:       digraph.addArc(invNodes[src], invNodes[trg]);
kpeter@171:     }
kpeter@171:     typename Digraph::template ArcMap<bool> found(digraph, false);
kpeter@171:     for (NodeIt src(digraph); src != INVALID; ++src) {
kpeter@171:       for (NodeIt trg(digraph); trg != INVALID; ++trg) {
kpeter@171:         for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
kpeter@171:           check(digraph.source(con) == src, "Wrong source.");
kpeter@171:           check(digraph.target(con) == trg, "Wrong target.");
kpeter@171:           check(found[con] == false, "The arc found already.");
kpeter@171:           found[con] = true;
kpeter@171:         }
kpeter@171:       }
kpeter@171:     }
kpeter@171:     for (ArcIt it(digraph); it != INVALID; ++it) {
kpeter@171:       check(found[it] == true, "The arc is not found.");
kpeter@171:     }
kpeter@171:   }
kpeter@171: 
kpeter@171:   {
kpeter@171:     int num = 5;
kpeter@171:     Digraph fg;
kpeter@171:     std::vector<Node> nodes;
kpeter@171:     for (int i = 0; i < num; ++i) {
kpeter@171:       nodes.push_back(fg.addNode());
kpeter@171:     }
kpeter@171:     for (int i = 0; i < num * num; ++i) {
kpeter@171:       fg.addArc(nodes[i / num], nodes[i % num]);
kpeter@171:     }
kpeter@171:     check(countNodes(fg) == num, "Wrong node number.");
kpeter@171:     check(countArcs(fg) == num*num, "Wrong arc number.");
kpeter@171:     for (NodeIt src(fg); src != INVALID; ++src) {
kpeter@171:       for (NodeIt trg(fg); trg != INVALID; ++trg) {
kpeter@171:         ConArcIt<Digraph> con(fg, src, trg);
kpeter@171:         check(con != INVALID, "There is no connecting arc.");
kpeter@171:         check(fg.source(con) == src, "Wrong source.");
kpeter@171:         check(fg.target(con) == trg, "Wrong target.");
kpeter@171:         check(++con == INVALID, "There is more connecting arc.");
kpeter@171:       }
kpeter@171:     }
kpeter@171:     ArcLookUp<Digraph> al1(fg);
kpeter@171:     DynArcLookUp<Digraph> al2(fg);
kpeter@171:     AllArcLookUp<Digraph> al3(fg);
kpeter@171:     for (NodeIt src(fg); src != INVALID; ++src) {
kpeter@171:       for (NodeIt trg(fg); trg != INVALID; ++trg) {
kpeter@171:         Arc con1 = al1(src, trg);
kpeter@171:         Arc con2 = al2(src, trg);
kpeter@171:         Arc con3 = al3(src, trg);
kpeter@171:         Arc con4 = findArc(fg, src, trg);
alpar@210:         check(con1 == con2 && con2 == con3 && con3 == con4,
alpar@210:               "Different results.")
kpeter@171:         check(con1 != INVALID, "There is no connecting arc.");
kpeter@171:         check(fg.source(con1) == src, "Wrong source.");
kpeter@171:         check(fg.target(con1) == trg, "Wrong target.");
alpar@210:         check(al3(src, trg, con3) == INVALID,
alpar@210:               "There is more connecting arc.");
alpar@210:         check(findArc(fg, src, trg, con4) == INVALID,
alpar@210:               "There is more connecting arc.");
kpeter@171:       }
kpeter@171:     }
kpeter@171:   }
kpeter@171: }
kpeter@171: 
kpeter@171: template <typename Graph>
kpeter@171: void checkFindEdges() {
kpeter@171:   TEMPLATE_GRAPH_TYPEDEFS(Graph);
kpeter@171:   Graph graph;
alpar@324:   typename Graph::template NodeMap<int> nodes(graph);
alpar@324:   std::vector<Node> invNodes;
kpeter@171:   for (int i = 0; i < 10; ++i) {
alpar@324:     invNodes.push_back(graph.addNode());
alpar@324:     nodes[invNodes.back()]=invNodes.size()-1;
kpeter@171:   }
kpeter@171:   for (int i = 0; i < 100; ++i) {
kpeter@171:     int src = rnd[invNodes.size()];
kpeter@171:     int trg = rnd[invNodes.size()];
kpeter@171:     graph.addEdge(invNodes[src], invNodes[trg]);
kpeter@171:   }
kpeter@171:   typename Graph::template EdgeMap<int> found(graph, 0);
kpeter@171:   for (NodeIt src(graph); src != INVALID; ++src) {
kpeter@171:     for (NodeIt trg(graph); trg != INVALID; ++trg) {
kpeter@171:       for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
kpeter@171:         check( (graph.u(con) == src && graph.v(con) == trg) ||
alpar@210:                (graph.v(con) == src && graph.u(con) == trg),
alpar@210:                "Wrong end nodes.");
kpeter@171:         ++found[con];
kpeter@171:         check(found[con] <= 2, "The edge found more than twice.");
kpeter@171:       }
kpeter@171:     }
kpeter@171:   }
kpeter@171:   for (EdgeIt it(graph); it != INVALID; ++it) {
kpeter@171:     check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
kpeter@171:            (graph.u(it) == graph.v(it) && found[it] == 1),
kpeter@171:            "The edge is not found correctly.");
kpeter@171:   }
kpeter@171: }
kpeter@171: 
kpeter@171: template <class Digraph>
kpeter@171: void checkDeg()
deba@139: {
kpeter@171:   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@209: 
kpeter@171:   const int nodeNum = 10;
kpeter@171:   const int arcNum = 100;
kpeter@171:   Digraph digraph;
kpeter@171:   InDegMap<Digraph> inDeg(digraph);
kpeter@171:   OutDegMap<Digraph> outDeg(digraph);
kpeter@171:   std::vector<Node> nodes(nodeNum);
kpeter@171:   for (int i = 0; i < nodeNum; ++i) {
kpeter@171:     nodes[i] = digraph.addNode();
kpeter@171:   }
kpeter@171:   std::vector<Arc> arcs(arcNum);
kpeter@171:   for (int i = 0; i < arcNum; ++i) {
kpeter@171:     arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
kpeter@171:   }
kpeter@171:   for (int i = 0; i < nodeNum; ++i) {
alpar@209:     check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
kpeter@171:           "Wrong in degree map");
kpeter@171:   }
kpeter@171:   for (int i = 0; i < nodeNum; ++i) {
alpar@209:     check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
kpeter@171:           "Wrong out degree map");
kpeter@171:   }
kpeter@171: }
kpeter@171: 
kpeter@171: template <class Digraph>
kpeter@171: void checkSnapDeg()
kpeter@171: {
kpeter@171:   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171: 
kpeter@171:   Digraph g;
kpeter@171:   Node n1=g.addNode();
kpeter@171:   Node n2=g.addNode();
alpar@209: 
kpeter@171:   InDegMap<Digraph> ind(g);
alpar@209: 
deba@139:   g.addArc(n1,n2);
alpar@209: 
kpeter@171:   typename Digraph::Snapshot snap(g);
alpar@209: 
kpeter@171:   OutDegMap<Digraph> outd(g);
alpar@209: 
deba@139:   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
deba@139:   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
deba@139: 
deba@139:   g.addArc(n1,n2);
deba@139:   g.addArc(n2,n1);
kpeter@171: 
deba@139:   check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
deba@139:   check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
deba@139: 
deba@139:   snap.restore();
deba@139: 
deba@139:   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
deba@139:   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
deba@139: }
deba@139: 
deba@139: int main() {
kpeter@171:   // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
kpeter@171:   checkFindArcs<ListDigraph>();
kpeter@171:   checkFindArcs<SmartDigraph>();
kpeter@171:   checkFindEdges<ListGraph>();
kpeter@171:   checkFindEdges<SmartGraph>();
deba@139: 
kpeter@171:   // Checking In/OutDegMap (and Snapshot feature)
kpeter@171:   checkDeg<ListDigraph>();
kpeter@171:   checkDeg<SmartDigraph>();
deba@139:   checkSnapDeg<ListDigraph>();
deba@139:   checkSnapDeg<SmartDigraph>();
deba@139: 
deba@139:   return 0;
deba@139: }