1.1 --- a/lemon/topology.h Tue Nov 21 17:28:08 2006 +0000
1.2 +++ b/lemon/topology.h Tue Nov 21 18:22:08 2006 +0000
1.3 @@ -1389,6 +1389,64 @@
1.4 return true;
1.5 }
1.6
1.7 + namespace _topology_bits {
1.8 +
1.9 + template <typename Graph>
1.10 + class BipartiteVisitor : public BfsVisitor<Graph> {
1.11 + public:
1.12 + typedef typename Graph::Edge Edge;
1.13 + typedef typename Graph::Node Node;
1.14 +
1.15 + BipartiteVisitor(const Graph& graph, bool& bipartite)
1.16 + : _graph(graph), _part(graph), _bipartite(bipartite) {}
1.17 +
1.18 + void start(const Node& node) {
1.19 + _part[node] = true;
1.20 + }
1.21 + void discover(const Edge& edge) {
1.22 + _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1.23 + }
1.24 + void examine(const Edge& edge) {
1.25 + _bipartite = _bipartite &&
1.26 + _part[_graph.target(edge)] != _part[_graph.source(edge)];
1.27 + }
1.28 +
1.29 + private:
1.30 +
1.31 + const Graph& _graph;
1.32 + typename Graph::template NodeMap<bool> _part;
1.33 + bool& _bipartite;
1.34 + };
1.35 +
1.36 + template <typename Graph, typename PartMap>
1.37 + class BipartitePartitionsVisitor : public BfsVisitor<Graph> {
1.38 + public:
1.39 + typedef typename Graph::Edge Edge;
1.40 + typedef typename Graph::Node Node;
1.41 +
1.42 + BipartitePartitionsVisitor(const Graph& graph,
1.43 + PartMap& part, bool& bipartite)
1.44 + : _graph(graph), _part(part), _bipartite(bipartite) {}
1.45 +
1.46 + void start(const Node& node) {
1.47 + _part.set(node, true);
1.48 + }
1.49 + void discover(const Edge& edge) {
1.50 + _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1.51 + }
1.52 + void examine(const Edge& edge) {
1.53 + _bipartite = _bipartite &&
1.54 + _part[_graph.target(edge)] != _part[_graph.source(edge)];
1.55 + }
1.56 +
1.57 + private:
1.58 +
1.59 + const Graph& _graph;
1.60 + PartMap& _part;
1.61 + bool& _bipartite;
1.62 + };
1.63 + }
1.64 +
1.65 /// \ingroup topology
1.66 ///
1.67 /// \brief Check if the given undirected graph is bipartite or not
1.68 @@ -1402,21 +1460,29 @@
1.69 /// \author Balazs Attila Mihaly
1.70 template<typename UGraph>
1.71 inline bool bipartite(const UGraph &graph){
1.72 + using namespace _topology_bits;
1.73 +
1.74 checkConcept<concepts::UGraph, UGraph>();
1.75
1.76 typedef typename UGraph::NodeIt NodeIt;
1.77 typedef typename UGraph::EdgeIt EdgeIt;
1.78
1.79 - Bfs<UGraph> bfs(graph);
1.80 + bool bipartite = true;
1.81 +
1.82 + BipartiteVisitor<UGraph>
1.83 + visitor(graph, bipartite);
1.84 + BfsVisit<UGraph, BipartiteVisitor<UGraph> >
1.85 + bfs(graph, visitor);
1.86 bfs.init();
1.87 - for(NodeIt i(graph);i!=INVALID;++i){
1.88 - if(!bfs.reached(i)){
1.89 - bfs.run(i);
1.90 + for(NodeIt it(graph); it != INVALID; ++it) {
1.91 + if(!bfs.reached(it)){
1.92 + bfs.addSource(it);
1.93 + while (!bfs.emptyQueue()) {
1.94 + bfs.processNextNode();
1.95 + if (!bipartite) return false;
1.96 + }
1.97 }
1.98 }
1.99 - for(EdgeIt i(graph);i!=INVALID;++i){
1.100 - if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
1.101 - }
1.102 return true;
1.103 }
1.104
1.105 @@ -1439,25 +1505,80 @@
1.106 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1.107 template<typename UGraph, typename NodeMap>
1.108 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
1.109 + using namespace _topology_bits;
1.110 +
1.111 checkConcept<concepts::UGraph, UGraph>();
1.112
1.113 typedef typename UGraph::Node Node;
1.114 typedef typename UGraph::NodeIt NodeIt;
1.115 typedef typename UGraph::EdgeIt EdgeIt;
1.116 -
1.117 - Bfs<UGraph> bfs(graph);
1.118 +
1.119 + bool bipartite = true;
1.120 +
1.121 + BipartitePartitionsVisitor<UGraph, NodeMap>
1.122 + visitor(graph, partMap, bipartite);
1.123 + BfsVisit<UGraph, BipartitePartitionsVisitor<UGraph, NodeMap> >
1.124 + bfs(graph, visitor);
1.125 bfs.init();
1.126 - for(NodeIt i(graph);i!=INVALID;++i){
1.127 - if(!bfs.reached(i)){
1.128 - bfs.addSource(i);
1.129 - for(Node j=bfs.processNextNode();!bfs.emptyQueue();
1.130 - j=bfs.processNextNode()){
1.131 - partMap.set(j,bfs.dist(j)%2==0);
1.132 - }
1.133 + for(NodeIt it(graph); it != INVALID; ++it) {
1.134 + if(!bfs.reached(it)){
1.135 + bfs.addSource(it);
1.136 + while (!bfs.emptyQueue()) {
1.137 + bfs.processNextNode();
1.138 + if (!bipartite) return false;
1.139 + }
1.140 }
1.141 }
1.142 - for(EdgeIt i(graph);i!=INVALID;++i){
1.143 - if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
1.144 + return true;
1.145 + }
1.146 +
1.147 + /// \brief Returns true when there is not loop edge in the graph.
1.148 + ///
1.149 + /// Returns true when there is not loop edge in the graph.
1.150 + template <typename Graph>
1.151 + bool loopFree(const Graph& graph) {
1.152 + for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
1.153 + if (graph.source(it) == graph.target(it)) return false;
1.154 + }
1.155 + return true;
1.156 + }
1.157 +
1.158 + /// \brief Returns true when there is not parallel edges in the graph.
1.159 + ///
1.160 + /// Returns true when there is not parallel edges in the graph.
1.161 + template <typename Graph>
1.162 + bool parallelFree(const Graph& graph) {
1.163 + typename Graph::template NodeMap<bool> reached(graph, false);
1.164 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.165 + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1.166 + if (reached[graph.target(e)]) return false;
1.167 + reached.set(graph.target(e), true);
1.168 + }
1.169 + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1.170 + reached.set(graph.target(e), false);
1.171 + }
1.172 + }
1.173 + return true;
1.174 + }
1.175 +
1.176 + /// \brief Returns true when there is not loop edge and parallel
1.177 + /// edges in the graph.
1.178 + ///
1.179 + /// Returns true when there is not loop edge and parallel edges in
1.180 + /// the graph.
1.181 + template <typename Graph>
1.182 + bool simpleGraph(const Graph& graph) {
1.183 + typename Graph::template NodeMap<bool> reached(graph, false);
1.184 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.185 + reached.set(n, true);
1.186 + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1.187 + if (reached[graph.target(e)]) return false;
1.188 + reached.set(graph.target(e), true);
1.189 + }
1.190 + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1.191 + reached.set(graph.target(e), false);
1.192 + }
1.193 + reached.set(n, false);
1.194 }
1.195 return true;
1.196 }