RhodeCode

\code

ALL_UPPER_CASE_WITH_UNDERSCORES

\endcode

\subsection cs-loc-var Class and instance member variables, auto variables

\code

all_lower_case_with_underscores

\endcode

\subsection pri-loc-var Private member variables

a single target that is maximum. Formally, there is a \f$G=(V,A)\f$

directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity

function and given \f$s, t \in V\f$ source and target node. The

maximum flow is the \f$f_a\f$ solution of the next optimization problem:

\f[ 0 \le f_a \le c_a \f]

\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]

LEMON contains several algorithms for solving maximum flow problems:

- \ref lemon::EdmondsKarp "Edmonds-Karp"

- \ref lemon::Preflow "Goldberg's Preflow algorithm"

- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"

The minimum cut problem is to find a non-empty and non-complete

\f$X\f$ subset of the vertices with minimum overall capacity on

outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an

\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

cut is the \f$X\f$ solution of the next optimization problem:

LEMON contains several algorithms related to minimum cut problems:

- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut

  in directed graphs

- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to

/**

@defgroup planar Planarity embedding and drawing

@ingroup algs

\brief Algorithms for planarity checking, embedding and drawing

\image html planar.png

\image latex planar.eps "Plane graph" width=\textwidth

*/

/**

/**

@defgroup lemon_io Lemon Input-Output

@ingroup io_group

\brief Reading and writing \ref lgf-format "Lemon Graph Format".

*/

