1.1 --- a/demo/graph_to_eps_demo.cc Mon Jul 25 11:17:23 2005 +0000
1.2 +++ b/demo/graph_to_eps_demo.cc Tue Jul 26 13:15:13 2005 +0000
1.3 @@ -20,10 +20,11 @@
1.4 ///
1.5 /// This demo program shows examples how to use the function \ref
1.6 /// graphToEps(). It takes no input but simply creates six
1.7 -/// <tt>.eps</tt> files demonstrating how to draw directed/undirected
1.8 -/// graphs, how to handle parallel egdes, how to change the properties
1.9 -/// (like color, shape, size, title etc.) of nodes and edges
1.10 -/// individually using appropriate \ref maps-page "graphmaps".
1.11 +/// <tt>.eps</tt> files demonstrating the capability of \ref
1.12 +/// graphToEps(), and showing how to draw directed/undirected graphs,
1.13 +/// how to handle parallel egdes, how to change the properties (like
1.14 +/// color, shape, size, title etc.) of nodes and edges individually
1.15 +/// using appropriate \ref maps-page "graphmapfactory".
1.16
1.17 #include <cmath>
1.18
2.1 --- a/doc/groups.dox Mon Jul 25 11:17:23 2005 +0000
2.2 +++ b/doc/groups.dox Tue Jul 26 13:15:13 2005 +0000
2.3 @@ -164,7 +164,7 @@
2.4 graph structures and helper classes used to implement these.
2.5 */
2.6
2.7 -/**
2.8 +/* --- Unused group
2.9 @defgroup experimental Experimental Structures and Algorithms
2.10 This group contains some Experimental structures and algorithms.
2.11 The stuff here is subject to change.
3.1 --- a/lemon/bits/alteration_notifier.h Mon Jul 25 11:17:23 2005 +0000
3.2 +++ b/lemon/bits/alteration_notifier.h Tue Jul 26 13:15:13 2005 +0000
3.3 @@ -20,13 +20,13 @@
3.4 #include <vector>
3.5 #include <algorithm>
3.6
3.7 -///\ingroup graphmaps
3.8 +///\ingroup graphmapfactory
3.9 ///\file
3.10 ///\brief Observer registry for graph alteration observers.
3.11
3.12 namespace lemon {
3.13
3.14 - /// \addtogroup graphmaps
3.15 + /// \addtogroup graphmapfactory
3.16 /// @{
3.17
3.18 /// \brief Registry class to register objects observes alterations in
4.1 --- a/lemon/bits/array_map.h Mon Jul 25 11:17:23 2005 +0000
4.2 +++ b/lemon/bits/array_map.h Tue Jul 26 13:15:13 2005 +0000
4.3 @@ -20,7 +20,7 @@
4.4 #include <memory>
4.5 #include <lemon/bits/map_iterator.h>
4.6
4.7 -///\ingroup graphmaps
4.8 +///\ingroup graphmapfactory
4.9 ///\file
4.10 ///\brief Graph maps that construates and destruates
4.11 ///their elements dynamically.
4.12 @@ -28,7 +28,7 @@
4.13 namespace lemon {
4.14
4.15
4.16 - /// \addtogroup graphmaps
4.17 + /// \addtogroup graphmapfactory
4.18 /// @{
4.19
4.20 /// The ArrayMap template class is graph map structure what
5.1 --- a/lemon/bits/default_map.h Mon Jul 25 11:17:23 2005 +0000
5.2 +++ b/lemon/bits/default_map.h Tue Jul 26 13:15:13 2005 +0000
5.3 @@ -21,14 +21,14 @@
5.4 #include <lemon/bits/array_map.h>
5.5 #include <lemon/bits/vector_map.h>
5.6
5.7 -///\ingroup graphmaps
5.8 +///\ingroup graphmapfactory
5.9 ///\file
5.10 ///\brief Graph maps that construct and destruct
5.11 ///their elements dynamically.
5.12
5.13 namespace lemon {
5.14
5.15 -/// \addtogroup graphmaps
5.16 +/// \addtogroup graphmapfactory
5.17 /// @{
5.18
5.19 /** The ArrayMap template class is graph map structure what
6.1 --- a/lemon/bits/map_iterator.h Mon Jul 25 11:17:23 2005 +0000
6.2 +++ b/lemon/bits/map_iterator.h Tue Jul 26 13:15:13 2005 +0000
6.3 @@ -22,13 +22,13 @@
6.4 #include <lemon/bits/extended_pair.h>
6.5 #include <lemon/graph_utils.h>
6.6
6.7 -///\ingroup graphmaps
6.8 +///\ingroup graphmapfactory
6.9 ///\file
6.10 ///\brief Iterators on the maps.
6.11
6.12 namespace lemon {
6.13
6.14 - /// \addtogroup graphmaps
6.15 + /// \addtogroup graphmapfactory
6.16 /// @{
6.17
6.18 /** The base class all of the map iterators.
7.1 --- a/lemon/bits/vector_map.h Mon Jul 25 11:17:23 2005 +0000
7.2 +++ b/lemon/bits/vector_map.h Tue Jul 26 13:15:13 2005 +0000
7.3 @@ -24,13 +24,13 @@
7.4 #include <lemon/bits/map_iterator.h>
7.5 #include <lemon/bits/alteration_notifier.h>
7.6
7.7 -///\ingroup graphmaps
7.8 +///\ingroup graphmapfactory
7.9 ///\file
7.10 ///\brief Vector based graph maps.
7.11
7.12 namespace lemon {
7.13
7.14 - /// \addtogroup graphmaps
7.15 + /// \addtogroup graphmapfactory
7.16 /// @{
7.17
7.18 /// The VectorMap template class is graph map structure what
8.1 --- a/lemon/max_matching.h Mon Jul 25 11:17:23 2005 +0000
8.2 +++ b/lemon/max_matching.h Tue Jul 26 13:15:13 2005 +0000
8.3 @@ -97,32 +97,88 @@
8.4 ///Runs Edmonds' algorithm for sparse graphs (number of edges <
8.5 ///2*number of nodes), and a heuristical Edmonds' algorithm with a
8.6 ///heuristic of postponing shrinks for dense graphs.
8.7 - inline void run();
8.8 + void run() {
8.9 + if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
8.10 + greedyMatching();
8.11 + runEdmonds(0);
8.12 + } else runEdmonds(1);
8.13 + }
8.14 +
8.15
8.16 ///Runs Edmonds' algorithm.
8.17
8.18 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
8.19 ///Edmonds' algorithm with a heuristic of postponing shrinks,
8.20 ///giving a faster algorithm for dense graphs.
8.21 - void runEdmonds( int heur );
8.22 + void runEdmonds( int heur = 1 ) {
8.23 +
8.24 + for(NodeIt v(g); v!=INVALID; ++v)
8.25 + position.set(v,C);
8.26 +
8.27 + typename Graph::template NodeMap<Node> ear(g,INVALID);
8.28 + //undefined for the base nodes of the blossoms (i.e. for the
8.29 + //representative elements of UFE blossom) and for the nodes in C
8.30 +
8.31 + typename UFE::MapType blossom_base(g);
8.32 + UFE blossom(blossom_base);
8.33 + typename UFE::MapType tree_base(g);
8.34 + UFE tree(tree_base);
8.35 + //If these UFE's would be members of the class then also
8.36 + //blossom_base and tree_base should be a member.
8.37 +
8.38 + for(NodeIt v(g); v!=INVALID; ++v) {
8.39 + if ( position[v]==C && _mate[v]==INVALID ) {
8.40 + blossom.insert(v);
8.41 + tree.insert(v);
8.42 + position.set(v,D);
8.43 + if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
8.44 + else normShrink( v, ear, blossom, tree );
8.45 + }
8.46 + }
8.47 + }
8.48 +
8.49
8.50 ///Finds a greedy matching starting from the actual matching.
8.51
8.52 ///Starting form the actual matching stored, it finds a maximal
8.53 ///greedy matching.
8.54 - void greedyMatching();
8.55 + void greedyMatching() {
8.56 + for(NodeIt v(g); v!=INVALID; ++v)
8.57 + if ( _mate[v]==INVALID ) {
8.58 + for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
8.59 + Node y=g.runningNode(e);
8.60 + if ( _mate[y]==INVALID && y!=v ) {
8.61 + _mate.set(v,y);
8.62 + _mate.set(y,v);
8.63 + break;
8.64 + }
8.65 + }
8.66 + }
8.67 + }
8.68
8.69 ///Returns the size of the actual matching stored.
8.70
8.71 ///Returns the size of the actual matching stored. After \ref
8.72 ///run() it returns the size of a maximum matching in the graph.
8.73 - int size() const;
8.74 + int size() const {
8.75 + int s=0;
8.76 + for(NodeIt v(g); v!=INVALID; ++v) {
8.77 + if ( _mate[v]!=INVALID ) {
8.78 + ++s;
8.79 + }
8.80 + }
8.81 + return s/2;
8.82 + }
8.83 +
8.84
8.85 ///Resets the actual matching to the empty matching.
8.86
8.87 ///Resets the actual matching to the empty matching.
8.88 ///
8.89 - void resetMatching();
8.90 + void resetMatching() {
8.91 + for(NodeIt v(g); v!=INVALID; ++v)
8.92 + _mate.set(v,INVALID);
8.93 + }
8.94
8.95 ///Returns the mate of a node in the actual matching.
8.96
8.97 @@ -284,44 +340,6 @@
8.98
8.99
8.100 template <typename Graph>
8.101 - void MaxMatching<Graph>::run() {
8.102 - if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
8.103 - greedyMatching();
8.104 - runEdmonds(0);
8.105 - } else runEdmonds(1);
8.106 - }
8.107 -
8.108 -
8.109 - template <typename Graph>
8.110 - void MaxMatching<Graph>::runEdmonds( int heur=1 ) {
8.111 -
8.112 - for(NodeIt v(g); v!=INVALID; ++v)
8.113 - position.set(v,C);
8.114 -
8.115 - typename Graph::template NodeMap<Node> ear(g,INVALID);
8.116 - //undefined for the base nodes of the blossoms (i.e. for the
8.117 - //representative elements of UFE blossom) and for the nodes in C
8.118 -
8.119 - typename UFE::MapType blossom_base(g);
8.120 - UFE blossom(blossom_base);
8.121 - typename UFE::MapType tree_base(g);
8.122 - UFE tree(tree_base);
8.123 - //If these UFE's would be members of the class then also
8.124 - //blossom_base and tree_base should be a member.
8.125 -
8.126 - for(NodeIt v(g); v!=INVALID; ++v) {
8.127 - if ( position[v]==C && _mate[v]==INVALID ) {
8.128 - blossom.insert(v);
8.129 - tree.insert(v);
8.130 - position.set(v,D);
8.131 - if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
8.132 - else normShrink( v, ear, blossom, tree );
8.133 - }
8.134 - }
8.135 - }
8.136 -
8.137 -
8.138 - template <typename Graph>
8.139 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
8.140 UFE& blossom, UFE& tree) {
8.141
8.142 @@ -460,38 +478,6 @@
8.143 }
8.144
8.145 template <typename Graph>
8.146 - void MaxMatching<Graph>::greedyMatching() {
8.147 - for(NodeIt v(g); v!=INVALID; ++v)
8.148 - if ( _mate[v]==INVALID ) {
8.149 - for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
8.150 - Node y=g.runningNode(e);
8.151 - if ( _mate[y]==INVALID && y!=v ) {
8.152 - _mate.set(v,y);
8.153 - _mate.set(y,v);
8.154 - break;
8.155 - }
8.156 - }
8.157 - }
8.158 - }
8.159 -
8.160 - template <typename Graph>
8.161 - int MaxMatching<Graph>::size() const {
8.162 - int s=0;
8.163 - for(NodeIt v(g); v!=INVALID; ++v) {
8.164 - if ( _mate[v]!=INVALID ) {
8.165 - ++s;
8.166 - }
8.167 - }
8.168 - return s/2;
8.169 - }
8.170 -
8.171 - template <typename Graph>
8.172 - void MaxMatching<Graph>::resetMatching() {
8.173 - for(NodeIt v(g); v!=INVALID; ++v)
8.174 - _mate.set(v,INVALID);
8.175 - }
8.176 -
8.177 - template <typename Graph>
8.178 bool MaxMatching<Graph>::noShrinkStep(Node x,
8.179 typename Graph::template
8.180 NodeMap<Node>& ear,