RhodeCode

The dual solution of the minimum cost flow problem is represented by

node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.

An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal

if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials

the following \e complementary \e slackness optimality conditions hold.

 - For all \f$uv\in A\f$ arcs:

   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;

   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

 - For all \f$u\in V\f$ nodes:

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc

\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.

\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]

All algorithms provide dual solution (node potentials), as well,

if an optimal flow is found.

\section mcf_eq Equality Form

Note that the optimality conditions for this supply constraint type are

slightly differ from the conditions that are discussed for the GEQ form,

namely the potentials have to be non-negative instead of non-positive.

An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem

is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$

node potentials the following conditions hold.

 - For all \f$uv\in A\f$ arcs:

   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;

   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

 - For all \f$u\in V\f$ nodes:

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

*/

}

    };

    template <class T>

    struct SetOperationTraitsTraits : public Traits {

      typedef T OperationTraits;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting 

    /// \c OperationTraits type.

    ///

    /// \ref named-templ-param "Named parameter" for setting

    /// \c OperationTraits type.

    template <class T>

    struct SetOperationTraits

      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {

      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >

      Create;

    };

    ///@}

  protected:

    BellmanFord() {}

    /// using this function.

    Value dist(Node v) const { return (*_dist)[v]; }

    /// \brief Returns the 'previous arc' of the shortest path tree for

    /// the given node.

    ///

    /// This function returns the 'previous arc' of the shortest path

    /// tree for node \c v, i.e. it returns the last arc of a

    /// shortest path from a root to \c v. It is \c INVALID if \c v

    /// is not reached from the root(s) or if \c v is a root.

    ///

    /// The shortest path tree used here is equal to the shortest path

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    Arc predArc(Node v) const { return (*_pred)[v]; }

    /// \brief Returns the 'previous node' of the shortest path tree for

    /// the given node.

    ///

    /// This function returns the 'previous node' of the shortest path

    /// tree for node \c v, i.e. it returns the last but one node of

    /// a shortest path from a root to \c v. It is \c INVALID if \c v

    /// is not reached from the root(s) or if \c v is a root.

    ///

    /// The shortest path tree used here is equal to the shortest path

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    Node predNode(Node v) const { 

      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 

    }

    /// \brief Returns a const reference to the node map that stores the

    /// distances of the nodes.

    ///

    /// Returns a const reference to the node map that stores the distances

    /// of the nodes calculated by the algorithm.

    ///This function instantiates a \ref PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \c ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the \ref ProcessedMap

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

    ///This function instantiates a PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

        return new Elevator(digraph, max_level);

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// Elevator type with automatic allocation

    ///

    /// \ref named-templ-param "Named parameter" for setting Elevator

    /// type with automatic allocation.

    /// The Elevator should have standard constructor interface to be

    /// able to automatically created by the algorithm (i.e. the

    /// digraph and the maximum level should be passed to it).

    /// algorithm with the \ref elevator(Elevator&) "elevator()" function

    /// before calling \ref run() or \ref init().

    /// \sa SetElevator

    template <typename T>

    struct SetStandardElevator

      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

                       SetStandardElevatorTraits<T> > {

      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

                      SetStandardElevatorTraits<T> > Create;

    };

    /// @}

        /// Artificial ordering operator.

        ///

        /// \note This operator only has to define some strict ordering of

        /// the nodes; this order has nothing to do with the iteration

        /// ordering of the nodes.

        bool operator<(Node) const { return false; }

      };

      /// Iterator class for the nodes.

      /// This iterator goes through each node of the digraph.

      /// of nodes in a digraph \c g of type \c %Digraph like this:

      ///\code

      /// int count=0;

      /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;

      ///\endcode

      class NodeIt : public Node {

      public:

        /// Default constructor

        /// Default constructor.

        /// \warning It sets the iterator to an undefined value.

        NodeIt() { }

        /// Artificial ordering operator.

        ///

        /// \note This operator only has to define some strict ordering of

        /// the arcs; this order has nothing to do with the iteration

        /// ordering of the arcs.

        bool operator<(Arc) const { return false; }

      };

      /// Iterator class for the outgoing arcs of a node.

      /// This iterator goes trough the \e outgoing arcs of a certain node

      /// of a digraph.

      /// of outgoing arcs of a node \c n

      /// in a digraph \c g of type \c %Digraph as follows.

      ///\code

      /// int count=0;

      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;

      ///\endcode

      class OutArcIt : public Arc {

      public:

        /// Default constructor

        /// Default constructor.

        /// \warning It sets the iterator to an undefined value.

        OutArcIt(const Digraph&, const Arc&) { }

        /// Next outgoing arc

        /// Assign the iterator to the next

        /// outgoing arc of the corresponding node.

        OutArcIt& operator++() { return *this; }

      };

      /// Iterator class for the incoming arcs of a node.

      /// This iterator goes trough the \e incoming arcs of a certain node

      /// of a digraph.

      /// of incoming arcs of a node \c n

      /// in a digraph \c g of type \c %Digraph as follows.

      ///\code

      /// int count=0;

      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;

      ///\endcode

      class InArcIt : public Arc {

      public:

        /// Default constructor

        /// Default constructor.

        /// \warning It sets the iterator to an undefined value.

        ///

        InArcIt(const Digraph&, const Arc&) { }

        /// Next incoming arc

        /// Assign the iterator to the next

        /// incoming arc of the corresponding node.

        InArcIt& operator++() { return *this; }

      };

      /// Iterator class for the arcs.

      /// This iterator goes through each arc of the digraph.

      /// of arcs in a digraph \c g of type \c %Digraph as follows:

      ///\code

      /// int count=0;

      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;

      ///\endcode

      class ArcIt : public Arc {

      public:

        /// Default constructor

        /// Default constructor.

        /// \warning It sets the iterator to an undefined value.

        ArcIt() { }

        /// Artificial ordering operator.

        ///

        /// \note This operator only has to define some strict ordering of

        /// the items; this order has nothing to do with the iteration

        /// ordering of the items.

        bool operator<(Node) const { return false; }

      };

      /// Iterator class for the nodes.

      /// This iterator goes through each node of the graph.

      /// of nodes in a graph \c g of type \c %Graph like this:

      ///\code

      /// int count=0;

      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;

      ///\endcode

      class NodeIt : public Node {

      public:

        /// Default constructor

        /// Default constructor.

        /// \warning It sets the iterator to an undefined value.

        NodeIt() { }

        /// Artificial ordering operator.

        ///

        /// \note This operator only has to define some strict ordering of

        /// the edges; this order has nothing to do with the iteration

        /// ordering of the edges.

        bool operator<(Edge) const { return false; }

      };

      /// Iterator class for the edges.

      /// This iterator goes through each edge of the graph.

      /// of edges in a graph \c g of type \c %Graph as follows:

      ///\code

      /// int count=0;

      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;

      ///\endcode

      class EdgeIt : public Edge {

      public:

        /// Default constructor

        /// Default constructor.

        /// \warning It sets the iterator to an undefined value.

        EdgeIt() { }

        EdgeIt(const Graph&, const Edge&) { }

        /// Next edge

        /// Assign the iterator to the next edge.

        ///

        EdgeIt& operator++() { return *this; }

      };

      /// Iterator class for the incident edges of a node.

      /// This iterator goes trough the incident undirected edges

      /// of a certain node of a graph.

      /// degree (i.e. the number of incident edges) of a node \c n

      /// in a graph \c g of type \c %Graph as follows.

      ///

      ///\code

      /// int count=0;

      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;

      ///\endcode

      ///

      /// \warning Loop edges will be iterated twice.

      class IncEdgeIt : public Edge {

      public:

        /// Default constructor

        bool operator<(Arc) const { return false; }

        /// Converison to \c Edge

        /// Converison to \c Edge.

        ///

        operator Edge() const { return Edge(); }

      };

      /// Iterator class for the arcs.

      /// This iterator goes through each directed arc of the graph.

      /// of arcs in a graph \c g of type \c %Graph as follows:

      ///\code

      /// int count=0;

      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;

      ///\endcode

      class ArcIt : public Arc {

      public:

        /// Default constructor

        /// Default constructor.

        /// \warning It sets the iterator to an undefined value.

        ArcIt() { }

        ArcIt(const Graph&, const Arc&) { }

        /// Next arc

        /// Assign the iterator to the next arc.

        ///

        ArcIt& operator++() { return *this; }

      };

      /// Iterator class for the outgoing arcs of a node.

      /// This iterator goes trough the \e outgoing directed arcs of a

      /// certain node of a graph.

      /// of outgoing arcs of a node \c n

      /// in a graph \c g of type \c %Graph as follows.

      ///\code

      /// int count=0;

      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;

      ///\endcode

      class OutArcIt : public Arc {

      public:

        /// Default constructor

        /// Default constructor.

        /// \warning It sets the iterator to an undefined value.

        OutArcIt(const Graph&, const Arc&) { }

        /// Next outgoing arc

        /// Assign the iterator to the next

        /// outgoing arc of the corresponding node.

        OutArcIt& operator++() { return *this; }

      };

      /// Iterator class for the incoming arcs of a node.

      /// This iterator goes trough the \e incoming directed arcs of a

      /// certain node of a graph.

      /// of incoming arcs of a node \c n

      /// in a graph \c g of type \c %Graph as follows.

      ///\code

      /// int count=0;

      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;

      ///\endcode

      class InArcIt : public Arc {

      public:

        /// Default constructor

        /// Default constructor.

        /// \warning It sets the iterator to an undefined value.

        ///Assignment operator

        template <typename CMap>

        EdgeMap& operator=(const CMap&) {

          checkConcept<ReadMap<Edge, T>, CMap>();

          return *this;

        }

      };

      /// \brief The first node of the edge.

      ///

      /// Returns the first node of the given edge.

      ///

      /// u() and v() are used to query the two end-nodes of an edge.

      /// The orientation of an edge that arises this way is called

      /// the inherent direction, it is used to define the default

      /// direction for the corresponding arcs.

      /// \sa v()

      /// \sa direction()

      Node u(Edge) const { return INVALID; }

      /// \brief The second node of the edge.

      ///

      /// Returns the second node of the given edge.

      ///

      /// u() and v() are used to query the two end-nodes of an edge.

      /// The orientation of an edge that arises this way is called

      /// the inherent direction, it is used to define the default

      /// direction for the corresponding arcs.

      /// \sa u()

      /// \sa direction()

      Node v(Edge) const { return INVALID; }

      /// \brief The source node of the arc.

      ///

      /// Returns the source node of the given arc.

      Node source(Arc) const { return INVALID; }

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

