↑ Collapse diff ↑
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_BFS_H
20 20
#define LEMON_BFS_H
21 21

	
22 22
///\ingroup search
23 23
///\file
24 24
///\brief BFS algorithm.
25 25

	
26 26
#include <lemon/list_graph.h>
27 27
#include <lemon/bits/path_dump.h>
28 28
#include <lemon/core.h>
29 29
#include <lemon/error.h>
30 30
#include <lemon/maps.h>
31 31
#include <lemon/path.h>
32 32

	
33 33
namespace lemon {
34 34

	
35 35
  ///Default traits class of Bfs class.
36 36

	
37 37
  ///Default traits class of Bfs class.
38 38
  ///\tparam GR Digraph type.
39 39
  template<class GR>
40 40
  struct BfsDefaultTraits
41 41
  {
42 42
    ///The type of the digraph the algorithm runs on.
43 43
    typedef GR Digraph;
44 44

	
45 45
    ///\brief The type of the map that stores the predecessor
46 46
    ///arcs of the shortest paths.
47 47
    ///
48 48
    ///The type of the map that stores the predecessor
49 49
    ///arcs of the shortest paths.
50 50
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
51 51
    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
52 52
    ///Instantiates a \ref PredMap.
53 53

	
54 54
    ///This function instantiates a \ref PredMap.
55 55
    ///\param g is the digraph, to which we would like to define the
56 56
    ///\ref PredMap.
57
    ///\todo The digraph alone may be insufficient to initialize
58 57
    static PredMap *createPredMap(const Digraph &g)
59 58
    {
60 59
      return new PredMap(g);
61 60
    }
62 61

	
63 62
    ///The type of the map that indicates which nodes are processed.
64 63

	
65 64
    ///The type of the map that indicates which nodes are processed.
66 65
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
67
    ///By default it is a NullMap.
68 66
    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
69 67
    ///Instantiates a \ref ProcessedMap.
70 68

	
71 69
    ///This function instantiates a \ref ProcessedMap.
72 70
    ///\param g is the digraph, to which
73 71
    ///we would like to define the \ref ProcessedMap
74 72
#ifdef DOXYGEN
75 73
    static ProcessedMap *createProcessedMap(const Digraph &g)
76 74
#else
77 75
    static ProcessedMap *createProcessedMap(const Digraph &)
78 76
#endif
79 77
    {
80 78
      return new ProcessedMap();
81 79
    }
82 80

	
83 81
    ///The type of the map that indicates which nodes are reached.
84 82

	
85 83
    ///The type of the map that indicates which nodes are reached.
86 84
    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
87 85
    typedef typename Digraph::template NodeMap<bool> ReachedMap;
88 86
    ///Instantiates a \ref ReachedMap.
89 87

	
90 88
    ///This function instantiates a \ref ReachedMap.
91 89
    ///\param g is the digraph, to which
92 90
    ///we would like to define the \ref ReachedMap.
93 91
    static ReachedMap *createReachedMap(const Digraph &g)
94 92
    {
95 93
      return new ReachedMap(g);
96 94
    }
97 95

	
98 96
    ///The type of the map that stores the distances of the nodes.
99 97

	
100 98
    ///The type of the map that stores the distances of the nodes.
101 99
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
102 100
    typedef typename Digraph::template NodeMap<int> DistMap;
103 101
    ///Instantiates a \ref DistMap.
104 102

	
105 103
    ///This function instantiates a \ref DistMap.
106 104
    ///\param g is the digraph, to which we would like to define the
107 105
    ///\ref DistMap.
108 106
    static DistMap *createDistMap(const Digraph &g)
109 107
    {
110 108
      return new DistMap(g);
111 109
    }
112 110
  };
113 111

	
114 112
  ///%BFS algorithm class.
115 113

	
116 114
  ///\ingroup search
117 115
  ///This class provides an efficient implementation of the %BFS algorithm.
118 116
  ///
119 117
  ///There is also a \ref bfs() "function-type interface" for the BFS
120 118
  ///algorithm, which is convenient in the simplier cases and it can be
121 119
  ///used easier.
122 120
  ///
123 121
  ///\tparam GR The type of the digraph the algorithm runs on.
124 122
  ///The default value is \ref ListDigraph. The value of GR is not used
125 123
  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
126 124
  ///\tparam TR Traits class to set various data types used by the algorithm.
127 125
  ///The default traits class is
128 126
  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
129 127
  ///See \ref BfsDefaultTraits for the documentation of
130 128
  ///a Bfs traits class.
131 129
#ifdef DOXYGEN
132 130
  template <typename GR,
133 131
            typename TR>
134 132
#else
135 133
  template <typename GR=ListDigraph,
136 134
            typename TR=BfsDefaultTraits<GR> >
137 135
#endif
138 136
  class Bfs {
139 137
  public:
140 138
    ///\ref Exception for uninitialized parameters.
141 139

	
142 140
    ///This error represents problems in the initialization of the
143 141
    ///parameters of the algorithm.
144 142
    class UninitializedParameter : public lemon::UninitializedParameter {
145 143
    public:
146 144
      virtual const char* what() const throw() {
147 145
        return "lemon::Bfs::UninitializedParameter";
148 146
      }
149 147
    };
150 148

	
151 149
    ///The type of the digraph the algorithm runs on.
152 150
    typedef typename TR::Digraph Digraph;
153 151

	
154 152
    ///\brief The type of the map that stores the predecessor arcs of the
155 153
    ///shortest paths.
156 154
    typedef typename TR::PredMap PredMap;
157 155
    ///The type of the map that stores the distances of the nodes.
158 156
    typedef typename TR::DistMap DistMap;
159 157
    ///The type of the map that indicates which nodes are reached.
160 158
    typedef typename TR::ReachedMap ReachedMap;
161 159
    ///The type of the map that indicates which nodes are processed.
162 160
    typedef typename TR::ProcessedMap ProcessedMap;
163 161
    ///The type of the paths.
164 162
    typedef PredMapPath<Digraph, PredMap> Path;
165 163

	
166 164
    ///The traits class.
167 165
    typedef TR Traits;
168 166

	
169 167
  private:
170 168

	
171 169
    typedef typename Digraph::Node Node;
172 170
    typedef typename Digraph::NodeIt NodeIt;
173 171
    typedef typename Digraph::Arc Arc;
174 172
    typedef typename Digraph::OutArcIt OutArcIt;
175 173

	
176 174
    //Pointer to the underlying digraph.
177 175
    const Digraph *G;
178 176
    //Pointer to the map of predecessor arcs.
179 177
    PredMap *_pred;
180 178
    //Indicates if _pred is locally allocated (true) or not.
181 179
    bool local_pred;
182 180
    //Pointer to the map of distances.
183 181
    DistMap *_dist;
184 182
    //Indicates if _dist is locally allocated (true) or not.
185 183
    bool local_dist;
186 184
    //Pointer to the map of reached status of the nodes.
187 185
    ReachedMap *_reached;
188 186
    //Indicates if _reached is locally allocated (true) or not.
189 187
    bool local_reached;
190 188
    //Pointer to the map of processed status of the nodes.
191 189
    ProcessedMap *_processed;
192 190
    //Indicates if _processed is locally allocated (true) or not.
193 191
    bool local_processed;
194 192

	
195 193
    std::vector<typename Digraph::Node> _queue;
196 194
    int _queue_head,_queue_tail,_queue_next_dist;
197 195
    int _curr_dist;
198 196

	
199
    ///Creates the maps if necessary.
200
    ///\todo Better memory allocation (instead of new).
197
    //Creates the maps if necessary.
201 198
    void create_maps()
202 199
    {
203 200
      if(!_pred) {
204 201
        local_pred = true;
205 202
        _pred = Traits::createPredMap(*G);
206 203
      }
207 204
      if(!_dist) {
208 205
        local_dist = true;
209 206
        _dist = Traits::createDistMap(*G);
210 207
      }
211 208
      if(!_reached) {
212 209
        local_reached = true;
213 210
        _reached = Traits::createReachedMap(*G);
214 211
      }
215 212
      if(!_processed) {
216 213
        local_processed = true;
217 214
        _processed = Traits::createProcessedMap(*G);
218 215
      }
219 216
    }
220 217

	
221 218
  protected:
222 219

	
223 220
    Bfs() {}
224 221

	
225 222
  public:
226 223

	
227 224
    typedef Bfs Create;
228 225

	
229 226
    ///\name Named template parameters
230 227

	
231 228
    ///@{
232 229

	
233 230
    template <class T>
234 231
    struct SetPredMapTraits : public Traits {
235 232
      typedef T PredMap;
236 233
      static PredMap *createPredMap(const Digraph &)
237 234
      {
238 235
        throw UninitializedParameter();
239 236
      }
240 237
    };
241 238
    ///\brief \ref named-templ-param "Named parameter" for setting
242 239
    ///\ref PredMap type.
243 240
    ///
244 241
    ///\ref named-templ-param "Named parameter" for setting
245 242
    ///\ref PredMap type.
246 243
    template <class T>
247 244
    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
248 245
      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
249 246
    };
250 247

	
251 248
    template <class T>
252 249
    struct SetDistMapTraits : public Traits {
253 250
      typedef T DistMap;
254 251
      static DistMap *createDistMap(const Digraph &)
255 252
      {
256 253
        throw UninitializedParameter();
257 254
      }
258 255
    };
259 256
    ///\brief \ref named-templ-param "Named parameter" for setting
260 257
    ///\ref DistMap type.
261 258
    ///
262 259
    ///\ref named-templ-param "Named parameter" for setting
263 260
    ///\ref DistMap type.
264 261
    template <class T>
265 262
    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
266 263
      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
267 264
    };
268 265

	
269 266
    template <class T>
270 267
    struct SetReachedMapTraits : public Traits {
271 268
      typedef T ReachedMap;
272 269
      static ReachedMap *createReachedMap(const Digraph &)
273 270
      {
274 271
        throw UninitializedParameter();
275 272
      }
276 273
    };
277 274
    ///\brief \ref named-templ-param "Named parameter" for setting
278 275
    ///\ref ReachedMap type.
279 276
    ///
280 277
    ///\ref named-templ-param "Named parameter" for setting
281 278
    ///\ref ReachedMap type.
282 279
    template <class T>
283 280
    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
284 281
      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
285 282
    };
286 283

	
287 284
    template <class T>
288 285
    struct SetProcessedMapTraits : public Traits {
289 286
      typedef T ProcessedMap;
290 287
      static ProcessedMap *createProcessedMap(const Digraph &)
291 288
      {
292 289
        throw UninitializedParameter();
293 290
      }
294 291
    };
295 292
    ///\brief \ref named-templ-param "Named parameter" for setting
296 293
    ///\ref ProcessedMap type.
297 294
    ///
298 295
    ///\ref named-templ-param "Named parameter" for setting
299 296
    ///\ref ProcessedMap type.
300 297
    template <class T>
301 298
    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
302 299
      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
303 300
    };
304 301

	
305 302
    struct SetStandardProcessedMapTraits : public Traits {
306 303
      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
307 304
      static ProcessedMap *createProcessedMap(const Digraph &g)
308 305
      {
309 306
        return new ProcessedMap(g);
310 307
      }
311 308
    };
312 309
    ///\brief \ref named-templ-param "Named parameter" for setting
313 310
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
314 311
    ///
315 312
    ///\ref named-templ-param "Named parameter" for setting
316 313
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
317 314
    ///If you don't set it explicitly, it will be automatically allocated.
318 315
    struct SetStandardProcessedMap :
319 316
      public Bfs< Digraph, SetStandardProcessedMapTraits > {
320 317
      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
321 318
    };
322 319

	
323 320
    ///@}
324 321

	
325 322
  public:
326 323

	
327 324
    ///Constructor.
328 325

	
... ...
@@ -723,257 +720,256 @@
723 720
    ///    if (!b.reached(n)) {
724 721
    ///      b.addSource(n);
725 722
    ///      b.start();
726 723
    ///    }
727 724
    ///  }
728 725
    ///\endcode
729 726
    void run() {
730 727
      init();
731 728
      for (NodeIt n(*G); n != INVALID; ++n) {
732 729
        if (!reached(n)) {
733 730
          addSource(n);
734 731
          start();
735 732
        }
736 733
      }
737 734
    }
738 735

	
739 736
    ///@}
740 737

	
741 738
    ///\name Query Functions
742 739
    ///The result of the %BFS algorithm can be obtained using these
743 740
    ///functions.\n
744 741
    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
745 742
    ///"start()" must be called before using them.
746 743

	
747 744
    ///@{
748 745

	
749 746
    ///The shortest path to a node.
750 747

	
751 748
    ///Returns the shortest path to a node.
752 749
    ///
753 750
    ///\warning \c t should be reachable from the root(s).
754 751
    ///
755 752
    ///\pre Either \ref run() or \ref start() must be called before
756 753
    ///using this function.
757 754
    Path path(Node t) const { return Path(*G, *_pred, t); }
758 755

	
759 756
    ///The distance of a node from the root(s).
760 757

	
761 758
    ///Returns the distance of a node from the root(s).
762 759
    ///
763 760
    ///\warning If node \c v is not reachable from the root(s), then
764 761
    ///the return value of this function is undefined.
765 762
    ///
766 763
    ///\pre Either \ref run() or \ref start() must be called before
767 764
    ///using this function.
768 765
    int dist(Node v) const { return (*_dist)[v]; }
769 766

	
770 767
    ///Returns the 'previous arc' of the shortest path tree for a node.
771 768

	
772 769
    ///This function returns the 'previous arc' of the shortest path
773 770
    ///tree for the node \c v, i.e. it returns the last arc of a
774 771
    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
775 772
    ///is not reachable from the root(s) or if \c v is a root.
776 773
    ///
777 774
    ///The shortest path tree used here is equal to the shortest path
778 775
    ///tree used in \ref predNode().
779 776
    ///
780 777
    ///\pre Either \ref run() or \ref start() must be called before
781 778
    ///using this function.
782 779
    Arc predArc(Node v) const { return (*_pred)[v];}
783 780

	
784 781
    ///Returns the 'previous node' of the shortest path tree for a node.
785 782

	
786 783
    ///This function returns the 'previous node' of the shortest path
787 784
    ///tree for the node \c v, i.e. it returns the last but one node
788 785
    ///from a shortest path from the root(s) to \c v. It is \c INVALID
789 786
    ///if \c v is not reachable from the root(s) or if \c v is a root.
790 787
    ///
791 788
    ///The shortest path tree used here is equal to the shortest path
792 789
    ///tree used in \ref predArc().
793 790
    ///
794 791
    ///\pre Either \ref run() or \ref start() must be called before
795 792
    ///using this function.
796 793
    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
797 794
                                  G->source((*_pred)[v]); }
798 795

	
799 796
    ///\brief Returns a const reference to the node map that stores the
800 797
    /// distances of the nodes.
801 798
    ///
802 799
    ///Returns a const reference to the node map that stores the distances
803 800
    ///of the nodes calculated by the algorithm.
804 801
    ///
805 802
    ///\pre Either \ref run() or \ref init()
806 803
    ///must be called before using this function.
807 804
    const DistMap &distMap() const { return *_dist;}
808 805

	
809 806
    ///\brief Returns a const reference to the node map that stores the
810 807
    ///predecessor arcs.
811 808
    ///
812 809
    ///Returns a const reference to the node map that stores the predecessor
813 810
    ///arcs, which form the shortest path tree.
814 811
    ///
815 812
    ///\pre Either \ref run() or \ref init()
816 813
    ///must be called before using this function.
817 814
    const PredMap &predMap() const { return *_pred;}
818 815

	
819 816
    ///Checks if a node is reachable from the root(s).
820 817

	
821 818
    ///Returns \c true if \c v is reachable from the root(s).
822 819
    ///\pre Either \ref run() or \ref start()
823 820
    ///must be called before using this function.
824 821
    bool reached(Node v) const { return (*_reached)[v]; }
825 822

	
826 823
    ///@}
827 824
  };
828 825

	
829 826
  ///Default traits class of bfs() function.
830 827

	
831 828
  ///Default traits class of bfs() function.
832 829
  ///\tparam GR Digraph type.
833 830
  template<class GR>
834 831
  struct BfsWizardDefaultTraits
835 832
  {
836 833
    ///The type of the digraph the algorithm runs on.
837 834
    typedef GR Digraph;
838 835

	
839 836
    ///\brief The type of the map that stores the predecessor
840 837
    ///arcs of the shortest paths.
841 838
    ///
842 839
    ///The type of the map that stores the predecessor
843 840
    ///arcs of the shortest paths.
844 841
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
845 842
    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
846 843
    ///Instantiates a \ref PredMap.
847 844

	
848 845
    ///This function instantiates a \ref PredMap.
849 846
    ///\param g is the digraph, to which we would like to define the
850 847
    ///\ref PredMap.
851
    ///\todo The digraph alone may be insufficient to initialize
852 848
    static PredMap *createPredMap(const Digraph &g)
853 849
    {
854 850
      return new PredMap(g);
855 851
    }
856 852

	
857 853
    ///The type of the map that indicates which nodes are processed.
858 854

	
859 855
    ///The type of the map that indicates which nodes are processed.
860 856
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
861 857
    ///By default it is a NullMap.
862 858
    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
863 859
    ///Instantiates a \ref ProcessedMap.
864 860

	
865 861
    ///This function instantiates a \ref ProcessedMap.
866 862
    ///\param g is the digraph, to which
867 863
    ///we would like to define the \ref ProcessedMap.
868 864
#ifdef DOXYGEN
869 865
    static ProcessedMap *createProcessedMap(const Digraph &g)
870 866
#else
871 867
    static ProcessedMap *createProcessedMap(const Digraph &)
872 868
#endif
873 869
    {
874 870
      return new ProcessedMap();
875 871
    }
876 872

	
877 873
    ///The type of the map that indicates which nodes are reached.
878 874

	
879 875
    ///The type of the map that indicates which nodes are reached.
880 876
    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
881 877
    typedef typename Digraph::template NodeMap<bool> ReachedMap;
882 878
    ///Instantiates a \ref ReachedMap.
883 879

	
884 880
    ///This function instantiates a \ref ReachedMap.
885 881
    ///\param g is the digraph, to which
886 882
    ///we would like to define the \ref ReachedMap.
887 883
    static ReachedMap *createReachedMap(const Digraph &g)
888 884
    {
889 885
      return new ReachedMap(g);
890 886
    }
891 887

	
892 888
    ///The type of the map that stores the distances of the nodes.
893 889

	
894 890
    ///The type of the map that stores the distances of the nodes.
895 891
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
896 892
    typedef typename Digraph::template NodeMap<int> DistMap;
897 893
    ///Instantiates a \ref DistMap.
898 894

	
899 895
    ///This function instantiates a \ref DistMap.
900 896
    ///\param g is the digraph, to which we would like to define
901 897
    ///the \ref DistMap
902 898
    static DistMap *createDistMap(const Digraph &g)
903 899
    {
904 900
      return new DistMap(g);
905 901
    }
906 902

	
907 903
    ///The type of the shortest paths.
908 904

	
909 905
    ///The type of the shortest paths.
910 906
    ///It must meet the \ref concepts::Path "Path" concept.
911 907
    typedef lemon::Path<Digraph> Path;
912 908
  };
913 909

	
914 910
  /// Default traits class used by \ref BfsWizard
915 911

	
916 912
  /// To make it easier to use Bfs algorithm
917 913
  /// we have created a wizard class.
918 914
  /// This \ref BfsWizard class needs default traits,
919 915
  /// as well as the \ref Bfs class.
920 916
  /// The \ref BfsWizardBase is a class to be the default traits of the
921 917
  /// \ref BfsWizard class.
922 918
  template<class GR>
923 919
  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
924 920
  {
925 921

	
926 922
    typedef BfsWizardDefaultTraits<GR> Base;
927 923
  protected:
928 924
    //The type of the nodes in the digraph.
929 925
    typedef typename Base::Digraph::Node Node;
930 926

	
931 927
    //Pointer to the digraph the algorithm runs on.
932 928
    void *_g;
933 929
    //Pointer to the map of reached nodes.
934 930
    void *_reached;
935 931
    //Pointer to the map of processed nodes.
936 932
    void *_processed;
937 933
    //Pointer to the map of predecessors arcs.
938 934
    void *_pred;
939 935
    //Pointer to the map of distances.
940 936
    void *_dist;
941 937
    //Pointer to the shortest path to the target node.
942 938
    void *_path;
943 939
    //Pointer to the distance of the target node.
944 940
    int *_di;
945 941

	
946 942
    public:
947 943
    /// Constructor.
948 944

	
949 945
    /// This constructor does not require parameters, therefore it initiates
950 946
    /// all of the attributes to \c 0.
951 947
    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
952 948
                      _dist(0), _path(0), _di(0) {}
953 949

	
954 950
    /// Constructor.
955 951

	
956 952
    /// This constructor requires one parameter,
957 953
    /// others are initiated to \c 0.
958 954
    /// \param g The digraph the algorithm runs on.
959 955
    BfsWizardBase(const GR &g) :
960 956
      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
961 957
      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
962 958

	
963 959
  };
964 960

	
965 961
  /// Auxiliary class for the function-type interface of BFS algorithm.
966 962

	
967 963
  /// This auxiliary class is created to implement the
968 964
  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
969 965
  /// It does not have own \ref run() method, it uses the functions
970 966
  /// and features of the plain \ref Bfs.
971 967
  ///
972 968
  /// This class should only be used through the \ref bfs() function,
973 969
  /// which makes it easier to use the algorithm.
974 970
  template<class TR>
975 971
  class BfsWizard : public TR
976 972
  {
977 973
    typedef TR Base;
978 974

	
979 975
    ///The type of the digraph the algorithm runs on.
... ...
@@ -1245,258 +1241,257 @@
1245 1241
    void discover(const Arc&) {}
1246 1242
    void examine(const Arc&) {}
1247 1243

	
1248 1244
    template <typename _Visitor>
1249 1245
    struct Constraints {
1250 1246
      void constraints() {
1251 1247
        Arc arc;
1252 1248
        Node node;
1253 1249
        visitor.start(node);
1254 1250
        visitor.reach(node);
1255 1251
        visitor.process(node);
1256 1252
        visitor.discover(arc);
1257 1253
        visitor.examine(arc);
1258 1254
      }
1259 1255
      _Visitor& visitor;
1260 1256
    };
1261 1257
  };
1262 1258
#endif
1263 1259

	
1264 1260
  /// \brief Default traits class of BfsVisit class.
1265 1261
  ///
1266 1262
  /// Default traits class of BfsVisit class.
1267 1263
  /// \tparam _Digraph The type of the digraph the algorithm runs on.
1268 1264
  template<class _Digraph>
1269 1265
  struct BfsVisitDefaultTraits {
1270 1266

	
1271 1267
    /// \brief The type of the digraph the algorithm runs on.
1272 1268
    typedef _Digraph Digraph;
1273 1269

	
1274 1270
    /// \brief The type of the map that indicates which nodes are reached.
1275 1271
    ///
1276 1272
    /// The type of the map that indicates which nodes are reached.
1277 1273
    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1278 1274
    typedef typename Digraph::template NodeMap<bool> ReachedMap;
1279 1275

	
1280 1276
    /// \brief Instantiates a \ref ReachedMap.
1281 1277
    ///
1282 1278
    /// This function instantiates a \ref ReachedMap.
1283 1279
    /// \param digraph is the digraph, to which
1284 1280
    /// we would like to define the \ref ReachedMap.
1285 1281
    static ReachedMap *createReachedMap(const Digraph &digraph) {
1286 1282
      return new ReachedMap(digraph);
1287 1283
    }
1288 1284

	
1289 1285
  };
1290 1286

	
1291 1287
  /// \ingroup search
1292 1288
  ///
1293 1289
  /// \brief %BFS algorithm class with visitor interface.
1294 1290
  ///
1295 1291
  /// This class provides an efficient implementation of the %BFS algorithm
1296 1292
  /// with visitor interface.
1297 1293
  ///
1298 1294
  /// The %BfsVisit class provides an alternative interface to the Bfs
1299 1295
  /// class. It works with callback mechanism, the BfsVisit object calls
1300 1296
  /// the member functions of the \c Visitor class on every BFS event.
1301 1297
  ///
1302 1298
  /// This interface of the BFS algorithm should be used in special cases
1303 1299
  /// when extra actions have to be performed in connection with certain
1304 1300
  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1305 1301
  /// instead.
1306 1302
  ///
1307 1303
  /// \tparam _Digraph The type of the digraph the algorithm runs on.
1308 1304
  /// The default value is
1309 1305
  /// \ref ListDigraph. The value of _Digraph is not used directly by
1310 1306
  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
1311 1307
  /// \tparam _Visitor The Visitor type that is used by the algorithm.
1312 1308
  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
1313 1309
  /// does not observe the BFS events. If you want to observe the BFS
1314 1310
  /// events, you should implement your own visitor class.
1315 1311
  /// \tparam _Traits Traits class to set various data types used by the
1316 1312
  /// algorithm. The default traits class is
1317 1313
  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1318 1314
  /// See \ref BfsVisitDefaultTraits for the documentation of
1319 1315
  /// a BFS visit traits class.
1320 1316
#ifdef DOXYGEN
1321 1317
  template <typename _Digraph, typename _Visitor, typename _Traits>
1322 1318
#else
1323 1319
  template <typename _Digraph = ListDigraph,
1324 1320
            typename _Visitor = BfsVisitor<_Digraph>,
1325 1321
            typename _Traits = BfsDefaultTraits<_Digraph> >
