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

author	Alpar Juttner <alpar@cs.elte.hu>
	Sun, 07 Mar 2010 09:42:47 +0000
branch	1.1
changeset 720	86a880ba752d
parent 464	acfb0f24d178
child 791	939d747055cd
child 792	761fe0846f49
permissions	-rw-r--r--