1.1 --- a/lemon/smart_graph.h Mon Nov 21 12:07:05 2005 +0000
1.2 +++ b/lemon/smart_graph.h Mon Nov 21 17:48:00 2005 +0000
1.3 @@ -33,6 +33,7 @@
1.4 #include <lemon/bits/graph_extender.h>
1.5
1.6 #include <lemon/utility.h>
1.7 +#include <lemon/error.h>
1.8
1.9 namespace lemon {
1.10
1.11 @@ -374,6 +375,228 @@
1.12 class UndirSmartGraph : public ExtendedUndirSmartGraphBase {
1.13 };
1.14
1.15 +
1.16 + class SmartUndirBipartiteGraphBase {
1.17 + public:
1.18 +
1.19 + class NodeSetError : public LogicError {
1.20 + virtual const char* exceptionName() const {
1.21 + return "lemon::FullUndirBipartiteGraph::NodeSetError";
1.22 + }
1.23 + };
1.24 +
1.25 + protected:
1.26 +
1.27 + struct NodeT {
1.28 + int first;
1.29 + NodeT() {}
1.30 + NodeT(int _first) : first(_first) {}
1.31 + };
1.32 +
1.33 + struct EdgeT {
1.34 + int upper, next_down;
1.35 + int lower, next_up;
1.36 + };
1.37 +
1.38 + std::vector<NodeT> upperNodes;
1.39 + std::vector<NodeT> lowerNodes;
1.40 +
1.41 + std::vector<EdgeT> edges;
1.42 +
1.43 + public:
1.44 +
1.45 + class Node {
1.46 + friend class SmartUndirBipartiteGraphBase;
1.47 + protected:
1.48 + int id;
1.49 +
1.50 + Node(int _id) : id(_id) {}
1.51 + public:
1.52 + Node() {}
1.53 + Node(Invalid) { id = -1; }
1.54 + bool operator==(const Node i) const {return id==i.id;}
1.55 + bool operator!=(const Node i) const {return id!=i.id;}
1.56 + bool operator<(const Node i) const {return id<i.id;}
1.57 + };
1.58 +
1.59 + class Edge {
1.60 + friend class SmartUndirBipartiteGraphBase;
1.61 + protected:
1.62 + int id;
1.63 +
1.64 + Edge(int _id) { id = _id;}
1.65 + public:
1.66 + Edge() {}
1.67 + Edge (Invalid) { id = -1; }
1.68 + bool operator==(const Edge i) const {return id==i.id;}
1.69 + bool operator!=(const Edge i) const {return id!=i.id;}
1.70 + bool operator<(const Edge i) const {return id<i.id;}
1.71 + };
1.72 +
1.73 + void firstUpper(Node& node) const {
1.74 + node.id = 2 * upperNodes.size() - 2;
1.75 + if (node.id < 0) node.id = -1;
1.76 + }
1.77 + void nextUpper(Node& node) const {
1.78 + node.id -= 2;
1.79 + if (node.id < 0) node.id = -1;
1.80 + }
1.81 +
1.82 + void firstLower(Node& node) const {
1.83 + node.id = 2 * lowerNodes.size() - 1;
1.84 + }
1.85 + void nextLower(Node& node) const {
1.86 + node.id -= 2;
1.87 + }
1.88 +
1.89 + void first(Node& node) const {
1.90 + if (upperNodes.size() > 0) {
1.91 + node.id = 2 * upperNodes.size() - 2;
1.92 + } else {
1.93 + node.id = 2 * lowerNodes.size() - 1;
1.94 + }
1.95 + }
1.96 + void next(Node& node) const {
1.97 + node.id -= 2;
1.98 + if (node.id == -2) {
1.99 + node.id = 2 * lowerNodes.size() - 1;
1.100 + }
1.101 + }
1.102 +
1.103 + void first(Edge& edge) const {
1.104 + edge.id = edges.size() - 1;
1.105 + }
1.106 + void next(Edge& edge) const {
1.107 + --edge.id;
1.108 + }
1.109 +
1.110 + void firstDown(Edge& edge, const Node& node) const {
1.111 + LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1.112 + edge.id = upperNodes[node.id >> 1].first;
1.113 + }
1.114 + void nextDown(Edge& edge) const {
1.115 + edge.id = edges[edge.id].next_down;
1.116 + }
1.117 +
1.118 + void firstUp(Edge& edge, const Node& node) const {
1.119 + LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1.120 + edge.id = lowerNodes[node.id >> 1].first;
1.121 + }
1.122 + void nextUp(Edge& edge) const {
1.123 + edge.id = edges[edge.id].next_up;
1.124 + }
1.125 +
1.126 + static int id(const Node& node) {
1.127 + return node.id;
1.128 + }
1.129 + static Node nodeFromId(int id) {
1.130 + return Node(id);
1.131 + }
1.132 + int maxNodeId() const {
1.133 + return upperNodes.size() > lowerNodes.size() ?
1.134 + upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
1.135 + }
1.136 +
1.137 + static int id(const Edge& edge) {
1.138 + return edge.id;
1.139 + }
1.140 + static Edge edgeFromId(int id) {
1.141 + return Edge(id);
1.142 + }
1.143 + int maxEdgeId() const {
1.144 + return edges.size();
1.145 + }
1.146 +
1.147 + static int upperId(const Node& node) {
1.148 + return node.id >> 1;
1.149 + }
1.150 + static Node fromUpperId(int id, Node) {
1.151 + return Node(id << 1);
1.152 + }
1.153 + int maxUpperId() const {
1.154 + return upperNodes.size();
1.155 + }
1.156 +
1.157 + static int lowerId(const Node& node) {
1.158 + return node.id >> 1;
1.159 + }
1.160 + static Node fromLowerId(int id) {
1.161 + return Node((id << 1) + 1);
1.162 + }
1.163 + int maxLowerId() const {
1.164 + return lowerNodes.size();
1.165 + }
1.166 +
1.167 + Node upperNode(const Edge& edge) const {
1.168 + return Node(edges[edge.id].upper);
1.169 + }
1.170 + Node lowerNode(const Edge& edge) const {
1.171 + return Node(edges[edge.id].lower);
1.172 + }
1.173 +
1.174 + static bool upper(const Node& node) {
1.175 + return (node.id & 1) == 0;
1.176 + }
1.177 +
1.178 + static bool lower(const Node& node) {
1.179 + return (node.id & 1) == 1;
1.180 + }
1.181 +
1.182 + Node addUpperNode() {
1.183 + NodeT nodeT;
1.184 + nodeT.first = -1;
1.185 + upperNodes.push_back(nodeT);
1.186 + return Node(upperNodes.size() * 2 - 2);
1.187 + }
1.188 +
1.189 + Node addLowerNode() {
1.190 + NodeT nodeT;
1.191 + nodeT.first = -1;
1.192 + lowerNodes.push_back(nodeT);
1.193 + return Node(lowerNodes.size() * 2 - 1);
1.194 + }
1.195 +
1.196 + Edge addEdge(const Node& source, const Node& target) {
1.197 + LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1.198 + EdgeT edgeT;
1.199 + if ((source.id & 1) == 0) {
1.200 + edgeT.upper = source.id;
1.201 + edgeT.lower = target.id;
1.202 + } else {
1.203 + edgeT.upper = target.id;
1.204 + edgeT.lower = source.id;
1.205 + }
1.206 + edgeT.next_down = upperNodes[edgeT.upper >> 1].first;
1.207 + upperNodes[edgeT.upper >> 1].first = edges.size();
1.208 + edgeT.next_up = lowerNodes[edgeT.lower >> 1].first;
1.209 + lowerNodes[edgeT.lower >> 1].first = edges.size();
1.210 + edges.push_back(edgeT);
1.211 + return Edge(edges.size() - 1);
1.212 + }
1.213 +
1.214 + void clear() {
1.215 + upperNodes.clear();
1.216 + lowerNodes.clear();
1.217 + edges.clear();
1.218 + }
1.219 +
1.220 + };
1.221 +
1.222 +
1.223 + typedef ClearableUndirBipartiteGraphExtender<
1.224 + ExtendableUndirBipartiteGraphExtender<
1.225 + MappableUndirBipartiteGraphExtender<
1.226 + IterableUndirBipartiteGraphExtender<
1.227 + AlterableUndirBipartiteGraphExtender<
1.228 + UndirBipartiteGraphExtender <
1.229 + SmartUndirBipartiteGraphBase> > > > > >
1.230 + ExtendedSmartUndirBipartiteGraphBase;
1.231 +
1.232 +
1.233 + class SmartUndirBipartiteGraph :
1.234 + public ExtendedSmartUndirBipartiteGraphBase {
1.235 + };
1.236 +
1.237
1.238 /// @}
1.239 } //namespace lemon