1326 1322
#endif
1327 1323
  class BfsVisit {
1328 1324
  public:
1329 1325

	
1330 1326
    /// \brief \ref Exception for uninitialized parameters.
1331 1327
    ///
1332 1328
    /// This error represents problems in the initialization
1333 1329
    /// of the parameters of the algorithm.
1334 1330
    class UninitializedParameter : public lemon::UninitializedParameter {
1335 1331
    public:
1336 1332
      virtual const char* what() const throw()
1337 1333
      {
1338 1334
        return "lemon::BfsVisit::UninitializedParameter";
1339 1335
      }
1340 1336
    };
1341 1337

	
1342 1338
    ///The traits class.
1343 1339
    typedef _Traits Traits;
1344 1340

	
1345 1341
    ///The type of the digraph the algorithm runs on.
1346 1342
    typedef typename Traits::Digraph Digraph;
1347 1343

	
1348 1344
    ///The visitor type used by the algorithm.
1349 1345
    typedef _Visitor Visitor;
1350 1346

	
1351 1347
    ///The type of the map that indicates which nodes are reached.
1352 1348
    typedef typename Traits::ReachedMap ReachedMap;
1353 1349

	
1354 1350
  private:
1355 1351

	
1356 1352
    typedef typename Digraph::Node Node;
1357 1353
    typedef typename Digraph::NodeIt NodeIt;
1358 1354
    typedef typename Digraph::Arc Arc;
1359 1355
    typedef typename Digraph::OutArcIt OutArcIt;
1360 1356

	
1361 1357
    //Pointer to the underlying digraph.
1362 1358
    const Digraph *_digraph;
1363 1359
    //Pointer to the visitor object.
1364 1360
    Visitor *_visitor;
1365 1361
    //Pointer to the map of reached status of the nodes.
1366 1362
    ReachedMap *_reached;
1367 1363
    //Indicates if _reached is locally allocated (true) or not.
1368 1364
    bool local_reached;
1369 1365

	
1370 1366
    std::vector<typename Digraph::Node> _list;
1371 1367
    int _list_front, _list_back;
1372 1368

	
1373
    ///Creates the maps if necessary.
1374
    ///\todo Better memory allocation (instead of new).
1369
    //Creates the maps if necessary.
1375 1370
    void create_maps() {
1376 1371
      if(!_reached) {
1377 1372
        local_reached = true;
1378 1373
        _reached = Traits::createReachedMap(*_digraph);
1379 1374
      }
1380 1375
    }
1381 1376

	
1382 1377
  protected:
1383 1378

	
1384 1379
    BfsVisit() {}
1385 1380

	
1386 1381
  public:
1387 1382

	
1388 1383
    typedef BfsVisit Create;
1389 1384

	
1390 1385
    /// \name Named template parameters
1391 1386

	
1392 1387
    ///@{
1393 1388
    template <class T>
1394 1389
    struct SetReachedMapTraits : public Traits {
1395 1390
      typedef T ReachedMap;
1396 1391
      static ReachedMap *createReachedMap(const Digraph &digraph) {
1397 1392
        throw UninitializedParameter();
1398 1393
      }
1399 1394
    };
1400 1395
    /// \brief \ref named-templ-param "Named parameter" for setting
1401 1396
    /// ReachedMap type.
1402 1397
    ///
1403 1398
    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1404 1399
    template <class T>
1405 1400
    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
1406 1401
                                            SetReachedMapTraits<T> > {
1407 1402
      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
1408 1403
    };
1409 1404
    ///@}
1410 1405

	
1411 1406
  public:
1412 1407

	
1413 1408
    /// \brief Constructor.
1414 1409
    ///
1415 1410
    /// Constructor.
1416 1411
    ///
1417 1412
    /// \param digraph The digraph the algorithm runs on.
1418 1413
    /// \param visitor The visitor object of the algorithm.
1419 1414
    BfsVisit(const Digraph& digraph, Visitor& visitor)
1420 1415
      : _digraph(&digraph), _visitor(&visitor),
1421 1416
        _reached(0), local_reached(false) {}
1422 1417

	
1423 1418
    /// \brief Destructor.
1424 1419
    ~BfsVisit() {
1425 1420
      if(local_reached) delete _reached;
1426 1421
    }
1427 1422

	
1428 1423
    /// \brief Sets the map that indicates which nodes are reached.
1429 1424
    ///
1430 1425
    /// Sets the map that indicates which nodes are reached.
1431 1426
    /// If you don't use this function before calling \ref run(),
1432 1427
    /// it will allocate one. The destructor deallocates this
1433 1428
    /// automatically allocated map, of course.
1434 1429
    /// \return <tt> (*this) </tt>
1435 1430
    BfsVisit &reachedMap(ReachedMap &m) {
1436 1431
      if(local_reached) {
1437 1432
        delete _reached;
1438 1433
        local_reached = false;
1439 1434
      }
1440 1435
      _reached = &m;
1441 1436
      return *this;
1442 1437
    }
1443 1438

	
1444 1439
  public:
1445 1440

	
1446 1441
    /// \name Execution control
1447 1442
    /// The simplest way to execute the algorithm is to use
1448 1443
    /// one of the member functions called \ref lemon::BfsVisit::run()
1449 1444
    /// "run()".
1450 1445
    /// \n
1451 1446
    /// If you need more control on the execution, first you must call
1452 1447
    /// \ref lemon::BfsVisit::init() "init()", then you can add several
1453 1448
    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
1454 1449
    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
1455 1450
    /// actual path computation.
1456 1451

	
1457 1452
    /// @{
1458 1453

	
1459 1454
    /// \brief Initializes the internal data structures.
1460 1455
    ///
1461 1456
    /// Initializes the internal data structures.
1462 1457
    void init() {
1463 1458
      create_maps();
1464 1459
      _list.resize(countNodes(*_digraph));
1465 1460
      _list_front = _list_back = -1;
1466 1461
      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1467 1462
        _reached->set(u, false);
1468 1463
      }
1469 1464
    }
1470 1465

	
1471 1466
    /// \brief Adds a new source node.
1472 1467
    ///
1473 1468
    /// Adds a new source node to the set of nodes to be processed.
1474 1469
    void addSource(Node s) {
1475 1470
      if(!(*_reached)[s]) {
1476 1471
          _reached->set(s,true);
1477 1472
          _visitor->start(s);
1478 1473
          _visitor->reach(s);
1479 1474
          _list[++_list_back] = s;
1480 1475
        }
1481 1476
    }
1482 1477

	
1483 1478
    /// \brief Processes the next node.
1484 1479
    ///
1485 1480
    /// Processes the next node.
1486 1481
    ///
1487 1482
    /// \return The processed node.
1488 1483
    ///
1489 1484
    /// \pre The queue must not be empty.
