20 #include <lemon/list_graph.h> |
20 #include <lemon/list_graph.h> |
21 #include <lemon/smart_graph.h> |
21 #include <lemon/smart_graph.h> |
22 // #include <lemon/full_graph.h> |
22 // #include <lemon/full_graph.h> |
23 // #include <lemon/grid_graph.h> |
23 // #include <lemon/grid_graph.h> |
24 |
24 |
25 #include <lemon/graph_utils.h> |
|
26 |
|
27 #include "test_tools.h" |
25 #include "test_tools.h" |
28 |
26 #include "graph_test.h" |
|
27 #include "graph_maps_test.h" |
29 |
28 |
30 using namespace lemon; |
29 using namespace lemon; |
31 using namespace lemon::concepts; |
30 using namespace lemon::concepts; |
32 |
31 |
33 void check_concepts() { |
32 void check_concepts() { |
34 |
33 { // Checking graph components |
35 { // checking digraph components |
|
36 checkConcept<BaseGraphComponent, BaseGraphComponent >(); |
34 checkConcept<BaseGraphComponent, BaseGraphComponent >(); |
37 |
35 |
38 checkConcept<IDableGraphComponent<>, |
36 checkConcept<IDableGraphComponent<>, |
39 IDableGraphComponent<> >(); |
37 IDableGraphComponent<> >(); |
40 |
38 |
41 checkConcept<IterableGraphComponent<>, |
39 checkConcept<IterableGraphComponent<>, |
42 IterableGraphComponent<> >(); |
40 IterableGraphComponent<> >(); |
43 |
41 |
44 checkConcept<MappableGraphComponent<>, |
42 checkConcept<MappableGraphComponent<>, |
45 MappableGraphComponent<> >(); |
43 MappableGraphComponent<> >(); |
46 |
44 } |
47 } |
45 { // Checking skeleton graph |
48 { |
46 checkConcept<Graph, Graph>(); |
49 checkConcept<Graph, ListGraph>(); |
47 } |
50 checkConcept<Graph, SmartGraph>(); |
48 { // Checking ListGraph |
51 // checkConcept<Graph, FullGraph>(); |
49 checkConcept<Graph, ListGraph>(); |
52 // checkConcept<Graph, Graph>(); |
50 checkConcept<AlterableGraphComponent<>, ListGraph>(); |
53 // checkConcept<Graph, GridGraph>(); |
51 checkConcept<ExtendableGraphComponent<>, ListGraph>(); |
54 } |
52 checkConcept<ClearableGraphComponent<>, ListGraph>(); |
|
53 checkConcept<ErasableGraphComponent<>, ListGraph>(); |
|
54 checkGraphIterators<ListGraph>(); |
|
55 } |
|
56 { // Checking SmartGraph |
|
57 checkConcept<Graph, SmartGraph>(); |
|
58 checkConcept<AlterableGraphComponent<>, SmartGraph>(); |
|
59 checkConcept<ExtendableGraphComponent<>, SmartGraph>(); |
|
60 checkConcept<ClearableGraphComponent<>, SmartGraph>(); |
|
61 checkGraphIterators<SmartGraph>(); |
|
62 } |
|
63 // { // Checking FullGraph |
|
64 // checkConcept<Graph, FullGraph>(); |
|
65 // checkGraphIterators<FullGraph>(); |
|
66 // } |
|
67 // { // Checking GridGraph |
|
68 // checkConcept<Graph, GridGraph>(); |
|
69 // checkGraphIterators<GridGraph>(); |
|
70 // } |
55 } |
71 } |
56 |
72 |
57 template <typename Graph> |
73 template <typename Graph> |
58 void check_item_counts(Graph &g, int n, int e) { |
74 void check_graph_validity() { |
59 int nn = 0; |
|
60 for (typename Graph::NodeIt it(g); it != INVALID; ++it) { |
|
61 ++nn; |
|
62 } |
|
63 |
|
64 check(nn == n, "Wrong node number."); |
|
65 // check(countNodes(g) == n, "Wrong node number."); |
|
66 |
|
67 int ee = 0; |
|
68 for (typename Graph::ArcIt it(g); it != INVALID; ++it) { |
|
69 ++ee; |
|
70 } |
|
71 |
|
72 check(ee == 2*e, "Wrong arc number."); |
|
73 // check(countArcs(g) == 2*e, "Wrong arc number."); |
|
74 |
|
75 int uee = 0; |
|
76 for (typename Graph::EdgeIt it(g); it != INVALID; ++it) { |
|
77 ++uee; |
|
78 } |
|
79 |
|
80 check(uee == e, "Wrong edge number."); |
|
81 // check(countEdges(g) == e, "Wrong edge number."); |
|
82 } |
|
83 |
|
84 template <typename Graph> |
|
85 void check_graph_counts() { |
|
86 |
|
87 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
75 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
88 Graph g; |
76 Graph g; |
89 |
|
90 check_item_counts(g,0,0); |
|
91 |
77 |
92 Node |
78 Node |
93 n1 = g.addNode(), |
79 n1 = g.addNode(), |
94 n2 = g.addNode(), |
80 n2 = g.addNode(), |
95 n3 = g.addNode(); |
81 n3 = g.addNode(); |
96 |
82 |
97 Edge |
83 Edge |
98 e1 = g.addEdge(n1, n2), |
84 e1 = g.addEdge(n1, n2), |
99 e2 = g.addEdge(n2, n3); |
85 e2 = g.addEdge(n2, n3); |
100 |
86 |
101 check_item_counts(g,3,2); |
87 check(g.valid(n1), "Wrong validity check"); |
|
88 check(g.valid(e1), "Wrong validity check"); |
|
89 check(g.valid(g.direct(e1, true)), "Wrong validity check"); |
|
90 |
|
91 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); |
|
92 check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); |
|
93 check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
102 } |
94 } |
103 |
95 |
104 template <typename Graph> |
96 template <typename Graph> |
105 void check_graph_validity() { |
97 void check_graph_validity_erase() { |
106 |
|
107 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
98 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
108 Graph g; |
99 Graph g; |
109 |
|
110 check_item_counts(g,0,0); |
|
111 |
100 |
112 Node |
101 Node |
113 n1 = g.addNode(), |
102 n1 = g.addNode(), |
114 n2 = g.addNode(), |
103 n2 = g.addNode(), |
115 n3 = g.addNode(); |
104 n3 = g.addNode(); |
116 |
105 |
117 Edge |
106 Edge |
118 e1 = g.addEdge(n1, n2), |
107 e1 = g.addEdge(n1, n2), |
119 e2 = g.addEdge(n2, n3); |
108 e2 = g.addEdge(n2, n3); |
120 |
109 |
121 check(g.valid(n1), "Validity check"); |
110 check(g.valid(n1), "Wrong validity check"); |
122 check(g.valid(e1), "Validity check"); |
111 check(g.valid(e1), "Wrong validity check"); |
123 check(g.valid(g.direct(e1, true)), "Validity check"); |
112 check(g.valid(g.direct(e1, true)), "Wrong validity check"); |
124 |
|
125 check(!g.valid(g.nodeFromId(-1)), "Validity check"); |
|
126 check(!g.valid(g.edgeFromId(-1)), "Validity check"); |
|
127 check(!g.valid(g.arcFromId(-1)), "Validity check"); |
|
128 |
|
129 } |
|
130 |
|
131 template <typename Graph> |
|
132 void check_graph_validity_erase() { |
|
133 |
|
134 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
135 Graph g; |
|
136 |
|
137 check_item_counts(g,0,0); |
|
138 |
|
139 Node |
|
140 n1 = g.addNode(), |
|
141 n2 = g.addNode(), |
|
142 n3 = g.addNode(); |
|
143 |
|
144 Edge |
|
145 e1 = g.addEdge(n1, n2), |
|
146 e2 = g.addEdge(n2, n3); |
|
147 |
|
148 check(g.valid(n1), "Validity check"); |
|
149 check(g.valid(e1), "Validity check"); |
|
150 check(g.valid(g.direct(e1, true)), "Validity check"); |
|
151 |
113 |
152 g.erase(n1); |
114 g.erase(n1); |
153 |
115 |
154 check(!g.valid(n1), "Validity check"); |
116 check(!g.valid(n1), "Wrong validity check"); |
155 check(g.valid(n2), "Validity check"); |
117 check(g.valid(n2), "Wrong validity check"); |
156 check(g.valid(n3), "Validity check"); |
118 check(g.valid(n3), "Wrong validity check"); |
157 check(!g.valid(e1), "Validity check"); |
119 check(!g.valid(e1), "Wrong validity check"); |
158 check(g.valid(e2), "Validity check"); |
120 check(g.valid(e2), "Wrong validity check"); |
159 |
121 |
160 check(!g.valid(g.nodeFromId(-1)), "Validity check"); |
122 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); |
161 check(!g.valid(g.edgeFromId(-1)), "Validity check"); |
123 check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); |
162 check(!g.valid(g.arcFromId(-1)), "Validity check"); |
124 check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
163 |
125 } |
164 } |
|
165 |
|
166 |
|
167 |
126 |
168 // void checkGridGraph(const GridGraph& g, int w, int h) { |
127 // void checkGridGraph(const GridGraph& g, int w, int h) { |
169 // check(g.width() == w, "Wrong width"); |
128 // check(g.width() == w, "Wrong width"); |
170 // check(g.height() == h, "Wrong height"); |
129 // check(g.height() == h, "Wrong height"); |
171 |
130 |