1.1 --- a/lemon/topology.h Wed Nov 16 09:08:36 2005 +0000
1.2 +++ b/lemon/topology.h Wed Nov 16 09:10:24 2005 +0000
1.3 @@ -480,13 +480,13 @@
1.4 namespace _topology_bits {
1.5
1.6 template <typename Graph>
1.7 - class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
1.8 + class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
1.9 public:
1.10 typedef typename Graph::Node Node;
1.11 typedef typename Graph::Edge Edge;
1.12 typedef typename Graph::UndirEdge UndirEdge;
1.13
1.14 - CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)
1.15 + CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
1.16 : _graph(graph), _compNum(compNum),
1.17 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.18
1.19 @@ -538,13 +538,13 @@
1.20 };
1.21
1.22 template <typename Graph, typename EdgeMap>
1.23 - class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
1.24 + class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
1.25 public:
1.26 typedef typename Graph::Node Node;
1.27 typedef typename Graph::Edge Edge;
1.28 typedef typename Graph::UndirEdge UndirEdge;
1.29
1.30 - NodeBiconnectedComponentsVisitor(const Graph& graph,
1.31 + BiNodeConnectedComponentsVisitor(const Graph& graph,
1.32 EdgeMap& compMap, int &compNum)
1.33 : _graph(graph), _compMap(compMap), _compNum(compNum),
1.34 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.35 @@ -618,13 +618,13 @@
1.36
1.37
1.38 template <typename Graph, typename NodeMap>
1.39 - class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
1.40 + class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
1.41 public:
1.42 typedef typename Graph::Node Node;
1.43 typedef typename Graph::Edge Edge;
1.44 typedef typename Graph::UndirEdge UndirEdge;
1.45
1.46 - NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
1.47 + BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
1.48 int& cutNum)
1.49 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
1.50 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.51 @@ -696,7 +696,7 @@
1.52 }
1.53
1.54 template <typename UndirGraph>
1.55 - int countNodeBiconnectedComponents(const UndirGraph& graph);
1.56 + int countBiNodeConnectedComponents(const UndirGraph& graph);
1.57
1.58 /// \ingroup topology
1.59 ///
1.60 @@ -711,7 +711,7 @@
1.61 /// \todo Make it faster.
1.62 template <typename UndirGraph>
1.63 bool biNodeConnected(const UndirGraph& graph) {
1.64 - return countNodeBiconnectedComponents(graph) == 1;
1.65 + return countBiNodeConnectedComponents(graph) == 1;
1.66 }
1.67
1.68 /// \ingroup topology
1.69 @@ -726,13 +726,13 @@
1.70 /// \param graph The graph.
1.71 /// \return The number of components.
1.72 template <typename UndirGraph>
1.73 - int countNodeBiconnectedComponents(const UndirGraph& graph) {
1.74 + int countBiNodeConnectedComponents(const UndirGraph& graph) {
1.75 checkConcept<concept::UndirGraph, UndirGraph>();
1.76 typedef typename UndirGraph::NodeIt NodeIt;
1.77
1.78 using namespace _topology_bits;
1.79
1.80 - typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
1.81 + typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor;
1.82
1.83 int compNum = 0;
1.84 Visitor visitor(graph, compNum);
1.85 @@ -778,7 +778,7 @@
1.86
1.87 using namespace _topology_bits;
1.88
1.89 - typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
1.90 + typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
1.91
1.92 int compNum = 0;
1.93 Visitor visitor(graph, compMap, compNum);
1.94 @@ -818,7 +818,7 @@
1.95
1.96 using namespace _topology_bits;
1.97
1.98 - typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
1.99 + typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
1.100
1.101 int cutNum = 0;
1.102 Visitor visitor(graph, cutMap, cutNum);
1.103 @@ -838,13 +838,13 @@
1.104 namespace _topology_bits {
1.105
1.106 template <typename Graph>
1.107 - class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
1.108 + class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
1.109 public:
1.110 typedef typename Graph::Node Node;
1.111 typedef typename Graph::Edge Edge;
1.112 typedef typename Graph::UndirEdge UndirEdge;
1.113
1.114 - CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)
1.115 + CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
1.116 : _graph(graph), _compNum(compNum),
1.117 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.118
1.119 @@ -894,13 +894,13 @@
1.120 };
1.121
1.122 template <typename Graph, typename NodeMap>
1.123 - class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
1.124 + class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
1.125 public:
1.126 typedef typename Graph::Node Node;
1.127 typedef typename Graph::Edge Edge;
1.128 typedef typename Graph::UndirEdge UndirEdge;
1.129
1.130 - EdgeBiconnectedComponentsVisitor(const Graph& graph,
1.131 + BiEdgeConnectedComponentsVisitor(const Graph& graph,
1.132 NodeMap& compMap, int &compNum)
1.133 : _graph(graph), _compMap(compMap), _compNum(compNum),
1.134 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.135 @@ -961,13 +961,13 @@
1.136
1.137
1.138 template <typename Graph, typename EdgeMap>
1.139 - class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
1.140 + class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
1.141 public:
1.142 typedef typename Graph::Node Node;
1.143 typedef typename Graph::Edge Edge;
1.144 typedef typename Graph::UndirEdge UndirEdge;
1.145
1.146 - EdgeBiconnectedCutEdgesVisitor(const Graph& graph,
1.147 + BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
1.148 EdgeMap& cutMap, int &cutNum)
1.149 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
1.150 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.151 @@ -1023,7 +1023,7 @@
1.152 }
1.153
1.154 template <typename UndirGraph>
1.155 - int countEdgeBiconnectedComponents(const UndirGraph& graph);
1.156 + int countbiEdgeConnectedComponents(const UndirGraph& graph);
1.157
1.158 /// \ingroup topology
1.159 ///
1.160 @@ -1038,7 +1038,7 @@
1.161 /// \todo Make it faster.
1.162 template <typename UndirGraph>
1.163 bool biEdgeConnected(const UndirGraph& graph) {
1.164 - return countEdgeBiconnectedComponents(graph) == 1;
1.165 + return countBiEdgeConnectedComponents(graph) == 1;
1.166 }
1.167
1.168 /// \ingroup topology
1.169 @@ -1053,13 +1053,13 @@
1.170 /// \param graph The undirected graph.
1.171 /// \return The number of components.
1.172 template <typename UndirGraph>
1.173 - int countEdgeBiconnectedComponents(const UndirGraph& graph) {
1.174 + int countBiEdgeConnectedComponents(const UndirGraph& graph) {
1.175 checkConcept<concept::UndirGraph, UndirGraph>();
1.176 typedef typename UndirGraph::NodeIt NodeIt;
1.177
1.178 using namespace _topology_bits;
1.179
1.180 - typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
1.181 + typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor;
1.182
1.183 int compNum = 0;
1.184 Visitor visitor(graph, compNum);
1.185 @@ -1104,7 +1104,7 @@
1.186
1.187 using namespace _topology_bits;
1.188
1.189 - typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
1.190 + typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
1.191
1.192 int compNum = 0;
1.193 Visitor visitor(graph, compMap, compNum);
1.194 @@ -1145,7 +1145,7 @@
1.195
1.196 using namespace _topology_bits;
1.197
1.198 - typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
1.199 + typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
1.200
1.201 int cutNum = 0;
1.202 Visitor visitor(graph, cutMap, cutNum);
1.203 @@ -1388,41 +1388,76 @@
1.204
1.205 /// \ingroup topology
1.206 ///
1.207 - /// \brief Check that the given undirected graph is bipartite.
1.208 + /// \brief Check if the given undirected graph is bipartite or not
1.209 ///
1.210 - /// Check that the given undirected graph is bipartite.
1.211 + /// The function checks if the given undirected \c graph graph is bipartite
1.212 + /// or not. The \ref Bfs algorithm is used to calculate the result.
1.213 /// \param graph The undirected graph.
1.214 - /// \return %True when the nodes can be separated into two sets that
1.215 - /// there are not connected nodes in neither sets.
1.216 - template <typename UndirGraph>
1.217 - bool bipartite(const UndirGraph& graph) {
1.218 + /// \return %True if \c graph is bipartite, %false otherwise.
1.219 + /// \sa bipartitePartitions
1.220 + ///
1.221 + /// \author Balazs Attila Mihaly
1.222 + template<typename UndirGraph>
1.223 + inline bool bipartite(const UndirGraph &graph){
1.224 checkConcept<concept::UndirGraph, UndirGraph>();
1.225 +
1.226 + typedef typename UndirGraph::NodeIt NodeIt;
1.227 + typedef typename UndirGraph::EdgeIt EdgeIt;
1.228 +
1.229 + Bfs<UndirGraph> bfs(graph);
1.230 + bfs.init();
1.231 + for(NodeIt i(graph);i!=INVALID;++i){
1.232 + if(!bfs.reached(i)){
1.233 + bfs.run(i);
1.234 + }
1.235 + }
1.236 + for(EdgeIt i(graph);i!=INVALID;++i){
1.237 + if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
1.238 + }
1.239 + return true;
1.240 + };
1.241 +
1.242 + /// \ingroup topology
1.243 + ///
1.244 + /// \brief Check if the given undirected graph is bipartite or not
1.245 + ///
1.246 + /// The function checks if the given undirected graph is bipartite
1.247 + /// or not. The \ref Bfs algorithm is used to calculate the result.
1.248 + /// During the execution, the \c partMap will be set as the two
1.249 + /// partitions of the graph.
1.250 + /// \param graph The undirected graph.
1.251 + /// \retval partMap A writeable bool map of nodes. It will be set as the
1.252 + /// two partitions of the graph.
1.253 + /// \return %True if \c graph is bipartite, %false otherwise.
1.254 + ///
1.255 + /// \author Balazs Attila Mihaly
1.256 + ///
1.257 + /// \image html bipartite_partitions.png
1.258 + /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1.259 + template<typename UndirGraph, typename NodeMap>
1.260 + inline bool bipartitePartitions(const UndirGraph &graph, NodeMap &partMap){
1.261 + checkConcept<concept::UndirGraph, UndirGraph>();
1.262 +
1.263 typedef typename UndirGraph::Node Node;
1.264 typedef typename UndirGraph::NodeIt NodeIt;
1.265 - typedef typename UndirGraph::Edge Edge;
1.266 - if (NodeIt(graph) == INVALID) return false;
1.267 - Dfs<UndirGraph> dfs(graph);
1.268 - dfs.init();
1.269 - typename UndirGraph::template NodeMap<bool> red(graph);
1.270 - for (NodeIt it(graph); it != INVALID; ++it) {
1.271 - if (!dfs.reached(it)) {
1.272 - dfs.addSource(it);
1.273 - red[it] = true;
1.274 - while (!dfs.emptyQueue()) {
1.275 - Edge edge = dfs.nextEdge();
1.276 - Node source = graph.source(edge);
1.277 - Node target = graph.target(edge);
1.278 - if (dfs.reached(target) && red[source] == red[target]) {
1.279 - return false;
1.280 - } else {
1.281 - red[target] = !red[source];
1.282 - }
1.283 - dfs.processNextEdge();
1.284 + typedef typename UndirGraph::EdgeIt EdgeIt;
1.285 +
1.286 + Bfs<UndirGraph> bfs(graph);
1.287 + bfs.init();
1.288 + for(NodeIt i(graph);i!=INVALID;++i){
1.289 + if(!bfs.reached(i)){
1.290 + bfs.addSource(i);
1.291 + for(Node j=bfs.processNextNode();!bfs.emptyQueue();
1.292 + j=bfs.processNextNode()){
1.293 + partMap.set(j,bfs.dist(j)%2==0);
1.294 }
1.295 }
1.296 }
1.297 + for(EdgeIt i(graph);i!=INVALID;++i){
1.298 + if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
1.299 + }
1.300 return true;
1.301 - }
1.302 + };
1.303
1.304 } //namespace lemon
1.305