1490 1485
    Node processNextNode() {
1491 1486
      Node n = _list[++_list_front];
1492 1487
      _visitor->process(n);
1493 1488
      Arc e;
1494 1489
      for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1495 1490
        Node m = _digraph->target(e);
1496 1491
        if (!(*_reached)[m]) {
1497 1492
          _visitor->discover(e);
1498 1493
          _visitor->reach(m);
1499 1494
          _reached->set(m, true);
1500 1495
          _list[++_list_back] = m;
1501 1496
        } else {
1502 1497
          _visitor->examine(e);
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_BITS_BASE_EXTENDER_H
20 20
#define LEMON_BITS_BASE_EXTENDER_H
21 21

	
22 22
#include <lemon/core.h>
23 23
#include <lemon/error.h>
24 24

	
25 25
#include <lemon/bits/map_extender.h>
26 26
#include <lemon/bits/default_map.h>
27 27

	
28 28
#include <lemon/concept_check.h>
29 29
#include <lemon/concepts/maps.h>
30 30

	
31 31
///\ingroup digraphbits
32 32
///\file
33 33
///\brief Extenders for the digraph types
34 34
namespace lemon {
35 35

	
36 36
  /// \ingroup digraphbits
37 37
  ///
38 38
  /// \brief BaseDigraph to BaseGraph extender
39 39
  template <typename Base>
40 40
  class UndirDigraphExtender : public Base {
41 41

	
42 42
  public:
43 43

	
44 44
    typedef Base Parent;
45 45
    typedef typename Parent::Arc Edge;
46 46
    typedef typename Parent::Node Node;
47 47

	
48 48
    typedef True UndirectedTag;
49 49

	
50 50
    class Arc : public Edge {
51 51
      friend class UndirDigraphExtender;
52 52

	
53 53
    protected:
54 54
      bool forward;
55 55

	
56 56
      Arc(const Edge &ue, bool _forward) :
57 57
        Edge(ue), forward(_forward) {}
58 58

	
59 59
    public:
60 60
      Arc() {}
61 61

	
62 62
      // Invalid arc constructor
63 63
      Arc(Invalid i) : Edge(i), forward(true) {}
64 64

	
65 65
      bool operator==(const Arc &that) const {
66 66
        return forward==that.forward && Edge(*this)==Edge(that);
67 67
      }
68 68
      bool operator!=(const Arc &that) const {
69 69
        return forward!=that.forward || Edge(*this)!=Edge(that);
70 70
      }
71 71
      bool operator<(const Arc &that) const {
72 72
        return forward<that.forward ||
73 73
          (!(that.forward<forward) && Edge(*this)<Edge(that));
74 74
      }
75 75
    };
76 76

	
77 77
    /// First node of the edge
78 78
    Node u(const Edge &e) const {
79 79
      return Parent::source(e);
80 80
    }
81 81

	
82 82
    /// Source of the given arc
83 83
    Node source(const Arc &e) const {
84 84
      return e.forward ? Parent::source(e) : Parent::target(e);
85 85
    }
86 86

	
87 87
    /// Second node of the edge
88 88
    Node v(const Edge &e) const {
89 89
      return Parent::target(e);
90 90
    }
91 91

	
92 92
    /// Target of the given arc
93 93
    Node target(const Arc &e) const {
94 94
      return e.forward ? Parent::target(e) : Parent::source(e);
95 95
    }
96 96

	
97 97
    /// \brief Directed arc from an edge.
98 98
    ///
99 99
    /// Returns a directed arc corresponding to the specified edge.
100 100
    /// If the given bool is true, the first node of the given edge and
101 101
    /// the source node of the returned arc are the same.
102 102
    static Arc direct(const Edge &e, bool d) {
103 103
      return Arc(e, d);
104 104
    }
105 105

	
106 106
    /// Returns whether the given directed arc has the same orientation
107 107
    /// as the corresponding edge.
108
    ///
109
    /// \todo reference to the corresponding point of the undirected digraph
110
    /// concept. "What does the direction of an edge mean?"
111 108
    static bool direction(const Arc &a) { return a.forward; }
112 109

	
113 110
    using Parent::first;
114 111
    using Parent::next;
115 112

	
116 113
    void first(Arc &e) const {
117 114
      Parent::first(e);
118 115
      e.forward=true;
119 116
    }
120 117

	
121 118
    void next(Arc &e) const {
122 119
      if( e.forward ) {
123 120
        e.forward = false;
124 121
      }
125 122
      else {
126 123
        Parent::next(e);
127 124
        e.forward = true;
128 125
      }
129 126
    }
130 127

	
131 128
    void firstOut(Arc &e, const Node &n) const {
132 129
      Parent::firstIn(e,n);
133 130
      if( Edge(e) != INVALID ) {
134 131
        e.forward = false;
135 132
      }
136 133
      else {
137 134
        Parent::firstOut(e,n);
138 135
        e.forward = true;
139 136
      }
140 137
    }
141 138
    void nextOut(Arc &e) const {
142 139
      if( ! e.forward ) {
143 140
        Node n = Parent::target(e);
144 141
        Parent::nextIn(e);
145 142
        if( Edge(e) == INVALID ) {
146 143
          Parent::firstOut(e, n);
147 144
          e.forward = true;
148 145
        }
149 146
      }
150 147
      else {
151 148
        Parent::nextOut(e);
152 149
      }
153 150
    }
154 151

	
155 152
    void firstIn(Arc &e, const Node &n) const {
156 153
      Parent::firstOut(e,n);
157 154
      if( Edge(e) != INVALID ) {
158 155
        e.forward = false;
159 156
      }
160 157
      else {
161 158
        Parent::firstIn(e,n);
162 159
        e.forward = true;
163 160
      }
164 161
    }
165 162
    void nextIn(Arc &e) const {
166 163
      if( ! e.forward ) {
167 164
        Node n = Parent::source(e);
168 165
        Parent::nextOut(e);
169 166
        if( Edge(e) == INVALID ) {
170 167
          Parent::firstIn(e, n);
171 168
          e.forward = true;
172 169
        }
173 170
      }
174 171
      else {
175 172
        Parent::nextIn(e);
176 173
      }
177 174
    }
178 175

	
179 176
    void firstInc(Edge &e, bool &d, const Node &n) const {
180 177
      d = true;
181 178
      Parent::firstOut(e, n);
182 179
      if (e != INVALID) return;
183 180
      d = false;
184 181
      Parent::firstIn(e, n);
185 182
    }
186 183

	
187 184
    void nextInc(Edge &e, bool &d) const {
188 185
      if (d) {
189 186
        Node s = Parent::source(e);
190 187
        Parent::nextOut(e);
191 188
        if (e != INVALID) return;
192 189
        d = false;
193 190
        Parent::firstIn(e, s);
194 191
      } else {
195 192
        Parent::nextIn(e);
196 193
      }
197 194
    }
198 195

	
199 196
    Node nodeFromId(int ix) const {
200 197
      return Parent::nodeFromId(ix);
201 198
    }
202 199

	
203 200
    Arc arcFromId(int ix) const {
204 201
      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
205 202
    }
206 203

	
207 204
    Edge edgeFromId(int ix) const {
208 205
      return Parent::arcFromId(ix);
209 206
    }
210 207

	
211 208
    int id(const Node &n) const {
212 209
      return Parent::id(n);
213 210
    }
214 211

	
215 212
    int id(const Edge &e) const {
216 213
      return Parent::id(e);
217 214
    }
218 215

	
219 216
    int id(const Arc &e) const {
220 217
      return 2 * Parent::id(e) + int(e.forward);
221 218
    }
222 219

	
223 220
    int maxNodeId() const {
224 221
      return Parent::maxNodeId();
225 222
    }
226 223

	
227 224
    int maxArcId() const {
228 225
      return 2 * Parent::maxArcId() + 1;
229 226
    }
230 227

	
231 228
    int maxEdgeId() const {
232 229
      return Parent::maxArcId();
233 230
    }
234 231

	
235 232
    int arcNum() const {
236 233
      return 2 * Parent::arcNum();
237 234
    }
238 235

	
Ignore white space 256 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_BITS_VECTOR_MAP_H
20 20
#define LEMON_BITS_VECTOR_MAP_H
21 21

	
22 22
#include <vector>
23 23
#include <algorithm>
24 24

	
25 25
#include <lemon/core.h>
26 26
#include <lemon/bits/alteration_notifier.h>
27 27

	
28 28
#include <lemon/concept_check.h>
29 29
#include <lemon/concepts/maps.h>
30 30

	
31 31
///\ingroup graphbits
32 32
///
33 33
///\file
34 34
///\brief Vector based graph maps.
35 35
namespace lemon {
36 36

	
37 37
  /// \ingroup graphbits
38 38
  ///
39 39
  /// \brief Graph map based on the std::vector storage.
40 40
  ///
41 41
  /// The VectorMap template class is graph map structure what
42 42
  /// automatically updates the map when a key is added to or erased from
43 43
  /// the map. This map type uses the std::vector to store the values.
44 44
  ///
45
  /// \tparam _Notifier The AlterationNotifier that will notify this map.
45
  /// \tparam _Graph The graph this map is attached to.
46 46
  /// \tparam _Item The item type of the graph items.
47 47
  /// \tparam _Value The value type of the map.
48
  /// \todo Fix the doc: there is _Graph parameter instead of _Notifier.
49 48
  template <typename _Graph, typename _Item, typename _Value>
50 49
  class VectorMap
51 50
    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
52 51
  private:
53 52

	
54 53
    /// The container type of the map.
55 54
    typedef std::vector<_Value> Container;
56 55

	
57 56
  public:
58 57

	
59 58
    /// The graph type of the map.
60 59
    typedef _Graph Graph;
61 60
    /// The item type of the map.
62 61
    typedef _Item Item;
63 62
    /// The reference map tag.
64 63
    typedef True ReferenceMapTag;
65 64

	
66 65
    /// The key type of the map.
67 66
    typedef _Item Key;
68 67
    /// The value type of the map.
69 68
    typedef _Value Value;
70 69

	
71 70
    /// The notifier type.
72 71
    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
73 72

	
74 73
    /// The map type.
75 74
    typedef VectorMap Map;
76 75
    /// The base class of the map.
77 76
    typedef typename Notifier::ObserverBase Parent;
78 77

	
79 78
    /// The reference type of the map;
80 79
    typedef typename Container::reference Reference;
81 80
    /// The const reference type of the map;
82 81
    typedef typename Container::const_reference ConstReference;
83 82

	
84 83

	
85 84
    /// \brief Constructor to attach the new map into the notifier.
86 85
    ///
87 86
    /// It constructs a map and attachs it into the notifier.
88 87
    /// It adds all the items of the graph to the map.
89 88
    VectorMap(const Graph& graph) {
90 89
      Parent::attach(graph.notifier(Item()));
91 90
      container.resize(Parent::notifier()->maxId() + 1);
92 91
    }
93 92

	
94 93
    /// \brief Constructor uses given value to initialize the map.
95 94
    ///
96 95
    /// It constructs a map uses a given value to initialize the map.
97 96
    /// It adds all the items of the graph to the map.
98 97
    VectorMap(const Graph& graph, const Value& value) {
99 98
      Parent::attach(graph.notifier(Item()));
100 99
      container.resize(Parent::notifier()->maxId() + 1, value);
101 100
    }
102 101

	
103 102
  private:
104 103
    /// \brief Copy constructor
105 104
    ///
106 105
    /// Copy constructor.
107 106
    VectorMap(const VectorMap& _copy) : Parent() {
108 107
      if (_copy.attached()) {
109 108
        Parent::attach(*_copy.notifier());
110 109
        container = _copy.container;
111 110
      }
112 111
    }
113 112

	
114 113
    /// \brief Assign operator.
115 114
    ///
116 115
    /// This operator assigns for each item in the map the
117 116
    /// value mapped to the same item in the copied map.
118 117
    /// The parameter map should be indiced with the same
119 118
    /// itemset because this assign operator does not change
120 119
    /// the container of the map.
121 120
    VectorMap& operator=(const VectorMap& cmap) {
122 121
      return operator=<VectorMap>(cmap);
123 122
    }
124 123

	
125 124

	
126 125
    /// \brief Template assign operator.
127 126
    ///
128 127
    /// The given parameter should be conform to the ReadMap
129 128
    /// concecpt and could be indiced by the current item set of
130 129
    /// the NodeMap. In this case the value for each item
131 130
    /// is assigned by the value of the given ReadMap.
132 131
    template <typename CMap>
133 132
    VectorMap& operator=(const CMap& cmap) {
134 133
      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
135 134
      const typename Parent::Notifier* nf = Parent::notifier();
136 135
      Item it;
137 136
      for (nf->first(it); it != INVALID; nf->next(it)) {
138 137
        set(it, cmap[it]);
139 138
      }
140 139
      return *this;
141 140
    }
142 141

	
143 142
  public:
144 143

	
145 144
    /// \brief The subcript operator.
146 145
    ///
147 146
    /// The subscript operator. The map can be subscripted by the
148 147
    /// actual items of the graph.
149 148
    Reference operator[](const Key& key) {
150 149
      return container[Parent::notifier()->id(key)];
151 150
    }
152 151

	
153 152
    /// \brief The const subcript operator.
154 153
    ///
155 154
    /// The const subscript operator. The map can be subscripted by the
156 155
    /// actual items of the graph.
157 156
    ConstReference operator[](const Key& key) const {
158 157
      return container[Parent::notifier()->id(key)];
159 158
    }
160 159

	
161 160

	
162 161
    /// \brief The setter function of the map.
163 162
    ///
164 163
    /// It the same as operator[](key) = value expression.
165 164
    void set(const Key& key, const Value& value) {
166 165
      (*this)[key] = value;
167 166
    }
168 167

	
169 168
  protected:
170 169

	
171 170
    /// \brief Adds a new key to the map.
172 171
    ///
173 172
    /// It adds a new key to the map. It called by the observer notifier
174 173
    /// and it overrides the add() member function of the observer base.
175 174
    virtual void add(const Key& key) {
176 175
      int id = Parent::notifier()->id(key);
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
// This file contains a modified version of the concept checking
20 20
// utility from BOOST.
21 21
// See the appropriate copyright notice below.
22 22

	
23 23
// (C) Copyright Jeremy Siek 2000.
24 24
// Distributed under the Boost Software License, Version 1.0. (See
25 25
// accompanying file LICENSE_1_0.txt or copy at
26 26
// http://www.boost.org/LICENSE_1_0.txt)
27 27
//
28 28
// Revision History:
29 29
//   05 May   2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
30 30
//   02 April 2001: Removed limits header altogether. (Jeremy Siek)
31 31
//   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
32 32
//
33 33

	
34 34
// See http://www.boost.org/libs/concept_check for documentation.
35 35

	
36 36
///\file
37 37
///\brief Basic utilities for concept checking.
38 38
///
39
///\todo Are we still using BOOST concept checking utility?
40
///Is the BOOST copyright notice necessary?
41 39

	
42 40
#ifndef LEMON_CONCEPT_CHECK_H
43 41
#define LEMON_CONCEPT_CHECK_H
44 42

	
45 43
namespace lemon {
46 44

	
47 45
  /*
48 46
    "inline" is used for ignore_unused_variable_warning()
49 47
    and function_requires() to make sure there is no
50 48
    overtarget with g++.
51 49
  */
52 50

	
53 51
  template <class T> inline void ignore_unused_variable_warning(const T&) { }
54 52

	
55 53
  ///\e
56 54
  template <class Concept>
57 55
  inline void function_requires()
58 56
  {
59 57
#if !defined(NDEBUG)
60 58
    void (Concept::*x)() = & Concept::constraints;
61 59
    ignore_unused_variable_warning(x);
62 60
#endif
63 61
  }
64 62

	
65 63
  ///\e
66 64
  template <typename Concept, typename Type>
67 65
  inline void checkConcept() {
68 66
#if !defined(NDEBUG)
69 67
    typedef typename Concept::template Constraints<Type> ConceptCheck;
70 68
    void (ConceptCheck::*x)() = & ConceptCheck::constraints;
71 69
    ignore_unused_variable_warning(x);
72 70
#endif
73 71
  }
74 72

	
75 73
} // namespace lemon
76 74

	
77 75
#endif // LEMON_CONCEPT_CHECK_H
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
///\ingroup concept
20 20
///\file
21 21
///\brief Classes for representing paths in digraphs.
22 22
///
23
///\todo Iterators have obsolete style
24 23

	
25 24
#ifndef LEMON_CONCEPT_PATH_H
26 25
#define LEMON_CONCEPT_PATH_H
27 26

	
28 27
#include <lemon/core.h>
29 28
#include <lemon/concept_check.h>
30 29

	
31 30
namespace lemon {
32 31
  namespace concepts {
33 32

	
34 33
    /// \addtogroup concept
35 34
    /// @{
36 35

	
37 36
    /// \brief A skeleton structure for representing directed paths in
38 37
    /// a digraph.
39 38
    ///
40 39
    /// A skeleton structure for representing directed paths in a
41 40
    /// digraph.
42 41
    /// \tparam _Digraph The digraph type in which the path is.
43 42
    ///
44 43
    /// In a sense, the path can be treated as a list of arcs. The
45 44
    /// lemon path type stores just this list. As a consequence it
46 45
    /// cannot enumerate the nodes in the path and the zero length
47 46
    /// paths cannot store the source.
48 47
    ///
49 48
    template <typename _Digraph>
50 49
    class Path {
51 50
    public:
52 51

	
53 52
      /// Type of the underlying digraph.
54 53
      typedef _Digraph Digraph;
55 54
      /// Arc type of the underlying digraph.
56 55
      typedef typename Digraph::Arc Arc;
57 56

	
58 57
      class ArcIt;
59 58

	
60 59
      /// \brief Default constructor
61 60
      Path() {}
62 61

	
63 62
      /// \brief Template constructor
64 63
      template <typename CPath>
65 64
      Path(const CPath& cpath) {}
66 65

	
67 66
      /// \brief Template assigment
68 67
      template <typename CPath>
69 68
      Path& operator=(const CPath& cpath) {
70 69
        ignore_unused_variable_warning(cpath);
71 70
        return *this;
72 71
      }
73 72

	
74 73
      /// Length of the path ie. the number of arcs in the path.
75 74
      int length() const { return 0;}
76 75

	
77 76
      /// Returns whether the path is empty.
78 77
      bool empty() const { return true;}
79 78

	
80 79
      /// Resets the path to an empty path.
81 80
      void clear() {}
82 81

	
83 82
      /// \brief LEMON style iterator for path arcs
84 83
      ///
85 84
      /// This class is used to iterate on the arcs of the paths.
86 85
      class ArcIt {
87 86
      public:
88 87
        /// Default constructor
89 88
        ArcIt() {}
90 89
        /// Invalid constructor
91 90
        ArcIt(Invalid) {}
92 91
        /// Constructor for first arc
93 92
        ArcIt(const Path &) {}
94 93

	
95 94
        /// Conversion to Arc
96 95
        operator Arc() const { return INVALID; }
97 96

	
98 97
        /// Next arc
99 98
        ArcIt& operator++() {return *this;}
100 99

	
101 100
        /// Comparison operator
102 101
        bool operator==(const ArcIt&) const {return true;}
103 102
        /// Comparison operator
104 103
        bool operator!=(const ArcIt&) const {return true;}
105 104
        /// Comparison operator
106 105
        bool operator<(const ArcIt&) const {return false;}
107 106

	
108 107
      };
109 108

	
110 109
      template <typename _Path>
111 110
      struct Constraints {
112 111
        void constraints() {
113 112
          Path<Digraph> pc;
114 113
          _Path p, pp(pc);
115 114
          int l = p.length();
116 115
          int e = p.empty();
117 116
          p.clear();
118 117

	
119 118
          p = pc;
120 119

	
121 120
          typename _Path::ArcIt id, ii(INVALID), i(p);
122 121

	
123 122
          ++i;
124 123
          typename Digraph::Arc ed = i;
125 124

	
126 125
          e = (i == ii);
127 126
          e = (i != ii);
128 127
          e = (i < ii);
129 128

	
130 129
          ignore_unused_variable_warning(l);
131 130
          ignore_unused_variable_warning(pp);
132 131
          ignore_unused_variable_warning(e);
133 132
          ignore_unused_variable_warning(id);
134 133
          ignore_unused_variable_warning(ii);
135 134
          ignore_unused_variable_warning(ed);
136 135
        }
137 136
      };
138 137

	
139 138
    };
140 139

	
141 140
    namespace _path_bits {
142 141

	
143 142
      template <typename _Digraph, typename _Path, typename RevPathTag = void>
144 143
      struct PathDumperConstraints {
145 144
        void constraints() {
146 145
          int l = p.length();
147 146
          int e = p.empty();
148 147

	
149 148
          typename _Path::ArcIt id, i(p);
150 149

	
151 150
          ++i;
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_DFS_H
20 20
#define LEMON_DFS_H
21 21

	
22 22
///\ingroup search
23 23
///\file
24 24
///\brief DFS algorithm.
25 25

	
26 26
#include <lemon/list_graph.h>
27 27
#include <lemon/bits/path_dump.h>
28 28
#include <lemon/core.h>
29 29
#include <lemon/error.h>
30 30
#include <lemon/assert.h>
31 31
#include <lemon/maps.h>
32 32
#include <lemon/path.h>
33 33

	
34 34
namespace lemon {
35 35

	
36 36
  ///Default traits class of Dfs class.
37 37

	
38 38
  ///Default traits class of Dfs class.
39 39
  ///\tparam GR Digraph type.
40 40
  template<class GR>
41 41
  struct DfsDefaultTraits
42 42
  {
43 43
    ///The type of the digraph the algorithm runs on.
44 44
    typedef GR Digraph;
45 45

	
46 46
    ///\brief The type of the map that stores the predecessor
47 47
    ///arcs of the %DFS paths.
48 48
    ///
49 49
    ///The type of the map that stores the predecessor
50 50
    ///arcs of the %DFS paths.
51 51
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
52 52
    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
53 53
    ///Instantiates a \ref PredMap.
54 54

	
55 55
    ///This function instantiates a \ref PredMap.
56 56
    ///\param g is the digraph, to which we would like to define the
57 57
    ///\ref PredMap.
58
    ///\todo The digraph alone may be insufficient to initialize
59 58
    static PredMap *createPredMap(const Digraph &g)
60 59
    {
61 60
      return new PredMap(g);
62 61
    }
63 62

	
64 63
    ///The type of the map that indicates which nodes are processed.
65 64

	
66 65
    ///The type of the map that indicates which nodes are processed.
67 66
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
68
    ///By default it is a NullMap.
69 67
    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
70 68
    ///Instantiates a \ref ProcessedMap.
71 69

	
72 70
    ///This function instantiates a \ref ProcessedMap.
73 71
    ///\param g is the digraph, to which
74 72
    ///we would like to define the \ref ProcessedMap
75 73
#ifdef DOXYGEN
76 74
    static ProcessedMap *createProcessedMap(const Digraph &g)
77 75
#else
78 76
    static ProcessedMap *createProcessedMap(const Digraph &)
79 77
#endif
80 78
    {
81 79
      return new ProcessedMap();
82 80
    }
83 81

	
84 82
    ///The type of the map that indicates which nodes are reached.
85 83

	
86 84
    ///The type of the map that indicates which nodes are reached.
87 85
    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
88 86
    typedef typename Digraph::template NodeMap<bool> ReachedMap;
89 87
    ///Instantiates a \ref ReachedMap.
90 88

	
91 89
    ///This function instantiates a \ref ReachedMap.
92 90
    ///\param g is the digraph, to which
93 91
    ///we would like to define the \ref ReachedMap.
94 92
    static ReachedMap *createReachedMap(const Digraph &g)
95 93
    {
96 94
      return new ReachedMap(g);
97 95
    }
98 96

	
99 97
    ///The type of the map that stores the distances of the nodes.
100 98

	
101 99
    ///The type of the map that stores the distances of the nodes.
102 100
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
103 101
    typedef typename Digraph::template NodeMap<int> DistMap;
104 102
    ///Instantiates a \ref DistMap.
105 103

	
106 104
    ///This function instantiates a \ref DistMap.
107 105
    ///\param g is the digraph, to which we would like to define the
108 106
    ///\ref DistMap.
109 107
    static DistMap *createDistMap(const Digraph &g)
110 108
    {
111 109
      return new DistMap(g);
112 110
    }
113 111
  };
114 112

	
115 113
  ///%DFS algorithm class.
116 114

	
117 115
  ///\ingroup search
118 116
  ///This class provides an efficient implementation of the %DFS algorithm.
119 117
  ///
120 118
  ///There is also a \ref dfs() "function-type interface" for the DFS
121 119
  ///algorithm, which is convenient in the simplier cases and it can be
122 120
  ///used easier.
123 121
  ///
124 122
  ///\tparam GR The type of the digraph the algorithm runs on.
125 123
  ///The default value is \ref ListDigraph. The value of GR is not used
126 124
  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
127 125
  ///\tparam TR Traits class to set various data types used by the algorithm.
128 126
  ///The default traits class is
129 127
  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
130 128
  ///See \ref DfsDefaultTraits for the documentation of
131 129
  ///a Dfs traits class.
132 130
#ifdef DOXYGEN
133 131
  template <typename GR,
134 132
            typename TR>
135 133
#else
136 134
  template <typename GR=ListDigraph,
137 135
            typename TR=DfsDefaultTraits<GR> >
138 136
#endif
139 137
  class Dfs {
140 138
  public:
141 139
    ///\ref Exception for uninitialized parameters.
142 140

	
143 141
    ///This error represents problems in the initialization of the
144 142
    ///parameters of the algorithm.
145 143
    class UninitializedParameter : public lemon::UninitializedParameter {
146 144
    public:
147 145
      virtual const char* what() const throw() {
148 146
        return "lemon::Dfs::UninitializedParameter";
149 147
      }
150 148
    };
151 149

	
152 150
    ///The type of the digraph the algorithm runs on.
153 151
    typedef typename TR::Digraph Digraph;
154 152

	
155 153
    ///\brief The type of the map that stores the predecessor arcs of the
156 154
    ///DFS paths.
157 155
    typedef typename TR::PredMap PredMap;
158 156
    ///The type of the map that stores the distances of the nodes.
159 157
    typedef typename TR::DistMap DistMap;
160 158
    ///The type of the map that indicates which nodes are reached.
161 159
    typedef typename TR::ReachedMap ReachedMap;
162 160
    ///The type of the map that indicates which nodes are processed.
163 161
    typedef typename TR::ProcessedMap ProcessedMap;
164 162
    ///The type of the paths.
165 163
    typedef PredMapPath<Digraph, PredMap> Path;
166 164

	
167 165
    ///The traits class.
168 166
    typedef TR Traits;
169 167

	
170 168
  private:
171 169

	
172 170
    typedef typename Digraph::Node Node;
173 171
    typedef typename Digraph::NodeIt NodeIt;
174 172
    typedef typename Digraph::Arc Arc;
175 173
    typedef typename Digraph::OutArcIt OutArcIt;
176 174

	
177 175
    //Pointer to the underlying digraph.
178 176
    const Digraph *G;
179 177
    //Pointer to the map of predecessor arcs.
180 178
    PredMap *_pred;
181 179
    //Indicates if _pred is locally allocated (true) or not.
182 180
    bool local_pred;
183 181
    //Pointer to the map of distances.
184 182
    DistMap *_dist;
185 183
    //Indicates if _dist is locally allocated (true) or not.
186 184
    bool local_dist;
187 185
    //Pointer to the map of reached status of the nodes.
188 186
    ReachedMap *_reached;
189 187
    //Indicates if _reached is locally allocated (true) or not.
190 188
    bool local_reached;
191 189
    //Pointer to the map of processed status of the nodes.
192 190
    ProcessedMap *_processed;
193 191
    //Indicates if _processed is locally allocated (true) or not.
194 192
    bool local_processed;
195 193

	
196 194
    std::vector<typename Digraph::OutArcIt> _stack;
197 195
    int _stack_head;
198 196

	
199
    ///Creates the maps if necessary.
200
    ///\todo Better memory allocation (instead of new).
197
    //Creates the maps if necessary.
201 198
    void create_maps()
202 199
    {
203 200
      if(!_pred) {
204 201
        local_pred = true;
205 202
        _pred = Traits::createPredMap(*G);
206 203
      }
207 204
      if(!_dist) {
208 205
        local_dist = true;
209 206
        _dist = Traits::createDistMap(*G);
210 207
      }
211 208
      if(!_reached) {
212 209
        local_reached = true;
213 210
        _reached = Traits::createReachedMap(*G);
214 211
      }
215 212
      if(!_processed) {
216 213
        local_processed = true;
217 214
        _processed = Traits::createProcessedMap(*G);
218 215
      }
219 216
    }
220 217

	
221 218
  protected:
222 219

	
223 220
    Dfs() {}
224 221

	
225 222
  public:
226 223

	
227 224
    typedef Dfs Create;
228 225

	
229 226
    ///\name Named template parameters
230 227

	
231 228
    ///@{
232 229

	
233 230
    template <class T>
234 231
    struct SetPredMapTraits : public Traits {
235 232
      typedef T PredMap;
236 233
      static PredMap *createPredMap(const Digraph &)
237 234
      {
238 235
        throw UninitializedParameter();
239 236
      }
240 237
    };
241 238
    ///\brief \ref named-templ-param "Named parameter" for setting
242 239
    ///\ref PredMap type.
243 240
    ///
244 241
    ///\ref named-templ-param "Named parameter" for setting
245 242
    ///\ref PredMap type.
246 243
    template <class T>
247 244
    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
248 245
      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
249 246
    };
250 247

	
251 248
    template <class T>
252 249
    struct SetDistMapTraits : public Traits {
253 250
      typedef T DistMap;
254 251
      static DistMap *createDistMap(const Digraph &)
255 252
      {
256 253
        throw UninitializedParameter();
257 254
      }
258 255
    };
259 256
    ///\brief \ref named-templ-param "Named parameter" for setting
260 257
    ///\ref DistMap type.
261 258
    ///
262 259
    ///\ref named-templ-param "Named parameter" for setting
263 260
    ///\ref DistMap type.
264 261
    template <class T>
265 262
    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
266 263
      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
267 264
    };
268 265

	
269 266
    template <class T>
270 267
    struct SetReachedMapTraits : public Traits {
271 268
      typedef T ReachedMap;
272 269
      static ReachedMap *createReachedMap(const Digraph &)
273 270
      {
274 271
        throw UninitializedParameter();
275 272
      }
276 273
    };
277 274
    ///\brief \ref named-templ-param "Named parameter" for setting
278 275
    ///\ref ReachedMap type.
279 276
    ///
280 277
    ///\ref named-templ-param "Named parameter" for setting
281 278
    ///\ref ReachedMap type.
282 279
    template <class T>
283 280
    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
284 281
      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
285 282
    };
286 283

	
287 284
    template <class T>
288 285
    struct SetProcessedMapTraits : public Traits {
289 286
      typedef T ProcessedMap;
290 287
      static ProcessedMap *createProcessedMap(const Digraph &)
291 288
      {
292 289
        throw UninitializedParameter();
293 290
      }
294 291
    };
295 292
    ///\brief \ref named-templ-param "Named parameter" for setting
296 293
    ///\ref ProcessedMap type.
297 294
    ///
298 295
    ///\ref named-templ-param "Named parameter" for setting
299 296
    ///\ref ProcessedMap type.
300 297
    template <class T>
301 298
    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
302 299
      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
303 300
    };
304 301

	
305 302
    struct SetStandardProcessedMapTraits : public Traits {
306 303
      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
307 304
      static ProcessedMap *createProcessedMap(const Digraph &g)
308 305
      {
309 306
        return new ProcessedMap(g);
310 307
      }
311 308
    };
312 309
    ///\brief \ref named-templ-param "Named parameter" for setting
313 310
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
314 311
    ///
315 312
    ///\ref named-templ-param "Named parameter" for setting
316 313
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
317 314
    ///If you don't set it explicitly, it will be automatically allocated.
318 315
    struct SetStandardProcessedMap :
319 316
      public Dfs< Digraph, SetStandardProcessedMapTraits > {
320 317
      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
321 318
    };
322 319

	
323 320
    ///@}
324 321

	
325 322
  public:
326 323

	
327 324
    ///Constructor.
328 325

	
... ...
@@ -657,257 +654,256 @@
657 654
    ///    if (!d.reached(n)) {
658 655
    ///      d.addSource(n);
659 656
    ///      d.start();
660 657
    ///    }
661 658
    ///  }
662 659
    ///\endcode
663 660
    void run() {
664 661
      init();
665 662
      for (NodeIt it(*G); it != INVALID; ++it) {
666 663
        if (!reached(it)) {
667 664
          addSource(it);
668 665
          start();
669 666
        }
670 667
      }
671 668
    }
672 669

	
673 670
    ///@}
674 671

	
675 672
    ///\name Query Functions
676 673
    ///The result of the %DFS algorithm can be obtained using these
677 674
    ///functions.\n
678 675
    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
679 676
    ///"start()" must be called before using them.
680 677

	
681 678
    ///@{
682 679

	
683 680
    ///The DFS path to a node.
684 681

	
685 682
    ///Returns the DFS path to a node.
686 683
    ///
687 684
    ///\warning \c t should be reachable from the root.
688 685
    ///
689 686
    ///\pre Either \ref run() or \ref start() must be called before
690 687
    ///using this function.
691 688
    Path path(Node t) const { return Path(*G, *_pred, t); }
692 689

	
693 690
    ///The distance of a node from the root.
694 691

	
695 692
    ///Returns the distance of a node from the root.
696 693
    ///
697 694
    ///\warning If node \c v is not reachable from the root, then
698 695
    ///the return value of this function is undefined.
699 696
    ///
700 697
    ///\pre Either \ref run() or \ref start() must be called before
701 698
    ///using this function.
702 699
    int dist(Node v) const { return (*_dist)[v]; }
703 700

	
704 701
    ///Returns the 'previous arc' of the %DFS tree for a node.
705 702

	
706 703
    ///This function returns the 'previous arc' of the %DFS tree for the
707 704
    ///node \c v, i.e. it returns the last arc of a %DFS path from the
708 705
    ///root to \c v. It is \c INVALID
709 706
    ///if \c v is not reachable from the root(s) or if \c v is a root.
710 707
    ///
711 708
    ///The %DFS tree used here is equal to the %DFS tree used in
712 709
    ///\ref predNode().
713 710
    ///
714 711
    ///\pre Either \ref run() or \ref start() must be called before using
715 712
    ///this function.
716 713
    Arc predArc(Node v) const { return (*_pred)[v];}
717 714

	
718 715
    ///Returns the 'previous node' of the %DFS tree.
719 716

	
720 717
    ///This function returns the 'previous node' of the %DFS
721 718
    ///tree for the node \c v, i.e. it returns the last but one node
722 719
    ///from a %DFS path from the root to \c v. It is \c INVALID
723 720
    ///if \c v is not reachable from the root(s) or if \c v is a root.
724 721
    ///
725 722
    ///The %DFS tree used here is equal to the %DFS tree used in
726 723
    ///\ref predArc().
727 724
    ///
728 725
    ///\pre Either \ref run() or \ref start() must be called before
729 726
    ///using this function.
730 727
    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
731 728
                                  G->source((*_pred)[v]); }
732 729

	
733 730
    ///\brief Returns a const reference to the node map that stores the
734 731
    ///distances of the nodes.
735 732
    ///
736 733
    ///Returns a const reference to the node map that stores the
737 734
    ///distances of the nodes calculated by the algorithm.
738 735
    ///
739 736
    ///\pre Either \ref run() or \ref init()
740 737
    ///must be called before using this function.
741 738
    const DistMap &distMap() const { return *_dist;}
742 739

	
743 740
    ///\brief Returns a const reference to the node map that stores the
744 741
    ///predecessor arcs.
745 742
    ///
746 743
    ///Returns a const reference to the node map that stores the predecessor
747 744
    ///arcs, which form the DFS tree.
748 745
    ///
749 746
    ///\pre Either \ref run() or \ref init()
750 747
    ///must be called before using this function.
751 748
    const PredMap &predMap() const { return *_pred;}
752 749

	
753 750
    ///Checks if a node is reachable from the root(s).
754 751

	
755 752
    ///Returns \c true if \c v is reachable from the root(s).
756 753
    ///\pre Either \ref run() or \ref start()
757 754
    ///must be called before using this function.
758 755
    bool reached(Node v) const { return (*_reached)[v]; }
759 756

	
760 757
    ///@}
761 758
  };
762 759

	
763 760
  ///Default traits class of dfs() function.
764 761

	
765 762
  ///Default traits class of dfs() function.
766 763
  ///\tparam GR Digraph type.
767 764
  template<class GR>
768 765
  struct DfsWizardDefaultTraits
769 766
  {
770 767
    ///The type of the digraph the algorithm runs on.
771 768
    typedef GR Digraph;
772 769

	
773 770
    ///\brief The type of the map that stores the predecessor
774 771
    ///arcs of the %DFS paths.
775 772
    ///
776 773
    ///The type of the map that stores the predecessor
777 774
    ///arcs of the %DFS paths.
778 775
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
779 776
    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
780 777
    ///Instantiates a \ref PredMap.
781 778

	
782 779
    ///This function instantiates a \ref PredMap.
783 780
    ///\param g is the digraph, to which we would like to define the
784 781
    ///\ref PredMap.
785
    ///\todo The digraph alone may be insufficient to initialize
786 782
    static PredMap *createPredMap(const Digraph &g)
787 783
    {
788 784
      return new PredMap(g);
789 785
    }
790 786

	
791 787
    ///The type of the map that indicates which nodes are processed.
792 788

	
793 789
    ///The type of the map that indicates which nodes are processed.
794 790
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
795 791
    ///By default it is a NullMap.
796 792
    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
797 793
    ///Instantiates a \ref ProcessedMap.
798 794

	
799 795
    ///This function instantiates a \ref ProcessedMap.
800 796
    ///\param g is the digraph, to which
801 797
    ///we would like to define the \ref ProcessedMap.
802 798
#ifdef DOXYGEN
803 799
    static ProcessedMap *createProcessedMap(const Digraph &g)
804 800
#else
805 801
    static ProcessedMap *createProcessedMap(const Digraph &)
806 802
#endif
807 803
    {
808 804
      return new ProcessedMap();
809 805
    }
810 806

	
811 807
    ///The type of the map that indicates which nodes are reached.
812 808

	
813 809
    ///The type of the map that indicates which nodes are reached.
814 810
    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
815 811
    typedef typename Digraph::template NodeMap<bool> ReachedMap;
816 812
    ///Instantiates a \ref ReachedMap.
817 813

	
818 814
    ///This function instantiates a \ref ReachedMap.
819 815
    ///\param g is the digraph, to which
820 816
    ///we would like to define the \ref ReachedMap.
821 817
    static ReachedMap *createReachedMap(const Digraph &g)
822 818
    {
823 819
      return new ReachedMap(g);
824 820
    }
825 821

	
826 822
    ///The type of the map that stores the distances of the nodes.
827 823

	
828 824
    ///The type of the map that stores the distances of the nodes.
829 825
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
830 826
    typedef typename Digraph::template NodeMap<int> DistMap;
831 827
    ///Instantiates a \ref DistMap.
832 828

	
833 829
    ///This function instantiates a \ref DistMap.
834 830
    ///\param g is the digraph, to which we would like to define
835 831
    ///the \ref DistMap
836 832
    static DistMap *createDistMap(const Digraph &g)
837 833
    {
838 834
      return new DistMap(g);
839 835
    }
840 836

	
841 837
    ///The type of the DFS paths.
842 838

	
843 839
    ///The type of the DFS paths.
844 840
    ///It must meet the \ref concepts::Path "Path" concept.
845 841
    typedef lemon::Path<Digraph> Path;
846 842
  };
847 843

	
848 844
  /// Default traits class used by \ref DfsWizard
849 845

	
850 846
  /// To make it easier to use Dfs algorithm
851 847
  /// we have created a wizard class.
852 848
  /// This \ref DfsWizard class needs default traits,
853 849
  /// as well as the \ref Dfs class.
854 850
  /// The \ref DfsWizardBase is a class to be the default traits of the
855 851
  /// \ref DfsWizard class.
856 852
  template<class GR>
857 853
  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
858 854
  {
859 855

	
860 856
    typedef DfsWizardDefaultTraits<GR> Base;
861 857
  protected:
862 858
    //The type of the nodes in the digraph.
863 859
    typedef typename Base::Digraph::Node Node;
864 860

	
865 861
    //Pointer to the digraph the algorithm runs on.
866 862
    void *_g;
867 863
    //Pointer to the map of reached nodes.
868 864
    void *_reached;
869 865
    //Pointer to the map of processed nodes.
870 866
    void *_processed;
871 867
    //Pointer to the map of predecessors arcs.
872 868
    void *_pred;
873 869
    //Pointer to the map of distances.
874 870
    void *_dist;
875 871
    //Pointer to the DFS path to the target node.
876 872
    void *_path;
877 873
    //Pointer to the distance of the target node.
878 874
    int *_di;
879 875

	
880 876
    public:
881 877
    /// Constructor.
882 878

	
883 879
    /// This constructor does not require parameters, therefore it initiates
884 880
    /// all of the attributes to \c 0.
885 881
    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
886 882
                      _dist(0), _path(0), _di(0) {}
887 883

	
888 884
    /// Constructor.
889 885

	
890 886
    /// This constructor requires one parameter,
891 887
    /// others are initiated to \c 0.
892 888
    /// \param g The digraph the algorithm runs on.
893 889
    DfsWizardBase(const GR &g) :
894 890
      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
895 891
      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
896 892

	
897 893
  };
898 894

	
899 895
  /// Auxiliary class for the function-type interface of DFS algorithm.
900 896

	
901 897
  /// This auxiliary class is created to implement the
902 898
  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
903 899
  /// It does not have own \ref run() method, it uses the functions
904 900
  /// and features of the plain \ref Dfs.
905 901
  ///
906 902
  /// This class should only be used through the \ref dfs() function,
907 903
  /// which makes it easier to use the algorithm.
908 904
  template<class TR>
909 905
  class DfsWizard : public TR
910 906
  {
911 907
    typedef TR Base;
912 908

	
913 909
    ///The type of the digraph the algorithm runs on.
... ...
@@ -1192,258 +1188,257 @@
1192 1188

	
1193 1189
    template <typename _Visitor>
1194 1190
    struct Constraints {
1195 1191
      void constraints() {
1196 1192
        Arc arc;
1197 1193
        Node node;
1198 1194
        visitor.start(node);
1199 1195
        visitor.stop(arc);
1200 1196
        visitor.reach(node);
1201 1197
        visitor.discover(arc);
1202 1198
        visitor.examine(arc);
1203 1199
        visitor.leave(node);
1204 1200
        visitor.backtrack(arc);
1205 1201
      }
1206 1202
      _Visitor& visitor;
1207 1203
    };
1208 1204
  };
1209 1205
#endif
1210 1206

	
1211 1207
  /// \brief Default traits class of DfsVisit class.
1212 1208
  ///
1213 1209
  /// Default traits class of DfsVisit class.
1214 1210
  /// \tparam _Digraph The type of the digraph the algorithm runs on.
1215 1211
  template<class _Digraph>
1216 1212
  struct DfsVisitDefaultTraits {
1217 1213

	
1218 1214
    /// \brief The type of the digraph the algorithm runs on.
1219 1215
    typedef _Digraph Digraph;
1220 1216

	
1221 1217
    /// \brief The type of the map that indicates which nodes are reached.
1222 1218
    ///
1223 1219
    /// The type of the map that indicates which nodes are reached.
1224 1220
    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1225 1221
    typedef typename Digraph::template NodeMap<bool> ReachedMap;
1226 1222

	
1227 1223
    /// \brief Instantiates a \ref ReachedMap.
1228 1224
    ///
1229 1225
    /// This function instantiates a \ref ReachedMap.
1230 1226
    /// \param digraph is the digraph, to which
1231 1227
    /// we would like to define the \ref ReachedMap.
1232 1228
    static ReachedMap *createReachedMap(const Digraph &digraph) {
1233 1229
      return new ReachedMap(digraph);
1234 1230
    }
1235 1231

	
1236 1232
  };
1237 1233

	
1238 1234
  /// \ingroup search
1239 1235
  ///
1240 1236
  /// \brief %DFS algorithm class with visitor interface.
1241 1237
  ///
1242 1238
  /// This class provides an efficient implementation of the %DFS algorithm
1243 1239
  /// with visitor interface.
1244 1240
  ///
1245 1241
  /// The %DfsVisit class provides an alternative interface to the Dfs
1246 1242
  /// class. It works with callback mechanism, the DfsVisit object calls
1247 1243
  /// the member functions of the \c Visitor class on every DFS event.
1248 1244
  ///
1249 1245
  /// This interface of the DFS algorithm should be used in special cases
1250 1246
  /// when extra actions have to be performed in connection with certain
1251 1247
  /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
1252 1248
  /// instead.
1253 1249
  ///
1254 1250
  /// \tparam _Digraph The type of the digraph the algorithm runs on.
1255 1251
  /// The default value is
1256 1252
  /// \ref ListDigraph. The value of _Digraph is not used directly by
1257 1253
  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
1258 1254
  /// \tparam _Visitor The Visitor type that is used by the algorithm.
1259 1255
  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
1260 1256
  /// does not observe the DFS events. If you want to observe the DFS
1261 1257
  /// events, you should implement your own visitor class.
1262 1258
  /// \tparam _Traits Traits class to set various data types used by the
1263 1259
  /// algorithm. The default traits class is
1264 1260
  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1265 1261
  /// See \ref DfsVisitDefaultTraits for the documentation of
1266 1262
  /// a DFS visit traits class.
1267 1263
#ifdef DOXYGEN
1268 1264
  template <typename _Digraph, typename _Visitor, typename _Traits>
1269 1265
#else
1270 1266
  template <typename _Digraph = ListDigraph,
1271 1267
            typename _Visitor = DfsVisitor<_Digraph>,
1272 1268
            typename _Traits = DfsDefaultTraits<_Digraph> >
1273 1269
#endif
1274 1270
  class DfsVisit {
1275 1271
  public:
1276 1272

	
1277 1273
    /// \brief \ref Exception for uninitialized parameters.
1278 1274
    ///
1279 1275
    /// This error represents problems in the initialization
1280 1276
    /// of the parameters of the algorithm.
1281 1277
    class UninitializedParameter : public lemon::UninitializedParameter {
1282 1278
    public:
1283 1279
      virtual const char* what() const throw()
1284 1280
      {
1285 1281
        return "lemon::DfsVisit::UninitializedParameter";
1286 1282
      }
1287 1283
    };
1288 1284

	
1289 1285
    ///The traits class.
1290 1286
    typedef _Traits Traits;
1291 1287

	
1292 1288
    ///The type of the digraph the algorithm runs on.
1293 1289
    typedef typename Traits::Digraph Digraph;
1294 1290

	
1295 1291
    ///The visitor type used by the algorithm.
1296 1292
    typedef _Visitor Visitor;
1297 1293

	
1298 1294
    ///The type of the map that indicates which nodes are reached.
1299 1295
    typedef typename Traits::ReachedMap ReachedMap;
1300 1296

	
1301 1297
  private:
1302 1298

	
1303 1299
    typedef typename Digraph::Node Node;
1304 1300
    typedef typename Digraph::NodeIt NodeIt;
1305 1301
    typedef typename Digraph::Arc Arc;
1306 1302
    typedef typename Digraph::OutArcIt OutArcIt;
1307 1303

	
1308 1304
    //Pointer to the underlying digraph.
1309 1305
    const Digraph *_digraph;
1310 1306
    //Pointer to the visitor object.
1311 1307
    Visitor *_visitor;
1312 1308
    //Pointer to the map of reached status of the nodes.
1313 1309
    ReachedMap *_reached;
1314 1310
    //Indicates if _reached is locally allocated (true) or not.
1315 1311
    bool local_reached;
1316 1312

	
1317 1313
    std::vector<typename Digraph::Arc> _stack;
1318 1314
    int _stack_head;
1319 1315

	
1320
    ///Creates the maps if necessary.
1321
    ///\todo Better memory allocation (instead of new).
1316
    //Creates the maps if necessary.
1322 1317
    void create_maps() {
1323 1318
      if(!_reached) {
1324 1319
        local_reached = true;
1325 1320
        _reached = Traits::createReachedMap(*_digraph);
1326 1321
      }
1327 1322
    }
1328 1323

	
1329 1324
  protected:
1330 1325

	
1331 1326
    DfsVisit() {}
1332 1327

	
1333 1328
  public:
1334 1329

	
1335 1330
    typedef DfsVisit Create;
1336 1331

	
1337 1332
    /// \name Named template parameters
1338 1333

	
1339 1334
    ///@{
1340 1335
    template <class T>
1341 1336
    struct SetReachedMapTraits : public Traits {
1342 1337
      typedef T ReachedMap;
1343 1338
      static ReachedMap *createReachedMap(const Digraph &digraph) {
1344 1339
        throw UninitializedParameter();
1345 1340
      }
1346 1341
    };
1347 1342
    /// \brief \ref named-templ-param "Named parameter" for setting
1348 1343
    /// ReachedMap type.
1349 1344
    ///
1350 1345
    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1351 1346
    template <class T>
1352 1347
    struct SetReachedMap : public DfsVisit< Digraph, Visitor,
1353 1348
                                            SetReachedMapTraits<T> > {
1354 1349
      typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
1355 1350
    };
1356 1351
    ///@}
1357 1352

	
1358 1353
  public:
1359 1354

	
1360 1355
    /// \brief Constructor.
1361 1356
    ///
1362 1357
    /// Constructor.
1363 1358
    ///
1364 1359
    /// \param digraph The digraph the algorithm runs on.
1365 1360
    /// \param visitor The visitor object of the algorithm.
1366 1361
    DfsVisit(const Digraph& digraph, Visitor& visitor)
1367 1362
      : _digraph(&digraph), _visitor(&visitor),
1368 1363
        _reached(0), local_reached(false) {}
1369 1364

	
1370 1365
    /// \brief Destructor.
1371 1366
    ~DfsVisit() {
1372 1367
      if(local_reached) delete _reached;
1373 1368
    }
1374 1369

	
1375 1370
    /// \brief Sets the map that indicates which nodes are reached.
1376 1371
    ///
1377 1372
    /// Sets the map that indicates which nodes are reached.
1378 1373
    /// If you don't use this function before calling \ref run(),
1379 1374
    /// it will allocate one. The destructor deallocates this
1380 1375
    /// automatically allocated map, of course.
1381 1376
    /// \return <tt> (*this) </tt>
1382 1377
    DfsVisit &reachedMap(ReachedMap &m) {
1383 1378
      if(local_reached) {
1384 1379
        delete _reached;
1385 1380
        local_reached=false;
1386 1381
      }
1387 1382
      _reached = &m;
1388 1383
      return *this;
1389 1384
    }
1390 1385

	
1391 1386
  public:
1392 1387

	
1393 1388
    /// \name Execution control
1394 1389
    /// The simplest way to execute the algorithm is to use
1395 1390
    /// one of the member functions called \ref lemon::DfsVisit::run()
1396 1391
    /// "run()".
1397 1392
    /// \n
1398 1393
    /// If you need more control on the execution, first you must call
1399 1394
    /// \ref lemon::DfsVisit::init() "init()", then you can add several
1400 1395
    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
1401 1396
    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
1402 1397
    /// actual path computation.
1403 1398

	
1404 1399
    /// @{
1405 1400

	
1406 1401
    /// \brief Initializes the internal data structures.
1407 1402
    ///
1408 1403
    /// Initializes the internal data structures.
1409 1404
    void init() {
1410 1405
      create_maps();
1411 1406
      _stack.resize(countNodes(*_digraph));
1412 1407
      _stack_head = -1;
1413 1408
      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1414 1409
        _reached->set(u, false);
1415 1410
      }
1416 1411
    }
1417 1412

	
1418 1413
    ///Adds a new source node.
1419 1414

	
1420 1415
    ///Adds a new source node to the set of nodes to be processed.
1421 1416
    ///
1422 1417
    ///\pre The stack must be empty. (Otherwise the algorithm gives
1423 1418
    ///false results.)
1424 1419
    ///
1425 1420
    ///\warning Distances will be wrong (or at least strange) in case of
1426 1421
    ///multiple sources.
1427 1422
    void addSource(Node s)
1428 1423
    {
1429 1424
      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1430 1425
      if(!(*_reached)[s]) {
1431 1426
          _reached->set(s,true);
1432 1427
          _visitor->start(s);
1433 1428
          _visitor->reach(s);
1434 1429
          Arc e;
1435 1430
          _digraph->firstOut(e, s);
1436 1431
          if (e != INVALID) {
1437 1432
            _stack[++_stack_head] = e;
1438 1433
          } else {
1439 1434
            _visitor->leave(s);
1440 1435
          }
1441 1436
        }
1442 1437
    }
1443 1438

	
1444 1439
    /// \brief Processes the next arc.
1445 1440
    ///
1446 1441
    /// Processes the next arc.
1447 1442
    ///
1448 1443
    /// \return The processed arc.
1449 1444
    ///
Ignore white space 6 line context
... ...
@@ -19,411 +19,407 @@
19 19
#ifndef LEMON_DIJKSTRA_H
20 20
#define LEMON_DIJKSTRA_H
21 21

	
22 22
///\ingroup shortest_path
23 23
///\file
24 24
///\brief Dijkstra algorithm.
25 25

	
26 26
#include <limits>
27 27
#include <lemon/list_graph.h>
28 28
#include <lemon/bin_heap.h>
29 29
#include <lemon/bits/path_dump.h>
30 30
#include <lemon/core.h>
31 31
#include <lemon/error.h>
32 32
#include <lemon/maps.h>
33 33
#include <lemon/path.h>
34 34

	
35 35
namespace lemon {
36 36

	
37 37
  /// \brief Default operation traits for the Dijkstra algorithm class.
38 38
  ///
39 39
  /// This operation traits class defines all computational operations and
40 40
  /// constants which are used in the Dijkstra algorithm.
41 41
  template <typename Value>
42 42
  struct DijkstraDefaultOperationTraits {
43 43
    /// \brief Gives back the zero value of the type.
44 44
    static Value zero() {
45 45
      return static_cast<Value>(0);
46 46
    }
47 47
    /// \brief Gives back the sum of the given two elements.
48 48
    static Value plus(const Value& left, const Value& right) {
49 49
      return left + right;
50 50
    }
51 51
    /// \brief Gives back true only if the first value is less than the second.
52 52
    static bool less(const Value& left, const Value& right) {
53 53
      return left < right;
54 54
    }
55 55
  };
56 56

	
57 57
  /// \brief Widest path operation traits for the Dijkstra algorithm class.
58 58
  ///
59 59
  /// This operation traits class defines all computational operations and
60 60
  /// constants which are used in the Dijkstra algorithm for widest path
61 61
  /// computation.
62 62
  ///
63 63
  /// \see DijkstraDefaultOperationTraits
64 64
  template <typename Value>
65 65
  struct DijkstraWidestPathOperationTraits {
66 66
    /// \brief Gives back the maximum value of the type.
67 67
    static Value zero() {
68 68
      return std::numeric_limits<Value>::max();
69 69
    }
70 70
    /// \brief Gives back the minimum of the given two elements.
71 71
    static Value plus(const Value& left, const Value& right) {
72 72
      return std::min(left, right);
73 73
    }
74 74
    /// \brief Gives back true only if the first value is less than the second.
75 75
    static bool less(const Value& left, const Value& right) {
76 76
      return left < right;
77 77
    }
78 78
  };
79 79

	
80 80
  ///Default traits class of Dijkstra class.
81 81

	
82 82
  ///Default traits class of Dijkstra class.
83 83
  ///\tparam GR The type of the digraph.
84 84
  ///\tparam LM The type of the length map.
85 85
  template<class GR, class LM>
86 86
  struct DijkstraDefaultTraits
87 87
  {
88 88
    ///The type of the digraph the algorithm runs on.
89 89
    typedef GR Digraph;
90 90

	
91 91
    ///The type of the map that stores the arc lengths.
92 92

	
93 93
    ///The type of the map that stores the arc lengths.
94 94
    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
95 95
    typedef LM LengthMap;
96 96
    ///The type of the length of the arcs.
97 97
    typedef typename LM::Value Value;
98 98

	
99 99
    /// Operation traits for Dijkstra algorithm.
100 100

	
101 101
    /// This class defines the operations that are used in the algorithm.
102 102
    /// \see DijkstraDefaultOperationTraits
103 103
    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
104 104

	
105 105
    /// The cross reference type used by the heap.
106 106

	
107 107
    /// The cross reference type used by the heap.
108 108
    /// Usually it is \c Digraph::NodeMap<int>.
109 109
    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
110 110
    ///Instantiates a \ref HeapCrossRef.
111 111

	
112 112
    ///This function instantiates a \ref HeapCrossRef.
113 113
    /// \param g is the digraph, to which we would like to define the
114 114
    /// \ref HeapCrossRef.
115 115
    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
116 116
    {
117 117
      return new HeapCrossRef(g);
118 118
    }
119 119

	
120 120
    ///The heap type used by the Dijkstra algorithm.
121 121

	
122 122
    ///The heap type used by the Dijkstra algorithm.
123 123
    ///
124 124
    ///\sa BinHeap
125 125
    ///\sa Dijkstra
126 126
    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
127 127
    ///Instantiates a \ref Heap.
128 128

	
129 129
    ///This function instantiates a \ref Heap.
130 130
    static Heap *createHeap(HeapCrossRef& r)
131 131
    {
132 132
      return new Heap(r);
133 133
    }
134 134

	
135 135
    ///\brief The type of the map that stores the predecessor
136 136
    ///arcs of the shortest paths.
137 137
    ///
138 138
    ///The type of the map that stores the predecessor
139 139
    ///arcs of the shortest paths.
140 140
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
141 141
    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
142 142
    ///Instantiates a \ref PredMap.
143 143

	
144 144
    ///This function instantiates a \ref PredMap.
145 145
    ///\param g is the digraph, to which we would like to define the
146 146
    ///\ref PredMap.
147
    ///\todo The digraph alone may be insufficient for the initialization
148 147
    static PredMap *createPredMap(const Digraph &g)
149 148
    {
150 149
      return new PredMap(g);
151 150
    }
152 151

	
153 152
    ///The type of the map that indicates which nodes are processed.
154 153

	
155 154
    ///The type of the map that indicates which nodes are processed.
156 155
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
157 156
    ///By default it is a NullMap.
158
    ///\todo If it is set to a real map,
159
    ///Dijkstra::processed() should read this.
160 157
    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
161 158
    ///Instantiates a \ref ProcessedMap.
162 159

	
163 160
    ///This function instantiates a \ref ProcessedMap.
164 161
    ///\param g is the digraph, to which
165 162
    ///we would like to define the \ref ProcessedMap
166 163
#ifdef DOXYGEN
167 164
    static ProcessedMap *createProcessedMap(const Digraph &g)
168 165
#else
169 166
    static ProcessedMap *createProcessedMap(const Digraph &)
170 167
#endif
171 168
    {
172 169
      return new ProcessedMap();
173 170
    }
174 171

	
175 172
    ///The type of the map that stores the distances of the nodes.
176 173

	
177 174
    ///The type of the map that stores the distances of the nodes.
178 175
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
179 176
    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
180 177
    ///Instantiates a \ref DistMap.
181 178

	
182 179
    ///This function instantiates a \ref DistMap.
183 180
    ///\param g is the digraph, to which we would like to define
184 181
    ///the \ref DistMap
185 182
    static DistMap *createDistMap(const Digraph &g)
186 183
    {
187 184
      return new DistMap(g);
188 185
    }
189 186
  };
190 187

	
191 188
  ///%Dijkstra algorithm class.
192 189

	
193 190
  /// \ingroup shortest_path
194 191
  ///This class provides an efficient implementation of the %Dijkstra algorithm.
195 192
  ///
196 193
  ///The arc lengths are passed to the algorithm using a
197 194
  ///\ref concepts::ReadMap "ReadMap",
198 195
  ///so it is easy to change it to any kind of length.
199 196
  ///The type of the length is determined by the
200 197
  ///\ref concepts::ReadMap::Value "Value" of the length map.
201 198
  ///It is also possible to change the underlying priority heap.
202 199
  ///
203 200
  ///There is also a \ref dijkstra() "function-type interface" for the
204 201
  ///%Dijkstra algorithm, which is convenient in the simplier cases and
205 202
  ///it can be used easier.
206 203
  ///
207 204
  ///\tparam GR The type of the digraph the algorithm runs on.
208 205
  ///The default value is \ref ListDigraph.
209 206
  ///The value of GR is not used directly by \ref Dijkstra, it is only
210 207
  ///passed to \ref DijkstraDefaultTraits.
211 208
  ///\tparam LM A readable arc map that determines the lengths of the
212 209
  ///arcs. It is read once for each arc, so the map may involve in
213 210
  ///relatively time consuming process to compute the arc lengths if
214 211
  ///it is necessary. The default map type is \ref
215 212
  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
216 213
  ///The value of LM is not used directly by \ref Dijkstra, it is only
217 214
  ///passed to \ref DijkstraDefaultTraits.
218 215
  ///\tparam TR Traits class to set various data types used by the algorithm.
219 216
  ///The default traits class is \ref DijkstraDefaultTraits
220 217
  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
221 218
  ///for the documentation of a Dijkstra traits class.
222 219
#ifdef DOXYGEN
223 220
  template <typename GR, typename LM, typename TR>
224 221
#else
225 222
  template <typename GR=ListDigraph,
226 223
            typename LM=typename GR::template ArcMap<int>,
227 224
            typename TR=DijkstraDefaultTraits<GR,LM> >
228 225
#endif
229 226
  class Dijkstra {
230 227
  public:
231 228
    ///\ref Exception for uninitialized parameters.
232 229

	
233 230
    ///This error represents problems in the initialization of the
234 231
    ///parameters of the algorithm.
235 232
    class UninitializedParameter : public lemon::UninitializedParameter {
236 233
    public:
237 234
      virtual const char* what() const throw() {
238 235
        return "lemon::Dijkstra::UninitializedParameter";
239 236
      }
240 237
    };
241 238

	
242 239
    ///The type of the digraph the algorithm runs on.
243 240
    typedef typename TR::Digraph Digraph;
244 241

	
245 242
    ///The type of the length of the arcs.
246 243
    typedef typename TR::LengthMap::Value Value;
247 244
    ///The type of the map that stores the arc lengths.
248 245
    typedef typename TR::LengthMap LengthMap;
249 246
    ///\brief The type of the map that stores the predecessor arcs of the
250 247
    ///shortest paths.
251 248
    typedef typename TR::PredMap PredMap;
252 249
    ///The type of the map that stores the distances of the nodes.
253 250
    typedef typename TR::DistMap DistMap;
254 251
    ///The type of the map that indicates which nodes are processed.
255 252
    typedef typename TR::ProcessedMap ProcessedMap;
256 253
    ///The type of the paths.
257 254
    typedef PredMapPath<Digraph, PredMap> Path;
258 255
    ///The cross reference type used for the current heap.
259 256
    typedef typename TR::HeapCrossRef HeapCrossRef;
260 257
    ///The heap type used by the algorithm.
261 258
    typedef typename TR::Heap Heap;
262 259
    ///The operation traits class.
263 260
    typedef typename TR::OperationTraits OperationTraits;
264 261

	
265 262
    ///The traits class.
266 263
    typedef TR Traits;
267 264

	
268 265
  private:
269 266

	
270 267
    typedef typename Digraph::Node Node;
271 268
    typedef typename Digraph::NodeIt NodeIt;
272 269
    typedef typename Digraph::Arc Arc;
273 270
    typedef typename Digraph::OutArcIt OutArcIt;
274 271

	
275 272
    //Pointer to the underlying digraph.
276 273
    const Digraph *G;
277 274
    //Pointer to the length map.
278 275
    const LengthMap *length;
279 276
    //Pointer to the map of predecessors arcs.
280 277
    PredMap *_pred;
281 278
    //Indicates if _pred is locally allocated (true) or not.
282 279
    bool local_pred;
283 280
    //Pointer to the map of distances.
284 281
    DistMap *_dist;
285 282
    //Indicates if _dist is locally allocated (true) or not.
286 283
    bool local_dist;
287 284
    //Pointer to the map of processed status of the nodes.
288 285
    ProcessedMap *_processed;
289 286
    //Indicates if _processed is locally allocated (true) or not.
290 287
    bool local_processed;
291 288
    //Pointer to the heap cross references.
292 289
    HeapCrossRef *_heap_cross_ref;
293 290
    //Indicates if _heap_cross_ref is locally allocated (true) or not.
294 291
    bool local_heap_cross_ref;
295 292
    //Pointer to the heap.
296 293
    Heap *_heap;
297 294
    //Indicates if _heap is locally allocated (true) or not.
298 295
    bool local_heap;
299 296

	
300
    ///Creates the maps if necessary.
301
    ///\todo Better memory allocation (instead of new).
297
    //Creates the maps if necessary.
302 298
    void create_maps()
303 299
    {
304 300
      if(!_pred) {
305 301
        local_pred = true;
306 302
        _pred = Traits::createPredMap(*G);
307 303
      }
308 304
      if(!_dist) {
309 305
        local_dist = true;
310 306
        _dist = Traits::createDistMap(*G);
311 307
      }
312 308
      if(!_processed) {
313 309
        local_processed = true;
314 310
        _processed = Traits::createProcessedMap(*G);
315 311
      }
316 312
      if (!_heap_cross_ref) {
317 313
        local_heap_cross_ref = true;
318 314
        _heap_cross_ref = Traits::createHeapCrossRef(*G);
319 315
      }
320 316
      if (!_heap) {
321 317
        local_heap = true;
322 318
        _heap = Traits::createHeap(*_heap_cross_ref);
323 319
      }
324 320
    }
325 321

	
326 322
  public:
327 323

	
328 324
    typedef Dijkstra Create;
329 325

	
330 326
    ///\name Named template parameters
331 327

	
332 328
    ///@{
333 329

	
334 330
    template <class T>
335 331
    struct SetPredMapTraits : public Traits {
336 332
      typedef T PredMap;
337 333
      static PredMap *createPredMap(const Digraph &)
338 334
      {
339 335
        throw UninitializedParameter();
340 336
      }
341 337
    };
342 338
    ///\brief \ref named-templ-param "Named parameter" for setting
343 339
    ///\ref PredMap type.
344 340
    ///
345 341
    ///\ref named-templ-param "Named parameter" for setting
346 342
    ///\ref PredMap type.
347 343
    template <class T>
348 344
    struct SetPredMap
349 345
      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
350 346
      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
351 347
    };
352 348

	
353 349
    template <class T>
354 350
    struct SetDistMapTraits : public Traits {
355 351
      typedef T DistMap;
356 352
      static DistMap *createDistMap(const Digraph &)
357 353
      {
358 354
        throw UninitializedParameter();
359 355
      }
360 356
    };
361 357
    ///\brief \ref named-templ-param "Named parameter" for setting
362 358
    ///\ref DistMap type.
363 359
    ///
364 360
    ///\ref named-templ-param "Named parameter" for setting
365 361
    ///\ref DistMap type.
366 362
    template <class T>
367 363
    struct SetDistMap
368 364
      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
369 365
      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
370 366
    };
371 367

	
372 368
    template <class T>
373 369
    struct SetProcessedMapTraits : public Traits {
374 370
      typedef T ProcessedMap;
375 371
      static ProcessedMap *createProcessedMap(const Digraph &)
376 372
      {
377 373
        throw UninitializedParameter();
378 374
      }
379 375
    };
380 376
    ///\brief \ref named-templ-param "Named parameter" for setting
381 377
    ///\ref ProcessedMap type.
382 378
    ///
383 379
    ///\ref named-templ-param "Named parameter" for setting
384 380
    ///\ref ProcessedMap type.
385 381
    template <class T>
386 382
    struct SetProcessedMap
387 383
      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
388 384
      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
389 385
    };
390 386

	
391 387
    struct SetStandardProcessedMapTraits : public Traits {
392 388
      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
393 389
      static ProcessedMap *createProcessedMap(const Digraph &g)
394 390
      {
395 391
        return new ProcessedMap(g);
396 392
      }
397 393
    };
398 394
    ///\brief \ref named-templ-param "Named parameter" for setting
399 395
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
400 396
    ///
401 397
    ///\ref named-templ-param "Named parameter" for setting
402 398
    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
403 399
    ///If you don't set it explicitly, it will be automatically allocated.
404 400
    struct SetStandardProcessedMap
405 401
      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
406 402
      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
407 403
      Create;
408 404
    };
409 405

	
410 406
    template <class H, class CR>
411 407
    struct SetHeapTraits : public Traits {
412 408
      typedef CR HeapCrossRef;
413 409
      typedef H Heap;
414 410
      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
415 411
        throw UninitializedParameter();
416 412
      }
417 413
      static Heap *createHeap(HeapCrossRef &)
418 414
      {
419 415
        throw UninitializedParameter();
420 416
      }
421 417
    };
422 418
    ///\brief \ref named-templ-param "Named parameter" for setting
423 419
    ///heap and cross reference type
424 420
    ///
425 421
    ///\ref named-templ-param "Named parameter" for setting heap and cross
426 422
    ///reference type.
427 423
    template <class H, class CR = typename Digraph::template NodeMap<int> >
428 424
    struct SetHeap
429 425
      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
... ...
@@ -833,352 +829,346 @@
833 829
    ///\warning \c t should be reachable from the root(s).
834 830
    ///
835 831
    ///\pre Either \ref run() or \ref start() must be called before
836 832
    ///using this function.
837 833
    Path path(Node t) const { return Path(*G, *_pred, t); }
838 834

	
839 835
    ///The distance of a node from the root(s).
840 836

	
841 837
    ///Returns the distance of a node from the root(s).
842 838
    ///
843 839
    ///\warning If node \c v is not reachable from the root(s), then
844 840
    ///the return value of this function is undefined.
845 841
    ///
846 842
    ///\pre Either \ref run() or \ref start() must be called before
847 843
    ///using this function.
848 844
    Value dist(Node v) const { return (*_dist)[v]; }
849 845

	
850 846
    ///Returns the 'previous arc' of the shortest path tree for a node.
851 847

	
852 848
    ///This function returns the 'previous arc' of the shortest path
853 849
    ///tree for the node \c v, i.e. it returns the last arc of a
854 850
    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
855 851
    ///is not reachable from the root(s) or if \c v is a root.
856 852
    ///
857 853
    ///The shortest path tree used here is equal to the shortest path
858 854
    ///tree used in \ref predNode().
859 855
    ///
860 856
    ///\pre Either \ref run() or \ref start() must be called before
861 857
    ///using this function.
862 858
    Arc predArc(Node v) const { return (*_pred)[v]; }
863 859

	
864 860
    ///Returns the 'previous node' of the shortest path tree for a node.
865 861

	
866 862
    ///This function returns the 'previous node' of the shortest path
867 863
    ///tree for the node \c v, i.e. it returns the last but one node
868 864
    ///from a shortest path from the root(s) to \c v. It is \c INVALID
869 865
    ///if \c v is not reachable from the root(s) or if \c v is a root.
870 866
    ///
871 867
    ///The shortest path tree used here is equal to the shortest path
872 868
    ///tree used in \ref predArc().
873 869
    ///
874 870
    ///\pre Either \ref run() or \ref start() must be called before
875 871
    ///using this function.
876 872
    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
877 873
                                  G->source((*_pred)[v]); }
878 874

	
879 875
    ///\brief Returns a const reference to the node map that stores the
880 876
    ///distances of the nodes.
881 877
    ///
882 878
    ///Returns a const reference to the node map that stores the distances
883 879
    ///of the nodes calculated by the algorithm.
884 880
    ///
885 881
    ///\pre Either \ref run() or \ref init()
886 882
    ///must be called before using this function.
887 883
    const DistMap &distMap() const { return *_dist;}
888 884

	
889 885
    ///\brief Returns a const reference to the node map that stores the
890 886
    ///predecessor arcs.
891 887
    ///
892 888
    ///Returns a const reference to the node map that stores the predecessor
893 889
    ///arcs, which form the shortest path tree.
894 890
    ///
895 891
    ///\pre Either \ref run() or \ref init()
896 892
    ///must be called before using this function.
897 893
    const PredMap &predMap() const { return *_pred;}
898 894

	
899 895
    ///Checks if a node is reachable from the root(s).
900 896

	
901 897
    ///Returns \c true if \c v is reachable from the root(s).
902 898
    ///\pre Either \ref run() or \ref start()
903 899
    ///must be called before using this function.
904 900
    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
905 901
                                        Heap::PRE_HEAP; }
906 902

	
907 903
    ///Checks if a node is processed.
908 904

	
909 905
    ///Returns \c true if \c v is processed, i.e. the shortest
910 906
    ///path to \c v has already found.
911 907
    ///\pre Either \ref run() or \ref start()
912 908
    ///must be called before using this function.
913 909
    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
914 910
                                          Heap::POST_HEAP; }
915 911

	
916 912
    ///The current distance of a node from the root(s).
917 913

	
918 914
    ///Returns the current distance of a node from the root(s).
919 915
    ///It may be decreased in the following processes.
920 916
    ///\pre \c v should be reached but not processed.
921 917
    Value currentDist(Node v) const { return (*_heap)[v]; }
922 918

	
923 919
    ///@}
924 920
  };
