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

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

Documentation improvements

Rearrangements:

IO modules
Algorithms

New documentation:

Demos:

strongly_connected_orientation.cc

Benchmarks:

swap_bipartite_bench.cc

Location:
lemon
Files:
12 edited

### Legend:

Unmodified
Removed

 r2040 /// /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's /// a-nodeset will be the original graph's b-nodeset and the adaptor's /// b-nodeset will be the original graph's a-nodeset. /// anode-set will be the original graph's bnode-set and the adaptor's /// bnode-set will be the original graph's anode-set. /// /// As example look at an algorithm what can be sped up with the /// swap bipartite undirected graph adaptor. If we want to find the /// maximum matching in the bipartite graph then it will be not changed /// if we swap the two nodesets. But the algorithm use the two nodeset /// different way. If we swap the nodesets it provides different /// running time. We run a test on random bipartite graphs with /// different rate of the anode-set size and bnode-set size. /// We always made graphs with 10000 nodes and 20000 edges and we /// computed the maximum cardinality matching with the Hopcroft-Karp /// algorithm. /// /// The next diagram shows the running time of the tests. If the anode-set /// is smaller than the bnode-set the running time is better than with /// the swapped graph. Other conclusion is that the running time /// is greater when the two nodesets size are nearly equal. /// /// \image html swap_test.png /// \image latex swap_test.eps "Swapping nodesets" width=\textwidth /// /// The next part shows how can we swap the two nodeset: /// ///\code /// typedef SwapBpUGraphAdaptor SBpUGraph; /// SBpUGraph sbpugraph(bpugraph); /// MaxBipartiteMatching sbpumatch(sbpugraph); ///\endcode template class SwapBpUGraphAdaptor public: /// \brief Construct a swapped graph. /// /// Construct a swapped graph. explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
• ## lemon/eps.h

 r2008 #include ///\ingroup io_group ///\ingroup eps_io ///\file ///\brief Simple tool to create \c .eps files namespace lemon { ///\ingroup io_group ///\ingroup eps_io ///\brief A simple tool to create \c .eps files ///

 r2037 */ ///\ingroup io_group ///\ingroup lemon_io ///\file ///\brief Lemon Graph Format reader. namespace lemon { /// \addtogroup io_group /// \addtogroup lemon_io /// @{
• ## lemon/graph_to_eps.h

 r2028 ///\ingroup io_group ///\ingroup eps_io ///\file ///\brief Simple graph drawer ///Generates an EPS file from a graph ///\ingroup io_group ///\ingroup eps_io ///Generates an EPS file from a graph. ///\param g is a reference to the graph to be printed ///Generates an EPS file from a graph ///\ingroup io_group ///\ingroup eps_io ///This function does the same as ///\ref graphToEps(G &g,std::ostream& os) ///Generates an EPS file from a graph ///\ingroup io_group ///\ingroup eps_io ///This function does the same as ///\ref graphToEps(G &g,std::ostream& os)
• ## lemon/kruskal.h

 r1993 #include #include /** @defgroup spantree Minimum Cost Spanning Tree Algorithms @ingroup galgs \brief This group containes the algorithms for finding a minimum cost spanning tree in a graph This group containes the algorithms for finding a minimum cost spanning tree in a graph */ ///\ingroup spantree

 r2016 */ ///\ingroup io_group ///\ingroup lemon_io ///\file ///\brief Lemon Format reader. } /// \ingroup io_group /// \ingroup lemon_io /// \brief Lemon Format reader class. /// char_type* eptr() { return _eptr; } int blen() { return _eptr - _base; } void setb(char_type* buf, int len) { int_type blen() { return _eptr - _base; } void setb(char_type* buf, int_type len) { _base = buf; _eptr = buf + len; } virtual int underflow() { virtual int_type underflow() { char c; if (_is.read(&c, 1)) { } virtual int sync() { virtual int_type sync() { return EOF; }
• ## lemon/lemon_writer.h

 r2016 */ ///\ingroup io_group ///\ingroup lemon_io ///\file ///\brief Lemon Format writer. } /// \ingroup io_group /// \ingroup lemon_io /// \brief Lemon Format writer class. /// virtual std::string header() = 0; /// \brief  Writer function of the section. /// \brief Writer function of the section. /// /// Write the content of the section. virtual void write(std::ostream& os) = 0; /// \brief Gives back true when the section should be written. /// /// Gives back true when the section should be written. virtual bool valid() { return true; } }; SectionWriters::iterator it; for (it = writers.begin(); it != writers.end(); ++it) { *os << (*it)->header() << std::endl; (*it)->write(*os); if ((*it)->valid()) { *os << (*it)->header() << std::endl; (*it)->write(*os); } } *os << "@end" << std::endl; virtual void write(std::ostream& os) { for (int i = 0; i < (int)writers.size(); ++i) { if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) { if (writers[i].first == "label") { labelMap = writers[i].second; forceLabelMap = false; } for (int i = 0; i < (int)writers.size(); ++i) { if (writers[i].first == "label" || (writers[i].first == "id" && labelMap == 0)) { if (writers[i].first == "label") { labelMap = writers[i].second; forceLabelMap = false; } } /// \brief Gives back true when the section should be written. /// /// Gives back true when the section should be written. virtual bool valid() { return !writers.empty(); } private: } } /// \brief Gives back true when the section should be written. /// /// Gives back true when the section should be written. virtual bool valid() { return !writers.empty(); } private: } } /// \brief Gives back true when the section should be written. /// /// Gives back true when the section should be written. virtual bool valid() { return !uEdgeWriters.empty() || !edgeWriters.empty(); } private: } /// \brief Gives back true when the section should be written. /// /// Gives back true when the section should be written. virtual bool valid() { return !writers.empty(); } private: std::string name;
• ## lemon/matrix_maps.h

 r2072 /// \brief Constructor of the row map /// /// Constructor of the row map. MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row) : matrix(_matrix), row(_row) {} /// \brief Constructor of the row map /// /// Constructor of the row map. ConstMatrixRowMap(const MatrixMap& _matrix, typename MatrixMap::FirstKey _row) }; /// \ingroup matrices /// /// \brief Gives back a row view of the matrix map /// /// \ingroup matrices /// Gives back a row view of the matrix map. /// /// \sa MatrixRowMap /// \sa ConstMatrixRowMap template MatrixRowMap matrixRowMap(MatrixMap& matrixMap, typedef typename MatrixMap::Value Value; /// \brief Constructor of the column map /// /// Constructor of the column map. MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col) : matrix(_matrix), col(_col) {} typedef typename MatrixMap::Value Value; /// \brief Constructor of the column map /// /// Constructor of the column map. ConstMatrixColMap(const MatrixMap& _matrix, typename MatrixMap::SecondKey _col) }; /// \ingroup matrices /// /// \brief Gives back a column view of the matrix map /// /// \ingroup matrices /// Gives back a column view of the matrix map. /// /// \sa MatrixColMap /// \sa ConstMatrixColMap template MatrixColMap matrixColMap(MatrixMap& matrixMap,
• ## lemon/path.h

 r2045 */ /** @defgroup paths Path Structures @ingroup datas \brief Path structures implemented in LEMON. LEMON provides flexible data structures to work with paths. All of them have the same interface, especially they can be built or extended using a standard Builder subclass. This make is easy to have e.g. the Dijkstra algorithm to store its result in any kind of path structure. \sa lemon::concept::Path */ ///\ingroup paths