RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 */

namespace lemon {

/*!

\page migration Migration from the 0.x Series

This guide gives an in depth description on what has changed compared

to the 0.x release series.

Many of these changes adjusted automatically by the

<tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual

update are typeset <b>boldface</b>.

\section migration-graph Graph Related Name Changes

- \ref concepts::Digraph "Directed graphs" are called \c Digraph and

  they have <tt>Arc</tt>s (instead of <tt>Edge</tt>s), while

  \ref concepts::Graph "undirected graphs" are called \c Graph

  (instead of \c UGraph) and they have <tt>Edge</tt>s (instead of

  <tt>UEdge</tt>s). These changes reflected thoroughly everywhere in

  the library. Namely,

  - \c Graph -> \c Digraph

    - \c %ListGraph -> \c ListDigraph, \c %SmartGraph -> \c SmartDigraph etc.

  - \c UGraph -> \c Graph

    - \c ListUGraph -> \c ListGraph, \c SmartUGraph -> \c SmartGraph etc.

  - \c Edge -> \c Arc, \c UEdge -> \c Edge

  - \c EdgeMap -> \c ArcMap, \c UEdgeMap -> \c EdgeMap

  - \c EdgeIt -> \c ArcIt, \c UEdgeIt -> \c EdgeIt

  - Class names and function names containing the words \c graph,

    \c ugraph, \e edge or \e arc should also be updated.

- <b>The two endpoints of an (\e undirected) \c Edge can be obtained by the

  <tt>u()</tt> and <tt>v()</tt> member function of the graph

  (instead of <tt>source()</tt> and <tt>target()</tt>). This change

  must be done by hand.</b>

  \n Of course, you can still use <tt>source()</tt> and <tt>target()</tt>

  for <tt>Arc</tt>s (directed edges).

\warning

<b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of

the words \c graph, \c digraph, \c edge and \c arc, so it replaces them

in strings, comments etc. as well as in all identifiers.</b>

\section migration-lgf LGF tools

 - The \ref lgf-format "LGF file format" has changed,

   <tt>\@nodeset</tt> has changed to <tt>\@nodes</tt>,

   <tt>\@edgeset</tt> and <tt>\@uedgeset</tt> to <tt>\@arcs</tt> or

   <tt>\@edges</tt>, which become completely equivalents. The

   <tt>\@nodes</tt>, <tt>\@edges</tt> and <tt>\@uedges</tt> sections are

   removed from the format, the content of them should be

   the part of <tt>\@attributes</tt> section. The data fields in

   the sections must follow a strict format, they must be either character

   sequences without whitespaces or quoted strings.

 - The <tt>LemonReader</tt> and <tt>LemonWriter</tt> core interfaces

   are no longer available.

 - The implementation of the general section readers and writers has changed

   they are simple functors now. Beside the old

   stream based section handling, currently line oriented section

   reading and writing are also supported. In the

   section readers the lines must be counted manually. The sections

   should be read and written with the SectionWriter and SectionReader

   classes.

 - Instead of the item readers and writers, item converters should be

   used. The converters are functors, which map the type to

   std::string or std::string to the type. The converters for standard

   containers hasn't yet been implemented in the new LEMON. The converters

   can return strings in any format, because if it is necessary, the LGF

   writer and reader will quote and unquote the given value.

 - The DigraphReader and DigraphWriter can used similarly to the

   0.x series, however the <tt>read</tt> or <tt>write</tt> prefix of

   the member functions are removed.

 - The new LEMON supports the function like interface, the \c

   digraphReader and \c digraphWriter functions are more convenient than

   using the classes directly.

\section migration-search BFS, DFS and Dijkstra

- <b>Using the function interface of BFS, DFS and %Dijkstra both source and

  target nodes can be given as parameters of the <tt>run()</tt> function

  (instead of \c bfs(), \c dfs() or \c dijkstra() itself).</b>

- \ref named-templ-param "Named class template parameters" of \c Bfs,

  \c Dfs, \c Dijkstra, \c BfsVisit, \c DfsVisit are renamed to start

  with "Set" instead of "Def". Namely,

  - \c DefPredMap -> \c SetPredMap

  - \c DefDistMap -> \c SetDistMap

  - \c DefReachedMap -> \c SetReachedMap

  - \c DefProcessedMap -> \c SetProcessedMap

  - \c DefHeap -> \c SetHeap

  - \c DefStandardHeap -> \c SetStandardHeap

  - \c DefOperationTraits -> \c SetOperationTraits

  - \c DefProcessedMapToBeDefaultMap -> \c SetStandardProcessedMap

\section migration-error Exceptions and Debug tools

<b>The class hierarchy of exceptions has largely been simplified. Now,

only the i/o related tools may throw exceptions. All other exceptions

have been replaced with either the \c LEMON_ASSERT or the \c LEMON_DEBUG

macros.</b>

<b>On the other hand, the parameter order of constructors of the

exceptions has been changed. See \ref IoError and \ref FormatError for

more details.</b>

\section migration-other Others

- <b>The contents of <tt>graph_utils.h</tt> are moved to <tt>core.h</tt>

  and <tt>maps.h</tt>. <tt>core.h</tt> is included by all graph types,

  therefore it usually do not have to be included directly.</b>

- <b><tt>path_utils.h</tt> is merged to \c path.h.</b>

- <b>The semantic of the assignment operations and copy constructors of maps

  are still under discussion. So, you must copy them by hand (i.e. copy

  each entry one-by-one)</b>

- <b>The parameters of the graph copying tools (i.e. \c GraphCopy,

  \c DigraphCopy) have to be given in the from-to order.</b>

- \c copyDigraph() and \c copyGraph() are renamed to \c digraphCopy()

  and \c graphCopy(), respectively.

- <b>The interface of \ref DynArcLookUp has changed. It is now the same as

  of \ref ArcLookUp and \ref AllArcLookUp</b>

- Some map types should also been renamed. Namely,

  - \c IntegerMap -> \c RangeMap

  - \c StdMap -> \c SparseMap

  - \c FunctorMap -> \c FunctorToMap

  - \c MapFunctor -> \c MapToFunctor

  - \c ForkWriteMap -> \c ForkMap

  - \c StoreBoolMap -> \c LoggerBoolMap

- \c dim2::BoundingBox -> \c dim2::Box

*/

}

