COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
1 deleted
7 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r698 r687  
    336336In most cases the \ref Preflow "Preflow" algorithm provides the
    337337fastest method for computing a maximum flow. All implementations
    338 also provide functions to query the minimum cut, which is the dual
    339 problem of maximum flow.
    340 
    341 \ref Circulation is a preflow push-relabel algorithm implemented directly
    342 for finding feasible circulations, which is a somewhat different problem,
    343 but it is strongly related to maximum flow.
    344 For more information, see \ref Circulation.
     338provides functions to also query the minimum cut, which is the dual
     339problem of the maximum flow.
    345340*/
    346341
    … …  
    547542@defgroup spantree Minimum Spanning Tree Algorithms
    548543@ingroup algs
    549 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    550 
    551 This group contains the algorithms for finding minimum cost spanning
    552 trees and arborescences.
     544\brief Algorithms for finding a minimum cost spanning tree in a graph.
     545
     546This group contains the algorithms for finding a minimum cost spanning
     547tree in a graph.
    553548*/
    554549

  • doc/mainpage.dox

    r698 r606  
    4242\subsection howtoread How to read the documentation
    4343
    44 If you would like to get to know the library, see
     44If you want to get a quick start and see the most important features then
     45take a look at our \ref quicktour
     46"Quick Tour to LEMON" which will guide you along.
     47
     48If you already feel like using our library, see the
    4549<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    4650
    47 If you know what you are looking for, then try to find it under the
     51If you know what you are looking for then try to find it under the
    4852<a class="el" href="modules.html">Modules</a> section.
    4953

  • lemon/connectivity.h

    r695 r633  
    4343  /// \ingroup graph_properties
    4444  ///
    45   /// \brief Check whether an undirected graph is connected.
    46   ///
    47   /// This function checks whether the given undirected graph is connected,
    48   /// i.e. there is a path between any two nodes in the graph.
    49   ///
    50   /// \return \c true if the graph is connected.
     45  /// \brief Check whether the given undirected graph is connected.
     46  ///
     47  /// Check whether the given undirected graph is connected.
     48  /// \param graph The undirected graph.
     49  /// \return \c true when there is path between any two nodes in the graph.
    5150  /// \note By definition, the empty graph is connected.
    52   ///
    53   /// \see countConnectedComponents(), connectedComponents()
    54   /// \see stronglyConnected()
    5551  template <typename Graph>
    5652  bool connected(const Graph& graph) {
    … …  
    7268  /// \brief Count the number of connected components of an undirected graph
    7369  ///
    74   /// This function counts the number of connected components of the given
    75   /// undirected graph.
    76   ///
    77   /// The connected components are the classes of an equivalence relation
    78   /// on the nodes of an undirected graph. Two nodes are in the same class
    79   /// if they are connected with a path.
    80   ///
    81   /// \return The number of connected components.
     70  /// Count the number of connected components of an undirected graph
     71  ///
     72  /// \param graph The graph. It must be undirected.
     73  /// \return The number of components
    8274  /// \note By definition, the empty graph consists
    8375  /// of zero connected components.
    84   ///
    85   /// \see connected(), connectedComponents()
    8676  template <typename Graph>
    8777  int countConnectedComponents(const Graph &graph) {
    … …  
    120110  /// \brief Find the connected components of an undirected graph
    121111  ///
    122   /// This function finds the connected components of the given undirected
    123   /// graph.
    124   ///
    125   /// The connected components are the classes of an equivalence relation
    126   /// on the nodes of an undirected graph. Two nodes are in the same class
    127   /// if they are connected with a path.
     112  /// Find the connected components of an undirected graph.
    128113  ///
    129114  /// \image html connected_components.png
    130115  /// \image latex connected_components.eps "Connected components" width=\textwidth
    131116  ///
    132   /// \param graph The undirected graph.
     117  /// \param graph The graph. It must be undirected.
    133118  /// \retval compMap A writable node map. The values will be set from 0 to
    134   /// the number of the connected components minus one. Each value of the map
    135   /// will be set exactly once, and the values of a certain component will be
     119  /// the number of the connected components minus one. Each values of the map
     120  /// will be set exactly once, the values of a certain component will be
    136121  /// set continuously.
    137   /// \return The number of connected components.
    138   /// \note By definition, the empty graph consists
    139   /// of zero connected components.
    140   ///
    141   /// \see connected(), countConnectedComponents()
     122  /// \return The number of components
    142123  template <class Graph, class NodeMap>
    143124  int connectedComponents(const Graph &graph, NodeMap &compMap) {
    … …  
    251232  /// \ingroup graph_properties
    252233  ///
    253   /// \brief Check whether a directed graph is strongly connected.
    254   ///
    255   /// This function checks whether the given directed graph is strongly
    256   /// connected, i.e. any two nodes of the digraph are
     234  /// \brief Check whether the given directed graph is strongly connected.
     235  ///
     236  /// Check whether the given directed graph is strongly connected. The
     237  /// graph is strongly connected when any two nodes of the graph are
    257238  /// connected with directed paths in both direction.
    258   ///
    259   /// \return \c true if the digraph is strongly connected.
    260   /// \note By definition, the empty digraph is strongly connected.
    261   ///
    262   /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
    263   /// \see connected()
     239  /// \return \c false when the graph is not strongly connected.
     240  /// \see connected
     241  ///
     242  /// \note By definition, the empty graph is strongly connected.
    264243  template <typename Digraph>
    265244  bool stronglyConnected(const Digraph& digraph) {
    … …  
    292271    RDigraph rdigraph(digraph);
    293272
    294     typedef DfsVisitor<RDigraph> RVisitor;
     273    typedef DfsVisitor<Digraph> RVisitor;
    295274    RVisitor rvisitor;
    296275
    … …  
    311290  /// \ingroup graph_properties
    312291  ///
    313   /// \brief Count the number of strongly connected components of a
    314   /// directed graph
    315   ///
    316   /// This function counts the number of strongly connected components of
    317   /// the given directed graph.
    318   ///
     292  /// \brief Count the strongly connected components of a directed graph
     293  ///
     294  /// Count the strongly connected components of a directed graph.
    319295  /// The strongly connected components are the classes of an
    320   /// equivalence relation on the nodes of a digraph. Two nodes are in
     296  /// equivalence relation on the nodes of the graph. Two nodes are in
    321297  /// the same class if they are connected with directed paths in both
    322298  /// direction.
    323299  ///
    324   /// \return The number of strongly connected components.
    325   /// \note By definition, the empty digraph has zero
     300  /// \param digraph The graph.
     301  /// \return The number of components
     302  /// \note By definition, the empty graph has zero
    326303  /// strongly connected components.
    327   ///
    328   /// \see stronglyConnected(), stronglyConnectedComponents()
    329304  template <typename Digraph>
    330305  int countStronglyConnectedComponents(const Digraph& digraph) {
    … …  
    381356  /// \brief Find the strongly connected components of a directed graph
    382357  ///
    383   /// This function finds the strongly connected components of the given
    384   /// directed graph. In addition, the numbering of the components will
    385   /// satisfy that there is no arc going from a higher numbered component
    386   /// to a lower one (i.e. it provides a topological order of the components).
    387   ///
    388   /// The strongly connected components are the classes of an
    389   /// equivalence relation on the nodes of a digraph. Two nodes are in
    390   /// the same class if they are connected with directed paths in both
    391   /// direction.
     358  /// Find the strongly connected components of a directed graph.  The
     359  /// strongly connected components are the classes of an equivalence
     360  /// relation on the nodes of the graph. Two nodes are in
     361  /// relationship when there are directed paths between them in both
     362  /// direction. In addition, the numbering of components will satisfy
     363  /// that there is no arc going from a higher numbered component to
     364  /// a lower.
    392365  ///
    393366  /// \image html strongly_connected_components.png
    … …  
    397370  /// \retval compMap A writable node map. The values will be set from 0 to
    398371  /// the number of the strongly connected components minus one. Each value
    399   /// of the map will be set exactly once, and the values of a certain
    400   /// component will be set continuously.
    401   /// \return The number of strongly connected components.
    402   /// \note By definition, the empty digraph has zero
    403   /// strongly connected components.
    404   ///
    405   /// \see stronglyConnected(), countStronglyConnectedComponents()
     372  /// of the map will be set exactly once, the values of a certain component
     373  /// will be set continuously.
     374  /// \return The number of components
    406375  template <typename Digraph, typename NodeMap>
    407376  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
    … …  
    456425  /// \brief Find the cut arcs of the strongly connected components.
    457426  ///
    458   /// This function finds the cut arcs of the strongly connected components
    459   /// of the given digraph.
    460   ///
    461   /// The strongly connected components are the classes of an
    462   /// equivalence relation on the nodes of a digraph. Two nodes are in
    463   /// the same class if they are connected with directed paths in both
    464   /// direction.
     427  /// Find the cut arcs of the strongly connected components.
     428  /// The strongly connected components are the classes of an equivalence
     429  /// relation on the nodes of the graph. Two nodes are in relationship
     430  /// when there are directed paths between them in both direction.
    465431  /// The strongly connected components are separated by the cut arcs.
    466432  ///
    467   /// \param digraph The digraph.
    468   /// \retval cutMap A writable arc map. The values will be set to \c true
    469   /// for the cut arcs (exactly once for each cut arc), and will not be
    470   /// changed for other arcs.
    471   /// \return The number of cut arcs.
    472   ///
    473   /// \see stronglyConnected(), stronglyConnectedComponents()
     433  /// \param graph The graph.
     434  /// \retval cutMap A writable node map. The values will be set true when the
     435  /// arc is a cut arc.
     436  ///
     437  /// \return The number of cut arcs
    474438  template <typename Digraph, typename ArcMap>
    475   int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
     439  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
    476440    checkConcept<concepts::Digraph, Digraph>();
    477441    typedef typename Digraph::Node Node;
    … …  
    485449    typedef typename Container::iterator Iterator;
    486450
    487     Container nodes(countNodes(digraph));
     451    Container nodes(countNodes(graph));
    488452    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
    489453    Visitor visitor(nodes.begin());
    490454
    491     DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
     455    DfsVisit<Digraph, Visitor> dfs(graph, visitor);
    492456    dfs.init();
    493     for (NodeIt it(digraph); it != INVALID; ++it) {
     457    for (NodeIt it(graph); it != INVALID; ++it) {
    494458      if (!dfs.reached(it)) {
    495459        dfs.addSource(it);
    … …  
    501465    typedef ReverseDigraph<const Digraph> RDigraph;
    502466
    503     RDigraph rdigraph(digraph);
     467    RDigraph rgraph(graph);
    504468
    505469    int cutNum = 0;
    506470
    507471    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
    508     RVisitor rvisitor(rdigraph, cutMap, cutNum);
    509 
    510     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
     472    RVisitor rvisitor(rgraph, cutMap, cutNum);
     473
     474    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
    511475
    512476    rdfs.init();
    … …  
    743707  /// \ingroup graph_properties
    744708  ///
    745   /// \brief Check whether an undirected graph is bi-node-connected.
    746   ///
    747   /// This function checks whether the given undirected graph is
    748   /// bi-node-connected, i.e. any two edges are on same circle.
    749   ///
    750   /// \return \c true if the graph bi-node-connected.
    751   /// \note By definition, the empty graph is bi-node-connected.
    752   ///
    753   /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
     709  /// \brief Checks the graph is bi-node-connected.
     710  ///
     711  /// This function checks that the undirected graph is bi-node-connected
     712  /// graph. The graph is bi-node-connected if any two undirected edge is
     713  /// on same circle.
     714  ///
     715  /// \param graph The graph.
     716  /// \return \c true when the graph bi-node-connected.
    754717  template <typename Graph>
    755718  bool biNodeConnected(const Graph& graph) {
    … …  
    759722  /// \ingroup graph_properties
    760723  ///
    761   /// \brief Count the number of bi-node-connected components of an
    762   /// undirected graph.
    763   ///
    764   /// This function counts the number of bi-node-connected components of
    765   /// the given undirected graph.
    766   ///
    767   /// The bi-node-connected components are the classes of an equivalence
    768   /// relation on the edges of a undirected graph. Two edges are in the
    769   /// same class if they are on same circle.
    770   ///
    771   /// \return The number of bi-node-connected components.
    772   ///
    773   /// \see biNodeConnected(), biNodeConnectedComponents()
     724  /// \brief Count the biconnected components.
     725  ///
     726  /// This function finds the bi-node-connected components in an undirected
     727  /// graph. The biconnected components are the classes of an equivalence
     728  /// relation on the undirected edges. Two undirected edge is in relationship
     729  /// when they are on same circle.
     730  ///
     731  /// \param graph The graph.
     732  /// \return The number of components.
    774733  template <typename Graph>
    775734  int countBiNodeConnectedComponents(const Graph& graph) {
    … …  
    798757  /// \ingroup graph_properties
    799758  ///
    800   /// \brief Find the bi-node-connected components of an undirected graph.
    801   ///
    802   /// This function finds the bi-node-connected components of the given
    803   /// undirected graph.
    804   ///
    805   /// The bi-node-connected components are the classes of an equivalence
    806   /// relation on the edges of a undirected graph. Two edges are in the
    807   /// same class if they are on same circle.
     759  /// \brief Find the bi-node-connected components.
     760  ///
     761  /// This function finds the bi-node-connected components in an undirected
     762  /// graph. The bi-node-connected components are the classes of an equivalence
     763  /// relation on the undirected edges. Two undirected edge are in relationship
     764  /// when they are on same circle.
    808765  ///
    809766  /// \image html node_biconnected_components.png
    810767  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
    811768  ///
    812   /// \param graph The undirected graph.
    813   /// \retval compMap A writable edge map. The values will be set from 0
    814   /// to the number of the bi-node-connected components minus one. Each
    815   /// value of the map will be set exactly once, and the values of a
    816   /// certain component will be set continuously.
    817   /// \return The number of bi-node-connected components.
    818   ///
    819   /// \see biNodeConnected(), countBiNodeConnectedComponents()
     769  /// \param graph The graph.
     770  /// \retval compMap A writable uedge map. The values will be set from 0
     771  /// to the number of the biconnected components minus one. Each values
     772  /// of the map will be set exactly once, the values of a certain component
     773  /// will be set continuously.
     774  /// \return The number of components.
    820775  template <typename Graph, typename EdgeMap>
    821776  int biNodeConnectedComponents(const Graph& graph,
    … …  
    847802  /// \ingroup graph_properties
    848803  ///
    849   /// \brief Find the bi-node-connected cut nodes in an undirected graph.
    850   ///
    851   /// This function finds the bi-node-connected cut nodes in the given
    852   /// undirected graph.
    853   ///
    854   /// The bi-node-connected components are the classes of an equivalence
    855   /// relation on the edges of a undirected graph. Two edges are in the
    856   /// same class if they are on same circle.
    857   /// The bi-node-connected components are separted by the cut nodes of
    858   /// the components.
    859   ///
    860   /// \param graph The undirected graph.
    861   /// \retval cutMap A writable node map. The values will be set to
    862   /// \c true for the nodes that separate two or more components
    863   /// (exactly once for each cut node), and will not be changed for
    864   /// other nodes.
     804  /// \brief Find the bi-node-connected cut nodes.
     805  ///
     806  /// This function finds the bi-node-connected cut nodes in an undirected
     807  /// graph. The bi-node-connected components are the classes of an equivalence
     808  /// relation on the undirected edges. Two undirected edges are in
     809  /// relationship when they are on same circle. The biconnected components
     810  /// are separted by nodes which are the cut nodes of the components.
     811  ///
     812  /// \param graph The graph.
     813  /// \retval cutMap A writable edge map. The values will be set true when
     814  /// the node separate two or more components.
    865815  /// \return The number of the cut nodes.
    866   ///
    867   /// \see biNodeConnected(), biNodeConnectedComponents()
    868816  template <typename Graph, typename NodeMap>
    869817  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
    … …  
    10841032  /// \ingroup graph_properties
    10851033  ///
    1086   /// \brief Check whether an undirected graph is bi-edge-connected.
    1087   ///
    1088   /// This function checks whether the given undirected graph is
    1089   /// bi-edge-connected, i.e. any two nodes are connected with at least
    1090   /// two edge-disjoint paths.
    1091   ///
    1092   /// \return \c true if the graph is bi-edge-connected.
    1093   /// \note By definition, the empty graph is bi-edge-connected.
    1094   ///
    1095   /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
     1034  /// \brief Checks that the graph is bi-edge-connected.
     1035  ///
     1036  /// This function checks that the graph is bi-edge-connected. The undirected
     1037  /// graph is bi-edge-connected when any two nodes are connected with two
     1038  /// edge-disjoint paths.
     1039  ///
     1040  /// \param graph The undirected graph.
     1041  /// \return The number of components.
    10961042  template <typename Graph>
    10971043  bool biEdgeConnected(const Graph& graph) {
    … …  
    11011047  /// \ingroup graph_properties
    11021048  ///
    1103   /// \brief Count the number of bi-edge-connected components of an
    1104   /// undirected graph.
    1105   ///
    1106   /// This function counts the number of bi-edge-connected components of
    1107   /// the given undirected graph.
    1108   ///
    1109   /// The bi-edge-connected components are the classes of an equivalence
    1110   /// relation on the nodes of an undirected graph. Two nodes are in the
    1111   /// same class if they are connected with at least two edge-disjoint
    1112   /// paths.
    1113   ///
    1114   /// \return The number of bi-edge-connected components.
    1115   ///
    1116   /// \see biEdgeConnected(), biEdgeConnectedComponents()
     1049  /// \brief Count the bi-edge-connected components.
     1050  ///
     1051  /// This function count the bi-edge-connected components in an undirected
     1052  /// graph. The bi-edge-connected components are the classes of an equivalence
     1053  /// relation on the nodes. Two nodes are in relationship when they are
     1054  /// connected with at least two edge-disjoint paths.
     1055  ///
     1056  /// \param graph The undirected graph.
     1057  /// \return The number of components.
    11171058  template <typename Graph>
    11181059  int countBiEdgeConnectedComponents(const Graph& graph) {
    … …  
    11411082  /// \ingroup graph_properties
    11421083  ///
    1143   /// \brief Find the bi-edge-connected components of an undirected graph.
    1144   ///
    1145   /// This function finds the bi-edge-connected components of the given
    1146   /// undirected graph.
    1147   ///
    1148   /// The bi-edge-connected components are the classes of an equivalence
    1149   /// relation on the nodes of an undirected graph. Two nodes are in the
    1150   /// same class if they are connected with at least two edge-disjoint
    1151   /// paths.
     1084  /// \brief Find the bi-edge-connected components.
     1085  ///
     1086  /// This function finds the bi-edge-connected components in an undirected
     1087  /// graph. The bi-edge-connected components are the classes of an equivalence
     1088  /// relation on the nodes. Two nodes are in relationship when they are
     1089  /// connected at least two edge-disjoint paths.
    11521090  ///
    11531091  /// \image html edge_biconnected_components.png
    11541092  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    11551093  ///
    1156   /// \param graph The undirected graph.
     1094  /// \param graph The graph.
    11571095  /// \retval compMap A writable node map. The values will be set from 0 to
    1158   /// the number of the bi-edge-connected components minus one. Each value
    1159   /// of the map will be set exactly once, and the values of a certain
    1160   /// component will be set continuously.
    1161   /// \return The number of bi-edge-connected components.
    1162   ///
    1163   /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
     1096  /// the number of the biconnected components minus one. Each values
     1097  /// of the map will be set exactly once, the values of a certain component
     1098  /// will be set continuously.
     1099  /// \return The number of components.
    11641100  template <typename Graph, typename NodeMap>
    11651101  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
    … …  
    11901126  /// \ingroup graph_properties
    11911127  ///
    1192   /// \brief Find the bi-edge-connected cut edges in an undirected graph.
    1193   ///
    1194   /// This function finds the bi-edge-connected cut edges in the given
    1195   /// undirected graph.
    1196   ///
    1197   /// The bi-edge-connected components are the classes of an equivalence
    1198   /// relation on the nodes of an undirected graph. Two nodes are in the
    1199   /// same class if they are connected with at least two edge-disjoint
    1200   /// paths.
    1201   /// The bi-edge-connected components are separted by the cut edges of
    1202   /// the components.
    1203   ///
    1204   /// \param graph The undirected graph.
    1205   /// \retval cutMap A writable edge map. The values will be set to \c true
    1206   /// for the cut edges (exactly once for each cut edge), and will not be
    1207   /// changed for other edges.
     1128  /// \brief Find the bi-edge-connected cut edges.
     1129  ///
     1130  /// This function finds the bi-edge-connected components in an undirected
     1131  /// graph. The bi-edge-connected components are the classes of an equivalence
     1132  /// relation on the nodes. Two nodes are in relationship when they are
     1133  /// connected with at least two edge-disjoint paths. The bi-edge-connected
     1134  /// components are separted by edges which are the cut edges of the
     1135  /// components.
     1136  ///
     1137  /// \param graph The graph.
     1138  /// \retval cutMap A writable node map. The values will be set true when the
     1139  /// edge is a cut edge.
    12081140  /// \return The number of cut edges.
    1209   ///
    1210   /// \see biEdgeConnected(), biEdgeConnectedComponents()
    12111141  template <typename Graph, typename EdgeMap>
    12121142  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
    … …  
    12601190  /// \ingroup graph_properties
    12611191  ///
    1262   /// \brief Check whether a digraph is DAG.
    1263   ///
    1264   /// This function checks whether the given digraph is DAG, i.e.
    1265   /// \e Directed \e Acyclic \e Graph.
    1266   /// \return \c true if there is no directed cycle in the digraph.
    1267   /// \see acyclic()
    1268   template <typename Digraph>
    1269   bool dag(const Digraph& digraph) {
     1192  /// \brief Sort the nodes of a DAG into topolgical order.
     1193  ///
     1194  /// Sort the nodes of a DAG into topolgical order.
     1195  ///
     1196  /// \param graph The graph. It must be directed and acyclic.
     1197  /// \retval order A writable node map. The values will be set from 0 to
     1198  /// the number of the nodes in the graph minus one. Each values of the map
     1199  /// will be set exactly once, the values  will be set descending order.
     1200  ///
     1201  /// \see checkedTopologicalSort
     1202  /// \see dag
     1203  template <typename Digraph, typename NodeMap>
     1204  void topologicalSort(const Digraph& graph, NodeMap& order) {
     1205    using namespace _connectivity_bits;
    12701206
    12711207    checkConcept<concepts::Digraph, Digraph>();
     1208    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
    12721209
    12731210    typedef typename Digraph::Node Node;
    … …  
    12751212    typedef typename Digraph::Arc Arc;
    12761213
    1277     typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    1278 
    1279     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
    1280       Create dfs(digraph);
    1281 
    1282     ProcessedMap processed(digraph);
    1283     dfs.processedMap(processed);
     1214    TopologicalSortVisitor<Digraph, NodeMap>
     1215      visitor(order, countNodes(graph));
     1216
     1217    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
     1218      dfs(graph, visitor);
    12841219
    12851220    dfs.init();
    1286     for (NodeIt it(digraph); it != INVALID; ++it) {
    1287       if (!dfs.reached(it)) {
    1288         dfs.addSource(it);
    1289         while (!dfs.emptyQueue()) {
    1290           Arc arc = dfs.nextArc();
    1291           Node target = digraph.target(arc);
    1292           if (dfs.reached(target) && !processed[target]) {
    1293             return false;
    1294           }
    1295           dfs.processNextArc();
    1296         }
    1297       }
    1298     }
    1299     return true;
    1300   }
    1301 
    1302   /// \ingroup graph_properties
    1303   ///
    1304   /// \brief Sort the nodes of a DAG into topolgical order.
    1305   ///
    1306   /// This function sorts the nodes of the given acyclic digraph (DAG)
    1307   /// into topolgical order.
    1308   ///
    1309   /// \param digraph The digraph, which must be DAG.
    1310   /// \retval order A writable node map. The values will be set from 0 to
    1311   /// the number of the nodes in the digraph minus one. Each value of the
    1312   /// map will be set exactly once, and the values will be set descending
    1313   /// order.
    1314   ///
    1315   /// \see dag(), checkedTopologicalSort()
    1316   template <typename Digraph, typename NodeMap>
    1317   void topologicalSort(const Digraph& digraph, NodeMap& order) {
    1318     using namespace _connectivity_bits;
    1319 
    1320     checkConcept<concepts::Digraph, Digraph>();
    1321     checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
    1322 
    1323     typedef typename Digraph::Node Node;
    1324     typedef typename Digraph::NodeIt NodeIt;
    1325     typedef typename Digraph::Arc Arc;
    1326 
    1327     TopologicalSortVisitor<Digraph, NodeMap>
    1328       visitor(order, countNodes(digraph));
    1329 
    1330     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
    1331       dfs(digraph, visitor);
    1332 
    1333     dfs.init();
    1334     for (NodeIt it(digraph); it != INVALID; ++it) {
     1221    for (NodeIt it(graph); it != INVALID; ++it) {
    13351222      if (!dfs.reached(it)) {
    13361223        dfs.addSource(it);
    … …  
    13441231  /// \brief Sort the nodes of a DAG into topolgical order.
    13451232  ///
    1346   /// This function sorts the nodes of the given acyclic digraph (DAG)
    1347   /// into topolgical order and also checks whether the given digraph
    1348   /// is DAG.
    1349   ///
    1350   /// \param digraph The digraph.
    1351   /// \retval order A readable and writable node map. The values will be
    1352   /// set from 0 to the number of the nodes in the digraph minus one.
    1353   /// Each value of the map will be set exactly once, and the values will
    1354   /// be set descending order.
    1355   /// \return \c false if the digraph is not DAG.
    1356   ///
    1357   /// \see dag(), topologicalSort()
     1233  /// Sort the nodes of a DAG into topolgical order. It also checks
     1234  /// that the given graph is DAG.
     1235  ///
     1236  /// \param digraph The graph. It must be directed and acyclic.
     1237  /// \retval order A readable - writable node map. The values will be set
     1238  /// from 0 to the number of the nodes in the graph minus one. Each values
     1239  /// of the map will be set exactly once, the values will be set descending
     1240  /// order.
     1241  /// \return \c false when the graph is not DAG.
     1242  ///
     1243  /// \see topologicalSort
     1244  /// \see dag
    13581245  template <typename Digraph, typename NodeMap>
    13591246  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
    … …  
    13971284  /// \ingroup graph_properties
    13981285  ///
    1399   /// \brief Check whether an undirected graph is acyclic.
    1400   ///
    1401   /// This function checks whether the given undirected graph is acyclic.
    1402   /// \return \c true if there is no cycle in the graph.
    1403   /// \see dag()
     1286  /// \brief Check that the given directed graph is a DAG.
     1287  ///
     1288  /// Check that the given directed graph is a DAG. The DAG is
     1289  /// an Directed Acyclic Digraph.
     1290  /// \return \c false when the graph is not DAG.
     1291  /// \see acyclic
     1292  template <typename Digraph>
     1293  bool dag(const Digraph& digraph) {
     1294
     1295    checkConcept<concepts::Digraph, Digraph>();
     1296
     1297    typedef typename Digraph::Node Node;
     1298    typedef typename Digraph::NodeIt NodeIt;
     1299    typedef typename Digraph::Arc Arc;
     1300
     1301    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
     1302
     1303    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
     1304      Create dfs(digraph);
     1305
     1306    ProcessedMap processed(digraph);
     1307    dfs.processedMap(processed);
     1308
     1309    dfs.init();
     1310    for (NodeIt it(digraph); it != INVALID; ++it) {
     1311      if (!dfs.reached(it)) {
     1312        dfs.addSource(it);
     1313        while (!dfs.emptyQueue()) {
     1314          Arc edge = dfs.nextArc();
     1315          Node target = digraph.target(edge);
     1316          if (dfs.reached(target) && !processed[target]) {
     1317            return false;
     1318          }
     1319          dfs.processNextArc();
     1320        }
     1321      }
     1322    }
     1323    return true;
     1324  }
     1325
     1326  /// \ingroup graph_properties
     1327  ///
     1328  /// \brief Check that the given undirected graph is acyclic.
     1329  ///
     1330  /// Check that the given undirected graph acyclic.
     1331  /// \param graph The undirected graph.
     1332  /// \return \c true when there is no circle in the graph.
     1333  /// \see dag
    14041334  template <typename Graph>
    14051335  bool acyclic(const Graph& graph) {
    … …  
    14141344        dfs.addSource(it);
    14151345        while (!dfs.emptyQueue()) {
    1416           Arc arc = dfs.nextArc();
    1417           Node source = graph.source(arc);
    1418           Node target = graph.target(arc);
     1346          Arc edge = dfs.nextArc();
     1347          Node source = graph.source(edge);
     1348          Node target = graph.target(edge);
    14191349          if (dfs.reached(target) &&
    1420               dfs.predArc(source) != graph.oppositeArc(arc)) {
     1350              dfs.predArc(source) != graph.oppositeArc(edge)) {
    14211351            return false;
    14221352          }
    … …  
    14301360  /// \ingroup graph_properties
    14311361  ///
    1432   /// \brief Check whether an undirected graph is tree.
    1433   ///
    1434   /// This function checks whether the given undirected graph is tree.
    1435   /// \return \c true if the graph is acyclic and connected.
    1436   /// \see acyclic(), connected()
     1362  /// \brief Check that the given undirected graph is tree.
     1363  ///
     1364  /// Check that the given undirected graph is tree.
     1365  /// \param graph The undirected graph.
     1366  /// \return \c true when the graph is acyclic and connected.
    14371367  template <typename Graph>
    14381368  bool tree(const Graph& graph) {
    … …  
    14411371    typedef typename Graph::NodeIt NodeIt;
    14421372    typedef typename Graph::Arc Arc;
    1443     if (NodeIt(graph) == INVALID) return true;
    14441373    Dfs<Graph> dfs(graph);
    14451374    dfs.init();
    14461375    dfs.addSource(NodeIt(graph));
    14471376    while (!dfs.emptyQueue()) {
    1448       Arc arc = dfs.nextArc();
    1449       Node source = graph.source(arc);
    1450       Node target = graph.target(arc);
     1377      Arc edge = dfs.nextArc();
     1378      Node source = graph.source(edge);
     1379      Node target = graph.target(edge);
    14511380      if (dfs.reached(target) &&
    1452           dfs.predArc(source) != graph.oppositeArc(arc)) {
     1381          dfs.predArc(source) != graph.oppositeArc(edge)) {
    14531382        return false;
    14541383      }
    … …  
    15231452  /// \ingroup graph_properties
    15241453  ///
    1525   /// \brief Check whether an undirected graph is bipartite.
    1526   ///
    1527   /// The function checks whether the given undirected graph is bipartite.
    1528   /// \return \c true if the graph is bipartite.
    1529   ///
    1530   /// \see bipartitePartitions()
     1454  /// \brief Check if the given undirected graph is bipartite or not
     1455  ///
     1456  /// The function checks if the given undirected \c graph graph is bipartite
     1457  /// or not. The \ref Bfs algorithm is used to calculate the result.
     1458  /// \param graph The undirected graph.
     1459  /// \return \c true if \c graph is bipartite, \c false otherwise.
     1460  /// \sa bipartitePartitions
    15311461  template<typename Graph>
    1532   bool bipartite(const Graph &graph){
     1462  inline bool bipartite(const Graph &graph){
    15331463    using namespace _connectivity_bits;
    15341464
    … …  
    15591489  /// \ingroup graph_properties
    15601490  ///
    1561   /// \brief Find the bipartite partitions of an undirected graph.
    1562   ///
    1563   /// This function checks whether the given undirected graph is bipartite
    1564   /// and gives back the bipartite partitions.
     1491  /// \brief Check if the given undirected graph is bipartite or not
     1492  ///
     1493  /// The function checks if the given undirected graph is bipartite
     1494  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
     1495  /// During the execution, the \c partMap will be set as the two
     1496  /// partitions of the graph.
    15651497  ///
    15661498  /// \image html bipartite_partitions.png
    … …  
    15681500  ///
    15691501  /// \param graph The undirected graph.
    1570   /// \retval partMap A writable node map of \c bool (or convertible) value
    1571   /// type. The values will be set to \c true for one component and
    1572   /// \c false for the other one.
    1573   /// \return \c true if the graph is bipartite, \c false otherwise.
    1574   ///
    1575   /// \see bipartite()
     1502  /// \retval partMap A writable bool map of nodes. It will be set as the
     1503  /// two partitions of the graph.
     1504  /// \return \c true if \c graph is bipartite, \c false otherwise.
    15761505  template<typename Graph, typename NodeMap>
    1577   bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
     1506  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
    15781507    using namespace _connectivity_bits;
    15791508
    15801509    checkConcept<concepts::Graph, Graph>();
    1581     checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
    15821510
    15831511    typedef typename Graph::Node Node;
    … …  
    16041532  }
    16051533
    1606   /// \ingroup graph_properties
    1607   ///
    1608   /// \brief Check whether the given graph contains no loop arcs/edges.
    1609   ///
    1610   /// This function returns \c true if there are no loop arcs/edges in
    1611   /// the given graph. It works for both directed and undirected graphs.
    1612   template <typename Graph>
    1613   bool loopFree(const Graph& graph) {
    1614     for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
    1615       if (graph.source(it) == graph.target(it)) return false;
     1534  /// \brief Returns true when there are not loop edges in the graph.
     1535  ///
     1536  /// Returns true when there are not loop edges in the graph.
     1537  template <typename Digraph>
     1538  bool loopFree(const Digraph& digraph) {
     1539    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
     1540      if (digraph.source(it) == digraph.target(it)) return false;
    16161541    }
    16171542    return true;
    16181543  }
    16191544
    1620   /// \ingroup graph_properties
    1621   ///
    1622   /// \brief Check whether the given graph contains no parallel arcs/edges.
    1623   ///
    1624   /// This function returns \c true if there are no parallel arcs/edges in
    1625   /// the given graph. It works for both directed and undirected graphs.
    1626   template <typename Graph>
    1627   bool parallelFree(const Graph& graph) {
    1628     typename Graph::template NodeMap<int> reached(graph, 0);
    1629     int cnt = 1;
    1630     for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
    1631       for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
    1632         if (reached[graph.target(a)] == cnt) return false;
    1633         reached[graph.target(a)] = cnt;
    1634       }
    1635       ++cnt;
     1545  /// \brief Returns true when there are not parallel edges in the graph.
     1546  ///
     1547  /// Returns true when there are not parallel edges in the graph.
     1548  template <typename Digraph>
     1549  bool parallelFree(const Digraph& digraph) {
     1550    typename Digraph::template NodeMap<bool> reached(digraph, false);
     1551    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
     1552      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
     1553        if (reached[digraph.target(a)]) return false;
     1554        reached.set(digraph.target(a), true);
     1555      }
     1556      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
     1557        reached.set(digraph.target(a), false);
     1558      }
    16361559    }
    16371560    return true;
    16381561  }
    16391562
    1640   /// \ingroup graph_properties
    1641   ///
    1642   /// \brief Check whether the given graph is simple.
    1643   ///
    1644   /// This function returns \c true if the given graph is simple, i.e.
    1645   /// it contains no loop arcs/edges and no parallel arcs/edges.
    1646   /// The function works for both directed and undirected graphs.
    1647   /// \see loopFree(), parallelFree()
    1648   template <typename Graph>
    1649   bool simpleGraph(const Graph& graph) {
    1650     typename Graph::template NodeMap<int> reached(graph, 0);
    1651     int cnt = 1;
    1652     for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
    1653       reached[n] = cnt;
    1654       for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
    1655         if (reached[graph.target(a)] == cnt) return false;
    1656         reached[graph.target(a)] = cnt;
    1657       }
    1658       ++cnt;
     1563  /// \brief Returns true when there are not loop edges and parallel
     1564  /// edges in the graph.
     1565  ///
     1566  /// Returns true when there are not loop edges and parallel edges in
     1567  /// the graph.
     1568  template <typename Digraph>
     1569  bool simpleDigraph(const Digraph& digraph) {
     1570    typename Digraph::template NodeMap<bool> reached(digraph, false);
     1571    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
     1572      reached.set(n, true);
     1573      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
     1574        if (reached[digraph.target(a)]) return false;
     1575        reached.set(digraph.target(a), true);
     1576      }
     1577      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
     1578        reached.set(digraph.target(a), false);
     1579      }
     1580      reached.set(n, false);
    16591581    }
    16601582    return true;

  • lemon/euler.h

    r695 r639  
    245245
    246246
    247   ///Check if the given graph is Eulerian
     247  ///Check if the given graph is \e Eulerian
    248248
    249249  /// \ingroup graph_properties
    250   ///This function checks if the given graph is Eulerian.
     250  ///This function checks if the given graph is \e Eulerian.
    251251  ///It works for both directed and undirected graphs.
    252252  ///

  • lemon/matching.h

    r698 r641  
    500500    /// This function runs the original Edmonds' algorithm.
    501501    ///
    502     /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
     502    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
    503503    /// called before using this function.
    504504    void startSparse() {
    … …  
    519519    /// shrinks, therefore resulting in a faster algorithm for dense graphs.
    520520    ///
    521     /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
     521    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
    522522    /// called before using this function.
    523523    void startDense() {

  • test/CMakeLists.txt

    r696 r674  
    1010  bfs_test
    1111  circulation_test
    12   connectivity_test
    1312  counter_test
    1413  dfs_test

  • test/Makefile.am

    r696 r658  
    1010        test/bfs_test \
    1111        test/circulation_test \
    12         test/connectivity_test \
    1312        test/counter_test \
    1413        test/dfs_test \
    … …  
    5655test_circulation_test_SOURCES = test/circulation_test.cc
    5756test_counter_test_SOURCES = test/counter_test.cc
    58 test_connectivity_test_SOURCES = test/connectivity_test.cc
    5957test_dfs_test_SOURCES = test/dfs_test.cc
    6058test_digraph_test_SOURCES = test/digraph_test.cc
Note: See TracChangeset for help on using the changeset viewer.