925 921

	
926 922

	
927 923
  ///Default traits class of dijkstra() function.
928 924

	
929 925
  ///Default traits class of dijkstra() function.
930 926
  ///\tparam GR The type of the digraph.
931 927
  ///\tparam LM The type of the length map.
932 928
  template<class GR, class LM>
933 929
  struct DijkstraWizardDefaultTraits
934 930
  {
935 931
    ///The type of the digraph the algorithm runs on.
936 932
    typedef GR Digraph;
937 933
    ///The type of the map that stores the arc lengths.
938 934

	
939 935
    ///The type of the map that stores the arc lengths.
940 936
    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
941 937
    typedef LM LengthMap;
942 938
    ///The type of the length of the arcs.
943 939
    typedef typename LM::Value Value;
944 940

	
945 941
    /// Operation traits for Dijkstra algorithm.
946 942

	
947 943
    /// This class defines the operations that are used in the algorithm.
948 944
    /// \see DijkstraDefaultOperationTraits
949 945
    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
950 946

	
951 947
    /// The cross reference type used by the heap.
952 948

	
953 949
    /// The cross reference type used by the heap.
954 950
    /// Usually it is \c Digraph::NodeMap<int>.
955 951
    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
956 952
    ///Instantiates a \ref HeapCrossRef.
957 953

	
958 954
    ///This function instantiates a \ref HeapCrossRef.
959 955
    /// \param g is the digraph, to which we would like to define the
960 956
    /// HeapCrossRef.
961
    /// \todo The digraph alone may be insufficient for the initialization
962 957
    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
963 958
    {
964 959
      return new HeapCrossRef(g);
965 960
    }
966 961

	
967 962
    ///The heap type used by the Dijkstra algorithm.
968 963

	
969 964
    ///The heap type used by the Dijkstra algorithm.
970 965
    ///
971 966
    ///\sa BinHeap
972 967
    ///\sa Dijkstra
973 968
    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
974 969
                    std::less<Value> > Heap;
975 970

	
976 971
    ///Instantiates a \ref Heap.
977 972

	
978 973
    ///This function instantiates a \ref Heap.
979 974
    /// \param r is the HeapCrossRef which is used.
980 975
    static Heap *createHeap(HeapCrossRef& r)
981 976
    {
982 977
      return new Heap(r);
983 978
    }
984 979

	
985 980
    ///\brief The type of the map that stores the predecessor
986 981
    ///arcs of the shortest paths.
987 982
    ///
988 983
    ///The type of the map that stores the predecessor
989 984
    ///arcs of the shortest paths.
990 985
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
991 986
    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
992 987
    ///Instantiates a \ref PredMap.
993 988

	
994 989
    ///This function instantiates a \ref PredMap.
995 990
    ///\param g is the digraph, to which we would like to define the
996 991
    ///\ref PredMap.
997
    ///\todo The digraph alone may be insufficient to initialize
998 992
    static PredMap *createPredMap(const Digraph &g)
999 993
    {
1000 994
      return new PredMap(g);
1001 995
    }
1002 996

	
1003 997
    ///The type of the map that indicates which nodes are processed.
1004 998

	
1005 999
    ///The type of the map that indicates which nodes are processed.
1006 1000
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1007 1001
    ///By default it is a NullMap.
1008
    ///\todo If it is set to a real map,
1009
    ///Dijkstra::processed() should read this.
1010
    ///\todo named parameter to set this type, function to read and write.
1011 1002
    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1012 1003
    ///Instantiates a \ref ProcessedMap.
1013 1004

	
1014 1005
    ///This function instantiates a \ref ProcessedMap.
1015 1006
    ///\param g is the digraph, to which
1016 1007
    ///we would like to define the \ref ProcessedMap.
1017 1008
#ifdef DOXYGEN
1018 1009
    static ProcessedMap *createProcessedMap(const Digraph &g)
1019 1010
#else
1020 1011
    static ProcessedMap *createProcessedMap(const Digraph &)
1021 1012
#endif
1022 1013
    {
1023 1014
      return new ProcessedMap();
1024 1015
    }
1025 1016

	
1026 1017
    ///The type of the map that stores the distances of the nodes.
1027 1018

	
1028 1019
    ///The type of the map that stores the distances of the nodes.
1029 1020
    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1030 1021
    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1031 1022
    ///Instantiates a \ref DistMap.
1032 1023

	
1033 1024
    ///This function instantiates a \ref DistMap.
1034 1025
    ///\param g is the digraph, to which we would like to define
1035 1026
    ///the \ref DistMap
1036 1027
    static DistMap *createDistMap(const Digraph &g)
1037 1028
    {
1038 1029
      return new DistMap(g);
1039 1030
    }
1040 1031

	
1041 1032
    ///The type of the shortest paths.
1042 1033

	
1043 1034
    ///The type of the shortest paths.
1044 1035
    ///It must meet the \ref concepts::Path "Path" concept.
1045 1036
    typedef lemon::Path<Digraph> Path;
1046 1037
  };
