LEMON/LEMON-official Changeset - r184:716b220697a0

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r184:716b220697a0

« 183:0c6556

185:33e45a »

r184:716b220697a0

Thu, 27 Mar 2008 16:27:23

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Fix gcc-4.3 compilation errors and warnings

0 6 0

default

6 files changed with 11 insertions and 10 deletions:

lemon/bits/bezier.h

lemon/bits/traits.h

lemon/dijkstra.h

lemon/graph_to_eps.h

lemon/list_graph.h

test/test_tools.h

↑ Collapse diff ↑

lemon/bits/bezier.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BEZIER_H
 		#define LEMON_BEZIER_H
 		///\ingroup misc
 		///\file
 		///\brief Classes to compute with Bezier curves.
 		///
 		///Up to now this file is used internally by \ref graph_to_eps.h
 		#include<lemon/dim2.h>
 		namespace lemon {
 		  namespace dim2 {
 		class BezierBase {
 		public:
 		  typedef Point<double> Point;
+		  typedef lemon::dim2::Point<double> Point;
 		protected:
 		  static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;}
 		};
 		class Bezier1 : public BezierBase
+		{
 		public:
 		  Point p1,p2;
 		  Bezier1() {}
 		  Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {}
 		  Point operator()(double t) const
+		  {
 		    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 		    return conv(p1,p2,t);
+		  }
 		  Bezier1 before(double t) const
+		  {
 		    return Bezier1(p1,conv(p1,p2,t));
+		  }
 		  Bezier1 after(double t) const
+		  {
 		    return Bezier1(conv(p1,p2,t),p2);
+		  }
 		  Bezier1 revert() const { return Bezier1(p2,p1);}
 		  Bezier1 operator()(double a,double b) const { return before(b).after(a/b); }
 		  Point grad() const { return p2-p1; }
 		  Point norm() const { return rot90(p2-p1); }
 		  Point grad(double) const { return grad(); }
 		  Point norm(double t) const { return rot90(grad(t)); }
 		};
 		class Bezier2 : public BezierBase
+		{
 		public:
 		  Point p1,p2,p3;
 		  Bezier2() {}
 		  Bezier2(Point _p1, Point _p2, Point _p3) :p1(_p1), p2(_p2), p3(_p3) {}
 		  Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {}
 		  Point operator()(double t) const
+		  {
 		    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 		    return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3;
+		  }
 		  Bezier2 before(double t) const
+		  {
 		    Point q(conv(p1,p2,t));
 		    Point r(conv(p2,p3,t));
 		    return Bezier2(p1,q,conv(q,r,t));
+		  }
 		  Bezier2 after(double t) const
+		  {
 		    Point q(conv(p1,p2,t));
 		    Point r(conv(p2,p3,t));
 		    return Bezier2(conv(q,r,t),r,p3);
+		  }
 		  Bezier2 revert() const { return Bezier2(p3,p2,p1);}
 		  Bezier2 operator()(double a,double b) const { return before(b).after(a/b); }
 		  Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); }
 		  Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); }
 		  Point grad(double t) const { return grad()(t); }
 		  Point norm(double t) const { return rot90(grad(t)); }
 		};
 		class Bezier3 : public BezierBase
+		{
 		public:
 		  Point p1,p2,p3,p4;
 		  Bezier3() {}
 		  Bezier3(Point _p1, Point _p2, Point _p3, Point _p4)
 		    : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}
 		  Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)),
 					      p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}
 		  Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)),
 					      p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}
 		  Point operator()(double t) const
+		    {
 		      //    return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t);
 		      return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+
 			(3*t*t*(1-t))*p3+(t*t*t)*p4;
+		    }
 		  Bezier3 before(double t) const
+		    {
 		      Point p(conv(p1,p2,t));
 		      Point q(conv(p2,p3,t));
 		      Point r(conv(p3,p4,t));
 		      Point a(conv(p,q,t));
 		      Point b(conv(q,r,t));
 		      Point c(conv(a,b,t));
 		      return Bezier3(p1,p,a,c);
+		    }
 		  Bezier3 after(double t) const
+		    {
 		      Point p(conv(p1,p2,t));
 		      Point q(conv(p2,p3,t));
 		      Point r(conv(p3,p4,t));
 		      Point a(conv(p,q,t));
 		      Point b(conv(q,r,t));
 		      Point c(conv(a,b,t));
 		      return Bezier3(c,b,r,p4);
+		    }
 		  Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);}
 		  Bezier3 operator()(double a,double b) const { return before(b).after(a/b); }
 		  Bezier2 grad() const { return Bezier2(3.0*(p2-p1),3.0*(p3-p2),3.0*(p4-p3)); }
 		  Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1),
 .0*rot90(p3-p2),
 .0*rot90(p4-p3)); }
 		  Point grad(double t) const { return grad()(t); }
 		  Point norm(double t) const { return rot90(grad(t)); }
 		  template<class R,class F,class S,class D>
 		  R recSplit(F &_f,const S &_s,D _d) const
+		  {
 		    const Point a=(p1+p2)/2;
 		    const Point b=(p2+p3)/2;
 		    const Point c=(p3+p4)/2;
 		    const Point d=(a+b)/2;
 		    const Point e=(b+c)/2;
 		    const Point f=(d+e)/2;
 		    R f1=_f(Bezier3(p1,a,d,e),_d);
 		    R f2=_f(Bezier3(e,d,c,p4),_d);
 		    return _s(f1,f2);
+		  }
 		};
 		} //END OF NAMESPACE dim2
 		} //END OF NAMESPACE lemon
 		#endif // LEMON_BEZIER_H

lemon/bits/traits.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_TRAITS_H
 		#define LEMON_BITS_TRAITS_H
 		#include <lemon/bits/utility.h>
 		///\file
 		///\brief Traits for graphs and maps
 		///
 		namespace lemon {
 		  template <typename _Graph, typename _Item>
 		  class ItemSetTraits {};
 		  template <typename Graph, typename Enable = void>
 		  struct NodeNotifierIndicator {
 		    typedef InvalidType Type;
 		  };
 		  template <typename Graph>
 		  struct NodeNotifierIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
 		  > {
 		    typedef typename Graph::NodeNotifier Type;
 		  };
 		  template <typename _Graph>
 		  class ItemSetTraits<_Graph, typename _Graph::Node> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Node Item;
 		    typedef typename Graph::NodeIt ItemIt;
 		    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
 		    template <typename _Value>
 		    class Map : public Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename Graph::template NodeMap<_Value> Parent;
 		      typedef typename Graph::template NodeMap<_Value> Type;
 		      typedef typename Parent::Value Value;
 		      Map(const Graph& _digraph) : Parent(_digraph) {}
 		      Map(const Graph& _digraph, const Value& _value)
 			: Parent(_digraph, _value) {}
 		     };
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct ArcNotifierIndicator {
 		    typedef InvalidType Type;
 		  };
 		  template <typename Graph>
 		  struct ArcNotifierIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type
 		  > {
 		    typedef typename Graph::ArcNotifier Type;
 		  };
 		  template <typename _Graph>
 		  class ItemSetTraits<_Graph, typename _Graph::Arc> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Arc Item;
 		    typedef typename Graph::ArcIt ItemIt;
 		    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;
 		    template <typename _Value>
 		    class Map : public Graph::template ArcMap<_Value> {
 		    public:
 		      typedef typename Graph::template ArcMap<_Value> Parent;
 		      typedef typename Graph::template ArcMap<_Value> Type;
 		      typedef typename Parent::Value Value;
 		      Map(const Graph& _digraph) : Parent(_digraph) {}
 		      Map(const Graph& _digraph, const Value& _value)
 			: Parent(_digraph, _value) {}
 		    };
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct EdgeNotifierIndicator {
 		    typedef InvalidType Type;
 		  };
 		  template <typename Graph>
 		  struct EdgeNotifierIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
 		  > {
 		    typedef typename Graph::EdgeNotifier Type;
 		  };
 		  template <typename _Graph>
 		  class ItemSetTraits<_Graph, typename _Graph::Edge> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Edge Item;
 		    typedef typename Graph::EdgeIt ItemIt;
 		    typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
 		    template <typename _Value>
 		    class Map : public Graph::template EdgeMap<_Value> {
 		    public:
 		      typedef typename Graph::template EdgeMap<_Value> Parent;
 		      typedef typename Graph::template EdgeMap<_Value> Type;
 		      typedef typename Parent::Value Value;
 		      Map(const Graph& _digraph) : Parent(_digraph) {}
 		      Map(const Graph& _digraph, const Value& _value)
 			: Parent(_digraph, _value) {}
 		    };
 		  };
 		  template <typename Map, typename Enable = void>
 		  struct MapTraits {
 		    typedef False ReferenceMapTag;
 		    typedef typename Map::Key Key;
 		    typedef typename Map::Value Value;
 		    typedef const Value ConstReturnValue;
 		    typedef const Value ReturnValue;
 		    typedef Value ConstReturnValue;
 		    typedef Value ReturnValue;
 		  };
 		  template <typename Map>
 		  struct MapTraits<
 		    Map, typename enable_if<typename Map::ReferenceMapTag, void>::type >