#!/bin/bash

set -e

if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then

	echo "Usage:"

	echo "  $0 source-file"

	exit

fi

TMP=`mktemp`

sed	-e "s/undirected graph/_gr_aph_label_/g"\

	-e "s/undirected edge/_ed_ge_label_/g"\

	-e "s/graph_/_gr_aph_label__/g"\

	-e "s/_graph/__gr_aph_label_/g"\

	-e "s/UGraph/_Gr_aph_label_/g"\

	-e "s/uGraph/_gr_aph_label_/g"\

	-e "s/ugraph/_gr_aph_label_/g"\

	-e "s/Graph/_Digr_aph_label_/g"\

	-e "s/graph/_digr_aph_label_/g"\

	-e "s/UEdge/_Ed_ge_label_/g"\

	-e "s/uEdge/_ed_ge_label_/g"\

	-e "s/uedge/_ed_ge_label_/g"\

	-e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\

	-e "s/Edge/_Ar_c_label_/g"\

	-e "s/edge/_ar_c_label_/g"\

	-e "s/ANode/_Re_d_label_/g"\

	-e "s/BNode/_Blu_e_label_/g"\

	-e "s/A-Node/_Re_d_label_/g"\

	-e "s/B-Node/_Blu_e_label_/g"\

	-e "s/anode/_re_d_label_/g"\

	-e "s/bnode/_blu_e_label_/g"\

	-e "s/aNode/_re_d_label_/g"\

	-e "s/bNode/_blu_e_label_/g"\

	-e "s/_Digr_aph_label_/Digraph/g"\

	-e "s/_digr_aph_label_/digraph/g"\

	-e "s/_Gr_aph_label_/Graph/g"\

	-e "s/_gr_aph_label_/graph/g"\

	-e "s/_Ar_c_label_/Arc/g"\

	-e "s/_ar_c_label_/arc/g"\

	-e "s/_Ed_ge_label_/Edge/g"\

	-e "s/_ed_ge_label_/edge/g"\

	-e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\

	-e "s/_Re_d_label_/Red/g"\

	-e "s/_Blu_e_label_/Blue/g"\

	-e "s/_re_d_label_/red/g"\

	-e "s/_blu_e_label_/blue/g"\

	-e "s/\(\W\)DefPredMap\(\W\)/\1SetPredMap\2/g"\

	-e "s/\(\W\)DefPredMap$/\1SetPredMap/g"\

	-e "s/^DefPredMap\(\W\)/SetPredMap\1/g"\

	-e "s/^DefPredMap$/SetPredMap/g"\

	-e "s/\(\W\)DefDistMap\(\W\)/\1SetDistMap\2/g"\

	-e "s/\(\W\)DefDistMap$/\1SetDistMap/g"\

	-e "s/^DefDistMap\(\W\)/SetDistMap\1/g"\

	-e "s/^DefDistMap$/SetDistMap/g"\

	-e "s/\(\W\)DefReachedMap\(\W\)/\1SetReachedMap\2/g"\

	-e "s/\(\W\)DefReachedMap$/\1SetReachedMap/g"\

	-e "s/^DefReachedMap\(\W\)/SetReachedMap\1/g"\

	-e "s/^DefReachedMap$/SetReachedMap/g"\

	-e "s/\(\W\)DefProcessedMap\(\W\)/\1SetProcessedMap\2/g"\

	-e "s/\(\W\)DefProcessedMap$/\1SetProcessedMap/g"\

	-e "s/^DefProcessedMap\(\W\)/SetProcessedMap\1/g"\

	-e "s/^DefProcessedMap$/SetProcessedMap/g"\

	-e "s/\(\W\)DefHeap\(\W\)/\1SetHeap\2/g"\

	-e "s/\(\W\)DefHeap$/\1SetHeap/g"\

	-e "s/^DefHeap\(\W\)/SetHeap\1/g"\

	-e "s/^DefHeap$/SetHeap/g"\

	-e "s/\(\W\)DefStandardHeap\(\W\)/\1SetStandradHeap\2/g"\

	-e "s/\(\W\)DefStandardHeap$/\1SetStandradHeap/g"\

	-e "s/^DefStandardHeap\(\W\)/SetStandradHeap\1/g"\

	-e "s/^DefStandardHeap$/SetStandradHeap/g"\

	-e "s/\(\W\)DefOperationTraits\(\W\)/\1SetOperationTraits\2/g"\

	-e "s/\(\W\)DefOperationTraits$/\1SetOperationTraits/g"\

	-e "s/^DefOperationTraits\(\W\)/SetOperationTraits\1/g"\

	-e "s/^DefOperationTraits$/SetOperationTraits/g"\

	-e "s/\(\W\)DefProcessedMapToBeDefaultMap\(\W\)/\1SetStandardProcessedMap\2/g"\

	-e "s/\(\W\)DefProcessedMapToBeDefaultMap$/\1SetStandardProcessedMap/g"\

	-e "s/^DefProcessedMapToBeDefaultMap\(\W\)/SetStandardProcessedMap\1/g"\

	-e "s/^DefProcessedMapToBeDefaultMap$/SetStandardProcessedMap/g"\

	-e "s/\(\W\)IntegerMap\(\W\)/\1RangeMap\2/g"\

	-e "s/\(\W\)IntegerMap$/\1RangeMap/g"\

	-e "s/^IntegerMap\(\W\)/RangeMap\1/g"\

	-e "s/^IntegerMap$/RangeMap/g"\

	-e "s/\(\W\)integerMap\(\W\)/\1rangeMap\2/g"\

	-e "s/\(\W\)integerMap$/\1rangeMap/g"\

	-e "s/^integerMap\(\W\)/rangeMap\1/g"\

	-e "s/^integerMap$/rangeMap/g"\

	-e "s/\(\W\)copyGraph\(\W\)/\1graphCopy\2/g"\

	-e "s/\(\W\)copyGraph$/\1graphCopy/g"\

	-e "s/^copyGraph\(\W\)/graphCopy\1/g"\

	-e "s/^copyGraph$/graphCopy/g"\

	-e "s/\(\W\)copyDigraph\(\W\)/\1digraphCopy\2/g"\

	-e "s/\(\W\)copyDigraph$/\1digraphCopy/g"\

	-e "s/^copyDigraph\(\W\)/digraphCopy\1/g"\

	-e "s/^copyDigraph$/digraphCopy/g"\

	-e "s/\(\W\)\([sS]\)tdMap\(\W\)/\1\2parseMap\3/g"\

	-e "s/\(\W\)\([sS]\)tdMap$/\1\2parseMap/g"\

	-e "s/^\([sS]\)tdMap\(\W\)/\1parseMap\2/g"\

	-e "s/^\([sS]\)tdMap$/\1parseMap/g"\

	-e "s/\(\W\)\([Ff]\)unctorMap\(\W\)/\1\2unctorToMap\3/g"\

	-e "s/\(\W\)\([Ff]\)unctorMap$/\1\2unctorToMap/g"\

	-e "s/^\([Ff]\)unctorMap\(\W\)/\1unctorToMap\2/g"\

	-e "s/^\([Ff]\)unctorMap$/\1unctorToMap/g"\

	-e "s/\(\W\)\([Mm]\)apFunctor\(\W\)/\1\2apToFunctor\3/g"\

	-e "s/\(\W\)\([Mm]\)apFunctor$/\1\2apToFunctor/g"\

	-e "s/^\([Mm]\)apFunctor\(\W\)/\1apToFunctor\2/g"\

	-e "s/^\([Mm]\)apFunctor$/\1apToFunctor/g"\

	-e "s/\(\W\)\([Ff]\)orkWriteMap\(\W\)/\1\2orkMap\3/g"\

	-e "s/\(\W\)\([Ff]\)orkWriteMap$/\1\2orkMap/g"\

	-e "s/^\([Ff]\)orkWriteMap\(\W\)/\1orkMap\2/g"\

	-e "s/^\([Ff]\)orkWriteMap$/\1orkMap/g"\

	-e "s/\(\W\)StoreBoolMap\(\W\)/\1LoggerBoolMap\2/g"\

	-e "s/\(\W\)StoreBoolMap$/\1LoggerBoolMap/g"\

	-e "s/^StoreBoolMap\(\W\)/LoggerBoolMap\1/g"\

	-e "s/^StoreBoolMap$/LoggerBoolMap/g"\

	-e "s/\(\W\)storeBoolMap\(\W\)/\1loggerBoolMap\2/g"\

	-e "s/\(\W\)storeBoolMap$/\1loggerBoolMap/g"\

	-e "s/^storeBoolMap\(\W\)/loggerBoolMap\1/g"\

	-e "s/^storeBoolMap$/loggerBoolMap/g"\

	-e "s/\(\W\)BoundingBox\(\W\)/\1Box\2/g"\

	-e "s/\(\W\)BoundingBox$/\1Box/g"\

	-e "s/^BoundingBox\(\W\)/Box\1/g"\

	-e "s/^BoundingBox$/Box/g"\

