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

author	Alpar Juttner <alpar@cs.elte.hu>
	Sat, 25 May 2013 06:59:31 +0200
changeset 1064	fc3854d936f7
parent 995	4bb9e72e1a41
parent 997	761fe0846f49
child 1084	8b2d4e5d96e4
permissions	-rw-r--r--