# Changes in /[697:a8dfe89b7719:700:682941948726] in lemon

Ignore:
Files:
7 edited

Unmodified
Removed
• ## doc/groups.dox

 r687 In most cases the \ref Preflow "Preflow" algorithm provides the fastest method for computing a maximum flow. All implementations provides functions to also query the minimum cut, which is the dual problem of the maximum flow. also provide functions to query the minimum cut, which is the dual problem of maximum flow. \ref Circulation is a preflow push-relabel algorithm implemented directly for finding feasible circulations, which is a somewhat different problem, but it is strongly related to maximum flow. For more information, see \ref Circulation. */ @defgroup spantree Minimum Spanning Tree Algorithms @ingroup algs \brief Algorithms for finding a minimum cost spanning tree in a graph. This group contains the algorithms for finding a minimum cost spanning tree in a graph. \brief Algorithms for finding minimum cost spanning trees and arborescences. This group contains the algorithms for finding minimum cost spanning trees and arborescences. */
• ## doc/mainpage.dox

 r606 \subsection howtoread How to read the documentation If you want to get a quick start and see the most important features then take a look at our \ref quicktour "Quick Tour to LEMON" which will guide you along. If you already feel like using our library, see the If you would like to get to know the library, see LEMON Tutorial. If you know what you are looking for then try to find it under the If you know what you are looking for, then try to find it under the Modules section.
