|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2007 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
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. |
|
12 * |
|
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 |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_TEST_GRAPH_TEST_H |
|
20 #define LEMON_TEST_GRAPH_TEST_H |
|
21 |
|
22 //#include <lemon/graph_utils.h> |
|
23 #include "test_tools.h" |
|
24 |
|
25 //! \ingroup misc |
|
26 //! \file |
|
27 //! \brief Some utility and test cases to test digraph classes. |
|
28 namespace lemon { |
|
29 |
|
30 ///Structure returned by \ref addPetersen(). |
|
31 |
|
32 ///Structure returned by \ref addPetersen(). |
|
33 /// |
|
34 template<class Digraph> |
|
35 struct PetStruct |
|
36 { |
|
37 ///Vector containing the outer nodes. |
|
38 std::vector<typename Digraph::Node> outer; |
|
39 ///Vector containing the inner nodes. |
|
40 std::vector<typename Digraph::Node> inner; |
|
41 ///Vector containing the edges of the inner circle. |
|
42 std::vector<typename Digraph::Arc> incir; |
|
43 ///Vector containing the edges of the outer circle. |
|
44 std::vector<typename Digraph::Arc> outcir; |
|
45 ///Vector containing the chord edges. |
|
46 std::vector<typename Digraph::Arc> chords; |
|
47 }; |
|
48 |
|
49 |
|
50 |
|
51 ///Adds a Petersen graph to \c G. |
|
52 |
|
53 ///Adds a Petersen graph to \c G. |
|
54 ///\return The nodes and edges of the generated graph. |
|
55 |
|
56 template<typename Digraph> |
|
57 PetStruct<Digraph> addPetersen(Digraph &G,int num = 5) |
|
58 { |
|
59 PetStruct<Digraph> n; |
|
60 |
|
61 for(int i=0;i<num;i++) { |
|
62 n.outer.push_back(G.addNode()); |
|
63 n.inner.push_back(G.addNode()); |
|
64 } |
|
65 |
|
66 for(int i=0;i<num;i++) { |
|
67 n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); |
|
68 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num])); |
|
69 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num])); |
|
70 } |
|
71 return n; |
|
72 } |
|
73 |
|
74 /// \brief Adds to the digraph the reverse pair of all edges. |
|
75 /// |
|
76 /// Adds to the digraph the reverse pair of all edges. |
|
77 /// |
|
78 template<class Digraph> |
|
79 void bidirDigraph(Digraph &G) |
|
80 { |
|
81 typedef typename Digraph::Arc Arc; |
|
82 typedef typename Digraph::ArcIt ArcIt; |
|
83 |
|
84 std::vector<Arc> ee; |
|
85 |
|
86 for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); |
|
87 |
|
88 for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++) |
|
89 G.addArc(G.target(*p),G.source(*p)); |
|
90 } |
|
91 |
|
92 |
|
93 /// \brief Checks the bidirectioned Petersen graph. |
|
94 /// |
|
95 /// Checks the bidirectioned Petersen graph. |
|
96 /// |
|
97 template<class Digraph> |
|
98 void checkBidirPetersen(Digraph &G, int num = 5) |
|
99 { |
|
100 typedef typename Digraph::Node Node; |
|
101 |
|
102 typedef typename Digraph::ArcIt ArcIt; |
|
103 typedef typename Digraph::NodeIt NodeIt; |
|
104 |
|
105 checkDigraphNodeList(G, 2 * num); |
|
106 checkDigraphArcList(G, 6 * num); |
|
107 |
|
108 for(NodeIt n(G);n!=INVALID;++n) { |
|
109 checkDigraphInArcList(G, n, 3); |
|
110 checkDigraphOutArcList(G, n, 3); |
|
111 } |
|
112 } |
|
113 |
|
114 template<class Digraph> void checkDigraphNodeList(Digraph &G, int nn) |
|
115 { |
|
116 typename Digraph::NodeIt n(G); |
|
117 for(int i=0;i<nn;i++) { |
|
118 check(n!=INVALID,"Wrong Node list linking."); |
|
119 ++n; |
|
120 } |
|
121 check(n==INVALID,"Wrong Node list linking."); |
|
122 } |
|
123 |
|
124 template<class Digraph> |
|
125 void checkDigraphArcList(Digraph &G, int nn) |
|
126 { |
|
127 typedef typename Digraph::ArcIt ArcIt; |
|
128 |
|
129 ArcIt e(G); |
|
130 for(int i=0;i<nn;i++) { |
|
131 check(e!=INVALID,"Wrong Arc list linking."); |
|
132 ++e; |
|
133 } |
|
134 check(e==INVALID,"Wrong Arc list linking."); |
|
135 } |
|
136 |
|
137 template<class Digraph> |
|
138 void checkDigraphOutArcList(Digraph &G, typename Digraph::Node n, int nn) |
|
139 { |
|
140 typename Digraph::OutArcIt e(G,n); |
|
141 for(int i=0;i<nn;i++) { |
|
142 check(e!=INVALID,"Wrong OutArc list linking."); |
|
143 check(n==G.source(e), "Wrong OutArc list linking."); |
|
144 ++e; |
|
145 } |
|
146 check(e==INVALID,"Wrong OutArc list linking."); |
|
147 } |
|
148 |
|
149 template<class Digraph> void |
|
150 checkDigraphInArcList(Digraph &G, typename Digraph::Node n, int nn) |
|
151 { |
|
152 typename Digraph::InArcIt e(G,n); |
|
153 for(int i=0;i<nn;i++) { |
|
154 check(e!=INVALID,"Wrong InArc list linking."); |
|
155 check(n==G.target(e), "Wrong InArc list linking."); |
|
156 ++e; |
|
157 } |
|
158 check(e==INVALID,"Wrong InArc list linking."); |
|
159 } |
|
160 |
|
161 template <class Digraph> |
|
162 void checkDigraph() { |
|
163 const int num = 5; |
|
164 Digraph G; |
|
165 addPetersen(G, num); |
|
166 bidirDigraph(G); |
|
167 checkBidirPetersen(G, num); |
|
168 } |
|
169 |
|
170 template <class Digraph> |
|
171 void checkDigraphIterators(const Digraph& digraph) { |
|
172 typedef typename Digraph::Node Node; |
|
173 typedef typename Digraph::NodeIt NodeIt; |
|
174 typedef typename Digraph::Arc Arc; |
|
175 typedef typename Digraph::ArcIt ArcIt; |
|
176 typedef typename Digraph::InArcIt InArcIt; |
|
177 typedef typename Digraph::OutArcIt OutArcIt; |
|
178 // typedef ConArcIt<Digraph> ConArcIt; |
|
179 } |
|
180 |
|
181 ///\file |
|
182 ///\todo Check target(), source() as well; |
|
183 |
|
184 |
|
185 } //namespace lemon |
|
186 |
|
187 |
|
188 #endif |