+		  {
 		    typedef True ReferenceMapTag;
 		    typedef typename Map::Key Key;
 		    typedef typename Map::Value Value;
 		    typedef typename Map::ConstReference ConstReturnValue;
 		    typedef typename Map::Reference ReturnValue;
 		    typedef typename Map::ConstReference ConstReference;
 		    typedef typename Map::Reference Reference;
 		 };
 		  template <typename MatrixMap, typename Enable = void>
 		  struct MatrixMapTraits {
 		    typedef False ReferenceMapTag;
 		    typedef typename MatrixMap::FirstKey FirstKey;
 		    typedef typename MatrixMap::SecondKey SecondKey;
 		    typedef typename MatrixMap::Value Value;
 		    typedef const Value ConstReturnValue;
 		    typedef const Value ReturnValue;
 		    typedef Value ConstReturnValue;
 		    typedef Value ReturnValue;
 		  };
 		  template <typename MatrixMap>
 		  struct MatrixMapTraits<
 		    MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag,
 		                                  void>::type >
+		  {
 		    typedef True ReferenceMapTag;
 		    typedef typename MatrixMap::FirstKey FirstKey;
 		    typedef typename MatrixMap::SecondKey SecondKey;
 		    typedef typename MatrixMap::Value Value;
 		    typedef typename MatrixMap::ConstReference ConstReturnValue;
 		    typedef typename MatrixMap::Reference ReturnValue;
 		    typedef typename MatrixMap::ConstReference ConstReference;
 		    typedef typename MatrixMap::Reference Reference;
 		 };
 		  // Indicators for the tags
 		  template <typename Graph, typename Enable = void>
 		  struct NodeNumTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct NodeNumTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::NodeNumTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct EdgeNumTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct EdgeNumTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::EdgeNumTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct FindEdgeTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct FindEdgeTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::FindEdgeTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct UndirectedTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct UndirectedTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::UndirectedTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
 		  template <typename Graph, typename Enable = void>
 		  struct BuildTagIndicator {
 		    static const bool value = false;
 		  };
 		  template <typename Graph>
 		  struct BuildTagIndicator<
 		    Graph,
 		    typename enable_if<typename Graph::BuildTag, void>::type
 		  > {
 		    static const bool value = true;
 		  };
+		}
 		#endif