<$1 > $TMP

mv $TMP $1

dist_bin_SCRIPTS =

int main(int argc, char **argv)

/// using appropriate graph maps.

	doc/migration.dox \

with any graph structure.

<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".

LEMON provides several special purpose maps and map adaptors that e.g. combine

<b>See also:</b> \ref map_concepts "Map Concepts".

usage of map adaptors with the \c graphToEps() function.

  graphToEps(graph, "graph.eps")

\c nodeColor() function. The \c composeMap() compose the \c degree_map

Breadth-First Search (BFS) and Depth-First Search (DFS).

@defgroup shortest_path Shortest Path Algorithms

@defgroup max_flow Maximum Flow Algorithms

@defgroup min_cost_flow Minimum Cost Flow Algorithms

@defgroup min_cut Minimum Cut Algorithms

@defgroup graph_prop Connectivity and Other Graph Properties

@defgroup planar Planarity Embedding and Drawing

@defgroup matching Matching Algorithms

@defgroup spantree Minimum Spanning Tree Algorithms

@defgroup auxalg Auxiliary Algorithms

@defgroup approx Approximation Algorithms

@ingroup algs

@defgroup lp_group Lp and Mip Solvers

@defgroup lp_utils Tools for Lp and Mip Solvers

@defgroup timecount Time Measuring and Counting