/**

@defgroup eps_io Postscript exporting

@ingroup io_group

\brief General \c EPS drawer and graph exporter

        {

          int set=0;

          for(GroupData::Opts::iterator o=i->second.opts.begin();

              o!=i->second.opts.end();++o)

            if(_opts.find(*o)->second.set) ++set;

          if(i->second.mandatory&&!set) {

            ok=false;

            for(GroupData::Opts::iterator o=i->second.opts.begin();

                o!=i->second.opts.end();++o)

              showHelp(_opts.find(*o));

          }

          if(i->second.only_one&&set>1) {

            ok=false;

            for(GroupData::Opts::iterator o=i->second.opts.begin();

                o!=i->second.opts.end();++o)

              showHelp(_opts.find(*o));

          }

        }

/// - \c LEMON_ASSERT_ABORT This mode is similar to the \c

///   LEMON_ASSERT_LOG, but it aborts the program. It is the default

///   behaviour.

/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler

///   function.

///   \code

///   \endcode

///   The name of the function should be defined as the \c

///   LEMON_CUSTOM_ASSERT_HANDLER macro name.

///   \code

///     #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler

///   \endcode

///   LEMON_ASSERT(false, msg);

/// \endcode

///

/// \see LEMON_ASSERT

#  define LEMON_FIXME(msg)                                                \

  (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \

                        static_cast<const char*>(0)))

/// \ingroup exceptions

///

/// \brief Macro for internal assertions

///

#    if LEMON_ENABLE_DEBUG

#      define LEMON_DEBUG(exp, msg)

         (static_cast<void> (!!(exp) ? 0 : (         \

           LEMON_ASSERT_HANDLER(__FILE__, __LINE__,  \

                                LEMON_FUNCTION_NAME, \

                                #exp), 0)))

#    else

#      define LEMON_DEBUG(exp, msg) (static_cast<void>(0))

#    endif

#  endif

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

    ///

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap.

    static DistMap *createDistMap(const GR &G)

    {

      return new DistMap(G);

    }

  };

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

    ///

    typedef NullMap<typename Digraph::Node,int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap.

#ifdef DOXYGEN

    static DistMap *createDistMap(const GR &g)

#else

    static DistMap *createDistMap(const GR &)

#endif

    {

  /// with visitor interface.

  ///

  /// The %BfsVisit class provides an alternative interface to the Bfs

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// on every bfs event the \c Visitor class member functions.

  ///

  /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it

  /// is only passed to \ref BfsDefaultTraits.

  /// \tparam _Visitor The Visitor object for the algorithm. The

  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which

  /// does not observe the Bfs events. If you want to observe the bfs

  /// events you should implement your own Visitor class.

    template<typename K, typename T>

    class ReadMap

    {

    public:

      /// The key type of the map.

      typedef K Key;

      typedef T Value;

      /// Returns the value associated with the given key.

      Value operator[](const Key &) const {

        return *static_cast<Value *>(0);

      }

    template<typename K, typename T>

    class WriteMap

    {

    public:

      /// The key type of the map.

      typedef K Key;

      typedef T Value;

      /// Sets the value associated with the given key.

      void set(const Key &, const Value &) {}

      /// Default constructor.

    class ReadWriteMap : public ReadMap<K,T>,

                         public WriteMap<K,T>

    {

    public:

      /// The key type of the map.

      typedef K Key;

      typedef T Value;

      /// Returns the value associated with the given key.

      Value operator[](const Key &) const {

        return *static_cast<Value *>(0);

      }

    {

    public:

      /// Tag for reference maps.

      typedef True ReferenceMapTag;

      /// The key type of the map.

      typedef K Key;

      typedef T Value;

      /// The reference type of the map.

      typedef R Reference;

      /// The const reference type of the map.

      typedef CR ConstReference;

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

    ///

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap.

    static DistMap *createDistMap(const GR &G)

    {

      return new DistMap(G);

    }

  };

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

    ///

    typedef NullMap<typename Digraph::Node,int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap.

#ifdef DOXYGEN

    static DistMap *createDistMap(const GR &g)

#else

    static DistMap *createDistMap(const GR &)

#endif

    {

  /// with visitor interface.

  ///

  /// The %DfsVisit class provides an alternative interface to the Dfs

  /// class. It works with callback mechanism, the DfsVisit object calls

  /// on every dfs event the \c Visitor class member functions.

  ///

  /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it

  /// is only passed to \ref DfsDefaultTraits.

  /// \tparam _Visitor The Visitor object for the algorithm. The

  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which

  /// does not observe the Dfs events. If you want to observe the dfs

  /// events you should implement your own Visitor class.

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

    static DistMap *createDistMap(const GR &G)

    {

      return new DistMap(G);

    }

  };

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

    };

    template <class T>

    struct DefDistMapTraits : public Traits {

      typedef T DistMap;

      static DistMap *createDistMap(const Digraph &)

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

    };

    struct DefDigraphProcessedMapTraits : public Traits {

      typedef typename Digraph::template NodeMap<bool> ProcessedMap;

      static ProcessedMap *createProcessedMap(const Digraph &G)

      {

    ///\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> {

    };

    template <class H, class CR>

    struct DefHeapTraits : public Traits {

      typedef CR HeapCrossRef;

      typedef H Heap;

    ///

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

    };

    template <class H, class CR>

    struct DefStandardHeapTraits : public Traits {

      typedef CR HeapCrossRef;

      typedef H Heap;

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

      Create;

    };

    template <class T>

    struct DefOperationTraitsTraits : public Traits {

      typedef T OperationTraits;

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

    ///

    typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap.

#ifdef DOXYGEN

    static DistMap *createDistMap(const GR &g)

#else

    static DistMap *createDistMap(const GR &)

#endif

    {

  bool _preScale;

  ///Constructor

  ///Constructor

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

  ///\param _os 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 G &_g,std::ostream& _os=std::cout,

                          bool _pros=false) :

    g(_g), os(_os),

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

    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";

    //x y r

    //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";

       << "   } 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"

       << "  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)

       << "  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"

       << "  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

       << "       /w exch def /len exch def\n"

       << "       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"

          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.source(*i)])+

//             dvec*(double(_nodeSizes[g.source(*i)])/

//                (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));

           m=dim2::Point<double>(mycoords[g.source(*i)])+

              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)

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

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

  /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).

  /// The previously read label node map should be passed to the \c

  /// useNodes() functions. Another application of multipass reading when

  /// a single pass, because the arcs are not constructed when the node

  /// maps are read.

  template <typename _Digraph>

  class DigraphReader {

  public:

    ///\name Control the state of the timer

    ///Basically a Timer can be either running or stopped,

    ///but it provides a bit finer control on the execution.

    ///The \ref Timer also counts the number of \ref start()

    ///executions, and is stops only after the same amount (or more)

    ///of recursive functions.

    ///

    ///@{

    ///Reset and stop the time counters

  check(pathSource(G, p) == s,"path() found a wrong path.");

  check(pathTarget(G, p) == t,"path() found a wrong path.");

  for(ArcIt e(G); e!=INVALID; ++e) {

    Node u=G.source(e);

    Node v=G.target(e);

  }

  for(NodeIt v(G); v!=INVALID; ++v){

    check(dijkstra_test.reached(v),"Each node should be reached.");

    if ( dijkstra_test.predArc(v)!=INVALID ) {

      Arc e=dijkstra_test.predArc(v);

      Node u=G.source(e);

      check(u==dijkstra_test.predNode(v),"Wrong tree.");

      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],

    }

  }

  {

    NullMap<Node,Arc> myPredMap;

    dijkstra(G,length).predMap(myPredMap).run(s);

    for (NodeIt src(fg); src != INVALID; ++src) {

      for (NodeIt trg(fg); trg != INVALID; ++trg) {

        Arc con1 = al1(src, trg);

        Arc con2 = al2(src, trg);

        Arc con3 = al3(src, trg);

        Arc con4 = findArc(fg, src, trg);

        check(con1 != INVALID, "There is no connecting arc.");

        check(fg.source(con1) == src, "Wrong source.");

        check(fg.target(con1) == trg, "Wrong target.");

      }

    }

  }

}

template <typename Graph>

  typename Graph::template EdgeMap<int> found(graph, 0);

  DescriptorMap<Graph, Edge> edges(graph);

  for (NodeIt src(graph); src != INVALID; ++src) {

    for (NodeIt trg(graph); trg != INVALID; ++trg) {

      for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {

        check( (graph.u(con) == src && graph.v(con) == trg) ||

        ++found[con];

        check(found[con] <= 2, "The edge found more than twice.");

      }

    }

  }

  for (EdgeIt it(graph); it != INVALID; ++it) {

    checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >();

    ConstMap<A,Const<int,10> > map6;

    ConstMap<A,Const<int,10> > map7 = map6;

    map6 = constMap<A,int,10>();

    map7 = constMap<A,Const<int,10> >();

  }

  // IdentityMap

  {

    checkConcept<ReadMap<A,A>, IdentityMap<A> >();

    IdentityMap<A> map1;

    IdentityMap<A> map2 = map1;

    map1 = identityMap<A>();

    checkConcept<ReadMap<double,double>, IdentityMap<double> >();

          "Something is wrong with IdentityMap");

  }

  // RangeMap

  {

    checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();

    std::map<double, int> m;

    SparseMap<double, int> map5(m);

    SparseMap<double, int> map6(m,10);

    SparseMap<double, int> map7 = sparseMap(m);

    SparseMap<double, int> map8 = sparseMap(m,10);

          "Something is wrong with SparseMap");

    map5[1.0] = map6[3.14] = 100;

          "Something is wrong with SparseMap");

  }

  // ComposeMap

  {

    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;

    checkConcept<ReadMap<B,double>, CompMap>();

    CompMap map1(DoubleMap(),ReadMap<B,A>());

    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());

    SparseMap<double, bool> m1(false); m1[3.14] = true;

    RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14;

  }

  // CombineMap

  {

    typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;

    checkConcept<ReadMap<A,double>, CombMap>();

    FunctorToMap<F> map2(F());

    B b = functorToMap(F())[A()];

    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();

    MapToFunctor<ReadMap<A,B> > map(ReadMap<A,B>());

          "Something is wrong with FunctorToMap or MapToFunctor");

    check(functorToMap(mapToFunctor(constMap<A,int>(2)))[A()] == 2,

          "Something is wrong with FunctorToMap or MapToFunctor");

  }

  // ConvertMap

  {

    ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));

    ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));

  }

  // ForkMap

  {

    SM m2(-1);

    checkConcept<ReadWriteMap<int, double>, ForkMap<RM, SM> >();

    checkConcept<ReadWriteMap<int, double>, ForkMap<SM, RM> >();

    ForkMap<RM, SM> map1(m1,m2);

    ForkMap<SM, RM> map2 = forkMap(m2,m1);

    map2.set(5, 10);

          "Something is wrong with ForkMap");

  }

  // Arithmetic maps:

  // - AddMap, SubMap, MulMap, DivMap

  // - ShiftMap, ShiftWriteMap, ScaleMap, ScaleWriteMap

    checkConcept<DoubleMap, MulMap<DoubleMap,DoubleMap> >();

    checkConcept<DoubleMap, DivMap<DoubleMap,DoubleMap> >();

    ConstMap<int, double> c1(1.0), c2(3.14);

    IdentityMap<int> im;

    ConvertMap<IdentityMap<int>, double> id(im);

    checkConcept<DoubleMap, ShiftMap<DoubleMap> >();

    checkConcept<DoubleWriteMap, ShiftWriteMap<DoubleWriteMap> >();

    checkConcept<DoubleMap, ScaleMap<DoubleMap> >();

    checkConcept<DoubleWriteMap, ScaleWriteMap<DoubleWriteMap> >();

    checkConcept<DoubleMap, NegMap<DoubleMap> >();

    checkConcept<DoubleWriteMap, NegWriteMap<DoubleWriteMap> >();

    checkConcept<DoubleMap, AbsMap<DoubleMap> >();

    check(shiftMap(id, 2.0)[1] == 3.0 && shiftMap(id, 2.0)[10] == 12.0,

          "Something is wrong with ShiftMap");

          "Something is wrong with ShiftWriteMap");

    check(scaleMap(id, 2.0)[1] == 2.0 && scaleMap(id, 2.0)[10] == 20.0,

          "Something is wrong with ScaleMap");

          "Something is wrong with ScaleWriteMap");

    check(negMap(id)[1] == -1.0 && negMap(id)[-10] == 10.0,

          "Something is wrong with NegMap");

    check(negWriteMap(id)[1] == -1.0 && negWriteMap(id)[-10] == 10.0,

          "Something is wrong with NegWriteMap");

    check(absMap(id)[1] == 1.0 && absMap(id)[-10] == 10.0,

    checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();

    TrueMap<int> tm;

    FalseMap<int> fm;

    RangeMap<bool> rm(2);

    rm[0] = true; rm[1] = false;

          "Something is wrong with AndMap");

          "Something is wrong with OrMap");

    ConstMap<int, double> cm(2.0);

    IdentityMap<int> im;

    ConvertMap<IdentityMap<int>, double> id(im);

    check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],

          "Something is wrong with LessMap");

  // LoggerBoolMap

  {

    typedef std::vector<int> vec;

    vec v1;

    vec v2(10);

    LoggerBoolMap<vec::iterator> map2(v2.begin());

    map1.set(10, false);

    map1.set(20, true);   map2.set(20, true);

    map1.set(30, false);  map2.set(40, false);

    map1.set(50, true);   map2.set(50, true);

    map1.set(60, true);   map2.set(60, true);

    check(v1.size() == 3 && v2.size() == 10 &&

          "Something is wrong with LoggerBoolMap");

    int i = 0;

    for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();

          it != map2.end(); ++it )

      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");