lemon/dijkstra.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_DIJKSTRA_H
 		#define LEMON_DIJKSTRA_H
 		///\ingroup shortest_path
 		///\file
 		///\brief Dijkstra algorithm.
 		#include <limits>
 		#include <lemon/list_graph.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/bits/invalid.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		namespace lemon {
 		  /// \brief Default OperationTraits for the Dijkstra algorithm class.
 		  ///
 		  /// It defines all computational operations and constants which are
 		  /// used in the Dijkstra algorithm.
 		  template <typename Value>
 		  struct DijkstraDefaultOperationTraits {
 		    /// \brief Gives back the zero value of the type.
 		    static Value zero() {
 		      return static_cast<Value>(0);
+		    }
 		    /// \brief Gives back the sum of the given two elements.
 		    static Value plus(const Value& left, const Value& right) {
 		      return left + right;
+		    }
 		    /// \brief Gives back true only if the first value less than the second.
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
 		  ///
 		  /// It defines all computational operations and constants which are
 		  /// used in the Dijkstra algorithm for widest path computation.
 		  template <typename Value>
 		  struct DijkstraWidestPathOperationTraits {
 		    /// \brief Gives back the maximum value of the type.
 		    static Value zero() {
 		      return std::numeric_limits<Value>::max();
+		    }
 		    /// \brief Gives back the minimum of the given two elements.
 		    static Value plus(const Value& left, const Value& right) {
 		      return std::min(left, right);
+		    }
 		    /// \brief Gives back true only if the first value less than the second.
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  ///Default traits class of Dijkstra class.
 		  ///Default traits class of Dijkstra class.
 		  ///\tparam GR Digraph type.
 		  ///\tparam LM Type of length map.
 		  template<class GR, class LM>
 		  struct DijkstraDefaultTraits
+		  {
 		    ///The digraph type the algorithm runs on.
 		    typedef GR Digraph;
 		    ///The type of the map that stores the arc lengths.
 		    ///The type of the map that stores the arc lengths.
 		    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LM LengthMap;
 		    //The type of the length of the arcs.
 		    typedef typename LM::Value Value;
 		    /// Operation traits for Dijkstra algorithm.
 		    /// It defines the used operation by the algorithm.
 		    /// \see DijkstraDefaultOperationTraits
 		    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
 		    /// The cross reference type used by heap.
 		    /// The cross reference type used by heap.
 		    /// Usually it is \c Digraph::NodeMap<int>.
 		    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		    ///Instantiates a HeapCrossRef.
 		    ///This function instantiates a \c HeapCrossRef.
 		    /// \param G is the digraph, to which we would like to define the
 		    /// HeapCrossRef.
 		    static HeapCrossRef *createHeapCrossRef(const GR &G)
+		    {
 		      return new HeapCrossRef(G);
+		    }
 		    ///The heap type used by Dijkstra algorithm.
 		    ///The heap type used by Dijkstra algorithm.
 		    ///
 		    ///\sa BinHeap
 		    ///\sa Dijkstra
 		    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
 		    static Heap *createHeap(HeapCrossRef& R)
+		    {
 		      return new Heap(R);
+		    }
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a \c PredMap.
 		    ///\param G is the digraph, to which we would like to define the PredMap.
 		    ///\todo The digraph alone may be insufficient for the initialization
 		    static PredMap *createPredMap(const GR &G)
+		    {
 		      return new PredMap(G);
+		    }
 		    ///The type of the map that stores whether a nodes is processed.
 		    ///The type of the map that stores whether a nodes is processed.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    ///\todo If it is set to a real map,
 		    ///Dijkstra::processed() should read this.
 		    ///\todo named parameter to set this type, function to read and write.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
 		    ///This function instantiates a \c ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \c ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const GR &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const GR &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that stores the dists of the nodes.
 		    ///The type of the map that stores the dists of the nodes.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    ///
 		    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
 		    ///Instantiates a DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param G is the digraph, to which we would like to define the \ref DistMap
 		    static DistMap *createDistMap(const GR &G)
+		    {
 		      return new DistMap(G);
+		    }
 		  };
 		  ///%Dijkstra algorithm class.
 		  /// \ingroup shortest_path
 		  ///This class provides an efficient implementation of %Dijkstra algorithm.
 		  ///The arc lengths are passed to the algorithm using a
 		  ///\ref concepts::ReadMap "ReadMap",
 		  ///so it is easy to change it to any kind of length.
 		  ///
 		  ///The type of the length is determined by the
 		  ///\ref concepts::ReadMap::Value "Value" of the length map.
 		  ///
 		  ///It is also possible to change the underlying priority heap.
 		  ///
 		  ///\tparam GR The digraph type the algorithm runs on. The default value
 		  ///is \ref ListDigraph. The value of GR is not used directly by
 		  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
 		  ///\tparam LM This read-only ArcMap determines the lengths of the
 		  ///arcs. It is read once for each arc, so the map may involve in
 		  ///relatively time consuming process to compute the arc length if
 		  ///it is necessary. The default map type is \ref
 		  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value
 		  ///of LM is not used directly by Dijkstra, it is only passed to \ref
 		  ///DijkstraDefaultTraits.
 		  ///\tparam TR Traits class to set
 		  ///various data types used by the algorithm.  The default traits
 		  ///class is \ref DijkstraDefaultTraits
 		  ///"DijkstraDefaultTraits<GR,LM>".  See \ref
 		  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
 		  ///class.
 		#ifdef DOXYGEN
 		  template <typename GR, typename LM, typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 			    typename LM=typename GR::template ArcMap<int>,
 			    typename TR=DijkstraDefaultTraits<GR,LM> >
 		#endif
 		  class Dijkstra {
 		  public:
 		    /**
 		     * \brief \ref Exception for uninitialized parameters.
+		     *
 		     * This error represents problems in the initialization
 		     * of the parameters of the algorithms.
 		     */
 		    class UninitializedParameter : public lemon::UninitializedParameter {
 		    public:
 		      virtual const char* what() const throw() {
 			return "lemon::Dijkstra::UninitializedParameter";
+		      }
 		    };
 		    typedef TR Traits;
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    ///\e
 		    typedef typename Digraph::Node Node;
 		    ///\e
 		    typedef typename Digraph::NodeIt NodeIt;
 		    ///\e
 		    typedef typename Digraph::Arc Arc;
 		    ///\e
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///The type of the length of the arcs.
 		    typedef typename TR::LengthMap::Value Value;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///\brief The type of the map that stores the last
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map indicating if a node is processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the map that stores the dists of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The cross reference type used for the current heap.
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    ///The heap type used by the dijkstra algorithm.
 		    typedef typename TR::Heap Heap;
 		    ///The operation traits.
 		    typedef typename TR::OperationTraits OperationTraits;
 		  private:
 		    /// Pointer to the underlying digraph.
 		    const Digraph *G;
 		    /// Pointer to the length map
 		    const LengthMap *length;
 		    ///Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    ///Indicates if \ref _pred is locally allocated (\c true) or not.
 		    bool local_pred;
 		    ///Pointer to the map of distances.
 		    DistMap *_dist;
 		    ///Indicates if \ref _dist is locally allocated (\c true) or not.
 		    bool local_dist;
 		    ///Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    ///Indicates if \ref _processed is locally allocated (\c true) or not.
 		    bool local_processed;
 		    ///Pointer to the heap cross references.
 		    HeapCrossRef *_heap_cross_ref;
 		    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
 		    bool local_heap_cross_ref;
 		    ///Pointer to the heap.
 		    Heap *_heap;
 		    ///Indicates if \ref _heap is locally allocated (\c true) or not.
 		    bool local_heap;
 		    ///Creates the maps if necessary.
 		    ///\todo Better memory allocation (instead of new).
 		    void create_maps()
+		    {
 		      if(!_pred) {
 			local_pred = true;
 			_pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 			local_dist = true;
 			_dist = Traits::createDistMap(*G);
+		      }
 		      if(!_processed) {
 			local_processed = true;
 			_processed = Traits::createProcessedMap(*G);
+		      }
 		      if (!_heap_cross_ref) {
 			local_heap_cross_ref = true;
 			_heap_cross_ref = Traits::createHeapCrossRef(*G);
+		      }
 		      if (!_heap) {
 			local_heap = true;
 			_heap = Traits::createHeap(*_heap_cross_ref);
+		      }
+		    }
 		  public :
 		    typedef Dijkstra Create;
 		    ///\name Named template parameters
 		    ///@{
 		    template <class T>
 		    struct DefPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\ref named-templ-param "Named parameter" for setting PredMap type
 		    ///\ref named-templ-param "Named parameter" for setting PredMap type
 		    ///
 		    template <class T>
 		    struct DefPredMap
 		      : public Dijkstra< Digraph,	LengthMap, DefPredMapTraits<T> > {
 		      typedef Dijkstra< Digraph,	LengthMap, DefPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\ref named-templ-param "Named parameter" for setting DistMap type
 		    ///\ref named-templ-param "Named parameter" for setting DistMap type
 		    ///
 		    template <class T>
 		    struct DefDistMap
 		      : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct DefProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &G)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
 		    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
 		    ///
 		    template <class T>
 		    struct DefProcessedMap
 		      : public Dijkstra< Digraph,	LengthMap, DefProcessedMapTraits<T> > {
 		      typedef Dijkstra< Digraph,	LengthMap, DefProcessedMapTraits<T> > Create;
 		    };
 		    struct DefDigraphProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &G)
+		      {
 			return new ProcessedMap(G);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter"
 		    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
 		    ///
 		    ///\ref named-templ-param "Named parameter"
 		    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
 		    ///If you don't set it explicitely, it will be automatically allocated.
 		    template <class T>
 		    struct DefProcessedMapToBeDefaultMap
 		      : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
 		      typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create;
 		    };
 		    template <class H, class CR>
 		    struct DefHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
 			throw UninitializedParameter();
+		      }
 		      static Heap *createHeap(HeapCrossRef &)
+		      {
 			throw UninitializedParameter();
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///heap and cross reference type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting heap and cross
 		    ///reference type
 		    ///
 		    template <class H, class CR = typename Digraph::template NodeMap<int> >
 		    struct DefHeap
 		      : public Dijkstra< Digraph,	LengthMap, DefHeapTraits<H, CR> > {
 		      typedef Dijkstra< Digraph,	LengthMap, DefHeapTraits<H, CR> > Create;
 		    };
 		    template <class H, class CR>
 		    struct DefStandardHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
 			return new HeapCrossRef(G);
+		      }
 		      static Heap *createHeap(HeapCrossRef &R)
+		      {
 			return new Heap(R);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///heap and cross reference type with automatic allocation
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting heap and cross
 		    ///reference type. It can allocate the heap and the cross reference
 		    ///object if the cross reference's constructor waits for the digraph as
 		    ///parameter and the heap's constructor waits for the cross reference.
 		    template <class H, class CR = typename Digraph::template NodeMap<int> >
 		    struct DefStandardHeap
 		      : public Dijkstra< Digraph,	LengthMap, DefStandardHeapTraits<H, CR> > {
 		      typedef Dijkstra< Digraph,	LengthMap, DefStandardHeapTraits<H, CR> >
 		      Create;
 		    };
 		    template <class T>
 		    struct DefOperationTraitsTraits : public Traits {
 		      typedef T OperationTraits;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// OperationTraits type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting OperationTraits
 		    /// type
 		    template <class T>
 		    struct DefOperationTraits
 		      : public Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > {
 		      typedef Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> >
 		      Create;
 		    };
 		    ///@}
 		  protected:
 		    Dijkstra() {}
 		  public:
 		    ///Constructor.
 		    ///\param _G the digraph the algorithm will run on.
 		    ///\param _length the length map used by the algorithm.
 		    Dijkstra(const Digraph& _G, const LengthMap& _length) :
 		      G(&_G), length(&_length),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _processed(NULL), local_processed(false),
 		      _heap_cross_ref(NULL), local_heap_cross_ref(false),
 		      _heap(NULL), local_heap(false)
 		    { }
 		    ///Destructor.
 		    ~Dijkstra()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_processed) delete _processed;
 		      if(local_heap_cross_ref) delete _heap_cross_ref;
 		      if(local_heap) delete _heap;
+		    }
 		    ///Sets the length map.
 		    ///Sets the length map.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &lengthMap(const LengthMap &m)
+		    {
 		      length = &m;
 		      return *this;
+		    }
 		    ///Sets the map storing the predecessor arcs.
 		    ///Sets the map storing the predecessor arcs.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destuctor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 			delete _pred;
 			local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///Sets the map storing the distances calculated by the algorithm.
 		    ///Sets the map storing the distances calculated by the algorithm.
 		    ///If you don't use this function before calling \ref run(),
 		    ///it will allocate one. The destuctor deallocates this
 		    ///automatically allocated map, of course.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &distMap(DistMap &m)
+		    {
 		      if(local_dist) {
 			delete _dist;
 			local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;

lemon/graph_to_eps.h

Show inline comments

@@ -506,741 +506,742 @@
 		  GraphToEps<T> &absoluteNodeSizes(bool b=true) {
 		    _absoluteNodeSizes=b;return *this;
+		  }
 		  ///Negates the Y coordinates.
 		  ///Negates the Y coordinates.
 		  ///
 		  GraphToEps<T> &negateY(bool b=true) {
 		    _negY=b;return *this;
+		  }
 		  ///Turn on/off pre-scaling
 		  ///By default graphToEps() rescales the whole image in order to avoid
 		  ///very big or very small bounding boxes.
 		  ///
 		  ///This (p)rescaling can be turned off with this function.
 		  ///
 		  GraphToEps<T> &preScale(bool b=true) {
 		    _preScale=b;return *this;
+		  }
 		  ///Sets a global scale factor for arc widths
 		  /// Sets a global scale factor for arc widths.
 		  ///
 		  /// If arcWidths() is not given, this function simply sets the arc
 		  /// widths to \c d.  If arcWidths() is given, but
 		  /// autoArcWidthScale() is not, then the arc withs given by
 		  /// arcWidths() will be multiplied by the value \c d.
 		  /// If both arcWidths() and autoArcWidthScale() are used, then the
 		  /// arc withs will be scaled in such a way that the greatest width will be
 		  /// equal to \c d.
 		  GraphToEps<T> &arcWidthScale(double d=.003) {_arcWidthScale=d;return *this;}
 		  ///Turns on/off the automatic arc width scaling.
 		  ///Turns on/off the automatic arc width scaling.
 		  ///
 		  ///\sa arcWidthScale()
 		  ///
 		  GraphToEps<T> &autoArcWidthScale(bool b=true) {
 		    _autoArcWidthScale=b;return *this;
+		  }
 		  ///Turns on/off the absolutematic arc width scaling.
 		  ///Turns on/off the absolutematic arc width scaling.
 		  ///
 		  ///\sa arcWidthScale()
 		  ///
 		  GraphToEps<T> &absoluteArcWidths(bool b=true) {
 		    _absoluteArcWidths=b;return *this;
+		  }
 		  ///Sets a global scale factor for the whole picture
 		  ///Sets a global scale factor for the whole picture
 		  ///
 		  GraphToEps<T> &scale(double d) {_scale=d;return *this;}
 		  ///Sets the width of the border around the picture
 		  ///Sets the width of the border around the picture
 		  ///
 		  GraphToEps<T> &border(double b=10) {_xBorder=_yBorder=b;return *this;}
 		  ///Sets the width of the border around the picture
 		  ///Sets the width of the border around the picture
 		  ///
 		  GraphToEps<T> &border(double x, double y) {
 		    _xBorder=x;_yBorder=y;return *this;
+		  }
 		  ///Sets whether to draw arrows
 		  ///Sets whether to draw arrows
 		  ///
 		  GraphToEps<T> &drawArrows(bool b=true) {_drawArrows=b;return *this;}
 		  ///Sets the length of the arrowheads
 		  ///Sets the length of the arrowheads
 		  ///
 		  GraphToEps<T> &arrowLength(double d=1.0) {_arrowLength*=d;return *this;}
 		  ///Sets the width of the arrowheads
 		  ///Sets the width of the arrowheads
 		  ///
 		  GraphToEps<T> &arrowWidth(double d=.3) {_arrowWidth*=d;return *this;}
 		  ///Scales the drawing to fit to A4 page
 		  ///Scales the drawing to fit to A4 page
 		  ///
 		  GraphToEps<T> &scaleToA4() {_scaleToA4=true;return *this;}
 		  ///Enables parallel arcs
 		  ///Enables parallel arcs
 		  GraphToEps<T> &enableParallel(bool b=true) {_enableParallel=b;return *this;}
 		  ///Sets the distance
 		  ///Sets the distance
 		  ///
 		  GraphToEps<T> &parArcDist(double d) {_parArcDist*=d;return *this;}
 		  ///Hides the arcs
 		  ///Hides the arcs
 		  ///
 		  GraphToEps<T> &hideArcs(bool b=true) {_showArcs=!b;return *this;}
 		  ///Hides the nodes
 		  ///Hides the nodes
 		  ///
 		  GraphToEps<T> &hideNodes(bool b=true) {_showNodes=!b;return *this;}
 		  ///Sets the size of the node texts
 		  ///Sets the size of the node texts
 		  ///
 		  GraphToEps<T> &nodeTextSize(double d) {_nodeTextSize=d;return *this;}
 		  ///Sets the color of the node texts to be different from the node color
 		  ///Sets the color of the node texts to be as different from the node color
 		  ///as it is possible
 		  ///
 		  GraphToEps<T> &distantColorNodeTexts()
 		  {_nodeTextColorType=DIST_COL;return *this;}
 		  ///Sets the color of the node texts to be black or white and always visible.
 		  ///Sets the color of the node texts to be black or white according to
 		  ///which is more
 		  ///different from the node color
 		  ///
 		  GraphToEps<T> &distantBWNodeTexts()
 		  {_nodeTextColorType=DIST_BW;return *this;}
 		  ///Gives a preamble block for node Postscript block.
 		  ///Gives a preamble block for node Postscript block.
 		  ///
 		  ///\sa nodePsTexts()
 		  GraphToEps<T> & nodePsTextsPreamble(const char *str) {
 		    _nodePsTextsPreamble=str ;return *this;
+		  }
 		  ///Sets whether the the graph is undirected
 		  ///Sets whether the the graph is undirected.
 		  ///
 		  ///This setting is the default for undirected graphs.
 		  ///
 		  ///\sa directed()
 		   GraphToEps<T> &undirected(bool b=true) {_undirected=b;return *this;}
 		  ///Sets whether the the graph is directed
 		  ///Sets whether the the graph is directed.
 		  ///Use it to show the edges as a pair of directed ones.
 		  ///
 		  ///This setting is the default for digraphs.
 		  ///
 		  ///\sa undirected()
 		  GraphToEps<T> &directed(bool b=true) {_undirected=!b;return *this;}
 		  ///Sets the title.
 		  ///Sets the title of the generated image,
 		  ///namely it inserts a <tt>%%Title:</tt> DSC field to the header of
 		  ///the EPS file.
 		  GraphToEps<T> &title(const std::string &t) {_title=t;return *this;}
 		  ///Sets the copyright statement.
 		  ///Sets the copyright statement of the generated image,
 		  ///namely it inserts a <tt>%%Copyright:</tt> DSC field to the header of
 		  ///the EPS file.
 		  GraphToEps<T> &copyright(const std::string &t) {_copyright=t;return *this;}
 		protected:
 		  bool isInsideNode(dim2::Point<double> p, double r,int t)
+		  {
 		    switch(t) {
 		    case CIRCLE:
 		    case MALE:
 		    case FEMALE:
 		      return p.normSquare()<=r*r;
 		    case SQUARE:
 		      return p.x<=r&&p.x>=-r&&p.y<=r&&p.y>=-r;
 		    case DIAMOND:
 		      return p.x+p.y<=r && p.x-p.y<=r && -p.x+p.y<=r && -p.x-p.y<=r;
+		    }
 		    return false;
+		  }
 		public:
 		  ~GraphToEps() { }
 		  ///Draws the graph.
 		  ///Like other functions using
 		  ///\ref named-templ-func-param "named template parameters",
 		  ///this function calls the algorithm itself, i.e. in this case
 		  ///it draws the graph.
 		  void run() {
 		    //\todo better 'epsilon' would be nice here.
 		    const double EPSILON=1e-9;
 		    if(dontPrint) return;
 		    _graph_to_eps_bits::_NegY<typename T::CoordsMapType>
 		      mycoords(_coords,_negY);
 		    os << "%!PS-Adobe-2.0 EPSF-2.0\n";
 		    if(_title.size()>0) os << "%%Title: " << _title << '\n';
 		     if(_copyright.size()>0) os << "%%Copyright: " << _copyright << '\n';
 		//        << "%%Copyright: XXXX\n"
 		    os << "%%Creator: LEMON, graphToEps()\n";
+		    {
 		#ifndef WIN32
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      char cbuf[26];
 		      ctime_r(&tv.tv_sec,cbuf);
 		      os << "%%CreationDate: " << cbuf;
 		#else
 		      SYSTEMTIME time;
 		      char buf1[11], buf2[9], buf3[5];
 		      GetSystemTime(&time);
 		      if (GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
 					"ddd MMM dd", buf1, 11) &&
 			  GetTimeFormat(LOCALE_USER_DEFAULT, 0, &time,
 					"HH':'mm':'ss", buf2, 9) &&
 			  GetDateFormat(LOCALE_USER_DEFAULT, 0, &time,
 						"yyyy", buf3, 5)) {
 			os << "%%CreationDate: " << buf1 << ' '
 			   << buf2 << ' ' << buf3 << std::endl;
+		      }
 		#endif
+		    }
 		    if (_autoArcWidthScale) {
 		      double max_w=0;
 		      for(ArcIt e(g);e!=INVALID;++e)
 			max_w=std::max(double(_arcWidths[e]),max_w);
 		      ///\todo better 'epsilon' would be nice here.
 		      if(max_w>EPSILON) {
 			_arcWidthScale/=max_w;
+		      }
+		    }
 		    if (_autoNodeScale) {
 		      double max_s=0;
 		      for(NodeIt n(g);n!=INVALID;++n)
 			max_s=std::max(double(_nodeSizes[n]),max_s);
 		      ///\todo better 'epsilon' would be nice here.
 		      if(max_s>EPSILON) {
 			_nodeScale/=max_s;
+		      }
+		    }
 		    double diag_len = 1;
 		    if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {
 		      dim2::BoundingBox<double> bb;
 		      for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);
 		      if (bb.empty()) {
 			bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
+		      }
 		      diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());
 		      if(diag_len<EPSILON) diag_len = 1;
 		      if(!_absoluteNodeSizes) _nodeScale*=diag_len;
 		      if(!_absoluteArcWidths) _arcWidthScale*=diag_len;
+		    }
 		    dim2::BoundingBox<double> bb;
 		    for(NodeIt n(g);n!=INVALID;++n) {
 		      double ns=_nodeSizes[n]*_nodeScale;
 		      dim2::Point<double> p(ns,ns);
 		      switch(_nodeShapes[n]) {
 		      case CIRCLE:
 		      case SQUARE:
 		      case DIAMOND:
 			bb.add(p+mycoords[n]);
 			bb.add(-p+mycoords[n]);
 			break;
 		      case MALE:
 			bb.add(-p+mycoords[n]);
 			bb.add(dim2::Point<double>(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]);
 			break;
 		      case FEMALE:
 			bb.add(p+mycoords[n]);
 			bb.add(dim2::Point<double>(-ns,-3.01*ns)+mycoords[n]);
 			break;
+		      }
+		    }
 		    if (bb.empty()) {
 		      bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
+		    }
 		    if(_scaleToA4)
 		      os <<"%%BoundingBox: 0 0 596 842\n%%DocumentPaperSizes: a4\n";
 		    else {
 		      if(_preScale) {
 			//Rescale so that BoundingBox won't be neither to big nor too small.
 			while(bb.height()*_scale>1000||bb.width()*_scale>1000) _scale/=10;
 			while(bb.height()*_scale<100||bb.width()*_scale<100) _scale*=10;
+		      }
 		      os << "%%BoundingBox: "
 			 << int(floor(bb.left()   * _scale - _xBorder)) << ' '
 			 << int(floor(bb.bottom() * _scale - _yBorder)) << ' '
 			 << int(ceil(bb.right()  * _scale + _xBorder)) << ' '
 			 << int(ceil(bb.top()    * _scale + _yBorder)) << '\n';
+		    }
 		    os << "%%EndComments\n";
 		    //x1 y1 x2 y2 x3 y3 cr cg cb w
 		    os << "/lb { setlinewidth setrgbcolor newpath moveto\n"
 		       << "      4 2 roll 1 index 1 index curveto stroke } bind def\n";
 		    os << "/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def\n";
 		    //x y r
 		    os << "/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def\n";
 		    //x y r
 		    os << "/sq { newpath 2 index 1 index add 2 index 2 index add moveto\n"
 		       << "      2 index 1 index sub 2 index 2 index add lineto\n"
 		       << "      2 index 1 index sub 2 index 2 index sub lineto\n"
 		       << "      2 index 1 index add 2 index 2 index sub lineto\n"
 		       << "      closepath pop pop pop} bind def\n";
 		    //x y r
 		    os << "/di { newpath 2 index 1 index add 2 index moveto\n"
 		       << "      2 index             2 index 2 index add lineto\n"
 		       << "      2 index 1 index sub 2 index             lineto\n"
 		       << "      2 index             2 index 2 index sub lineto\n"
 		       << "      closepath pop pop pop} bind def\n";
 		    // x y r cr cg cb
 		    os << "/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill\n"
 		       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
 		       << "   } bind def\n";
 		    os << "/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill\n"
 		       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div sq fill\n"
 		       << "   } bind def\n";
 		    os << "/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill\n"
 		       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div di fill\n"
 		       << "   } bind def\n";
 		    os << "/nfemale { 0 0 0 setrgbcolor 3 index "
 		       << _nodeBorderQuotient/(1+_nodeBorderQuotient)
 		       << " 1.5 mul mul setlinewidth\n"
 		       << "  newpath 5 index 5 index moveto "
 		       << "5 index 5 index 5 index 3.01 mul sub\n"
 		       << "  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto\n"
 		       << "  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke\n"
 		       << "  5 index 5 index 5 index c fill\n"
 		       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
 		       << "  } bind def\n";
 		    os << "/nmale {\n"
 		       << "  0 0 0 setrgbcolor 3 index "
 		       << _nodeBorderQuotient/(1+_nodeBorderQuotient)
 		       <<" 1.5 mul mul setlinewidth\n"
 		       << "  newpath 5 index 5 index moveto\n"
 		       << "  5 index 4 index 1 mul 1.5 mul add\n"
 		       << "  5 index 5 index 3 sqrt 1.5 mul mul add\n"
 		       << "  1 index 1 index lineto\n"
 		       << "  1 index 1 index 7 index sub moveto\n"
 		       << "  1 index 1 index lineto\n"
 		       << "  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto\n"
 		       << "  stroke\n"
 		       << "  5 index 5 index 5 index c fill\n"
 		       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
 		       << "  } bind def\n";
 		    os << "/arrl " << _arrowLength << " def\n";
 		    os << "/arrw " << _arrowWidth << " def\n";
 		    // l dx_norm dy_norm
 		    os << "/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def\n";
 		    //len w dx_norm dy_norm x1 y1 cr cg cb
 		    os << "/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def\n"
 		       << "       /w exch def /len exch def\n"
 		      //	 << "       0.1 setlinewidth x1 y1 moveto dx len mul dy len mul rlineto stroke"
 		       << "       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto\n"
 		       << "       len w sub arrl sub dx dy lrl\n"
 		       << "       arrw dy dx neg lrl\n"
 		       << "       dx arrl w add mul dy w 2 div arrw add mul sub\n"
 		       << "       dy arrl w add mul dx w 2 div arrw add mul add rlineto\n"
 		       << "       dx arrl w add mul neg dy w 2 div arrw add mul sub\n"
 		       << "       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto\n"
 		       << "       arrw dy dx neg lrl\n"
 		       << "       len w sub arrl sub neg dx dy lrl\n"
 		       << "       closepath fill } bind def\n";
 		    os << "/cshow { 2 index 2 index moveto dup stringwidth pop\n"
 		       << "         neg 2 div fosi .35 mul neg rmoveto show pop pop} def\n";
 		    os << "\ngsave\n";
 		    if(_scaleToA4)
 		      if(bb.height()>bb.width()) {
 			double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.height(),
 				  (A4WIDTH-2*A4BORDER)/bb.width());
 			os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' '
 			   << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER
 			   << " translate\n"
 			   << sc << " dup scale\n"
 			   << -bb.left() << ' ' << -bb.bottom() << " translate\n";
+		      }
 		      else {
 			//\todo Verify centering
 			double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(),
 				  (A4WIDTH-2*A4BORDER)/bb.height());
 			os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' '
 			   << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER
 			   << " translate\n"
 			   << sc << " dup scale\n90 rotate\n"
 			   << -bb.left() << ' ' << -bb.top() << " translate\n";