///\ingroup graph_concepts

///\file

#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H

#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H

#include <lemon/core.h>

#include <lemon/concepts/maps.h>

#include <lemon/bits/alteration_notifier.h>

namespace lemon {

  namespace concepts {

    /// Resets the counter to the given value.

    /// \note This function does not reset the values of

    /// \ref SubCounter "SubCounter"s but it resets \ref NoSubCounter

    /// "NoSubCounter"s along with the main counter.

    void reset(int c=0) {count=c;}

    /// Returns the value of the counter.

    operator int() {return count;}

  };

  /// 'Do nothing' version of Counter.

  /// does not count at all and does not print report on destruction.

  ///

  /// Replacing a \ref Counter with a \ref NoCounter makes it possible

  /// to turn off all counting and reporting (SubCounters should also

  /// be replaced with NoSubCounters), so it does not affect the

  /// efficiency of the program at all.

  ///

  /// \sa Counter

  class NoCounter

  {

  public:

    typedef _NoSubCounter<NoCounter> SubCounter;

    ///This function instantiates a \ref PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \c ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the \ref ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

    ///This function instantiates a PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

    ///This function instantiates a \ref PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \c ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the \ref ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

        return new Heap(R);

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///heap and cross reference types with automatic allocation

    ///

    ///\ref named-templ-param "Named parameter" for setting heap and cross

