# HG changeset patch # User deba # Date 1147686591 0 # Node ID 59769591eb60a455912f6f57801a17d23c768c98 # Parent f50c8c191cbd7b4ce5e4e67039839ef820d8b1e1 Documentation improvements Rearrangements: IO modules Algorithms New documentation: SwapBpUGraphAdaptor Demos: strongly_connected_orientation.cc Benchmarks: swap_bipartite_bench.cc diff -r f50c8c191cbd -r 59769591eb60 benchmark/Makefile.am --- a/benchmark/Makefile.am Mon May 15 09:46:33 2006 +0000 +++ b/benchmark/Makefile.am Mon May 15 09:49:51 2006 +0000 @@ -2,7 +2,12 @@ noinst_HEADERS = bench_tools.h -noinst_PROGRAMS = graph-bench hcube bfs-bench radix_sort-bench +noinst_PROGRAMS = \ + graph-bench \ + hcube \ + swap_bipartite_bench \ + bfs-bench \ + swap_bipartite_bench graph_bench_SOURCES = graph-bench.cc @@ -11,3 +16,5 @@ bfs_bench_SOURCES = bfs-bench.cc radix_sort_bench_SOURCES = radix_sort-bench.cc + +swap_bipartite_bench_SOURCES = swap_bipartite_bench.cc \ No newline at end of file diff -r f50c8c191cbd -r 59769591eb60 benchmark/swap_bipartite_bench.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/benchmark/swap_bipartite_bench.cc Mon May 15 09:49:51 2006 +0000 @@ -0,0 +1,92 @@ +#include +#include +#include + +#include + +#include +#include + +#include +#include +#include + +#include + +using namespace std; +using namespace lemon; + +typedef SmartBpUGraph Graph; +BPUGRAPH_TYPEDEFS(Graph); + +int _urandom_init() { + int seed = time(0); + srand(seed); + return seed; +} + +int urandom(int n) { + static int seed = _urandom_init(); + return (int)(rand() / (1.0 + RAND_MAX) * n); +} + +int main() { + + for (int k = 1; k < 100; ++k) { + + int n = k * 100; + int m = (100 - k) * 100; + int e = 20000; + int s = 100; + + Timer nt(false), st(false); + + for (int i = 0; i < s; ++i) { + Graph graph; + vector aNodes; + vector bNodes; + + for (int i = 0; i < n; ++i) { + Node node = graph.addANode(); + aNodes.push_back(node); + } + for (int i = 0; i < m; ++i) { + Node node = graph.addBNode(); + bNodes.push_back(node); + } + for (int i = 0; i < e; ++i) { + Node aNode = aNodes[urandom(n)]; + Node bNode = bNodes[urandom(m)]; + graph.addEdge(aNode, bNode); + } + + { + MaxBipartiteMatching bpmatch(graph); + + nt.start(); + bpmatch.init(); + bpmatch.start(); + nt.stop(); + + } + + { + typedef SwapBpUGraphAdaptor SGraph; + SGraph sgraph(graph); + MaxBipartiteMatching bpmatch(sgraph); + + st.start(); + bpmatch.init(); + bpmatch.start(); + st.stop(); + + } + + } + + cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl; + + } + + return 0; +} diff -r f50c8c191cbd -r 59769591eb60 demo/Makefile.am --- a/demo/Makefile.am Mon May 15 09:46:33 2006 +0000 +++ b/demo/Makefile.am Mon May 15 09:49:51 2006 +0000 @@ -19,7 +19,8 @@ grid_ugraph_demo \ topology_demo \ simann_maxcut_demo \ - disjoint_paths_demo + disjoint_paths_demo \ + strongly_connected_orientation if HAVE_GLPK noinst_PROGRAMS += lp_demo lp_maxflow_demo @@ -68,4 +69,6 @@ simann_maxcut_demo_SOURCES = simann_maxcut_demo.cc -disjoint_paths_demo_SOURCES = disjoint_paths.cc +disjoint_paths_demo_SOURCES = disjoint_paths_demo.cc + +strongly_connected_orientation_SOURCES = strongly_connected_orientation.cc \ No newline at end of file diff -r f50c8c191cbd -r 59769591eb60 demo/disjoint_paths.cc --- a/demo/disjoint_paths.cc Mon May 15 09:46:33 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,107 +0,0 @@ -/* -*- C++ -*- - * - * This file is a part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2003-2006 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Research Group on Combinatorial Optimization, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -/// \ingroup demos -/// \file -/// \brief Node and edge disjoint paths in directed graph. -/// -/// This demo program calculates how many edge disjoint and node disjoint -/// paths are in a directed graph between a source and a target node. -/// The edge disjoint paths can be computed with a flow algorithm, -/// in this example we use the Preflow algorithm class. To get the node -/// disjoint paths we should first adapt the graph with the SplitGraphAdaptor -/// and just then calculate the flow. -/// -/// \include disjoint_paths.cc - -#include - -#include -#include -#include -#include -#include - -using namespace lemon; -using namespace std; - -Color color(bool b) { - return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0); -} - -int main() { - cout << "This program calculates the number " << - "of disjoint paths in a graph" << endl; - cout << "The graph is read from the disjoint_paths.lgf file" << endl; - typedef SmartGraph Graph; - - Graph graph; - - Graph::NodeMap > coords(graph); - Graph::Node source, target; - GraphReader("disjoint_paths.lgf", graph). - readNodeMap("coords", coords). - readNode("source", source).readNode("target", target).run(); - - typedef ConstMap Capacity; - Capacity capacity(1); - - Graph::EdgeMap flow(graph); - - Preflow preflow(graph, source, target, capacity, flow); - - preflow.run(); - - cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl; - - graphToEps(graph, "edge_disjoint.eps"). - title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows(). - edgeColors(composeMap(functorMap(color), flow)). - coords(coords).autoNodeScale().run(); - - - cout << "The paths are written into edge_disjoint.eps" << endl; - - typedef SplitGraphAdaptor SGraph; - - SGraph sgraph(graph); - - typedef ConstMap SCapacity; - SCapacity scapacity(1); - - SGraph::EdgeMap sflow(sgraph); - - Preflow spreflow(sgraph, SGraph::outNode(source), - SGraph::inNode(target), - scapacity, sflow); - - spreflow.run(); - - cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl; - - - graphToEps(sgraph, "node_disjoint.eps"). - title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows(). - edgeColors(composeMap(functorMap(color), sflow)). - coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy(5, 0)))). - autoNodeScale().run(); - - cout << "The paths are written into node_disjoint.eps" << endl; - - return 0; -} diff -r f50c8c191cbd -r 59769591eb60 demo/disjoint_paths.lgf --- a/demo/disjoint_paths.lgf Mon May 15 09:46:33 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,46 +0,0 @@ -@nodeset -coords label -(-20,17) 15 -(39,13) 14 -(39,-11) 13 -(-12,7) 12 -(25,-15) 11 -(-18,-14) 10 -(45,3) 9 -(28,13) 8 -(25,-5) 7 -(1,21) 6 -(3,3) 5 -(3,-9) 4 -(-9,15) 3 -(-13,-4) 2 -(-27,5) 1 -@edgeset - label -1 15 22 -8 14 20 -11 13 18 -1 12 8 -4 11 14 -1 10 1 -14 9 21 -13 9 19 -8 9 17 -7 9 16 -11 9 15 -5 8 12 -6 8 11 -5 7 13 -3 6 4 -12 5 9 -2 5 6 -3 5 5 -2 4 10 -10 4 7 -15 3 23 -1 3 3 -1 2 2 -@nodes -source 1 -target 9 -@end diff -r f50c8c191cbd -r 59769591eb60 demo/disjoint_paths_demo.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/disjoint_paths_demo.cc Mon May 15 09:49:51 2006 +0000 @@ -0,0 +1,107 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2006 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +/// \ingroup demos +/// \file +/// \brief Node and edge disjoint paths in directed graph. +/// +/// This demo program calculates how many edge disjoint and node disjoint +/// paths are in a directed graph between a source and a target node. +/// The edge disjoint paths can be computed with a flow algorithm, +/// in this example we use the Preflow algorithm class. To get the node +/// disjoint paths we should first adapt the graph with the SplitGraphAdaptor +/// and just then calculate the flow. +/// +/// \include disjoint_paths_demo.cc + +#include + +#include +#include +#include +#include +#include + +using namespace lemon; +using namespace std; + +Color color(bool b) { + return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0); +} + +int main() { + cout << "This program calculates the number " << + "of disjoint paths in a graph" << endl; + cout << "The graph is read from the disjoint_paths_demo.lgf file" << endl; + typedef SmartGraph Graph; + + Graph graph; + + Graph::NodeMap > coords(graph); + Graph::Node source, target; + GraphReader("disjoint_paths_demo.lgf", graph). + readNodeMap("coords", coords). + readNode("source", source).readNode("target", target).run(); + + typedef ConstMap Capacity; + Capacity capacity(1); + + Graph::EdgeMap flow(graph); + + Preflow preflow(graph, source, target, capacity, flow); + + preflow.run(); + + cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl; + + graphToEps(graph, "edge_disjoint_paths.eps"). + title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows(). + edgeColors(composeMap(functorMap(color), flow)). + coords(coords).autoNodeScale().run(); + + + cout << "The paths are written into edge_disjoint_paths.eps" << endl; + + typedef SplitGraphAdaptor SGraph; + + SGraph sgraph(graph); + + typedef ConstMap SCapacity; + SCapacity scapacity(1); + + SGraph::EdgeMap sflow(sgraph); + + Preflow spreflow(sgraph, SGraph::outNode(source), + SGraph::inNode(target), + scapacity, sflow); + + spreflow.run(); + + cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl; + + + graphToEps(sgraph, "node_disjoint_paths.eps"). + title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows(). + edgeColors(composeMap(functorMap(color), sflow)). + coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy(5, 0)))). + autoNodeScale().run(); + + cout << "The paths are written into node_disjoint_paths.eps" << endl; + + return 0; +} diff -r f50c8c191cbd -r 59769591eb60 demo/disjoint_paths_demo.lgf --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/disjoint_paths_demo.lgf Mon May 15 09:49:51 2006 +0000 @@ -0,0 +1,46 @@ +@nodeset +coords label +(-20,17) 15 +(39,13) 14 +(39,-11) 13 +(-12,7) 12 +(25,-15) 11 +(-18,-14) 10 +(45,3) 9 +(28,13) 8 +(25,-5) 7 +(1,21) 6 +(3,3) 5 +(3,-9) 4 +(-9,15) 3 +(-13,-4) 2 +(-27,5) 1 +@edgeset + label +1 15 22 +8 14 20 +11 13 18 +1 12 8 +4 11 14 +1 10 1 +14 9 21 +13 9 19 +8 9 17 +7 9 16 +11 9 15 +5 8 12 +6 8 11 +5 7 13 +3 6 4 +12 5 9 +2 5 6 +3 5 5 +2 4 10 +10 4 7 +15 3 23 +1 3 3 +1 2 2 +@nodes +source 1 +target 9 +@end diff -r f50c8c191cbd -r 59769591eb60 demo/strongly_connected_orientation.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/strongly_connected_orientation.cc Mon May 15 09:49:51 2006 +0000 @@ -0,0 +1,110 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2006 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include + +#include +#include +#include +#include +#include +#include + + +/// \ingroup demos +/// \file +/// \brief Strongly connected orientation +/// +/// This example demonstrates the usage of the DirUGraphAdaptor, +/// the DfsVisitor and some topology functions. The program reads +/// an input undirected graph and with a DfsVisit it orients each edge +/// to minimize the strongly connected components in the graph. At least +/// it checks the result of the orientation with to topology functions. +/// +/// \include strongly_connected_orientation.cc + +using namespace lemon; +using namespace std; + +typedef SmartUGraph UGraph; +UGRAPH_TYPEDEFS(UGraph) + +Color color(bool c) { + return c ? Color(0.0, 0.0, 0.0) : Color(1.0, 0.0, 0.0); +} + +template +class OrientVisitor : public DfsVisitor { +public: + + OrientVisitor(const UGraph& ugraph, DirMap& dirMap) + : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {} + + void discover(const Edge& edge) { + _processed.set(edge, true); + _dirMap.set(edge, _ugraph.direction(edge)); + } + + void examine(const Edge& edge) { + if (_processed[edge]) return; + _processed.set(edge, true); + _dirMap.set(edge, _ugraph.direction(edge)); + } + +private: + const UGraph& _ugraph; + DirMap& _dirMap; + UGraph::UEdgeMap _processed; +}; + + +int main(int argc, const char *argv[]) { + cout << "Orientation of the strongly_connected_orientation.lgf " + << "to be strongly connected" << endl; + + UGraph ugraph; + UGraph::NodeMap > coords(ugraph); + UGraphReader("strongly_connected_orientation.lgf", ugraph). + readNodeMap("coords", coords).run(); + + UGraph::UEdgeMap dmap(ugraph); + + typedef OrientVisitor > Visitor; + Visitor visitor(ugraph, dmap); + + DfsVisit dfs(ugraph, visitor); + + dfs.run(); + + typedef DirUGraphAdaptor DGraph; + DGraph dgraph(ugraph, dmap); + + cout << "The result written into the " + << "strongly_connected_orientation.eps file" << endl; + + graphToEps(dgraph, "strongly_connected_orientation.eps"). + drawArrows().coords(coords).scaleToA4().enableParallel(). + autoNodeScale().autoEdgeWidthScale().run(); + + int num_scc = countStronglyConnectedComponents(dgraph); + int num_becc = countBiEdgeConnectedComponents(ugraph); + + LEMON_ASSERT(num_scc == num_becc, "Wrong Orientation"); + + return 0; +} diff -r f50c8c191cbd -r 59769591eb60 demo/strongly_connected_orientation.lgf --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/demo/strongly_connected_orientation.lgf Mon May 15 09:49:51 2006 +0000 @@ -0,0 +1,26 @@ +@nodeset +coords label +(12,6) 9 +(-12,3) 8 +(-34,6) 7 +(-23,22) 6 +(16,26) 5 +(43,8) 4 +(24,-8) 3 +(-4,-14) 2 +(-29,-11) 1 +@uedgeset + label +5 9 9 +9 8 5 +7 6 7 +8 6 6 +4 5 11 +6 5 8 +3 4 12 +9 4 10 +3 2 4 +8 2 3 +1 2 2 +7 1 1 +@end diff -r f50c8c191cbd -r 59769591eb60 doc/graph-adaptors.dox --- a/doc/graph-adaptors.dox Mon May 15 09:46:33 2006 +0000 +++ b/doc/graph-adaptors.dox Mon May 15 09:49:51 2006 +0000 @@ -36,8 +36,8 @@ The code looks as follows \code ListGraph g; - RevGraphAdaptor rgw(g); - int result=algorithm(rgw); + RevGraphAdaptor rga(g); + int result=algorithm(rga); \endcode After running the algorithm, the original graph \c g is untouched. @@ -58,7 +58,7 @@ capabilities of the original graph while in other cases this would be meaningless. This means that the concepts that they are models of depend on the graph adaptor, and the wrapped graph(s). - If an edge of \c rgw is deleted, this is carried out by + If an edge of \c rga is deleted, this is carried out by deleting the corresponding edge of \c g, thus the adaptor modifies the original graph. But for a residual @@ -73,8 +73,8 @@ then it have to be instantiated with Graph=const ListGraph. \code int algorithm1(const ListGraph& g) { - RevGraphAdaptor rgw(g); - return algorithm2(rgw); + RevGraphAdaptor rga(g); + return algorithm2(rga); } \endcode */ diff -r f50c8c191cbd -r 59769591eb60 doc/groups.dox --- a/doc/groups.dox Mon May 15 09:46:33 2006 +0000 +++ b/doc/groups.dox Mon May 15 09:49:51 2006 +0000 @@ -14,13 +14,14 @@ planned to be easily used in an experimental phase of implementation studies, and thereafter the program code can be made efficient by small modifications. -The most efficient implementation of diverse applications require the usage of different physical graph implementations. These differences appear in the size of -graph we require to handle, memory or time usage limitations or in -the set of operations through which the graph can be accessed. -LEMON provides several physical graph structures to meet the -diverging requirements of the possible users. -In order to save on running time or on memory usage, some structures may -fail to provide some graph features like edge or node deletion. +The most efficient implementation of diverse applications require the +usage of different physical graph implementations. These differences +appear in the size of graph we require to handle, memory or time usage +limitations or in the set of operations through which the graph can be +accessed. LEMON provides several physical graph structures to meet +the diverging requirements of the possible users. In order to save on +running time or on memory usage, some structures may fail to provide +some graph features like edge or node deletion. Alteration of standard containers need a very limited number of operations, these together satisfy the everyday requirements. @@ -76,7 +77,7 @@ Map adaptors are used to create "implicit" maps from other maps. Most of them are \ref lemon::concept::ReadMap "ReadMap"s. They can -make arithmetic oprerations between one or two maps (negation, scalig, +make arithmetic oprerations between one or two maps (negation, scaling, addition, multiplication etc.) or e.g. convert a map to another one of different Value type. */ @@ -86,10 +87,24 @@ @ingroup datas \brief Two dimensional data storages. -Two dimensional -data storages. +Two dimensional data storages. */ +/** +@defgroup paths Path Structures +@ingroup datas +\brief Path structures implemented in LEMON. + +LEMON provides flexible data structures +to work with paths. + +All of them have the same interface, especially they can be built or extended +using a standard Builder subclass. This make is easy to have e.g. the Dijkstra +algorithm to store its result in any kind of path structure. + +\sa lemon::concept::Path + +*/ /** @defgroup auxdat Auxiliary Data Structures @@ -110,35 +125,25 @@ */ /** -@defgroup galgs Graph Algorithms -\brief This group describes the several graph algorithms +@defgroup algs Algorithms +\brief This group describes the several algorithms implemented in LEMON. -This group describes the several graph algorithms +This group describes the several algorithms implemented in LEMON. */ /** @defgroup gutils General Graph Utilities -@ingroup galgs +@ingroup algs \brief This group describes some simple general graph utilities. This group describes some simple general graph utilities. */ /** -@defgroup gen_opt_group General Optimization Tools -\brief This group describes some general optimization frameworks -implemented in LEMON. - -This group describes some general optimization frameworks -implemented in LEMON. - -*/ - -/** @defgroup flowalgs Path and Flow Algorithms -@ingroup galgs +@ingroup algs \brief This group describes the algorithms for finding paths and flows in graphs. @@ -151,7 +156,7 @@ /** @defgroup topology Topology related algorithms -@ingroup galgs +@ingroup algs \brief This group describes the algorithms for discover the topology of the graphs. @@ -165,7 +170,7 @@ /** @defgroup matching Matching algorithms in graphs and bipartite graphs -@ingroup galgs +@ingroup algs \brief This group describes the algorithms for find matchings in graphs and bipartite graphs. @@ -178,8 +183,34 @@ */ /** -@defgroup exceptions Exceptions -This group contains the exceptions thrown by LEMON library +@defgroup spantree Minimum Cost Spanning Tree Algorithms +@ingroup algs +\brief This group containes the algorithms for finding a minimum cost spanning +tree in a graph + +This group containes the algorithms for finding a minimum cost spanning +tree in a graph +*/ + + +/** +@defgroup auxalg Auxiliary Algorithms +@ingroup algs +\brief Some algorithms implemented in LEMON. + +This group describes the algorithms in LEMON in order to make +it easier to implement complex algorithms. + +*/ + +/** +@defgroup gen_opt_group General Optimization Tools +\brief This group describes some general optimization frameworks +implemented in LEMON. + +This group describes some general optimization frameworks +implemented in LEMON. + */ /** @@ -197,13 +228,27 @@ /** @defgroup io_group Input-Output -Here you can find tools for imporing and exporting graphs and graph related -data +\brief Several Graph Input-Output methods + +Here you can find tools for importing and exporting graphs +and graph related data. Now it supports the LEMON format, the +dimacs format and the encapsulated postscript format. +*/ + +/** +@defgroup lemon_io Lemon Input-Output +@ingroup io_group +\brief Reading and writing LEMON format + +Methods for reading and writing LEMON format. More about this +format you can find on the \ref graph-io-page "Graph Input-Output" +tutorial pages. + */ /** @defgroup section_io Section readers and writers -@ingroup io_group +@ingroup lemon_io \brief Section readers and writers for lemon Input-Output. Here you can find which section readers and writers can attach to @@ -212,7 +257,7 @@ /** @defgroup item_io Item Readers and Writers -@ingroup io_group +@ingroup lemon_io \brief Item readers and writers for lemon Input-Output. The Input-Output classes can handle more data type by example @@ -221,6 +266,20 @@ */ /** +@defgroup eps_io Postscript exporting +@ingroup io_group +\brief General EPS drawer and graph exporter + +This group contains general EPS drawing methods and special +graph exporting tools. +*/ + +/** +@defgroup exceptions Exceptions +This group contains the exceptions thrown by LEMON library +*/ + +/** @defgroup concept Concepts \brief Skeleton classes and concept checking classes @@ -234,6 +293,7 @@ */ + /** @defgroup graph_concepts Graph Structure Concepts @ingroup concept diff -r f50c8c191cbd -r 59769591eb60 doc/images/swap_test.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/images/swap_test.eps Mon May 15 09:49:51 2006 +0000 @@ -0,0 +1,763 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: swap_test.eps +%%Creator: gnuplot 4.0 patchlevel 0 +%%CreationDate: Sat May 13 18:29:57 2006 +%%DocumentFonts: (atend) +%%BoundingBox: 50 50 338 251 +%%Orientation: Portrait +%%EndComments +/gnudict 256 dict def +gnudict begin +/Color false def +/Solid false def +/gnulinewidth 5.000 def +/userlinewidth gnulinewidth def +/vshift -46 def +/dl {10.0 mul} def +/hpt_ 31.5 def +/vpt_ 31.5 def +/hpt hpt_ def +/vpt vpt_ def +/Rounded false def +/M {moveto} bind def +/L {lineto} bind def +/R {rmoveto} bind def +/V {rlineto} bind def +/N {newpath moveto} bind def +/C {setrgbcolor} bind def +/f {rlineto fill} bind def +/vpt2 vpt 2 mul def +/hpt2 hpt 2 mul def +/Lshow { currentpoint stroke M + 0 vshift R show } def +/Rshow { currentpoint stroke M + dup stringwidth pop neg vshift R show } def +/Cshow { currentpoint stroke M + dup stringwidth pop -2 div vshift R show } def +/UP { dup vpt_ mul /vpt exch def hpt_ mul /hpt exch def + /hpt2 hpt 2 mul def /vpt2 vpt 2 mul def } def +/DL { Color {setrgbcolor Solid {pop []} if 0 setdash } + {pop pop pop 0 setgray Solid {pop []} if 0 setdash} ifelse } def +/BL { stroke userlinewidth 2 mul setlinewidth + Rounded { 1 setlinejoin 1 setlinecap } if } def +/AL { stroke userlinewidth 2 div setlinewidth + Rounded { 1 setlinejoin 1 setlinecap } if } def +/UL { dup gnulinewidth mul /userlinewidth exch def + dup 1 lt {pop 1} if 10 mul /udl exch def } def +/PL { stroke userlinewidth setlinewidth + Rounded { 1 setlinejoin 1 setlinecap } if } def +/LTw { PL [] 1 setgray } def +/LTb { BL [] 0 0 0 DL } def +/LTa { AL [1 udl mul 2 udl mul] 0 setdash 0 0 0 setrgbcolor } def +/LT0 { PL [] 1 0 0 DL } def +/LT1 { PL [4 dl 2 dl] 0 1 0 DL } def +/LT2 { PL [2 dl 3 dl] 0 0 1 DL } def +/LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def +/LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def +/LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def +/LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def +/LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def +/LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def +/Pnt { stroke [] 0 setdash + gsave 1 setlinecap M 0 0 V stroke grestore } def +/Dia { stroke [] 0 setdash 2 copy vpt add M + hpt neg vpt neg V hpt vpt neg V + hpt vpt V hpt neg vpt V closepath stroke + Pnt } def +/Pls { stroke [] 0 setdash vpt sub M 0 vpt2 V + currentpoint stroke M + hpt neg vpt neg R hpt2 0 V stroke + } def +/Box { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M + 0 vpt2 neg V hpt2 0 V 0 vpt2 V + hpt2 neg 0 V closepath stroke + Pnt } def +/Crs { stroke [] 0 setdash exch hpt sub exch vpt add M + hpt2 vpt2 neg V currentpoint stroke M + hpt2 neg 0 R hpt2 vpt2 V stroke } def +/TriU { stroke [] 0 setdash 2 copy vpt 1.12 mul add M + hpt neg vpt -1.62 mul V + hpt 2 mul 0 V + hpt neg vpt 1.62 mul V closepath stroke + Pnt } def +/Star { 2 copy Pls Crs } def +/BoxF { stroke [] 0 setdash exch hpt sub exch vpt add M + 0 vpt2 neg V hpt2 0 V 0 vpt2 V + hpt2 neg 0 V closepath fill } def +/TriUF { stroke [] 0 setdash vpt 1.12 mul add M + hpt neg vpt -1.62 mul V + hpt 2 mul 0 V + hpt neg vpt 1.62 mul V closepath fill } def +/TriD { stroke [] 0 setdash 2 copy vpt 1.12 mul sub M + hpt neg vpt 1.62 mul V + hpt 2 mul 0 V + hpt neg vpt -1.62 mul V closepath stroke + Pnt } def +/TriDF { stroke [] 0 setdash vpt 1.12 mul sub M + hpt neg vpt 1.62 mul V + hpt 2 mul 0 V + hpt neg vpt -1.62 mul V closepath fill} def +/DiaF { stroke [] 0 setdash vpt add M + hpt neg vpt neg V hpt vpt neg V + hpt vpt V hpt neg vpt V closepath fill } def +/Pent { stroke [] 0 setdash 2 copy gsave + translate 0 hpt M 4 {72 rotate 0 hpt L} repeat + closepath stroke grestore Pnt } def +/PentF { stroke [] 0 setdash gsave + translate 0 hpt M 4 {72 rotate 0 hpt L} repeat + closepath fill grestore } def +/Circle { stroke [] 0 setdash 2 copy + hpt 0 360 arc stroke Pnt } def +/CircleF { stroke [] 0 setdash hpt 0 360 arc fill } def +/C0 { BL [] 0 setdash 2 copy moveto vpt 90 450 arc } bind def +/C1 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 0 90 arc closepath fill + vpt 0 360 arc closepath } bind def +/C2 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 90 180 arc closepath fill + vpt 0 360 arc closepath } bind def +/C3 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 0 180 arc closepath fill + vpt 0 360 arc closepath } bind def +/C4 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 180 270 arc closepath fill + vpt 0 360 arc closepath } bind def +/C5 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 0 90 arc + 2 copy moveto + 2 copy vpt 180 270 arc closepath fill + vpt 0 360 arc } bind def +/C6 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 90 270 arc closepath fill + vpt 0 360 arc closepath } bind def +/C7 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 0 270 arc closepath fill + vpt 0 360 arc closepath } bind def +/C8 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 270 360 arc closepath fill + vpt 0 360 arc closepath } bind def +/C9 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 270 450 arc closepath fill + vpt 0 360 arc closepath } bind def +/C10 { BL [] 0 setdash 2 copy 2 copy moveto vpt 270 360 arc closepath fill + 2 copy moveto + 2 copy vpt 90 180 arc closepath fill + vpt 0 360 arc closepath } bind def +/C11 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 0 180 arc closepath fill + 2 copy moveto + 2 copy vpt 270 360 arc closepath fill + vpt 0 360 arc closepath } bind def +/C12 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 180 360 arc closepath fill + vpt 0 360 arc closepath } bind def +/C13 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 0 90 arc closepath fill + 2 copy moveto + 2 copy vpt 180 360 arc closepath fill + vpt 0 360 arc closepath } bind def +/C14 { BL [] 0 setdash 2 copy moveto + 2 copy vpt 90 360 arc closepath fill + vpt 0 360 arc } bind def +/C15 { BL [] 0 setdash 2 copy vpt 0 360 arc closepath fill + vpt 0 360 arc closepath } bind def +/Rec { newpath 4 2 roll moveto 1 index 0 rlineto 0 exch rlineto + neg 0 rlineto closepath } bind def +/Square { dup Rec } bind def +/Bsquare { vpt sub exch vpt sub exch vpt2 Square } bind def +/S0 { BL [] 0 setdash 2 copy moveto 0 vpt rlineto BL Bsquare } bind def +/S1 { BL [] 0 setdash 2 copy vpt Square fill Bsquare } bind def +/S2 { BL [] 0 setdash 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def +/S3 { BL [] 0 setdash 2 copy exch vpt sub exch vpt2 vpt Rec fill Bsquare } bind def +/S4 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def +/S5 { BL [] 0 setdash 2 copy 2 copy vpt Square fill + exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def +/S6 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill Bsquare } bind def +/S7 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill + 2 copy vpt Square fill + Bsquare } bind def +/S8 { BL [] 0 setdash 2 copy vpt sub vpt Square fill Bsquare } bind def +/S9 { BL [] 0 setdash 2 copy vpt sub vpt vpt2 Rec fill Bsquare } bind def +/S10 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt Square fill + Bsquare } bind def +/S11 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt2 vpt Rec fill + Bsquare } bind def +/S12 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill Bsquare } bind def +/S13 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill + 2 copy vpt Square fill Bsquare } bind def +/S14 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill + 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def +/S15 { BL [] 0 setdash 2 copy Bsquare fill Bsquare } bind def +/D0 { gsave translate 45 rotate 0 0 S0 stroke grestore } bind def +/D1 { gsave translate 45 rotate 0 0 S1 stroke grestore } bind def +/D2 { gsave translate 45 rotate 0 0 S2 stroke grestore } bind def +/D3 { gsave translate 45 rotate 0 0 S3 stroke grestore } bind def +/D4 { gsave translate 45 rotate 0 0 S4 stroke grestore } bind def +/D5 { gsave translate 45 rotate 0 0 S5 stroke grestore } bind def +/D6 { gsave translate 45 rotate 0 0 S6 stroke grestore } bind def +/D7 { gsave translate 45 rotate 0 0 S7 stroke grestore } bind def +/D8 { gsave translate 45 rotate 0 0 S8 stroke grestore } bind def +/D9 { gsave translate 45 rotate 0 0 S9 stroke grestore } bind def +/D10 { gsave translate 45 rotate 0 0 S10 stroke grestore } bind def +/D11 { gsave translate 45 rotate 0 0 S11 stroke grestore } bind def +/D12 { gsave translate 45 rotate 0 0 S12 stroke grestore } bind def +/D13 { gsave translate 45 rotate 0 0 S13 stroke grestore } bind def +/D14 { gsave translate 45 rotate 0 0 S14 stroke grestore } bind def +/D15 { gsave translate 45 rotate 0 0 S15 stroke grestore } bind def +/DiaE { stroke [] 0 setdash vpt add M + hpt neg vpt neg V hpt vpt neg V + hpt vpt V hpt neg vpt V closepath stroke } def +/BoxE { stroke [] 0 setdash exch hpt sub exch vpt add M + 0 vpt2 neg V hpt2 0 V 0 vpt2 V + hpt2 neg 0 V closepath stroke } def +/TriUE { stroke [] 0 setdash vpt 1.12 mul add M + hpt neg vpt -1.62 mul V + hpt 2 mul 0 V + hpt neg vpt 1.62 mul V closepath stroke } def +/TriDE { stroke [] 0 setdash vpt 1.12 mul sub M + hpt neg vpt 1.62 mul V + hpt 2 mul 0 V + hpt neg vpt -1.62 mul V closepath stroke } def +/PentE { stroke [] 0 setdash gsave + translate 0 hpt M 4 {72 rotate 0 hpt L} repeat + closepath stroke grestore } def +/CircE { stroke [] 0 setdash + hpt 0 360 arc stroke } def +/Opaque { gsave closepath 1 setgray fill grestore 0 setgray closepath } def +/DiaW { stroke [] 0 setdash vpt add M + hpt neg vpt neg V hpt vpt neg V + hpt vpt V hpt neg vpt V Opaque stroke } def +/BoxW { stroke [] 0 setdash exch hpt sub exch vpt add M + 0 vpt2 neg V hpt2 0 V 0 vpt2 V + hpt2 neg 0 V Opaque stroke } def +/TriUW { stroke [] 0 setdash vpt 1.12 mul add M + hpt neg vpt -1.62 mul V + hpt 2 mul 0 V + hpt neg vpt 1.62 mul V Opaque stroke } def +/TriDW { stroke [] 0 setdash vpt 1.12 mul sub M + hpt neg vpt 1.62 mul V + hpt 2 mul 0 V + hpt neg vpt -1.62 mul V Opaque stroke } def +/PentW { stroke [] 0 setdash gsave + translate 0 hpt M 4 {72 rotate 0 hpt L} repeat + Opaque stroke grestore } def +/CircW { stroke [] 0 setdash + hpt 0 360 arc Opaque stroke } def +/BoxFill { gsave Rec 1 setgray fill grestore } def +/BoxColFill { + gsave Rec + /Fillden exch def + currentrgbcolor + /ColB exch def /ColG exch def /ColR exch def + /ColR ColR Fillden mul Fillden sub 1 add def + /ColG ColG Fillden mul Fillden sub 1 add def + /ColB ColB Fillden mul Fillden sub 1 add def + ColR ColG ColB setrgbcolor + fill grestore } def +% +% PostScript Level 1 Pattern Fill routine +% Usage: x y w h s a XX PatternFill +% x,y = lower left corner of box to be filled +% w,h = width and height of box +% a = angle in degrees between lines and x-axis +% XX = 0/1 for no/yes cross-hatch +% +/PatternFill { gsave /PFa [ 9 2 roll ] def + PFa 0 get PFa 2 get 2 div add PFa 1 get PFa 3 get 2 div add translate + PFa 2 get -2 div PFa 3 get -2 div PFa 2 get PFa 3 get Rec + gsave 1 setgray fill grestore clip + currentlinewidth 0.5 mul setlinewidth + /PFs PFa 2 get dup mul PFa 3 get dup mul add sqrt def + 0 0 M PFa 5 get rotate PFs -2 div dup translate + 0 1 PFs PFa 4 get div 1 add floor cvi + { PFa 4 get mul 0 M 0 PFs V } for + 0 PFa 6 get ne { + 0 1 PFs PFa 4 get div 1 add floor cvi + { PFa 4 get mul 0 2 1 roll M PFs 0 V } for + } if + stroke grestore } def +% +/Symbol-Oblique /Symbol findfont [1 0 .167 1 0 0] makefont +dup length dict begin {1 index /FID eq {pop pop} {def} ifelse} forall +currentdict end definefont pop +end +%%EndProlog +gnudict begin +gsave +50 50 translate +0.050 0.050 scale +0 setgray +newpath +(Helvetica) findfont 140 scalefont setfont +1.000 UL +LTb +574 280 M +63 0 V +4885 0 R +-63 0 V +490 280 M +gsave 0 setgray +( 0) Rshow +grestore +1.000 UL +LTb +574 606 M +63 0 V +4885 0 R +-63 0 V +490 606 M +gsave 0 setgray +( 0.5) Rshow +grestore +1.000 UL +LTb +574 932 M +63 0 V +4885 0 R +-63 0 V +490 932 M +gsave 0 setgray +( 1) Rshow +grestore +1.000 UL +LTb +574 1257 M +63 0 V +4885 0 R +-63 0 V +-4969 0 R +gsave 0 setgray +( 1.5) Rshow +grestore +1.000 UL +LTb +574 1583 M +63 0 V +4885 0 R +-63 0 V +-4969 0 R +gsave 0 setgray +( 2) Rshow +grestore +1.000 UL +LTb +574 1909 M +63 0 V +4885 0 R +-63 0 V +-4969 0 R +gsave 0 setgray +( 2.5) Rshow +grestore +1.000 UL +LTb +574 2235 M +63 0 V +4885 0 R +-63 0 V +-4969 0 R +gsave 0 setgray +( 3) Rshow +grestore +1.000 UL +LTb +574 2561 M +63 0 V +4885 0 R +-63 0 V +-4969 0 R +gsave 0 setgray +( 3.5) Rshow +grestore +1.000 UL +LTb +574 2887 M +63 0 V +4885 0 R +-63 0 V +-4969 0 R +gsave 0 setgray +( 4) Rshow +grestore +1.000 UL +LTb +574 3212 M +63 0 V +4885 0 R +-63 0 V +-4969 0 R +gsave 0 setgray +( 4.5) Rshow +grestore +1.000 UL +LTb +574 3538 M +63 0 V +4885 0 R +-63 0 V +-4969 0 R +gsave 0 setgray +( 5) Rshow +grestore +1.000 UL +LTb +574 3864 M +63 0 V +4885 0 R +-63 0 V +-4969 0 R +gsave 0 setgray +( 5.5) Rshow +grestore +1.000 UL +LTb +574 280 M +0 63 V +0 3521 R +0 -63 V +574 140 M +gsave 0 setgray +( 0) Cshow +grestore +1.000 UL +LTb +1069 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 1000) Cshow +grestore +1.000 UL +LTb +1564 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 2000) Cshow +grestore +1.000 UL +LTb +2058 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 3000) Cshow +grestore +1.000 UL +LTb +2553 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 4000) Cshow +grestore +1.000 UL +LTb +3048 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 5000) Cshow +grestore +1.000 UL +LTb +3543 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 6000) Cshow +grestore +1.000 UL +LTb +4038 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 7000) Cshow +grestore +1.000 UL +LTb +4532 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 8000) Cshow +grestore +1.000 UL +LTb +5027 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 9000) Cshow +grestore +1.000 UL +LTb +5522 280 M +0 63 V +0 3521 R +0 -63 V +0 -3661 R +gsave 0 setgray +( 10000) Cshow +grestore +1.000 UL +LTb +1.000 UL +LTb +574 280 M +4948 0 V +0 3584 V +-4948 0 V +574 280 L +1.000 UP +1.000 UL +LT5 +LTb +4871 3731 M +gsave 0 setgray +(Original) Rshow +grestore +LT5 +4955 3731 M +399 0 V +623 521 M +50 2 V +49 -7 V +50 33 V +49 -25 V +50 21 V +49 2 V +50 0 V +49 1 V +50 -6 V +49 5 V +50 4 V +49 4 V +50 10 V +49 0 V +50 2 V +49 -1 V +50 9 V +49 2 V +50 6 V +49 36 V +50 2 V +49 21 V +50 8 V +49 11 V +49 5 V +50 5 V +49 2 V +50 104 V +49 -82 V +50 13 V +49 4 V +50 16 V +49 36 V +50 32 V +49 -5 V +50 32 V +49 36 V +50 30 V +49 -8 V +50 42 V +49 28 V +50 33 V +49 43 V +50 58 V +49 78 V +50 95 V +49 126 V +50 285 V +49 1708 V +49 -665 V +50 -235 V +49 -143 V +50 -103 V +49 -101 V +50 -118 V +49 -94 V +50 -40 V +49 -57 V +50 -133 V +49 5 V +50 -16 V +49 57 V +50 -144 V +49 -37 V +50 -48 V +49 -64 V +50 17 V +49 -67 V +50 -41 V +49 -18 V +50 -9 V +49 10 V +50 -5 V +49 -2 V +49 -26 V +50 -26 V +49 -42 V +50 50 V +49 -78 V +50 -51 V +49 -13 V +50 9 V +49 -8 V +50 0 V +49 -1 V +50 -7 V +49 1 V +50 -4 V +49 -13 V +50 -7 V +49 -25 V +50 5 V +49 -11 V +50 -16 V +49 -9 V +50 -24 V +49 -2 V +50 -21 V +1.000 UL +LT0 +LTb +4871 3591 M +gsave 0 setgray +(Swapped) Rshow +grestore +LT0 +4955 3591 M +399 0 V +623 1034 M +50 -1 V +49 30 V +50 -5 V +49 57 V +50 -20 V +49 26 V +50 0 V +49 11 V +50 -10 V +49 25 V +50 6 V +49 6 V +50 -16 V +49 21 V +50 15 V +49 82 V +50 -88 V +49 26 V +50 37 V +49 1 V +50 22 V +49 64 V +50 21 V +49 -3 V +49 11 V +50 -8 V +49 29 V +50 8 V +49 6 V +50 29 V +49 7 V +50 119 V +49 26 V +50 49 V +49 32 V +50 24 V +49 64 V +50 -9 V +49 51 V +50 35 V +49 84 V +50 99 V +49 77 V +50 87 V +49 84 V +50 212 V +49 48 V +50 281 V +49 771 V +49 -1861 V +50 -283 V +49 -116 V +50 -117 V +49 -89 V +50 -47 V +49 -54 V +50 -29 V +49 -32 V +50 -39 V +49 -18 V +50 14 V +49 -48 V +50 -29 V +49 -22 V +50 -17 V +49 -26 V +50 4 V +49 -30 V +50 -12 V +49 -12 V +50 -1 V +49 -21 V +50 -9 V +49 21 V +49 -20 V +50 -8 V +49 -7 V +50 -19 V +49 -21 V +50 -11 V +49 2 V +50 -6 V +49 -7 V +50 2 V +49 72 V +50 -87 V +49 -7 V +50 5 V +49 -12 V +50 1 V +49 4 V +50 -2 V +49 -14 V +50 -10 V +49 -2 V +50 19 V +49 -29 V +50 5 V +1.000 UL +LTb +574 280 M +4948 0 V +0 3584 V +-4948 0 V +574 280 L +1.000 UP +stroke +grestore +end +showpage +%%Trailer +%%DocumentFonts: Helvetica diff -r f50c8c191cbd -r 59769591eb60 doc/images/swap_test.png Binary file doc/images/swap_test.png has changed diff -r f50c8c191cbd -r 59769591eb60 lemon/bpugraph_adaptor.h --- a/lemon/bpugraph_adaptor.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/bpugraph_adaptor.h Mon May 15 09:49:51 2006 +0000 @@ -409,8 +409,35 @@ /// \brief Bipartite graph adaptor which swaps the two nodeset. /// /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's - /// a-nodeset will be the original graph's b-nodeset and the adaptor's - /// b-nodeset will be the original graph's a-nodeset. + /// anode-set will be the original graph's bnode-set and the adaptor's + /// bnode-set will be the original graph's anode-set. + /// + /// As example look at an algorithm what can be sped up with the + /// swap bipartite undirected graph adaptor. If we want to find the + /// maximum matching in the bipartite graph then it will be not changed + /// if we swap the two nodesets. But the algorithm use the two nodeset + /// different way. If we swap the nodesets it provides different + /// running time. We run a test on random bipartite graphs with + /// different rate of the anode-set size and bnode-set size. + /// We always made graphs with 10000 nodes and 20000 edges and we + /// computed the maximum cardinality matching with the Hopcroft-Karp + /// algorithm. + /// + /// The next diagram shows the running time of the tests. If the anode-set + /// is smaller than the bnode-set the running time is better than with + /// the swapped graph. Other conclusion is that the running time + /// is greater when the two nodesets size are nearly equal. + /// + /// \image html swap_test.png + /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth + /// + /// The next part shows how can we swap the two nodeset: + /// + ///\code + /// typedef SwapBpUGraphAdaptor SBpUGraph; + /// SBpUGraph sbpugraph(bpugraph); + /// MaxBipartiteMatching sbpumatch(sbpugraph); + ///\endcode template class SwapBpUGraphAdaptor : public BpUGraphAdaptorExtender > { @@ -425,6 +452,9 @@ public: + /// \brief Construct a swapped graph. + /// + /// Construct a swapped graph. explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); } }; diff -r f50c8c191cbd -r 59769591eb60 lemon/eps.h --- a/lemon/eps.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/eps.h Mon May 15 09:49:51 2006 +0000 @@ -26,7 +26,7 @@ #include #include - ///\ingroup io_group + ///\ingroup eps_io ///\file ///\brief Simple tool to create \c .eps files /// @@ -34,7 +34,7 @@ namespace lemon { - ///\ingroup io_group + ///\ingroup eps_io ///\brief A simple tool to create \c .eps files /// ///A simple tool to create \c .eps files diff -r f50c8c191cbd -r 59769591eb60 lemon/graph_adaptor.h --- a/lemon/graph_adaptor.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/graph_adaptor.h Mon May 15 09:49:51 2006 +0000 @@ -264,6 +264,40 @@ ///\endcode /// implements the graph obtained from \c g by /// reversing the orientation of its edges. + /// + /// A good example of using RevGraphAdaptor is to decide that the + /// directed graph is wheter strongly connected or not. If from one + /// node each node is reachable and from each node is reachable this + /// node then and just then the graph is strongly connected. Instead of + /// this condition we use a little bit different. From one node each node + /// ahould be reachable in the graph and in the reversed graph. Now this + /// condition can be checked with the Dfs algorithm class and the + /// RevGraphAdaptor algorithm class. + /// + /// And look at the code: + /// + ///\code + /// bool stronglyConnected(const Graph& graph) { + /// if (NodeIt(graph) == INVALID) return true; + /// Dfs dfs(graph); + /// dfs.run(NodeIt(graph)); + /// for (NodeIt it(graph); it != INVALID; ++it) { + /// if (!dfs.reached(it)) { + /// return false; + /// } + /// } + /// typedef RevGraphAdaptor RGraph; + /// RGraph rgraph(graph); + /// DfsVisit rdfs(rgraph); + /// rdfs.run(NodeIt(graph)); + /// for (NodeIt it(graph); it != INVALID; ++it) { + /// if (!rdfs.reached(it)) { + /// return false; + /// } + /// } + /// return true; + /// } + ///\endcode template class RevGraphAdaptor : public GraphAdaptorExtender > { @@ -2387,7 +2421,7 @@ /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth /// /// The second solution contains just 3 disjoint paths while the first 4. - /// The full code can be found in the \ref disjoint_paths.cc demo file. + /// The full code can be found in the \ref disjoint_paths_demo.cc demo file. /// /// This graph adaptor is fully conform to the /// \ref concept::StaticGraph "StaticGraph" concept and @@ -2587,6 +2621,15 @@ }; + /// \brief Just gives back a split graph adaptor + /// + /// Just gives back a split graph adaptor + template + SplitGraphAdaptor + splitGraphAdaptor(const Graph& graph) { + return SplitGraphAdaptor(graph); + } + } //namespace lemon diff -r f50c8c191cbd -r 59769591eb60 lemon/graph_reader.h --- a/lemon/graph_reader.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/graph_reader.h Mon May 15 09:49:51 2006 +0000 @@ -16,7 +16,7 @@ * */ -///\ingroup io_group +///\ingroup lemon_io ///\file ///\brief Lemon Graph Format reader. @@ -30,7 +30,7 @@ namespace lemon { - /// \addtogroup io_group + /// \addtogroup lemon_io /// @{ /// \brief The graph reader class. diff -r f50c8c191cbd -r 59769591eb60 lemon/graph_to_eps.h --- a/lemon/graph_to_eps.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/graph_to_eps.h Mon May 15 09:49:51 2006 +0000 @@ -41,7 +41,7 @@ #include -///\ingroup io_group +///\ingroup eps_io ///\file ///\brief Simple graph drawer /// @@ -1042,7 +1042,7 @@ ///Generates an EPS file from a graph -///\ingroup io_group +///\ingroup eps_io ///Generates an EPS file from a graph. ///\param g is a reference to the graph to be printed ///\param os is a reference to the output stream. @@ -1071,7 +1071,7 @@ ///Generates an EPS file from a graph -///\ingroup io_group +///\ingroup eps_io ///This function does the same as ///\ref graphToEps(G &g,std::ostream& os) ///but it writes its output into the file \c file_name @@ -1087,7 +1087,7 @@ ///Generates an EPS file from a graph -///\ingroup io_group +///\ingroup eps_io ///This function does the same as ///\ref graphToEps(G &g,std::ostream& os) ///but it writes its output into the file \c file_name diff -r f50c8c191cbd -r 59769591eb60 lemon/kruskal.h --- a/lemon/kruskal.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/kruskal.h Mon May 15 09:49:51 2006 +0000 @@ -25,16 +25,6 @@ #include #include -/** -@defgroup spantree Minimum Cost Spanning Tree Algorithms -@ingroup galgs -\brief This group containes the algorithms for finding a minimum cost spanning -tree in a graph - -This group containes the algorithms for finding a minimum cost spanning -tree in a graph -*/ - ///\ingroup spantree ///\file ///\brief Kruskal's algorithm to compute a minimum cost tree diff -r f50c8c191cbd -r 59769591eb60 lemon/lemon_reader.h --- a/lemon/lemon_reader.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/lemon_reader.h Mon May 15 09:49:51 2006 +0000 @@ -16,7 +16,7 @@ * */ -///\ingroup io_group +///\ingroup lemon_io ///\file ///\brief Lemon Format reader. @@ -456,7 +456,7 @@ } - /// \ingroup io_group + /// \ingroup lemon_io /// \brief Lemon Format reader class. /// /// The Lemon Format contains several sections. We do not want to @@ -523,9 +523,9 @@ char_type* eptr() { return _eptr; } - int blen() { return _eptr - _base; } + int_type blen() { return _eptr - _base; } - void setb(char_type* buf, int len) { + void setb(char_type* buf, int_type len) { _base = buf; _eptr = buf + len; } @@ -581,7 +581,7 @@ return false; } - virtual int underflow() { + virtual int_type underflow() { char c; if (_is.read(&c, 1)) { _is.putback(c); @@ -612,7 +612,7 @@ return *base(); } - virtual int sync() { + virtual int_type sync() { return EOF; } }; diff -r f50c8c191cbd -r 59769591eb60 lemon/lemon_writer.h --- a/lemon/lemon_writer.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/lemon_writer.h Mon May 15 09:49:51 2006 +0000 @@ -16,7 +16,7 @@ * */ -///\ingroup io_group +///\ingroup lemon_io ///\file ///\brief Lemon Format writer. @@ -257,7 +257,7 @@ } - /// \ingroup io_group + /// \ingroup lemon_io /// \brief Lemon Format writer class. /// /// The Lemon Format contains several sections. We do not want to @@ -310,10 +310,15 @@ /// It gives back the header of the section. virtual std::string header() = 0; - /// \brief Writer function of the section. + /// \brief Writer function of the section. /// /// Write the content of the section. virtual void write(std::ostream& os) = 0; + + /// \brief Gives back true when the section should be written. + /// + /// Gives back true when the section should be written. + virtual bool valid() { return true; } }; /// \brief Constructor for LemonWriter. @@ -355,8 +360,10 @@ void run() { SectionWriters::iterator it; for (it = writers.begin(); it != writers.end(); ++it) { - *os << (*it)->header() << std::endl; - (*it)->write(*os); + if ((*it)->valid()) { + *os << (*it)->header() << std::endl; + (*it)->write(*os); + } } *os << "@end" << std::endl; } @@ -464,7 +471,7 @@ /// Write the content of the section. virtual void write(std::ostream& os) { for (int i = 0; i < (int)writers.size(); ++i) { - if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) { + if (writers[i].first == "label") { labelMap = writers[i].second; forceLabelMap = false; break; @@ -636,7 +643,7 @@ throw DataFormatError("Cannot find nodeset or label map"); } for (int i = 0; i < (int)writers.size(); ++i) { - if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) { + if (writers[i].first == "label") { labelMap = writers[i].second; forceLabelMap = false; break; @@ -1008,6 +1015,11 @@ os << std::endl; } } + + /// \brief Gives back true when the section should be written. + /// + /// Gives back true when the section should be written. + virtual bool valid() { return !writers.empty(); } private: @@ -1087,6 +1099,11 @@ os << std::endl; } } + + /// \brief Gives back true when the section should be written. + /// + /// Gives back true when the section should be written. + virtual bool valid() { return !writers.empty(); } private: @@ -1189,6 +1206,13 @@ os << std::endl; } } + + /// \brief Gives back true when the section should be written. + /// + /// Gives back true when the section should be written. + virtual bool valid() { + return !uEdgeWriters.empty() || !edgeWriters.empty(); + } private: @@ -1288,6 +1312,11 @@ } } + /// \brief Gives back true when the section should be written. + /// + /// Gives back true when the section should be written. + virtual bool valid() { return !writers.empty(); } + private: std::string name; diff -r f50c8c191cbd -r 59769591eb60 lemon/matrix_maps.h --- a/lemon/matrix_maps.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/matrix_maps.h Mon May 15 09:49:51 2006 +0000 @@ -47,6 +47,9 @@ typedef typename MatrixMap::Value Value; + /// \brief Constructor of the row map + /// + /// Constructor of the row map. MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row) : matrix(_matrix), row(_row) {} @@ -91,6 +94,9 @@ typedef typename MatrixMap::Value Value; + /// \brief Constructor of the row map + /// + /// Constructor of the row map. ConstMatrixRowMap(const MatrixMap& _matrix, typename MatrixMap::FirstKey _row) : matrix(_matrix), row(_row) {} @@ -108,11 +114,14 @@ typename MatrixMap::FirstKey row; }; + /// \ingroup matrices + /// /// \brief Gives back a row view of the matrix map /// - /// \ingroup matrices /// Gives back a row view of the matrix map. /// + /// \sa MatrixRowMap + /// \sa ConstMatrixRowMap template MatrixRowMap matrixRowMap(MatrixMap& matrixMap, typename MatrixMap::FirstKey row) { @@ -137,6 +146,9 @@ typedef typename MatrixMap::FirstKey Key; typedef typename MatrixMap::Value Value; + /// \brief Constructor of the column map + /// + /// Constructor of the column map. MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col) : matrix(_matrix), col(_col) {} @@ -180,6 +192,9 @@ typedef typename MatrixMap::FirstKey Key; typedef typename MatrixMap::Value Value; + /// \brief Constructor of the column map + /// + /// Constructor of the column map. ConstMatrixColMap(const MatrixMap& _matrix, typename MatrixMap::SecondKey _col) : matrix(_matrix), col(_col) {} @@ -197,11 +212,14 @@ typename MatrixMap::SecondKey col; }; + /// \ingroup matrices + /// /// \brief Gives back a column view of the matrix map /// - /// \ingroup matrices /// Gives back a column view of the matrix map. /// + /// \sa MatrixColMap + /// \sa ConstMatrixColMap template MatrixColMap matrixColMap(MatrixMap& matrixMap, typename MatrixMap::SecondKey col) { diff -r f50c8c191cbd -r 59769591eb60 lemon/path.h --- a/lemon/path.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/path.h Mon May 15 09:49:51 2006 +0000 @@ -16,21 +16,6 @@ * */ -/** -@defgroup paths Path Structures -@ingroup datas -\brief Path structures implemented in LEMON. - -LEMON provides flexible data structures -to work with paths. - -All of them have the same interface, especially they can be built or extended -using a standard Builder subclass. This make is easy to have e.g. the Dijkstra -algorithm to store its result in any kind of path structure. - -\sa lemon::concept::Path - -*/ ///\ingroup paths ///\file diff -r f50c8c191cbd -r 59769591eb60 lemon/radix_sort.h --- a/lemon/radix_sort.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/radix_sort.h Mon May 15 09:49:51 2006 +0000 @@ -19,7 +19,7 @@ #ifndef RADIX_SORT_H #define RADIX_SORT_H -/// \ingroup auxdat +/// \ingroup auxalg /// \file /// \brief Radix sort /// @@ -194,7 +194,7 @@ } - /// \ingroup auxdat + /// \ingroup auxalg /// /// \brief Sorts the stl compatible range into ascending order. /// @@ -411,7 +411,7 @@ } - /// \ingroup auxdat + /// \ingroup auxalg /// /// \brief Sorts stable the stl compatible range into ascending order. /// diff -r f50c8c191cbd -r 59769591eb60 lemon/ugraph_adaptor.h --- a/lemon/ugraph_adaptor.h Mon May 15 09:46:33 2006 +0000 +++ b/lemon/ugraph_adaptor.h Mon May 15 09:49:51 2006 +0000 @@ -38,8 +38,6 @@ namespace lemon { - /// \ingroup graph_adaptors - /// /// \brief Base type for the Graph Adaptors /// /// This is the base type for most of LEMON graph adaptors. @@ -233,6 +231,11 @@ }; /// \ingroup graph_adaptors + /// + /// \brief Trivial undirected graph adaptor + /// + /// This class is an adaptor which does not change the adapted undirected + /// graph. It can be used only to test the undirected graph adaptors. template class UGraphAdaptor : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > { @@ -348,44 +351,42 @@ || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d); } - ///\e - + /// \brief Hide the given node in the graph. + /// /// This function hides \c n in the graph, i.e. the iteration /// jumps over it. This is done by simply setting the value of \c n /// to be false in the corresponding node-map. void hide(const Node& n) const { node_filter_map->set(n, false); } - ///\e - + /// \brief Hide the given undirected edge in the graph. + /// /// This function hides \c e in the graph, i.e. the iteration /// jumps over it. This is done by simply setting the value of \c e - /// to be false in the corresponding edge-map. + /// to be false in the corresponding uedge-map. void hide(const UEdge& e) const { uedge_filter_map->set(e, false); } - ///\e - + /// \brief Unhide the given node in the graph. + /// /// The value of \c n is set to be true in the node-map which stores /// hide information. If \c n was hidden previuosly, then it is shown /// again void unHide(const Node& n) const { node_filter_map->set(n, true); } - ///\e - - /// The value of \c e is set to be true in the edge-map which stores + /// \brief Hide the given undirected edge in the graph. + /// + /// The value of \c e is set to be true in the uedge-map which stores /// hide information. If \c e was hidden previuosly, then it is shown /// again void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); } + /// \brief Returns true if \c n is hidden. + /// /// Returns true if \c n is hidden. - - ///\e - /// bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } - /// Returns true if \c n is hidden. - - ///\e + /// \brief Returns true if \c e is hidden. /// + /// Returns true if \c e is hidden. bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; } typedef False NodeNumTag; @@ -577,44 +578,42 @@ while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); } - ///\e - + /// \brief Hide the given node in the graph. + /// /// This function hides \c n in the graph, i.e. the iteration /// jumps over it. This is done by simply setting the value of \c n /// to be false in the corresponding node-map. void hide(const Node& n) const { node_filter_map->set(n, false); } - ///\e - + /// \brief Hide the given undirected edge in the graph. + /// /// This function hides \c e in the graph, i.e. the iteration /// jumps over it. This is done by simply setting the value of \c e - /// to be false in the corresponding edge-map. + /// to be false in the corresponding uedge-map. void hide(const UEdge& e) const { uedge_filter_map->set(e, false); } - ///\e - + /// \brief Unhide the given node in the graph. + /// /// The value of \c n is set to be true in the node-map which stores /// hide information. If \c n was hidden previuosly, then it is shown /// again void unHide(const Node& n) const { node_filter_map->set(n, true); } - ///\e - - /// The value of \c e is set to be true in the edge-map which stores + /// \brief Hide the given undirected edge in the graph. + /// + /// The value of \c e is set to be true in the uedge-map which stores /// hide information. If \c e was hidden previuosly, then it is shown /// again void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); } + /// \brief Returns true if \c n is hidden. + /// /// Returns true if \c n is hidden. - - ///\e - /// bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } - /// Returns true if \c n is hidden. - - ///\e + /// \brief Returns true if \c e is hidden. /// + /// Returns true if \c e is hidden. bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; } typedef False NodeNumTag; @@ -733,9 +732,6 @@ /// should filter all edges which's source or target is filtered by the /// node-filter. /// - /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to - /// \c Graph::Node that is why \c g.id(n) can be applied. - /// template class SubUGraphAdaptor :