klao@946: /* -*- C++ -*-
klao@946:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
klao@946:  *
klao@946:  * Permission to use, modify and distribute this software is granted
klao@946:  * provided that this copyright notice appears in all copies. For
klao@946:  * precise terms see the accompanying LICENSE file.
klao@946:  *
klao@946:  * This software is provided "AS IS" with no warranty of any kind,
klao@946:  * express or implied, and with no claim as to its suitability for any
klao@946:  * purpose.
klao@946:  *
klao@946:  */
alpar@1956: 
klao@946: #ifndef LEMON_TEST_GRAPH_UTILS_TEST_H
klao@946: #define LEMON_TEST_GRAPH_UTILS_TEST_H
klao@946: 
klao@946: 
klao@946: #include "test_tools.h"
deba@1568: #include <cstdlib>
deba@1568: #include <ctime>
klao@946: 
klao@946: //! \ingroup misc
klao@946: //! \file
klao@946: //! \brief Test cases for graph utils.
klao@946: namespace lemon {
klao@946:   
klao@946:   template <typename Graph>
klao@946:   void checkGraphCounters() {
klao@946:     const int num = 5;
klao@946:     Graph graph;
klao@946:     addPetersen(graph, num);
klao@946:     bidirGraph(graph);
klao@977:     check(countNodes(graph) == 2*num, "Wrong node number.");
klao@977:     check(countEdges(graph) == 6*num, "Wrong edge number.");    
klao@946:     for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
klao@977:       check(countOutEdges(graph, it) == 3, "Wrong out degree number.");
klao@977:       check(countInEdges(graph, it) == 3, "Wrong in degree number.");
klao@946:     }
klao@946:   }
deba@1568: 
deba@1568:   template <typename Graph>
deba@1568:   void checkFindEdge() {
deba@1568:     typedef typename Graph::Node Node;
deba@1568:     typedef typename Graph::Edge Edge;
deba@1568:     typedef typename Graph::NodeIt NodeIt;
deba@1568:     typedef typename Graph::EdgeIt EdgeIt;
deba@1568:     Graph graph;
deba@1568:     srand(time(0));
deba@1568:     for (int i = 0; i < 10; ++i) {
deba@1568:       graph.addNode();
deba@1568:     }
deba@1568:     DescriptorMap<Graph, Node> nodes(graph);
deba@1568:     typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
deba@1568:     for (int i = 0; i < 100; ++i) {
deba@1568:       int src = (int)(rand() / (RAND_MAX + 1.0) * invNodes.size());
deba@1568:       int trg = (int)(rand() / (RAND_MAX + 1.0) * invNodes.size());
deba@1568:       graph.addEdge(invNodes[src], invNodes[trg]);
deba@1568:     }
deba@1568:     typename Graph::template EdgeMap<bool> found(graph, false);
deba@1568:     DescriptorMap<Graph, Edge> edges(graph);
deba@1568:     for (NodeIt src(graph); src != INVALID; ++src) {
deba@1568:       for (NodeIt trg(graph); trg != INVALID; ++trg) {
deba@1568: 	for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
deba@1568: 	  check(graph.source(con) == src, "Wrong source.");
deba@1568: 	  check(graph.target(con) == trg, "Wrong target.");
deba@1568: 	  check(found[con] == false, "The edge found already.");
deba@1568: 	  found[con] = true;
deba@1568: 	}
deba@1568:       }
deba@1568:     }
deba@1568:     for (EdgeIt it(graph); it != INVALID; ++it) {
deba@1568:       check(found[it] == true, "The edge is not found.");
deba@1568:     }
deba@1568:   }
klao@946:   
klao@946: } //namespace lemon
klao@946: 
klao@946: 
klao@946: #endif