    ///reference types with automatic allocation.

    ///They should have standard constructor interfaces to be able to

    ///automatically created by the algorithm (i.e. the digraph should be

    ///passed to the constructor of the cross reference and the cross

    ///reference should be passed to the constructor of the heap).

    ///passed to the algorithm using the \ref heap() function before

    ///calling \ref run(Node) "run()" or \ref init().

    ///\sa SetHeap

    template <class H, class CR = typename Digraph::template NodeMap<int> >

    struct SetStandardHeap

      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {

      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >

      Create;

    };

    template <class T>

    struct SetOperationTraitsTraits : public Traits {

      typedef T OperationTraits;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    ///\c OperationTraits type

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\c OperationTraits type.

    template <class T>

    struct SetOperationTraits

      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {

      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >

      Create;

    };

    ///@}

  protected:

    Dijkstra() {}

    ///This function instantiates a PredMap.

    ///\param g is the digraph, to which we would like to define the

    ///PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

    ///\param g is the digraph, to which

    ///we would like to define the ProcessedMap.

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#else

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

    /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.

    ///

    /// \param s The base node.

    /// \param t The node you want to separate from node \c s.

    /// \param cutMap The cut will be returned in this map.

    /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap

    /// "ReadWriteMap" on the graph nodes.

    ///

