COIN-OR::LEMON - Graph Library

Changeset 2084:59769591eb60 in lemon-0.x for lemon


Ignore:
Timestamp:
05/15/06 11:49:51 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2749
Message:

Documentation improvements

Rearrangements:

IO modules
Algorithms

New documentation:

SwapBpUGraphAdaptor

Demos:

strongly_connected_orientation.cc

Benchmarks:

swap_bipartite_bench.cc

Location:
lemon
Files:
12 edited

Legend:

Unmodified
Added
Removed
  • lemon/bpugraph_adaptor.h

    r2040 r2084  
    410410  ///
    411411  /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
    412   /// a-nodeset will be the original graph's b-nodeset and the adaptor's
    413   /// b-nodeset will be the original graph's a-nodeset.
     412  /// anode-set will be the original graph's bnode-set and the adaptor's
     413  /// bnode-set will be the original graph's anode-set.
     414  ///
     415  /// As example look at an algorithm what can be sped up with the
     416  /// swap bipartite undirected graph adaptor. If we want to find the
     417  /// maximum matching in the bipartite graph then it will be not changed
     418  /// if we swap the two nodesets. But the algorithm use the two nodeset
     419  /// different way. If we swap the nodesets it provides different
     420  /// running time. We run a test on random bipartite graphs with
     421  /// different rate of the anode-set size and bnode-set size.
     422  /// We always made graphs with 10000 nodes and 20000 edges and we
     423  /// computed the maximum cardinality matching with the Hopcroft-Karp
     424  /// algorithm.
     425  ///
     426  /// The next diagram shows the running time of the tests. If the anode-set
     427  /// is smaller than the bnode-set the running time is better than with
     428  /// the swapped graph. Other conclusion is that the running time
     429  /// is greater when the two nodesets size are nearly equal.
     430  ///
     431  /// \image html swap_test.png
     432  /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth
     433  ///
     434  /// The next part shows how can we swap the two nodeset:
     435  ///
     436  ///\code
     437  /// typedef SwapBpUGraphAdaptor<BpUGraph> SBpUGraph;
     438  /// SBpUGraph sbpugraph(bpugraph);
     439  /// MaxBipartiteMatching<SBpUGraph> sbpumatch(sbpugraph);
     440  ///\endcode
    414441  template <typename _BpUGraph>
    415442  class SwapBpUGraphAdaptor
     
    426453  public:
    427454
     455    /// \brief Construct a swapped graph.
     456    ///
     457    /// Construct a swapped graph.
    428458    explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
    429459
  • lemon/eps.h

    r2008 r2084  
    2727#include<lemon/xy.h>
    2828
    29   ///\ingroup io_group
     29  ///\ingroup eps_io
    3030  ///\file
    3131  ///\brief Simple tool to create \c .eps files
     
    3535namespace lemon {
    3636 
    37   ///\ingroup io_group
     37  ///\ingroup eps_io
    3838  ///\brief A simple tool to create \c .eps files
    3939  ///
  • lemon/graph_adaptor.h

    r2081 r2084  
    265265  /// implements the graph obtained from \c g by
    266266  /// reversing the orientation of its edges.
     267  ///
     268  /// A good example of using RevGraphAdaptor is to decide that the
     269  /// directed graph is wheter strongly connected or not. If from one
     270  /// node each node is reachable and from each node is reachable this
     271  /// node then and just then the graph is strongly connected. Instead of
     272  /// this condition we use a little bit different. From one node each node
     273  /// ahould be reachable in the graph and in the reversed graph. Now this
     274  /// condition can be checked with the Dfs algorithm class and the
     275  /// RevGraphAdaptor algorithm class.
     276  ///
     277  /// And look at the code:
     278  ///
     279  ///\code
     280  /// bool stronglyConnected(const Graph& graph) {
     281  ///   if (NodeIt(graph) == INVALID) return true;
     282  ///   Dfs<Graph> dfs(graph);
     283  ///   dfs.run(NodeIt(graph));
     284  ///   for (NodeIt it(graph); it != INVALID; ++it) {
     285  ///     if (!dfs.reached(it)) {
     286  ///       return false;
     287  ///     }
     288  ///   }
     289  ///   typedef RevGraphAdaptor<const Graph> RGraph;
     290  ///   RGraph rgraph(graph);
     291  ///   DfsVisit<RGraph> rdfs(rgraph);
     292  ///   rdfs.run(NodeIt(graph));
     293  ///   for (NodeIt it(graph); it != INVALID; ++it) {
     294  ///     if (!rdfs.reached(it)) {
     295  ///       return false;
     296  ///     }
     297  ///   }
     298  ///   return true;
     299  /// }
     300  ///\endcode
    267301  template<typename _Graph>
    268302  class RevGraphAdaptor :
     
    23882422  ///
    23892423  /// The second solution contains just 3 disjoint paths while the first 4.
    2390   /// The full code can be found in the \ref disjoint_paths.cc demo file.
     2424  /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
    23912425  ///
    23922426  /// This graph adaptor is fully conform to the
     
    25882622  };
    25892623
     2624  /// \brief Just gives back a split graph adaptor
     2625  ///
     2626  /// Just gives back a split graph adaptor
     2627  template<typename Graph>
     2628  SplitGraphAdaptor<Graph>
     2629  splitGraphAdaptor(const Graph& graph) {
     2630    return SplitGraphAdaptor<Graph>(graph);
     2631  }
     2632
    25902633
    25912634} //namespace lemon
  • lemon/graph_reader.h

    r2037 r2084  
    1717 */
    1818
    19 ///\ingroup io_group
     19///\ingroup lemon_io
    2020///\file
    2121///\brief Lemon Graph Format reader.
     
    3131namespace lemon {
    3232
    33   /// \addtogroup io_group
     33  /// \addtogroup lemon_io
    3434  /// @{
    3535
  • lemon/graph_to_eps.h

    r2028 r2084  
    4242
    4343
    44 ///\ingroup io_group
     44///\ingroup eps_io
    4545///\file
    4646///\brief Simple graph drawer
     
    10431043///Generates an EPS file from a graph
    10441044
    1045 ///\ingroup io_group
     1045///\ingroup eps_io
    10461046///Generates an EPS file from a graph.
    10471047///\param g is a reference to the graph to be printed
     
    10721072///Generates an EPS file from a graph
    10731073
    1074 ///\ingroup io_group
     1074///\ingroup eps_io
    10751075///This function does the same as
    10761076///\ref graphToEps(G &g,std::ostream& os)
     
    10881088///Generates an EPS file from a graph
    10891089
    1090 ///\ingroup io_group
     1090///\ingroup eps_io
    10911091///This function does the same as
    10921092///\ref graphToEps(G &g,std::ostream& os)
  • lemon/kruskal.h

    r1993 r2084  
    2525#include <lemon/bits/utility.h>
    2626#include <lemon/bits/traits.h>
    27 
    28 /**
    29 @defgroup spantree Minimum Cost Spanning Tree Algorithms
    30 @ingroup galgs
    31 \brief This group containes the algorithms for finding a minimum cost spanning
    32 tree in a graph
    33 
    34 This group containes the algorithms for finding a minimum cost spanning
    35 tree in a graph
    36 */
    3727
    3828///\ingroup spantree
  • lemon/lemon_reader.h

    r2016 r2084  
    1717 */
    1818
    19 ///\ingroup io_group
     19///\ingroup lemon_io
    2020///\file
    2121///\brief Lemon Format reader.
     
    457457  }
    458458
    459   /// \ingroup io_group
     459  /// \ingroup lemon_io
    460460  /// \brief Lemon Format reader class.
    461461  ///
     
    524524      char_type* eptr() { return _eptr; }
    525525
    526       int blen() { return _eptr - _base; }
    527 
    528       void setb(char_type* buf, int len) {
     526      int_type blen() { return _eptr - _base; }
     527
     528      void setb(char_type* buf, int_type len) {
    529529        _base = buf;
    530530        _eptr = buf + len;
     
    582582      }
    583583
    584       virtual int underflow() {
     584      virtual int_type underflow() {
    585585        char c;
    586586        if (_is.read(&c, 1)) {
     
    613613      }
    614614
    615       virtual int sync() {
     615      virtual int_type sync() {
    616616        return EOF;
    617617      }
  • lemon/lemon_writer.h

    r2016 r2084  
    1717 */
    1818
    19 ///\ingroup io_group
     19///\ingroup lemon_io
    2020///\file
    2121///\brief Lemon Format writer.
     
    258258  }
    259259
    260   /// \ingroup io_group
     260  /// \ingroup lemon_io
    261261  /// \brief Lemon Format writer class.
    262262  ///
     
    311311      virtual std::string header() = 0;
    312312
    313       /// \brief  Writer function of the section.
     313      /// \brief Writer function of the section.
    314314      ///
    315315      /// Write the content of the section.
    316316      virtual void write(std::ostream& os) = 0;
     317     
     318      /// \brief Gives back true when the section should be written.
     319      ///
     320      /// Gives back true when the section should be written.
     321      virtual bool valid() { return true; }
    317322    };
    318323
     
    356361      SectionWriters::iterator it;
    357362      for (it = writers.begin(); it != writers.end(); ++it) {
    358         *os << (*it)->header() << std::endl;
    359         (*it)->write(*os);
     363        if ((*it)->valid()) {
     364          *os << (*it)->header() << std::endl;
     365          (*it)->write(*os);
     366        }
    360367      }
    361368      *os << "@end" << std::endl;
     
    465472    virtual void write(std::ostream& os) {
    466473      for (int i = 0; i < (int)writers.size(); ++i) {
    467         if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) {
     474        if (writers[i].first == "label") {
    468475          labelMap = writers[i].second;
    469476          forceLabelMap = false;
     
    637644      }
    638645      for (int i = 0; i < (int)writers.size(); ++i) {
    639         if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) {
     646        if (writers[i].first == "label") {
    640647          labelMap = writers[i].second;
    641648          forceLabelMap = false;
     
    10091016      }
    10101017    }
     1018
     1019    /// \brief Gives back true when the section should be written.
     1020    ///
     1021    /// Gives back true when the section should be written.
     1022    virtual bool valid() { return !writers.empty(); }
    10111023   
    10121024  private:
     
    10881100      }
    10891101    }
     1102
     1103    /// \brief Gives back true when the section should be written.
     1104    ///
     1105    /// Gives back true when the section should be written.
     1106    virtual bool valid() { return !writers.empty(); }
    10901107   
    10911108  private:
     
    11901207      }
    11911208    }
     1209
     1210    /// \brief Gives back true when the section should be written.
     1211    ///
     1212    /// Gives back true when the section should be written.
     1213    virtual bool valid() {
     1214      return !uEdgeWriters.empty() || !edgeWriters.empty();
     1215    }
    11921216   
    11931217  private:
     
    12891313    }   
    12901314
     1315    /// \brief Gives back true when the section should be written.
     1316    ///
     1317    /// Gives back true when the section should be written.
     1318    virtual bool valid() { return !writers.empty(); }
     1319
    12911320  private:
    12921321    std::string name;
  • lemon/matrix_maps.h

    r2072 r2084  
    4848
    4949
     50    /// \brief Constructor of the row map
     51    ///
     52    /// Constructor of the row map.
    5053    MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row)
    5154      : matrix(_matrix), row(_row) {}
     
    9295
    9396
     97    /// \brief Constructor of the row map
     98    ///
     99    /// Constructor of the row map.
    94100    ConstMatrixRowMap(const MatrixMap& _matrix,
    95101                      typename MatrixMap::FirstKey _row)
     
    109115  };
    110116
     117  /// \ingroup matrices
     118  ///
    111119  /// \brief Gives back a row view of the matrix map
    112120  ///
    113   /// \ingroup matrices
    114121  /// Gives back a row view of the matrix map.
    115122  ///
     123  /// \sa MatrixRowMap
     124  /// \sa ConstMatrixRowMap
    116125  template <typename MatrixMap>
    117126  MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,
     
    138147    typedef typename MatrixMap::Value Value;
    139148
     149    /// \brief Constructor of the column map
     150    ///
     151    /// Constructor of the column map.
    140152    MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col)
    141153      : matrix(_matrix), col(_col) {}
     
    181193    typedef typename MatrixMap::Value Value;
    182194
     195    /// \brief Constructor of the column map
     196    ///
     197    /// Constructor of the column map.
    183198    ConstMatrixColMap(const MatrixMap& _matrix,
    184199                      typename MatrixMap::SecondKey _col)
     
    198213  };
    199214
     215  /// \ingroup matrices
     216  ///
    200217  /// \brief Gives back a column view of the matrix map
    201218  ///
    202   /// \ingroup matrices
    203219  /// Gives back a column view of the matrix map.
    204220  ///
     221  /// \sa MatrixColMap
     222  /// \sa ConstMatrixColMap
    205223  template <typename MatrixMap>
    206224  MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
  • lemon/path.h

    r2045 r2084  
    1717 */
    1818
    19 /**
    20 @defgroup paths Path Structures
    21 @ingroup datas
    22 \brief Path structures implemented in LEMON.
    23 
    24 LEMON provides flexible data structures
    25 to work with paths.
    26 
    27 All of them have the same interface, especially they can be built or extended
    28 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
    29 algorithm to store its result in any kind of path structure.
    30 
    31 \sa lemon::concept::Path
    32 
    33 */
    3419
    3520///\ingroup paths
  • lemon/radix_sort.h

    r2042 r2084  
    2020#define RADIX_SORT_H
    2121
    22 /// \ingroup auxdat
     22/// \ingroup auxalg
    2323/// \file
    2424/// \brief Radix sort
     
    195195  }
    196196
    197   /// \ingroup auxdat
     197  /// \ingroup auxalg
    198198  ///
    199199  /// \brief Sorts the stl compatible range into ascending order.
     
    412412  }
    413413
    414   /// \ingroup auxdat
     414  /// \ingroup auxalg
    415415  ///
    416416  /// \brief Sorts stable the stl compatible range into ascending order.
  • lemon/ugraph_adaptor.h

    r2069 r2084  
    3939namespace lemon {
    4040
    41   /// \ingroup graph_adaptors
    42   ///
    4341  /// \brief Base type for the Graph Adaptors
    4442  ///
     
    234232
    235233  /// \ingroup graph_adaptors
     234  ///
     235  /// \brief Trivial undirected graph adaptor
     236  ///
     237  /// This class is an adaptor which does not change the adapted undirected
     238  /// graph. It can be used only to test the undirected graph adaptors.
    236239  template <typename _UGraph>
    237240  class UGraphAdaptor
     
    349352    }
    350353
    351     ///\e
    352 
     354    /// \brief Hide the given node in the graph.
     355    ///
    353356    /// This function hides \c n in the graph, i.e. the iteration
    354357    /// jumps over it. This is done by simply setting the value of \c n 
     
    356359    void hide(const Node& n) const { node_filter_map->set(n, false); }
    357360
    358     ///\e
    359 
     361    /// \brief Hide the given undirected edge in the graph.
     362    ///
    360363    /// This function hides \c e in the graph, i.e. the iteration
    361364    /// jumps over it. This is done by simply setting the value of \c e 
    362     /// to be false in the corresponding edge-map.
     365    /// to be false in the corresponding uedge-map.
    363366    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
    364367
    365     ///\e
    366 
     368    /// \brief Unhide the given node in the graph.
     369    ///
    367370    /// The value of \c n is set to be true in the node-map which stores
    368371    /// hide information. If \c n was hidden previuosly, then it is shown
     
    370373     void unHide(const Node& n) const { node_filter_map->set(n, true); }
    371374
    372     ///\e
    373 
    374     /// The value of \c e is set to be true in the edge-map which stores
     375    /// \brief Hide the given undirected edge in the graph.
     376    ///
     377    /// The value of \c e is set to be true in the uedge-map which stores
    375378    /// hide information. If \c e was hidden previuosly, then it is shown
    376379    /// again
    377380    void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
    378381
     382    /// \brief Returns true if \c n is hidden.
     383    ///
    379384    /// Returns true if \c n is hidden.
    380    
    381     ///\e
    382     ///
    383385    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
    384386
    385     /// Returns true if \c n is hidden.
    386    
    387     ///\e
    388     ///
     387    /// \brief Returns true if \c e is hidden.
     388    ///
     389    /// Returns true if \c e is hidden.
    389390    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
    390391
     
    578579    }
    579580
    580     ///\e
    581 
     581    /// \brief Hide the given node in the graph.
     582    ///
    582583    /// This function hides \c n in the graph, i.e. the iteration
    583584    /// jumps over it. This is done by simply setting the value of \c n 
     
    585586    void hide(const Node& n) const { node_filter_map->set(n, false); }
    586587
    587     ///\e
    588 
     588    /// \brief Hide the given undirected edge in the graph.
     589    ///
    589590    /// This function hides \c e in the graph, i.e. the iteration
    590591    /// jumps over it. This is done by simply setting the value of \c e 
    591     /// to be false in the corresponding edge-map.
     592    /// to be false in the corresponding uedge-map.
    592593    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
    593594
    594     ///\e
    595 
     595    /// \brief Unhide the given node in the graph.
     596    ///
    596597    /// The value of \c n is set to be true in the node-map which stores
    597598    /// hide information. If \c n was hidden previuosly, then it is shown
     
    599600     void unHide(const Node& n) const { node_filter_map->set(n, true); }
    600601
    601     ///\e
    602 
    603     /// The value of \c e is set to be true in the edge-map which stores
     602    /// \brief Hide the given undirected edge in the graph.
     603    ///
     604    /// The value of \c e is set to be true in the uedge-map which stores
    604605    /// hide information. If \c e was hidden previuosly, then it is shown
    605606    /// again
    606607    void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
    607608
     609    /// \brief Returns true if \c n is hidden.
     610    ///
    608611    /// Returns true if \c n is hidden.
    609    
    610     ///\e
    611     ///
    612612    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
    613613
    614     /// Returns true if \c n is hidden.
    615    
    616     ///\e
    617     ///
     614    /// \brief Returns true if \c e is hidden.
     615    ///
     616    /// Returns true if \c e is hidden.
    618617    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
    619618
     
    734733  /// node-filter.
    735734  ///
    736   /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
    737   /// \c Graph::Node that is why \c g.id(n) can be applied.
    738   ///
    739735  template<typename _UGraph, typename NodeFilterMap,
    740736           typename UEdgeFilterMap, bool checked = true>
Note: See TracChangeset for help on using the changeset viewer.