• ## lemon/connectivity.h

 r633 /// \ingroup graph_properties /// /// \brief Check whether the given undirected graph is connected. /// /// Check whether the given undirected graph is connected. /// \param graph The undirected graph. /// \return \c true when there is path between any two nodes in the graph. /// \brief Check whether an undirected graph is connected. /// /// This function checks whether the given undirected graph is connected, /// i.e. there is a path between any two nodes in the graph. /// /// \return \c true if the graph is connected. /// \note By definition, the empty graph is connected. /// /// \see countConnectedComponents(), connectedComponents() /// \see stronglyConnected() template bool connected(const Graph& graph) { /// \brief Count the number of connected components of an undirected graph /// /// Count the number of connected components of an undirected graph /// /// \param graph The graph. It must be undirected. /// \return The number of components /// This function counts the number of connected components of the given /// undirected graph. /// /// The connected components are the classes of an equivalence relation /// on the nodes of an undirected graph. Two nodes are in the same class /// if they are connected with a path. /// /// \return The number of connected components. /// \note By definition, the empty graph consists /// of zero connected components. /// /// \see connected(), connectedComponents() template int countConnectedComponents(const Graph &graph) { /// \brief Find the connected components of an undirected graph /// /// Find the connected components of an undirected graph. /// This function finds the connected components of the given undirected /// graph. /// /// The connected components are the classes of an equivalence relation /// on the nodes of an undirected graph. Two nodes are in the same class /// if they are connected with a path. /// /// \image html connected_components.png /// \image latex connected_components.eps "Connected components" width=\textwidth /// /// \param graph The graph. It must be undirected. /// \param graph The undirected graph. /// \retval compMap A writable node map. The values will be set from 0 to /// the number of the connected components minus one. Each values of the map /// will be set exactly once, the values of a certain component will be /// the number of the connected components minus one. Each value of the map /// will be set exactly once, and the values of a certain component will be /// set continuously. /// \return The number of components /// \return The number of connected components. /// \note By definition, the empty graph consists /// of zero connected components. /// /// \see connected(), countConnectedComponents() template int connectedComponents(const Graph &graph, NodeMap &compMap) { /// \ingroup graph_properties /// /// \brief Check whether the given directed graph is strongly connected. /// /// Check whether the given directed graph is strongly connected. The /// graph is strongly connected when any two nodes of the graph are /// \brief Check whether a directed graph is strongly connected. /// /// This function checks whether the given directed graph is strongly /// connected, i.e. any two nodes of the digraph are /// connected with directed paths in both direction. /// \return \c false when the graph is not strongly connected. /// \see connected /// /// \note By definition, the empty graph is strongly connected. /// /// \return \c true if the digraph is strongly connected. /// \note By definition, the empty digraph is strongly connected. /// /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() /// \see connected() template bool stronglyConnected(const Digraph& digraph) { RDigraph rdigraph(digraph); typedef DfsVisitor RVisitor; typedef DfsVisitor RVisitor; RVisitor rvisitor; /// \ingroup graph_properties /// /// \brief Count the strongly connected components of a directed graph /// /// Count the strongly connected components of a directed graph. /// \brief Count the number of strongly connected components of a /// directed graph /// /// This function counts the number of strongly connected components of /// the given directed graph. /// /// The strongly connected components are the classes of an /// equivalence relation on the nodes of the graph. Two nodes are in /// equivalence relation on the nodes of a digraph. Two nodes are in /// the same class if they are connected with directed paths in both /// direction. /// /// \param digraph The graph. /// \return The number of components /// \note By definition, the empty graph has zero /// \return The number of strongly connected components. /// \note By definition, the empty digraph has zero /// strongly connected components. /// /// \see stronglyConnected(), stronglyConnectedComponents() template int countStronglyConnectedComponents(const Digraph& digraph) { /// \brief Find the strongly connected components of a directed graph /// /// Find the strongly connected components of a directed graph.  The /// strongly connected components are the classes of an equivalence /// relation on the nodes of the graph. Two nodes are in /// relationship when there are directed paths between them in both /// direction. In addition, the numbering of components will satisfy /// that there is no arc going from a higher numbered component to /// a lower. /// This function finds the strongly connected components of the given /// directed graph. In addition, the numbering of the components will /// satisfy that there is no arc going from a higher numbered component /// to a lower one (i.e. it provides a topological order of the components). /// /// The strongly connected components are the classes of an /// equivalence relation on the nodes of a digraph. Two nodes are in /// the same class if they are connected with directed paths in both /// direction. /// /// \image html strongly_connected_components.png /// \retval compMap A writable node map. The values will be set from 0 to /// the number of the strongly connected components minus one. Each value /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components /// of the map will be set exactly once, and the values of a certain /// component will be set continuously. /// \return The number of strongly connected components. /// \note By definition, the empty digraph has zero /// strongly connected components. /// /// \see stronglyConnected(), countStronglyConnectedComponents() template int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { /// \brief Find the cut arcs of the strongly connected components. /// /// Find the cut arcs of the strongly connected components. /// The strongly connected components are the classes of an equivalence /// relation on the nodes of the graph. Two nodes are in relationship /// when there are directed paths between them in both direction. /// This function finds the cut arcs of the strongly connected components /// of the given digraph. /// /// The strongly connected components are the classes of an /// equivalence relation on the nodes of a digraph. Two nodes are in /// the same class if they are connected with directed paths in both /// direction. /// The strongly connected components are separated by the cut arcs. /// /// \param graph The graph. /// \retval cutMap A writable node map. The values will be set true when the /// arc is a cut arc. /// /// \return The number of cut arcs /// \param digraph The digraph. /// \retval cutMap A writable arc map. The values will be set to \c true /// for the cut arcs (exactly once for each cut arc), and will not be /// changed for other arcs. /// \return The number of cut arcs. /// /// \see stronglyConnected(), stronglyConnectedComponents() template int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) { int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) { checkConcept(); typedef typename Digraph::Node Node; typedef typename Container::iterator Iterator; Container nodes(countNodes(graph)); Container nodes(countNodes(digraph)); typedef LeaveOrderVisitor Visitor; Visitor visitor(nodes.begin()); DfsVisit dfs(graph, visitor); DfsVisit dfs(digraph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); typedef ReverseDigraph RDigraph; RDigraph rgraph(graph); RDigraph rdigraph(digraph); int cutNum = 0; typedef StronglyConnectedCutArcsVisitor RVisitor; RVisitor rvisitor(rgraph, cutMap, cutNum); DfsVisit rdfs(rgraph, rvisitor); RVisitor rvisitor(rdigraph, cutMap, cutNum); DfsVisit rdfs(rdigraph, rvisitor); rdfs.init(); /// \ingroup graph_properties /// /// \brief Checks the graph is bi-node-connected. /// /// This function checks that the undirected graph is bi-node-connected /// graph. The graph is bi-node-connected if any two undirected edge is /// on same circle. /// /// \param graph The graph. /// \return \c true when the graph bi-node-connected. /// \brief Check whether an undirected graph is bi-node-connected. /// /// This function checks whether the given undirected graph is /// bi-node-connected, i.e. any two edges are on same circle. /// /// \return \c true if the graph bi-node-connected. /// \note By definition, the empty graph is bi-node-connected. /// /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() template bool biNodeConnected(const Graph& graph) { /// \ingroup graph_properties /// /// \brief Count the biconnected components. /// /// This function finds the bi-node-connected components in an undirected /// graph. The biconnected components are the classes of an equivalence /// relation on the undirected edges. Two undirected edge is in relationship /// when they are on same circle. /// /// \param graph The graph. /// \return The number of components. /// \brief Count the number of bi-node-connected components of an /// undirected graph. /// /// This function counts the number of bi-node-connected components of /// the given undirected graph. /// /// The bi-node-connected components are the classes of an equivalence /// relation on the edges of a undirected graph. Two edges are in the /// same class if they are on same circle. /// /// \return The number of bi-node-connected components. /// /// \see biNodeConnected(), biNodeConnectedComponents() template int countBiNodeConnectedComponents(const Graph& graph) { /// \ingroup graph_properties /// /// \brief Find the bi-node-connected components. /// /// This function finds the bi-node-connected components in an undirected /// graph. The bi-node-connected components are the classes of an equivalence /// relation on the undirected edges. Two undirected edge are in relationship /// when they are on same circle. /// \brief Find the bi-node-connected components of an undirected graph. /// /// This function finds the bi-node-connected components of the given /// undirected graph. /// /// The bi-node-connected components are the classes of an equivalence /// relation on the edges of a undirected graph. Two edges are in the /// same class if they are on same circle. /// /// \image html node_biconnected_components.png /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth /// /// \param graph The graph. /// \retval compMap A writable uedge map. The values will be set from 0 /// to the number of the biconnected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components. /// \param graph The undirected graph. /// \retval compMap A writable edge map. The values will be set from 0 /// to the number of the bi-node-connected components minus one. Each /// value of the map will be set exactly once, and the values of a /// certain component will be set continuously. /// \return The number of bi-node-connected components. /// /// \see biNodeConnected(), countBiNodeConnectedComponents() template int biNodeConnectedComponents(const Graph& graph, /// \ingroup graph_properties /// /// \brief Find the bi-node-connected cut nodes. /// /// This function finds the bi-node-connected cut nodes in an undirected /// graph. The bi-node-connected components are the classes of an equivalence /// relation on the undirected edges. Two undirected edges are in /// relationship when they are on same circle. The biconnected components /// are separted by nodes which are the cut nodes of the components. /// /// \param graph The graph. /// \retval cutMap A writable edge map. The values will be set true when /// the node separate two or more components. /// \brief Find the bi-node-connected cut nodes in an undirected graph. /// /// This function finds the bi-node-connected cut nodes in the given /// undirected graph. /// /// The bi-node-connected components are the classes of an equivalence /// relation on the edges of a undirected graph. Two edges are in the /// same class if they are on same circle. /// The bi-node-connected components are separted by the cut nodes of /// the components. /// /// \param graph The undirected graph. /// \retval cutMap A writable node map. The values will be set to /// \c true for the nodes that separate two or more components /// (exactly once for each cut node), and will not be changed for /// other nodes. /// \return The number of the cut nodes. /// /// \see biNodeConnected(), biNodeConnectedComponents() template int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) { /// \ingroup graph_properties /// /// \brief Checks that the graph is bi-edge-connected. /// /// This function checks that the graph is bi-edge-connected. The undirected /// graph is bi-edge-connected when any two nodes are connected with two /// edge-disjoint paths. /// /// \param graph The undirected graph. /// \return The number of components. /// \brief Check whether an undirected graph is bi-edge-connected. /// /// This function checks whether the given undirected graph is /// bi-edge-connected, i.e. any two nodes are connected with at least /// two edge-disjoint paths. /// /// \return \c true if the graph is bi-edge-connected. /// \note By definition, the empty graph is bi-edge-connected. /// /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents() template bool biEdgeConnected(const Graph& graph) { /// \ingroup graph_properties /// /// \brief Count the bi-edge-connected components. /// /// This function count the bi-edge-connected components in an undirected /// graph. The bi-edge-connected components are the classes of an equivalence /// relation on the nodes. Two nodes are in relationship when they are /// connected with at least two edge-disjoint paths. /// /// \param graph The undirected graph. /// \return The number of components. /// \brief Count the number of bi-edge-connected components of an /// undirected graph. /// /// This function counts the number of bi-edge-connected components of /// the given undirected graph. /// /// The bi-edge-connected components are the classes of an equivalence /// relation on the nodes of an undirected graph. Two nodes are in the /// same class if they are connected with at least two edge-disjoint /// paths. /// /// \return The number of bi-edge-connected components. /// /// \see biEdgeConnected(), biEdgeConnectedComponents() template int countBiEdgeConnectedComponents(const Graph& graph) { /// \ingroup graph_properties /// /// \brief Find the bi-edge-connected components. /// /// This function finds the bi-edge-connected components in an undirected /// graph. The bi-edge-connected components are the classes of an equivalence /// relation on the nodes. Two nodes are in relationship when they are /// connected at least two edge-disjoint paths. /// \brief Find the bi-edge-connected components of an undirected graph. /// /// This function finds the bi-edge-connected components of the given /// undirected graph. /// /// The bi-edge-connected components are the classes of an equivalence /// relation on the nodes of an undirected graph. Two nodes are in the /// same class if they are connected with at least two edge-disjoint /// paths. /// /// \image html edge_biconnected_components.png /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth /// /// \param graph The graph. /// \param graph The undirected graph. /// \retval compMap A writable node map. The values will be set from 0 to /// the number of the biconnected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components. /// the number of the bi-edge-connected components minus one. Each value /// of the map will be set exactly once, and the values of a certain /// component will be set continuously. /// \return The number of bi-edge-connected components. /// /// \see biEdgeConnected(), countBiEdgeConnectedComponents() template int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { /// \ingroup graph_properties /// /// \brief Find the bi-edge-connected cut edges. /// /// This function finds the bi-edge-connected components in an undirected /// graph. The bi-edge-connected components are the classes of an equivalence /// relation on the nodes. Two nodes are in relationship when they are /// connected with at least two edge-disjoint paths. The bi-edge-connected /// components are separted by edges which are the cut edges of the /// components. /// /// \param graph The graph. /// \retval cutMap A writable node map. The values will be set true when the /// edge is a cut edge. /// \brief Find the bi-edge-connected cut edges in an undirected graph. /// /// This function finds the bi-edge-connected cut edges in the given /// undirected graph. /// /// The bi-edge-connected components are the classes of an equivalence /// relation on the nodes of an undirected graph. Two nodes are in the /// same class if they are connected with at least two edge-disjoint /// paths. /// The bi-edge-connected components are separted by the cut edges of /// the components. /// /// \param graph The undirected graph. /// \retval cutMap A writable edge map. The values will be set to \c true /// for the cut edges (exactly once for each cut edge), and will not be /// changed for other edges. /// \return The number of cut edges. /// /// \see biEdgeConnected(), biEdgeConnectedComponents() template int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { /// \ingroup graph_properties /// /// \brief Sort the nodes of a DAG into topolgical order. /// /// Sort the nodes of a DAG into topolgical order. /// /// \param graph The graph. It must be directed and acyclic. /// \retval order A writable node map. The values will be set from 0 to /// the number of the nodes in the graph minus one. Each values of the map /// will be set exactly once, the values  will be set descending order. /// /// \see checkedTopologicalSort /// \see dag template void topologicalSort(const Digraph& graph, NodeMap& order) { using namespace _connectivity_bits; /// \brief Check whether a digraph is DAG. /// /// This function checks whether the given digraph is DAG, i.e. /// \e Directed \e Acyclic \e Graph. /// \return \c true if there is no directed cycle in the digraph. /// \see acyclic() template bool dag(const Digraph& digraph) { checkConcept(); checkConcept, NodeMap>(); typedef typename Digraph::Node Node; typedef typename Digraph::Arc Arc; typedef typename Digraph::template NodeMap ProcessedMap; typename Dfs::template SetProcessedMap:: Create dfs(digraph); ProcessedMap processed(digraph); dfs.processedMap(processed); dfs.init(); for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); while (!dfs.emptyQueue()) { Arc arc = dfs.nextArc(); Node target = digraph.target(arc); if (dfs.reached(target) && !processed[target]) { return false; } dfs.processNextArc(); } } } return true; } /// \ingroup graph_properties /// /// \brief Sort the nodes of a DAG into topolgical order. /// /// This function sorts the nodes of the given acyclic digraph (DAG) /// into topolgical order. /// /// \param digraph The digraph, which must be DAG. /// \retval order A writable node map. The values will be set from 0 to /// the number of the nodes in the digraph minus one. Each value of the /// map will be set exactly once, and the values will be set descending /// order. /// /// \see dag(), checkedTopologicalSort() template void topologicalSort(const Digraph& digraph, NodeMap& order) { using namespace _connectivity_bits; checkConcept(); checkConcept, NodeMap>(); typedef typename Digraph::Node Node; typedef typename Digraph::NodeIt NodeIt; typedef typename Digraph::Arc Arc; TopologicalSortVisitor visitor(order, countNodes(graph)); visitor(order, countNodes(digraph)); DfsVisit > dfs(graph, visitor); dfs(digraph, visitor); dfs.init(); for (NodeIt it(graph); it != INVALID; ++it) { for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); /// \brief Sort the nodes of a DAG into topolgical order. /// /// Sort the nodes of a DAG into topolgical order. It also checks /// that the given graph is DAG. /// /// \param digraph The graph. It must be directed and acyclic. /// \retval order A readable - writable node map. The values will be set /// from 0 to the number of the nodes in the graph minus one. Each values /// of the map will be set exactly once, the values will be set descending /// order. /// \return \c false when the graph is not DAG. /// /// \see topologicalSort /// \see dag /// This function sorts the nodes of the given acyclic digraph (DAG) /// into topolgical order and also checks whether the given digraph /// is DAG. /// /// \param digraph The digraph. /// \retval order A readable and writable node map. The values will be /// set from 0 to the number of the nodes in the digraph minus one. /// Each value of the map will be set exactly once, and the values will /// be set descending order. /// \return \c false if the digraph is not DAG. /// /// \see dag(), topologicalSort() template bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { /// \ingroup graph_properties /// /// \brief Check that the given directed graph is a DAG. /// /// Check that the given directed graph is a DAG. The DAG is /// an Directed Acyclic Digraph. /// \return \c false when the graph is not DAG. /// \see acyclic template bool dag(const Digraph& digraph) { checkConcept(); typedef typename Digraph::Node Node; typedef typename Digraph::NodeIt NodeIt; typedef typename Digraph::Arc Arc; typedef typename Digraph::template NodeMap ProcessedMap; typename Dfs::template SetProcessedMap:: Create dfs(digraph); ProcessedMap processed(digraph); dfs.processedMap(processed); dfs.init(); for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); while (!dfs.emptyQueue()) { Arc edge = dfs.nextArc(); Node target = digraph.target(edge); if (dfs.reached(target) && !processed[target]) { return false; } dfs.processNextArc(); } } } return true; } /// \ingroup graph_properties /// /// \brief Check that the given undirected graph is acyclic. /// /// Check that the given undirected graph acyclic. /// \param graph The undirected graph. /// \return \c true when there is no circle in the graph. /// \see dag /// \brief Check whether an undirected graph is acyclic. /// /// This function checks whether the given undirected graph is acyclic. /// \return \c true if there is no cycle in the graph. /// \see dag() template bool acyclic(const Graph& graph) { dfs.addSource(it); while (!dfs.emptyQueue()) { Arc edge = dfs.nextArc(); Node source = graph.source(edge); Node target = graph.target(edge); Arc arc = dfs.nextArc(); Node source = graph.source(arc); Node target = graph.target(arc); if (dfs.reached(target) && dfs.predArc(source) != graph.oppositeArc(edge)) { dfs.predArc(source) != graph.oppositeArc(arc)) { return false; } /// \ingroup graph_properties /// /// \brief Check that the given undirected graph is tree. /// /// Check that the given undirected graph is tree. /// \param graph The undirected graph. /// \return \c true when the graph is acyclic and connected. /// \brief Check whether an undirected graph is tree. /// /// This function checks whether the given undirected graph is tree. /// \return \c true if the graph is acyclic and connected. /// \see acyclic(), connected() template bool tree(const Graph& graph) { typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Arc Arc; if (NodeIt(graph) == INVALID) return true; Dfs dfs(graph); dfs.init(); dfs.addSource(NodeIt(graph)); while (!dfs.emptyQueue()) { Arc edge = dfs.nextArc(); Node source = graph.source(edge); Node target = graph.target(edge); Arc arc = dfs.nextArc(); Node source = graph.source(arc); Node target = graph.target(arc); if (dfs.reached(target) && dfs.predArc(source) != graph.oppositeArc(edge)) { dfs.predArc(source) != graph.oppositeArc(arc)) { return false; } /// \ingroup graph_properties /// /// \brief Check if the given undirected graph is bipartite or not /// /// The function checks if the given undirected \c graph graph is bipartite /// or not. The \ref Bfs algorithm is used to calculate the result. /// \param graph The undirected graph. /// \return \c true if \c graph is bipartite, \c false otherwise. /// \sa bipartitePartitions /// \brief Check whether an undirected graph is bipartite. /// /// The function checks whether the given undirected graph is bipartite. /// \return \c true if the graph is bipartite. /// /// \see bipartitePartitions() template inline bool bipartite(const Graph &graph){ bool bipartite(const Graph &graph){ using namespace _connectivity_bits; /// \ingroup graph_properties /// /// \brief Check if the given undirected graph is bipartite or not /// /// The function checks if the given undirected graph is bipartite /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result. /// During the execution, the \c partMap will be set as the two /// partitions of the graph. /// \brief Find the bipartite partitions of an undirected graph. /// /// This function checks whether the given undirected graph is bipartite /// and gives back the bipartite partitions. /// /// \image html bipartite_partitions.png /// /// \param graph The undirected graph. /// \retval partMap A writable bool map of nodes. It will be set as the /// two partitions of the graph. /// \return \c true if \c graph is bipartite, \c false otherwise. /// \retval partMap A writable node map of \c bool (or convertible) value /// type. The values will be set to \c true for one component and /// \c false for the other one. /// \return \c true if the graph is bipartite, \c false otherwise. /// /// \see bipartite() template inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ using namespace _connectivity_bits; checkConcept(); checkConcept, NodeMap>(); typedef typename Graph::Node Node; } /// \brief Returns true when there are not loop edges in the graph. /// /// Returns true when there are not loop edges in the graph. template bool loopFree(const Digraph& digraph) { for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) { if (digraph.source(it) == digraph.target(it)) return false; /// \ingroup graph_properties /// /// \brief Check whether the given graph contains no loop arcs/edges. /// /// This function returns \c true if there are no loop arcs/edges in /// the given graph. It works for both directed and undirected graphs. template bool loopFree(const Graph& graph) { for (typename Graph::ArcIt it(graph); it != INVALID; ++it) { if (graph.source(it) == graph.target(it)) return false; } return true; } /// \brief Returns true when there are not parallel edges in the graph. /// /// Returns true when there are not parallel edges in the graph. template bool parallelFree(const Digraph& digraph) { typename Digraph::template NodeMap reached(digraph, false); for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { if (reached[digraph.target(a)]) return false; reached.set(digraph.target(a), true); } for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { reached.set(digraph.target(a), false); } /// \ingroup graph_properties /// /// \brief Check whether the given graph contains no parallel arcs/edges. /// /// This function returns \c true if there are no parallel arcs/edges in /// the given graph. It works for both directed and undirected graphs. template bool parallelFree(const Graph& graph) { typename Graph::template NodeMap reached(graph, 0); int cnt = 1; for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { if (reached[graph.target(a)] == cnt) return false; reached[graph.target(a)] = cnt; } ++cnt; } return true; } /// \brief Returns true when there are not loop edges and parallel /// edges in the graph. /// /// Returns true when there are not loop edges and parallel edges in /// the graph. template bool simpleDigraph(const Digraph& digraph) { typename Digraph::template NodeMap reached(digraph, false); for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { reached.set(n, true); for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { if (reached[digraph.target(a)]) return false; reached.set(digraph.target(a), true); } for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { reached.set(digraph.target(a), false); } reached.set(n, false); /// \ingroup graph_properties /// /// \brief Check whether the given graph is simple. /// /// This function returns \c true if the given graph is simple, i.e. /// it contains no loop arcs/edges and no parallel arcs/edges. /// The function works for both directed and undirected graphs. /// \see loopFree(), parallelFree() template bool simpleGraph(const Graph& graph) { typename Graph::template NodeMap reached(graph, 0); int cnt = 1; for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { reached[n] = cnt; for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { if (reached[graph.target(a)] == cnt) return false; reached[graph.target(a)] = cnt; } ++cnt; } return true;
• ## lemon/euler.h

 r639 ///Check if the given graph is \e Eulerian ///Check if the given graph is Eulerian /// \ingroup graph_properties ///This function checks if the given graph is \e Eulerian. ///This function checks if the given graph is Eulerian. ///It works for both directed and undirected graphs. ///
• ## lemon/matching.h

 r641 /// This function runs the original Edmonds' algorithm. /// /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be /// called before using this function. void startSparse() { /// shrinks, therefore resulting in a faster algorithm for dense graphs. /// /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be /// called before using this function. void startDense() {
• ## test/CMakeLists.txt

 r674 bfs_test circulation_test connectivity_test counter_test dfs_test
• ## test/Makefile.am

 r658 test/bfs_test \ test/circulation_test \ test/connectivity_test \ test/counter_test \ test/dfs_test \ test_circulation_test_SOURCES = test/circulation_test.cc test_counter_test_SOURCES = test/counter_test.cc test_connectivity_test_SOURCES = test/connectivity_test.cc test_dfs_test_SOURCES = test/dfs_test.cc test_digraph_test_SOURCES = test/digraph_test.cc
Note: See TracChangeset for help on using the changeset viewer.