A push/relabel type max cardinality matching implementation.
(slightly incompatible with bipartite_matching.h)
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_TEST_GRAPH_TEST_H
20 #define LEMON_TEST_GRAPH_TEST_H
22 #include <lemon/graph_utils.h>
23 #include "test_tools.h"
27 //! \brief Some utility and test cases to test graph classes.
30 template<class Graph> void checkGraphNodeList(Graph &G, int nn)
32 typename Graph::NodeIt n(G);
33 for(int i=0;i<nn;i++) {
34 check(n!=INVALID,"Wrong Node list linking.");
37 check(n==INVALID,"Wrong Node list linking.");
41 void checkGraphEdgeList(Graph &G, int nn)
43 typedef typename Graph::EdgeIt EdgeIt;
46 for(int i=0;i<nn;i++) {
47 check(e!=INVALID,"Wrong Edge list linking.");
50 check(e==INVALID,"Wrong Edge list linking.");
54 void checkGraphOutEdgeList(Graph &G, typename Graph::Node n, int nn)
56 typename Graph::OutEdgeIt e(G,n);
57 for(int i=0;i<nn;i++) {
58 check(e!=INVALID,"Wrong OutEdge list linking.");
59 check(n==G.source(e), "Wrong OutEdge list linking.");
62 check(e==INVALID,"Wrong OutEdge list linking.");
65 template<class Graph> void
66 checkGraphInEdgeList(Graph &G, typename Graph::Node n, int nn)
68 typename Graph::InEdgeIt e(G,n);
69 for(int i=0;i<nn;i++) {
70 check(e!=INVALID,"Wrong InEdge list linking.");
71 check(n==G.target(e), "Wrong InEdge list linking.");
74 check(e==INVALID,"Wrong InEdge list linking.");
77 template <class Graph>
83 checkBidirPetersen(G, num);
86 template <class Graph>
87 void checkGraphIterators(const Graph& graph) {
88 typedef typename Graph::Node Node;
89 typedef typename Graph::NodeIt NodeIt;
90 typedef typename Graph::Edge Edge;
91 typedef typename Graph::EdgeIt EdgeIt;
92 typedef typename Graph::InEdgeIt InEdgeIt;
93 typedef typename Graph::OutEdgeIt OutEdgeIt;
94 typedef ConEdgeIt<Graph> ConEdgeIt;
96 for (NodeIt it(graph); it != INVALID; ++it) {}
100 ///\todo Check target(), source() as well;