lemon-main: test/adaptors_test.cc@eba5aa390aca (annotated)

deba@416	1	/* -- mode: C++; indent-tabs-mode: nil; --
deba@414	2	*
deba@416	3	* This file is a part of LEMON, a generic C++ optimization library.
deba@414	4	*
alpar@1092	5	* Copyright (C) 2003-2013
deba@414	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@414	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@414	8	*
deba@414	9	* Permission to use, modify and distribute this software is granted
deba@414	10	* provided that this copyright notice appears in all copies. For
deba@414	11	* precise terms see the accompanying LICENSE file.
deba@414	12	*
deba@414	13	* This software is provided "AS IS" with no warranty of any kind,
deba@414	14	* express or implied, and with no claim as to its suitability for any
deba@414	15	* purpose.
deba@414	16	*
deba@414	17	*/
deba@414	18
kpeter@463	19	#include <iostream>
kpeter@463	20	#include <limits>
deba@414	21
kpeter@463	22	#include <lemon/list_graph.h>
kpeter@463	23	#include <lemon/grid_graph.h>
deba@414	24	#include <lemon/bfs.h>
deba@414	25	#include <lemon/path.h>
deba@414	26
kpeter@463	27	#include <lemon/concepts/digraph.h>
kpeter@463	28	#include <lemon/concepts/graph.h>
kpeter@463	29	#include <lemon/concepts/graph_components.h>
kpeter@463	30	#include <lemon/concepts/maps.h>
kpeter@463	31	#include <lemon/concept_check.h>
kpeter@463	32
kpeter@463	33	#include <lemon/adaptors.h>
kpeter@463	34
kpeter@463	35	#include "test/test_tools.h"
kpeter@463	36	#include "test/graph_test.h"
deba@414	37
deba@414	38	using namespace lemon;
deba@414	39
deba@416	40	void checkReverseDigraph() {
kpeter@463	41	// Check concepts
deba@416	42	checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
kpeter@463	43	checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();
kpeter@463	44	checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463	45	ReverseDigraph<ListDigraph> >();
kpeter@463	46	checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463	47	ReverseDigraph<ListDigraph> >();
kpeter@463	48	checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463	49	ReverseDigraph<ListDigraph> >();
kpeter@463	50	checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463	51	ReverseDigraph<ListDigraph> >();
deba@414	52
kpeter@463	53	// Create a digraph and an adaptor
deba@414	54	typedef ListDigraph Digraph;
deba@416	55	typedef ReverseDigraph<Digraph> Adaptor;
deba@414	56
deba@414	57	Digraph digraph;
deba@414	58	Adaptor adaptor(digraph);
deba@414	59
kpeter@463	60	// Add nodes and arcs to the original digraph
deba@414	61	Digraph::Node n1 = digraph.addNode();
deba@414	62	Digraph::Node n2 = digraph.addNode();
deba@414	63	Digraph::Node n3 = digraph.addNode();
deba@414	64
deba@414	65	Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414	66	Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414	67	Digraph::Arc a3 = digraph.addArc(n2, n3);
alpar@1083	68	::lemon::ignore_unused_variable_warning(a3);
deba@416	69
kpeter@463	70	// Check the adaptor
deba@414	71	checkGraphNodeList(adaptor, 3);
deba@414	72	checkGraphArcList(adaptor, 3);
deba@414	73	checkGraphConArcList(adaptor, 3);
deba@414	74
deba@414	75	checkGraphOutArcList(adaptor, n1, 0);
deba@414	76	checkGraphOutArcList(adaptor, n2, 1);
deba@414	77	checkGraphOutArcList(adaptor, n3, 2);
deba@414	78
deba@414	79	checkGraphInArcList(adaptor, n1, 2);
deba@414	80	checkGraphInArcList(adaptor, n2, 1);
deba@414	81	checkGraphInArcList(adaptor, n3, 0);
deba@414	82
deba@414	83	checkNodeIds(adaptor);
deba@414	84	checkArcIds(adaptor);
deba@414	85
deba@414	86	checkGraphNodeMap(adaptor);
deba@414	87	checkGraphArcMap(adaptor);
deba@414	88
kpeter@463	89	// Check the orientation of the arcs
deba@414	90	for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414	91	check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
deba@414	92	check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
deba@414	93	}
kpeter@463	94
kpeter@463	95	// Add and erase nodes and arcs in the digraph through the adaptor
kpeter@463	96	Adaptor::Node n4 = adaptor.addNode();
kpeter@463	97
kpeter@463	98	Adaptor::Arc a4 = adaptor.addArc(n4, n3);
kpeter@463	99	Adaptor::Arc a5 = adaptor.addArc(n2, n4);
kpeter@463	100	Adaptor::Arc a6 = adaptor.addArc(n2, n4);
kpeter@463	101	Adaptor::Arc a7 = adaptor.addArc(n1, n4);
kpeter@463	102	Adaptor::Arc a8 = adaptor.addArc(n1, n2);
alpar@1083	103	::lemon::ignore_unused_variable_warning(a6,a7,a8);
kpeter@463	104
kpeter@463	105	adaptor.erase(a1);
kpeter@463	106	adaptor.erase(n3);
kpeter@463	107
kpeter@463	108	// Check the adaptor
kpeter@463	109	checkGraphNodeList(adaptor, 3);
kpeter@463	110	checkGraphArcList(adaptor, 4);
kpeter@463	111	checkGraphConArcList(adaptor, 4);
kpeter@463	112
kpeter@463	113	checkGraphOutArcList(adaptor, n1, 2);
kpeter@463	114	checkGraphOutArcList(adaptor, n2, 2);
kpeter@463	115	checkGraphOutArcList(adaptor, n4, 0);
kpeter@463	116
kpeter@463	117	checkGraphInArcList(adaptor, n1, 0);
kpeter@463	118	checkGraphInArcList(adaptor, n2, 1);
kpeter@463	119	checkGraphInArcList(adaptor, n4, 3);
kpeter@463	120
kpeter@463	121	checkNodeIds(adaptor);
kpeter@463	122	checkArcIds(adaptor);
kpeter@463	123
kpeter@463	124	checkGraphNodeMap(adaptor);
kpeter@463	125	checkGraphArcMap(adaptor);
kpeter@463	126
kpeter@463	127	// Check the digraph
kpeter@463	128	checkGraphNodeList(digraph, 3);
kpeter@463	129	checkGraphArcList(digraph, 4);
kpeter@463	130	checkGraphConArcList(digraph, 4);
kpeter@463	131
kpeter@463	132	checkGraphOutArcList(digraph, n1, 0);
kpeter@463	133	checkGraphOutArcList(digraph, n2, 1);
kpeter@463	134	checkGraphOutArcList(digraph, n4, 3);
kpeter@463	135
kpeter@463	136	checkGraphInArcList(digraph, n1, 2);
kpeter@463	137	checkGraphInArcList(digraph, n2, 2);
kpeter@463	138	checkGraphInArcList(digraph, n4, 0);
kpeter@463	139
kpeter@463	140	checkNodeIds(digraph);
kpeter@463	141	checkArcIds(digraph);
kpeter@463	142
kpeter@463	143	checkGraphNodeMap(digraph);
kpeter@463	144	checkGraphArcMap(digraph);
kpeter@463	145
kpeter@463	146	// Check the conversion of nodes and arcs
kpeter@463	147	Digraph::Node nd = n4;
kpeter@1197	148	::lemon::ignore_unused_variable_warning(nd);
kpeter@463	149	nd = n4;
kpeter@463	150	Adaptor::Node na = n1;
kpeter@1197	151	::lemon::ignore_unused_variable_warning(na);
kpeter@463	152	na = n2;
kpeter@463	153	Digraph::Arc ad = a4;
kpeter@1197	154	::lemon::ignore_unused_variable_warning(ad);
kpeter@463	155	ad = a5;
kpeter@463	156	Adaptor::Arc aa = a1;
kpeter@1197	157	::lemon::ignore_unused_variable_warning(aa);
kpeter@463	158	aa = a2;
deba@414	159	}
deba@414	160
deba@416	161	void checkSubDigraph() {
kpeter@463	162	// Check concepts
kpeter@463	163	checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();
kpeter@463	164	checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
kpeter@463	165	checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463	166	SubDigraph<ListDigraph> >();
kpeter@463	167	checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463	168	SubDigraph<ListDigraph> >();
kpeter@463	169	checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463	170	SubDigraph<ListDigraph> >();
kpeter@463	171	checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463	172	SubDigraph<ListDigraph> >();
deba@414	173
kpeter@463	174	// Create a digraph and an adaptor
deba@414	175	typedef ListDigraph Digraph;
deba@414	176	typedef Digraph::NodeMap<bool> NodeFilter;
deba@414	177	typedef Digraph::ArcMap<bool> ArcFilter;
deba@416	178	typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
deba@414	179
deba@414	180	Digraph digraph;
deba@414	181	NodeFilter node_filter(digraph);
deba@414	182	ArcFilter arc_filter(digraph);
deba@414	183	Adaptor adaptor(digraph, node_filter, arc_filter);
deba@414	184
kpeter@463	185	// Add nodes and arcs to the original digraph and the adaptor
deba@414	186	Digraph::Node n1 = digraph.addNode();
deba@414	187	Digraph::Node n2 = digraph.addNode();
kpeter@463	188	Adaptor::Node n3 = adaptor.addNode();
kpeter@463	189
kpeter@463	190	node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
deba@414	191
deba@414	192	Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414	193	Digraph::Arc a2 = digraph.addArc(n1, n3);
kpeter@463	194	Adaptor::Arc a3 = adaptor.addArc(n2, n3);
deba@414	195
deba@414	196	arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
alpar@440	197
deba@414	198	checkGraphNodeList(adaptor, 3);
deba@414	199	checkGraphArcList(adaptor, 3);
deba@414	200	checkGraphConArcList(adaptor, 3);
deba@414	201
deba@414	202	checkGraphOutArcList(adaptor, n1, 2);
deba@414	203	checkGraphOutArcList(adaptor, n2, 1);
deba@414	204	checkGraphOutArcList(adaptor, n3, 0);
deba@414	205
deba@414	206	checkGraphInArcList(adaptor, n1, 0);
deba@414	207	checkGraphInArcList(adaptor, n2, 1);
deba@414	208	checkGraphInArcList(adaptor, n3, 2);
deba@414	209
deba@414	210	checkNodeIds(adaptor);
deba@414	211	checkArcIds(adaptor);
deba@414	212
deba@414	213	checkGraphNodeMap(adaptor);
deba@414	214	checkGraphArcMap(adaptor);
deba@414	215
kpeter@463	216	// Hide an arc
kpeter@463	217	adaptor.status(a2, false);
kpeter@463	218	adaptor.disable(a3);
kpeter@463	219	if (!adaptor.status(a3)) adaptor.enable(a3);
deba@414	220
deba@414	221	checkGraphNodeList(adaptor, 3);
deba@414	222	checkGraphArcList(adaptor, 2);
deba@414	223	checkGraphConArcList(adaptor, 2);
deba@414	224
deba@414	225	checkGraphOutArcList(adaptor, n1, 1);
deba@414	226	checkGraphOutArcList(adaptor, n2, 1);
deba@414	227	checkGraphOutArcList(adaptor, n3, 0);
deba@414	228
deba@414	229	checkGraphInArcList(adaptor, n1, 0);
deba@414	230	checkGraphInArcList(adaptor, n2, 1);
deba@414	231	checkGraphInArcList(adaptor, n3, 1);
deba@414	232
deba@414	233	checkNodeIds(adaptor);
deba@414	234	checkArcIds(adaptor);
deba@414	235
deba@414	236	checkGraphNodeMap(adaptor);
deba@414	237	checkGraphArcMap(adaptor);
deba@414	238
kpeter@463	239	// Hide a node
kpeter@463	240	adaptor.status(n1, false);
kpeter@463	241	adaptor.disable(n3);
kpeter@463	242	if (!adaptor.status(n3)) adaptor.enable(n3);
kpeter@463	243
kpeter@463	244	checkGraphNodeList(adaptor, 2);
kpeter@463	245	checkGraphArcList(adaptor, 1);
kpeter@463	246	checkGraphConArcList(adaptor, 1);
kpeter@463	247
kpeter@463	248	checkGraphOutArcList(adaptor, n2, 1);
kpeter@463	249	checkGraphOutArcList(adaptor, n3, 0);
kpeter@463	250
kpeter@463	251	checkGraphInArcList(adaptor, n2, 0);
kpeter@463	252	checkGraphInArcList(adaptor, n3, 1);
kpeter@463	253
kpeter@463	254	checkNodeIds(adaptor);
kpeter@463	255	checkArcIds(adaptor);
kpeter@463	256
kpeter@463	257	checkGraphNodeMap(adaptor);
kpeter@463	258	checkGraphArcMap(adaptor);
kpeter@463	259
kpeter@463	260	// Hide all nodes and arcs
kpeter@463	261	node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
kpeter@463	262	arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
kpeter@463	263
kpeter@463	264	checkGraphNodeList(adaptor, 0);
kpeter@463	265	checkGraphArcList(adaptor, 0);
kpeter@463	266	checkGraphConArcList(adaptor, 0);
kpeter@463	267
kpeter@463	268	checkNodeIds(adaptor);
kpeter@463	269	checkArcIds(adaptor);
kpeter@463	270
kpeter@463	271	checkGraphNodeMap(adaptor);
kpeter@463	272	checkGraphArcMap(adaptor);
kpeter@463	273
kpeter@463	274	// Check the conversion of nodes and arcs
kpeter@463	275	Digraph::Node nd = n3;
kpeter@1197	276	::lemon::ignore_unused_variable_warning(nd);
kpeter@463	277	nd = n3;
kpeter@463	278	Adaptor::Node na = n1;
kpeter@1197	279	::lemon::ignore_unused_variable_warning(na);
kpeter@463	280	na = n2;
kpeter@463	281	Digraph::Arc ad = a3;
kpeter@1197	282	::lemon::ignore_unused_variable_warning(ad);
kpeter@463	283	ad = a3;
kpeter@463	284	Adaptor::Arc aa = a1;
kpeter@1197	285	::lemon::ignore_unused_variable_warning(aa);
kpeter@463	286	aa = a2;
kpeter@463	287	}
kpeter@463	288
kpeter@463	289	void checkFilterNodes1() {
kpeter@463	290	// Check concepts
kpeter@463	291	checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();
kpeter@463	292	checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
kpeter@463	293	checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463	294	FilterNodes<ListDigraph> >();
kpeter@463	295	checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463	296	FilterNodes<ListDigraph> >();
kpeter@463	297	checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463	298	FilterNodes<ListDigraph> >();
kpeter@463	299	checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463	300	FilterNodes<ListDigraph> >();
kpeter@463	301
kpeter@463	302	// Create a digraph and an adaptor
kpeter@463	303	typedef ListDigraph Digraph;
kpeter@463	304	typedef Digraph::NodeMap<bool> NodeFilter;
kpeter@463	305	typedef FilterNodes<Digraph, NodeFilter> Adaptor;
kpeter@463	306
kpeter@463	307	Digraph digraph;
kpeter@463	308	NodeFilter node_filter(digraph);
kpeter@463	309	Adaptor adaptor(digraph, node_filter);
kpeter@463	310
kpeter@463	311	// Add nodes and arcs to the original digraph and the adaptor
kpeter@463	312	Digraph::Node n1 = digraph.addNode();
kpeter@463	313	Digraph::Node n2 = digraph.addNode();
kpeter@463	314	Adaptor::Node n3 = adaptor.addNode();
kpeter@463	315
kpeter@463	316	node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
kpeter@463	317
kpeter@463	318	Digraph::Arc a1 = digraph.addArc(n1, n2);
kpeter@463	319	Digraph::Arc a2 = digraph.addArc(n1, n3);
kpeter@463	320	Adaptor::Arc a3 = adaptor.addArc(n2, n3);
kpeter@463	321
kpeter@463	322	checkGraphNodeList(adaptor, 3);
kpeter@463	323	checkGraphArcList(adaptor, 3);
kpeter@463	324	checkGraphConArcList(adaptor, 3);
kpeter@463	325
kpeter@463	326	checkGraphOutArcList(adaptor, n1, 2);
kpeter@463	327	checkGraphOutArcList(adaptor, n2, 1);
kpeter@463	328	checkGraphOutArcList(adaptor, n3, 0);
kpeter@463	329
kpeter@463	330	checkGraphInArcList(adaptor, n1, 0);
kpeter@463	331	checkGraphInArcList(adaptor, n2, 1);
kpeter@463	332	checkGraphInArcList(adaptor, n3, 2);
kpeter@463	333
kpeter@463	334	checkNodeIds(adaptor);
kpeter@463	335	checkArcIds(adaptor);
kpeter@463	336
kpeter@463	337	checkGraphNodeMap(adaptor);
kpeter@463	338	checkGraphArcMap(adaptor);
kpeter@463	339
kpeter@463	340	// Hide a node
kpeter@463	341	adaptor.status(n1, false);
kpeter@463	342	adaptor.disable(n3);
kpeter@463	343	if (!adaptor.status(n3)) adaptor.enable(n3);
kpeter@463	344
kpeter@463	345	checkGraphNodeList(adaptor, 2);
kpeter@463	346	checkGraphArcList(adaptor, 1);
kpeter@463	347	checkGraphConArcList(adaptor, 1);
kpeter@463	348
kpeter@463	349	checkGraphOutArcList(adaptor, n2, 1);
kpeter@463	350	checkGraphOutArcList(adaptor, n3, 0);
kpeter@463	351
kpeter@463	352	checkGraphInArcList(adaptor, n2, 0);
kpeter@463	353	checkGraphInArcList(adaptor, n3, 1);
kpeter@463	354
kpeter@463	355	checkNodeIds(adaptor);
kpeter@463	356	checkArcIds(adaptor);
kpeter@463	357
kpeter@463	358	checkGraphNodeMap(adaptor);
kpeter@463	359	checkGraphArcMap(adaptor);
kpeter@463	360
kpeter@463	361	// Hide all nodes
kpeter@463	362	node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
kpeter@463	363
kpeter@463	364	checkGraphNodeList(adaptor, 0);
kpeter@463	365	checkGraphArcList(adaptor, 0);
kpeter@463	366	checkGraphConArcList(adaptor, 0);
kpeter@463	367
kpeter@463	368	checkNodeIds(adaptor);
kpeter@463	369	checkArcIds(adaptor);
kpeter@463	370
kpeter@463	371	checkGraphNodeMap(adaptor);
kpeter@463	372	checkGraphArcMap(adaptor);
kpeter@463	373
kpeter@463	374	// Check the conversion of nodes and arcs
kpeter@463	375	Digraph::Node nd = n3;
kpeter@1197	376	::lemon::ignore_unused_variable_warning(nd);
kpeter@463	377	nd = n3;
kpeter@463	378	Adaptor::Node na = n1;
kpeter@1197	379	::lemon::ignore_unused_variable_warning(na);
kpeter@463	380	na = n2;
kpeter@463	381	Digraph::Arc ad = a3;
kpeter@1197	382	::lemon::ignore_unused_variable_warning(ad);
kpeter@463	383	ad = a3;
kpeter@463	384	Adaptor::Arc aa = a1;
kpeter@1197	385	::lemon::ignore_unused_variable_warning(aa);
kpeter@463	386	aa = a2;
kpeter@463	387	}
kpeter@463	388
kpeter@463	389	void checkFilterArcs() {
kpeter@463	390	// Check concepts
kpeter@463	391	checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();
kpeter@463	392	checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
kpeter@463	393	checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463	394	FilterArcs<ListDigraph> >();
kpeter@463	395	checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463	396	FilterArcs<ListDigraph> >();
kpeter@463	397	checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463	398	FilterArcs<ListDigraph> >();
kpeter@463	399	checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463	400	FilterArcs<ListDigraph> >();
kpeter@463	401
kpeter@463	402	// Create a digraph and an adaptor
kpeter@463	403	typedef ListDigraph Digraph;
kpeter@463	404	typedef Digraph::ArcMap<bool> ArcFilter;
kpeter@463	405	typedef FilterArcs<Digraph, ArcFilter> Adaptor;
kpeter@463	406
kpeter@463	407	Digraph digraph;
kpeter@463	408	ArcFilter arc_filter(digraph);
kpeter@463	409	Adaptor adaptor(digraph, arc_filter);
kpeter@463	410
kpeter@463	411	// Add nodes and arcs to the original digraph and the adaptor
kpeter@463	412	Digraph::Node n1 = digraph.addNode();
kpeter@463	413	Digraph::Node n2 = digraph.addNode();
kpeter@463	414	Adaptor::Node n3 = adaptor.addNode();
kpeter@463	415
kpeter@463	416	Digraph::Arc a1 = digraph.addArc(n1, n2);
kpeter@463	417	Digraph::Arc a2 = digraph.addArc(n1, n3);
kpeter@463	418	Adaptor::Arc a3 = adaptor.addArc(n2, n3);
kpeter@463	419
kpeter@463	420	arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
kpeter@463	421
kpeter@463	422	checkGraphNodeList(adaptor, 3);
kpeter@463	423	checkGraphArcList(adaptor, 3);
kpeter@463	424	checkGraphConArcList(adaptor, 3);
kpeter@463	425
kpeter@463	426	checkGraphOutArcList(adaptor, n1, 2);
kpeter@463	427	checkGraphOutArcList(adaptor, n2, 1);
kpeter@463	428	checkGraphOutArcList(adaptor, n3, 0);
kpeter@463	429
kpeter@463	430	checkGraphInArcList(adaptor, n1, 0);
kpeter@463	431	checkGraphInArcList(adaptor, n2, 1);
kpeter@463	432	checkGraphInArcList(adaptor, n3, 2);
kpeter@463	433
kpeter@463	434	checkNodeIds(adaptor);
kpeter@463	435	checkArcIds(adaptor);
kpeter@463	436
kpeter@463	437	checkGraphNodeMap(adaptor);
kpeter@463	438	checkGraphArcMap(adaptor);
kpeter@463	439
kpeter@463	440	// Hide an arc
kpeter@463	441	adaptor.status(a2, false);
kpeter@463	442	adaptor.disable(a3);
kpeter@463	443	if (!adaptor.status(a3)) adaptor.enable(a3);
kpeter@463	444
kpeter@463	445	checkGraphNodeList(adaptor, 3);
kpeter@463	446	checkGraphArcList(adaptor, 2);
kpeter@463	447	checkGraphConArcList(adaptor, 2);
kpeter@463	448
kpeter@463	449	checkGraphOutArcList(adaptor, n1, 1);
kpeter@463	450	checkGraphOutArcList(adaptor, n2, 1);
kpeter@463	451	checkGraphOutArcList(adaptor, n3, 0);
kpeter@463	452
kpeter@463	453	checkGraphInArcList(adaptor, n1, 0);
kpeter@463	454	checkGraphInArcList(adaptor, n2, 1);
kpeter@463	455	checkGraphInArcList(adaptor, n3, 1);
kpeter@463	456
kpeter@463	457	checkNodeIds(adaptor);
kpeter@463	458	checkArcIds(adaptor);
kpeter@463	459
kpeter@463	460	checkGraphNodeMap(adaptor);
kpeter@463	461	checkGraphArcMap(adaptor);
kpeter@463	462
kpeter@463	463	// Hide all arcs
deba@414	464	arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
deba@414	465
deba@414	466	checkGraphNodeList(adaptor, 3);
deba@414	467	checkGraphArcList(adaptor, 0);
deba@414	468	checkGraphConArcList(adaptor, 0);
deba@414	469
deba@414	470	checkNodeIds(adaptor);
deba@414	471	checkArcIds(adaptor);
deba@414	472
deba@414	473	checkGraphNodeMap(adaptor);
deba@414	474	checkGraphArcMap(adaptor);
kpeter@463	475
kpeter@463	476	// Check the conversion of nodes and arcs
kpeter@463	477	Digraph::Node nd = n3;
kpeter@1197	478	::lemon::ignore_unused_variable_warning(nd);
kpeter@463	479	nd = n3;
kpeter@463	480	Adaptor::Node na = n1;
kpeter@1197	481	::lemon::ignore_unused_variable_warning(na);
kpeter@463	482	na = n2;
kpeter@463	483	Digraph::Arc ad = a3;
kpeter@1197	484	::lemon::ignore_unused_variable_warning(ad);
kpeter@463	485	ad = a3;
kpeter@463	486	Adaptor::Arc aa = a1;
kpeter@1197	487	::lemon::ignore_unused_variable_warning(aa);
kpeter@463	488	aa = a2;
deba@414	489	}
deba@414	490
deba@416	491	void checkUndirector() {
kpeter@463	492	// Check concepts
deba@416	493	checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
kpeter@463	494	checkConcept<concepts::Graph, Undirector<ListDigraph> >();
kpeter@463	495	checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463	496	Undirector<ListDigraph> >();
kpeter@463	497	checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463	498	Undirector<ListDigraph> >();
kpeter@463	499	checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463	500	Undirector<ListDigraph> >();
kpeter@463	501	checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463	502	Undirector<ListDigraph> >();
deba@414	503
kpeter@463	504
kpeter@463	505	// Create a digraph and an adaptor
deba@414	506	typedef ListDigraph Digraph;
deba@416	507	typedef Undirector<Digraph> Adaptor;
deba@414	508
deba@414	509	Digraph digraph;
deba@414	510	Adaptor adaptor(digraph);
deba@414	511
kpeter@463	512	// Add nodes and arcs/edges to the original digraph and the adaptor
deba@414	513	Digraph::Node n1 = digraph.addNode();
deba@414	514	Digraph::Node n2 = digraph.addNode();
kpeter@463	515	Adaptor::Node n3 = adaptor.addNode();
deba@414	516
deba@414	517	Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414	518	Digraph::Arc a2 = digraph.addArc(n1, n3);
kpeter@463	519	Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
deba@416	520
kpeter@463	521	// Check the original digraph
kpeter@463	522	checkGraphNodeList(digraph, 3);
kpeter@463	523	checkGraphArcList(digraph, 3);
kpeter@463	524	checkGraphConArcList(digraph, 3);
kpeter@463	525
kpeter@463	526	checkGraphOutArcList(digraph, n1, 2);
kpeter@463	527	checkGraphOutArcList(digraph, n2, 1);
kpeter@463	528	checkGraphOutArcList(digraph, n3, 0);
kpeter@463	529
kpeter@463	530	checkGraphInArcList(digraph, n1, 0);
kpeter@463	531	checkGraphInArcList(digraph, n2, 1);
kpeter@463	532	checkGraphInArcList(digraph, n3, 2);
kpeter@463	533
kpeter@463	534	checkNodeIds(digraph);
kpeter@463	535	checkArcIds(digraph);
kpeter@463	536
kpeter@463	537	checkGraphNodeMap(digraph);
kpeter@463	538	checkGraphArcMap(digraph);
kpeter@463	539
kpeter@463	540	// Check the adaptor
deba@414	541	checkGraphNodeList(adaptor, 3);
deba@414	542	checkGraphArcList(adaptor, 6);
deba@414	543	checkGraphEdgeList(adaptor, 3);
deba@414	544	checkGraphConArcList(adaptor, 6);
deba@414	545	checkGraphConEdgeList(adaptor, 3);
deba@414	546
kpeter@463	547	checkGraphIncEdgeArcLists(adaptor, n1, 2);
kpeter@463	548	checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463	549	checkGraphIncEdgeArcLists(adaptor, n3, 2);
deba@414	550
deba@414	551	checkNodeIds(adaptor);
deba@414	552	checkArcIds(adaptor);
deba@414	553	checkEdgeIds(adaptor);
deba@414	554
deba@414	555	checkGraphNodeMap(adaptor);
deba@414	556	checkGraphArcMap(adaptor);
deba@414	557	checkGraphEdgeMap(adaptor);
deba@414	558
kpeter@463	559	// Check the edges of the adaptor
deba@414	560	for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
deba@414	561	check(adaptor.u(e) == digraph.source(e), "Wrong undir");
deba@414	562	check(adaptor.v(e) == digraph.target(e), "Wrong undir");
deba@414	563	}
deba@414	564
kpeter@463	565	// Check CombinedArcMap
kpeter@463	566	typedef Adaptor::CombinedArcMap
kpeter@463	567	<Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;
kpeter@463	568	typedef Adaptor::CombinedArcMap
kpeter@463	569	<Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;
kpeter@463	570	checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
kpeter@463	571	IntCombinedMap>();
kpeter@463	572	checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
kpeter@463	573	BoolCombinedMap>();
kpeter@463	574
kpeter@463	575	Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);
kpeter@463	576	for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
kpeter@463	577	fw_map[a] = digraph.id(a);
kpeter@463	578	bk_map[a] = -digraph.id(a);
kpeter@463	579	}
kpeter@463	580
kpeter@463	581	Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >
kpeter@463	582	comb_map(fw_map, bk_map);
kpeter@463	583	for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
kpeter@463	584	if (adaptor.source(a) == digraph.source(a)) {
kpeter@463	585	check(comb_map[a] == fw_map[a], "Wrong combined map");
kpeter@463	586	} else {
kpeter@463	587	check(comb_map[a] == bk_map[a], "Wrong combined map");
kpeter@463	588	}
kpeter@463	589	}
kpeter@463	590
kpeter@463	591	// Check the conversion of nodes and arcs/edges
kpeter@463	592	Digraph::Node nd = n3;
kpeter@1197	593	::lemon::ignore_unused_variable_warning(nd);
kpeter@463	594	nd = n3;
kpeter@463	595	Adaptor::Node na = n1;
kpeter@1197	596	::lemon::ignore_unused_variable_warning(na);
kpeter@463	597	na = n2;
kpeter@463	598	Digraph::Arc ad = e3;
kpeter@1197	599	::lemon::ignore_unused_variable_warning(ad);
kpeter@463	600	ad = e3;
kpeter@463	601	Adaptor::Edge ea = a1;
kpeter@1197	602	::lemon::ignore_unused_variable_warning(ea);
kpeter@463	603	ea = a2;
deba@414	604	}
deba@414	605
kpeter@464	606	void checkResidualDigraph() {
kpeter@463	607	// Check concepts
kpeter@464	608	checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();
kpeter@464	609	checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();
deba@414	610
kpeter@463	611	// Create a digraph and an adaptor
deba@414	612	typedef ListDigraph Digraph;
deba@414	613	typedef Digraph::ArcMap<int> IntArcMap;
kpeter@464	614	typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;
deba@414	615
deba@414	616	Digraph digraph;
deba@414	617	IntArcMap capacity(digraph), flow(digraph);
deba@414	618	Adaptor adaptor(digraph, capacity, flow);
deba@414	619
deba@414	620	Digraph::Node n1 = digraph.addNode();
deba@414	621	Digraph::Node n2 = digraph.addNode();
deba@414	622	Digraph::Node n3 = digraph.addNode();
deba@414	623	Digraph::Node n4 = digraph.addNode();
deba@414	624
deba@414	625	Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414	626	Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414	627	Digraph::Arc a3 = digraph.addArc(n1, n4);
deba@414	628	Digraph::Arc a4 = digraph.addArc(n2, n3);
deba@414	629	Digraph::Arc a5 = digraph.addArc(n2, n4);
deba@414	630	Digraph::Arc a6 = digraph.addArc(n3, n4);
deba@414	631
deba@414	632	capacity[a1] = 8;
deba@414	633	capacity[a2] = 6;
deba@414	634	capacity[a3] = 4;
deba@414	635	capacity[a4] = 4;
deba@414	636	capacity[a5] = 6;
deba@414	637	capacity[a6] = 10;
deba@414	638
kpeter@463	639	// Check the adaptor with various flow values
kpeter@463	640	for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
deba@414	641	flow[a] = 0;
deba@414	642	}
deba@416	643
deba@414	644	checkGraphNodeList(adaptor, 4);
deba@414	645	checkGraphArcList(adaptor, 6);
deba@414	646	checkGraphConArcList(adaptor, 6);
deba@414	647
deba@414	648	checkGraphOutArcList(adaptor, n1, 3);
deba@414	649	checkGraphOutArcList(adaptor, n2, 2);
deba@414	650	checkGraphOutArcList(adaptor, n3, 1);
deba@414	651	checkGraphOutArcList(adaptor, n4, 0);
deba@414	652
deba@414	653	checkGraphInArcList(adaptor, n1, 0);
deba@414	654	checkGraphInArcList(adaptor, n2, 1);
deba@414	655	checkGraphInArcList(adaptor, n3, 2);
deba@414	656	checkGraphInArcList(adaptor, n4, 3);
deba@414	657
kpeter@463	658	for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
deba@414	659	flow[a] = capacity[a] / 2;
deba@414	660	}
deba@416	661
deba@414	662	checkGraphNodeList(adaptor, 4);
deba@414	663	checkGraphArcList(adaptor, 12);
deba@414	664	checkGraphConArcList(adaptor, 12);
deba@414	665
deba@414	666	checkGraphOutArcList(adaptor, n1, 3);
deba@414	667	checkGraphOutArcList(adaptor, n2, 3);
deba@414	668	checkGraphOutArcList(adaptor, n3, 3);
deba@414	669	checkGraphOutArcList(adaptor, n4, 3);
deba@414	670
deba@414	671	checkGraphInArcList(adaptor, n1, 3);
deba@414	672	checkGraphInArcList(adaptor, n2, 3);
deba@414	673	checkGraphInArcList(adaptor, n3, 3);
deba@414	674	checkGraphInArcList(adaptor, n4, 3);
deba@414	675
deba@414	676	checkNodeIds(adaptor);
deba@414	677	checkArcIds(adaptor);
deba@414	678
deba@414	679	checkGraphNodeMap(adaptor);
deba@414	680	checkGraphArcMap(adaptor);
deba@414	681
kpeter@463	682	for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
deba@414	683	flow[a] = capacity[a];
deba@414	684	}
deba@416	685
deba@414	686	checkGraphNodeList(adaptor, 4);
deba@414	687	checkGraphArcList(adaptor, 6);
deba@414	688	checkGraphConArcList(adaptor, 6);
deba@414	689
deba@414	690	checkGraphOutArcList(adaptor, n1, 0);
deba@414	691	checkGraphOutArcList(adaptor, n2, 1);
deba@414	692	checkGraphOutArcList(adaptor, n3, 2);
deba@414	693	checkGraphOutArcList(adaptor, n4, 3);
deba@414	694
deba@414	695	checkGraphInArcList(adaptor, n1, 3);
deba@414	696	checkGraphInArcList(adaptor, n2, 2);
deba@414	697	checkGraphInArcList(adaptor, n3, 1);
deba@414	698	checkGraphInArcList(adaptor, n4, 0);
deba@414	699
kpeter@463	700	// Saturate all backward arcs
kpeter@463	701	// (set the flow to zero on all forward arcs)
deba@414	702	for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
kpeter@463	703	if (adaptor.backward(a))
kpeter@463	704	adaptor.augment(a, adaptor.residualCapacity(a));
deba@414	705	}
deba@414	706
kpeter@463	707	checkGraphNodeList(adaptor, 4);
kpeter@463	708	checkGraphArcList(adaptor, 6);
kpeter@463	709	checkGraphConArcList(adaptor, 6);
kpeter@463	710
kpeter@463	711	checkGraphOutArcList(adaptor, n1, 3);
kpeter@463	712	checkGraphOutArcList(adaptor, n2, 2);
kpeter@463	713	checkGraphOutArcList(adaptor, n3, 1);
kpeter@463	714	checkGraphOutArcList(adaptor, n4, 0);
kpeter@463	715
kpeter@463	716	checkGraphInArcList(adaptor, n1, 0);
kpeter@463	717	checkGraphInArcList(adaptor, n2, 1);
kpeter@463	718	checkGraphInArcList(adaptor, n3, 2);
kpeter@463	719	checkGraphInArcList(adaptor, n4, 3);
kpeter@463	720
kpeter@463	721	// Find maximum flow by augmenting along shortest paths
deba@414	722	int flow_value = 0;
kpeter@463	723	Adaptor::ResidualCapacity res_cap(adaptor);
deba@414	724	while (true) {
deba@416	725
deba@414	726	Bfs<Adaptor> bfs(adaptor);
deba@414	727	bfs.run(n1, n4);
deba@416	728
deba@414	729	if (!bfs.reached(n4)) break;
deba@414	730
deba@414	731	Path<Adaptor> p = bfs.path(n4);
deba@416	732
deba@414	733	int min = std::numeric_limits<int>::max();
deba@414	734	for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
kpeter@463	735	if (res_cap[a] < min) min = res_cap[a];
deba@414	736	}
deba@414	737
deba@414	738	for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
deba@414	739	adaptor.augment(a, min);
deba@414	740	}
deba@414	741	flow_value += min;
deba@414	742	}
deba@414	743
deba@414	744	check(flow_value == 18, "Wrong flow with res graph adaptor");
deba@414	745
kpeter@463	746	// Check forward() and backward()
kpeter@463	747	for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
kpeter@463	748	check(adaptor.forward(a) != adaptor.backward(a),
kpeter@463	749	"Wrong forward() or backward()");
kpeter@463	750	check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) \|\|
kpeter@463	751	(adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),
kpeter@463	752	"Wrong forward() or backward()");
kpeter@463	753	}
kpeter@463	754
kpeter@463	755	// Check the conversion of nodes and arcs
kpeter@463	756	Digraph::Node nd = Adaptor::NodeIt(adaptor);
kpeter@1197	757	::lemon::ignore_unused_variable_warning(nd);
kpeter@463	758	nd = ++Adaptor::NodeIt(adaptor);
kpeter@463	759	Adaptor::Node na = n1;
kpeter@1197	760	::lemon::ignore_unused_variable_warning(na);
kpeter@463	761	na = n2;
kpeter@463	762	Digraph::Arc ad = Adaptor::ArcIt(adaptor);
kpeter@1197	763	::lemon::ignore_unused_variable_warning(ad);
kpeter@463	764	ad = ++Adaptor::ArcIt(adaptor);
deba@414	765	}
deba@414	766
deba@416	767	void checkSplitNodes() {
kpeter@463	768	// Check concepts
deba@416	769	checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
kpeter@463	770	checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
deba@414	771
kpeter@463	772	// Create a digraph and an adaptor
deba@414	773	typedef ListDigraph Digraph;
deba@416	774	typedef SplitNodes<Digraph> Adaptor;
deba@414	775
deba@414	776	Digraph digraph;
deba@414	777	Adaptor adaptor(digraph);
deba@414	778
deba@414	779	Digraph::Node n1 = digraph.addNode();
deba@414	780	Digraph::Node n2 = digraph.addNode();
deba@414	781	Digraph::Node n3 = digraph.addNode();
deba@414	782
deba@414	783	Digraph::Arc a1 = digraph.addArc(n1, n2);
deba@414	784	Digraph::Arc a2 = digraph.addArc(n1, n3);
deba@414	785	Digraph::Arc a3 = digraph.addArc(n2, n3);
alpar@1083	786	::lemon::ignore_unused_variable_warning(a1,a2,a3);
deba@416	787
deba@414	788	checkGraphNodeList(adaptor, 6);
deba@414	789	checkGraphArcList(adaptor, 6);
deba@414	790	checkGraphConArcList(adaptor, 6);
deba@414	791
deba@414	792	checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
deba@414	793	checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
deba@414	794	checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
deba@414	795	checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
deba@414	796	checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
deba@414	797	checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
deba@414	798
deba@414	799	checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
deba@414	800	checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
deba@414	801	checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
deba@414	802	checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
deba@414	803	checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
deba@414	804	checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
deba@414	805
deba@414	806	checkNodeIds(adaptor);
deba@414	807	checkArcIds(adaptor);
deba@416	808
deba@414	809	checkGraphNodeMap(adaptor);
deba@414	810	checkGraphArcMap(adaptor);
deba@414	811
kpeter@463	812	// Check split
deba@414	813	for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
deba@414	814	if (adaptor.origArc(a)) {
deba@414	815	Digraph::Arc oa = a;
deba@416	816	check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
deba@416	817	"Wrong split");
deba@416	818	check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
deba@416	819	"Wrong split");
deba@414	820	} else {
deba@414	821	Digraph::Node on = a;
deba@414	822	check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
deba@414	823	check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
deba@414	824	}
deba@414	825	}
kpeter@463	826
kpeter@463	827	// Check combined node map
kpeter@463	828	typedef Adaptor::CombinedNodeMap
kpeter@463	829	<Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;
kpeter@463	830	typedef Adaptor::CombinedNodeMap
kpeter@463	831	<Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;
kpeter@463	832	checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,
kpeter@463	833	IntCombinedNodeMap>();
kpeter@463	834	//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,
kpeter@463	835	// BoolCombinedNodeMap>();
kpeter@463	836	checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,
kpeter@463	837	BoolCombinedNodeMap>();
kpeter@463	838
kpeter@463	839	Digraph::NodeMap<int> in_map(digraph), out_map(digraph);
kpeter@463	840	for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
kpeter@463	841	in_map[n] = digraph.id(n);
kpeter@463	842	out_map[n] = -digraph.id(n);
kpeter@463	843	}
kpeter@463	844
kpeter@463	845	Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >
kpeter@463	846	node_map(in_map, out_map);
kpeter@463	847	for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {
kpeter@463	848	if (adaptor.inNode(n)) {
kpeter@463	849	check(node_map[n] == in_map[n], "Wrong combined node map");
kpeter@463	850	} else {
kpeter@463	851	check(node_map[n] == out_map[n], "Wrong combined node map");
kpeter@463	852	}
kpeter@463	853	}
kpeter@463	854
kpeter@463	855	// Check combined arc map
kpeter@463	856	typedef Adaptor::CombinedArcMap
kpeter@463	857	<Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;
kpeter@463	858	typedef Adaptor::CombinedArcMap
kpeter@463	859	<Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;
kpeter@463	860	checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
kpeter@463	861	IntCombinedArcMap>();
kpeter@463	862	//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
kpeter@463	863	// BoolCombinedArcMap>();
kpeter@463	864	checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,
kpeter@463	865	BoolCombinedArcMap>();
kpeter@463	866
kpeter@463	867	Digraph::ArcMap<int> a_map(digraph);
kpeter@463	868	for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
kpeter@463	869	a_map[a] = digraph.id(a);
kpeter@463	870	}
kpeter@463	871
kpeter@463	872	Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >
kpeter@463	873	arc_map(a_map, out_map);
kpeter@463	874	for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
kpeter@463	875	check(arc_map[adaptor.arc(a)] == a_map[a], "Wrong combined arc map");
kpeter@463	876	}
kpeter@463	877	for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
kpeter@463	878	check(arc_map[adaptor.arc(n)] == out_map[n], "Wrong combined arc map");
kpeter@463	879	}
kpeter@463	880
kpeter@463	881	// Check the conversion of nodes
kpeter@463	882	Digraph::Node nd = adaptor.inNode(n1);
kpeter@463	883	check (nd == n1, "Wrong node conversion");
kpeter@463	884	nd = adaptor.outNode(n2);
kpeter@463	885	check (nd == n2, "Wrong node conversion");
deba@414	886	}
deba@414	887
deba@416	888	void checkSubGraph() {
kpeter@463	889	// Check concepts
kpeter@463	890	checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();
kpeter@463	891	checkConcept<concepts::Graph, SubGraph<ListGraph> >();
kpeter@463	892	checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463	893	SubGraph<ListGraph> >();
kpeter@463	894	checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463	895	SubGraph<ListGraph> >();
kpeter@463	896	checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463	897	SubGraph<ListGraph> >();
kpeter@463	898	checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463	899	SubGraph<ListGraph> >();
deba@414	900
kpeter@463	901	// Create a graph and an adaptor
deba@414	902	typedef ListGraph Graph;
deba@414	903	typedef Graph::NodeMap<bool> NodeFilter;
deba@414	904	typedef Graph::EdgeMap<bool> EdgeFilter;
deba@416	905	typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
deba@414	906
deba@414	907	Graph graph;
deba@414	908	NodeFilter node_filter(graph);
deba@414	909	EdgeFilter edge_filter(graph);
deba@414	910	Adaptor adaptor(graph, node_filter, edge_filter);
deba@414	911
kpeter@463	912	// Add nodes and edges to the original graph and the adaptor
deba@414	913	Graph::Node n1 = graph.addNode();
deba@414	914	Graph::Node n2 = graph.addNode();
kpeter@463	915	Adaptor::Node n3 = adaptor.addNode();
kpeter@463	916	Adaptor::Node n4 = adaptor.addNode();
kpeter@463	917
kpeter@463	918	node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@414	919
deba@414	920	Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414	921	Graph::Edge e2 = graph.addEdge(n1, n3);
kpeter@463	922	Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
kpeter@463	923	Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
deba@414	924
deba@414	925	edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
alpar@440	926
deba@414	927	checkGraphNodeList(adaptor, 4);
deba@414	928	checkGraphArcList(adaptor, 8);
deba@414	929	checkGraphEdgeList(adaptor, 4);
deba@414	930	checkGraphConArcList(adaptor, 8);
deba@414	931	checkGraphConEdgeList(adaptor, 4);
deba@414	932
kpeter@463	933	checkGraphIncEdgeArcLists(adaptor, n1, 2);
kpeter@463	934	checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463	935	checkGraphIncEdgeArcLists(adaptor, n3, 3);
kpeter@463	936	checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414	937
deba@414	938	checkNodeIds(adaptor);
deba@414	939	checkArcIds(adaptor);
deba@414	940	checkEdgeIds(adaptor);
deba@414	941
deba@414	942	checkGraphNodeMap(adaptor);
deba@414	943	checkGraphArcMap(adaptor);
deba@414	944	checkGraphEdgeMap(adaptor);
deba@414	945
kpeter@463	946	// Hide an edge
kpeter@463	947	adaptor.status(e2, false);
kpeter@463	948	adaptor.disable(e3);
kpeter@463	949	if (!adaptor.status(e3)) adaptor.enable(e3);
deba@414	950
deba@414	951	checkGraphNodeList(adaptor, 4);
deba@414	952	checkGraphArcList(adaptor, 6);
deba@414	953	checkGraphEdgeList(adaptor, 3);
deba@414	954	checkGraphConArcList(adaptor, 6);
deba@414	955	checkGraphConEdgeList(adaptor, 3);
deba@414	956
kpeter@463	957	checkGraphIncEdgeArcLists(adaptor, n1, 1);
kpeter@463	958	checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463	959	checkGraphIncEdgeArcLists(adaptor, n3, 2);
kpeter@463	960	checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414	961
deba@414	962	checkNodeIds(adaptor);
deba@414	963	checkArcIds(adaptor);
deba@414	964	checkEdgeIds(adaptor);
deba@414	965
deba@414	966	checkGraphNodeMap(adaptor);
deba@414	967	checkGraphArcMap(adaptor);
deba@414	968	checkGraphEdgeMap(adaptor);
deba@414	969
kpeter@463	970	// Hide a node
kpeter@463	971	adaptor.status(n1, false);
kpeter@463	972	adaptor.disable(n3);
kpeter@463	973	if (!adaptor.status(n3)) adaptor.enable(n3);
deba@414	974
deba@414	975	checkGraphNodeList(adaptor, 3);
deba@414	976	checkGraphArcList(adaptor, 4);
deba@414	977	checkGraphEdgeList(adaptor, 2);
deba@414	978	checkGraphConArcList(adaptor, 4);
deba@414	979	checkGraphConEdgeList(adaptor, 2);
deba@414	980
kpeter@463	981	checkGraphIncEdgeArcLists(adaptor, n2, 1);
kpeter@463	982	checkGraphIncEdgeArcLists(adaptor, n3, 2);
kpeter@463	983	checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414	984
deba@414	985	checkNodeIds(adaptor);
deba@414	986	checkArcIds(adaptor);
deba@414	987	checkEdgeIds(adaptor);
deba@414	988
deba@414	989	checkGraphNodeMap(adaptor);
deba@414	990	checkGraphArcMap(adaptor);
deba@414	991	checkGraphEdgeMap(adaptor);
deba@414	992
kpeter@463	993	// Hide all nodes and edges
deba@414	994	node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
deba@414	995	edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
deba@414	996
deba@414	997	checkGraphNodeList(adaptor, 0);
deba@414	998	checkGraphArcList(adaptor, 0);
deba@414	999	checkGraphEdgeList(adaptor, 0);
deba@414	1000	checkGraphConArcList(adaptor, 0);
deba@414	1001	checkGraphConEdgeList(adaptor, 0);
deba@414	1002
deba@414	1003	checkNodeIds(adaptor);
deba@414	1004	checkArcIds(adaptor);
deba@414	1005	checkEdgeIds(adaptor);
deba@414	1006
deba@414	1007	checkGraphNodeMap(adaptor);
deba@414	1008	checkGraphArcMap(adaptor);
deba@414	1009	checkGraphEdgeMap(adaptor);
kpeter@463	1010
kpeter@463	1011	// Check the conversion of nodes and edges
kpeter@463	1012	Graph::Node ng = n3;
kpeter@1197	1013	::lemon::ignore_unused_variable_warning(ng);
kpeter@463	1014	ng = n4;
kpeter@463	1015	Adaptor::Node na = n1;
kpeter@1197	1016	::lemon::ignore_unused_variable_warning(na);
kpeter@463	1017	na = n2;
kpeter@463	1018	Graph::Edge eg = e3;
kpeter@1197	1019	::lemon::ignore_unused_variable_warning(eg);
kpeter@463	1020	eg = e4;
kpeter@463	1021	Adaptor::Edge ea = e1;
kpeter@1197	1022	::lemon::ignore_unused_variable_warning(ea);
kpeter@463	1023	ea = e2;
deba@414	1024	}
deba@414	1025
deba@416	1026	void checkFilterNodes2() {
kpeter@463	1027	// Check concepts
kpeter@463	1028	checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();
kpeter@463	1029	checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
kpeter@463	1030	checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463	1031	FilterNodes<ListGraph> >();
kpeter@463	1032	checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463	1033	FilterNodes<ListGraph> >();
kpeter@463	1034	checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463	1035	FilterNodes<ListGraph> >();
kpeter@463	1036	checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463	1037	FilterNodes<ListGraph> >();
deba@414	1038
kpeter@463	1039	// Create a graph and an adaptor
deba@414	1040	typedef ListGraph Graph;
deba@414	1041	typedef Graph::NodeMap<bool> NodeFilter;
deba@416	1042	typedef FilterNodes<Graph, NodeFilter> Adaptor;
deba@414	1043
kpeter@463	1044	// Add nodes and edges to the original graph and the adaptor
deba@414	1045	Graph graph;
deba@414	1046	NodeFilter node_filter(graph);
deba@414	1047	Adaptor adaptor(graph, node_filter);
deba@414	1048
deba@414	1049	Graph::Node n1 = graph.addNode();
deba@414	1050	Graph::Node n2 = graph.addNode();
kpeter@463	1051	Adaptor::Node n3 = adaptor.addNode();
kpeter@463	1052	Adaptor::Node n4 = adaptor.addNode();
kpeter@463	1053
kpeter@463	1054	node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
deba@414	1055
deba@414	1056	Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414	1057	Graph::Edge e2 = graph.addEdge(n1, n3);
kpeter@463	1058	Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
kpeter@463	1059	Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
alpar@440	1060
deba@414	1061	checkGraphNodeList(adaptor, 4);
deba@414	1062	checkGraphArcList(adaptor, 8);
deba@414	1063	checkGraphEdgeList(adaptor, 4);
deba@414	1064	checkGraphConArcList(adaptor, 8);
deba@414	1065	checkGraphConEdgeList(adaptor, 4);
deba@414	1066
kpeter@463	1067	checkGraphIncEdgeArcLists(adaptor, n1, 2);
kpeter@463	1068	checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463	1069	checkGraphIncEdgeArcLists(adaptor, n3, 3);
kpeter@463	1070	checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414	1071
deba@414	1072	checkNodeIds(adaptor);
deba@414	1073	checkArcIds(adaptor);
deba@414	1074	checkEdgeIds(adaptor);
deba@414	1075
deba@414	1076	checkGraphNodeMap(adaptor);
deba@414	1077	checkGraphArcMap(adaptor);
deba@414	1078	checkGraphEdgeMap(adaptor);
deba@414	1079
kpeter@463	1080	// Hide a node
kpeter@463	1081	adaptor.status(n1, false);
kpeter@463	1082	adaptor.disable(n3);
kpeter@463	1083	if (!adaptor.status(n3)) adaptor.enable(n3);
deba@414	1084
deba@414	1085	checkGraphNodeList(adaptor, 3);
deba@414	1086	checkGraphArcList(adaptor, 4);
deba@414	1087	checkGraphEdgeList(adaptor, 2);
deba@414	1088	checkGraphConArcList(adaptor, 4);
deba@414	1089	checkGraphConEdgeList(adaptor, 2);
deba@414	1090
kpeter@463	1091	checkGraphIncEdgeArcLists(adaptor, n2, 1);
kpeter@463	1092	checkGraphIncEdgeArcLists(adaptor, n3, 2);
kpeter@463	1093	checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414	1094
deba@414	1095	checkNodeIds(adaptor);
deba@414	1096	checkArcIds(adaptor);
deba@414	1097	checkEdgeIds(adaptor);
deba@414	1098
deba@414	1099	checkGraphNodeMap(adaptor);
deba@414	1100	checkGraphArcMap(adaptor);
deba@414	1101	checkGraphEdgeMap(adaptor);
deba@414	1102
kpeter@463	1103	// Hide all nodes
deba@414	1104	node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
deba@414	1105
deba@414	1106	checkGraphNodeList(adaptor, 0);
deba@414	1107	checkGraphArcList(adaptor, 0);
deba@414	1108	checkGraphEdgeList(adaptor, 0);
deba@414	1109	checkGraphConArcList(adaptor, 0);
deba@414	1110	checkGraphConEdgeList(adaptor, 0);
deba@414	1111
deba@414	1112	checkNodeIds(adaptor);
deba@414	1113	checkArcIds(adaptor);
deba@414	1114	checkEdgeIds(adaptor);
deba@414	1115
deba@414	1116	checkGraphNodeMap(adaptor);
deba@414	1117	checkGraphArcMap(adaptor);
deba@414	1118	checkGraphEdgeMap(adaptor);
kpeter@463	1119
kpeter@463	1120	// Check the conversion of nodes and edges
kpeter@463	1121	Graph::Node ng = n3;
kpeter@1197	1122	::lemon::ignore_unused_variable_warning(ng);
kpeter@463	1123	ng = n4;
kpeter@463	1124	Adaptor::Node na = n1;
kpeter@1197	1125	::lemon::ignore_unused_variable_warning(na);
kpeter@463	1126	na = n2;
kpeter@463	1127	Graph::Edge eg = e3;
kpeter@1197	1128	::lemon::ignore_unused_variable_warning(eg);
kpeter@463	1129	eg = e4;
kpeter@463	1130	Adaptor::Edge ea = e1;
kpeter@1197	1131	::lemon::ignore_unused_variable_warning(ea);
kpeter@463	1132	ea = e2;
deba@414	1133	}
deba@414	1134
deba@416	1135	void checkFilterEdges() {
kpeter@463	1136	// Check concepts
kpeter@463	1137	checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();
kpeter@463	1138	checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
kpeter@463	1139	checkConcept<concepts::AlterableGraphComponent<>,
kpeter@463	1140	FilterEdges<ListGraph> >();
kpeter@463	1141	checkConcept<concepts::ExtendableGraphComponent<>,
kpeter@463	1142	FilterEdges<ListGraph> >();
kpeter@463	1143	checkConcept<concepts::ErasableGraphComponent<>,
kpeter@463	1144	FilterEdges<ListGraph> >();
kpeter@463	1145	checkConcept<concepts::ClearableGraphComponent<>,
kpeter@463	1146	FilterEdges<ListGraph> >();
deba@414	1147
kpeter@463	1148	// Create a graph and an adaptor
deba@414	1149	typedef ListGraph Graph;
deba@414	1150	typedef Graph::EdgeMap<bool> EdgeFilter;
deba@416	1151	typedef FilterEdges<Graph, EdgeFilter> Adaptor;
deba@414	1152
deba@414	1153	Graph graph;
deba@414	1154	EdgeFilter edge_filter(graph);
deba@414	1155	Adaptor adaptor(graph, edge_filter);
deba@414	1156
kpeter@463	1157	// Add nodes and edges to the original graph and the adaptor
deba@414	1158	Graph::Node n1 = graph.addNode();
deba@414	1159	Graph::Node n2 = graph.addNode();
kpeter@463	1160	Adaptor::Node n3 = adaptor.addNode();
kpeter@463	1161	Adaptor::Node n4 = adaptor.addNode();
deba@414	1162
deba@414	1163	Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414	1164	Graph::Edge e2 = graph.addEdge(n1, n3);
kpeter@463	1165	Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
kpeter@463	1166	Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
deba@414	1167
deba@414	1168	edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
alpar@440	1169
deba@414	1170	checkGraphNodeList(adaptor, 4);
deba@414	1171	checkGraphArcList(adaptor, 8);
deba@414	1172	checkGraphEdgeList(adaptor, 4);
deba@414	1173	checkGraphConArcList(adaptor, 8);
deba@414	1174	checkGraphConEdgeList(adaptor, 4);
deba@414	1175
kpeter@463	1176	checkGraphIncEdgeArcLists(adaptor, n1, 2);
kpeter@463	1177	checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463	1178	checkGraphIncEdgeArcLists(adaptor, n3, 3);
kpeter@463	1179	checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414	1180
deba@414	1181	checkNodeIds(adaptor);
deba@414	1182	checkArcIds(adaptor);
deba@414	1183	checkEdgeIds(adaptor);
deba@414	1184
deba@414	1185	checkGraphNodeMap(adaptor);
deba@414	1186	checkGraphArcMap(adaptor);
deba@414	1187	checkGraphEdgeMap(adaptor);
deba@414	1188
kpeter@463	1189	// Hide an edge
kpeter@463	1190	adaptor.status(e2, false);
kpeter@463	1191	adaptor.disable(e3);
kpeter@463	1192	if (!adaptor.status(e3)) adaptor.enable(e3);
deba@414	1193
deba@414	1194	checkGraphNodeList(adaptor, 4);
deba@414	1195	checkGraphArcList(adaptor, 6);
deba@414	1196	checkGraphEdgeList(adaptor, 3);
deba@414	1197	checkGraphConArcList(adaptor, 6);
deba@414	1198	checkGraphConEdgeList(adaptor, 3);
deba@414	1199
kpeter@463	1200	checkGraphIncEdgeArcLists(adaptor, n1, 1);
kpeter@463	1201	checkGraphIncEdgeArcLists(adaptor, n2, 2);
kpeter@463	1202	checkGraphIncEdgeArcLists(adaptor, n3, 2);
kpeter@463	1203	checkGraphIncEdgeArcLists(adaptor, n4, 1);
deba@414	1204
deba@414	1205	checkNodeIds(adaptor);
deba@414	1206	checkArcIds(adaptor);
deba@414	1207	checkEdgeIds(adaptor);
deba@414	1208
deba@414	1209	checkGraphNodeMap(adaptor);
deba@414	1210	checkGraphArcMap(adaptor);
deba@414	1211	checkGraphEdgeMap(adaptor);
deba@414	1212
kpeter@463	1213	// Hide all edges
deba@414	1214	edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
deba@414	1215
deba@414	1216	checkGraphNodeList(adaptor, 4);
deba@414	1217	checkGraphArcList(adaptor, 0);
deba@414	1218	checkGraphEdgeList(adaptor, 0);
deba@414	1219	checkGraphConArcList(adaptor, 0);
deba@414	1220	checkGraphConEdgeList(adaptor, 0);
deba@414	1221
deba@414	1222	checkNodeIds(adaptor);
deba@414	1223	checkArcIds(adaptor);
deba@414	1224	checkEdgeIds(adaptor);
deba@414	1225
deba@414	1226	checkGraphNodeMap(adaptor);
deba@414	1227	checkGraphArcMap(adaptor);
deba@414	1228	checkGraphEdgeMap(adaptor);
kpeter@463	1229
kpeter@463	1230	// Check the conversion of nodes and edges
kpeter@463	1231	Graph::Node ng = n3;
kpeter@1197	1232	::lemon::ignore_unused_variable_warning(ng);
kpeter@463	1233	ng = n4;
kpeter@463	1234	Adaptor::Node na = n1;
kpeter@1197	1235	::lemon::ignore_unused_variable_warning(na);
kpeter@463	1236	na = n2;
kpeter@463	1237	Graph::Edge eg = e3;
kpeter@1197	1238	::lemon::ignore_unused_variable_warning(eg);
kpeter@463	1239	eg = e4;
kpeter@463	1240	Adaptor::Edge ea = e1;
kpeter@1197	1241	::lemon::ignore_unused_variable_warning(ea);
kpeter@463	1242	ea = e2;
deba@414	1243	}
deba@414	1244
deba@416	1245	void checkOrienter() {
kpeter@463	1246	// Check concepts
kpeter@463	1247	checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();
kpeter@463	1248	checkConcept<concepts::Digraph, Orienter<ListGraph> >();
kpeter@463	1249	checkConcept<concepts::AlterableDigraphComponent<>,
kpeter@463	1250	Orienter<ListGraph> >();
kpeter@463	1251	checkConcept<concepts::ExtendableDigraphComponent<>,
kpeter@463	1252	Orienter<ListGraph> >();
kpeter@463	1253	checkConcept<concepts::ErasableDigraphComponent<>,
kpeter@463	1254	Orienter<ListGraph> >();
kpeter@463	1255	checkConcept<concepts::ClearableDigraphComponent<>,
kpeter@463	1256	Orienter<ListGraph> >();
deba@414	1257
kpeter@463	1258	// Create a graph and an adaptor
deba@414	1259	typedef ListGraph Graph;
deba@414	1260	typedef ListGraph::EdgeMap<bool> DirMap;
deba@416	1261	typedef Orienter<Graph> Adaptor;
deba@414	1262
deba@414	1263	Graph graph;
kpeter@463	1264	DirMap dir(graph);
deba@414	1265	Adaptor adaptor(graph, dir);
deba@414	1266
kpeter@463	1267	// Add nodes and edges to the original graph and the adaptor
deba@414	1268	Graph::Node n1 = graph.addNode();
deba@414	1269	Graph::Node n2 = graph.addNode();
kpeter@463	1270	Adaptor::Node n3 = adaptor.addNode();
deba@414	1271
deba@414	1272	Graph::Edge e1 = graph.addEdge(n1, n2);
deba@414	1273	Graph::Edge e2 = graph.addEdge(n1, n3);
kpeter@463	1274	Adaptor::Arc e3 = adaptor.addArc(n2, n3);
deba@416	1275
kpeter@463	1276	dir[e1] = dir[e2] = dir[e3] = true;
kpeter@463	1277
kpeter@463	1278	// Check the original graph
kpeter@463	1279	checkGraphNodeList(graph, 3);
kpeter@463	1280	checkGraphArcList(graph, 6);
kpeter@463	1281	checkGraphConArcList(graph, 6);
kpeter@463	1282	checkGraphEdgeList(graph, 3);
kpeter@463	1283	checkGraphConEdgeList(graph, 3);
kpeter@463	1284
kpeter@463	1285	checkGraphIncEdgeArcLists(graph, n1, 2);
kpeter@463	1286	checkGraphIncEdgeArcLists(graph, n2, 2);
kpeter@463	1287	checkGraphIncEdgeArcLists(graph, n3, 2);
kpeter@463	1288
kpeter@463	1289	checkNodeIds(graph);
kpeter@463	1290	checkArcIds(graph);
kpeter@463	1291	checkEdgeIds(graph);
kpeter@463	1292
kpeter@463	1293	checkGraphNodeMap(graph);
kpeter@463	1294	checkGraphArcMap(graph);
kpeter@463	1295	checkGraphEdgeMap(graph);
kpeter@463	1296
kpeter@463	1297	// Check the adaptor
deba@414	1298	checkGraphNodeList(adaptor, 3);
deba@414	1299	checkGraphArcList(adaptor, 3);
deba@414	1300	checkGraphConArcList(adaptor, 3);
deba@416	1301
kpeter@463	1302	checkGraphOutArcList(adaptor, n1, 2);
kpeter@463	1303	checkGraphOutArcList(adaptor, n2, 1);
kpeter@463	1304	checkGraphOutArcList(adaptor, n3, 0);
kpeter@463	1305
kpeter@463	1306	checkGraphInArcList(adaptor, n1, 0);
kpeter@463	1307	checkGraphInArcList(adaptor, n2, 1);
kpeter@463	1308	checkGraphInArcList(adaptor, n3, 2);
kpeter@463	1309
kpeter@463	1310	checkNodeIds(adaptor);
kpeter@463	1311	checkArcIds(adaptor);
kpeter@463	1312
kpeter@463	1313	checkGraphNodeMap(adaptor);
kpeter@463	1314	checkGraphArcMap(adaptor);
kpeter@463	1315
kpeter@463	1316	// Check direction changing
deba@414	1317	{
deba@414	1318	dir[e1] = true;
deba@414	1319	Adaptor::Node u = adaptor.source(e1);
deba@414	1320	Adaptor::Node v = adaptor.target(e1);
deba@416	1321
deba@414	1322	dir[e1] = false;
deba@414	1323	check (u == adaptor.target(e1), "Wrong dir");
deba@414	1324	check (v == adaptor.source(e1), "Wrong dir");
deba@414	1325
deba@414	1326	check ((u == n1 && v == n2) \|\| (u == n2 && v == n1), "Wrong dir");
deba@414	1327	dir[e1] = n1 == u;
deba@414	1328	}
deba@414	1329
deba@414	1330	{
deba@414	1331	dir[e2] = true;
deba@414	1332	Adaptor::Node u = adaptor.source(e2);
deba@414	1333	Adaptor::Node v = adaptor.target(e2);
deba@416	1334
deba@414	1335	dir[e2] = false;
deba@414	1336	check (u == adaptor.target(e2), "Wrong dir");
deba@414	1337	check (v == adaptor.source(e2), "Wrong dir");
deba@414	1338
deba@414	1339	check ((u == n1 && v == n3) \|\| (u == n3 && v == n1), "Wrong dir");
deba@414	1340	dir[e2] = n3 == u;
deba@414	1341	}
deba@414	1342
deba@414	1343	{
deba@414	1344	dir[e3] = true;
deba@414	1345	Adaptor::Node u = adaptor.source(e3);
deba@414	1346	Adaptor::Node v = adaptor.target(e3);
deba@416	1347
deba@414	1348	dir[e3] = false;
deba@414	1349	check (u == adaptor.target(e3), "Wrong dir");
deba@414	1350	check (v == adaptor.source(e3), "Wrong dir");
deba@414	1351
deba@414	1352	check ((u == n2 && v == n3) \|\| (u == n3 && v == n2), "Wrong dir");
deba@414	1353	dir[e3] = n2 == u;
deba@414	1354	}
deba@414	1355
kpeter@463	1356	// Check the adaptor again
kpeter@463	1357	checkGraphNodeList(adaptor, 3);
kpeter@463	1358	checkGraphArcList(adaptor, 3);
kpeter@463	1359	checkGraphConArcList(adaptor, 3);
kpeter@463	1360
deba@414	1361	checkGraphOutArcList(adaptor, n1, 1);
deba@414	1362	checkGraphOutArcList(adaptor, n2, 1);
deba@414	1363	checkGraphOutArcList(adaptor, n3, 1);
deba@414	1364
deba@414	1365	checkGraphInArcList(adaptor, n1, 1);
deba@414	1366	checkGraphInArcList(adaptor, n2, 1);
deba@414	1367	checkGraphInArcList(adaptor, n3, 1);
deba@414	1368
deba@414	1369	checkNodeIds(adaptor);
deba@414	1370	checkArcIds(adaptor);
deba@414	1371
deba@414	1372	checkGraphNodeMap(adaptor);
deba@414	1373	checkGraphArcMap(adaptor);
deba@414	1374
kpeter@463	1375	// Check reverseArc()
kpeter@463	1376	adaptor.reverseArc(e2);
kpeter@463	1377	adaptor.reverseArc(e3);
kpeter@463	1378	adaptor.reverseArc(e2);
kpeter@463	1379
kpeter@463	1380	checkGraphNodeList(adaptor, 3);
kpeter@463	1381	checkGraphArcList(adaptor, 3);
kpeter@463	1382	checkGraphConArcList(adaptor, 3);
kpeter@463	1383
kpeter@463	1384	checkGraphOutArcList(adaptor, n1, 1);
kpeter@463	1385	checkGraphOutArcList(adaptor, n2, 0);
kpeter@463	1386	checkGraphOutArcList(adaptor, n3, 2);
kpeter@463	1387
kpeter@463	1388	checkGraphInArcList(adaptor, n1, 1);
kpeter@463	1389	checkGraphInArcList(adaptor, n2, 2);
kpeter@463	1390	checkGraphInArcList(adaptor, n3, 0);
kpeter@463	1391
kpeter@463	1392	// Check the conversion of nodes and arcs/edges
kpeter@463	1393	Graph::Node ng = n3;
kpeter@1197	1394	::lemon::ignore_unused_variable_warning(ng);
kpeter@463	1395	ng = n3;
kpeter@463	1396	Adaptor::Node na = n1;
kpeter@1197	1397	::lemon::ignore_unused_variable_warning(na);
kpeter@463	1398	na = n2;
kpeter@463	1399	Graph::Edge eg = e3;
kpeter@1197	1400	::lemon::ignore_unused_variable_warning(eg);
kpeter@463	1401	eg = e3;
kpeter@463	1402	Adaptor::Arc aa = e1;
kpeter@1197	1403	::lemon::ignore_unused_variable_warning(aa);
kpeter@463	1404	aa = e2;
deba@414	1405	}
deba@414	1406
kpeter@463	1407	void checkCombiningAdaptors() {
kpeter@463	1408	// Create a grid graph
kpeter@463	1409	GridGraph graph(2,2);
kpeter@463	1410	GridGraph::Node n1 = graph(0,0);
kpeter@463	1411	GridGraph::Node n2 = graph(0,1);
kpeter@463	1412	GridGraph::Node n3 = graph(1,0);
kpeter@463	1413	GridGraph::Node n4 = graph(1,1);
kpeter@463	1414
kpeter@463	1415	GridGraph::EdgeMap<bool> dir_map(graph);
kpeter@515	1416	dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1;
kpeter@515	1417	dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1;
kpeter@515	1418	dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4;
kpeter@515	1419	dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4;
kpeter@463	1420
kpeter@463	1421	// Apply several adaptors on the grid graph
alpar@995	1422	typedef Orienter< const GridGraph, GridGraph::EdgeMap<bool> >
alpar@995	1423	OrientedGridGraph;
alpar@995	1424	typedef SplitNodes<OrientedGridGraph> SplitGridGraph;
kpeter@463	1425	typedef Undirector<const SplitGridGraph> USplitGridGraph;
kpeter@463	1426	checkConcept<concepts::Digraph, SplitGridGraph>();
kpeter@463	1427	checkConcept<concepts::Graph, USplitGridGraph>();
kpeter@463	1428
alpar@995	1429	OrientedGridGraph oadaptor = orienter(graph, dir_map);
alpar@995	1430	SplitGridGraph adaptor = splitNodes(oadaptor);
kpeter@463	1431	USplitGridGraph uadaptor = undirector(adaptor);
kpeter@463	1432
kpeter@463	1433	// Check adaptor
kpeter@463	1434	checkGraphNodeList(adaptor, 8);
kpeter@463	1435	checkGraphArcList(adaptor, 8);
kpeter@463	1436	checkGraphConArcList(adaptor, 8);
kpeter@463	1437
kpeter@515	1438	checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
kpeter@515	1439	checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1);
kpeter@515	1440	checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
kpeter@515	1441	checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0);
kpeter@515	1442	checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
kpeter@515	1443	checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1);
kpeter@515	1444	checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1);
kpeter@515	1445	checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2);
kpeter@463	1446
kpeter@515	1447	checkGraphInArcList(adaptor, adaptor.inNode(n1), 1);
kpeter@515	1448	checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
kpeter@515	1449	checkGraphInArcList(adaptor, adaptor.inNode(n2), 2);
kpeter@515	1450	checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
kpeter@515	1451	checkGraphInArcList(adaptor, adaptor.inNode(n3), 1);
kpeter@515	1452	checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
kpeter@515	1453	checkGraphInArcList(adaptor, adaptor.inNode(n4), 0);
kpeter@515	1454	checkGraphInArcList(adaptor, adaptor.outNode(n4), 1);
kpeter@463	1455
kpeter@463	1456	checkNodeIds(adaptor);
kpeter@463	1457	checkArcIds(adaptor);
kpeter@463	1458
kpeter@463	1459	checkGraphNodeMap(adaptor);
kpeter@463	1460	checkGraphArcMap(adaptor);
kpeter@463	1461
kpeter@463	1462	// Check uadaptor
kpeter@463	1463	checkGraphNodeList(uadaptor, 8);
kpeter@463	1464	checkGraphEdgeList(uadaptor, 8);
kpeter@463	1465	checkGraphArcList(uadaptor, 16);
kpeter@463	1466	checkGraphConEdgeList(uadaptor, 8);
kpeter@463	1467	checkGraphConArcList(uadaptor, 16);
kpeter@463	1468
kpeter@463	1469	checkNodeIds(uadaptor);
kpeter@463	1470	checkEdgeIds(uadaptor);
kpeter@463	1471	checkArcIds(uadaptor);
kpeter@463	1472
kpeter@463	1473	checkGraphNodeMap(uadaptor);
kpeter@463	1474	checkGraphEdgeMap(uadaptor);
kpeter@463	1475	checkGraphArcMap(uadaptor);
kpeter@463	1476
kpeter@515	1477	checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2);
kpeter@515	1478	checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2);
kpeter@515	1479	checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3);
kpeter@515	1480	checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1);
kpeter@515	1481	checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2);
kpeter@515	1482	checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2);
kpeter@515	1483	checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1);
kpeter@515	1484	checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3);
kpeter@463	1485	}
deba@414	1486
deba@414	1487	int main(int, const char **) {
kpeter@463	1488	// Check the digraph adaptors (using ListDigraph)
deba@416	1489	checkReverseDigraph();
deba@416	1490	checkSubDigraph();
deba@416	1491	checkFilterNodes1();
deba@416	1492	checkFilterArcs();
deba@416	1493	checkUndirector();
kpeter@464	1494	checkResidualDigraph();
deba@416	1495	checkSplitNodes();
deba@414	1496
kpeter@463	1497	// Check the graph adaptors (using ListGraph)
deba@416	1498	checkSubGraph();
deba@416	1499	checkFilterNodes2();
deba@416	1500	checkFilterEdges();
deba@416	1501	checkOrienter();
deba@414	1502
kpeter@463	1503	// Combine adaptors (using GridGraph)
kpeter@463	1504	checkCombiningAdaptors();
kpeter@463	1505
deba@414	1506	return 0;
deba@414	1507	}

author	Alpar Juttner <alpar@cs.elte.hu>
	Thu, 21 Jan 2021 18:58:37 +0100
changeset 1207	eba5aa390aca
parent 1092	dceba191c00d
permissions	-rw-r--r--