+			}
 		    else if(_scale!=1.0) os << _scale << " dup scale\n";
 		    if(_showArcs) {
 		      os << "%Arcs:\ngsave\n";
 		      if(_enableParallel) {
 			std::vector<Arc> el;
 			for(ArcIt e(g);e!=INVALID;++e)
 			  if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0
 			     &&g.source(e)!=g.target(e))
 			    el.push_back(e);
 			std::sort(el.begin(),el.end(),arcLess(g));
 			typename std::vector<Arc>::iterator j;
 			for(typename std::vector<Arc>::iterator i=el.begin();i!=el.end();i=j) {
 			  for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ;
 			  double sw=0;
 			  for(typename std::vector<Arc>::iterator e=i;e!=j;++e)
 			    sw+=_arcWidths[*e]*_arcWidthScale+_parArcDist;
 			  sw-=_parArcDist;
 			  sw/=-2.0;
 			  dim2::Point<double>
 			    dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);
 			  double l=std::sqrt(dvec.normSquare());
 			  //\todo better 'epsilon' would be nice here.
 			  dim2::Point<double> d(dvec/std::max(l,EPSILON));
 		 	  dim2::Point<double> m;
 		// 	  m=dim2::Point<double>(mycoords[g.target(*i)]+mycoords[g.source(*i)])/2.0;
 		//  	  m=dim2::Point<double>(mycoords[g.source(*i)])+
 		// 	    dvec*(double(_nodeSizes[g.source(*i)])/
 		// 	       (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));
 		 	  m=dim2::Point<double>(mycoords[g.source(*i)])+
 			    d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0;
 			  for(typename std::vector<Arc>::iterator e=i;e!=j;++e) {
 			    sw+=_arcWidths[*e]*_arcWidthScale/2.0;
 			    dim2::Point<double> mm=m+rot90(d)*sw/.75;
 			    if(_drawArrows) {
 			      int node_shape;
 			      dim2::Point<double> s=mycoords[g.source(*e)];
 			      dim2::Point<double> t=mycoords[g.target(*e)];
 			      double rn=_nodeSizes[g.target(*e)]*_nodeScale;
 			      node_shape=_nodeShapes[g.target(*e)];
 			      dim2::Bezier3 bez(s,mm,mm,t);
 			      double t1=0,t2=1;
 			      for(int ii=0;ii<INTERPOL_PREC;++ii)
 				if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2;
 				else t1=(t1+t2)/2;
 			      dim2::Point<double> apoint=bez((t1+t2)/2);
 			      rn = _arrowLength+_arcWidths[*e]*_arcWidthScale;
 			      rn*=rn;
 			      t2=(t1+t2)/2;t1=0;
 			      for(int ii=0;ii<INTERPOL_PREC;++ii)
 				if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2;
 				else t2=(t1+t2)/2;
 			      dim2::Point<double> linend=bez((t1+t2)/2);
 			      bez=bez.before((t1+t2)/2);
 		// 	      rn=_nodeSizes[g.source(*e)]*_nodeScale;
 		// 	      node_shape=_nodeShapes[g.source(*e)];
 		// 	      t1=0;t2=1;
 		// 	      for(int i=0;i<INTERPOL_PREC;++i)
 		// 		if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t1=(t1+t2)/2;
 		// 		else t2=(t1+t2)/2;
 		// 	      bez=bez.after((t1+t2)/2);
 			      os << _arcWidths[*e]*_arcWidthScale << " setlinewidth "
 				 << _arcColors[*e].red() << ' '
 				 << _arcColors[*e].green() << ' '
 				 << _arcColors[*e].blue() << " setrgbcolor newpath\n"
 				 << bez.p1.x << ' ' <<  bez.p1.y << " moveto\n"
 				 << bez.p2.x << ' ' << bez.p2.y << ' '
 				 << bez.p3.x << ' ' << bez.p3.y << ' '
 				 << bez.p4.x << ' ' << bez.p4.y << " curveto stroke\n";
 			      dim2::Point<double> dd(rot90(linend-apoint));
 			      dd*=(.5*_arcWidths[*e]*_arcWidthScale+_arrowWidth)/
 				std::sqrt(dd.normSquare());
 			      os << "newpath " << psOut(apoint) << " moveto "
 				 << psOut(linend+dd) << " lineto "
 				 << psOut(linend-dd) << " lineto closepath fill\n";
+			    }
 			    else {
 			      os << mycoords[g.source(*e)].x << ' '
 				 << mycoords[g.source(*e)].y << ' '
 				 << mm.x << ' ' << mm.y << ' '
 				 << mycoords[g.target(*e)].x << ' '
 				 << mycoords[g.target(*e)].y << ' '
 				 << _arcColors[*e].red() << ' '
 				 << _arcColors[*e].green() << ' '
 				 << _arcColors[*e].blue() << ' '
 				 << _arcWidths[*e]*_arcWidthScale << " lb\n";
+			    }
 			    sw+=_arcWidths[*e]*_arcWidthScale/2.0+_parArcDist;
+			  }
+			}
+		      }
 		      else for(ArcIt e(g);e!=INVALID;++e)
 			if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0
 			   &&g.source(e)!=g.target(e))
