RhodeCode

with any graph structures.

LEMON provides several special purpose maps that e.g. combine

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

  digraphToEps(graph, "graph.eps")

\e nodeColor() function. The \c composeMap() compose the \e 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

@defgroup lp_group Lp and Mip solvers

@defgroup lp_utils Tools for Lp and Mip solvers

@defgroup timecount Time measuring and Counting

@defgroup graphbits Tools for Graph Implementation

@ingroup utils

\brief Tools to make it easier to create graphs.

This group describes the tools that makes it easier to create graphs and

the maps that dynamically update with the graph changes.

*/

/**

and graph related data. Now it supports the LEMON format, the

\c DIMACS format and the encapsulated postscript (EPS) format.

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

@defgroup eps_io Postscript exporting

/* --- Unused group

@defgroup experimental Experimental Structures and Algorithms

This group describes some Experimental structures and algorithms.

The stuff here is subject to change.

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.

\section migration-lgf LGF tools 

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

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

      /// more item is added to the container.

      ///

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

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

      /// subclasses.

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

      /// item is erased from the container.

      ///

      /// The erase() member function notificates the observer about an

      /// item is erased from the container. It have to be overrided in

      /// the subclasses.

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

      /// more item is erased from the container.

      ///

      /// The erase() member function notificates the observer about more item

      /// is erased from the container. It have to be overrided in the

      /// subclasses.

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

      /// container is built.

      ///

      /// The build() member function notificates the observer about the

      /// container is built from an empty container. It have to be

      /// overrided in the subclasses.

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

      /// items are erased from the container.

      ///

      /// The clear() member function notificates the observer about all

      /// items are erased from the container. It have to be overrided in

      /// the subclasses.

    /// \brief Default constructor.

    ///

    /// The default constructor of the AlterationNotifier.

    /// It creates an empty notifier.

    /// \brief Constructor.

    ///

    /// Constructor with the observed container parameter.

    /// \brief Copy Constructor of the AlterationNotifier.

    ///

    /// Copy constructor of the AlterationNotifier.

    /// It creates only an empty notifier because the copiable

    /// notifier's observers have to be registered still into that notifier.

    /// \brief Destructor.

    ///

    /// Destructor of the AlterationNotifier.

    ///

    /// \brief Sets the container.

    ///

    /// Sets the container.

    /// \brief First item in the container.

    ///

    /// Returns the first item in the container. It is

    /// for start the iteration on the container.

    /// \brief Next item in the container.

    ///

    /// Returns the next item in the container. It is

    /// for iterate on the container.

    /// \brief Returns the id of the item.

    ///

    /// Returns the id of the item provided by the container.

    /// \brief Returns the maximum id of the container.

    ///

    /// Returns the maximum id of the container.

    /// \brief Notifies all the registed observers about an item added to

    /// the container.

    ///

    /// It notifies all the registed observers about an item added to

    /// the container.

    ///

    /// \brief Notifies all the registed observers about more item added to

    /// the container.

    ///

    /// It notifies all the registed observers about more item added to

    /// the container.

    ///

    /// \brief Notifies all the registed observers about an item erased from

    /// the container.

    ///

    /// It notifies all the registed observers about an item erased from

    /// the container.

    ///

    /// \brief Notifies all the registed observers about more item erased

    /// from the container.

    ///

    /// It notifies all the registed observers about more item erased from

    /// the container.

    ///

    /// \brief Notifies all the registed observers about the container is

    /// built.

    ///

    /// Notifies all the registed observers about the container is built

    /// from an empty container.

    /// \brief Notifies all the registed observers about all items are

    /// erased.

    ///

    /// Notifies all the registed observers about all items are erased

    /// from the container.

/// \ingroup graphbits

/// \file

/// \brief Graph map based on the array storage.

  /// \ingroup graphbits

  ///

  /// \brief Graph map based on the array storage.

  ///

  /// The ArrayMap template class is graph map structure what

  /// automatically updates the map when a key is added to or erased from

  /// the map. This map uses the allocators to implement

  /// the container functionality.

  ///

  /// The template parameters are the Graph the current Item type and

  /// the Value type of the map.

    /// The graph type of the maps.

    /// The item type of the map.

    /// The reference map tag.

    /// The key type of the maps.

    /// The value type of the map.

    /// The const reference type of the map.

    /// The reference type of the map.

    /// The notifier type.

    /// The MapBase of the Map which imlements the core regisitry function.

    /// \brief Graph initialized map constructor.

    ///

    /// Graph initialized map constructor.

    /// \brief Constructor to use default value to initialize the map.

    ///

    /// It constructs a map and initialize all of the the map.

    /// \brief Constructor to copy a map of the same map type.

    ///

    /// Constructor to copy a map of the same map type.

    /// \brief Assign operator.

    ///

    /// This operator assigns for each item in the map the

    /// value mapped to the same item in the copied map.

    /// The parameter map should be indiced with the same

    /// itemset because this assign operator does not change

    /// the container of the map.

    /// \brief Template assign operator.

    ///

    /// The given parameter should be conform to the ReadMap

    /// concecpt and could be indiced by the current item set of

    /// the NodeMap. In this case the value for each item

    /// is assigned by the value of the given ReadMap.

    /// \brief The destructor of the map.

    ///

    /// The destructor of the map.

    /// \brief The subscript operator.

    ///

    /// The subscript operator. The map can be subscripted by the

    /// actual keys of the graph.

    /// \brief The const subscript operator.

    ///

    /// The const subscript operator. The map can be subscripted by the

    /// actual keys of the graph.

    /// \brief Setter function of the map.

    ///

    /// Setter function of the map. Equivalent with map[key] = val.

    /// This is a compatibility feature with the not dereferable maps.

    /// \brief Adds a new key to the map.

    ///

    /// It adds a new key to the map. It called by the observer notifier

    /// and it overrides the add() member function of the observer base.

    /// \brief Adds more new keys to the map.

    ///

    /// It adds more new keys to the map. It called by the observer notifier

    /// and it overrides the add() member function of the observer base.

    /// \brief Erase a key from the map.

    ///

    /// Erase a key from the map. It called by the observer notifier

    /// and it overrides the erase() member function of the observer base.

    /// \brief Erase more keys from the map.

    ///

    /// Erase more keys from the map. It called by the observer notifier

    /// and it overrides the erase() member function of the observer base.

    /// \brief Buildes the map.

    ///

    /// It buildes the map. It called by the observer notifier

    /// and it overrides the build() member function of the observer base.

    /// \brief Clear the map.

    ///

    /// It erase all items from the map. It called by the observer notifier

    /// and it overrides the clear() member function of the observer base.

///\ingroup digraphbits

///\file

///\brief Extenders for the digraph types

  /// \ingroup digraphbits

  ///

  /// \brief BaseDigraph to BaseGraph extender

    /// First node of the edge

    /// Source of the given arc

    /// Second node of the edge

    /// Target of the given arc

    /// \brief Directed arc from an edge.

    ///

    /// Returns a directed arc corresponding to the specified edge.

    /// If the given bool is true, the first node of the given edge and

    /// the source node of the returned arc are the same.

    /// Returns whether the given directed arc has the same orientation

    /// as the corresponding edge.

///\ingroup misc

///\file

///\brief Classes to compute with Bezier curves.

///

///Up to now this file is used internally by \ref graph_to_eps.h

///\ingroup graphbits

///\file

///\brief Graph maps that construct and destruct their elements dynamically.

  /// DefaultMap class