1047 1038

	
1048 1039
  /// Default traits class used by \ref DijkstraWizard
1049 1040

	
1050 1041
  /// To make it easier to use Dijkstra algorithm
1051 1042
  /// we have created a wizard class.
1052 1043
  /// This \ref DijkstraWizard class needs default traits,
1053 1044
  /// as well as the \ref Dijkstra class.
1054 1045
  /// The \ref DijkstraWizardBase is a class to be the default traits of the
1055 1046
  /// \ref DijkstraWizard class.
1056
  /// \todo More named parameters are required...
1057 1047
  template<class GR,class LM>
1058 1048
  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1059 1049
  {
1060 1050
    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1061 1051
  protected:
1062 1052
    //The type of the nodes in the digraph.
1063 1053
    typedef typename Base::Digraph::Node Node;
1064 1054

	
1065 1055
    //Pointer to the digraph the algorithm runs on.
1066 1056
    void *_g;
1067 1057
    //Pointer to the length map.
1068 1058
    void *_length;
1069 1059
    //Pointer to the map of processed nodes.
1070 1060
    void *_processed;
1071 1061
    //Pointer to the map of predecessors arcs.
1072 1062
    void *_pred;
1073 1063
    //Pointer to the map of distances.
1074 1064
    void *_dist;
1075 1065
    //Pointer to the shortest path to the target node.
1076 1066
    void *_path;
1077 1067
    //Pointer to the distance of the target node.
1078 1068
    void *_di;
1079 1069

	
1080 1070
  public:
1081 1071
    /// Constructor.
1082 1072

	
1083 1073
    /// This constructor does not require parameters, therefore it initiates
1084 1074
    /// all of the attributes to \c 0.
1085 1075
    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
1086 1076
                           _dist(0), _path(0), _di(0) {}
1087 1077

	
1088 1078
    /// Constructor.
1089 1079

	
1090 1080
    /// This constructor requires two parameters,
1091 1081
    /// others are initiated to \c 0.
1092 1082
    /// \param g The digraph the algorithm runs on.
1093 1083
    /// \param l The length map.
1094 1084
    DijkstraWizardBase(const GR &g,const LM &l) :
1095 1085
      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1096 1086
      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1097 1087
      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
1098 1088

	
1099 1089
  };
1100 1090

	
1101 1091
  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
1102 1092

	
1103 1093
  /// This auxiliary class is created to implement the
1104 1094
  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
1105 1095
  /// It does not have own \ref run() method, it uses the functions
1106 1096
  /// and features of the plain \ref Dijkstra.
1107 1097
  ///
1108 1098
  /// This class should only be used through the \ref dijkstra() function,
1109 1099
  /// which makes it easier to use the algorithm.
1110 1100
  template<class TR>
1111 1101
  class DijkstraWizard : public TR
1112 1102
  {
1113 1103
    typedef TR Base;
1114 1104

	
1115 1105
    ///The type of the digraph the algorithm runs on.
1116 1106
    typedef typename TR::Digraph Digraph;
1117 1107

	
1118 1108
    typedef typename Digraph::Node Node;
1119 1109
    typedef typename Digraph::NodeIt NodeIt;
1120 1110
    typedef typename Digraph::Arc Arc;
1121 1111
    typedef typename Digraph::OutArcIt OutArcIt;
1122 1112

	
1123 1113
    ///The type of the map that stores the arc lengths.
1124 1114
    typedef typename TR::LengthMap LengthMap;
1125 1115
    ///The type of the length of the arcs.
1126 1116
    typedef typename LengthMap::Value Value;
1127 1117
    ///\brief The type of the map that stores the predecessor
1128 1118
    ///arcs of the shortest paths.
1129 1119
    typedef typename TR::PredMap PredMap;
1130 1120
    ///The type of the map that stores the distances of the nodes.
1131 1121
    typedef typename TR::DistMap DistMap;
1132 1122
    ///The type of the map that indicates which nodes are processed.
1133 1123
    typedef typename TR::ProcessedMap ProcessedMap;
1134 1124
    ///The type of the shortest paths
1135 1125
    typedef typename TR::Path Path;
1136 1126
    ///The heap type used by the dijkstra algorithm.
1137 1127
    typedef typename TR::Heap Heap;
1138 1128

	
1139 1129
  public:
1140 1130

	
1141 1131
    /// Constructor.
1142 1132
    DijkstraWizard() : TR() {}
1143 1133

	
1144 1134
    /// Constructor that requires parameters.
1145 1135

	
1146 1136
    /// Constructor that requires parameters.
1147 1137
    /// These parameters will be the default values for the traits class.
1148 1138
    /// \param g The digraph the algorithm runs on.
1149 1139
    /// \param l The length map.
1150 1140
    DijkstraWizard(const Digraph &g, const LengthMap &l) :
1151 1141
      TR(g,l) {}
1152 1142

	
1153 1143
    ///Copy constructor
1154 1144
    DijkstraWizard(const TR &b) : TR(b) {}
1155 1145

	
1156 1146
    ~DijkstraWizard() {}
1157 1147

	
1158 1148
    ///Runs Dijkstra algorithm from the given source node.
1159 1149

	
1160 1150
    ///This method runs %Dijkstra algorithm from the given source node
1161 1151
    ///in order to compute the shortest path to each node.
1162 1152
    void run(Node s)
1163 1153
    {
1164 1154
      if (s==INVALID) throw UninitializedParameter();
1165 1155
      Dijkstra<Digraph,LengthMap,TR>
1166 1156
        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1167 1157
             *reinterpret_cast<const LengthMap*>(Base::_length));
1168 1158
      if (Base::_pred)
1169 1159
        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1170 1160
      if (Base::_dist)
1171 1161
        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1172 1162
      if (Base::_processed)
1173 1163
        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1174 1164
      dijk.run(s);
1175 1165
    }
1176 1166

	
1177 1167
    ///Finds the shortest path between \c s and \c t.
1178 1168

	
1179 1169
    ///This method runs the %Dijkstra algorithm from node \c s
1180 1170
    ///in order to compute the shortest path to node \c t
1181 1171
    ///(it stops searching when \c t is processed).
1182 1172
    ///
1183 1173
    ///\return \c true if \c t is reachable form \c s.
1184 1174
    bool run(Node s, Node t)
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_ERROR_H
20 20
#define LEMON_ERROR_H
21 21

	
22 22
/// \ingroup exceptions
23 23
/// \file
24 24
/// \brief Basic exception classes and error handling.
25 25

	
26 26
#include <exception>
27 27
#include <string>
28 28
#include <sstream>
29 29
#include <iostream>
30 30
#include <cstdlib>
31 31
#include <memory>
32 32

	
33 33
namespace lemon {
34 34

	
35 35
  /// \addtogroup exceptions
36 36
  /// @{
37 37

	
38 38
  /// \brief Exception safe wrapper class.
39 39
  ///
40 40
  /// Exception safe wrapper class to implement the members of exceptions.
41 41
  template <typename _Type>
42 42
  class ExceptionMember {
43 43
  public:
44 44
    typedef _Type Type;
45 45

	
46 46
    ExceptionMember() throw() {
47 47
      try {
48 48
        ptr.reset(new Type());
49 49
      } catch (...) {}
50 50
    }
51 51

	
52 52
    ExceptionMember(const Type& type) throw() {
53 53
      try {
54 54
        ptr.reset(new Type());
55 55
        if (ptr.get() == 0) return;
56 56
        *ptr = type;
57 57
      } catch (...) {}
58 58
    }
59 59

	
60 60
    ExceptionMember(const ExceptionMember& copy) throw() {
61 61
      try {
62 62
        if (!copy.valid()) return;
63 63
        ptr.reset(new Type());
64 64
        if (ptr.get() == 0) return;
65 65
        *ptr = copy.get();
66 66
      } catch (...) {}
67 67
    }
68 68

	
69 69
    ExceptionMember& operator=(const ExceptionMember& copy) throw() {
70 70
      if (ptr.get() == 0) return;
71 71
      try {
72 72
        if (!copy.valid()) return;
73 73
        *ptr = copy.get();
74 74
      } catch (...) {}
75 75
    }
76 76

	
77 77
    void set(const Type& type) throw() {
78 78
      if (ptr.get() == 0) return;
79 79
      try {
80 80
        *ptr = type;
81 81
      } catch (...) {}
82 82
    }
83 83

	
84 84
    const Type& get() const {
85 85
      return *ptr;
86 86
    }
87 87

	
88 88
    bool valid() const throw() {
89 89
      return ptr.get() != 0;
90 90
    }
91 91

	
92 92
  private:
93 93
    std::auto_ptr<_Type> ptr;
94 94
  };
95 95

	
96 96
  /// Exception-safe convenient error message builder class.
97 97

	
98 98
  /// Helper class which provides a convenient ostream-like (operator <<
99 99
  /// based) interface to create a string message. Mostly useful in
100 100
  /// exception classes (therefore the name).
101 101
  class ErrorMessage {
102 102
  protected:
103 103
    ///\e
104 104

	
105
    ///\todo The good solution is boost::shared_ptr...
106
    ///
107 105
    mutable std::auto_ptr<std::ostringstream> buf;
108 106

	
109 107
    ///\e
110 108
    bool init() throw() {
111 109
      try {
112 110
        buf.reset(new std::ostringstream);
113 111
      }
114 112
      catch(...) {
115 113
        buf.reset();
116 114
      }
117 115
      return buf.get();
118 116
    }
119 117

	
120 118
  public:
121 119

	
122 120
    ///\e
123 121
    ErrorMessage() throw() { init(); }
124 122

	
125 123
    ErrorMessage(const ErrorMessage& em) throw() : buf(em.buf) { }
126 124

	
127 125
    ///\e
128 126
    ErrorMessage(const char *msg) throw() {
129 127
      init();
130 128
      *this << msg;
131 129
    }
132 130

	
133 131
    ///\e
134 132
    ErrorMessage(const std::string &msg) throw() {
135 133
      init();
136 134
      *this << msg;
137 135
    }
138 136

	
139 137
    ///\e
140 138
    template <typename T>
141 139
    ErrorMessage& operator<<(const T &t) throw() {
142 140
      if( ! buf.get() ) return *this;
143 141

	
144 142
      try {
145 143
        *buf << t;
146 144
      }
147 145
      catch(...) {
148 146
        buf.reset();
149 147
      }
150 148
      return *this;
151 149
    }
152 150

	
153 151
    ///\e
154 152
    const char* message() throw() {
155 153
      if( ! buf.get() ) return 0;
156 154

	
157 155
      const char* mes = 0;
158 156
      try {
159 157
        mes = buf->str().c_str();
160 158
      }
161 159
      catch(...) {}
162 160
      return mes;
163 161
    }
164 162

	
165 163
  };
166 164

	
167 165
  /// Generic exception class.
168 166

	
169 167
  /// Base class for exceptions used in LEMON.
170 168
  ///
171 169
  class Exception : public std::exception {
172 170
  public:
173 171
    ///\e
174 172
    Exception() {}
175 173
    ///\e
176 174
    virtual ~Exception() throw() {}
177 175
    ///\e
178 176
    virtual const char* what() const throw() {
179 177
      return "lemon::Exception";
180 178
    }
181 179
  };
182 180

	
183 181
  /// One of the two main subclasses of \ref Exception.
184 182

	
185 183
  /// Logic errors represent problems in the internal logic of a program;
186 184
  /// in theory, these are preventable, and even detectable before the
187 185
  /// program runs (e.g. violations of class invariants).
188 186
  ///
189 187
  /// A typical example for this is \ref UninitializedParameter.
190 188
  class LogicError : public Exception {
191 189
  public:
192 190
    virtual const char* what() const throw() {
193 191
      return "lemon::LogicError";
194 192
    }
195 193
  };
196 194

	
197 195
  /// \ref Exception for uninitialized parameters.
198 196

	
199 197
  /// This error represents problems in the initialization
200 198
  /// of the parameters of the algorithms.
201 199
  class UninitializedParameter : public LogicError {
202 200
  public:
203 201
    virtual const char* what() const throw() {
204 202
      return "lemon::UninitializedParameter";
205 203
    }
206 204
  };
207 205

	
208 206

	
209 207
  /// One of the two main subclasses of \ref Exception.
210 208

	
211 209
  /// Runtime errors represent problems outside the scope of a program;
212 210
  /// they cannot be easily predicted and can generally only be caught
213 211
  /// as the program executes.
214 212
  class RuntimeError : public Exception {
215 213
  public:
216 214
    virtual const char* what() const throw() {
217 215
      return "lemon::RuntimeError";
218 216
    }
219 217
  };
220 218

	
221 219
  ///\e
222 220
  class RangeError : public RuntimeError {
223 221
  public:
224 222
    virtual const char* what() const throw() {
225 223
      return "lemon::RangeError";
226 224
    }
227 225
  };
228 226

	
229 227
  ///\e
230 228
  class IoError : public RuntimeError {
231 229
  public:
232 230
    virtual const char* what() const throw() {
233 231
      return "lemon::IoError";
234 232
    }
Ignore white space 6 line context
... ...
@@ -541,497 +541,492 @@
541 541

	
542 542
  ///Turns on/off the automatic arc width scaling.
543 543
  ///
544 544
  ///\sa arcWidthScale()
545 545
  ///
546 546
  GraphToEps<T> &autoArcWidthScale(bool b=true) {
547 547
    _autoArcWidthScale=b;return *this;
548 548
  }
549 549
  ///Turns on/off the absolutematic arc width scaling.
550 550

	
551 551
  ///Turns on/off the absolutematic arc width scaling.
552 552
  ///
553 553
  ///\sa arcWidthScale()
554 554
  ///
555 555
  GraphToEps<T> &absoluteArcWidths(bool b=true) {
556 556
    _absoluteArcWidths=b;return *this;
557 557
  }
558 558
  ///Sets a global scale factor for the whole picture
559 559
  GraphToEps<T> &scale(double d) {_scale=d;return *this;}
560 560
  ///Sets the width of the border around the picture
561 561
  GraphToEps<T> &border(double b=10) {_xBorder=_yBorder=b;return *this;}
562 562
  ///Sets the width of the border around the picture
563 563
  GraphToEps<T> &border(double x, double y) {
564 564
    _xBorder=x;_yBorder=y;return *this;
565 565
  }
566 566
  ///Sets whether to draw arrows
567 567
  GraphToEps<T> &drawArrows(bool b=true) {_drawArrows=b;return *this;}
568 568
  ///Sets the length of the arrowheads
569 569
  GraphToEps<T> &arrowLength(double d=1.0) {_arrowLength*=d;return *this;}
570 570
  ///Sets the width of the arrowheads
571 571
  GraphToEps<T> &arrowWidth(double d=.3) {_arrowWidth*=d;return *this;}
572 572

	
573 573
  ///Scales the drawing to fit to A4 page
574 574
  GraphToEps<T> &scaleToA4() {_scaleToA4=true;return *this;}
575 575

	
576 576
  ///Enables parallel arcs
577 577
  GraphToEps<T> &enableParallel(bool b=true) {_enableParallel=b;return *this;}
578 578

	
579 579
  ///Sets the distance between parallel arcs
580 580
  GraphToEps<T> &parArcDist(double d) {_parArcDist*=d;return *this;}
581 581

	
582 582
  ///Hides the arcs
583 583
  GraphToEps<T> &hideArcs(bool b=true) {_showArcs=!b;return *this;}
584 584
  ///Hides the nodes
585 585
  GraphToEps<T> &hideNodes(bool b=true) {_showNodes=!b;return *this;}
586 586

	
587 587
  ///Sets the size of the node texts
588 588
  GraphToEps<T> &nodeTextSize(double d) {_nodeTextSize=d;return *this;}
589 589

	
590 590
  ///Sets the color of the node texts to be different from the node color
591 591

	
592 592
  ///Sets the color of the node texts to be as different from the node color
593 593
  ///as it is possible.
594 594
  GraphToEps<T> &distantColorNodeTexts()
595 595
  {_nodeTextColorType=DIST_COL;return *this;}
596 596
  ///Sets the color of the node texts to be black or white and always visible.
597 597

	
598 598
  ///Sets the color of the node texts to be black or white according to
599 599
  ///which is more different from the node color.
600 600
  GraphToEps<T> &distantBWNodeTexts()
601 601
  {_nodeTextColorType=DIST_BW;return *this;}
602 602

	
603 603
  ///Gives a preamble block for node Postscript block.
604 604

	
605 605
  ///Gives a preamble block for node Postscript block.
606 606
  ///
607 607
  ///\sa nodePsTexts()
608 608
  GraphToEps<T> & nodePsTextsPreamble(const char *str) {
609 609
    _nodePsTextsPreamble=str ;return *this;
610 610
  }
611 611
  ///Sets whether the graph is undirected
612 612

	
613 613
  ///Sets whether the graph is undirected.
614 614
  ///
615 615
  ///This setting is the default for undirected graphs.
616 616
  ///
617 617
  ///\sa directed()
618 618
   GraphToEps<T> &undirected(bool b=true) {_undirected=b;return *this;}
619 619

	
620 620
  ///Sets whether the graph is directed
621 621

	
622 622
  ///Sets whether the graph is directed.
623 623
  ///Use it to show the edges as a pair of directed ones.
624 624
  ///
625 625
  ///This setting is the default for digraphs.
626 626
  ///
627 627
  ///\sa undirected()
628 628
  GraphToEps<T> &directed(bool b=true) {_undirected=!b;return *this;}
629 629

	
630 630
  ///Sets the title.
631 631

	
632 632
  ///Sets the title of the generated image,
633 633
  ///namely it inserts a <tt>%%Title:</tt> DSC field to the header of
634 634
  ///the EPS file.
635 635
  GraphToEps<T> &title(const std::string &t) {_title=t;return *this;}
636 636
  ///Sets the copyright statement.
637 637

	
638 638
  ///Sets the copyright statement of the generated image,
639 639
  ///namely it inserts a <tt>%%Copyright:</tt> DSC field to the header of
640 640
  ///the EPS file.
641 641
  GraphToEps<T> &copyright(const std::string &t) {_copyright=t;return *this;}
642 642

	
643 643
protected:
644 644
  bool isInsideNode(dim2::Point<double> p, double r,int t)
645 645
  {
646 646
    switch(t) {
647 647
    case CIRCLE:
648 648
    case MALE:
649 649
    case FEMALE:
650 650
      return p.normSquare()<=r*r;
651 651
    case SQUARE:
652 652
      return p.x<=r&&p.x>=-r&&p.y<=r&&p.y>=-r;
653 653
    case DIAMOND:
654 654
      return p.x+p.y<=r && p.x-p.y<=r && -p.x+p.y<=r && -p.x-p.y<=r;
655 655
    }
656 656
    return false;
657 657
  }
658 658

	
659 659
public:
660 660
  ~GraphToEps() { }
661 661

	
662 662
  ///Draws the graph.
663 663

	
664 664
  ///Like other functions using
665 665
  ///\ref named-templ-func-param "named template parameters",
666 666
  ///this function calls the algorithm itself, i.e. in this case
667 667
  ///it draws the graph.
668 668
  void run() {
669
    //\todo better 'epsilon' would be nice here.
670 669
    const double EPSILON=1e-9;
671 670
    if(dontPrint) return;
672 671

	
673 672
    _graph_to_eps_bits::_NegY<typename T::CoordsMapType>
674 673
      mycoords(_coords,_negY);
675 674

	
676 675
    os << "%!PS-Adobe-2.0 EPSF-2.0\n";
677 676
    if(_title.size()>0) os << "%%Title: " << _title << '\n';
678 677
     if(_copyright.size()>0) os << "%%Copyright: " << _copyright << '\n';
679 678
    os << "%%Creator: LEMON, graphToEps()\n";
680 679

	
681 680
    {
682 681
#ifndef WIN32
683 682
      timeval tv;
684 683
      gettimeofday(&tv, 0);
685 684

	
686 685
      char cbuf[26];
687 686
      ctime_r(&tv.tv_sec,cbuf);
688 687
      os << "%%CreationDate: " << cbuf;
689 688
#else
690 689
      SYSTEMTIME time;
691 690
      char buf1[11], buf2[9], buf3[5];
692 691

	
693 692
      GetSystemTime(&time);
694 693
      if (GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
695 694
                        "ddd MMM dd", buf1, 11) &&
696 695
          GetTimeFormat(LOCALE_USER_DEFAULT, 0, &time,
697 696
                        "HH':'mm':'ss", buf2, 9) &&
698 697
          GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
699 698
                                "yyyy", buf3, 5)) {
700 699
        os << "%%CreationDate: " << buf1 << ' '
701 700
           << buf2 << ' ' << buf3 << std::endl;
702 701
      }
703 702
#endif
704 703
    }
705 704

	
706 705
    if (_autoArcWidthScale) {
707 706
      double max_w=0;
708 707
      for(ArcIt e(g);e!=INVALID;++e)
709 708
        max_w=std::max(double(_arcWidths[e]),max_w);
710
      //\todo better 'epsilon' would be nice here.
711 709
      if(max_w>EPSILON) {
712 710
        _arcWidthScale/=max_w;
713 711
      }
714 712
    }
715 713

	
716 714
    if (_autoNodeScale) {
717 715
      double max_s=0;
718 716
      for(NodeIt n(g);n!=INVALID;++n)
719 717
        max_s=std::max(double(_nodeSizes[n]),max_s);
720
      //\todo better 'epsilon' would be nice here.
721 718
      if(max_s>EPSILON) {
722 719
        _nodeScale/=max_s;
723 720
      }
724 721
    }
725 722

	
726 723
    double diag_len = 1;
727 724
    if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {
728 725
      dim2::Box<double> bb;
729 726
      for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);
730 727
      if (bb.empty()) {
731 728
        bb = dim2::Box<double>(dim2::Point<double>(0,0));
732 729
      }
733 730
      diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());