+			   &&g.source(e)!=g.target(e)) {
 			  if(_drawArrows) {
 			    dim2::Point<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]);
 			    double rn=_nodeSizes[g.target(e)]*_nodeScale;
 			    int node_shape=_nodeShapes[g.target(e)];
 			    double t1=0,t2=1;
 			    for(int i=0;i<INTERPOL_PREC;++i)
 			      if(isInsideNode((-(t1+t2)/2)*d,rn,node_shape)) t1=(t1+t2)/2;
 			      else t2=(t1+t2)/2;
 			    double l=std::sqrt(d.normSquare());
 			    d/=l;
 			    os << l*(1-(t1+t2)/2) << ' '
 			       << _arcWidths[e]*_arcWidthScale << ' '
 			       << d.x << ' ' << d.y << ' '
 			       << mycoords[g.source(e)].x << ' '
 			       << mycoords[g.source(e)].y << ' '
 			       << _arcColors[e].red() << ' '
 			       << _arcColors[e].green() << ' '
 			       << _arcColors[e].blue() << " arr\n";
+			  }
 			  else os << mycoords[g.source(e)].x << ' '
 				  << mycoords[g.source(e)].y << ' '
 				  << mycoords[g.target(e)].x << ' '
 				  << mycoords[g.target(e)].y << ' '
 				  << _arcColors[e].red() << ' '
 				  << _arcColors[e].green() << ' '
 				  << _arcColors[e].blue() << ' '
 				  << _arcWidths[e]*_arcWidthScale << " l\n";
