# Changeset 1767:58455e2aa13e in lemon-0.x for lemon/topology.h

Ignore:
Timestamp:
11/04/05 16:52:24 (14 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2299
Message:

Changed name

File:
1 edited

Unmodified
Added
Removed
• ## lemon/topology.h

 r1763 /// \ingroup topology /// /// \brief Checks the graph is node biconnected. /// /// This function checks that the undirected graph is node biconnected /// graph. The graph is node biconnected if any two undirected edge is /// \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 %True when the graph node biconnected. /// \return %True when the graph bi-node-connected. /// \todo Make it faster. template bool nodeBiconnected(const UndirGraph& graph) { bool biNodeConnected(const UndirGraph& graph) { return countNodeBiconnectedComponents(graph) == 1; } /// \brief Count the biconnected components. /// /// This function finds the node biconnected components in an undirected /// 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 /// \ingroup topology /// /// \brief Find the node biconnected components. /// /// This function finds the node biconnected components in an undirected /// graph. The node biconnected components are the classes of an equivalence /// \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. /// /// \image html node_biconnected_components.png /// \image latex node_biconnected_components.eps "Node biconnected components" width=\textwidth /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth /// /// \param graph The graph. /// template int nodeBiconnectedComponents(const UndirGraph& graph, int biNodeConnectedComponents(const UndirGraph& graph, UndirEdgeMap& compMap) { checkConcept(); /// \ingroup topology /// /// \brief Find the node biconnected cut nodes. /// /// This function finds the node biconnected cut nodes in an undirected /// graph. The node biconnected components are the classes of an equivalence /// \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 /// \return The number of the cut nodes. template int nodeBiconnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) { int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) { checkConcept(); typedef typename UndirGraph::Node Node; /// \ingroup topology /// /// \brief Checks that the graph is edge biconnected. /// /// This function checks that the graph is edge biconnected. The undirected /// graph is edge biconnected when any two nodes are connected with two /// \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. /// /// \todo Make it faster. template bool edgeBiconnected(const UndirGraph& graph) { bool biEdgeConnected(const UndirGraph& graph) { return countEdgeBiconnectedComponents(graph) == 1; } /// \ingroup topology /// /// \brief Count the edge biconnected components. /// /// This function count the edge biconnected components in an undirected /// graph. The edge biconnected components are the classes of an equivalence /// \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. /// \ingroup topology /// /// \brief Find the edge biconnected components. /// /// This function finds the edge biconnected components in an undirected /// graph. The edge biconnected components are the classes of an equivalence /// \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. /// /// \image html edge_biconnected_components.png /// \image latex edge_biconnected_components.eps "Edge biconnected components" width=\textwidth /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth /// /// \param graph The graph. /// template int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) { int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) { checkConcept(); typedef typename UndirGraph::NodeIt NodeIt; /// \ingroup topology /// /// \brief Find the edge biconnected cut edges. /// /// This function finds the edge biconnected components in an undirected /// graph. The edge biconnected components are the classes of an equivalence /// \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 edge biconnected /// 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. /// \return The number of cut edges. template int edgeBiconnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { checkConcept(); typedef typename UndirGraph::NodeIt NodeIt;
Note: See TracChangeset for help on using the changeset viewer.