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: #ifndef LEMON_TEST_GRAPH_UTILS_TEST_H
deba@139: #define LEMON_TEST_GRAPH_UTILS_TEST_H
deba@139: 
deba@139: 
deba@139: #include "test_tools.h"
deba@139: #include <cstdlib>
deba@139: #include <ctime>
deba@139: 
deba@139: //! \ingroup misc
deba@139: //! \file
deba@139: //! \brief Test cases for graph utils.
deba@139: namespace lemon {
deba@139:   
deba@139:   template <typename Digraph>
deba@139:   void checkDigraphCounters() {
deba@139:     const int num = 5;
deba@139:     Digraph digraph;
deba@139:     addPetersen(digraph, num);
deba@139:     bidirDigraph(digraph);
deba@139:     check(countNodes(digraph) == 2*num, "Wrong node number.");
deba@139:     check(countArcs(digraph) == 6*num, "Wrong arc number.");    
deba@139:     for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
deba@139:       check(countOutArcs(digraph, it) == 3, "Wrong out degree number.");
deba@139:       check(countInArcs(digraph, it) == 3, "Wrong in degree number.");
deba@139:     }
deba@139:   }
deba@139: 
deba@139:   template <typename Digraph>
deba@139:   void checkFindArc() {
deba@139:     typedef typename Digraph::Node Node;
deba@139:     typedef typename Digraph::Arc Arc;
deba@139:     typedef typename Digraph::NodeIt NodeIt;
deba@139:     typedef typename Digraph::ArcIt ArcIt;
deba@139:     Digraph digraph;
deba@139:     for (int i = 0; i < 10; ++i) {
deba@139:       digraph.addNode();
deba@139:     }
deba@139:     DescriptorMap<Digraph, Node> nodes(digraph);
deba@139:     typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
deba@139:     for (int i = 0; i < 100; ++i) {
deba@139:       int src = rnd[invNodes.size()];
deba@139:       int trg = rnd[invNodes.size()];
deba@139:       digraph.addArc(invNodes[src], invNodes[trg]);
deba@139:     }
deba@139:     typename Digraph::template ArcMap<bool> found(digraph, false);
deba@139:     DescriptorMap<Digraph, Arc> arcs(digraph);
deba@139:     for (NodeIt src(digraph); src != INVALID; ++src) {
deba@139:       for (NodeIt trg(digraph); trg != INVALID; ++trg) {
deba@139: 	for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
deba@139: 	  check(digraph.source(con) == src, "Wrong source.");
deba@139: 	  check(digraph.target(con) == trg, "Wrong target.");
deba@139: 	  check(found[con] == false, "The arc found already.");
deba@139: 	  found[con] = true;
deba@139: 	}
deba@139:       }
deba@139:     }
deba@139:     for (ArcIt it(digraph); it != INVALID; ++it) {
deba@139:       check(found[it] == true, "The arc is not found.");
deba@139:     }
deba@139:   }
deba@139:   
deba@139: } //namespace lemon
deba@139: 
deba@139: 
deba@139: #endif