1.1 --- a/benchmark/Makefile.am Mon May 15 09:46:33 2006 +0000
1.2 +++ b/benchmark/Makefile.am Mon May 15 09:49:51 2006 +0000
1.3 @@ -2,7 +2,12 @@
1.4
1.5 noinst_HEADERS = bench_tools.h
1.6
1.7 -noinst_PROGRAMS = graph-bench hcube bfs-bench radix_sort-bench
1.8 +noinst_PROGRAMS = \
1.9 + graph-bench \
1.10 + hcube \
1.11 + swap_bipartite_bench \
1.12 + bfs-bench \
1.13 + swap_bipartite_bench
1.14
1.15 graph_bench_SOURCES = graph-bench.cc
1.16
1.17 @@ -11,3 +16,5 @@
1.18 bfs_bench_SOURCES = bfs-bench.cc
1.19
1.20 radix_sort_bench_SOURCES = radix_sort-bench.cc
1.21 +
1.22 +swap_bipartite_bench_SOURCES = swap_bipartite_bench.cc
1.23 \ No newline at end of file
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/benchmark/swap_bipartite_bench.cc Mon May 15 09:49:51 2006 +0000
2.3 @@ -0,0 +1,92 @@
2.4 +#include <cstdlib>
2.5 +#include <iostream>
2.6 +#include <sstream>
2.7 +
2.8 +#include <lemon/smart_graph.h>
2.9 +
2.10 +#include <lemon/bpugraph_adaptor.h>
2.11 +#include <lemon/bipartite_matching.h>
2.12 +
2.13 +#include <lemon/graph_utils.h>
2.14 +#include <lemon/xy.h>
2.15 +#include <lemon/graph_to_eps.h>
2.16 +
2.17 +#include <lemon/time_measure.h>
2.18 +
2.19 +using namespace std;
2.20 +using namespace lemon;
2.21 +
2.22 +typedef SmartBpUGraph Graph;
2.23 +BPUGRAPH_TYPEDEFS(Graph);
2.24 +
2.25 +int _urandom_init() {
2.26 + int seed = time(0);
2.27 + srand(seed);
2.28 + return seed;
2.29 +}
2.30 +
2.31 +int urandom(int n) {
2.32 + static int seed = _urandom_init();
2.33 + return (int)(rand() / (1.0 + RAND_MAX) * n);
2.34 +}
2.35 +
2.36 +int main() {
2.37 +
2.38 + for (int k = 1; k < 100; ++k) {
2.39 +
2.40 + int n = k * 100;
2.41 + int m = (100 - k) * 100;
2.42 + int e = 20000;
2.43 + int s = 100;
2.44 +
2.45 + Timer nt(false), st(false);
2.46 +
2.47 + for (int i = 0; i < s; ++i) {
2.48 + Graph graph;
2.49 + vector<Node> aNodes;
2.50 + vector<Node> bNodes;
2.51 +
2.52 + for (int i = 0; i < n; ++i) {
2.53 + Node node = graph.addANode();
2.54 + aNodes.push_back(node);
2.55 + }
2.56 + for (int i = 0; i < m; ++i) {
2.57 + Node node = graph.addBNode();
2.58 + bNodes.push_back(node);
2.59 + }
2.60 + for (int i = 0; i < e; ++i) {
2.61 + Node aNode = aNodes[urandom(n)];
2.62 + Node bNode = bNodes[urandom(m)];
2.63 + graph.addEdge(aNode, bNode);
2.64 + }
2.65 +
2.66 + {
2.67 + MaxBipartiteMatching<Graph> bpmatch(graph);
2.68 +
2.69 + nt.start();
2.70 + bpmatch.init();
2.71 + bpmatch.start();
2.72 + nt.stop();
2.73 +
2.74 + }
2.75 +
2.76 + {
2.77 + typedef SwapBpUGraphAdaptor<Graph> SGraph;
2.78 + SGraph sgraph(graph);
2.79 + MaxBipartiteMatching<SGraph> bpmatch(sgraph);
2.80 +
2.81 + st.start();
2.82 + bpmatch.init();
2.83 + bpmatch.start();
2.84 + st.stop();
2.85 +
2.86 + }
2.87 +
2.88 + }
2.89 +
2.90 + cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
2.91 +
2.92 + }
2.93 +
2.94 + return 0;
2.95 +}
3.1 --- a/demo/Makefile.am Mon May 15 09:46:33 2006 +0000
3.2 +++ b/demo/Makefile.am Mon May 15 09:49:51 2006 +0000
3.3 @@ -19,7 +19,8 @@
3.4 grid_ugraph_demo \
3.5 topology_demo \
3.6 simann_maxcut_demo \
3.7 - disjoint_paths_demo
3.8 + disjoint_paths_demo \
3.9 + strongly_connected_orientation
3.10
3.11 if HAVE_GLPK
3.12 noinst_PROGRAMS += lp_demo lp_maxflow_demo
3.13 @@ -68,4 +69,6 @@
3.14
3.15 simann_maxcut_demo_SOURCES = simann_maxcut_demo.cc
3.16
3.17 -disjoint_paths_demo_SOURCES = disjoint_paths.cc
3.18 +disjoint_paths_demo_SOURCES = disjoint_paths_demo.cc
3.19 +
3.20 +strongly_connected_orientation_SOURCES = strongly_connected_orientation.cc
3.21 \ No newline at end of file
4.1 --- a/demo/disjoint_paths.cc Mon May 15 09:46:33 2006 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,107 +0,0 @@
4.4 -/* -*- C++ -*-
4.5 - *
4.6 - * This file is a part of LEMON, a generic C++ optimization library
4.7 - *
4.8 - * Copyright (C) 2003-2006
4.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 - *
4.12 - * Permission to use, modify and distribute this software is granted
4.13 - * provided that this copyright notice appears in all copies. For
4.14 - * precise terms see the accompanying LICENSE file.
4.15 - *
4.16 - * This software is provided "AS IS" with no warranty of any kind,
4.17 - * express or implied, and with no claim as to its suitability for any
4.18 - * purpose.
4.19 - *
4.20 - */
4.21 -
4.22 -/// \ingroup demos
4.23 -/// \file
4.24 -/// \brief Node and edge disjoint paths in directed graph.
4.25 -///
4.26 -/// This demo program calculates how many edge disjoint and node disjoint
4.27 -/// paths are in a directed graph between a source and a target node.
4.28 -/// The edge disjoint paths can be computed with a flow algorithm,
4.29 -/// in this example we use the Preflow algorithm class. To get the node
4.30 -/// disjoint paths we should first adapt the graph with the SplitGraphAdaptor
4.31 -/// and just then calculate the flow.
4.32 -///
4.33 -/// \include disjoint_paths.cc
4.34 -
4.35 -#include <iostream>
4.36 -
4.37 -#include <lemon/smart_graph.h>
4.38 -#include <lemon/graph_adaptor.h>
4.39 -#include <lemon/graph_reader.h>
4.40 -#include <lemon/preflow.h>
4.41 -#include <lemon/graph_to_eps.h>
4.42 -
4.43 -using namespace lemon;
4.44 -using namespace std;
4.45 -
4.46 -Color color(bool b) {
4.47 - return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0);
4.48 -}
4.49 -
4.50 -int main() {
4.51 - cout << "This program calculates the number " <<
4.52 - "of disjoint paths in a graph" << endl;
4.53 - cout << "The graph is read from the disjoint_paths.lgf file" << endl;
4.54 - typedef SmartGraph Graph;
4.55 -
4.56 - Graph graph;
4.57 -
4.58 - Graph::NodeMap<xy<double> > coords(graph);
4.59 - Graph::Node source, target;
4.60 - GraphReader<Graph>("disjoint_paths.lgf", graph).
4.61 - readNodeMap("coords", coords).
4.62 - readNode("source", source).readNode("target", target).run();
4.63 -
4.64 - typedef ConstMap<Graph::Edge, int> Capacity;
4.65 - Capacity capacity(1);
4.66 -
4.67 - Graph::EdgeMap<int> flow(graph);
4.68 -
4.69 - Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow);
4.70 -
4.71 - preflow.run();
4.72 -
4.73 - cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;
4.74 -
4.75 - graphToEps(graph, "edge_disjoint.eps").
4.76 - title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
4.77 - edgeColors(composeMap(functorMap(color), flow)).
4.78 - coords(coords).autoNodeScale().run();
4.79 -
4.80 -
4.81 - cout << "The paths are written into edge_disjoint.eps" << endl;
4.82 -
4.83 - typedef SplitGraphAdaptor<SmartGraph> SGraph;
4.84 -
4.85 - SGraph sgraph(graph);
4.86 -
4.87 - typedef ConstMap<SGraph::Edge, int> SCapacity;
4.88 - SCapacity scapacity(1);
4.89 -
4.90 - SGraph::EdgeMap<int> sflow(sgraph);
4.91 -
4.92 - Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source),
4.93 - SGraph::inNode(target),
4.94 - scapacity, sflow);
4.95 -
4.96 - spreflow.run();
4.97 -
4.98 - cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl;
4.99 -
4.100 -
4.101 - graphToEps(sgraph, "node_disjoint.eps").
4.102 - title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
4.103 - edgeColors(composeMap(functorMap(color), sflow)).
4.104 - coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy<double>(5, 0)))).
4.105 - autoNodeScale().run();
4.106 -
4.107 - cout << "The paths are written into node_disjoint.eps" << endl;
4.108 -
4.109 - return 0;
4.110 -}
5.1 --- a/demo/disjoint_paths.lgf Mon May 15 09:46:33 2006 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,46 +0,0 @@
5.4 -@nodeset
5.5 -coords label
5.6 -(-20,17) 15
5.7 -(39,13) 14
5.8 -(39,-11) 13
5.9 -(-12,7) 12
5.10 -(25,-15) 11
5.11 -(-18,-14) 10
5.12 -(45,3) 9
5.13 -(28,13) 8
5.14 -(25,-5) 7
5.15 -(1,21) 6
5.16 -(3,3) 5
5.17 -(3,-9) 4
5.18 -(-9,15) 3
5.19 -(-13,-4) 2
5.20 -(-27,5) 1
5.21 -@edgeset
5.22 - label
5.23 -1 15 22
5.24 -8 14 20
5.25 -11 13 18
5.26 -1 12 8
5.27 -4 11 14
5.28 -1 10 1
5.29 -14 9 21
5.30 -13 9 19
5.31 -8 9 17
5.32 -7 9 16
5.33 -11 9 15
5.34 -5 8 12
5.35 -6 8 11
5.36 -5 7 13
5.37 -3 6 4
5.38 -12 5 9
5.39 -2 5 6
5.40 -3 5 5
5.41 -2 4 10
5.42 -10 4 7
5.43 -15 3 23
5.44 -1 3 3
5.45 -1 2 2
5.46 -@nodes
5.47 -source 1
5.48 -target 9
5.49 -@end
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/demo/disjoint_paths_demo.cc Mon May 15 09:49:51 2006 +0000
6.3 @@ -0,0 +1,107 @@
6.4 +/* -*- C++ -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library
6.7 + *
6.8 + * Copyright (C) 2003-2006
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +/// \ingroup demos
6.23 +/// \file
6.24 +/// \brief Node and edge disjoint paths in directed graph.
6.25 +///
6.26 +/// This demo program calculates how many edge disjoint and node disjoint
6.27 +/// paths are in a directed graph between a source and a target node.
6.28 +/// The edge disjoint paths can be computed with a flow algorithm,
6.29 +/// in this example we use the Preflow algorithm class. To get the node
6.30 +/// disjoint paths we should first adapt the graph with the SplitGraphAdaptor
6.31 +/// and just then calculate the flow.
6.32 +///
6.33 +/// \include disjoint_paths_demo.cc
6.34 +
6.35 +#include <iostream>
6.36 +
6.37 +#include <lemon/smart_graph.h>
6.38 +#include <lemon/graph_adaptor.h>
6.39 +#include <lemon/graph_reader.h>
6.40 +#include <lemon/preflow.h>
6.41 +#include <lemon/graph_to_eps.h>
6.42 +
6.43 +using namespace lemon;
6.44 +using namespace std;
6.45 +
6.46 +Color color(bool b) {
6.47 + return b ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 0.0);
6.48 +}
6.49 +
6.50 +int main() {
6.51 + cout << "This program calculates the number " <<
6.52 + "of disjoint paths in a graph" << endl;
6.53 + cout << "The graph is read from the disjoint_paths_demo.lgf file" << endl;
6.54 + typedef SmartGraph Graph;
6.55 +
6.56 + Graph graph;
6.57 +
6.58 + Graph::NodeMap<xy<double> > coords(graph);
6.59 + Graph::Node source, target;
6.60 + GraphReader<Graph>("disjoint_paths_demo.lgf", graph).
6.61 + readNodeMap("coords", coords).
6.62 + readNode("source", source).readNode("target", target).run();
6.63 +
6.64 + typedef ConstMap<Graph::Edge, int> Capacity;
6.65 + Capacity capacity(1);
6.66 +
6.67 + Graph::EdgeMap<int> flow(graph);
6.68 +
6.69 + Preflow<Graph, int, Capacity> preflow(graph, source, target, capacity, flow);
6.70 +
6.71 + preflow.run();
6.72 +
6.73 + cout << "Number of edge disjoint paths: " << preflow.flowValue() << endl;
6.74 +
6.75 + graphToEps(graph, "edge_disjoint_paths.eps").
6.76 + title("edge disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
6.77 + edgeColors(composeMap(functorMap(color), flow)).
6.78 + coords(coords).autoNodeScale().run();
6.79 +
6.80 +
6.81 + cout << "The paths are written into edge_disjoint_paths.eps" << endl;
6.82 +
6.83 + typedef SplitGraphAdaptor<SmartGraph> SGraph;
6.84 +
6.85 + SGraph sgraph(graph);
6.86 +
6.87 + typedef ConstMap<SGraph::Edge, int> SCapacity;
6.88 + SCapacity scapacity(1);
6.89 +
6.90 + SGraph::EdgeMap<int> sflow(sgraph);
6.91 +
6.92 + Preflow<SGraph, int, SCapacity> spreflow(sgraph, SGraph::outNode(source),
6.93 + SGraph::inNode(target),
6.94 + scapacity, sflow);
6.95 +
6.96 + spreflow.run();
6.97 +
6.98 + cout << "Number of node disjoint paths: " << spreflow.flowValue() << endl;
6.99 +
6.100 +
6.101 + graphToEps(sgraph, "node_disjoint_paths.eps").
6.102 + title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
6.103 + edgeColors(composeMap(functorMap(color), sflow)).
6.104 + coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy<double>(5, 0)))).
6.105 + autoNodeScale().run();
6.106 +
6.107 + cout << "The paths are written into node_disjoint_paths.eps" << endl;
6.108 +
6.109 + return 0;
6.110 +}
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/demo/disjoint_paths_demo.lgf Mon May 15 09:49:51 2006 +0000
7.3 @@ -0,0 +1,46 @@
7.4 +@nodeset
7.5 +coords label
7.6 +(-20,17) 15
7.7 +(39,13) 14
7.8 +(39,-11) 13
7.9 +(-12,7) 12
7.10 +(25,-15) 11
7.11 +(-18,-14) 10
7.12 +(45,3) 9
7.13 +(28,13) 8
7.14 +(25,-5) 7
7.15 +(1,21) 6
7.16 +(3,3) 5
7.17 +(3,-9) 4
7.18 +(-9,15) 3
7.19 +(-13,-4) 2
7.20 +(-27,5) 1
7.21 +@edgeset
7.22 + label
7.23 +1 15 22
7.24 +8 14 20
7.25 +11 13 18
7.26 +1 12 8
7.27 +4 11 14
7.28 +1 10 1
7.29 +14 9 21
7.30 +13 9 19
7.31 +8 9 17
7.32 +7 9 16
7.33 +11 9 15
7.34 +5 8 12
7.35 +6 8 11
7.36 +5 7 13
7.37 +3 6 4
7.38 +12 5 9
7.39 +2 5 6
7.40 +3 5 5
7.41 +2 4 10
7.42 +10 4 7
7.43 +15 3 23
7.44 +1 3 3
7.45 +1 2 2
7.46 +@nodes
7.47 +source 1
7.48 +target 9
7.49 +@end
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/demo/strongly_connected_orientation.cc Mon May 15 09:49:51 2006 +0000
8.3 @@ -0,0 +1,110 @@
8.4 +/* -*- C++ -*-
8.5 + *
8.6 + * This file is a part of LEMON, a generic C++ optimization library
8.7 + *
8.8 + * Copyright (C) 2003-2006
8.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
8.11 + *
8.12 + * Permission to use, modify and distribute this software is granted
8.13 + * provided that this copyright notice appears in all copies. For
8.14 + * precise terms see the accompanying LICENSE file.
8.15 + *
8.16 + * This software is provided "AS IS" with no warranty of any kind,
8.17 + * express or implied, and with no claim as to its suitability for any
8.18 + * purpose.
8.19 + *
8.20 + */
8.21 +
8.22 +#include <iostream>
8.23 +
8.24 +#include <lemon/smart_graph.h>
8.25 +#include <lemon/graph_reader.h>
8.26 +#include <lemon/ugraph_adaptor.h>
8.27 +#include <lemon/graph_to_eps.h>
8.28 +#include <lemon/dfs.h>
8.29 +#include <lemon/topology.h>
8.30 +
8.31 +
8.32 +/// \ingroup demos
8.33 +/// \file
8.34 +/// \brief Strongly connected orientation
8.35 +///
8.36 +/// This example demonstrates the usage of the DirUGraphAdaptor,
8.37 +/// the DfsVisitor and some topology functions. The program reads
8.38 +/// an input undirected graph and with a DfsVisit it orients each edge
8.39 +/// to minimize the strongly connected components in the graph. At least
8.40 +/// it checks the result of the orientation with to topology functions.
8.41 +///
8.42 +/// \include strongly_connected_orientation.cc
8.43 +
8.44 +using namespace lemon;
8.45 +using namespace std;
8.46 +
8.47 +typedef SmartUGraph UGraph;
8.48 +UGRAPH_TYPEDEFS(UGraph)
8.49 +
8.50 +Color color(bool c) {
8.51 + return c ? Color(0.0, 0.0, 0.0) : Color(1.0, 0.0, 0.0);
8.52 +}
8.53 +
8.54 +template <typename DirMap>
8.55 +class OrientVisitor : public DfsVisitor<UGraph> {
8.56 +public:
8.57 +
8.58 + OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
8.59 + : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
8.60 +
8.61 + void discover(const Edge& edge) {
8.62 + _processed.set(edge, true);
8.63 + _dirMap.set(edge, _ugraph.direction(edge));
8.64 + }
8.65 +
8.66 + void examine(const Edge& edge) {
8.67 + if (_processed[edge]) return;
8.68 + _processed.set(edge, true);
8.69 + _dirMap.set(edge, _ugraph.direction(edge));
8.70 + }
8.71 +
8.72 +private:
8.73 + const UGraph& _ugraph;
8.74 + DirMap& _dirMap;
8.75 + UGraph::UEdgeMap<bool> _processed;
8.76 +};
8.77 +
8.78 +
8.79 +int main(int argc, const char *argv[]) {
8.80 + cout << "Orientation of the strongly_connected_orientation.lgf "
8.81 + << "to be strongly connected" << endl;
8.82 +
8.83 + UGraph ugraph;
8.84 + UGraph::NodeMap<xy<double> > coords(ugraph);
8.85 + UGraphReader<UGraph>("strongly_connected_orientation.lgf", ugraph).
8.86 + readNodeMap("coords", coords).run();
8.87 +
8.88 + UGraph::UEdgeMap<bool> dmap(ugraph);
8.89 +
8.90 + typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
8.91 + Visitor visitor(ugraph, dmap);
8.92 +
8.93 + DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
8.94 +
8.95 + dfs.run();
8.96 +
8.97 + typedef DirUGraphAdaptor<UGraph> DGraph;
8.98 + DGraph dgraph(ugraph, dmap);
8.99 +
8.100 + cout << "The result written into the "
8.101 + << "strongly_connected_orientation.eps file" << endl;
8.102 +
8.103 + graphToEps(dgraph, "strongly_connected_orientation.eps").
8.104 + drawArrows().coords(coords).scaleToA4().enableParallel().
8.105 + autoNodeScale().autoEdgeWidthScale().run();
8.106 +
8.107 + int num_scc = countStronglyConnectedComponents(dgraph);
8.108 + int num_becc = countBiEdgeConnectedComponents(ugraph);
8.109 +
8.110 + LEMON_ASSERT(num_scc == num_becc, "Wrong Orientation");
8.111 +
8.112 + return 0;
8.113 +}
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/demo/strongly_connected_orientation.lgf Mon May 15 09:49:51 2006 +0000
9.3 @@ -0,0 +1,26 @@
9.4 +@nodeset
9.5 +coords label
9.6 +(12,6) 9
9.7 +(-12,3) 8
9.8 +(-34,6) 7
9.9 +(-23,22) 6
9.10 +(16,26) 5
9.11 +(43,8) 4
9.12 +(24,-8) 3
9.13 +(-4,-14) 2
9.14 +(-29,-11) 1
9.15 +@uedgeset
9.16 + label
9.17 +5 9 9
9.18 +9 8 5
9.19 +7 6 7
9.20 +8 6 6
9.21 +4 5 11
9.22 +6 5 8
9.23 +3 4 12
9.24 +9 4 10
9.25 +3 2 4
9.26 +8 2 3
9.27 +1 2 2
9.28 +7 1 1
9.29 +@end
10.1 --- a/doc/graph-adaptors.dox Mon May 15 09:46:33 2006 +0000
10.2 +++ b/doc/graph-adaptors.dox Mon May 15 09:49:51 2006 +0000
10.3 @@ -36,8 +36,8 @@
10.4 The code looks as follows
10.5 \code
10.6 ListGraph g;
10.7 - RevGraphAdaptor<ListGraph> rgw(g);
10.8 - int result=algorithm(rgw);
10.9 + RevGraphAdaptor<ListGraph> rga(g);
10.10 + int result=algorithm(rga);
10.11 \endcode
10.12 After running the algorithm, the original graph \c g
10.13 is untouched.
10.14 @@ -58,7 +58,7 @@
10.15 capabilities of the original graph while in other cases this would be
10.16 meaningless. This means that the concepts that they are models of depend
10.17 on the graph adaptor, and the wrapped graph(s).
10.18 - If an edge of \c rgw is deleted, this is carried out by
10.19 + If an edge of \c rga is deleted, this is carried out by
10.20 deleting the corresponding edge of \c g, thus the adaptor modifies the
10.21 original graph.
10.22 But for a residual
10.23 @@ -73,8 +73,8 @@
10.24 then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
10.25 \code
10.26 int algorithm1(const ListGraph& g) {
10.27 - RevGraphAdaptor<const ListGraph> rgw(g);
10.28 - return algorithm2(rgw);
10.29 + RevGraphAdaptor<const ListGraph> rga(g);
10.30 + return algorithm2(rga);
10.31 }
10.32 \endcode
10.33 */
11.1 --- a/doc/groups.dox Mon May 15 09:46:33 2006 +0000
11.2 +++ b/doc/groups.dox Mon May 15 09:49:51 2006 +0000
11.3 @@ -14,13 +14,14 @@
11.4 planned to be easily used in an experimental phase of implementation studies,
11.5 and thereafter the program code can be made efficient by small modifications.
11.6
11.7 -The most efficient implementation of diverse applications require the usage of different physical graph implementations. These differences appear in the size of
11.8 -graph we require to handle, memory or time usage limitations or in
11.9 -the set of operations through which the graph can be accessed.
11.10 -LEMON provides several physical graph structures to meet the
11.11 -diverging requirements of the possible users.
11.12 -In order to save on running time or on memory usage, some structures may
11.13 -fail to provide some graph features like edge or node deletion.
11.14 +The most efficient implementation of diverse applications require the
11.15 +usage of different physical graph implementations. These differences
11.16 +appear in the size of graph we require to handle, memory or time usage
11.17 +limitations or in the set of operations through which the graph can be
11.18 +accessed. LEMON provides several physical graph structures to meet
11.19 +the diverging requirements of the possible users. In order to save on
11.20 +running time or on memory usage, some structures may fail to provide
11.21 +some graph features like edge or node deletion.
11.22
11.23 Alteration of standard containers need a very limited number of
11.24 operations, these together satisfy the everyday requirements.
11.25 @@ -76,7 +77,7 @@
11.26 Map adaptors are used to create "implicit" maps from other maps.
11.27
11.28 Most of them are \ref lemon::concept::ReadMap "ReadMap"s. They can
11.29 -make arithmetic oprerations between one or two maps (negation, scalig,
11.30 +make arithmetic oprerations between one or two maps (negation, scaling,
11.31 addition, multiplication etc.) or e.g. convert a map to another one
11.32 of different Value type.
11.33 */
11.34 @@ -86,10 +87,24 @@
11.35 @ingroup datas
11.36 \brief Two dimensional data storages.
11.37
11.38 -Two dimensional
11.39 -data storages.
11.40 +Two dimensional data storages.
11.41 */
11.42
11.43 +/**
11.44 +@defgroup paths Path Structures
11.45 +@ingroup datas
11.46 +\brief Path structures implemented in LEMON.
11.47 +
11.48 +LEMON provides flexible data structures
11.49 +to work with paths.
11.50 +
11.51 +All of them have the same interface, especially they can be built or extended
11.52 +using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
11.53 +algorithm to store its result in any kind of path structure.
11.54 +
11.55 +\sa lemon::concept::Path
11.56 +
11.57 +*/
11.58
11.59 /**
11.60 @defgroup auxdat Auxiliary Data Structures
11.61 @@ -110,35 +125,25 @@
11.62 */
11.63
11.64 /**
11.65 -@defgroup galgs Graph Algorithms
11.66 -\brief This group describes the several graph algorithms
11.67 +@defgroup algs Algorithms
11.68 +\brief This group describes the several algorithms
11.69 implemented in LEMON.
11.70
11.71 -This group describes the several graph algorithms
11.72 +This group describes the several algorithms
11.73 implemented in LEMON.
11.74 */
11.75
11.76 /**
11.77 @defgroup gutils General Graph Utilities
11.78 -@ingroup galgs
11.79 +@ingroup algs
11.80 \brief This group describes some simple general graph utilities.
11.81
11.82 This group describes some simple general graph utilities.
11.83 */
11.84
11.85 /**
11.86 -@defgroup gen_opt_group General Optimization Tools
11.87 -\brief This group describes some general optimization frameworks
11.88 -implemented in LEMON.
11.89 -
11.90 -This group describes some general optimization frameworks
11.91 -implemented in LEMON.
11.92 -
11.93 -*/
11.94 -
11.95 -/**
11.96 @defgroup flowalgs Path and Flow Algorithms
11.97 -@ingroup galgs
11.98 +@ingroup algs
11.99 \brief This group describes the algorithms
11.100 for finding paths and flows in graphs.
11.101
11.102 @@ -151,7 +156,7 @@
11.103
11.104 /**
11.105 @defgroup topology Topology related algorithms
11.106 -@ingroup galgs
11.107 +@ingroup algs
11.108 \brief This group describes the algorithms
11.109 for discover the topology of the graphs.
11.110
11.111 @@ -165,7 +170,7 @@
11.112
11.113 /**
11.114 @defgroup matching Matching algorithms in graphs and bipartite graphs
11.115 -@ingroup galgs
11.116 +@ingroup algs
11.117 \brief This group describes the algorithms
11.118 for find matchings in graphs and bipartite graphs.
11.119
11.120 @@ -178,8 +183,34 @@
11.121 */
11.122
11.123 /**
11.124 -@defgroup exceptions Exceptions
11.125 -This group contains the exceptions thrown by LEMON library
11.126 +@defgroup spantree Minimum Cost Spanning Tree Algorithms
11.127 +@ingroup algs
11.128 +\brief This group containes the algorithms for finding a minimum cost spanning
11.129 +tree in a graph
11.130 +
11.131 +This group containes the algorithms for finding a minimum cost spanning
11.132 +tree in a graph
11.133 +*/
11.134 +
11.135 +
11.136 +/**
11.137 +@defgroup auxalg Auxiliary Algorithms
11.138 +@ingroup algs
11.139 +\brief Some algorithms implemented in LEMON.
11.140 +
11.141 +This group describes the algorithms in LEMON in order to make
11.142 +it easier to implement complex algorithms.
11.143 +
11.144 +*/
11.145 +
11.146 +/**
11.147 +@defgroup gen_opt_group General Optimization Tools
11.148 +\brief This group describes some general optimization frameworks
11.149 +implemented in LEMON.
11.150 +
11.151 +This group describes some general optimization frameworks
11.152 +implemented in LEMON.
11.153 +
11.154 */
11.155
11.156 /**
11.157 @@ -197,13 +228,27 @@
11.158
11.159 /**
11.160 @defgroup io_group Input-Output
11.161 -Here you can find tools for imporing and exporting graphs and graph related
11.162 -data
11.163 +\brief Several Graph Input-Output methods
11.164 +
11.165 +Here you can find tools for importing and exporting graphs
11.166 +and graph related data. Now it supports the LEMON format, the
11.167 +dimacs format and the encapsulated postscript format.
11.168 +*/
11.169 +
11.170 +/**
11.171 +@defgroup lemon_io Lemon Input-Output
11.172 +@ingroup io_group
11.173 +\brief Reading and writing LEMON format
11.174 +
11.175 +Methods for reading and writing LEMON format. More about this
11.176 +format you can find on the \ref graph-io-page "Graph Input-Output"
11.177 +tutorial pages.
11.178 +
11.179 */
11.180
11.181 /**
11.182 @defgroup section_io Section readers and writers
11.183 -@ingroup io_group
11.184 +@ingroup lemon_io
11.185 \brief Section readers and writers for lemon Input-Output.
11.186
11.187 Here you can find which section readers and writers can attach to
11.188 @@ -212,7 +257,7 @@
11.189
11.190 /**
11.191 @defgroup item_io Item Readers and Writers
11.192 -@ingroup io_group
11.193 +@ingroup lemon_io
11.194 \brief Item readers and writers for lemon Input-Output.
11.195
11.196 The Input-Output classes can handle more data type by example
11.197 @@ -221,6 +266,20 @@
11.198 */
11.199
11.200 /**
11.201 +@defgroup eps_io Postscript exporting
11.202 +@ingroup io_group
11.203 +\brief General EPS drawer and graph exporter
11.204 +
11.205 +This group contains general EPS drawing methods and special
11.206 +graph exporting tools.
11.207 +*/
11.208 +
11.209 +/**
11.210 +@defgroup exceptions Exceptions
11.211 +This group contains the exceptions thrown by LEMON library
11.212 +*/
11.213 +
11.214 +/**
11.215 @defgroup concept Concepts
11.216 \brief Skeleton classes and concept checking classes
11.217
11.218 @@ -234,6 +293,7 @@
11.219
11.220 */
11.221
11.222 +
11.223 /**
11.224 @defgroup graph_concepts Graph Structure Concepts
11.225 @ingroup concept
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/doc/images/swap_test.eps Mon May 15 09:49:51 2006 +0000
12.3 @@ -0,0 +1,763 @@
12.4 +%!PS-Adobe-2.0 EPSF-2.0
12.5 +%%Title: swap_test.eps
12.6 +%%Creator: gnuplot 4.0 patchlevel 0
12.7 +%%CreationDate: Sat May 13 18:29:57 2006
12.8 +%%DocumentFonts: (atend)
12.9 +%%BoundingBox: 50 50 338 251
12.10 +%%Orientation: Portrait
12.11 +%%EndComments
12.12 +/gnudict 256 dict def
12.13 +gnudict begin
12.14 +/Color false def
12.15 +/Solid false def
12.16 +/gnulinewidth 5.000 def
12.17 +/userlinewidth gnulinewidth def
12.18 +/vshift -46 def
12.19 +/dl {10.0 mul} def
12.20 +/hpt_ 31.5 def
12.21 +/vpt_ 31.5 def
12.22 +/hpt hpt_ def
12.23 +/vpt vpt_ def
12.24 +/Rounded false def
12.25 +/M {moveto} bind def
12.26 +/L {lineto} bind def
12.27 +/R {rmoveto} bind def
12.28 +/V {rlineto} bind def
12.29 +/N {newpath moveto} bind def
12.30 +/C {setrgbcolor} bind def
12.31 +/f {rlineto fill} bind def
12.32 +/vpt2 vpt 2 mul def
12.33 +/hpt2 hpt 2 mul def
12.34 +/Lshow { currentpoint stroke M
12.35 + 0 vshift R show } def
12.36 +/Rshow { currentpoint stroke M
12.37 + dup stringwidth pop neg vshift R show } def
12.38 +/Cshow { currentpoint stroke M
12.39 + dup stringwidth pop -2 div vshift R show } def
12.40 +/UP { dup vpt_ mul /vpt exch def hpt_ mul /hpt exch def
12.41 + /hpt2 hpt 2 mul def /vpt2 vpt 2 mul def } def
12.42 +/DL { Color {setrgbcolor Solid {pop []} if 0 setdash }
12.43 + {pop pop pop 0 setgray Solid {pop []} if 0 setdash} ifelse } def
12.44 +/BL { stroke userlinewidth 2 mul setlinewidth
12.45 + Rounded { 1 setlinejoin 1 setlinecap } if } def
12.46 +/AL { stroke userlinewidth 2 div setlinewidth
12.47 + Rounded { 1 setlinejoin 1 setlinecap } if } def
12.48 +/UL { dup gnulinewidth mul /userlinewidth exch def
12.49 + dup 1 lt {pop 1} if 10 mul /udl exch def } def
12.50 +/PL { stroke userlinewidth setlinewidth
12.51 + Rounded { 1 setlinejoin 1 setlinecap } if } def
12.52 +/LTw { PL [] 1 setgray } def
12.53 +/LTb { BL [] 0 0 0 DL } def
12.54 +/LTa { AL [1 udl mul 2 udl mul] 0 setdash 0 0 0 setrgbcolor } def
12.55 +/LT0 { PL [] 1 0 0 DL } def
12.56 +/LT1 { PL [4 dl 2 dl] 0 1 0 DL } def
12.57 +/LT2 { PL [2 dl 3 dl] 0 0 1 DL } def
12.58 +/LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def
12.59 +/LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def
12.60 +/LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def
12.61 +/LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def
12.62 +/LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def
12.63 +/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
12.64 +/Pnt { stroke [] 0 setdash
12.65 + gsave 1 setlinecap M 0 0 V stroke grestore } def
12.66 +/Dia { stroke [] 0 setdash 2 copy vpt add M
12.67 + hpt neg vpt neg V hpt vpt neg V
12.68 + hpt vpt V hpt neg vpt V closepath stroke
12.69 + Pnt } def
12.70 +/Pls { stroke [] 0 setdash vpt sub M 0 vpt2 V
12.71 + currentpoint stroke M
12.72 + hpt neg vpt neg R hpt2 0 V stroke
12.73 + } def
12.74 +/Box { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M
12.75 + 0 vpt2 neg V hpt2 0 V 0 vpt2 V
12.76 + hpt2 neg 0 V closepath stroke
12.77 + Pnt } def
12.78 +/Crs { stroke [] 0 setdash exch hpt sub exch vpt add M
12.79 + hpt2 vpt2 neg V currentpoint stroke M
12.80 + hpt2 neg 0 R hpt2 vpt2 V stroke } def
12.81 +/TriU { stroke [] 0 setdash 2 copy vpt 1.12 mul add M
12.82 + hpt neg vpt -1.62 mul V
12.83 + hpt 2 mul 0 V
12.84 + hpt neg vpt 1.62 mul V closepath stroke
12.85 + Pnt } def
12.86 +/Star { 2 copy Pls Crs } def
12.87 +/BoxF { stroke [] 0 setdash exch hpt sub exch vpt add M
12.88 + 0 vpt2 neg V hpt2 0 V 0 vpt2 V
12.89 + hpt2 neg 0 V closepath fill } def
12.90 +/TriUF { stroke [] 0 setdash vpt 1.12 mul add M
12.91 + hpt neg vpt -1.62 mul V
12.92 + hpt 2 mul 0 V
12.93 + hpt neg vpt 1.62 mul V closepath fill } def
12.94 +/TriD { stroke [] 0 setdash 2 copy vpt 1.12 mul sub M
12.95 + hpt neg vpt 1.62 mul V
12.96 + hpt 2 mul 0 V
12.97 + hpt neg vpt -1.62 mul V closepath stroke
12.98 + Pnt } def
12.99 +/TriDF { stroke [] 0 setdash vpt 1.12 mul sub M
12.100 + hpt neg vpt 1.62 mul V
12.101 + hpt 2 mul 0 V
12.102 + hpt neg vpt -1.62 mul V closepath fill} def
12.103 +/DiaF { stroke [] 0 setdash vpt add M
12.104 + hpt neg vpt neg V hpt vpt neg V
12.105 + hpt vpt V hpt neg vpt V closepath fill } def
12.106 +/Pent { stroke [] 0 setdash 2 copy gsave
12.107 + translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
12.108 + closepath stroke grestore Pnt } def
12.109 +/PentF { stroke [] 0 setdash gsave
12.110 + translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
12.111 + closepath fill grestore } def
12.112 +/Circle { stroke [] 0 setdash 2 copy
12.113 + hpt 0 360 arc stroke Pnt } def
12.114 +/CircleF { stroke [] 0 setdash hpt 0 360 arc fill } def
12.115 +/C0 { BL [] 0 setdash 2 copy moveto vpt 90 450 arc } bind def
12.116 +/C1 { BL [] 0 setdash 2 copy moveto
12.117 + 2 copy vpt 0 90 arc closepath fill
12.118 + vpt 0 360 arc closepath } bind def
12.119 +/C2 { BL [] 0 setdash 2 copy moveto
12.120 + 2 copy vpt 90 180 arc closepath fill
12.121 + vpt 0 360 arc closepath } bind def
12.122 +/C3 { BL [] 0 setdash 2 copy moveto
12.123 + 2 copy vpt 0 180 arc closepath fill
12.124 + vpt 0 360 arc closepath } bind def
12.125 +/C4 { BL [] 0 setdash 2 copy moveto
12.126 + 2 copy vpt 180 270 arc closepath fill
12.127 + vpt 0 360 arc closepath } bind def
12.128 +/C5 { BL [] 0 setdash 2 copy moveto
12.129 + 2 copy vpt 0 90 arc
12.130 + 2 copy moveto
12.131 + 2 copy vpt 180 270 arc closepath fill
12.132 + vpt 0 360 arc } bind def
12.133 +/C6 { BL [] 0 setdash 2 copy moveto
12.134 + 2 copy vpt 90 270 arc closepath fill
12.135 + vpt 0 360 arc closepath } bind def
12.136 +/C7 { BL [] 0 setdash 2 copy moveto
12.137 + 2 copy vpt 0 270 arc closepath fill
12.138 + vpt 0 360 arc closepath } bind def
12.139 +/C8 { BL [] 0 setdash 2 copy moveto
12.140 + 2 copy vpt 270 360 arc closepath fill
12.141 + vpt 0 360 arc closepath } bind def
12.142 +/C9 { BL [] 0 setdash 2 copy moveto
12.143 + 2 copy vpt 270 450 arc closepath fill
12.144 + vpt 0 360 arc closepath } bind def
12.145 +/C10 { BL [] 0 setdash 2 copy 2 copy moveto vpt 270 360 arc closepath fill
12.146 + 2 copy moveto
12.147 + 2 copy vpt 90 180 arc closepath fill
12.148 + vpt 0 360 arc closepath } bind def
12.149 +/C11 { BL [] 0 setdash 2 copy moveto
12.150 + 2 copy vpt 0 180 arc closepath fill
12.151 + 2 copy moveto
12.152 + 2 copy vpt 270 360 arc closepath fill
12.153 + vpt 0 360 arc closepath } bind def
12.154 +/C12 { BL [] 0 setdash 2 copy moveto
12.155 + 2 copy vpt 180 360 arc closepath fill
12.156 + vpt 0 360 arc closepath } bind def
12.157 +/C13 { BL [] 0 setdash 2 copy moveto
12.158 + 2 copy vpt 0 90 arc closepath fill
12.159 + 2 copy moveto
12.160 + 2 copy vpt 180 360 arc closepath fill
12.161 + vpt 0 360 arc closepath } bind def
12.162 +/C14 { BL [] 0 setdash 2 copy moveto
12.163 + 2 copy vpt 90 360 arc closepath fill
12.164 + vpt 0 360 arc } bind def
12.165 +/C15 { BL [] 0 setdash 2 copy vpt 0 360 arc closepath fill
12.166 + vpt 0 360 arc closepath } bind def
12.167 +/Rec { newpath 4 2 roll moveto 1 index 0 rlineto 0 exch rlineto
12.168 + neg 0 rlineto closepath } bind def
12.169 +/Square { dup Rec } bind def
12.170 +/Bsquare { vpt sub exch vpt sub exch vpt2 Square } bind def
12.171 +/S0 { BL [] 0 setdash 2 copy moveto 0 vpt rlineto BL Bsquare } bind def
12.172 +/S1 { BL [] 0 setdash 2 copy vpt Square fill Bsquare } bind def
12.173 +/S2 { BL [] 0 setdash 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
12.174 +/S3 { BL [] 0 setdash 2 copy exch vpt sub exch vpt2 vpt Rec fill Bsquare } bind def
12.175 +/S4 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
12.176 +/S5 { BL [] 0 setdash 2 copy 2 copy vpt Square fill
12.177 + exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
12.178 +/S6 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill Bsquare } bind def
12.179 +/S7 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill
12.180 + 2 copy vpt Square fill
12.181 + Bsquare } bind def
12.182 +/S8 { BL [] 0 setdash 2 copy vpt sub vpt Square fill Bsquare } bind def
12.183 +/S9 { BL [] 0 setdash 2 copy vpt sub vpt vpt2 Rec fill Bsquare } bind def
12.184 +/S10 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt Square fill
12.185 + Bsquare } bind def
12.186 +/S11 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt2 vpt Rec fill
12.187 + Bsquare } bind def
12.188 +/S12 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill Bsquare } bind def
12.189 +/S13 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
12.190 + 2 copy vpt Square fill Bsquare } bind def
12.191 +/S14 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
12.192 + 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
12.193 +/S15 { BL [] 0 setdash 2 copy Bsquare fill Bsquare } bind def
12.194 +/D0 { gsave translate 45 rotate 0 0 S0 stroke grestore } bind def
12.195 +/D1 { gsave translate 45 rotate 0 0 S1 stroke grestore } bind def
12.196 +/D2 { gsave translate 45 rotate 0 0 S2 stroke grestore } bind def
12.197 +/D3 { gsave translate 45 rotate 0 0 S3 stroke grestore } bind def
12.198 +/D4 { gsave translate 45 rotate 0 0 S4 stroke grestore } bind def
12.199 +/D5 { gsave translate 45 rotate 0 0 S5 stroke grestore } bind def
12.200 +/D6 { gsave translate 45 rotate 0 0 S6 stroke grestore } bind def
12.201 +/D7 { gsave translate 45 rotate 0 0 S7 stroke grestore } bind def
12.202 +/D8 { gsave translate 45 rotate 0 0 S8 stroke grestore } bind def
12.203 +/D9 { gsave translate 45 rotate 0 0 S9 stroke grestore } bind def
12.204 +/D10 { gsave translate 45 rotate 0 0 S10 stroke grestore } bind def
12.205 +/D11 { gsave translate 45 rotate 0 0 S11 stroke grestore } bind def
12.206 +/D12 { gsave translate 45 rotate 0 0 S12 stroke grestore } bind def
12.207 +/D13 { gsave translate 45 rotate 0 0 S13 stroke grestore } bind def
12.208 +/D14 { gsave translate 45 rotate 0 0 S14 stroke grestore } bind def
12.209 +/D15 { gsave translate 45 rotate 0 0 S15 stroke grestore } bind def
12.210 +/DiaE { stroke [] 0 setdash vpt add M
12.211 + hpt neg vpt neg V hpt vpt neg V
12.212 + hpt vpt V hpt neg vpt V closepath stroke } def
12.213 +/BoxE { stroke [] 0 setdash exch hpt sub exch vpt add M
12.214 + 0 vpt2 neg V hpt2 0 V 0 vpt2 V
12.215 + hpt2 neg 0 V closepath stroke } def
12.216 +/TriUE { stroke [] 0 setdash vpt 1.12 mul add M
12.217 + hpt neg vpt -1.62 mul V
12.218 + hpt 2 mul 0 V
12.219 + hpt neg vpt 1.62 mul V closepath stroke } def
12.220 +/TriDE { stroke [] 0 setdash vpt 1.12 mul sub M
12.221 + hpt neg vpt 1.62 mul V
12.222 + hpt 2 mul 0 V
12.223 + hpt neg vpt -1.62 mul V closepath stroke } def
12.224 +/PentE { stroke [] 0 setdash gsave
12.225 + translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
12.226 + closepath stroke grestore } def
12.227 +/CircE { stroke [] 0 setdash
12.228 + hpt 0 360 arc stroke } def
12.229 +/Opaque { gsave closepath 1 setgray fill grestore 0 setgray closepath } def
12.230 +/DiaW { stroke [] 0 setdash vpt add M
12.231 + hpt neg vpt neg V hpt vpt neg V
12.232 + hpt vpt V hpt neg vpt V Opaque stroke } def
12.233 +/BoxW { stroke [] 0 setdash exch hpt sub exch vpt add M
12.234 + 0 vpt2 neg V hpt2 0 V 0 vpt2 V
12.235 + hpt2 neg 0 V Opaque stroke } def
12.236 +/TriUW { stroke [] 0 setdash vpt 1.12 mul add M
12.237 + hpt neg vpt -1.62 mul V
12.238 + hpt 2 mul 0 V
12.239 + hpt neg vpt 1.62 mul V Opaque stroke } def
12.240 +/TriDW { stroke [] 0 setdash vpt 1.12 mul sub M
12.241 + hpt neg vpt 1.62 mul V
12.242 + hpt 2 mul 0 V
12.243 + hpt neg vpt -1.62 mul V Opaque stroke } def
12.244 +/PentW { stroke [] 0 setdash gsave
12.245 + translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
12.246 + Opaque stroke grestore } def
12.247 +/CircW { stroke [] 0 setdash
12.248 + hpt 0 360 arc Opaque stroke } def
12.249 +/BoxFill { gsave Rec 1 setgray fill grestore } def
12.250 +/BoxColFill {
12.251 + gsave Rec
12.252 + /Fillden exch def
12.253 + currentrgbcolor
12.254 + /ColB exch def /ColG exch def /ColR exch def
12.255 + /ColR ColR Fillden mul Fillden sub 1 add def
12.256 + /ColG ColG Fillden mul Fillden sub 1 add def
12.257 + /ColB ColB Fillden mul Fillden sub 1 add def
12.258 + ColR ColG ColB setrgbcolor
12.259 + fill grestore } def
12.260 +%
12.261 +% PostScript Level 1 Pattern Fill routine
12.262 +% Usage: x y w h s a XX PatternFill
12.263 +% x,y = lower left corner of box to be filled
12.264 +% w,h = width and height of box
12.265 +% a = angle in degrees between lines and x-axis
12.266 +% XX = 0/1 for no/yes cross-hatch
12.267 +%
12.268 +/PatternFill { gsave /PFa [ 9 2 roll ] def
12.269 + PFa 0 get PFa 2 get 2 div add PFa 1 get PFa 3 get 2 div add translate
12.270 + PFa 2 get -2 div PFa 3 get -2 div PFa 2 get PFa 3 get Rec
12.271 + gsave 1 setgray fill grestore clip
12.272 + currentlinewidth 0.5 mul setlinewidth
12.273 + /PFs PFa 2 get dup mul PFa 3 get dup mul add sqrt def
12.274 + 0 0 M PFa 5 get rotate PFs -2 div dup translate
12.275 + 0 1 PFs PFa 4 get div 1 add floor cvi
12.276 + { PFa 4 get mul 0 M 0 PFs V } for
12.277 + 0 PFa 6 get ne {
12.278 + 0 1 PFs PFa 4 get div 1 add floor cvi
12.279 + { PFa 4 get mul 0 2 1 roll M PFs 0 V } for
12.280 + } if
12.281 + stroke grestore } def
12.282 +%
12.283 +/Symbol-Oblique /Symbol findfont [1 0 .167 1 0 0] makefont
12.284 +dup length dict begin {1 index /FID eq {pop pop} {def} ifelse} forall
12.285 +currentdict end definefont pop
12.286 +end
12.287 +%%EndProlog
12.288 +gnudict begin
12.289 +gsave
12.290 +50 50 translate
12.291 +0.050 0.050 scale
12.292 +0 setgray
12.293 +newpath
12.294 +(Helvetica) findfont 140 scalefont setfont
12.295 +1.000 UL
12.296 +LTb
12.297 +574 280 M
12.298 +63 0 V
12.299 +4885 0 R
12.300 +-63 0 V
12.301 +490 280 M
12.302 +gsave 0 setgray
12.303 +( 0) Rshow
12.304 +grestore
12.305 +1.000 UL
12.306 +LTb
12.307 +574 606 M
12.308 +63 0 V
12.309 +4885 0 R
12.310 +-63 0 V
12.311 +490 606 M
12.312 +gsave 0 setgray
12.313 +( 0.5) Rshow
12.314 +grestore
12.315 +1.000 UL
12.316 +LTb
12.317 +574 932 M
12.318 +63 0 V
12.319 +4885 0 R
12.320 +-63 0 V
12.321 +490 932 M
12.322 +gsave 0 setgray
12.323 +( 1) Rshow
12.324 +grestore
12.325 +1.000 UL
12.326 +LTb
12.327 +574 1257 M
12.328 +63 0 V
12.329 +4885 0 R
12.330 +-63 0 V
12.331 +-4969 0 R
12.332 +gsave 0 setgray
12.333 +( 1.5) Rshow
12.334 +grestore
12.335 +1.000 UL
12.336 +LTb
12.337 +574 1583 M
12.338 +63 0 V
12.339 +4885 0 R
12.340 +-63 0 V
12.341 +-4969 0 R
12.342 +gsave 0 setgray
12.343 +( 2) Rshow
12.344 +grestore
12.345 +1.000 UL
12.346 +LTb
12.347 +574 1909 M
12.348 +63 0 V
12.349 +4885 0 R
12.350 +-63 0 V
12.351 +-4969 0 R
12.352 +gsave 0 setgray
12.353 +( 2.5) Rshow
12.354 +grestore
12.355 +1.000 UL
12.356 +LTb
12.357 +574 2235 M
12.358 +63 0 V
12.359 +4885 0 R
12.360 +-63 0 V
12.361 +-4969 0 R
12.362 +gsave 0 setgray
12.363 +( 3) Rshow
12.364 +grestore
12.365 +1.000 UL
12.366 +LTb
12.367 +574 2561 M
12.368 +63 0 V
12.369 +4885 0 R
12.370 +-63 0 V
12.371 +-4969 0 R
12.372 +gsave 0 setgray
12.373 +( 3.5) Rshow
12.374 +grestore
12.375 +1.000 UL
12.376 +LTb
12.377 +574 2887 M
12.378 +63 0 V
12.379 +4885 0 R
12.380 +-63 0 V
12.381 +-4969 0 R
12.382 +gsave 0 setgray
12.383 +( 4) Rshow
12.384 +grestore
12.385 +1.000 UL
12.386 +LTb
12.387 +574 3212 M
12.388 +63 0 V
12.389 +4885 0 R
12.390 +-63 0 V
12.391 +-4969 0 R
12.392 +gsave 0 setgray
12.393 +( 4.5) Rshow
12.394 +grestore
12.395 +1.000 UL
12.396 +LTb
12.397 +574 3538 M
12.398 +63 0 V
12.399 +4885 0 R
12.400 +-63 0 V
12.401 +-4969 0 R
12.402 +gsave 0 setgray
12.403 +( 5) Rshow
12.404 +grestore
12.405 +1.000 UL
12.406 +LTb
12.407 +574 3864 M
12.408 +63 0 V
12.409 +4885 0 R
12.410 +-63 0 V
12.411 +-4969 0 R
12.412 +gsave 0 setgray
12.413 +( 5.5) Rshow
12.414 +grestore
12.415 +1.000 UL
12.416 +LTb
12.417 +574 280 M
12.418 +0 63 V
12.419 +0 3521 R
12.420 +0 -63 V
12.421 +574 140 M
12.422 +gsave 0 setgray
12.423 +( 0) Cshow
12.424 +grestore
12.425 +1.000 UL
12.426 +LTb
12.427 +1069 280 M
12.428 +0 63 V
12.429 +0 3521 R
12.430 +0 -63 V
12.431 +0 -3661 R
12.432 +gsave 0 setgray
12.433 +( 1000) Cshow
12.434 +grestore
12.435 +1.000 UL
12.436 +LTb
12.437 +1564 280 M
12.438 +0 63 V
12.439 +0 3521 R
12.440 +0 -63 V
12.441 +0 -3661 R
12.442 +gsave 0 setgray
12.443 +( 2000) Cshow
12.444 +grestore
12.445 +1.000 UL
12.446 +LTb
12.447 +2058 280 M
12.448 +0 63 V
12.449 +0 3521 R
12.450 +0 -63 V
12.451 +0 -3661 R
12.452 +gsave 0 setgray
12.453 +( 3000) Cshow
12.454 +grestore
12.455 +1.000 UL
12.456 +LTb
12.457 +2553 280 M
12.458 +0 63 V
12.459 +0 3521 R
12.460 +0 -63 V
12.461 +0 -3661 R
12.462 +gsave 0 setgray
12.463 +( 4000) Cshow
12.464 +grestore
12.465 +1.000 UL
12.466 +LTb
12.467 +3048 280 M
12.468 +0 63 V
12.469 +0 3521 R
12.470 +0 -63 V
12.471 +0 -3661 R
12.472 +gsave 0 setgray
12.473 +( 5000) Cshow
12.474 +grestore
12.475 +1.000 UL
12.476 +LTb
12.477 +3543 280 M
12.478 +0 63 V
12.479 +0 3521 R
12.480 +0 -63 V
12.481 +0 -3661 R
12.482 +gsave 0 setgray
12.483 +( 6000) Cshow
12.484 +grestore
12.485 +1.000 UL
12.486 +LTb
12.487 +4038 280 M
12.488 +0 63 V
12.489 +0 3521 R
12.490 +0 -63 V
12.491 +0 -3661 R
12.492 +gsave 0 setgray
12.493 +( 7000) Cshow
12.494 +grestore
12.495 +1.000 UL
12.496 +LTb
12.497 +4532 280 M
12.498 +0 63 V
12.499 +0 3521 R
12.500 +0 -63 V
12.501 +0 -3661 R
12.502 +gsave 0 setgray
12.503 +( 8000) Cshow
12.504 +grestore
12.505 +1.000 UL
12.506 +LTb
12.507 +5027 280 M
12.508 +0 63 V
12.509 +0 3521 R
12.510 +0 -63 V
12.511 +0 -3661 R
12.512 +gsave 0 setgray
12.513 +( 9000) Cshow
12.514 +grestore
12.515 +1.000 UL
12.516 +LTb
12.517 +5522 280 M
12.518 +0 63 V
12.519 +0 3521 R
12.520 +0 -63 V
12.521 +0 -3661 R
12.522 +gsave 0 setgray
12.523 +( 10000) Cshow
12.524 +grestore
12.525 +1.000 UL
12.526 +LTb
12.527 +1.000 UL
12.528 +LTb
12.529 +574 280 M
12.530 +4948 0 V
12.531 +0 3584 V
12.532 +-4948 0 V
12.533 +574 280 L
12.534 +1.000 UP
12.535 +1.000 UL
12.536 +LT5
12.537 +LTb
12.538 +4871 3731 M
12.539 +gsave 0 setgray
12.540 +(Original) Rshow
12.541 +grestore
12.542 +LT5
12.543 +4955 3731 M
12.544 +399 0 V
12.545 +623 521 M
12.546 +50 2 V
12.547 +49 -7 V
12.548 +50 33 V
12.549 +49 -25 V
12.550 +50 21 V
12.551 +49 2 V
12.552 +50 0 V
12.553 +49 1 V
12.554 +50 -6 V
12.555 +49 5 V
12.556 +50 4 V
12.557 +49 4 V
12.558 +50 10 V
12.559 +49 0 V
12.560 +50 2 V
12.561 +49 -1 V
12.562 +50 9 V
12.563 +49 2 V
12.564 +50 6 V
12.565 +49 36 V
12.566 +50 2 V
12.567 +49 21 V
12.568 +50 8 V
12.569 +49 11 V
12.570 +49 5 V
12.571 +50 5 V
12.572 +49 2 V
12.573 +50 104 V
12.574 +49 -82 V
12.575 +50 13 V
12.576 +49 4 V
12.577 +50 16 V
12.578 +49 36 V
12.579 +50 32 V
12.580 +49 -5 V
12.581 +50 32 V
12.582 +49 36 V
12.583 +50 30 V
12.584 +49 -8 V
12.585 +50 42 V
12.586 +49 28 V
12.587 +50 33 V
12.588 +49 43 V
12.589 +50 58 V
12.590 +49 78 V
12.591 +50 95 V
12.592 +49 126 V
12.593 +50 285 V
12.594 +49 1708 V
12.595 +49 -665 V
12.596 +50 -235 V
12.597 +49 -143 V
12.598 +50 -103 V
12.599 +49 -101 V
12.600 +50 -118 V
12.601 +49 -94 V
12.602 +50 -40 V
12.603 +49 -57 V
12.604 +50 -133 V
12.605 +49 5 V
12.606 +50 -16 V
12.607 +49 57 V
12.608 +50 -144 V
12.609 +49 -37 V
12.610 +50 -48 V
12.611 +49 -64 V
12.612 +50 17 V
12.613 +49 -67 V
12.614 +50 -41 V
12.615 +49 -18 V
12.616 +50 -9 V
12.617 +49 10 V
12.618 +50 -5 V
12.619 +49 -2 V
12.620 +49 -26 V
12.621 +50 -26 V
12.622 +49 -42 V
12.623 +50 50 V
12.624 +49 -78 V
12.625 +50 -51 V
12.626 +49 -13 V
12.627 +50 9 V
12.628 +49 -8 V
12.629 +50 0 V
12.630 +49 -1 V
12.631 +50 -7 V
12.632 +49 1 V
12.633 +50 -4 V
12.634 +49 -13 V
12.635 +50 -7 V
12.636 +49 -25 V
12.637 +50 5 V
12.638 +49 -11 V
12.639 +50 -16 V
12.640 +49 -9 V
12.641 +50 -24 V
12.642 +49 -2 V
12.643 +50 -21 V
12.644 +1.000 UL
12.645 +LT0
12.646 +LTb
12.647 +4871 3591 M
12.648 +gsave 0 setgray
12.649 +(Swapped) Rshow
12.650 +grestore
12.651 +LT0
12.652 +4955 3591 M
12.653 +399 0 V
12.654 +623 1034 M
12.655 +50 -1 V
12.656 +49 30 V
12.657 +50 -5 V
12.658 +49 57 V
12.659 +50 -20 V
12.660 +49 26 V
12.661 +50 0 V
12.662 +49 11 V
12.663 +50 -10 V
12.664 +49 25 V
12.665 +50 6 V
12.666 +49 6 V
12.667 +50 -16 V
12.668 +49 21 V
12.669 +50 15 V
12.670 +49 82 V
12.671 +50 -88 V
12.672 +49 26 V
12.673 +50 37 V
12.674 +49 1 V
12.675 +50 22 V
12.676 +49 64 V
12.677 +50 21 V
12.678 +49 -3 V
12.679 +49 11 V
12.680 +50 -8 V
12.681 +49 29 V
12.682 +50 8 V
12.683 +49 6 V
12.684 +50 29 V
12.685 +49 7 V
12.686 +50 119 V
12.687 +49 26 V
12.688 +50 49 V
12.689 +49 32 V
12.690 +50 24 V
12.691 +49 64 V
12.692 +50 -9 V
12.693 +49 51 V
12.694 +50 35 V
12.695 +49 84 V
12.696 +50 99 V
12.697 +49 77 V
12.698 +50 87 V
12.699 +49 84 V
12.700 +50 212 V
12.701 +49 48 V
12.702 +50 281 V
12.703 +49 771 V
12.704 +49 -1861 V
12.705 +50 -283 V
12.706 +49 -116 V
12.707 +50 -117 V
12.708 +49 -89 V
12.709 +50 -47 V
12.710 +49 -54 V
12.711 +50 -29 V
12.712 +49 -32 V
12.713 +50 -39 V
12.714 +49 -18 V
12.715 +50 14 V
12.716 +49 -48 V
12.717 +50 -29 V
12.718 +49 -22 V
12.719 +50 -17 V
12.720 +49 -26 V
12.721 +50 4 V
12.722 +49 -30 V
12.723 +50 -12 V
12.724 +49 -12 V
12.725 +50 -1 V
12.726 +49 -21 V
12.727 +50 -9 V
12.728 +49 21 V
12.729 +49 -20 V
12.730 +50 -8 V
12.731 +49 -7 V
12.732 +50 -19 V
12.733 +49 -21 V
12.734 +50 -11 V
12.735 +49 2 V
12.736 +50 -6 V
12.737 +49 -7 V
12.738 +50 2 V
12.739 +49 72 V
12.740 +50 -87 V
12.741 +49 -7 V
12.742 +50 5 V
12.743 +49 -12 V
12.744 +50 1 V
12.745 +49 4 V
12.746 +50 -2 V
12.747 +49 -14 V
12.748 +50 -10 V
12.749 +49 -2 V
12.750 +50 19 V
12.751 +49 -29 V
12.752 +50 5 V
12.753 +1.000 UL
12.754 +LTb
12.755 +574 280 M
12.756 +4948 0 V
12.757 +0 3584 V
12.758 +-4948 0 V
12.759 +574 280 L
12.760 +1.000 UP
12.761 +stroke
12.762 +grestore
12.763 +end
12.764 +showpage
12.765 +%%Trailer
12.766 +%%DocumentFonts: Helvetica
13.1 Binary file doc/images/swap_test.png has changed
14.1 --- a/lemon/bpugraph_adaptor.h Mon May 15 09:46:33 2006 +0000
14.2 +++ b/lemon/bpugraph_adaptor.h Mon May 15 09:49:51 2006 +0000
14.3 @@ -409,8 +409,35 @@
14.4 /// \brief Bipartite graph adaptor which swaps the two nodeset.
14.5 ///
14.6 /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
14.7 - /// a-nodeset will be the original graph's b-nodeset and the adaptor's
14.8 - /// b-nodeset will be the original graph's a-nodeset.
14.9 + /// anode-set will be the original graph's bnode-set and the adaptor's
14.10 + /// bnode-set will be the original graph's anode-set.
14.11 + ///
14.12 + /// As example look at an algorithm what can be sped up with the
14.13 + /// swap bipartite undirected graph adaptor. If we want to find the
14.14 + /// maximum matching in the bipartite graph then it will be not changed
14.15 + /// if we swap the two nodesets. But the algorithm use the two nodeset
14.16 + /// different way. If we swap the nodesets it provides different
14.17 + /// running time. We run a test on random bipartite graphs with
14.18 + /// different rate of the anode-set size and bnode-set size.
14.19 + /// We always made graphs with 10000 nodes and 20000 edges and we
14.20 + /// computed the maximum cardinality matching with the Hopcroft-Karp
14.21 + /// algorithm.
14.22 + ///
14.23 + /// The next diagram shows the running time of the tests. If the anode-set
14.24 + /// is smaller than the bnode-set the running time is better than with
14.25 + /// the swapped graph. Other conclusion is that the running time
14.26 + /// is greater when the two nodesets size are nearly equal.
14.27 + ///
14.28 + /// \image html swap_test.png
14.29 + /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
14.30 + ///
14.31 + /// The next part shows how can we swap the two nodeset:
14.32 + ///
14.33 + ///\code
14.34 + /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
14.35 + /// SBpUGraph sbpugraph(bpugraph);
14.36 + /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
14.37 + ///\endcode
14.38 template <typename _BpUGraph>
14.39 class SwapBpUGraphAdaptor
14.40 : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > {
14.41 @@ -425,6 +452,9 @@
14.42
14.43 public:
14.44
14.45 + /// \brief Construct a swapped graph.
14.46 + ///
14.47 + /// Construct a swapped graph.
14.48 explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
14.49
14.50 };
15.1 --- a/lemon/eps.h Mon May 15 09:46:33 2006 +0000
15.2 +++ b/lemon/eps.h Mon May 15 09:49:51 2006 +0000
15.3 @@ -26,7 +26,7 @@
15.4 #include<lemon/color.h>
15.5 #include<lemon/xy.h>
15.6
15.7 - ///\ingroup io_group
15.8 + ///\ingroup eps_io
15.9 ///\file
15.10 ///\brief Simple tool to create \c .eps files
15.11 ///
15.12 @@ -34,7 +34,7 @@
15.13
15.14 namespace lemon {
15.15
15.16 - ///\ingroup io_group
15.17 + ///\ingroup eps_io
15.18 ///\brief A simple tool to create \c .eps files
15.19 ///
15.20 ///A simple tool to create \c .eps files
16.1 --- a/lemon/graph_adaptor.h Mon May 15 09:46:33 2006 +0000
16.2 +++ b/lemon/graph_adaptor.h Mon May 15 09:49:51 2006 +0000
16.3 @@ -264,6 +264,40 @@
16.4 ///\endcode
16.5 /// implements the graph obtained from \c g by
16.6 /// reversing the orientation of its edges.
16.7 + ///
16.8 + /// A good example of using RevGraphAdaptor is to decide that the
16.9 + /// directed graph is wheter strongly connected or not. If from one
16.10 + /// node each node is reachable and from each node is reachable this
16.11 + /// node then and just then the graph is strongly connected. Instead of
16.12 + /// this condition we use a little bit different. From one node each node
16.13 + /// ahould be reachable in the graph and in the reversed graph. Now this
16.14 + /// condition can be checked with the Dfs algorithm class and the
16.15 + /// RevGraphAdaptor algorithm class.
16.16 + ///
16.17 + /// And look at the code:
16.18 + ///
16.19 + ///\code
16.20 + /// bool stronglyConnected(const Graph& graph) {
16.21 + /// if (NodeIt(graph) == INVALID) return true;
16.22 + /// Dfs<Graph> dfs(graph);
16.23 + /// dfs.run(NodeIt(graph));
16.24 + /// for (NodeIt it(graph); it != INVALID; ++it) {
16.25 + /// if (!dfs.reached(it)) {
16.26 + /// return false;
16.27 + /// }
16.28 + /// }
16.29 + /// typedef RevGraphAdaptor<const Graph> RGraph;
16.30 + /// RGraph rgraph(graph);
16.31 + /// DfsVisit<RGraph> rdfs(rgraph);
16.32 + /// rdfs.run(NodeIt(graph));
16.33 + /// for (NodeIt it(graph); it != INVALID; ++it) {
16.34 + /// if (!rdfs.reached(it)) {
16.35 + /// return false;
16.36 + /// }
16.37 + /// }
16.38 + /// return true;
16.39 + /// }
16.40 + ///\endcode
16.41 template<typename _Graph>
16.42 class RevGraphAdaptor :
16.43 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
16.44 @@ -2387,7 +2421,7 @@
16.45 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
16.46 ///
16.47 /// The second solution contains just 3 disjoint paths while the first 4.
16.48 - /// The full code can be found in the \ref disjoint_paths.cc demo file.
16.49 + /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
16.50 ///
16.51 /// This graph adaptor is fully conform to the
16.52 /// \ref concept::StaticGraph "StaticGraph" concept and
16.53 @@ -2587,6 +2621,15 @@
16.54
16.55 };
16.56
16.57 + /// \brief Just gives back a split graph adaptor
16.58 + ///
16.59 + /// Just gives back a split graph adaptor
16.60 + template<typename Graph>
16.61 + SplitGraphAdaptor<Graph>
16.62 + splitGraphAdaptor(const Graph& graph) {
16.63 + return SplitGraphAdaptor<Graph>(graph);
16.64 + }
16.65 +
16.66
16.67 } //namespace lemon
16.68
17.1 --- a/lemon/graph_reader.h Mon May 15 09:46:33 2006 +0000
17.2 +++ b/lemon/graph_reader.h Mon May 15 09:49:51 2006 +0000
17.3 @@ -16,7 +16,7 @@
17.4 *
17.5 */
17.6
17.7 -///\ingroup io_group
17.8 +///\ingroup lemon_io
17.9 ///\file
17.10 ///\brief Lemon Graph Format reader.
17.11
17.12 @@ -30,7 +30,7 @@
17.13
17.14 namespace lemon {
17.15
17.16 - /// \addtogroup io_group
17.17 + /// \addtogroup lemon_io
17.18 /// @{
17.19
17.20 /// \brief The graph reader class.
18.1 --- a/lemon/graph_to_eps.h Mon May 15 09:46:33 2006 +0000
18.2 +++ b/lemon/graph_to_eps.h Mon May 15 09:49:51 2006 +0000
18.3 @@ -41,7 +41,7 @@
18.4 #include<lemon/bezier.h>
18.5
18.6
18.7 -///\ingroup io_group
18.8 +///\ingroup eps_io
18.9 ///\file
18.10 ///\brief Simple graph drawer
18.11 ///
18.12 @@ -1042,7 +1042,7 @@
18.13
18.14 ///Generates an EPS file from a graph
18.15
18.16 -///\ingroup io_group
18.17 +///\ingroup eps_io
18.18 ///Generates an EPS file from a graph.
18.19 ///\param g is a reference to the graph to be printed
18.20 ///\param os is a reference to the output stream.
18.21 @@ -1071,7 +1071,7 @@
18.22
18.23 ///Generates an EPS file from a graph
18.24
18.25 -///\ingroup io_group
18.26 +///\ingroup eps_io
18.27 ///This function does the same as
18.28 ///\ref graphToEps(G &g,std::ostream& os)
18.29 ///but it writes its output into the file \c file_name
18.30 @@ -1087,7 +1087,7 @@
18.31
18.32 ///Generates an EPS file from a graph
18.33
18.34 -///\ingroup io_group
18.35 +///\ingroup eps_io
18.36 ///This function does the same as
18.37 ///\ref graphToEps(G &g,std::ostream& os)
18.38 ///but it writes its output into the file \c file_name
19.1 --- a/lemon/kruskal.h Mon May 15 09:46:33 2006 +0000
19.2 +++ b/lemon/kruskal.h Mon May 15 09:49:51 2006 +0000
19.3 @@ -25,16 +25,6 @@
19.4 #include <lemon/bits/utility.h>
19.5 #include <lemon/bits/traits.h>
19.6
19.7 -/**
19.8 -@defgroup spantree Minimum Cost Spanning Tree Algorithms
19.9 -@ingroup galgs
19.10 -\brief This group containes the algorithms for finding a minimum cost spanning
19.11 -tree in a graph
19.12 -
19.13 -This group containes the algorithms for finding a minimum cost spanning
19.14 -tree in a graph
19.15 -*/
19.16 -
19.17 ///\ingroup spantree
19.18 ///\file
19.19 ///\brief Kruskal's algorithm to compute a minimum cost tree
20.1 --- a/lemon/lemon_reader.h Mon May 15 09:46:33 2006 +0000
20.2 +++ b/lemon/lemon_reader.h Mon May 15 09:49:51 2006 +0000
20.3 @@ -16,7 +16,7 @@
20.4 *
20.5 */
20.6
20.7 -///\ingroup io_group
20.8 +///\ingroup lemon_io
20.9 ///\file
20.10 ///\brief Lemon Format reader.
20.11
20.12 @@ -456,7 +456,7 @@
20.13
20.14 }
20.15
20.16 - /// \ingroup io_group
20.17 + /// \ingroup lemon_io
20.18 /// \brief Lemon Format reader class.
20.19 ///
20.20 /// The Lemon Format contains several sections. We do not want to
20.21 @@ -523,9 +523,9 @@
20.22
20.23 char_type* eptr() { return _eptr; }
20.24
20.25 - int blen() { return _eptr - _base; }
20.26 + int_type blen() { return _eptr - _base; }
20.27
20.28 - void setb(char_type* buf, int len) {
20.29 + void setb(char_type* buf, int_type len) {
20.30 _base = buf;
20.31 _eptr = buf + len;
20.32 }
20.33 @@ -581,7 +581,7 @@
20.34 return false;
20.35 }
20.36
20.37 - virtual int underflow() {
20.38 + virtual int_type underflow() {
20.39 char c;
20.40 if (_is.read(&c, 1)) {
20.41 _is.putback(c);
20.42 @@ -612,7 +612,7 @@
20.43 return *base();
20.44 }
20.45
20.46 - virtual int sync() {
20.47 + virtual int_type sync() {
20.48 return EOF;
20.49 }
20.50 };
21.1 --- a/lemon/lemon_writer.h Mon May 15 09:46:33 2006 +0000
21.2 +++ b/lemon/lemon_writer.h Mon May 15 09:49:51 2006 +0000
21.3 @@ -16,7 +16,7 @@
21.4 *
21.5 */
21.6
21.7 -///\ingroup io_group
21.8 +///\ingroup lemon_io
21.9 ///\file
21.10 ///\brief Lemon Format writer.
21.11
21.12 @@ -257,7 +257,7 @@
21.13
21.14 }
21.15
21.16 - /// \ingroup io_group
21.17 + /// \ingroup lemon_io
21.18 /// \brief Lemon Format writer class.
21.19 ///
21.20 /// The Lemon Format contains several sections. We do not want to
21.21 @@ -310,10 +310,15 @@
21.22 /// It gives back the header of the section.
21.23 virtual std::string header() = 0;
21.24
21.25 - /// \brief Writer function of the section.
21.26 + /// \brief Writer function of the section.
21.27 ///
21.28 /// Write the content of the section.
21.29 virtual void write(std::ostream& os) = 0;
21.30 +
21.31 + /// \brief Gives back true when the section should be written.
21.32 + ///
21.33 + /// Gives back true when the section should be written.
21.34 + virtual bool valid() { return true; }
21.35 };
21.36
21.37 /// \brief Constructor for LemonWriter.
21.38 @@ -355,8 +360,10 @@
21.39 void run() {
21.40 SectionWriters::iterator it;
21.41 for (it = writers.begin(); it != writers.end(); ++it) {
21.42 - *os << (*it)->header() << std::endl;
21.43 - (*it)->write(*os);
21.44 + if ((*it)->valid()) {
21.45 + *os << (*it)->header() << std::endl;
21.46 + (*it)->write(*os);
21.47 + }
21.48 }
21.49 *os << "@end" << std::endl;
21.50 }
21.51 @@ -464,7 +471,7 @@
21.52 /// Write the content of the section.
21.53 virtual void write(std::ostream& os) {
21.54 for (int i = 0; i < (int)writers.size(); ++i) {
21.55 - if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) {
21.56 + if (writers[i].first == "label") {
21.57 labelMap = writers[i].second;
21.58 forceLabelMap = false;
21.59 break;
21.60 @@ -636,7 +643,7 @@
21.61 throw DataFormatError("Cannot find nodeset or label map");
21.62 }
21.63 for (int i = 0; i < (int)writers.size(); ++i) {
21.64 - if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) {
21.65 + if (writers[i].first == "label") {
21.66 labelMap = writers[i].second;
21.67 forceLabelMap = false;
21.68 break;
21.69 @@ -1008,6 +1015,11 @@
21.70 os << std::endl;
21.71 }
21.72 }
21.73 +
21.74 + /// \brief Gives back true when the section should be written.
21.75 + ///
21.76 + /// Gives back true when the section should be written.
21.77 + virtual bool valid() { return !writers.empty(); }
21.78
21.79 private:
21.80
21.81 @@ -1087,6 +1099,11 @@
21.82 os << std::endl;
21.83 }
21.84 }
21.85 +
21.86 + /// \brief Gives back true when the section should be written.
21.87 + ///
21.88 + /// Gives back true when the section should be written.
21.89 + virtual bool valid() { return !writers.empty(); }
21.90
21.91 private:
21.92
21.93 @@ -1189,6 +1206,13 @@
21.94 os << std::endl;
21.95 }
21.96 }
21.97 +
21.98 + /// \brief Gives back true when the section should be written.
21.99 + ///
21.100 + /// Gives back true when the section should be written.
21.101 + virtual bool valid() {
21.102 + return !uEdgeWriters.empty() || !edgeWriters.empty();
21.103 + }
21.104
21.105 private:
21.106
21.107 @@ -1288,6 +1312,11 @@
21.108 }
21.109 }
21.110
21.111 + /// \brief Gives back true when the section should be written.
21.112 + ///
21.113 + /// Gives back true when the section should be written.
21.114 + virtual bool valid() { return !writers.empty(); }
21.115 +
21.116 private:
21.117 std::string name;
21.118
22.1 --- a/lemon/matrix_maps.h Mon May 15 09:46:33 2006 +0000
22.2 +++ b/lemon/matrix_maps.h Mon May 15 09:49:51 2006 +0000
22.3 @@ -47,6 +47,9 @@
22.4 typedef typename MatrixMap::Value Value;
22.5
22.6
22.7 + /// \brief Constructor of the row map
22.8 + ///
22.9 + /// Constructor of the row map.
22.10 MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row)
22.11 : matrix(_matrix), row(_row) {}
22.12
22.13 @@ -91,6 +94,9 @@
22.14 typedef typename MatrixMap::Value Value;
22.15
22.16
22.17 + /// \brief Constructor of the row map
22.18 + ///
22.19 + /// Constructor of the row map.
22.20 ConstMatrixRowMap(const MatrixMap& _matrix,
22.21 typename MatrixMap::FirstKey _row)
22.22 : matrix(_matrix), row(_row) {}
22.23 @@ -108,11 +114,14 @@
22.24 typename MatrixMap::FirstKey row;
22.25 };
22.26
22.27 + /// \ingroup matrices
22.28 + ///
22.29 /// \brief Gives back a row view of the matrix map
22.30 ///
22.31 - /// \ingroup matrices
22.32 /// Gives back a row view of the matrix map.
22.33 ///
22.34 + /// \sa MatrixRowMap
22.35 + /// \sa ConstMatrixRowMap
22.36 template <typename MatrixMap>
22.37 MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,
22.38 typename MatrixMap::FirstKey row) {
22.39 @@ -137,6 +146,9 @@
22.40 typedef typename MatrixMap::FirstKey Key;
22.41 typedef typename MatrixMap::Value Value;
22.42
22.43 + /// \brief Constructor of the column map
22.44 + ///
22.45 + /// Constructor of the column map.
22.46 MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col)
22.47 : matrix(_matrix), col(_col) {}
22.48
22.49 @@ -180,6 +192,9 @@
22.50 typedef typename MatrixMap::FirstKey Key;
22.51 typedef typename MatrixMap::Value Value;
22.52
22.53 + /// \brief Constructor of the column map
22.54 + ///
22.55 + /// Constructor of the column map.
22.56 ConstMatrixColMap(const MatrixMap& _matrix,
22.57 typename MatrixMap::SecondKey _col)
22.58 : matrix(_matrix), col(_col) {}
22.59 @@ -197,11 +212,14 @@
22.60 typename MatrixMap::SecondKey col;
22.61 };
22.62
22.63 + /// \ingroup matrices
22.64 + ///
22.65 /// \brief Gives back a column view of the matrix map
22.66 ///
22.67 - /// \ingroup matrices
22.68 /// Gives back a column view of the matrix map.
22.69 ///
22.70 + /// \sa MatrixColMap
22.71 + /// \sa ConstMatrixColMap
22.72 template <typename MatrixMap>
22.73 MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
22.74 typename MatrixMap::SecondKey col) {
23.1 --- a/lemon/path.h Mon May 15 09:46:33 2006 +0000
23.2 +++ b/lemon/path.h Mon May 15 09:49:51 2006 +0000
23.3 @@ -16,21 +16,6 @@
23.4 *
23.5 */
23.6
23.7 -/**
23.8 -@defgroup paths Path Structures
23.9 -@ingroup datas
23.10 -\brief Path structures implemented in LEMON.
23.11 -
23.12 -LEMON provides flexible data structures
23.13 -to work with paths.
23.14 -
23.15 -All of them have the same interface, especially they can be built or extended
23.16 -using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
23.17 -algorithm to store its result in any kind of path structure.
23.18 -
23.19 -\sa lemon::concept::Path
23.20 -
23.21 -*/
23.22
23.23 ///\ingroup paths
23.24 ///\file
24.1 --- a/lemon/radix_sort.h Mon May 15 09:46:33 2006 +0000
24.2 +++ b/lemon/radix_sort.h Mon May 15 09:49:51 2006 +0000
24.3 @@ -19,7 +19,7 @@
24.4 #ifndef RADIX_SORT_H
24.5 #define RADIX_SORT_H
24.6
24.7 -/// \ingroup auxdat
24.8 +/// \ingroup auxalg
24.9 /// \file
24.10 /// \brief Radix sort
24.11 ///
24.12 @@ -194,7 +194,7 @@
24.13
24.14 }
24.15
24.16 - /// \ingroup auxdat
24.17 + /// \ingroup auxalg
24.18 ///
24.19 /// \brief Sorts the stl compatible range into ascending order.
24.20 ///
24.21 @@ -411,7 +411,7 @@
24.22
24.23 }
24.24
24.25 - /// \ingroup auxdat
24.26 + /// \ingroup auxalg
24.27 ///
24.28 /// \brief Sorts stable the stl compatible range into ascending order.
24.29 ///
25.1 --- a/lemon/ugraph_adaptor.h Mon May 15 09:46:33 2006 +0000
25.2 +++ b/lemon/ugraph_adaptor.h Mon May 15 09:49:51 2006 +0000
25.3 @@ -38,8 +38,6 @@
25.4
25.5 namespace lemon {
25.6
25.7 - /// \ingroup graph_adaptors
25.8 - ///
25.9 /// \brief Base type for the Graph Adaptors
25.10 ///
25.11 /// This is the base type for most of LEMON graph adaptors.
25.12 @@ -233,6 +231,11 @@
25.13 };
25.14
25.15 /// \ingroup graph_adaptors
25.16 + ///
25.17 + /// \brief Trivial undirected graph adaptor
25.18 + ///
25.19 + /// This class is an adaptor which does not change the adapted undirected
25.20 + /// graph. It can be used only to test the undirected graph adaptors.
25.21 template <typename _UGraph>
25.22 class UGraphAdaptor
25.23 : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {
25.24 @@ -348,44 +351,42 @@
25.25 || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d);
25.26 }
25.27
25.28 - ///\e
25.29 -
25.30 + /// \brief Hide the given node in the graph.
25.31 + ///
25.32 /// This function hides \c n in the graph, i.e. the iteration
25.33 /// jumps over it. This is done by simply setting the value of \c n
25.34 /// to be false in the corresponding node-map.
25.35 void hide(const Node& n) const { node_filter_map->set(n, false); }
25.36
25.37 - ///\e
25.38 -
25.39 + /// \brief Hide the given undirected edge in the graph.
25.40 + ///
25.41 /// This function hides \c e in the graph, i.e. the iteration
25.42 /// jumps over it. This is done by simply setting the value of \c e
25.43 - /// to be false in the corresponding edge-map.
25.44 + /// to be false in the corresponding uedge-map.
25.45 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
25.46
25.47 - ///\e
25.48 -
25.49 + /// \brief Unhide the given node in the graph.
25.50 + ///
25.51 /// The value of \c n is set to be true in the node-map which stores
25.52 /// hide information. If \c n was hidden previuosly, then it is shown
25.53 /// again
25.54 void unHide(const Node& n) const { node_filter_map->set(n, true); }
25.55
25.56 - ///\e
25.57 -
25.58 - /// The value of \c e is set to be true in the edge-map which stores
25.59 + /// \brief Hide the given undirected edge in the graph.
25.60 + ///
25.61 + /// The value of \c e is set to be true in the uedge-map which stores
25.62 /// hide information. If \c e was hidden previuosly, then it is shown
25.63 /// again
25.64 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
25.65
25.66 + /// \brief Returns true if \c n is hidden.
25.67 + ///
25.68 /// Returns true if \c n is hidden.
25.69 -
25.70 - ///\e
25.71 - ///
25.72 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
25.73
25.74 - /// Returns true if \c n is hidden.
25.75 -
25.76 - ///\e
25.77 + /// \brief Returns true if \c e is hidden.
25.78 ///
25.79 + /// Returns true if \c e is hidden.
25.80 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
25.81
25.82 typedef False NodeNumTag;
25.83 @@ -577,44 +578,42 @@
25.84 while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
25.85 }
25.86
25.87 - ///\e
25.88 -
25.89 + /// \brief Hide the given node in the graph.
25.90 + ///
25.91 /// This function hides \c n in the graph, i.e. the iteration
25.92 /// jumps over it. This is done by simply setting the value of \c n
25.93 /// to be false in the corresponding node-map.
25.94 void hide(const Node& n) const { node_filter_map->set(n, false); }
25.95
25.96 - ///\e
25.97 -
25.98 + /// \brief Hide the given undirected edge in the graph.
25.99 + ///
25.100 /// This function hides \c e in the graph, i.e. the iteration
25.101 /// jumps over it. This is done by simply setting the value of \c e
25.102 - /// to be false in the corresponding edge-map.
25.103 + /// to be false in the corresponding uedge-map.
25.104 void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
25.105
25.106 - ///\e
25.107 -
25.108 + /// \brief Unhide the given node in the graph.
25.109 + ///
25.110 /// The value of \c n is set to be true in the node-map which stores
25.111 /// hide information. If \c n was hidden previuosly, then it is shown
25.112 /// again
25.113 void unHide(const Node& n) const { node_filter_map->set(n, true); }
25.114
25.115 - ///\e
25.116 -
25.117 - /// The value of \c e is set to be true in the edge-map which stores
25.118 + /// \brief Hide the given undirected edge in the graph.
25.119 + ///
25.120 + /// The value of \c e is set to be true in the uedge-map which stores
25.121 /// hide information. If \c e was hidden previuosly, then it is shown
25.122 /// again
25.123 void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
25.124
25.125 + /// \brief Returns true if \c n is hidden.
25.126 + ///
25.127 /// Returns true if \c n is hidden.
25.128 -
25.129 - ///\e
25.130 - ///
25.131 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
25.132
25.133 - /// Returns true if \c n is hidden.
25.134 -
25.135 - ///\e
25.136 + /// \brief Returns true if \c e is hidden.
25.137 ///
25.138 + /// Returns true if \c e is hidden.
25.139 bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
25.140
25.141 typedef False NodeNumTag;
25.142 @@ -733,9 +732,6 @@
25.143 /// should filter all edges which's source or target is filtered by the
25.144 /// node-filter.
25.145 ///
25.146 - /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
25.147 - /// \c Graph::Node that is why \c g.id(n) can be applied.
25.148 - ///
25.149 template<typename _UGraph, typename NodeFilterMap,
25.150 typename UEdgeFilterMap, bool checked = true>
25.151 class SubUGraphAdaptor :