+			}
 		      os << "grestore\n";
+		    }
 		    if(_showNodes) {
 		      os << "%Nodes:\ngsave\n";
 		      for(NodeIt n(g);n!=INVALID;++n) {
 			os << mycoords[n].x << ' ' << mycoords[n].y << ' '
 			   << _nodeSizes[n]*_nodeScale << ' '
 			   << _nodeColors[n].red() << ' '
 			   << _nodeColors[n].green() << ' '
 			   << _nodeColors[n].blue() << ' ';
 			switch(_nodeShapes[n]) {
 			case CIRCLE:
 			  os<< "nc";break;
 			case SQUARE:
 			  os<< "nsq";break;
 			case DIAMOND:
 			  os<< "ndi";break;
 			case MALE:
 			  os<< "nmale";break;
 			case FEMALE:
 			  os<< "nfemale";break;
+			}
 			os<<'\n';
+		      }
 		      os << "grestore\n";
+		    }
 		    if(_showNodeText) {
 		      os << "%Node texts:\ngsave\n";
 		      os << "/fosi " << _nodeTextSize << " def\n";
 		      os << "(Helvetica) findfont fosi scalefont setfont\n";
 		      for(NodeIt n(g);n!=INVALID;++n) {
 			switch(_nodeTextColorType) {
 			case DIST_COL:
 			  os << psOut(distantColor(_nodeColors[n])) << " setrgbcolor\n";
 			  break;
 			case DIST_BW:
 			  os << psOut(distantBW(_nodeColors[n])) << " setrgbcolor\n";
 			  break;
 			case CUST_COL:
 			  os << psOut(distantColor(_nodeTextColors[n])) << " setrgbcolor\n";
 			  break;
 			default:
 			  os << "0 0 0 setrgbcolor\n";
+			}
 			os << mycoords[n].x << ' ' << mycoords[n].y
 			   << " (" << _nodeTexts[n] << ") cshow\n";
+		      }
 		      os << "grestore\n";
+		    }
 		    if(_showNodePsText) {
 		      os << "%Node PS blocks:\ngsave\n";
 		      for(NodeIt n(g);n!=INVALID;++n)
 			os << mycoords[n].x << ' ' << mycoords[n].y
 			   << " moveto\n" << _nodePsTexts[n] << "\n";
 		      os << "grestore\n";
+		    }
 		    os << "grestore\nshowpage\n";
 		    //CleanUp:
 		    if(_pleaseRemoveOsStream) {delete &os;}
+		  }
 		  ///\name Aliases
 		  ///These are just some aliases to other parameter setting functions.
 		  ///@{
 		  ///An alias for arcWidths()
 		  ///An alias for arcWidths()
 		  ///
 		  template<class X> GraphToEps<ArcWidthsTraits<X> > edgeWidths(const X &x)
+		  {
 		    return arcWidths(x);
+		  }
 		  ///An alias for arcColors()
 		  ///An alias for arcColors()
 		  ///
 		  template<class X> GraphToEps<ArcColorsTraits<X> >
 		  edgeColors(const X &x)
+		  {
 		    return arcColors(x);
+		  }
 		  ///An alias for arcWidthScale()
 		  ///An alias for arcWidthScale()
 		  ///
 		  GraphToEps<T> &edgeWidthScale(double d) {return arcWidthScale(d);}
 		  ///An alias for autoArcWidthScale()
 		  ///An alias for autoArcWidthScale()
 		  ///
 		  GraphToEps<T> &autoEdgeWidthScale(bool b=true)
+		  {
 		    return autoArcWidthScale(b);
+		  }
 		  ///An alias for absoluteArcWidths()
 		  ///An alias for absoluteArcWidths()
 		  ///
 		  GraphToEps<T> &absoluteEdgeWidths(bool b=true)
+		  {
 		    return absoluteArcWidths(b);
+		  }
 		  ///An alias for parArcDist()
 		  ///An alias for parArcDist()
 		  ///
 		  GraphToEps<T> &parEdgeDist(double d) {return parArcDist(d);}
 		  ///An alias for hideArcs()
 		  ///An alias for hideArcs()
 		  ///
 		  GraphToEps<T> &hideEdges(bool b=true) {return hideArcs(b);}
 		  ///@}
 		};
 		template<class T>
 		const int GraphToEps<T>::INTERPOL_PREC = 20;
 		template<class T>
 		const double GraphToEps<T>::A4HEIGHT = 841.8897637795276;
 		template<class T>
 		const double GraphToEps<T>::A4WIDTH  = 595.275590551181;
 		template<class T>
 		const double GraphToEps<T>::A4BORDER = 15;
 		///Generates an EPS file from a graph
 		///\ingroup eps_io
 		///Generates an EPS file from a graph.
 		///\param g is a reference to the graph to be printed
 		///\param os is a reference to the output stream.
 		///By default it is <tt>std::cout</tt>
 		///
 		///This function also has a lot of
 		///\ref named-templ-func-param "named parameters",
 		///they are declared as the members of class \ref GraphToEps. The following
 		///example shows how to use these parameters.
 		///\code
 		/// graphToEps(g,os).scale(10).coords(coords)
 		///              .nodeScale(2).nodeSizes(sizes)
 		///              .arcWidthScale(.4).run();
 		///\endcode
 		///\warning Don't forget to put the \ref GraphToEps::run() "run()"
 		///to the end of the parameter list.
 		///\sa GraphToEps
 		///\sa graphToEps(G &g, const char *file_name)
 		template<class G>
 		GraphToEps<DefaultGraphToEpsTraits<G> >
 		graphToEps(G &g, std::ostream& os=std::cout)
+		{
 		  return
 		    GraphToEps<DefaultGraphToEpsTraits<G> >(DefaultGraphToEpsTraits<G>(g,os));
+		}
 		///Generates an EPS file from a graph
 		///\ingroup eps_io
 		///This function does the same as
 		///\ref graphToEps(G &g,std::ostream& os)
 		///but it writes its output into the file \c file_name
 		///instead of a stream.
 		///\sa graphToEps(G &g, std::ostream& os)
 		template<class G>
 		GraphToEps<DefaultGraphToEpsTraits<G> >
 		graphToEps(G &g,const char *file_name)
+		{
 		  return GraphToEps<DefaultGraphToEpsTraits<G> >
 		    (DefaultGraphToEpsTraits<G>(g,*new std::ofstream(file_name),true));
+		}
 		///Generates an EPS file from a graph
 		///\ingroup eps_io
 		///This function does the same as
 		///\ref graphToEps(G &g,std::ostream& os)
 		///but it writes its output into the file \c file_name
 		///instead of a stream.
 		///\sa graphToEps(G &g, std::ostream& os)
 		template<class G>
 		GraphToEps<DefaultGraphToEpsTraits<G> >
 		graphToEps(G &g,const std::string& file_name)