734 731
      if(diag_len<EPSILON) diag_len = 1;
735 732
      if(!_absoluteNodeSizes) _nodeScale*=diag_len;
736 733
      if(!_absoluteArcWidths) _arcWidthScale*=diag_len;
737 734
    }
738 735

	
739 736
    dim2::Box<double> bb;
740 737
    for(NodeIt n(g);n!=INVALID;++n) {
741 738
      double ns=_nodeSizes[n]*_nodeScale;
742 739
      dim2::Point<double> p(ns,ns);
743 740
      switch(_nodeShapes[n]) {
744 741
      case CIRCLE:
745 742
      case SQUARE:
746 743
      case DIAMOND:
747 744
        bb.add(p+mycoords[n]);
748 745
        bb.add(-p+mycoords[n]);
749 746
        break;
750 747
      case MALE:
751 748
        bb.add(-p+mycoords[n]);
752 749
        bb.add(dim2::Point<double>(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]);
753 750
        break;
754 751
      case FEMALE:
755 752
        bb.add(p+mycoords[n]);
756 753
        bb.add(dim2::Point<double>(-ns,-3.01*ns)+mycoords[n]);
757 754
        break;
758 755
      }
759 756
    }
760 757
    if (bb.empty()) {
761 758
      bb = dim2::Box<double>(dim2::Point<double>(0,0));
762 759
    }
763 760

	
764 761
    if(_scaleToA4)
765 762
      os <<"%%BoundingBox: 0 0 596 842\n%%DocumentPaperSizes: a4\n";
766 763
    else {
767 764
      if(_preScale) {
768 765
        //Rescale so that BoundingBox won't be neither to big nor too small.
769 766
        while(bb.height()*_scale>1000||bb.width()*_scale>1000) _scale/=10;
770 767
        while(bb.height()*_scale<100||bb.width()*_scale<100) _scale*=10;
771 768
      }
772 769

	
773 770
      os << "%%BoundingBox: "
774 771
         << int(floor(bb.left()   * _scale - _xBorder)) << ' '
775 772
         << int(floor(bb.bottom() * _scale - _yBorder)) << ' '
776 773
         << int(ceil(bb.right()  * _scale + _xBorder)) << ' '
777 774
         << int(ceil(bb.top()    * _scale + _yBorder)) << '\n';
778 775
    }
779 776

	
780 777
    os << "%%EndComments\n";
781 778

	
782 779
    //x1 y1 x2 y2 x3 y3 cr cg cb w
783 780
    os << "/lb { setlinewidth setrgbcolor newpath moveto\n"
784 781
       << "      4 2 roll 1 index 1 index curveto stroke } bind def\n";
785 782
    os << "/l { setlinewidth setrgbcolor newpath moveto lineto stroke }"
786 783
       << " bind def\n";
787 784
    //x y r
788 785
    os << "/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath }"
789 786
       << " bind def\n";
790 787
    //x y r
791 788
    os << "/sq { newpath 2 index 1 index add 2 index 2 index add moveto\n"
792 789
       << "      2 index 1 index sub 2 index 2 index add lineto\n"
793 790
       << "      2 index 1 index sub 2 index 2 index sub lineto\n"
794 791
       << "      2 index 1 index add 2 index 2 index sub lineto\n"
795 792
       << "      closepath pop pop pop} bind def\n";
796 793
    //x y r
797 794
    os << "/di { newpath 2 index 1 index add 2 index moveto\n"
798 795
       << "      2 index             2 index 2 index add lineto\n"
799 796
       << "      2 index 1 index sub 2 index             lineto\n"
800 797
       << "      2 index             2 index 2 index sub lineto\n"
801 798
       << "      closepath pop pop pop} bind def\n";
802 799
    // x y r cr cg cb
803 800
    os << "/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill\n"
804 801
       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
805 802
       << "   } bind def\n";
806 803
    os << "/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill\n"
807 804
       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div sq fill\n"
808 805
       << "   } bind def\n";
809 806
    os << "/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill\n"
810 807
       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div di fill\n"
811 808
       << "   } bind def\n";
812 809
    os << "/nfemale { 0 0 0 setrgbcolor 3 index "
813 810
       << _nodeBorderQuotient/(1+_nodeBorderQuotient)
814 811
       << " 1.5 mul mul setlinewidth\n"
815 812
       << "  newpath 5 index 5 index moveto "
816 813
       << "5 index 5 index 5 index 3.01 mul sub\n"
817 814
       << "  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub"
818 815
       << " moveto\n"
819 816
       << "  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto "
820 817
       << "stroke\n"
821 818
       << "  5 index 5 index 5 index c fill\n"
822 819
       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
823 820
       << "  } bind def\n";
824 821
    os << "/nmale {\n"
825 822
       << "  0 0 0 setrgbcolor 3 index "
826 823
       << _nodeBorderQuotient/(1+_nodeBorderQuotient)
827 824
       <<" 1.5 mul mul setlinewidth\n"
828 825
       << "  newpath 5 index 5 index moveto\n"
829 826
       << "  5 index 4 index 1 mul 1.5 mul add\n"
830 827
       << "  5 index 5 index 3 sqrt 1.5 mul mul add\n"
831 828
       << "  1 index 1 index lineto\n"
832 829
       << "  1 index 1 index 7 index sub moveto\n"
833 830
       << "  1 index 1 index lineto\n"
834 831
       << "  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub"
835 832
       << " lineto\n"
836 833
       << "  stroke\n"
837 834
       << "  5 index 5 index 5 index c fill\n"
838 835
       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
839 836
       << "  } bind def\n";
840 837

	
841 838

	
842 839
    os << "/arrl " << _arrowLength << " def\n";
843 840
    os << "/arrw " << _arrowWidth << " def\n";
844 841
    // l dx_norm dy_norm
845 842
    os << "/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def\n";
846 843
    //len w dx_norm dy_norm x1 y1 cr cg cb
847 844
    os << "/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx "
848 845
       << "exch def\n"
849 846
       << "       /w exch def /len exch def\n"
850 847
      //<< "0.1 setlinewidth x1 y1 moveto dx len mul dy len mul rlineto stroke"
851 848
       << "       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto\n"
852 849
       << "       len w sub arrl sub dx dy lrl\n"
853 850
       << "       arrw dy dx neg lrl\n"
854 851
       << "       dx arrl w add mul dy w 2 div arrw add mul sub\n"
855 852
       << "       dy arrl w add mul dx w 2 div arrw add mul add rlineto\n"
856 853
       << "       dx arrl w add mul neg dy w 2 div arrw add mul sub\n"
857 854
       << "       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto\n"
858 855
       << "       arrw dy dx neg lrl\n"
859 856
       << "       len w sub arrl sub neg dx dy lrl\n"
860 857
       << "       closepath fill } bind def\n";
861 858
    os << "/cshow { 2 index 2 index moveto dup stringwidth pop\n"
862 859
       << "         neg 2 div fosi .35 mul neg rmoveto show pop pop} def\n";
863 860

	
864 861
    os << "\ngsave\n";
865 862
    if(_scaleToA4)
866 863
      if(bb.height()>bb.width()) {
867 864
        double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.height(),
868 865
                  (A4WIDTH-2*A4BORDER)/bb.width());
869 866
        os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' '
870 867
           << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER
871 868
           << " translate\n"
872 869
           << sc << " dup scale\n"
873 870
           << -bb.left() << ' ' << -bb.bottom() << " translate\n";
874 871
      }
875 872
      else {
876
        //\todo Verify centering
877 873
        double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(),
878 874
                  (A4WIDTH-2*A4BORDER)/bb.height());
879 875
        os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' '
880 876
           << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER
881 877
           << " translate\n"
882 878
           << sc << " dup scale\n90 rotate\n"
883 879
           << -bb.left() << ' ' << -bb.top() << " translate\n";
884 880
        }
885 881
    else if(_scale!=1.0) os << _scale << " dup scale\n";
886 882

	
887 883
    if(_showArcs) {
888 884
      os << "%Arcs:\ngsave\n";
889 885
      if(_enableParallel) {
890 886
        std::vector<Arc> el;
891 887
        for(ArcIt e(g);e!=INVALID;++e)
892 888
          if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0
893 889
             &&g.source(e)!=g.target(e))
894 890
            el.push_back(e);
895 891
        std::sort(el.begin(),el.end(),arcLess(g));
896 892

	
897 893
        typename std::vector<Arc>::iterator j;
898 894
        for(typename std::vector<Arc>::iterator i=el.begin();i!=el.end();i=j) {
899 895
          for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ;
900 896

	
901 897
          double sw=0;
902 898
          for(typename std::vector<Arc>::iterator e=i;e!=j;++e)
903 899
            sw+=_arcWidths[*e]*_arcWidthScale+_parArcDist;
904 900
          sw-=_parArcDist;
905 901
          sw/=-2.0;
906 902
          dim2::Point<double>
907 903
            dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);
908 904
          double l=std::sqrt(dvec.normSquare());
909
          //\todo better 'epsilon' would be nice here.
910 905
          dim2::Point<double> d(dvec/std::max(l,EPSILON));
911 906
          dim2::Point<double> m;
912 907
//           m=dim2::Point<double>(mycoords[g.target(*i)]+
913 908
//                                 mycoords[g.source(*i)])/2.0;
914 909

	
915 910
//            m=dim2::Point<double>(mycoords[g.source(*i)])+
916 911
//             dvec*(double(_nodeSizes[g.source(*i)])/
917 912
//                (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));
918 913

	
919 914
          m=dim2::Point<double>(mycoords[g.source(*i)])+
920 915
            d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0;
921 916

	
922 917
          for(typename std::vector<Arc>::iterator e=i;e!=j;++e) {
923 918
            sw+=_arcWidths[*e]*_arcWidthScale/2.0;
924 919
            dim2::Point<double> mm=m+rot90(d)*sw/.75;
925 920
            if(_drawArrows) {
926 921
              int node_shape;
927 922
              dim2::Point<double> s=mycoords[g.source(*e)];
928 923
              dim2::Point<double> t=mycoords[g.target(*e)];
929 924
              double rn=_nodeSizes[g.target(*e)]*_nodeScale;
930 925
              node_shape=_nodeShapes[g.target(*e)];
931 926
              dim2::Bezier3 bez(s,mm,mm,t);
932 927
              double t1=0,t2=1;
933 928
              for(int ii=0;ii<INTERPOL_PREC;++ii)
934 929
                if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2;
935 930
                else t1=(t1+t2)/2;
936 931
              dim2::Point<double> apoint=bez((t1+t2)/2);
937 932
              rn = _arrowLength+_arcWidths[*e]*_arcWidthScale;
938 933
              rn*=rn;
939 934
              t2=(t1+t2)/2;t1=0;
940 935
              for(int ii=0;ii<INTERPOL_PREC;++ii)
941 936
                if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2;
942 937
                else t2=(t1+t2)/2;
943 938
              dim2::Point<double> linend=bez((t1+t2)/2);
944 939
              bez=bez.before((t1+t2)/2);
945 940
//               rn=_nodeSizes[g.source(*e)]*_nodeScale;
946 941
//               node_shape=_nodeShapes[g.source(*e)];
947 942
//               t1=0;t2=1;
948 943
//               for(int i=0;i<INTERPOL_PREC;++i)
949 944
//                 if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape))
950 945
//                   t1=(t1+t2)/2;
951 946
//                 else t2=(t1+t2)/2;
952 947
//               bez=bez.after((t1+t2)/2);
953 948
              os << _arcWidths[*e]*_arcWidthScale << " setlinewidth "
954 949
                 << _arcColors[*e].red() << ' '
955 950
                 << _arcColors[*e].green() << ' '
956 951
                 << _arcColors[*e].blue() << " setrgbcolor newpath\n"
957 952
                 << bez.p1.x << ' ' <<  bez.p1.y << " moveto\n"
958 953
                 << bez.p2.x << ' ' << bez.p2.y << ' '
959 954
                 << bez.p3.x << ' ' << bez.p3.y << ' '
960 955
                 << bez.p4.x << ' ' << bez.p4.y << " curveto stroke\n";
961 956
              dim2::Point<double> dd(rot90(linend-apoint));
962 957
              dd*=(.5*_arcWidths[*e]*_arcWidthScale+_arrowWidth)/
963 958
                std::sqrt(dd.normSquare());
964 959
              os << "newpath " << psOut(apoint) << " moveto "
965 960
                 << psOut(linend+dd) << " lineto "
966 961
                 << psOut(linend-dd) << " lineto closepath fill\n";
967 962
            }
968 963
            else {
969 964
              os << mycoords[g.source(*e)].x << ' '
970 965
                 << mycoords[g.source(*e)].y << ' '
971 966
                 << mm.x << ' ' << mm.y << ' '
972 967
                 << mycoords[g.target(*e)].x << ' '
973 968
                 << mycoords[g.target(*e)].y << ' '
974 969
                 << _arcColors[*e].red() << ' '
975 970
                 << _arcColors[*e].green() << ' '
976 971
                 << _arcColors[*e].blue() << ' '
977 972
                 << _arcWidths[*e]*_arcWidthScale << " lb\n";
978 973
            }
979 974
            sw+=_arcWidths[*e]*_arcWidthScale/2.0+_parArcDist;
980 975
          }
981 976
        }
982 977
      }
983 978
      else for(ArcIt e(g);e!=INVALID;++e)
984 979
        if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0
985 980
           &&g.source(e)!=g.target(e)) {
986 981
          if(_drawArrows) {
987 982
            dim2::Point<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]);
988 983
            double rn=_nodeSizes[g.target(e)]*_nodeScale;
989 984
            int node_shape=_nodeShapes[g.target(e)];
990 985
            double t1=0,t2=1;
991 986
            for(int i=0;i<INTERPOL_PREC;++i)
992 987
              if(isInsideNode((-(t1+t2)/2)*d,rn,node_shape)) t1=(t1+t2)/2;
993 988
              else t2=(t1+t2)/2;
994 989
            double l=std::sqrt(d.normSquare());
995 990
            d/=l;
996 991

	
997 992
            os << l*(1-(t1+t2)/2) << ' '
998 993
               << _arcWidths[e]*_arcWidthScale << ' '
999 994
               << d.x << ' ' << d.y << ' '
1000 995
               << mycoords[g.source(e)].x << ' '
1001 996
               << mycoords[g.source(e)].y << ' '
1002 997
               << _arcColors[e].red() << ' '
1003 998
               << _arcColors[e].green() << ' '
1004 999
               << _arcColors[e].blue() << " arr\n";
1005 1000
          }
1006 1001
          else os << mycoords[g.source(e)].x << ' '
1007 1002
                  << mycoords[g.source(e)].y << ' '
1008 1003
                  << mycoords[g.target(e)].x << ' '
1009 1004
                  << mycoords[g.target(e)].y << ' '
1010 1005
                  << _arcColors[e].red() << ' '
1011 1006
                  << _arcColors[e].green() << ' '
1012 1007
                  << _arcColors[e].blue() << ' '
1013 1008
                  << _arcWidths[e]*_arcWidthScale << " l\n";
1014 1009
        }
1015 1010
      os << "grestore\n";
1016 1011
    }
1017 1012
    if(_showNodes) {
1018 1013
      os << "%Nodes:\ngsave\n";
1019 1014
      for(NodeIt n(g);n!=INVALID;++n) {
1020 1015
        os << mycoords[n].x << ' ' << mycoords[n].y << ' '
1021 1016
           << _nodeSizes[n]*_nodeScale << ' '
1022 1017
           << _nodeColors[n].red() << ' '
1023 1018
           << _nodeColors[n].green() << ' '
1024 1019
           << _nodeColors[n].blue() << ' ';
1025 1020
        switch(_nodeShapes[n]) {
1026 1021
        case CIRCLE:
1027 1022
          os<< "nc";break;
1028 1023
        case SQUARE:
1029 1024
          os<< "nsq";break;
1030 1025
        case DIAMOND:
1031 1026
          os<< "ndi";break;
1032 1027
        case MALE:
1033 1028
          os<< "nmale";break;
1034 1029
        case FEMALE:
1035 1030
          os<< "nfemale";break;
1036 1031
        }
1037 1032
        os<<'\n';
Ignore white space 6 line context
... ...
@@ -376,260 +376,258 @@
376 376
    void erase(const Arc& a) { Parent::erase(a); }
377 377

	
378 378
    /// Node validity check
379 379

	
380 380
    /// This function gives back true if the given node is valid,
381 381
    /// ie. it is a real node of the graph.
382 382
    ///
383 383
    /// \warning A Node pointing to a removed item
384 384
    /// could become valid again later if new nodes are
385 385
    /// added to the graph.
386 386
    bool valid(Node n) const { return Parent::valid(n); }
387 387

	
388 388
    /// Arc validity check
389 389

	
390 390
    /// This function gives back true if the given arc is valid,
391 391
    /// ie. it is a real arc of the graph.
392 392
    ///
393 393
    /// \warning An Arc pointing to a removed item
394 394
    /// could become valid again later if new nodes are
395 395
    /// added to the graph.
396 396
    bool valid(Arc a) const { return Parent::valid(a); }
397 397

	
398 398
    /// Change the target of \c a to \c n
399 399

	
400 400
    /// Change the target of \c a to \c n
401 401
    ///
402 402
    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
403 403
    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
404 404
    ///invalidated.
405 405
    ///
406 406
    ///\warning This functionality cannot be used together with the Snapshot
407 407
    ///feature.
408 408
    void changeTarget(Arc a, Node n) {
409 409
      Parent::changeTarget(a,n);
410 410
    }
411 411
    /// Change the source of \c a to \c n
412 412

	
413 413
    /// Change the source of \c a to \c n
414 414
    ///
415 415
    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
416 416
    ///valid. However the <tt>ArcIt<tt>s and <tt>OutArcIt</tt>s are
417 417
    ///invalidated.
418 418
    ///
419 419
    ///\warning This functionality cannot be used together with the Snapshot
420 420
    ///feature.
421 421
    void changeSource(Arc a, Node n) {
422 422
      Parent::changeSource(a,n);
423 423
    }
424 424

	
425 425
    /// Invert the direction of an arc.
426 426

	
427 427
    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
428 428
    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
429 429
    ///invalidated.
430 430
    ///
431 431
    ///\warning This functionality cannot be used together with the Snapshot
432 432
    ///feature.
433 433
    void reverseArc(Arc e) {
434 434
      Node t=target(e);
435 435
      changeTarget(e,source(e));
436 436
      changeSource(e,t);
437 437
    }
438 438

	
439 439
    /// Reserve memory for nodes.
440 440

	
441 441
    /// Using this function it is possible to avoid the superfluous memory
442 442
    /// allocation: if you know that the digraph you want to build will
443 443
    /// be very large (e.g. it will contain millions of nodes and/or arcs)
444 444
    /// then it is worth reserving space for this amount before starting
445 445
    /// to build the digraph.
446 446
    /// \sa reserveArc
447 447
    void reserveNode(int n) { nodes.reserve(n); };
448 448

	
449 449
    /// Reserve memory for arcs.
450 450

	
451 451
    /// Using this function it is possible to avoid the superfluous memory
452 452
    /// allocation: if you know that the digraph you want to build will
453 453
    /// be very large (e.g. it will contain millions of nodes and/or arcs)
454 454
    /// then it is worth reserving space for this amount before starting
455 455
    /// to build the digraph.
456 456
    /// \sa reserveNode
457 457
    void reserveArc(int m) { arcs.reserve(m); };
458 458

	
459 459
    ///Contract two nodes.
460 460

	
461 461
    ///This function contracts two nodes.
462 462
    ///Node \p b will be removed but instead of deleting
463 463
    ///incident arcs, they will be joined to \p a.
464 464
    ///The last parameter \p r controls whether to remove loops. \c true
465 465
    ///means that loops will be removed.
466 466
    ///
467 467
    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
468 468
    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
469 469
    ///may be invalidated.
470 470
    ///
471 471
    ///\warning This functionality cannot be used together with the Snapshot
472 472
    ///feature.
473 473
    void contract(Node a, Node b, bool r = true)
474 474
    {
475 475
      for(OutArcIt e(*this,b);e!=INVALID;) {
476 476
        OutArcIt f=e;
477 477
        ++f;
478 478
        if(r && target(e)==a) erase(e);
479 479
        else changeSource(e,a);
480 480
        e=f;
481 481
      }
482 482
      for(InArcIt e(*this,b);e!=INVALID;) {
483 483
        InArcIt f=e;
484 484
        ++f;
485 485
        if(r && source(e)==a) erase(e);
486 486
        else changeTarget(e,a);
487 487
        e=f;
488 488
      }
489 489
      erase(b);
490 490
    }
491 491

	
492 492
    ///Split a node.
493 493

	
494 494
    ///This function splits a node. First a new node is added to the digraph,
495 495
    ///then the source of each outgoing arc of \c n is moved to this new node.
496 496
    ///If \c connect is \c true (this is the default value), then a new arc
497 497
    ///from \c n to the newly created node is also added.
498 498
    ///\return The newly created node.
499 499
    ///
500 500
    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
501 501
    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
502 502
    ///be invalidated.
503 503
    ///
504
    ///\warning This functionality cannot be used together with the
504
    ///\warning This functionality cannot be used in conjunction with the
505 505
    ///Snapshot feature.
506
    ///
507
    ///\todo It could be implemented in a bit faster way.
508 506
    Node split(Node n, bool connect = true) {
509 507
      Node b = addNode();
510 508
      for(OutArcIt e(*this,n);e!=INVALID;) {
511 509
        OutArcIt f=e;
512 510
        ++f;
513 511
        changeSource(e,b);
514 512
        e=f;
515 513
      }
516 514
      if (connect) addArc(n,b);
517 515
      return b;
518 516
    }
519 517

	
520 518
    ///Split an arc.
521 519

	
522 520
    ///This function splits an arc. First a new node \c b is added to
523 521
    ///the digraph, then the original arc is re-targeted to \c
524 522
    ///b. Finally an arc from \c b to the original target is added.
525 523
    ///
526 524
    ///\return The newly created node.
527 525
    ///
528 526
    ///\warning This functionality cannot be used together with the
529 527
    ///Snapshot feature.
530 528
    Node split(Arc e) {
531 529
      Node b = addNode();
532 530
      addArc(b,target(e));
533 531
      changeTarget(e,b);
534 532
      return b;
535 533
    }
536 534

	
537 535
    /// \brief Class to make a snapshot of the digraph and restore
538 536
    /// it later.
539 537
    ///
540 538
    /// Class to make a snapshot of the digraph and restore it later.
541 539
    ///
542 540
    /// The newly added nodes and arcs can be removed using the
543 541
    /// restore() function.
544 542
    ///
545 543
    /// \warning Arc and node deletions and other modifications (e.g.
546 544
    /// contracting, splitting, reversing arcs or nodes) cannot be
547 545
    /// restored. These events invalidate the snapshot.
548 546
    class Snapshot {
549 547
    protected:
550 548

	
551 549
      typedef Parent::NodeNotifier NodeNotifier;
552 550

	
553 551
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
554 552
      public:
555 553

	
556 554
        NodeObserverProxy(Snapshot& _snapshot)
557 555
          : snapshot(_snapshot) {}
558 556

	
559 557
        using NodeNotifier::ObserverBase::attach;
560 558
        using NodeNotifier::ObserverBase::detach;
561 559
        using NodeNotifier::ObserverBase::attached;
562 560

	
563 561
      protected:
564 562

	
565 563
        virtual void add(const Node& node) {
566 564
          snapshot.addNode(node);
567 565
        }
568 566
        virtual void add(const std::vector<Node>& nodes) {
569 567
          for (int i = nodes.size() - 1; i >= 0; ++i) {
570 568
            snapshot.addNode(nodes[i]);
571 569
          }
572 570
        }
573 571
        virtual void erase(const Node& node) {
574 572
          snapshot.eraseNode(node);
575 573
        }
576 574
        virtual void erase(const std::vector<Node>& nodes) {
577 575
          for (int i = 0; i < int(nodes.size()); ++i) {
578 576
            snapshot.eraseNode(nodes[i]);
579 577
          }
580 578
        }
581 579
        virtual void build() {
582 580
          Node node;
583 581
          std::vector<Node> nodes;
584 582
          for (notifier()->first(node); node != INVALID;
585 583
               notifier()->next(node)) {
586 584
            nodes.push_back(node);
587 585
          }
588 586
          for (int i = nodes.size() - 1; i >= 0; --i) {
589 587
            snapshot.addNode(nodes[i]);
590 588
          }
591 589
        }
592 590
        virtual void clear() {
593 591
          Node node;
594 592
          for (notifier()->first(node); node != INVALID;
595 593
               notifier()->next(node)) {
596 594
            snapshot.eraseNode(node);
597 595
          }
598 596
        }
599 597

	
600 598
        Snapshot& snapshot;
601 599
      };
602 600

	
603 601
      class ArcObserverProxy : public ArcNotifier::ObserverBase {
604 602
      public:
605 603

	
606 604
        ArcObserverProxy(Snapshot& _snapshot)
607 605
          : snapshot(_snapshot) {}
608 606

	
609 607
        using ArcNotifier::ObserverBase::attach;
610 608
        using ArcNotifier::ObserverBase::detach;
611 609
        using ArcNotifier::ObserverBase::attached;
612 610

	
613 611
      protected:
614 612

	
615 613
        virtual void add(const Arc& arc) {
616 614
          snapshot.addArc(arc);
617 615
        }
618 616
        virtual void add(const std::vector<Arc>& arcs) {
619 617
          for (int i = arcs.size() - 1; i >= 0; ++i) {
620 618
            snapshot.addArc(arcs[i]);
621 619
          }
622 620
        }
623 621
        virtual void erase(const Arc& arc) {
624 622
          snapshot.eraseArc(arc);
625 623
        }
626 624
        virtual void erase(const std::vector<Arc>& arcs) {
627 625
          for (int i = 0; i < int(arcs.size()); ++i) {
628 626
            snapshot.eraseArc(arcs[i]);
629 627
          }
630 628
        }
631 629
        virtual void build() {
632 630
          Arc arc;
633 631
          std::vector<Arc> arcs;
634 632
          for (notifier()->first(arc); arc != INVALID;
635 633
               notifier()->next(arc)) {
Ignore white space 6 line context
... ...
@@ -359,314 +359,310 @@
359 359
    friend class SparseMap;
360 360
  public:
361 361

	
362 362
    typedef MapBase<K, V> Parent;
363 363
    /// Key type
364 364
    typedef typename Parent::Key Key;
365 365
    /// Value type
366 366
    typedef typename Parent::Value Value;
367 367
    /// Reference type
368 368
    typedef Value& Reference;
369 369
    /// Const reference type
370 370
    typedef const Value& ConstReference;
371 371

	
372 372
    typedef True ReferenceMapTag;
373 373

	
374 374
  private:
375 375

	
376 376
    typedef std::map<K, V, Compare> Map;
377 377
    Map _map;
378 378
    Value _value;
379 379

	
380 380
  public:
381 381

	
382 382
    /// \brief Constructor with specified default value.
383 383
    SparseMap(const Value &value = Value()) : _value(value) {}
384 384
    /// \brief Constructs the map from an appropriate \c std::map, and
385 385
    /// explicitly specifies a default value.
386 386
    template <typename V1, typename Comp1>
387 387
    SparseMap(const std::map<Key, V1, Comp1> &map,
388 388
              const Value &value = Value())
389 389
      : _map(map.begin(), map.end()), _value(value) {}
390 390

	
391 391
    /// \brief Constructs the map from another \ref SparseMap.
392 392
    template<typename V1, typename Comp1>
393 393
    SparseMap(const SparseMap<Key, V1, Comp1> &c)
394 394
      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
395 395

	
396 396
  private:
397 397

	
398 398
    SparseMap& operator=(const SparseMap&);
399 399

	
400 400
  public:
401 401

	
402 402
    ///\e
403 403
    Reference operator[](const Key &k) {
404 404
      typename Map::iterator it = _map.lower_bound(k);
405 405
      if (it != _map.end() && !_map.key_comp()(k, it->first))
406 406
        return it->second;
407 407
      else
408 408
        return _map.insert(it, std::make_pair(k, _value))->second;
409 409
    }
410 410

	
411 411
    ///\e
412 412
    ConstReference operator[](const Key &k) const {
413 413
      typename Map::const_iterator it = _map.find(k);
414 414
      if (it != _map.end())
415 415
        return it->second;
416 416
      else
417 417
        return _value;
418 418
    }
419 419

	
420 420
    ///\e
421 421
    void set(const Key &k, const Value &v) {
422 422
      typename Map::iterator it = _map.lower_bound(k);
423 423
      if (it != _map.end() && !_map.key_comp()(k, it->first))
424 424
        it->second = v;
425 425
      else
426 426
        _map.insert(it, std::make_pair(k, v));
427 427
    }
428 428

	
429 429
    ///\e
430 430
    void setAll(const Value &v) {
431 431
      _value = v;
432 432
      _map.clear();
433 433
    }
434 434
  };
435 435

	
436 436
  /// Returns a \ref SparseMap class
437 437

	
438 438
  /// This function just returns a \ref SparseMap class with specified
439 439
  /// default value.
440 440
  /// \relates SparseMap
441 441
  template<typename K, typename V, typename Compare>
442 442
  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
443 443
    return SparseMap<K, V, Compare>(value);
444 444
  }
445 445

	
446 446
  template<typename K, typename V>
447 447
  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
448 448
    return SparseMap<K, V, std::less<K> >(value);
449 449
  }
450 450

	
451 451
  /// \brief Returns a \ref SparseMap class created from an appropriate
452 452
  /// \c std::map
453 453

	
454 454
  /// This function just returns a \ref SparseMap class created from an
455 455
  /// appropriate \c std::map.
456 456
  /// \relates SparseMap
457 457
  template<typename K, typename V, typename Compare>
458 458
  inline SparseMap<K, V, Compare>
459 459
    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
460 460
  {
461 461
    return SparseMap<K, V, Compare>(map, value);
462 462
  }
463 463

	
464 464
  /// @}
465 465

	
466 466
  /// \addtogroup map_adaptors
467 467
  /// @{
468 468

	
469 469
  /// Composition of two maps
470 470

	
471 471
  /// This \ref concepts::ReadMap "read-only map" returns the
472 472
  /// composition of two given maps. That is to say, if \c m1 is of
473 473
  /// type \c M1 and \c m2 is of \c M2, then for
474 474
  /// \code
475 475
  ///   ComposeMap<M1, M2> cm(m1,m2);
476 476
  /// \endcode
477 477
  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
478 478
  ///
479 479
  /// The \c Key type of the map is inherited from \c M2 and the
480 480
  /// \c Value type is from \c M1.
481 481
  /// \c M2::Value must be convertible to \c M1::Key.
482 482
  ///
483 483
  /// The simplest way of using this map is through the composeMap()
484 484
  /// function.
485 485
  ///
486 486
  /// \sa CombineMap
487
  ///
488
  /// \todo Check the requirements.
489 487
  template <typename M1, typename M2>
490 488
  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
491 489
    const M1 &_m1;
492 490
    const M2 &_m2;
493 491
  public:
494 492
    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
495 493
    typedef typename Parent::Key Key;
496 494
    typedef typename Parent::Value Value;
497 495

	
498 496
    /// Constructor
499 497
    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
500 498

	
501 499
    /// \e
502 500
    typename MapTraits<M1>::ConstReturnValue
503 501
    operator[](const Key &k) const { return _m1[_m2[k]]; }
504 502
  };
505 503

	
506 504
  /// Returns a \ref ComposeMap class
507 505

	
508 506
  /// This function just returns a \ref ComposeMap class.
509 507
  ///
510 508
  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
511 509
  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
512 510
  /// will be equal to <tt>m1[m2[x]]</tt>.
513 511
  ///
514 512
  /// \relates ComposeMap
515 513
  template <typename M1, typename M2>
516 514
  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
517 515
    return ComposeMap<M1, M2>(m1, m2);
518 516
  }
