Changeset 1767:58455e2aa13e in lemon-0.x
- Timestamp:
- 11/04/05 16:52:24 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2299
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/topology.h
r1763 r1767 697 697 /// \ingroup topology 698 698 /// 699 /// \brief Checks the graph is node biconnected.700 /// 701 /// This function checks that the undirected graph is node biconnected702 /// graph. The graph is node biconnected if any two undirected edge is699 /// \brief Checks the graph is bi-node-connected. 700 /// 701 /// This function checks that the undirected graph is bi-node-connected 702 /// graph. The graph is bi-node-connected if any two undirected edge is 703 703 /// on same circle. 704 704 /// 705 705 /// \param graph The graph. 706 /// \return %True when the graph node biconnected.706 /// \return %True when the graph bi-node-connected. 707 707 /// \todo Make it faster. 708 708 template <typename UndirGraph> 709 bool nodeBiconnected(const UndirGraph& graph) {709 bool biNodeConnected(const UndirGraph& graph) { 710 710 return countNodeBiconnectedComponents(graph) == 1; 711 711 } … … 715 715 /// \brief Count the biconnected components. 716 716 /// 717 /// This function finds the node biconnected components in an undirected717 /// This function finds the bi-node-connected components in an undirected 718 718 /// graph. The biconnected components are the classes of an equivalence 719 719 /// relation on the undirected edges. Two undirected edge is in relationship … … 748 748 /// \ingroup topology 749 749 /// 750 /// \brief Find the node biconnected components.751 /// 752 /// This function finds the node biconnected components in an undirected753 /// graph. The node biconnected components are the classes of an equivalence750 /// \brief Find the bi-node-connected components. 751 /// 752 /// This function finds the bi-node-connected components in an undirected 753 /// graph. The bi-node-connected components are the classes of an equivalence 754 754 /// relation on the undirected edges. Two undirected edge are in relationship 755 755 /// when they are on same circle. 756 756 /// 757 757 /// \image html node_biconnected_components.png 758 /// \image latex node_biconnected_components.eps " Node biconnected components" width=\textwidth758 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth 759 759 /// 760 760 /// \param graph The graph. … … 766 766 /// 767 767 template <typename UndirGraph, typename UndirEdgeMap> 768 int nodeBiconnectedComponents(const UndirGraph& graph,768 int biNodeConnectedComponents(const UndirGraph& graph, 769 769 UndirEdgeMap& compMap) { 770 770 checkConcept<concept::UndirGraph, UndirGraph>(); … … 794 794 /// \ingroup topology 795 795 /// 796 /// \brief Find the node biconnected cut nodes.797 /// 798 /// This function finds the node biconnected cut nodes in an undirected799 /// graph. The node biconnected components are the classes of an equivalence796 /// \brief Find the bi-node-connected cut nodes. 797 /// 798 /// This function finds the bi-node-connected cut nodes in an undirected 799 /// graph. The bi-node-connected components are the classes of an equivalence 800 800 /// relation on the undirected edges. Two undirected edges are in 801 801 /// relationship when they are on same circle. The biconnected components … … 807 807 /// \return The number of the cut nodes. 808 808 template <typename UndirGraph, typename NodeMap> 809 int nodeBiconnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {809 int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) { 810 810 checkConcept<concept::UndirGraph, UndirGraph>(); 811 811 typedef typename UndirGraph::Node Node; … … 1024 1024 /// \ingroup topology 1025 1025 /// 1026 /// \brief Checks that the graph is edge biconnected.1027 /// 1028 /// This function checks that the graph is edge biconnected. The undirected1029 /// graph is edge biconnected when any two nodes are connected with two1026 /// \brief Checks that the graph is bi-edge-connected. 1027 /// 1028 /// This function checks that the graph is bi-edge-connected. The undirected 1029 /// graph is bi-edge-connected when any two nodes are connected with two 1030 1030 /// edge-disjoint paths. 1031 1031 /// … … 1034 1034 /// \todo Make it faster. 1035 1035 template <typename UndirGraph> 1036 bool edgeBiconnected(const UndirGraph& graph) {1036 bool biEdgeConnected(const UndirGraph& graph) { 1037 1037 return countEdgeBiconnectedComponents(graph) == 1; 1038 1038 } … … 1040 1040 /// \ingroup topology 1041 1041 /// 1042 /// \brief Count the edge biconnected components.1043 /// 1044 /// This function count the edge biconnected components in an undirected1045 /// graph. The edge biconnected components are the classes of an equivalence1042 /// \brief Count the bi-edge-connected components. 1043 /// 1044 /// This function count the bi-edge-connected components in an undirected 1045 /// graph. The bi-edge-connected components are the classes of an equivalence 1046 1046 /// relation on the nodes. Two nodes are in relationship when they are 1047 1047 /// connected with at least two edge-disjoint paths. … … 1075 1075 /// \ingroup topology 1076 1076 /// 1077 /// \brief Find the edge biconnected components.1078 /// 1079 /// This function finds the edge biconnected components in an undirected1080 /// graph. The edge biconnected components are the classes of an equivalence1077 /// \brief Find the bi-edge-connected components. 1078 /// 1079 /// This function finds the bi-edge-connected components in an undirected 1080 /// graph. The bi-edge-connected components are the classes of an equivalence 1081 1081 /// relation on the nodes. Two nodes are in relationship when they are 1082 1082 /// connected at least two edge-disjoint paths. 1083 1083 /// 1084 1084 /// \image html edge_biconnected_components.png 1085 /// \image latex edge_biconnected_components.eps " Edge biconnected components" width=\textwidth1085 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 1086 1086 /// 1087 1087 /// \param graph The graph. … … 1093 1093 /// 1094 1094 template <typename UndirGraph, typename NodeMap> 1095 int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) {1095 int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) { 1096 1096 checkConcept<concept::UndirGraph, UndirGraph>(); 1097 1097 typedef typename UndirGraph::NodeIt NodeIt; … … 1120 1120 /// \ingroup topology 1121 1121 /// 1122 /// \brief Find the edge biconnected cut edges.1123 /// 1124 /// This function finds the edge biconnected components in an undirected1125 /// graph. The edge biconnected components are the classes of an equivalence1122 /// \brief Find the bi-edge-connected cut edges. 1123 /// 1124 /// This function finds the bi-edge-connected components in an undirected 1125 /// graph. The bi-edge-connected components are the classes of an equivalence 1126 1126 /// relation on the nodes. Two nodes are in relationship when they are 1127 /// connected with at least two edge-disjoint paths. The edge biconnected1127 /// connected with at least two edge-disjoint paths. The bi-edge-connected 1128 1128 /// components are separted by edges which are the cut edges of the 1129 1129 /// components. … … 1134 1134 /// \return The number of cut edges. 1135 1135 template <typename UndirGraph, typename UndirEdgeMap> 1136 int edgeBiconnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) {1136 int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { 1137 1137 checkConcept<concept::UndirGraph, UndirGraph>(); 1138 1138 typedef typename UndirGraph::NodeIt NodeIt;
Note: See TracChangeset
for help on using the changeset viewer.