+		{
 		  return GraphToEps<DefaultGraphToEpsTraits<G> >
 		    (DefaultGraphToEpsTraits<G>(g,*new std::ofstream(file_name.c_str()),true));
+		}
 		} //END OF NAMESPACE LEMON
 		#endif // LEMON_GRAPH_TO_EPS_H

lemon/list_graph.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_LIST_GRAPH_H
 		#define LEMON_LIST_GRAPH_H
 		///\ingroup graphs
 		///\file
 		///\brief ListDigraph, ListGraph classes.
 		#include <lemon/bits/graph_extender.h>
 		#include <vector>
 		#include <list>
 		namespace lemon {
 		  class ListDigraphBase {
 		  protected:
 		    struct NodeT {
 		      int first_in, first_out;
 		      int prev, next;
 		    };
 		    struct ArcT {
 		      int target, source;
 		      int prev_in, prev_out;
 		      int next_in, next_out;
 		    };
 		    std::vector<NodeT> nodes;
 		    int first_node;
 		    int first_free_node;
 		    std::vector<ArcT> arcs;
 		    int first_free_arc;
 		  public:
 		    typedef ListDigraphBase Digraph;
 		    class Node {
 		      friend class ListDigraphBase;
 		    protected:
 		      int id;
 		      explicit Node(int pid) { id = pid;}
 		    public:
 		      Node() {}
 		      Node (Invalid) { id = -1; }
 		      bool operator==(const Node& node) const {return id == node.id;}
 		      bool operator!=(const Node& node) const {return id != node.id;}
 		      bool operator<(const Node& node) const {return id < node.id;}
 		    };
 		    class Arc {
 		      friend class ListDigraphBase;
 		    protected:
 		      int id;
 		      explicit Arc(int pid) { id = pid;}
 		    public:
 		      Arc() {}
 		      Arc (Invalid) { id = -1; }
 		      bool operator==(const Arc& arc) const {return id == arc.id;}
 		      bool operator!=(const Arc& arc) const {return id != arc.id;}
 		      bool operator<(const Arc& arc) const {return id < arc.id;}
 		    };
 		    ListDigraphBase()
 		      : nodes(), first_node(-1),
 			first_free_node(-1), arcs(), first_free_arc(-1) {}
 		    int maxNodeId() const { return nodes.size()-1; }
 		    int maxArcId() const { return arcs.size()-1; }
 		    Node source(Arc e) const { return Node(arcs[e.id].source); }
 		    Node target(Arc e) const { return Node(arcs[e.id].target); }
 		    void first(Node& node) const {
 		      node.id = first_node;
+		    }
 		    void next(Node& node) const {
 		      node.id = nodes[node.id].next;
+		    }
 		    void first(Arc& arc) const {
 		      int n;
 		      for(n = first_node;
 			  n!=-1 && nodes[n].first_in == -1;
-			  n = nodes[n].next);
+			  n = nodes[n].next) {}
 		      arc.id = (n == -1) ? -1 : nodes[n].first_in;
+		    }
 		    void next(Arc& arc) const {
 		      if (arcs[arc.id].next_in != -1) {
 			arc.id = arcs[arc.id].next_in;
 		      } else {
 			int n;
 			for(n = nodes[arcs[arc.id].target].next;
 			  n!=-1 && nodes[n].first_in == -1;
-			  n = nodes[n].next);
+			    n = nodes[n].next) {}
 			arc.id = (n == -1) ? -1 : nodes[n].first_in;
+		      }
+		    }
 		    void firstOut(Arc &e, const Node& v) const {
 		      e.id = nodes[v.id].first_out;
+		    }
 		    void nextOut(Arc &e) const {
 		      e.id=arcs[e.id].next_out;
+		    }
 		    void firstIn(Arc &e, const Node& v) const {
 		      e.id = nodes[v.id].first_in;
+		    }
 		    void nextIn(Arc &e) const {
 		      e.id=arcs[e.id].next_in;
+		    }
 		    static int id(Node v) { return v.id; }
 		    static int id(Arc e) { return e.id; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    bool valid(Node n) const {
 		      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
 			nodes[n.id].prev != -2;
+		    }
 		    bool valid(Arc a) const {
 		      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
 			arcs[a.id].prev_in != -2;
+		    }
 		    Node addNode() {
 		      int n;
 		      if(first_free_node==-1) {
 			n = nodes.size();
 			nodes.push_back(NodeT());
 		      } else {
 			n = first_free_node;
 			first_free_node = nodes[n].next;
+		      }
 		      nodes[n].next = first_node;
 		      if(first_node != -1) nodes[first_node].prev = n;
 		      first_node = n;
 		      nodes[n].prev = -1;
 		      nodes[n].first_in = nodes[n].first_out = -1;
 		      return Node(n);
+		    }
 		    Arc addArc(Node u, Node v) {
 		      int n;
 		      if (first_free_arc == -1) {
 			n = arcs.size();
 			arcs.push_back(ArcT());
 		      } else {
 			n = first_free_arc;
 			first_free_arc = arcs[n].next_in;
+		      }
 		      arcs[n].source = u.id;
 		      arcs[n].target = v.id;
 		      arcs[n].next_out = nodes[u.id].first_out;
 		      if(nodes[u.id].first_out != -1) {
 			arcs[nodes[u.id].first_out].prev_out = n;
+		      }
 		      arcs[n].next_in = nodes[v.id].first_in;
 		      if(nodes[v.id].first_in != -1) {
 			arcs[nodes[v.id].first_in].prev_in = n;
+		      }
 		      arcs[n].prev_in = arcs[n].prev_out = -1;
 		      nodes[u.id].first_out = nodes[v.id].first_in = n;
 		      return Arc(n);
+		    }
 		    void erase(const Node& node) {
 		      int n = node.id;
 		      if(nodes[n].next != -1) {
 			nodes[nodes[n].next].prev = nodes[n].prev;
+		      }
 		      if(nodes[n].prev != -1) {
 			nodes[nodes[n].prev].next = nodes[n].next;
 		      } else {
 			first_node = nodes[n].next;
+		      }
 		      nodes[n].next = first_free_node;
 		      first_free_node = n;
 		      nodes[n].prev = -2;
+		    }
 		    void erase(const Arc& arc) {
 		      int n = arc.id;
 		      if(arcs[n].next_in!=-1) {
 			arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
+		      }
 		      if(arcs[n].prev_in!=-1) {
 			arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
 		      } else {
 			nodes[arcs[n].target].first_in = arcs[n].next_in;
+		      }
 		      if(arcs[n].next_out!=-1) {
 			arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+		      }
 		      if(arcs[n].prev_out!=-1) {
 			arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 		      } else {
 			nodes[arcs[n].source].first_out = arcs[n].next_out;
+		      }
 		      arcs[n].next_in = first_free_arc;
 		      first_free_arc = n;
 		      arcs[n].prev_in = -2;
+		    }
 		    void clear() {
 		      arcs.clear();
 		      nodes.clear();
 		      first_node = first_free_node = first_free_arc = -1;
+		    }
 		  protected:
 		    void changeTarget(Arc e, Node n)
+		    {
 		      if(arcs[e.id].next_in != -1)
 			arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
 		      if(arcs[e.id].prev_in != -1)
 			arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
 		      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
 		      if (nodes[n.id].first_in != -1) {
 			arcs[nodes[n.id].first_in].prev_in = e.id;
+		      }
 		      arcs[e.id].target = n.id;
 		      arcs[e.id].prev_in = -1;
 		      arcs[e.id].next_in = nodes[n.id].first_in;
 		      nodes[n.id].first_in = e.id;
+		    }
 		    void changeSource(Arc e, Node n)
+		    {
 		      if(arcs[e.id].next_out != -1)
 			arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
 		      if(arcs[e.id].prev_out != -1)
 			arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
 		      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
 		      if (nodes[n.id].first_out != -1) {
 			arcs[nodes[n.id].first_out].prev_out = e.id;
+		      }
 		      arcs[e.id].source = n.id;
 		      arcs[e.id].prev_out = -1;
 		      arcs[e.id].next_out = nodes[n.id].first_out;
 		      nodes[n.id].first_out = e.id;
+		    }
 		  };
 		  typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
 		  /// \addtogroup graphs
 		  /// @{
 		  ///A general directed graph structure.
 		  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
 		  ///implementation based on static linked lists that are stored in
 		  ///\c std::vector structures.
 		  ///
 		  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
 		  ///also provides several useful additional functionalities.
 		  ///Most of the member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///An important extra feature of this digraph implementation is that
 		  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
 		  ///
 		  ///\sa concepts::Digraph
 		  class ListDigraph : public ExtendedListDigraphBase {
 		  private:
 		    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 		    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
 		    ///
 		    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
 		    ///\brief Assignment of ListDigraph to another one is \e not allowed.
 		    ///Use copyDigraph() instead.
 		    ///Assignment of ListDigraph to another one is \e not allowed.
 		    ///Use copyDigraph() instead.
 		    void operator=(const ListDigraph &) {}
 		  public:
 		    typedef ExtendedListDigraphBase Parent;
 		    /// Constructor
 		    /// Constructor.
 		    ///
 		    ListDigraph() {}
 		    ///Add a new node to the digraph.
 		    ///Add a new node to the digraph.
 		    ///\return the new node.
 		    Node addNode() { return Parent::addNode(); }
 		    ///Add a new arc to the digraph.
 		    ///Add a new arc to the digraph with source node \c s
 		    ///and target node \c t.
 		    ///\return the new arc.
 		    Arc addArc(const Node& s, const Node& t) {
 		      return Parent::addArc(s, t);
+		    }
 		    /// Node validity check
 		    /// This function gives back true if the given node is valid,
 		    /// ie. it is a real node of the graph.
 		    ///
 		    /// \warning A Node pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// Arc validity check
 		    /// This function gives back true if the given arc is valid,
 		    /// ie. it is a real arc of the graph.
 		    ///
 		    /// \warning An Arc pointing to a removed item
 		    /// could become valid again later if new nodes are
 		    /// added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// Change the target of \c e to \c n
 		    /// Change the target of \c e to \c n
 		    ///
 		    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
 		    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void changeTarget(Arc e, Node n) {
 		      Parent::changeTarget(e,n);
+		    }
 		    /// Change the source of \c e to \c n
 		    /// Change the source of \c e to \c n
 		    ///
 		    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
 		    ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void changeSource(Arc e, Node n) {
 		      Parent::changeSource(e,n);
+		    }
 		    /// Invert the direction of an arc.
 		    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
 		    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void reverseArc(Arc e) {
 		      Node t=target(e);
 		      changeTarget(e,source(e));
 		      changeSource(e,t);
+		    }
 		    /// Reserve memory for nodes.
 		    /// Using this function it is possible to avoid the superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be very large (e.g. it will contain millions of nodes and/or arcs)
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveArc
 		    void reserveNode(int n) { nodes.reserve(n); };
 		    /// Reserve memory for arcs.
 		    /// Using this function it is possible to avoid the superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be very large (e.g. it will contain millions of nodes and/or arcs)
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveNode
 		    void reserveArc(int m) { arcs.reserve(m); };
 		    ///Contract two nodes.
 		    ///This function contracts two nodes.
 		    ///Node \p b will be removed but instead of deleting
 		    ///incident arcs, they will be joined to \p a.
 		    ///The last parameter \p r controls whether to remove loops. \c true
 		    ///means that loops will be removed.
 		    ///
 		    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
 		    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
 		    ///may be invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void contract(Node a, Node b, bool r = true)
+		    {
 		      for(OutArcIt e(*this,b);e!=INVALID;) {
 			OutArcIt f=e;
 			++f;
 			if(r && target(e)==a) erase(e);
 			else changeSource(e,a);
 			e=f;
+		      }
 		      for(InArcIt e(*this,b);e!=INVALID;) {
 			InArcIt f=e;
 			++f;
 			if(r && source(e)==a) erase(e);
 			else changeTarget(e,a);
 			e=f;
+		      }
 		      erase(b);
+		    }
 		    ///Split a node.
 		    ///This function splits a node. First a new node is added to the digraph,
 		    ///then the source of each outgoing arc of \c n is moved to this new node.
 		    ///If \c connect is \c true (this is the default value), then a new arc
 		    ///from \c n to the newly created node is also added.
 		    ///\return The newly created node.
 		    ///
 		    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
 		    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
 		    ///be invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    ///
 		    ///\todo It could be implemented in a bit faster way.
 		    Node split(Node n, bool connect = true) {
 		      Node b = addNode();
 		      for(OutArcIt e(*this,n);e!=INVALID;) {
 		 	OutArcIt f=e;
 			++f;
 			changeSource(e,b);
 			e=f;
+		      }
 		      if (connect) addArc(n,b);
 		      return b;
+		    }
 		    ///Split an arc.
 		    ///This function splits an arc. First a new node \c b is added to
 		    ///the digraph, then the original arc is re-targeted to \c
 		    ///b. Finally an arc from \c b to the original target is added.
 		    ///
 		    ///\return The newly created node.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    Node split(Arc e) {
 		      Node b = addNode();
 		      addArc(b,target(e));
 		      changeTarget(e,b);
 		      return b;
+		    }
 		    /// \brief Class to make a snapshot of the digraph and restore
 		    /// it later.
 		    ///
 		    /// Class to make a snapshot of the digraph and restore it later.
 		    ///
 		    /// The newly added nodes and arcs can be removed using the
 		    /// restore() function.
 		    ///
 		    /// \warning Arc and node deletions and other modifications (e.g.
 		    /// contracting, splitting, reversing arcs or nodes) cannot be
 		    /// restored. These events invalidate the snapshot.
 		    class Snapshot {
 		    protected:
 		      typedef Parent::NodeNotifier NodeNotifier;
 		      class NodeObserverProxy : public NodeNotifier::ObserverBase {
 		      public:
 		        NodeObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using NodeNotifier::ObserverBase::attach;
 		        using NodeNotifier::ObserverBase::detach;
 		        using NodeNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Node& node) {
 		          snapshot.addNode(node);
+		        }
 		        virtual void add(const std::vector<Node>& nodes) {
 		          for (int i = nodes.size() - 1; i >= 0; ++i) {
 		            snapshot.addNode(nodes[i]);
+		          }
+		        }
 		        virtual void erase(const Node& node) {
 		          snapshot.eraseNode(node);
+		        }
 		        virtual void erase(const std::vector<Node>& nodes) {
 		          for (int i = 0; i < int(nodes.size()); ++i) {
 		            snapshot.eraseNode(nodes[i]);
+		          }
+		        }
 		        virtual void build() {
 		          Node node;
 		          std::vector<Node> nodes;
 		          for (notifier()->first(node); node != INVALID;
 		               notifier()->next(node)) {
 		            nodes.push_back(node);
+		          }
 		          for (int i = nodes.size() - 1; i >= 0; --i) {
 		            snapshot.addNode(nodes[i]);
+		          }
+		        }
 		        virtual void clear() {
 		          Node node;
 		          for (notifier()->first(node); node != INVALID;
 		               notifier()->next(node)) {
 		            snapshot.eraseNode(node);
+		          }
+		        }
 		        Snapshot& snapshot;
 		      };
 		      class ArcObserverProxy : public ArcNotifier::ObserverBase {
 		      public:
 		        ArcObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using ArcNotifier::ObserverBase::attach;
 		        using ArcNotifier::ObserverBase::detach;
 		        using ArcNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Arc& arc) {
 		          snapshot.addArc(arc);
+		        }
 		        virtual void add(const std::vector<Arc>& arcs) {
 		          for (int i = arcs.size() - 1; i >= 0; ++i) {
 		            snapshot.addArc(arcs[i]);
+		          }
+		        }
 		        virtual void erase(const Arc& arc) {
 		          snapshot.eraseArc(arc);
+		        }
 		        virtual void erase(const std::vector<Arc>& arcs) {
 		          for (int i = 0; i < int(arcs.size()); ++i) {
 		            snapshot.eraseArc(arcs[i]);
+		          }
+		        }
 		        virtual void build() {
 		          Arc arc;
 		          std::vector<Arc> arcs;
 		          for (notifier()->first(arc); arc != INVALID;
 		               notifier()->next(arc)) {
 		            arcs.push_back(arc);
+		          }
 		          for (int i = arcs.size() - 1; i >= 0; --i) {
 		            snapshot.addArc(arcs[i]);
+		          }
+		        }
 		        virtual void clear() {
 		          Arc arc;
 		          for (notifier()->first(arc); arc != INVALID;
 		               notifier()->next(arc)) {
 		            snapshot.eraseArc(arc);
+		          }
+		        }
 		        Snapshot& snapshot;
 		      };
 		      ListDigraph *digraph;
 		      NodeObserverProxy node_observer_proxy;

test/test_tools.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_TEST_TEST_TOOLS_H
 		#define LEMON_TEST_TEST_TOOLS_H
 		///\ingroup misc
 		///\file
 		///\brief Some utilities to write test programs.
 		#include <iostream>
 		#include <stdlib.h>
 		///If \c rc is fail, writes an error message and exits.
 		///If \c rc is fail, writes an error message and exits.
 		///The error message contains the file name and the line number of the
 		///source code in a standard from, which makes it possible to go there
 		///using good source browsers like e.g. \c emacs.
 		///
 		///For example
 		///\code check(0==1,"This is obviously false.");\endcode will
 		///print something like this (and then exits).
 		///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
 		///
 		///\todo It should be in \c assert.h
 		#define check(rc, msg) \
 		  if(!(rc)) { \
 		    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
 		    abort(); \
 		  } else { } \
 		#endif

0 comments (0 inline)

RhodeCode

Login to your account