519 517

	
520 518

	
521 519
  /// Combination of two maps using an STL (binary) functor.
522 520

	
523 521
  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
524 522
  /// binary functor and returns the combination of the two given maps
525 523
  /// using the functor.
526 524
  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
527 525
  /// and \c f is of \c F, then for
528 526
  /// \code
529 527
  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
530 528
  /// \endcode
531 529
  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
532 530
  ///
533 531
  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
534 532
  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
535 533
  /// \c M2::Value and \c M1::Value must be convertible to the
536 534
  /// corresponding input parameter of \c F and the return type of \c F
537 535
  /// must be convertible to \c V.
538 536
  ///
539 537
  /// The simplest way of using this map is through the combineMap()
540 538
  /// function.
541 539
  ///
542 540
  /// \sa ComposeMap
543
  ///
544
  /// \todo Check the requirements.
545 541
  template<typename M1, typename M2, typename F,
546 542
           typename V = typename F::result_type>
547 543
  class CombineMap : public MapBase<typename M1::Key, V> {
548 544
    const M1 &_m1;
549 545
    const M2 &_m2;
550 546
    F _f;
551 547
  public:
552 548
    typedef MapBase<typename M1::Key, V> Parent;
553 549
    typedef typename Parent::Key Key;
554 550
    typedef typename Parent::Value Value;
555 551

	
556 552
    /// Constructor
557 553
    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
558 554
      : _m1(m1), _m2(m2), _f(f) {}
559 555
    /// \e
560 556
    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
561 557
  };
562 558

	
563 559
  /// Returns a \ref CombineMap class
564 560

	
565 561
  /// This function just returns a \ref CombineMap class.
566 562
  ///
567 563
  /// For example, if \c m1 and \c m2 are both maps with \c double
568 564
  /// values, then
569 565
  /// \code
570 566
  ///   combineMap(m1,m2,std::plus<double>())
571 567
  /// \endcode
572 568
  /// is equivalent to
573 569
  /// \code
574 570
  ///   addMap(m1,m2)
575 571
  /// \endcode
576 572
  ///
577 573
  /// This function is specialized for adaptable binary function
578 574
  /// classes and C++ functions.
579 575
  ///
580 576
  /// \relates CombineMap
581 577
  template<typename M1, typename M2, typename F, typename V>
582 578
  inline CombineMap<M1, M2, F, V>
583 579
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
584 580
    return CombineMap<M1, M2, F, V>(m1,m2,f);
585 581
  }
586 582

	
587 583
  template<typename M1, typename M2, typename F>
588 584
  inline CombineMap<M1, M2, F, typename F::result_type>
589 585
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
590 586
    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
591 587
  }
592 588

	
593 589
  template<typename M1, typename M2, typename K1, typename K2, typename V>
594 590
  inline CombineMap<M1, M2, V (*)(K1, K2), V>
595 591
  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
596 592
    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
597 593
  }
598 594

	
599 595

	
600 596
  /// Converts an STL style (unary) functor to a map
601 597

	
602 598
  /// This \ref concepts::ReadMap "read-only map" returns the value
603 599
  /// of a given functor. Actually, it just wraps the functor and
604 600
  /// provides the \c Key and \c Value typedefs.
605 601
  ///
606 602
  /// Template parameters \c K and \c V will become its \c Key and
607 603
  /// \c Value. In most cases they have to be given explicitly because
608 604
  /// a functor typically does not provide \c argument_type and
609 605
  /// \c result_type typedefs.
610 606
  /// Parameter \c F is the type of the used functor.
611 607
  ///
612 608
  /// The simplest way of using this map is through the functorToMap()
613 609
  /// function.
614 610
  ///
615 611
  /// \sa MapToFunctor
616 612
  template<typename F,
617 613
           typename K = typename F::argument_type,
618 614
           typename V = typename F::result_type>
619 615
  class FunctorToMap : public MapBase<K, V> {
620 616
    F _f;
621 617
  public:
622 618
    typedef MapBase<K, V> Parent;
623 619
    typedef typename Parent::Key Key;
624 620
    typedef typename Parent::Value Value;
625 621

	
626 622
    /// Constructor
627 623
    FunctorToMap(const F &f = F()) : _f(f) {}
628 624
    /// \e
629 625
    Value operator[](const Key &k) const { return _f(k); }
630 626
  };
631 627

	
632 628
  /// Returns a \ref FunctorToMap class
633 629

	
634 630
  /// This function just returns a \ref FunctorToMap class.
635 631
  ///
636 632
  /// This function is specialized for adaptable binary function
637 633
  /// classes and C++ functions.
638 634
  ///
639 635
  /// \relates FunctorToMap
640 636
  template<typename K, typename V, typename F>
641 637
  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
642 638
    return FunctorToMap<F, K, V>(f);
643 639
  }
644 640

	
645 641
  template <typename F>
646 642
  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
647 643
    functorToMap(const F &f)
648 644
  {
649 645
    return FunctorToMap<F, typename F::argument_type,
650 646
      typename F::result_type>(f);
651 647
  }
652 648

	
653 649
  template <typename K, typename V>
654 650
  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
655 651
    return FunctorToMap<V (*)(K), K, V>(f);
656 652
  }
657 653

	
658 654

	
659 655
  /// Converts a map to an STL style (unary) functor
660 656

	
661 657
  /// This class converts a map to an STL style (unary) functor.
662 658
  /// That is it provides an <tt>operator()</tt> to read its values.
663 659
  ///
664 660
  /// For the sake of convenience it also works as a usual
665 661
  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
666 662
  /// and the \c Key and \c Value typedefs also exist.
667 663
  ///
668 664
  /// The simplest way of using this map is through the mapToFunctor()
669 665
  /// function.
670 666
  ///
671 667
  ///\sa FunctorToMap
672 668
  template <typename M>
Ignore white space 6 line context
... ...
@@ -696,257 +696,256 @@
696 696
    ///
697 697
    /// It returns a random real number from the range [0, b).
698 698
    template <typename Number>
699 699
    Number real(Number b) {
700 700
      return real<Number>() * b;
701 701
    }
702 702

	
703 703
    /// \brief Returns a random real number from the range [a, b)
704 704
    ///
705 705
    /// It returns a random real number from the range [a, b).
706 706
    template <typename Number>
707 707
    Number real(Number a, Number b) {
708 708
      return real<Number>() * (b - a) + a;
709 709
    }
710 710

	
711 711
    /// @}
712 712

	
713 713
    ///\name Uniform distributions
714 714
    ///
715 715
    /// @{
716 716

	
717 717
    /// \brief Returns a random real number from the range [0, 1)
718 718
    ///
719 719
    /// It returns a random double from the range [0, 1).
720 720
    double operator()() {
721 721
      return real<double>();
722 722
    }
723 723

	
724 724
    /// \brief Returns a random real number from the range [0, b)
725 725
    ///
726 726
    /// It returns a random real number from the range [0, b).
727 727
    template <typename Number>
728 728
    Number operator()(Number b) {
729 729
      return real<Number>() * b;
730 730
    }
731 731

	
732 732
    /// \brief Returns a random real number from the range [a, b)
733 733
    ///
734 734
    /// It returns a random real number from the range [a, b).
735 735
    template <typename Number>
736 736
    Number operator()(Number a, Number b) {
737 737
      return real<Number>() * (b - a) + a;
738 738
    }
739 739

	
740 740
    /// \brief Returns a random integer from a range
741 741
    ///
742 742
    /// It returns a random integer from the range {0, 1, ..., b - 1}.
743 743
    template <typename Number>
744 744
    Number integer(Number b) {
745 745
      return _random_bits::Mapping<Number, Word>::map(core, b);
746 746
    }
747 747

	
748 748
    /// \brief Returns a random integer from a range
749 749
    ///
750 750
    /// It returns a random integer from the range {a, a + 1, ..., b - 1}.
751 751
    template <typename Number>
752 752
    Number integer(Number a, Number b) {
753 753
      return _random_bits::Mapping<Number, Word>::map(core, b - a) + a;
754 754
    }
755 755

	
756 756
    /// \brief Returns a random integer from a range
757 757
    ///
758 758
    /// It returns a random integer from the range {0, 1, ..., b - 1}.
759 759
    template <typename Number>
760 760
    Number operator[](Number b) {
761 761
      return _random_bits::Mapping<Number, Word>::map(core, b);
762 762
    }
763 763

	
764 764
    /// \brief Returns a random non-negative integer
765 765
    ///
766 766
    /// It returns a random non-negative integer uniformly from the
767 767
    /// whole range of the current \c Number type. The default result
768 768
    /// type of this function is <tt>unsigned int</tt>.
769 769
    template <typename Number>
770 770
    Number uinteger() {
771 771
      return _random_bits::IntConversion<Number, Word>::convert(core);
772 772
    }
773 773

	
774 774
    /// @}
775 775

	
776 776
    unsigned int uinteger() {
777 777
      return uinteger<unsigned int>();
778 778
    }
779 779

	
780 780
    /// \brief Returns a random integer
781 781
    ///
782 782
    /// It returns a random integer uniformly from the whole range of
783 783
    /// the current \c Number type. The default result type of this
784 784
    /// function is \c int.
785 785
    template <typename Number>
786 786
    Number integer() {
787 787
      static const int nb = std::numeric_limits<Number>::digits +
788 788
        (std::numeric_limits<Number>::is_signed ? 1 : 0);
789 789
      return _random_bits::IntConversion<Number, Word, nb>::convert(core);
790 790
    }
791 791

	
792 792
    int integer() {
793 793
      return integer<int>();
794 794
    }
795 795

	
796 796
    /// \brief Returns a random bool
797 797
    ///
798 798
    /// It returns a random bool. The generator holds a buffer for
799 799
    /// random bits. Every time when it become empty the generator makes
800 800
    /// a new random word and fill the buffer up.
801 801
    bool boolean() {
802 802
      return bool_producer.convert(core);
803 803
    }
804 804

	
805 805
    /// @}
806 806

	
807 807
    ///\name Non-uniform distributions
808 808
    ///
809 809

	
810 810
    ///@{
811 811

	
812 812
    /// \brief Returns a random bool
813 813
    ///
814 814
    /// It returns a random bool with given probability of true result.
815 815
    bool boolean(double p) {
816 816
      return operator()() < p;
817 817
    }
818 818

	
819 819
    /// Standard Gauss distribution
820 820

	
821 821
    /// Standard Gauss distribution.
822 822
    /// \note The Cartesian form of the Box-Muller
823 823
    /// transformation is used to generate a random normal distribution.
824
    /// \todo Consider using the "ziggurat" method instead.
825 824
    double gauss()
826 825
    {
827 826
      double V1,V2,S;
828 827
      do {
829 828
        V1=2*real<double>()-1;
830 829
        V2=2*real<double>()-1;
831 830
        S=V1*V1+V2*V2;
832 831
      } while(S>=1);
833 832
      return std::sqrt(-2*std::log(S)/S)*V1;
834 833
    }
835 834
    /// Gauss distribution with given mean and standard deviation
836 835

	
837 836
    /// Gauss distribution with given mean and standard deviation.
838 837
    /// \sa gauss()
839 838
    double gauss(double mean,double std_dev)
840 839
    {
841 840
      return gauss()*std_dev+mean;
842 841
    }
843 842

	
844 843
    /// Exponential distribution with given mean
845 844

	
846 845
    /// This function generates an exponential distribution random number
847 846
    /// with mean <tt>1/lambda</tt>.
848 847
    ///
849 848
    double exponential(double lambda=1.0)
850 849
    {
851 850
      return -std::log(1.0-real<double>())/lambda;
852 851
    }
853 852

	
854 853
    /// Gamma distribution with given integer shape
855 854

	
856 855
    /// This function generates a gamma distribution random number.
857 856
    ///
858 857
    ///\param k shape parameter (<tt>k>0</tt> integer)
859 858
    double gamma(int k)
860 859
    {
861 860
      double s = 0;
862 861
      for(int i=0;i<k;i++) s-=std::log(1.0-real<double>());
863 862
      return s;
864 863
    }
865 864

	
866 865
    /// Gamma distribution with given shape and scale parameter
867 866

	
868 867
    /// This function generates a gamma distribution random number.
869 868
    ///
870 869
    ///\param k shape parameter (<tt>k>0</tt>)
871 870
    ///\param theta scale parameter
872 871
    ///
873 872
    double gamma(double k,double theta=1.0)
874 873
    {
875 874
      double xi,nu;
876 875
      const double delta = k-std::floor(k);
877 876
      const double v0=E/(E-delta);
878 877
      do {
879 878
        double V0=1.0-real<double>();
880 879
        double V1=1.0-real<double>();
881 880
        double V2=1.0-real<double>();
882 881
        if(V2<=v0)
883 882
          {
884 883
            xi=std::pow(V1,1.0/delta);
885 884
            nu=V0*std::pow(xi,delta-1.0);
886 885
          }
887 886
        else
888 887
          {
889 888
            xi=1.0-std::log(V1);
890 889
            nu=V0*std::exp(-xi);
891 890
          }
892 891
      } while(nu>std::pow(xi,delta-1.0)*std::exp(-xi));
893 892
      return theta*(xi+gamma(int(std::floor(k))));
894 893
    }
895 894

	
896 895
    /// Weibull distribution
897 896

	
898 897
    /// This function generates a Weibull distribution random number.
899 898
    ///
900 899
    ///\param k shape parameter (<tt>k>0</tt>)
901 900
    ///\param lambda scale parameter (<tt>lambda>0</tt>)
902 901
    ///
903 902
    double weibull(double k,double lambda)
904 903
    {
905 904
      return lambda*pow(-std::log(1.0-real<double>()),1.0/k);
906 905
    }
907 906

	
908 907
    /// Pareto distribution
909 908

	
910 909
    /// This function generates a Pareto distribution random number.
911 910
    ///
912 911
    ///\param k shape parameter (<tt>k>0</tt>)
913 912
    ///\param x_min location parameter (<tt>x_min>0</tt>)
914 913
    ///
915 914
    double pareto(double k,double x_min)
916 915
    {
917 916
      return exponential(gamma(k,1.0/x_min))+x_min;
918 917
    }
919 918

	
920 919
    /// Poisson distribution
921 920

	
922 921
    /// This function generates a Poisson distribution random number with
923 922
    /// parameter \c lambda.
924 923
    ///
925 924
    /// The probability mass function of this distribusion is
926 925
    /// \f[ \frac{e^{-\lambda}\lambda^k}{k!} \f]
927 926
    /// \note The algorithm is taken from the book of Donald E. Knuth titled
928 927
    /// ''Seminumerical Algorithms'' (1969). Its running time is linear in the
929 928
    /// return value.
930 929

	
931 930
    int poisson(double lambda)
932 931
    {
933 932
      const double l = std::exp(-lambda);
934 933
      int k=0;
935 934
      double p = 1.0;
936 935
      do {
937 936
        k++;
938 937
        p*=real<double>();
939 938
      } while (p>=l);
940 939
      return k-1;
941 940
    }
942 941

	
943 942
    ///@}
944 943

	
945 944
    ///\name Two dimensional distributions
946 945
    ///
947 946

	
948 947
    ///@{
949 948

	
950 949
    /// Uniform distribution on the full unit circle
951 950

	
952 951
    /// Uniform distribution on the full unit circle.
Ignore white space 6 line context
... ...
@@ -175,257 +175,256 @@
175 175
      arc._id = nodes[node._id].first_in;
176 176
    }
177 177

	
178 178
    void nextIn(Arc& arc) const {
179 179
      arc._id = arcs[arc._id].next_in;
180 180
    }
181 181

	
182 182
  };
183 183

	
184 184
  typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;
185 185

	
186 186
  ///\ingroup graphs
187 187
  ///
188 188
  ///\brief A smart directed graph class.
189 189
  ///
190 190
  ///This is a simple and fast digraph implementation.
191 191
  ///It is also quite memory efficient, but at the price
192 192
  ///that <b> it does support only limited (only stack-like)
193 193
  ///node and arc deletions</b>.
194 194
  ///It conforms to the \ref concepts::Digraph "Digraph concept" with
195 195
  ///an important extra feature that its maps are real \ref
196 196
  ///concepts::ReferenceMap "reference map"s.
197 197
  ///
198 198
  ///\sa concepts::Digraph.
