deba@139: /* -*- C++ -*-
deba@139:  *
deba@139:  * 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: 
deba@139: #include <iostream>
deba@139: #include <vector>
deba@139: 
deba@139: #include <lemon/graph_utils.h>
deba@139: 
deba@139: #include <lemon/list_graph.h>
deba@139: #include <lemon/smart_graph.h>
deba@139: 
deba@139: #include "test_tools.h"
deba@139: #include "graph_utils_test.h"
deba@139: 
deba@139: 
deba@139: using namespace lemon;
deba@139: 
deba@139: template <class Graph>
deba@139: void checkSnapDeg() 
deba@139: {
deba@139:   Graph g;
deba@139:   typename Graph::Node n1=g.addNode();
deba@139:   typename Graph::Node n2=g.addNode();
deba@139:    
deba@139:   InDegMap<Graph> ind(g);
deba@139:  
deba@139:   g.addArc(n1,n2);
deba@139:   
deba@139:   typename Graph::Snapshot snap(g);
deba@139:   
deba@139:   OutDegMap<Graph> outd(g);
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:   g.addArc(n1,n2);
deba@139:   g.addArc(n2,n1);
deba@139:  
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: 
deba@139: int main() {
deba@139:   ///\file
deba@139:   { // checking list graph
deba@139:     checkDigraphCounters<ListDigraph>();
deba@139:     checkFindArc<ListDigraph>();
deba@139:   }
deba@139:   { // checking smart graph
deba@139:     checkDigraphCounters<SmartDigraph>();
deba@139:     checkFindArc<SmartDigraph>();
deba@139:   }
deba@139:   {
deba@139:     int num = 5;
deba@139:     SmartDigraph fg;
deba@139:     std::vector<SmartDigraph::Node> nodes;
deba@139:     for (int i = 0; i < num; ++i) {
deba@139:       nodes.push_back(fg.addNode());
deba@139:     }
deba@139:     for (int i = 0; i < num * num; ++i) {
deba@139:       fg.addArc(nodes[i / num], nodes[i % num]);
deba@139:     }
deba@139:     check(countNodes(fg) == num, "FullGraph: wrong node number.");
deba@139:     check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
deba@139:     for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
deba@139:       for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
deba@139: 	ConArcIt<SmartDigraph> con(fg, src, trg);
deba@139: 	check(con != INVALID, "There is no connecting arc.");
deba@139: 	check(fg.source(con) == src, "Wrong source.");
deba@139: 	check(fg.target(con) == trg, "Wrong target.");
deba@139: 	check(++con == INVALID, "There is more connecting arc.");
deba@139:       }
deba@139:     }
deba@139:     AllArcLookUp<SmartDigraph> el(fg);
deba@139:     for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
deba@139:       for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
deba@139: 	SmartDigraph::Arc con = el(src, trg);
deba@139: 	check(con != INVALID, "There is no connecting arc.");
deba@139: 	check(fg.source(con) == src, "Wrong source.");
deba@139: 	check(fg.target(con) == trg, "Wrong target.");
deba@139: 	check(el(src,trg,con) == INVALID, "There is more connecting arc.");
deba@139:       }
deba@139:     }
deba@139:   }
deba@139: 
deba@139:   //check In/OutDegMap (and Snapshot feature)
deba@139: 
deba@139:   checkSnapDeg<ListDigraph>();
deba@139:   checkSnapDeg<SmartDigraph>();
deba@139:   
deba@139:   {
deba@139:     const int nodeNum = 10;
deba@139:     const int arcNum = 100;
deba@139:     ListDigraph digraph;
deba@139:     InDegMap<ListDigraph> inDeg(digraph);
deba@139:     OutDegMap<ListDigraph> outDeg(digraph);
deba@139:     std::vector<ListDigraph::Node> nodes(nodeNum);
deba@139:     for (int i = 0; i < nodeNum; ++i) {
deba@139:       nodes[i] = digraph.addNode();
deba@139:     }
deba@139:     std::vector<ListDigraph::Arc> arcs(arcNum);
deba@139:     for (int i = 0; i < arcNum; ++i) {
deba@139:       arcs[i] = 
deba@139: 	digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
deba@139:     }
deba@139:     for (int i = 0; i < nodeNum; ++i) {
deba@139:       check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 
deba@139: 	    "Wrong in degree map");
deba@139:     }
deba@139:     for (int i = 0; i < nodeNum; ++i) {
deba@139:       check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 
deba@139: 	    "Wrong in degree map");
deba@139:     }
deba@139:   }
deba@139: 
deba@139:   ///Everything is OK
deba@139:   std::cout << __FILE__ ": All tests passed.\n";
deba@139: 
deba@139:   return 0;
deba@139: }