    /// \return The value of the minimum cut between \c s and \c t.

    ///

    /// \pre \ref run() must be called before using this function.

    template <typename CutMap>

                    const Node& t,

                    CutMap& cutMap

                    ) const {

      Node sn = s, tn = t;

      bool s_root=false;

      Node rn = INVALID;

      Value value = std::numeric_limits<Value>::max();

      while (sn != tn) {

	if ((*_order)[sn] < (*_order)[tn]) {

	  if ((*_weight)[tn] <= value) {

	    rn = tn;

            s_root = false;

	    value = (*_weight)[tn];

                   ///< If it is \c true (default) then the iterator lists

                   ///  the nodes of the component containing \c s,

                   ///  otherwise it lists the other component.

                   /// \note As the minimum cut is not always unique,

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, true);

                   /// \endcode

                   /// and

                   /// \code

                   /// MinCutNodeIt(gomory, t, s, false);

                   /// \endcode

                   /// does not necessarily give the same set of nodes.

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, true);

                   /// \endcode

                   /// and

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, false);

                   /// \endcode

                   /// together list each node exactly once.

                   )

        : _side(side), _cut(gomory._graph)

      {

        gomory.minCutMap(s,t,_cut);

  bool _absoluteNodeSizes;

  bool _absoluteArcWidths;

  bool _negY;

  bool _preScale;

  ///Constructor

  ///Constructor

  ///\param gr  Reference to the graph to be printed.

  ///\param ost Reference to the output stream.

  ///\param pros If it is \c true, then the \c ostream referenced by \c os

  ///will be explicitly deallocated by the destructor.

  DefaultGraphToEpsTraits(const GR &gr, std::ostream& ost = std::cout,

                          bool pros = false) :

    g(gr), os(ost),

    _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0),

    _nodeColors(WHITE), _arcColors(BLACK),

    _arcWidths(1.0), _arcWidthScale(0.003),

    _nodeScale(.01), _xBorder(10), _yBorder(10), _scale(1.0),

    _nodeBorderQuotient(.1),

    _drawArrows(false), _arrowLength(1), _arrowWidth(0.3),

    _showNodes(true), _showArcs(true),

  ///

  GraphToEps<T> &absoluteNodeSizes(bool b=true) {

    _absoluteNodeSizes=b;return *this;

  }

  ///Negates the Y coordinates.

  GraphToEps<T> &negateY(bool b=true) {

    _negY=b;return *this;

  }

  ///Turn on/off pre-scaling

  ///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.

  ///

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 Reference to the graph to be printed.

///\param os Reference to the output stream.

///

///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(GR &g, const char *file_name)

template<class GR>

GraphToEps<DefaultGraphToEpsTraits<GR> >

graphToEps(GR &g, std::ostream& os=std::cout)

{

  return

    GraphToEps<DefaultGraphToEpsTraits<GR> >(DefaultGraphToEpsTraits<GR>(g,os));

}

  typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;

  /// \ingroup graphs

  ///

  /// \brief Hypercube graph class

  ///

  /// HypercubeGraph implements a special graph type. The nodes of the

  /// graph are indexed with integers having at most \c dim binary digits.

  /// Two nodes are connected in the graph if and only if their indices

  /// differ only on one position in the binary form.

  /// This class is completely static and it needs constant memory space.

  /// the structure can be resized using resize().

  ///

  /// This type fully conforms to the \ref concepts::Graph "Graph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  ///