199 199
  class SmartDigraph : public ExtendedSmartDigraphBase {
200 200
  public:
201 201

	
202 202
    typedef ExtendedSmartDigraphBase Parent;
203 203

	
204 204
  private:
205 205

	
206 206
    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
207 207

	
208 208
    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
209 209
    ///
210 210
    SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
211 211
    ///\brief Assignment of SmartDigraph to another one is \e not allowed.
212 212
    ///Use DigraphCopy() instead.
213 213

	
214 214
    ///Assignment of SmartDigraph to another one is \e not allowed.
215 215
    ///Use DigraphCopy() instead.
216 216
    void operator=(const SmartDigraph &) {}
217 217

	
218 218
  public:
219 219

	
220 220
    /// Constructor
221 221

	
222 222
    /// Constructor.
223 223
    ///
224 224
    SmartDigraph() {};
225 225

	
226 226
    ///Add a new node to the digraph.
227 227

	
228 228
    /// \return the new node.
229 229
    ///
230 230
    Node addNode() { return Parent::addNode(); }
231 231

	
232 232
    ///Add a new arc to the digraph.
233 233

	
234 234
    ///Add a new arc to the digraph with source node \c s
235 235
    ///and target node \c t.
236 236
    ///\return the new arc.
237 237
    Arc addArc(const Node& s, const Node& t) {
238 238
      return Parent::addArc(s, t);
239 239
    }
240 240

	
241 241
    /// \brief Using this it is possible to avoid the superfluous memory
242 242
    /// allocation.
243 243

	
244 244
    /// Using this it is possible to avoid the superfluous memory
245 245
    /// allocation: if you know that the digraph you want to build will
246 246
    /// be very large (e.g. it will contain millions of nodes and/or arcs)
247 247
    /// then it is worth reserving space for this amount before starting
248 248
    /// to build the digraph.
249 249
    /// \sa reserveArc
250 250
    void reserveNode(int n) { nodes.reserve(n); };
251 251

	
252 252
    /// \brief Using this it is possible to avoid the superfluous memory
253 253
    /// allocation.
254 254

	
255 255
    /// Using this it is possible to avoid the superfluous memory
256 256
    /// allocation: if you know that the digraph you want to build will
257 257
    /// be very large (e.g. it will contain millions of nodes and/or arcs)
258 258
    /// then it is worth reserving space for this amount before starting
259 259
    /// to build the digraph.
260 260
    /// \sa reserveNode
261 261
    void reserveArc(int m) { arcs.reserve(m); };
262 262

	
263 263
    /// \brief Node validity check
264 264
    ///
265 265
    /// This function gives back true if the given node is valid,
266 266
    /// ie. it is a real node of the graph.
267 267
    ///
268 268
    /// \warning A removed node (using Snapshot) could become valid again
269 269
    /// when new nodes are added to the graph.
270 270
    bool valid(Node n) const { return Parent::valid(n); }
271 271

	
272 272
    /// \brief Arc validity check
273 273
    ///
274 274
    /// This function gives back true if the given arc is valid,
275 275
    /// ie. it is a real arc of the graph.
276 276
    ///
277 277
    /// \warning A removed arc (using Snapshot) could become valid again
278 278
    /// when new arcs are added to the graph.
279 279
    bool valid(Arc a) const { return Parent::valid(a); }
280 280

	
281 281
    ///Clear the digraph.
282 282

	
283 283
    ///Erase all the nodes and arcs from the digraph.
284 284
    ///
285 285
    void clear() {
286 286
      Parent::clear();
287 287
    }
288 288

	
289 289
    ///Split a node.
290 290

	
291 291
    ///This function splits a node. First a new node is added to the digraph,
292 292
    ///then the source of each outgoing arc of \c n is moved to this new node.
293 293
    ///If \c connect is \c true (this is the default value), then a new arc
294 294
    ///from \c n to the newly created node is also added.
295 295
    ///\return The newly created node.
296 296
    ///
297 297
    ///\note The <tt>Arc</tt>s
298 298
    ///referencing a moved arc remain
299 299
    ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
300 300
    ///may be invalidated.
301 301
    ///\warning This functionality cannot be used together with the Snapshot
302 302
    ///feature.
303
    ///\todo It could be implemented in a bit faster way.
304 303
    Node split(Node n, bool connect = true)
305 304
    {
306 305
      Node b = addNode();
307 306
      nodes[b._id].first_out=nodes[n._id].first_out;
308 307
      nodes[n._id].first_out=-1;
309 308
      for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
310 309
      if(connect) addArc(n,b);
311 310
      return b;
312 311
    }
313 312

	
314 313
  public:
315 314

	
316 315
    class Snapshot;
317 316

	
318 317
  protected:
319 318

	
320 319
    void restoreSnapshot(const Snapshot &s)
321 320
    {
322 321
      while(s.arc_num<arcs.size()) {
323 322
        Arc arc = arcFromId(arcs.size()-1);
324 323
        Parent::notifier(Arc()).erase(arc);
325 324
        nodes[arcs.back().source].first_out=arcs.back().next_out;
326 325
        nodes[arcs.back().target].first_in=arcs.back().next_in;
327 326
        arcs.pop_back();
328 327
      }
329 328
      while(s.node_num<nodes.size()) {
330 329
        Node node = nodeFromId(nodes.size()-1);
331 330
        Parent::notifier(Node()).erase(node);
332 331
        nodes.pop_back();
333 332
      }
334 333
    }
335 334

	
336 335
  public:
337 336

	
338 337
    ///Class to make a snapshot of the digraph and to restrore to it later.
339 338

	
340 339
    ///Class to make a snapshot of the digraph and to restrore to it later.
341 340
    ///
342 341
    ///The newly added nodes and arcs can be removed using the
343 342
    ///restore() function.
344 343
    ///\note After you restore a state, you cannot restore
345 344
    ///a later state, in other word you cannot add again the arcs deleted
346 345
    ///by restore() using another one Snapshot instance.
347 346
    ///
348 347
    ///\warning If you do not use correctly the snapshot that can cause
349 348
    ///either broken program, invalid state of the digraph, valid but
350 349
    ///not the restored digraph or no change. Because the runtime performance
351 350
    ///the validity of the snapshot is not stored.
352 351
    class Snapshot
353 352
    {
354 353
      SmartDigraph *_graph;
355 354
    protected:
356 355
      friend class SmartDigraph;
357 356
      unsigned int node_num;
358 357
      unsigned int arc_num;
359 358
    public:
360 359
      ///Default constructor.
361 360

	
362 361
      ///Default constructor.
363 362
      ///To actually make a snapshot you must call save().
364 363
      ///
365 364
      Snapshot() : _graph(0) {}
366 365
      ///Constructor that immediately makes a snapshot
367 366

	
368 367
      ///This constructor immediately makes a snapshot of the digraph.
369 368
      ///\param _g The digraph we make a snapshot of.
370 369
      Snapshot(SmartDigraph &graph) : _graph(&graph) {
371 370
        node_num=_graph->nodes.size();
372 371
        arc_num=_graph->arcs.size();
373 372
      }
374 373

	
375 374
      ///Make a snapshot.
376 375

	
377 376
      ///Make a snapshot of the digraph.
378 377
      ///
379 378
      ///This function can be called more than once. In case of a repeated
380 379
      ///call, the previous snapshot gets lost.
381 380
      ///\param _g The digraph we make the snapshot of.
382 381
      void save(SmartDigraph &graph)
383 382
      {
384 383
        _graph=&graph;
385 384
        node_num=_graph->nodes.size();
386 385
        arc_num=_graph->arcs.size();
387 386
      }
388 387

	
389 388
      ///Undo the changes until a snapshot.
390 389

	
391 390
      ///Undo the changes until a snapshot created by save().
392 391
      ///
393 392
      ///\note After you restored a state, you cannot restore
394 393
      ///a later state, in other word you cannot add again the arcs deleted
395 394
      ///by restore().
396 395
      void restore()
397 396
      {
398 397
        _graph->restoreSnapshot(*this);
399 398
      }
400 399
    };
401 400
  };
402 401

	
403 402

	
404 403
  class SmartGraphBase {
405 404

	
406 405
  protected:
407 406

	
408 407
    struct NodeT {
409 408
      int first_out;
410 409
    };
411 410

	
412 411
    struct ArcT {
413 412
      int target;
414 413
      int next_out;
415 414
    };
416 415

	
417 416
    std::vector<NodeT> nodes;
418 417
    std::vector<ArcT> arcs;
419 418

	
420 419
    int first_free_arc;
421 420

	
422 421
  public:
423 422

	
424 423
    typedef SmartGraphBase Digraph;
425 424

	
426 425
    class Node;
427 426
    class Arc;
428 427
    class Edge;
429 428

	
430 429
    class Node {
431 430
      friend class SmartGraphBase;
Ignore white space 6 line context
... ...
@@ -167,410 +167,408 @@
167 167
      TimeStamp t(*this);
168 168
      return t*=b;
169 169
    }
170 170
    friend TimeStamp operator*(double b,const TimeStamp &t);
171 171
    ///\e
172 172
    TimeStamp &operator/=(double b)
173 173
    {
174 174
      utime/=b;
175 175
      stime/=b;
176 176
      cutime/=b;
177 177
      cstime/=b;
178 178
      rtime/=b;
179 179
      return *this;
180 180
    }
181 181
    ///\e
182 182
    TimeStamp operator/(double b) const
183 183
    {
184 184
      TimeStamp t(*this);
185 185
      return t/=b;
186 186
    }
187 187
    ///The time ellapsed since the last call of stamp()
188 188
    TimeStamp ellapsed() const
189 189
    {
190 190
      TimeStamp t(NULL);
191 191
      return t-*this;
192 192
    }
193 193

	
194 194
    friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
195 195

	
196 196
    ///Gives back the user time of the process
197 197
    double userTime() const
198 198
    {
199 199
      return utime;
200 200
    }
201 201
    ///Gives back the system time of the process
202 202
    double systemTime() const
203 203
    {
204 204
      return stime;
205 205
    }
206 206
    ///Gives back the user time of the process' children
207 207

	
208 208
    ///\note On <tt>WIN32</tt> platform this value is not calculated.
209 209
    ///
210 210
    double cUserTime() const
211 211
    {
212 212
      return cutime;
213 213
    }
214 214
    ///Gives back the user time of the process' children
215 215

	
216 216
    ///\note On <tt>WIN32</tt> platform this value is not calculated.
217 217
    ///
218 218
    double cSystemTime() const
219 219
    {
220 220
      return cstime;
221 221
    }
222 222
    ///Gives back the real time
223 223
    double realTime() const {return rtime;}
224 224
  };
225 225

	
226 226
  TimeStamp operator*(double b,const TimeStamp &t)
227 227
  {
228 228
    return t*b;
229 229
  }
230 230

	
231 231
  ///Prints the time counters
232 232

	
233 233
  ///Prints the time counters in the following form:
234 234
  ///
235 235
  /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
236 236
  ///
237 237
  /// where the values are the
238 238
  /// \li \c u: user cpu time,
239 239
  /// \li \c s: system cpu time,
240 240
  /// \li \c cu: user cpu time of children,
241 241
  /// \li \c cs: system cpu time of children,
242 242
  /// \li \c real: real time.
243 243
  /// \relates TimeStamp
244 244
  /// \note On <tt>WIN32</tt> platform the cummulative values are not
245 245
  /// calculated.
246 246
  inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
247 247
  {
248 248
    os << "u: " << t.userTime() <<
249 249
      "s, s: " << t.systemTime() <<
250 250
      "s, cu: " << t.cUserTime() <<
251 251
      "s, cs: " << t.cSystemTime() <<
252 252
      "s, real: " << t.realTime() << "s";
253 253
    return os;
254 254
  }
255 255

	
256 256
  ///Class for measuring the cpu time and real time usage of the process
257 257

	
258 258
  ///Class for measuring the cpu time and real time usage of the process.
259 259
  ///It is quite easy-to-use, here is a short example.
260 260
  ///\code
261 261
  /// #include<lemon/time_measure.h>
262 262
  /// #include<iostream>
263 263
  ///
264 264
  /// int main()
265 265
  /// {
266 266
  ///
267 267
  ///   ...
268 268
  ///
269 269
  ///   Timer t;
270 270
  ///   doSomething();
271 271
  ///   std::cout << t << '\n';
272 272
  ///   t.restart();
273 273
  ///   doSomethingElse();
274 274
  ///   std::cout << t << '\n';
275 275
  ///
276 276
  ///   ...
277 277
  ///
278 278
  /// }
279 279
  ///\endcode
280 280
  ///
281 281
  ///The \ref Timer can also be \ref stop() "stopped" and
282 282
  ///\ref start() "started" again, so it is possible to compute collected
283 283
  ///running times.
284 284
  ///
285 285
  ///\warning Depending on the operation system and its actual configuration
286 286
  ///the time counters have a certain (10ms on a typical Linux system)
287 287
  ///granularity.
288 288
  ///Therefore this tool is not appropriate to measure very short times.
289 289
  ///Also, if you start and stop the timer very frequently, it could lead to
290 290
  ///distorted results.
291 291
  ///
292 292
  ///\note If you want to measure the running time of the execution of a certain
293 293
  ///function, consider the usage of \ref TimeReport instead.
294 294
  ///
295
  ///\todo This shouldn't be Unix (Linux) specific.
296 295
  ///\sa TimeReport
297 296
  class Timer
298 297
  {
299 298
    int _running; //Timer is running iff _running>0; (_running>=0 always holds)
300 299
    TimeStamp start_time; //This is the relativ start-time if the timer
301 300
                          //is _running, the collected _running time otherwise.
302 301

	
303 302
    void _reset() {if(_running) start_time.stamp(); else start_time.reset();}
304 303

	
305 304
  public:
306 305
    ///Constructor.
307 306

	
308 307
    ///\param run indicates whether or not the timer starts immediately.
309 308
    ///
310 309
    Timer(bool run=true) :_running(run) {_reset();}
311 310

	
312 311
    ///\name Control the state of the timer
313 312
    ///Basically a Timer can be either running or stopped,
314 313
    ///but it provides a bit finer control on the execution.
315 314
    ///The \ref Timer also counts the number of \ref start()
316 315
    ///executions, and is stops only after the same amount (or more)
317 316
    ///\ref stop() "stop()"s. This can be useful e.g. to compute
318 317
    ///the running time
319 318
    ///of recursive functions.
320 319
    ///
321 320

	
322 321
    ///@{
323 322

	
324 323
    ///Reset and stop the time counters
325 324

	
326 325
    ///This function resets and stops the time counters
327 326
    ///\sa restart()
328 327
    void reset()
329 328
    {
330 329
      _running=0;
331 330
      _reset();
332 331
    }
333 332

	
334 333
    ///Start the time counters
335 334

	
336 335
    ///This function starts the time counters.
337 336
    ///
338 337
    ///If the timer is started more than ones, it will remain running
339 338
    ///until the same amount of \ref stop() is called.
340 339
    ///\sa stop()
341 340
    void start()
342 341
    {
343 342
      if(_running) _running++;
344 343
      else {
345 344
        _running=1;
346 345
        TimeStamp t;
347 346
        t.stamp();
348 347
        start_time=t-start_time;
349 348
      }
350 349
    }
351 350

	
352 351

	
353 352
    ///Stop the time counters
354 353

	
355 354
    ///This function stops the time counters. If start() was executed more than
356 355
    ///once, then the same number of stop() execution is necessary the really
357 356
    ///stop the timer.
358 357
    ///
359 358
    ///\sa halt()
360 359
    ///\sa start()
361 360
    ///\sa restart()
362 361
    ///\sa reset()
363 362

	
364 363
    void stop()
365 364
    {
366 365
      if(_running && !--_running) {
367 366
        TimeStamp t;
368 367
        t.stamp();
369 368
        start_time=t-start_time;
370 369
      }
371 370
    }
372 371

	
373 372
    ///Halt (i.e stop immediately) the time counters
374 373

	
375 374
    ///This function stops immediately the time counters, i.e. <tt>t.halt()</tt>
376 375
    ///is a faster
377 376
    ///equivalent of the following.
378 377
    ///\code
379 378
    ///  while(t.running()) t.stop()
380 379
    ///\endcode
381 380
    ///
382 381
    ///
383 382
    ///\sa stop()
384 383
    ///\sa restart()
385 384
    ///\sa reset()
386 385

	
387 386
    void halt()
388 387
    {
389 388
      if(_running) {
390 389
        _running=0;
391 390
        TimeStamp t;
392 391
        t.stamp();
393 392
        start_time=t-start_time;
394 393
      }
395 394
    }
396 395

	
397 396
    ///Returns the running state of the timer
398 397

	
399 398
    ///This function returns the number of stop() exections that is
400 399
    ///necessary to really stop the timer.
401 400
    ///For example the timer
402 401
    ///is running if and only if the return value is \c true
403 402
    ///(i.e. greater than
404 403
    ///zero).
405 404
    int running()  { return _running; }
406 405

	
407 406

	
408 407
    ///Restart the time counters
409 408

	
410 409
    ///This function is a shorthand for
411 410
    ///a reset() and a start() calls.
412 411
    ///
413 412
    void restart()
414 413
    {
415 414
      reset();
416 415
      start();
417 416
    }
418 417

	
419 418
    ///@}
420 419

	
421 420
    ///\name Query Functions for the ellapsed time
422 421

	
423 422
    ///@{
424 423

	
425 424
    ///Gives back the ellapsed user time of the process
426 425
    double userTime() const
427 426
    {
428 427
      return operator TimeStamp().userTime();
429 428
    }
430 429
    ///Gives back the ellapsed system time of the process
431 430
    double systemTime() const
432 431
    {
433 432
      return operator TimeStamp().systemTime();
434 433
    }
435 434
    ///Gives back the ellapsed user time of the process' children
436 435

	
437 436
    ///\note On <tt>WIN32</tt> platform this value is not calculated.
438 437
    ///
439 438
    double cUserTime() const
440 439
    {
441 440
      return operator TimeStamp().cUserTime();
442 441
    }
443 442
    ///Gives back the ellapsed user time of the process' children
444 443

	
445 444
    ///\note On <tt>WIN32</tt> platform this value is not calculated.
446 445
    ///
447 446
    double cSystemTime() const
448 447
    {
449 448
      return operator TimeStamp().cSystemTime();
450 449
    }
451 450
    ///Gives back the ellapsed real time
452 451
    double realTime() const
453 452
    {
454 453
      return operator TimeStamp().realTime();
455 454
    }
456 455
    ///Computes the ellapsed time
457 456

	
458 457
    ///This conversion computes the ellapsed time, therefore you can print
459 458
    ///the ellapsed time like this.
460 459
    ///\code
461 460
    ///  Timer t;
462 461
    ///  doSomething();
463 462
    ///  std::cout << t << '\n';
464 463
    ///\endcode
465 464
    operator TimeStamp () const
466 465
    {
467 466
      TimeStamp t;
468 467
      t.stamp();
469 468
      return _running?t-start_time:start_time;
470 469
    }
471 470

	
472 471

	
473 472
    ///@}
474 473
  };
475 474

	
476 475
  ///Same as \ref Timer but prints a report on destruction.
477 476

	
478 477
  ///Same as \ref Timer but prints a report on destruction.
479 478
  ///This example shows its usage.
480 479
  ///\code
481 480
  ///  void myAlg(ListGraph &g,int n)
482 481
  ///  {
483 482
  ///    TimeReport tr("Running time of myAlg: ");
484 483
  ///    ... //Here comes the algorithm
485 484
  ///  }
486 485
  ///\endcode
487 486
  ///
488 487
  ///\sa Timer
489 488
  ///\sa NoTimeReport
490
  ///\todo There is no test case for this
491 489
  class TimeReport : public Timer
492 490
  {
493 491
    std::string _title;
494 492
    std::ostream &_os;
495 493
  public:
496 494
    ///\e
497 495

	
498 496
    ///\param title This text will be printed before the ellapsed time.
499 497
    ///\param os The stream to print the report to.
500 498
    ///\param run Sets whether the timer should start immediately.
501 499

	
502 500
    TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true)
503 501
      : Timer(run), _title(title), _os(os){}
504 502
    ///\e Prints the ellapsed time on destruction.
505 503
    ~TimeReport()
506 504
    {
507 505
      _os << _title << *this << std::endl;
508 506
    }
509 507
  };
510 508

	
511 509
  ///'Do nothing' version of \ref TimeReport
512 510

	
513 511
  ///\sa TimeReport
514 512
  ///
515 513
  class NoTimeReport
516 514
  {
517 515
  public:
518 516
    ///\e
519 517
    NoTimeReport(std::string,std::ostream &,bool) {}
520 518
    ///\e
521 519
    NoTimeReport(std::string,std::ostream &) {}
522 520
    ///\e
523 521
    NoTimeReport(std::string) {}
524 522
    ///\e Do nothing.
525 523
    ~NoTimeReport() {}
526 524

	
527 525
    operator TimeStamp () const { return TimeStamp(); }
528 526
    void reset() {}
529 527
    void start() {}
530 528
    void stop() {}
531 529
    void halt() {}
532 530
    int running() { return 0; }
533 531
    void restart() {}
534 532
    double userTime() const { return 0; }
535 533
    double systemTime() const { return 0; }
536 534
    double cUserTime() const { return 0; }
537 535
    double cSystemTime() const { return 0; }
538 536
    double realTime() const { return 0; }
539 537
  };
540 538

	
541 539
  ///Tool to measure the running time more exactly.
542 540

	
543 541
  ///This function calls \c f several times and returns the average
544 542
  ///running time. The number of the executions will be choosen in such a way
545 543
  ///that the full real running time will be roughly between \c min_time
546 544
  ///and <tt>2*min_time</tt>.
547 545
  ///\param f the function object to be measured.
548 546
  ///\param min_time the minimum total running time.
549 547
  ///\retval num if it is not \c NULL, then the actual
550 548
  ///        number of execution of \c f will be written into <tt>*num</tt>.
551 549
  ///\retval full_time if it is not \c NULL, then the actual
552 550
  ///        total running time will be written into <tt>*full_time</tt>.
553 551
  ///\return The average running time of \c f.
554 552

	
555 553
  template<class F>
556 554
  TimeStamp runningTimeTest(F f,double min_time=10,unsigned int *num = NULL,
557 555
                            TimeStamp *full_time=NULL)
558 556
  {
559 557
    TimeStamp full;
560 558
    unsigned int total=0;
561 559
    Timer t;
562 560
    for(unsigned int tn=1;tn <= 1U<<31 && full.realTime()<=min_time; tn*=2) {
563 561
      for(;total<tn;total++) f();
564 562
      full=t;
565 563
    }
566 564
    if(num) *num=total;
567 565
    if(full_time) *full_time=full;
568 566
    return full/total;
569 567
  }
570 568

	
571 569
  /// @}
572 570

	
573 571

	
574 572
} //namespace lemon
575 573

	
576 574
#endif //LEMON_TIME_MEASURE_H
Ignore white space 6 line context
1 1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2
 *
3 3
 * This file is a part of LEMON, a generic C++ optimization library.
4 4
 *
5 5
 * Copyright (C) 2003-2008
6 6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8
 *
9 9
 * Permission to use, modify and distribute this software is granted
10 10
 * provided that this copyright notice appears in all copies. For
11 11
 * precise terms see the accompanying LICENSE file.
12 12
 *
13 13
 * This software is provided "AS IS" with no warranty of any kind,
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_TOLERANCE_H
20 20
#define LEMON_TOLERANCE_H
21 21

	
22 22
///\ingroup misc
23 23
///\file
24 24
///\brief A basic tool to handle the anomalies of calculation with
25 25
///floating point numbers.
26 26
///
27
///\todo It should be in a module like "Basic tools"
28

	
29 27

	
30 28
namespace lemon {
31 29

	
32 30
  /// \addtogroup misc
33 31
  /// @{
34 32

	
35 33
  ///\brief A class to provide a basic way to
36 34
  ///handle the comparison of numbers that are obtained
37 35
  ///as a result of a probably inexact computation.
38 36
  ///
39 37
  ///\ref Tolerance is a class to provide a basic way to
40 38
  ///handle the comparison of numbers that are obtained
41 39
  ///as a result of a probably inexact computation.
42 40
  ///
43 41
  ///This is an abstract class, it should be specialized for all
44 42
  ///numerical data types. These specialized classes like
45 43
  ///Tolerance<double> may offer additional tuning parameters.
46 44
  ///
47 45
  ///\sa Tolerance<float>
48 46
  ///\sa Tolerance<double>
49 47
  ///\sa Tolerance<long double>
50 48
  ///\sa Tolerance<int>
51 49
  ///\sa Tolerance<long long int>
52 50
  ///\sa Tolerance<unsigned int>
53 51
  ///\sa Tolerance<unsigned long long int>
54 52

	
55 53
  template<class T>
56 54
  class Tolerance
57 55
  {
58 56
  public:
59 57
    typedef T Value;
60 58

	
61 59
    ///\name Comparisons
62 60
    ///The concept is that these bool functions return \c true only if
63 61
    ///the related comparisons hold even if some numerical error appeared
64 62
    ///during the computations.
65 63

	
66 64
    ///@{
67 65

	
68 66
    ///Returns \c true if \c a is \e surely strictly less than \c b
69 67
    static bool less(Value a,Value b) {return false;}
70 68
    ///Returns \c true if \c a is \e surely different from \c b
71 69
    static bool different(Value a,Value b) {return false;}
72 70
    ///Returns \c true if \c a is \e surely positive
73 71
    static bool positive(Value a) {return false;}
74 72
    ///Returns \c true if \c a is \e surely negative
75 73
    static bool negative(Value a) {return false;}
76 74
    ///Returns \c true if \c a is \e surely non-zero
77 75
    static bool nonZero(Value a) {return false;}
78 76

	
79 77
    ///@}
80 78

	
81 79
    ///Returns the zero value.
82 80
    static Value zero() {return T();}
83 81

	
84 82
    //   static bool finite(Value a) {}
85 83
    //   static Value big() {}
86 84
    //   static Value negativeBig() {}
87 85
  };
88 86

	
89 87

	
90 88
  ///Float specialization of Tolerance.
91 89

	
92 90
  ///Float specialization of Tolerance.
93 91
  ///\sa Tolerance
94 92
  ///\relates Tolerance
95 93
  template<>
96 94
  class Tolerance<float>
97 95
  {
98 96
    static float def_epsilon;
99 97
    float _epsilon;
100 98
  public:
101 99
    ///\e
102 100
    typedef float Value;
103 101

	
104 102
    ///Constructor setting the epsilon tolerance to the default value.
105 103
    Tolerance() : _epsilon(def_epsilon) {}
106 104
    ///Constructor setting the epsilon tolerance to the given value.
107 105
    Tolerance(float e) : _epsilon(e) {}
108 106

	
109 107
    ///Returns the epsilon value.
110 108
    Value epsilon() const {return _epsilon;}
111 109
    ///Sets the epsilon value.
112 110
    void epsilon(Value e) {_epsilon=e;}
113 111

	
114 112
    ///Returns the default epsilon value.
115 113
    static Value defaultEpsilon() {return def_epsilon;}
116 114
    ///Sets the default epsilon value.
117 115
    static void defaultEpsilon(Value e) {def_epsilon=e;}
118 116

	
119 117
    ///\name Comparisons
120 118
    ///See \ref lemon::Tolerance "Tolerance" for more details.
121 119

	
122 120
    ///@{
123 121

	
124 122
    ///Returns \c true if \c a is \e surely strictly less than \c b
125 123
    bool less(Value a,Value b) const {return a+_epsilon<b;}
126 124
    ///Returns \c true if \c a is \e surely different from \c b
127 125
    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }
128 126
    ///Returns \c true if \c a is \e surely positive
129 127
    bool positive(Value a) const { return _epsilon<a; }
130 128
    ///Returns \c true if \c a is \e surely negative
131 129
    bool negative(Value a) const { return -_epsilon>a; }
132 130
    ///Returns \c true if \c a is \e surely non-zero
133 131
    bool nonZero(Value a) const { return positive(a)||negative(a); }
134 132

	
135 133
    ///@}
136 134

	
137 135
    ///Returns zero
138 136
    static Value zero() {return 0;}
139 137
  };
140 138

	
141 139
  ///Double specialization of Tolerance.
142 140

	
143 141
  ///Double specialization of Tolerance.
144 142
  ///\sa Tolerance
145 143
  ///\relates Tolerance
146 144
  template<>
147 145
  class Tolerance<double>
148 146
  {
149 147
    static double def_epsilon;
150 148
    double _epsilon;
151 149
  public:
152 150
    ///\e
153 151
    typedef double Value;
154 152

	
155 153
    ///Constructor setting the epsilon tolerance to the default value.
156 154
    Tolerance() : _epsilon(def_epsilon) {}
0 comments (0 inline)