and graph related data. Now it supports the \ref lgf-format

"LEMON Graph Format", the \c DIMACS format and the encapsulated

postscript (EPS) format.

\brief Reading and writing LEMON Graph Format.

@defgroup eps_io Postscript Exporting

/**

@defgroup map_concepts Map Concepts

@ingroup concept

\brief Skeleton and concept checking classes for maps

This group describes the skeletons and concept checking classes of maps.

The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can

some \ref demoprograms "demo programs".

If you are a user of the old (0.x) series of LEMON, please check out the

\ref migration "Migration Guide" for the backward incompatibilities.

  ArgParser::ArgParser(int argc, const char * const *argv)

    :_argc(argc), _argv(argv), _command_name(argv[0]) {

    const char * const *_argv;

    ArgParser(int argc, const char * const *argv);

    ///Instantiates a PredMap.

    ///This function instantiates a PredMap.

    ///PredMap.

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

    ///we would like to define the ProcessedMap

    ///Instantiates a ReachedMap.

    ///This function instantiates a ReachedMap.

    ///we would like to define the ReachedMap.

    ///Instantiates a DistMap.

    ///This function instantiates a DistMap.

    ///DistMap.

    ///PredMap type.

    ///PredMap type.

    ///DistMap type.

    ///DistMap type.

    ///ReachedMap type.

    ///ReachedMap type.

    ///ProcessedMap type.

    ///ProcessedMap type.

    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.

    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.

    ///Instantiates a PredMap.

    ///This function instantiates a PredMap.

    ///PredMap.

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

    ///we would like to define the ProcessedMap.

    ///Instantiates a ReachedMap.

    ///This function instantiates a ReachedMap.

    ///we would like to define the ReachedMap.

    ///Instantiates a DistMap.

    ///This function instantiates a DistMap.

    ///the DistMap

  /// Default traits class used by BfsWizard

    ///for setting PredMap object.

    ///for setting PredMap object.

    ///for setting ReachedMap object.

    ///for setting ReachedMap object.

    ///for setting DistMap object.

    ///for setting DistMap object.

    ///for setting ProcessedMap object.

    ///for setting ProcessedMap object.

    /// \brief Instantiates a ReachedMap.

    /// This function instantiates a ReachedMap.

    /// we would like to define the ReachedMap.

//\ingroup graphbits

//\file

//\brief Observer notifier for graph alteration observers.

  // \ingroup graphbits

  //

  // \brief Notifier class to notify observes about alterations in

  // a container.

  //

  // The simple graph's can be refered as two containers, one node container

  // and one edge container. But they are not standard containers they

  // does not store values directly they are just key continars for more

  // value containers which are the node and edge maps.

  //

  // The graph's node and edge sets can be changed as we add or erase

  // nodes and edges in the graph. LEMON would like to handle easily

  // that the node and edge maps should contain values for all nodes or

  // edges. If we want to check on every indicing if the map contains

  // the current indicing key that cause a drawback in the performance

  // in the library. We use another solution we notify all maps about

  // an alteration in the graph, which cause only drawback on the

  // alteration of the graph.

  //

  // This class provides an interface to the container. The \e first() and \e

  // next() member functions make possible to iterate on the keys of the

  // container. The \e id() function returns an integer id for each key.

  // The \e maxId() function gives back an upper bound of the ids.

  //

  // For the proper functonality of this class, we should notify it

  // about each alteration in the container. The alterations have four type

  // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and

  // \e erase() signals that only one or few items added or erased to or

  // from the graph. If all items are erased from the graph or from an empty

  // graph a new graph is builded then it can be signaled with the

  // clear() and build() members. Important rule that if we erase items

  // from graph we should first signal the alteration and after that erase

  // them from the container, on the other way on item addition we should

  // first extend the container and just after that signal the alteration.

  //

  // The alteration can be observed with a class inherited from the

  // \e ObserverBase nested class. The signals can be handled with

  // overriding the virtual functions defined in the base class.  The

  // observer base can be attached to the notifier with the

  // \e attach() member and can be detached with detach() function. The

  // alteration handlers should not call any function which signals

  // an other alteration in the same notifier and should not

  // detach any observer from the notifier.

  //

  // Alteration observers try to be exception safe. If an \e add() or

  // a \e clear() function throws an exception then the remaining

  // observeres will not be notified and the fulfilled additions will

  // be rolled back by calling the \e erase() or \e clear()

  // functions. Thence the \e erase() and \e clear() should not throw

  // exception. Actullay, it can be throw only \ref ImmediateDetach

  // exception which detach the observer from the notifier.

  //

  // There are some place when the alteration observing is not completly

  // reliable. If we want to carry out the node degree in the graph

  // as in the \ref InDegMap and we use the reverseEdge that cause

  // unreliable functionality. Because the alteration observing signals

  // only erasing and adding but not the reversing it will stores bad

  // degrees. The sub graph adaptors cannot signal the alterations because

  // just a setting in the filter map can modify the graph and this cannot

  // be watched in any way.

  //

  // \param _Container The container which is observed.

  // \param _Item The item type which is obserbved.

    // \brief Exception which can be called from \e clear() and

    // \e erase().

    //

    // From the \e clear() and \e erase() function only this

    // exception is allowed to throw. The exception immediatly

    // detaches the current observer from the notifier. Because the

    // \e clear() and \e erase() should not throw other exceptions

    // it can be used to invalidate the observer.

    // \brief ObserverBase is the base class for the observers.

    //

    // ObserverBase is the abstract base class for the observers.

    // It will be notified about an item was inserted into or

    // erased from the graph.

    //

    // The observer interface contains some pure virtual functions

    // to override. The add() and erase() functions are

    // to notify the oberver when one item is added or

    // erased.

    //

    // The build() and clear() members are to notify the observer

    // about the container is built from an empty container or

    // is cleared to an empty container.

      // \brief Default constructor.

      //

      // Default constructor for ObserverBase.

      // \brief Constructor which attach the observer into notifier.

      //

      // Constructor which attach the observer into notifier.

      // \brief Constructor which attach the obserever to the same notifier.

      //

      // Constructor which attach the obserever to the same notifier as

      // the other observer is attached to.

      // \brief Destructor

      // \brief Attaches the observer into an AlterationNotifier.

      //

      // This member attaches the observer into an AlterationNotifier.

      // \brief Detaches the observer into an AlterationNotifier.

      //

      // This member detaches the observer from an AlterationNotifier.

      // \brief Gives back a pointer to the notifier which the map

      // attached into.

      //

      // This function gives back a pointer to the notifier which the map

      // attached into.

      // Gives back true when the observer is attached into a notifier.

      // \brief The member function to notificate the observer about an

      // item is added to the container.

      //

      // The add() member function notificates the observer about an item

      // is added to the container. It have to be overrided in the

      // subclasses.