Index: lemon/connectivity.h
===================================================================
 lemon/connectivity.h (revision 648)
+++ lemon/connectivity.h (revision 586)
@@ 43,14 +43,10 @@
/// \ingroup graph_properties
///
 /// \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.
+ /// \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.
/// \note By definition, the empty graph is connected.
 ///
 /// \see countConnectedComponents(), connectedComponents()
 /// \see stronglyConnected()
template
bool connected(const Graph& graph) {
@@ 72,16 +68,10 @@
/// \brief Count the number of connected components of an undirected graph
///
 /// 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.
+ /// Count the number of connected components of an undirected graph
+ ///
+ /// \param graph The graph. It must be undirected.
+ /// \return The number of components
/// \note By definition, the empty graph consists
/// of zero connected components.
 ///
 /// \see connected(), connectedComponents()
template
int countConnectedComponents(const Graph &graph) {
@@ 120,24 +110,15 @@
/// \brief 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.
+ /// Find the connected components of an undirected graph.
///
/// \image html connected_components.png
/// \image latex connected_components.eps "Connected components" width=\textwidth
///
 /// \param graph The undirected graph.
+ /// \param graph The graph. It must be undirected.
/// \retval compMap A writable node map. The values will be set from 0 to
 /// 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
+ /// 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
/// set continuously.
 /// \return The number of connected components.
 /// \note By definition, the empty graph consists
 /// of zero connected components.
 ///
 /// \see connected(), countConnectedComponents()
+ /// \return The number of components
template
int connectedComponents(const Graph &graph, NodeMap &compMap) {
@@ 251,15 +232,13 @@
/// \ingroup graph_properties
///
 /// \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
+ /// \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
/// connected with directed paths in both direction.
 ///
 /// \return \c true if the digraph is strongly connected.
 /// \note By definition, the empty digraph is strongly connected.
 ///
 /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
 /// \see connected()
+ /// \return \c false when the graph is not strongly connected.
+ /// \see connected
+ ///
+ /// \note By definition, the empty graph is strongly connected.
template
bool stronglyConnected(const Digraph& digraph) {
@@ 292,5 +271,5 @@
RDigraph rdigraph(digraph);
 typedef DfsVisitor RVisitor;
+ typedef DfsVisitor RVisitor;
RVisitor rvisitor;
@@ 311,20 +290,16 @@
/// \ingroup graph_properties
///
 /// \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.
 ///
+ /// \brief Count the strongly connected components of a directed graph
+ ///
+ /// Count the strongly connected components of a directed graph.
/// The strongly connected components are the classes of an
 /// equivalence relation on the nodes of a digraph. Two nodes are in
+ /// equivalence relation on the nodes of the graph. Two nodes are in
/// the same class if they are connected with directed paths in both
/// direction.
///
 /// \return The number of strongly connected components.
 /// \note By definition, the empty digraph has zero
+ /// \param digraph The graph.
+ /// \return The number of components
+ /// \note By definition, the empty graph has zero
/// strongly connected components.
 ///
 /// \see stronglyConnected(), stronglyConnectedComponents()
template
int countStronglyConnectedComponents(const Digraph& digraph) {
@@ 381,13 +356,11 @@
/// \brief Find the strongly connected components of a directed graph
///
 /// 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.
+ /// 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.
///
/// \image html strongly_connected_components.png
@@ 397,11 +370,7 @@
/// \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, 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()
+ /// of the map will be set exactly once, the values of a certain component
+ /// will be set continuously.
+ /// \return The number of components
template
int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
@@ 456,22 +425,17 @@
/// \brief Find the cut arcs of the strongly connected components.
///
 /// 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.
+ /// 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.
/// The strongly connected components are separated by the 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()
+ /// \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
template
 int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
+ int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
checkConcept();
typedef typename Digraph::Node Node;
@@ 485,11 +449,11 @@
typedef typename Container::iterator Iterator;
 Container nodes(countNodes(digraph));
+ Container nodes(countNodes(graph));
typedef LeaveOrderVisitor Visitor;
Visitor visitor(nodes.begin());
 DfsVisit dfs(digraph, visitor);
+ DfsVisit dfs(graph, visitor);
dfs.init();
 for (NodeIt it(digraph); it != INVALID; ++it) {
+ for (NodeIt it(graph); it != INVALID; ++it) {
if (!dfs.reached(it)) {
dfs.addSource(it);
@@ 501,12 +465,12 @@
typedef ReverseDigraph RDigraph;
 RDigraph rdigraph(digraph);
+ RDigraph rgraph(graph);
int cutNum = 0;
typedef StronglyConnectedCutArcsVisitor RVisitor;
 RVisitor rvisitor(rdigraph, cutMap, cutNum);

 DfsVisit rdfs(rdigraph, rvisitor);
+ RVisitor rvisitor(rgraph, cutMap, cutNum);
+
+ DfsVisit rdfs(rgraph, rvisitor);
rdfs.init();
@@ 743,13 +707,12 @@
/// \ingroup graph_properties
///
 /// \brief Check whether an undirected graph is binodeconnected.
 ///
 /// This function checks whether the given undirected graph is
 /// binodeconnected, i.e. any two edges are on same circle.
 ///
 /// \return \c true if the graph binodeconnected.
 /// \note By definition, the empty graph is binodeconnected.
 ///
 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
+ /// \brief Checks the graph is binodeconnected.
+ ///
+ /// This function checks that the undirected graph is binodeconnected
+ /// graph. The graph is binodeconnected if any two undirected edge is
+ /// on same circle.
+ ///
+ /// \param graph The graph.
+ /// \return \c true when the graph binodeconnected.
template
bool biNodeConnected(const Graph& graph) {
@@ 759,17 +722,13 @@
/// \ingroup graph_properties
///
 /// \brief Count the number of binodeconnected components of an
 /// undirected graph.
 ///
 /// This function counts the number of binodeconnected components of
 /// the given undirected graph.
 ///
 /// The binodeconnected 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 binodeconnected components.
 ///
 /// \see biNodeConnected(), biNodeConnectedComponents()
+ /// \brief Count the biconnected components.
+ ///
+ /// This function finds the binodeconnected 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.
template
int countBiNodeConnectedComponents(const Graph& graph) {
@@ 798,24 +757,20 @@
/// \ingroup graph_properties
///
 /// \brief Find the binodeconnected components of an undirected graph.
 ///
 /// This function finds the binodeconnected components of the given
 /// undirected graph.
 ///
 /// The binodeconnected 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.
+ /// \brief Find the binodeconnected components.
+ ///
+ /// This function finds the binodeconnected components in an undirected
+ /// graph. The binodeconnected components are the classes of an equivalence
+ /// relation on the undirected edges. Two undirected edge are in relationship
+ /// when they are on same circle.
///
/// \image html node_biconnected_components.png
/// \image latex node_biconnected_components.eps "binodeconnected components" width=\textwidth
///
 /// \param graph The undirected graph.
 /// \retval compMap A writable edge map. The values will be set from 0
 /// to the number of the binodeconnected 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 binodeconnected components.
 ///
 /// \see biNodeConnected(), countBiNodeConnectedComponents()
+ /// \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.
template
int biNodeConnectedComponents(const Graph& graph,
@@ 847,23 +802,16 @@
/// \ingroup graph_properties
///
 /// \brief Find the binodeconnected cut nodes in an undirected graph.
 ///
 /// This function finds the binodeconnected cut nodes in the given
 /// undirected graph.
 ///
 /// The binodeconnected 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 binodeconnected 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.
+ /// \brief Find the binodeconnected cut nodes.
+ ///
+ /// This function finds the binodeconnected cut nodes in an undirected
+ /// graph. The binodeconnected 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.
/// \return The number of the cut nodes.
 ///
 /// \see biNodeConnected(), biNodeConnectedComponents()
template
int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
@@ 1084,14 +1032,12 @@
/// \ingroup graph_properties
///
 /// \brief Check whether an undirected graph is biedgeconnected.
 ///
 /// This function checks whether the given undirected graph is
 /// biedgeconnected, i.e. any two nodes are connected with at least
 /// two edgedisjoint paths.
 ///
 /// \return \c true if the graph is biedgeconnected.
 /// \note By definition, the empty graph is biedgeconnected.
 ///
 /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
+ /// \brief Checks that the graph is biedgeconnected.
+ ///
+ /// This function checks that the graph is biedgeconnected. The undirected
+ /// graph is biedgeconnected when any two nodes are connected with two
+ /// edgedisjoint paths.
+ ///
+ /// \param graph The undirected graph.
+ /// \return The number of components.
template
bool biEdgeConnected(const Graph& graph) {
@@ 1101,18 +1047,13 @@
/// \ingroup graph_properties
///
 /// \brief Count the number of biedgeconnected components of an
 /// undirected graph.
 ///
 /// This function counts the number of biedgeconnected components of
 /// the given undirected graph.
 ///
 /// The biedgeconnected 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 edgedisjoint
 /// paths.
 ///
 /// \return The number of biedgeconnected components.
 ///
 /// \see biEdgeConnected(), biEdgeConnectedComponents()
+ /// \brief Count the biedgeconnected components.
+ ///
+ /// This function count the biedgeconnected components in an undirected
+ /// graph. The biedgeconnected components are the classes of an equivalence
+ /// relation on the nodes. Two nodes are in relationship when they are
+ /// connected with at least two edgedisjoint paths.
+ ///
+ /// \param graph The undirected graph.
+ /// \return The number of components.
template
int countBiEdgeConnectedComponents(const Graph& graph) {
@@ 1141,25 +1082,20 @@
/// \ingroup graph_properties
///
 /// \brief Find the biedgeconnected components of an undirected graph.
 ///
 /// This function finds the biedgeconnected components of the given
 /// undirected graph.
 ///
 /// The biedgeconnected 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 edgedisjoint
 /// paths.
+ /// \brief Find the biedgeconnected components.
+ ///
+ /// This function finds the biedgeconnected components in an undirected
+ /// graph. The biedgeconnected components are the classes of an equivalence
+ /// relation on the nodes. Two nodes are in relationship when they are
+ /// connected at least two edgedisjoint paths.
///
/// \image html edge_biconnected_components.png
/// \image latex edge_biconnected_components.eps "biedgeconnected components" width=\textwidth
///
 /// \param graph The undirected graph.
+ /// \param graph The graph.
/// \retval compMap A writable node map. The values will be set from 0 to
 /// the number of the biedgeconnected 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 biedgeconnected components.
 ///
 /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
+ /// 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.
template
int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
@@ 1190,23 +1126,17 @@
/// \ingroup graph_properties
///
 /// \brief Find the biedgeconnected cut edges in an undirected graph.
 ///
 /// This function finds the biedgeconnected cut edges in the given
 /// undirected graph.
 ///
 /// The biedgeconnected 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 edgedisjoint
 /// paths.
 /// The biedgeconnected 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.
+ /// \brief Find the biedgeconnected cut edges.
+ ///
+ /// This function finds the biedgeconnected components in an undirected
+ /// graph. The biedgeconnected components are the classes of an equivalence
+ /// relation on the nodes. Two nodes are in relationship when they are
+ /// connected with at least two edgedisjoint paths. The biedgeconnected
+ /// 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.
/// \return The number of cut edges.
 ///
 /// \see biEdgeConnected(), biEdgeConnectedComponents()
template
int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
@@ 1260,14 +1190,21 @@
/// \ingroup graph_properties
///
 /// \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) {
+ /// \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;
checkConcept();
+ checkConcept, NodeMap>();
typedef typename Digraph::Node Node;
@@ 1275,62 +1212,12 @@
typedef typename Digraph::Arc Arc;
 typedef typename Digraph::template NodeMap ProcessedMap;

 typename Dfs::template SetProcessedMap::
 Create dfs(digraph);

 ProcessedMap processed(digraph);
 dfs.processedMap(processed);
+ TopologicalSortVisitor
+ visitor(order, countNodes(graph));
+
+ DfsVisit >
+ dfs(graph, visitor);
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(digraph));

 DfsVisit >
 dfs(digraph, visitor);

 dfs.init();
 for (NodeIt it(digraph); it != INVALID; ++it) {
+ for (NodeIt it(graph); it != INVALID; ++it) {
if (!dfs.reached(it)) {
dfs.addSource(it);
@@ 1344,16 +1231,16 @@
/// \brief Sort the nodes of a DAG into topolgical order.
///
 /// 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()
+ /// 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
template
bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
@@ 1397,9 +1284,52 @@
/// \ingroup graph_properties
///
 /// \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()
+ /// \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
template
bool acyclic(const Graph& graph) {
@@ 1414,9 +1344,9 @@
dfs.addSource(it);
while (!dfs.emptyQueue()) {
 Arc arc = dfs.nextArc();
 Node source = graph.source(arc);
 Node target = graph.target(arc);
+ Arc edge = dfs.nextArc();
+ Node source = graph.source(edge);
+ Node target = graph.target(edge);
if (dfs.reached(target) &&
 dfs.predArc(source) != graph.oppositeArc(arc)) {
+ dfs.predArc(source) != graph.oppositeArc(edge)) {
return false;
}
@@ 1430,9 +1360,9 @@
/// \ingroup graph_properties
///
 /// \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()
+ /// \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.
template
bool tree(const Graph& graph) {
@@ 1441,14 +1371,13 @@
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 arc = dfs.nextArc();
 Node source = graph.source(arc);
 Node target = graph.target(arc);
+ Arc edge = dfs.nextArc();
+ Node source = graph.source(edge);
+ Node target = graph.target(edge);
if (dfs.reached(target) &&
 dfs.predArc(source) != graph.oppositeArc(arc)) {
+ dfs.predArc(source) != graph.oppositeArc(edge)) {
return false;
}
@@ 1523,12 +1452,13 @@
/// \ingroup graph_properties
///
 /// \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()
+ /// \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
template
 bool bipartite(const Graph &graph){
+ inline bool bipartite(const Graph &graph){
using namespace _connectivity_bits;
@@ 1559,8 +1489,10 @@
/// \ingroup graph_properties
///
 /// \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.
+ /// \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.
///
/// \image html bipartite_partitions.png
@@ 1568,16 +1500,12 @@
///
/// \param graph The undirected graph.
 /// \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()
+ /// \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.
template
 bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
+ inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
using namespace _connectivity_bits;
checkConcept();
 checkConcept, NodeMap>();
typedef typename Graph::Node Node;
@@ 1604,57 +1532,51 @@
}
 /// \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;
+ /// \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;
}
return true;
}
 /// \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;
+ /// \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);
+ }
}
return true;
}
 /// \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;
+ /// \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);
}
return true;
Index: lemon/euler.h
===================================================================
 lemon/euler.h (revision 648)
+++ lemon/euler.h (revision 592)
@@ 245,8 +245,8 @@
 ///Check if the given graph is Eulerian
+ ///Check if the given graph is \e Eulerian
/// \ingroup graph_properties
 ///This function checks if the given graph is Eulerian.
+ ///This function checks if the given graph is \e Eulerian.
///It works for both directed and undirected graphs.
///
Index: lemon/glpk.h
===================================================================
 lemon/glpk.h (revision 576)
+++ lemon/glpk.h (revision 650)
@@ 27,7 +27,8 @@
// forward declaration
#ifndef _GLP_PROB
+#if !defined _GLP_PROB && !defined GLP_PROB
#define _GLP_PROB
typedef struct { double _prob; } glp_prob;
+#define GLP_PROB
+typedef struct { double _opaque_prob; } glp_prob;
/* LP/MIP problem object */
#endif
Index: test/CMakeLists.txt
===================================================================
 test/CMakeLists.txt (revision 649)
+++ test/CMakeLists.txt (revision 627)
@@ 10,5 +10,4 @@
bfs_test
circulation_test
 connectivity_test
counter_test
dfs_test
Index: test/Makefile.am
===================================================================
 test/Makefile.am (revision 649)
+++ test/Makefile.am (revision 611)
@@ 10,5 +10,4 @@
test/bfs_test \
test/circulation_test \
 test/connectivity_test \
test/counter_test \
test/dfs_test \
@@ 56,5 +55,4 @@
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
Index: st/connectivity_test.cc
===================================================================
 test/connectivity_test.cc (revision 649)
+++ (revision )
@@ 1,297 +1,0 @@
/* * mode: C++; indenttabsmode: nil; *
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 20032009
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include
#include
#include

#include "test_tools.h"

using namespace lemon;


int main()
{
 typedef ListDigraph Digraph;
 typedef Undirector Graph;

 {
 Digraph d;
 Digraph::NodeMap order(d);
 Graph g(d);

 check(stronglyConnected(d), "The empty digraph is strongly connected");
 check(countStronglyConnectedComponents(d) == 0,
 "The empty digraph has 0 strongly connected component");
 check(connected(g), "The empty graph is connected");
 check(countConnectedComponents(g) == 0,
 "The empty graph has 0 connected component");

 check(biNodeConnected(g), "The empty graph is binodeconnected");
 check(countBiNodeConnectedComponents(g) == 0,
 "The empty graph has 0 binodeconnected component");
 check(biEdgeConnected(g), "The empty graph is biedgeconnected");
 check(countBiEdgeConnectedComponents(g) == 0,
 "The empty graph has 0 biedgeconnected component");

 check(dag(d), "The empty digraph is DAG.");
 check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
 check(loopFree(d), "The empty digraph is loopfree.");
 check(parallelFree(d), "The empty digraph is parallelfree.");
 check(simpleGraph(d), "The empty digraph is simple.");

 check(acyclic(g), "The empty graph is acyclic.");
 check(tree(g), "The empty graph is tree.");
 check(bipartite(g), "The empty graph is bipartite.");
 check(loopFree(g), "The empty graph is loopfree.");
 check(parallelFree(g), "The empty graph is parallelfree.");
 check(simpleGraph(g), "The empty graph is simple.");
 }

 {
 Digraph d;
 Digraph::NodeMap order(d);
 Graph g(d);
 Digraph::Node n = d.addNode();

 check(stronglyConnected(d), "This digraph is strongly connected");
 check(countStronglyConnectedComponents(d) == 1,
 "This digraph has 1 strongly connected component");
 check(connected(g), "This graph is connected");
 check(countConnectedComponents(g) == 1,
 "This graph has 1 connected component");

 check(biNodeConnected(g), "This graph is binodeconnected");
 check(countBiNodeConnectedComponents(g) == 0,
 "This graph has 0 binodeconnected component");
 check(biEdgeConnected(g), "This graph is biedgeconnected");
 check(countBiEdgeConnectedComponents(g) == 1,
 "This graph has 1 biedgeconnected component");

 check(dag(d), "This digraph is DAG.");
 check(checkedTopologicalSort(d, order), "This digraph is DAG.");
 check(loopFree(d), "This digraph is loopfree.");
 check(parallelFree(d), "This digraph is parallelfree.");
 check(simpleGraph(d), "This digraph is simple.");

 check(acyclic(g), "This graph is acyclic.");
 check(tree(g), "This graph is tree.");
 check(bipartite(g), "This graph is bipartite.");
 check(loopFree(g), "This graph is loopfree.");
 check(parallelFree(g), "This graph is parallelfree.");
 check(simpleGraph(g), "This graph is simple.");
 }

 {
 Digraph d;
 Digraph::NodeMap order(d);
 Graph g(d);

 Digraph::Node n1 = d.addNode();
 Digraph::Node n2 = d.addNode();
 Digraph::Node n3 = d.addNode();
 Digraph::Node n4 = d.addNode();
 Digraph::Node n5 = d.addNode();
 Digraph::Node n6 = d.addNode();

 d.addArc(n1, n3);
 d.addArc(n3, n2);
 d.addArc(n2, n1);
 d.addArc(n4, n2);
 d.addArc(n4, n3);
 d.addArc(n5, n6);
 d.addArc(n6, n5);

 check(!stronglyConnected(d), "This digraph is not strongly connected");
 check(countStronglyConnectedComponents(d) == 3,
 "This digraph has 3 strongly connected components");
 check(!connected(g), "This graph is not connected");
 check(countConnectedComponents(g) == 2,
 "This graph has 2 connected components");

 check(!dag(d), "This digraph is not DAG.");
 check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
 check(loopFree(d), "This digraph is loopfree.");
 check(parallelFree(d), "This digraph is parallelfree.");
 check(simpleGraph(d), "This digraph is simple.");

 check(!acyclic(g), "This graph is not acyclic.");
 check(!tree(g), "This graph is not tree.");
 check(!bipartite(g), "This graph is not bipartite.");
 check(loopFree(g), "This graph is loopfree.");
 check(!parallelFree(g), "This graph is not parallelfree.");
 check(!simpleGraph(g), "This graph is not simple.");

 d.addArc(n3, n3);

 check(!loopFree(d), "This digraph is not loopfree.");
 check(!loopFree(g), "This graph is not loopfree.");
 check(!simpleGraph(d), "This digraph is not simple.");

 d.addArc(n3, n2);

 check(!parallelFree(d), "This digraph is not parallelfree.");
 }

 {
 Digraph d;
 Digraph::ArcMap cutarcs(d, false);
 Graph g(d);

 Digraph::Node n1 = d.addNode();
 Digraph::Node n2 = d.addNode();
 Digraph::Node n3 = d.addNode();
 Digraph::Node n4 = d.addNode();
 Digraph::Node n5 = d.addNode();
 Digraph::Node n6 = d.addNode();
 Digraph::Node n7 = d.addNode();
 Digraph::Node n8 = d.addNode();

 d.addArc(n1, n2);
 d.addArc(n5, n1);
 d.addArc(n2, n8);
 d.addArc(n8, n5);
 d.addArc(n6, n4);
 d.addArc(n4, n6);
 d.addArc(n2, n5);
 d.addArc(n1, n8);
 d.addArc(n6, n7);
 d.addArc(n7, n6);

 check(!stronglyConnected(d), "This digraph is not strongly connected");
 check(countStronglyConnectedComponents(d) == 3,
 "This digraph has 3 strongly connected components");
 Digraph::NodeMap scomp1(d);
 check(stronglyConnectedComponents(d, scomp1) == 3,
 "This digraph has 3 strongly connected components");
 check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
 scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
 check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
 scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
 check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
 "Wrong stronglyConnectedComponents()");
 Digraph::ArcMap scut1(d, false);
 check(stronglyConnectedCutArcs(d, scut1) == 0,
 "This digraph has 0 strongly connected cut arc.");
 for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
 }

 check(!connected(g), "This graph is not connected");
 check(countConnectedComponents(g) == 3,
 "This graph has 3 connected components");
 Graph::NodeMap comp(g);
 check(connectedComponents(g, comp) == 3,
 "This graph has 3 connected components");
 check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
 comp[n3] != comp[n4], "Wrong connectedComponents()");
 check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
 comp[n1] == comp[n8], "Wrong connectedComponents()");
 check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
 "Wrong connectedComponents()");

 cutarcs[d.addArc(n3, n1)] = true;
 cutarcs[d.addArc(n3, n5)] = true;
 cutarcs[d.addArc(n3, n8)] = true;
 cutarcs[d.addArc(n8, n6)] = true;
 cutarcs[d.addArc(n8, n7)] = true;

 check(!stronglyConnected(d), "This digraph is not strongly connected");
 check(countStronglyConnectedComponents(d) == 3,
 "This digraph has 3 strongly connected components");
 Digraph::NodeMap scomp2(d);
 check(stronglyConnectedComponents(d, scomp2) == 3,
 "This digraph has 3 strongly connected components");
 check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
 check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
 scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
 check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
 "Wrong stronglyConnectedComponents()");
 Digraph::ArcMap scut2(d, false);
 check(stronglyConnectedCutArcs(d, scut2) == 5,
 "This digraph has 5 strongly connected cut arcs.");
 for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
 }
 }

 {
 // DAG example for topological sort from the book New Algorithms
 // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
 Digraph d;
 Digraph::NodeMap order(d);

 Digraph::Node belt = d.addNode();
 Digraph::Node trousers = d.addNode();
 Digraph::Node necktie = d.addNode();
 Digraph::Node coat = d.addNode();
 Digraph::Node socks = d.addNode();
 Digraph::Node shirt = d.addNode();
 Digraph::Node shoe = d.addNode();
 Digraph::Node watch = d.addNode();
 Digraph::Node pants = d.addNode();

 d.addArc(socks, shoe);
 d.addArc(pants, shoe);
 d.addArc(pants, trousers);
 d.addArc(trousers, shoe);
 d.addArc(trousers, belt);
 d.addArc(belt, coat);
 d.addArc(shirt, belt);
 d.addArc(shirt, necktie);
 d.addArc(necktie, coat);

 check(dag(d), "This digraph is DAG.");
 topologicalSort(d, order);
 for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 check(order[d.source(a)] < order[d.target(a)],
 "Wrong topologicalSort()");
 }
 }

 {
 ListGraph g;
 ListGraph::NodeMap map(g);

 ListGraph::Node n1 = g.addNode();
 ListGraph::Node n2 = g.addNode();
 ListGraph::Node n3 = g.addNode();
 ListGraph::Node n4 = g.addNode();
 ListGraph::Node n5 = g.addNode();
 ListGraph::Node n6 = g.addNode();
 ListGraph::Node n7 = g.addNode();

 g.addEdge(n1, n3);
 g.addEdge(n1, n4);
 g.addEdge(n2, n5);
 g.addEdge(n3, n6);
 g.addEdge(n4, n6);
 g.addEdge(n4, n7);
 g.addEdge(n5, n7);

 check(bipartite(g), "This graph is bipartite");
 check(bipartitePartitions(g, map), "This graph is bipartite");

 check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
 "Wrong bipartitePartitions()");
 check(map[n3] == map[n4] && map[n3] == map[n5],
 "Wrong bipartitePartitions()");
 }

 return 0;
}