  /// \note The type of the indices is chosen to \c int for efficiency

  /// reasons. Thus the maximum dimension of this implementation is 26

  /// (assuming that the size of \c int is 32 bit).

  class HypercubeGraph : public ExtendedHypercubeGraphBase {

    typedef ExtendedHypercubeGraphBase Parent;

  /// rules.

  ///

  ///\code

  /// DigraphReader<DGR>(digraph, std::cin).

  ///   nodeMap("coordinates", coord_map).

  ///   arcMap("capacity", cap_map).

  ///   node("source", src).

  ///   node("target", trg).

  ///   attribute("caption", caption).

  ///   run();

  ///\endcode

  ///

  /// proper type. If a section has an optional name, then it can be

  /// selected for reading by giving an optional name parameter to the

  /// \c nodes(), \c arcs() or \c attributes() functions.

  ///

  /// The \c useNodes() and \c useArcs() functions are used to tell the reader

  /// that the nodes or arcs should not be constructed (added to the

  /// graph) during the reading, but instead the label map of the items

  /// are given as a parameter of these functions. An

  /// application of these functions is multipass reading, which is

  /// important if two \c \@arcs sections must be read from the

  /// file. In this case the first phase would read the node set and one

  /// of the arc sets, while the second phase would read the second arc

    /// \name Section Readers

    /// @{

    /// \brief Add a section processor with line oriented reading

    ///

    /// The first parameter is the type descriptor of the section, the

    /// second is a functor, which takes just one \c std::string

    /// parameter. At the reading process, each line of the section

    /// will be given to the functor object. However, the empty lines

    /// and the comment lines are filtered out, and the leading

    /// whitespaces are trimmed from each processed string.

    ///

    /// integers, which should be inserted into a vector.

    ///\code

    ///  @numbers

    ///  12 45 23

    ///  4

    ///  23 6

    ///\endcode

    ///

    /// The functor is implemented as a struct:

    ///\code

    ///  struct NumberSection {

    ///    std::vector<int>& _data;

    /// This function gives back \c true if the given arc is valid,

    /// i.e. it is a real arc of the digraph.

    ///

    /// \warning A removed arc could become valid again if new arcs are

    /// added to the digraph.

    bool valid(Arc a) const { return Parent::valid(a); }

    /// Change the target node of an arc

    /// This function changes the target node of the given arc \c a to \c n.

    ///

    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void changeTarget(Arc a, Node n) {

      Parent::changeTarget(a,n);

    }

    /// Change the source node of an arc

    /// This function changes the source node of the given arc \c a to \c n.

    ///

    ///\note \c InArcIt iterators referencing the changed arc remain

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void changeSource(Arc a, Node n) {

      Parent::changeSource(a,n);

    }

    /// Reverse the direction of an arc.

    /// This function reverses the direction of the given arc.

    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing

    ///the changed arc are invalidated.

    /// 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.

    ///

    /// \note After a state is restored, you cannot restore a later state, 

    /// i.e. you cannot add the removed nodes and arcs again using

    /// another Snapshot instance.

    ///

    /// \warning Node and arc deletions and other modifications (e.g.

    /// reversing, contracting, splitting arcs or nodes) cannot be

    /// restored. These events invalidate the snapshot.

    /// making the current snapshot can be removed without invalidating it.

    class Snapshot {

    protected:

      typedef Parent::NodeNotifier NodeNotifier;

      class NodeObserverProxy : public NodeNotifier::ObserverBase {

      public:

        NodeObserverProxy(Snapshot& _snapshot)

          : snapshot(_snapshot) {}

    ///base node is the changed node are also invalidated.

    ///

    ///\warning This functionality cannot be used together with the

    ///Snapshot feature.

    void changeU(Edge e, Node n) {

      Parent::changeU(e,n);

    }

    /// \brief Change the second node of an edge.

    ///

    /// This function changes the second node of the given edge \c e to \c n.

    ///

    ///\note \c EdgeIt iterators referencing the changed edge remain

    ///all other iterators whose base node is the changed node are also

    ///invalidated.

    ///

    ///\warning This functionality cannot be used together with the

    ///Snapshot feature.

    void changeV(Edge e, Node n) {

      Parent::changeV(e,n);

    }