1.1 --- a/lemon/bits/base_extender.h Tue May 09 14:28:02 2006 +0000
1.2 +++ b/lemon/bits/base_extender.h Fri May 12 09:51:45 2006 +0000
1.3 @@ -37,7 +37,7 @@
1.4 ///
1.5 /// \brief BaseExtender for the UGraphs
1.6 template <typename Base>
1.7 - class UGraphBaseExtender : public Base {
1.8 + class UndirGraphExtender : public Base {
1.9
1.10 public:
1.11
1.12 @@ -48,7 +48,7 @@
1.13 typedef True UndirectedTag;
1.14
1.15 class Edge : public UEdge {
1.16 - friend class UGraphBaseExtender;
1.17 + friend class UndirGraphExtender;
1.18
1.19 protected:
1.20 bool forward;
1.21 @@ -275,208 +275,6 @@
1.22 }
1.23 };
1.24
1.25 -
1.26 - /// \ingroup graphbits
1.27 - ///
1.28 - /// \brief BaseExtender for the BpUGraphs
1.29 - template <typename Base>
1.30 - class BpUGraphBaseExtender : public Base {
1.31 - public:
1.32 - typedef Base Parent;
1.33 - typedef BpUGraphBaseExtender Graph;
1.34 -
1.35 - typedef typename Parent::Node Node;
1.36 - typedef typename Parent::Edge UEdge;
1.37 -
1.38 -
1.39 - using Parent::first;
1.40 - using Parent::next;
1.41 -
1.42 - using Parent::id;
1.43 -
1.44 - class ANode : public Node {
1.45 - friend class BpUGraphBaseExtender;
1.46 - public:
1.47 - ANode() {}
1.48 - ANode(const Node& node) : Node(node) {
1.49 - LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
1.50 - typename Parent::NodeSetError());
1.51 - }
1.52 - ANode(Invalid) : Node(INVALID) {}
1.53 - };
1.54 -
1.55 - void first(ANode& node) const {
1.56 - Parent::firstANode(static_cast<Node&>(node));
1.57 - }
1.58 - void next(ANode& node) const {
1.59 - Parent::nextANode(static_cast<Node&>(node));
1.60 - }
1.61 -
1.62 - int id(const ANode& node) const {
1.63 - return Parent::aNodeId(node);
1.64 - }
1.65 -
1.66 - class BNode : public Node {
1.67 - friend class BpUGraphBaseExtender;
1.68 - public:
1.69 - BNode() {}
1.70 - BNode(const Node& node) : Node(node) {
1.71 - LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
1.72 - typename Parent::NodeSetError());
1.73 - }
1.74 - BNode(Invalid) : Node(INVALID) {}
1.75 - };
1.76 -
1.77 - void first(BNode& node) const {
1.78 - Parent::firstBNode(static_cast<Node&>(node));
1.79 - }
1.80 - void next(BNode& node) const {
1.81 - Parent::nextBNode(static_cast<Node&>(node));
1.82 - }
1.83 -
1.84 - int id(const BNode& node) const {
1.85 - return Parent::aNodeId(node);
1.86 - }
1.87 -
1.88 - Node source(const UEdge& edge) const {
1.89 - return aNode(edge);
1.90 - }
1.91 - Node target(const UEdge& edge) const {
1.92 - return bNode(edge);
1.93 - }
1.94 -
1.95 - void firstInc(UEdge& edge, bool& direction, const Node& node) const {
1.96 - if (Parent::aNode(node)) {
1.97 - Parent::firstOut(edge, node);
1.98 - direction = true;
1.99 - } else {
1.100 - Parent::firstIn(edge, node);
1.101 - direction = static_cast<UEdge&>(edge) == INVALID;
1.102 - }
1.103 - }
1.104 - void nextInc(UEdge& edge, bool& direction) const {
1.105 - if (direction) {
1.106 - Parent::nextOut(edge);
1.107 - } else {
1.108 - Parent::nextIn(edge);
1.109 - if (edge == INVALID) direction = true;
1.110 - }
1.111 - }
1.112 -
1.113 - int maxUEdgeId() const {
1.114 - return Parent::maxEdgeId();
1.115 - }
1.116 -
1.117 - UEdge uEdgeFromId(int id) const {
1.118 - return Parent::edgeFromId(id);
1.119 - }
1.120 -
1.121 - class Edge : public UEdge {
1.122 - friend class BpUGraphBaseExtender;
1.123 - protected:
1.124 - bool forward;
1.125 -
1.126 - Edge(const UEdge& edge, bool _forward)
1.127 - : UEdge(edge), forward(_forward) {}
1.128 -
1.129 - public:
1.130 - Edge() {}
1.131 - Edge (Invalid) : UEdge(INVALID), forward(true) {}
1.132 - bool operator==(const Edge& i) const {
1.133 - return UEdge::operator==(i) && forward == i.forward;
1.134 - }
1.135 - bool operator!=(const Edge& i) const {
1.136 - return UEdge::operator!=(i) || forward != i.forward;
1.137 - }
1.138 - bool operator<(const Edge& i) const {
1.139 - return UEdge::operator<(i) ||
1.140 - (!(i.forward<forward) && UEdge(*this)<UEdge(i));
1.141 - }
1.142 - };
1.143 -
1.144 - void first(Edge& edge) const {
1.145 - Parent::first(static_cast<UEdge&>(edge));
1.146 - edge.forward = true;
1.147 - }
1.148 -
1.149 - void next(Edge& edge) const {
1.150 - if (!edge.forward) {
1.151 - Parent::next(static_cast<UEdge&>(edge));
1.152 - }
1.153 - edge.forward = !edge.forward;
1.154 - }
1.155 -
1.156 - void firstOut(Edge& edge, const Node& node) const {
1.157 - if (Parent::aNode(node)) {
1.158 - Parent::firstOut(edge, node);
1.159 - edge.forward = true;
1.160 - } else {
1.161 - Parent::firstIn(edge, node);
1.162 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
1.163 - }
1.164 - }
1.165 - void nextOut(Edge& edge) const {
1.166 - if (edge.forward) {
1.167 - Parent::nextOut(edge);
1.168 - } else {
1.169 - Parent::nextIn(edge);
1.170 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
1.171 - }
1.172 - }
1.173 -
1.174 - void firstIn(Edge& edge, const Node& node) const {
1.175 - if (Parent::bNode(node)) {
1.176 - Parent::firstIn(edge, node);
1.177 - edge.forward = true;
1.178 - } else {
1.179 - Parent::firstOut(edge, node);
1.180 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
1.181 - }
1.182 - }
1.183 - void nextIn(Edge& edge) const {
1.184 - if (edge.forward) {
1.185 - Parent::nextIn(edge);
1.186 - } else {
1.187 - Parent::nextOut(edge);
1.188 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
1.189 - }
1.190 - }
1.191 -
1.192 - Node source(const Edge& edge) const {
1.193 - return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
1.194 - }
1.195 - Node target(const Edge& edge) const {
1.196 - return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
1.197 - }
1.198 -
1.199 - int id(const Edge& edge) const {
1.200 - return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
1.201 - }
1.202 - Edge edgeFromId(int id) const {
1.203 - return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
1.204 - }
1.205 - int maxEdgeId() const {
1.206 - return (Parent::maxId(UEdge()) << 1) + 1;
1.207 - }
1.208 -
1.209 - bool direction(const Edge& edge) const {
1.210 - return edge.forward;
1.211 - }
1.212 -
1.213 - Edge direct(const UEdge& edge, bool direction) const {
1.214 - return Edge(edge, direction);
1.215 - }
1.216 -
1.217 - int edgeNum() const {
1.218 - return 2 * Parent::edgeNum();
1.219 - }
1.220 -
1.221 - int uEdgeNum() const {
1.222 - return Parent::edgeNum();
1.223 - }
1.224 -
1.225 - };
1.226 -
1.227 }
1.228
1.229 #endif
2.1 --- a/lemon/bits/graph_adaptor_extender.h Tue May 09 14:28:02 2006 +0000
2.2 +++ b/lemon/bits/graph_adaptor_extender.h Fri May 12 09:51:45 2006 +0000
2.3 @@ -453,11 +453,6 @@
2.4 typedef typename Parent::Edge Edge;
2.5 typedef typename Parent::UEdge UEdge;
2.6
2.7 - Node oppositeNode(const UEdge& edge, const Node& node) const {
2.8 - return source(edge) == node ?
2.9 - target(edge) : source(edge);
2.10 - }
2.11 -
2.12
2.13 int maxId(Node) const {
2.14 return Parent::maxNodeId();
3.1 --- a/lemon/bits/graph_extender.h Tue May 09 14:28:02 2006 +0000
3.2 +++ b/lemon/bits/graph_extender.h Fri May 12 09:51:45 2006 +0000
3.3 @@ -734,17 +734,193 @@
3.4 typedef BpUGraphExtender Graph;
3.5
3.6 typedef typename Parent::Node Node;
3.7 - typedef typename Parent::BNode BNode;
3.8 - typedef typename Parent::ANode ANode;
3.9 - typedef typename Parent::Edge Edge;
3.10 typedef typename Parent::UEdge UEdge;
3.11
3.12 +
3.13 + using Parent::first;
3.14 + using Parent::next;
3.15 +
3.16 + using Parent::id;
3.17 +
3.18 + class ANode : public Node {
3.19 + friend class BpUGraphExtender;
3.20 + public:
3.21 + ANode() {}
3.22 + ANode(const Node& node) : Node(node) {
3.23 + LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
3.24 + typename Parent::NodeSetError());
3.25 + }
3.26 + ANode(Invalid) : Node(INVALID) {}
3.27 + };
3.28 +
3.29 + void first(ANode& node) const {
3.30 + Parent::firstANode(static_cast<Node&>(node));
3.31 + }
3.32 + void next(ANode& node) const {
3.33 + Parent::nextANode(static_cast<Node&>(node));
3.34 + }
3.35 +
3.36 + int id(const ANode& node) const {
3.37 + return Parent::aNodeId(node);
3.38 + }
3.39 +
3.40 + class BNode : public Node {
3.41 + friend class BpUGraphExtender;
3.42 + public:
3.43 + BNode() {}
3.44 + BNode(const Node& node) : Node(node) {
3.45 + LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
3.46 + typename Parent::NodeSetError());
3.47 + }
3.48 + BNode(Invalid) : Node(INVALID) {}
3.49 + };
3.50 +
3.51 + void first(BNode& node) const {
3.52 + Parent::firstBNode(static_cast<Node&>(node));
3.53 + }
3.54 + void next(BNode& node) const {
3.55 + Parent::nextBNode(static_cast<Node&>(node));
3.56 + }
3.57 +
3.58 + int id(const BNode& node) const {
3.59 + return Parent::aNodeId(node);
3.60 + }
3.61 +
3.62 + Node source(const UEdge& edge) const {
3.63 + return aNode(edge);
3.64 + }
3.65 + Node target(const UEdge& edge) const {
3.66 + return bNode(edge);
3.67 + }
3.68 +
3.69 + void firstInc(UEdge& edge, bool& direction, const Node& node) const {
3.70 + if (Parent::aNode(node)) {
3.71 + Parent::firstFromANode(edge, node);
3.72 + direction = true;
3.73 + } else {
3.74 + Parent::firstFromBNode(edge, node);
3.75 + direction = static_cast<UEdge&>(edge) == INVALID;
3.76 + }
3.77 + }
3.78 + void nextInc(UEdge& edge, bool& direction) const {
3.79 + if (direction) {
3.80 + Parent::nextFromANode(edge);
3.81 + } else {
3.82 + Parent::nextFromBNode(edge);
3.83 + if (edge == INVALID) direction = true;
3.84 + }
3.85 + }
3.86 +
3.87 + class Edge : public UEdge {
3.88 + friend class BpUGraphExtender;
3.89 + protected:
3.90 + bool forward;
3.91 +
3.92 + Edge(const UEdge& edge, bool _forward)
3.93 + : UEdge(edge), forward(_forward) {}
3.94 +
3.95 + public:
3.96 + Edge() {}
3.97 + Edge (Invalid) : UEdge(INVALID), forward(true) {}
3.98 + bool operator==(const Edge& i) const {
3.99 + return UEdge::operator==(i) && forward == i.forward;
3.100 + }
3.101 + bool operator!=(const Edge& i) const {
3.102 + return UEdge::operator!=(i) || forward != i.forward;
3.103 + }
3.104 + bool operator<(const Edge& i) const {
3.105 + return UEdge::operator<(i) ||
3.106 + (!(i.forward<forward) && UEdge(*this)<UEdge(i));
3.107 + }
3.108 + };
3.109 +
3.110 + void first(Edge& edge) const {
3.111 + Parent::first(static_cast<UEdge&>(edge));
3.112 + edge.forward = true;
3.113 + }
3.114 +
3.115 + void next(Edge& edge) const {
3.116 + if (!edge.forward) {
3.117 + Parent::next(static_cast<UEdge&>(edge));
3.118 + }
3.119 + edge.forward = !edge.forward;
3.120 + }
3.121 +
3.122 + void firstOut(Edge& edge, const Node& node) const {
3.123 + if (Parent::aNode(node)) {
3.124 + Parent::firstFromANode(edge, node);
3.125 + edge.forward = true;
3.126 + } else {
3.127 + Parent::firstFromBNode(edge, node);
3.128 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
3.129 + }
3.130 + }
3.131 + void nextOut(Edge& edge) const {
3.132 + if (edge.forward) {
3.133 + Parent::nextFromANode(edge);
3.134 + } else {
3.135 + Parent::nextFromBNode(edge);
3.136 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
3.137 + }
3.138 + }
3.139 +
3.140 + void firstIn(Edge& edge, const Node& node) const {
3.141 + if (Parent::bNode(node)) {
3.142 + Parent::firstFromBNode(edge, node);
3.143 + edge.forward = true;
3.144 + } else {
3.145 + Parent::firstFromANode(edge, node);
3.146 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
3.147 + }
3.148 + }
3.149 + void nextIn(Edge& edge) const {
3.150 + if (edge.forward) {
3.151 + Parent::nextFromBNode(edge);
3.152 + } else {
3.153 + Parent::nextFromANode(edge);
3.154 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
3.155 + }
3.156 + }
3.157 +
3.158 + Node source(const Edge& edge) const {
3.159 + return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
3.160 + }
3.161 + Node target(const Edge& edge) const {
3.162 + return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
3.163 + }
3.164 +
3.165 + int id(const Edge& edge) const {
3.166 + return (Parent::id(static_cast<const UEdge&>(edge)) << 1) +
3.167 + (edge.forward ? 0 : 1);
3.168 + }
3.169 + Edge edgeFromId(int id) const {
3.170 + return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
3.171 + }
3.172 + int maxEdgeId() const {
3.173 + return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
3.174 + }
3.175 +
3.176 + bool direction(const Edge& edge) const {
3.177 + return edge.forward;
3.178 + }
3.179 +
3.180 + Edge direct(const UEdge& edge, bool direction) const {
3.181 + return Edge(edge, direction);
3.182 + }
3.183 +
3.184 + int edgeNum() const {
3.185 + return 2 * Parent::uEdgeNum();
3.186 + }
3.187 +
3.188 + int uEdgeNum() const {
3.189 + return Parent::uEdgeNum();
3.190 + }
3.191 +
3.192 Node oppositeNode(const UEdge& edge, const Node& node) const {
3.193 return source(edge) == node ?
3.194 target(edge) : source(edge);
3.195 }
3.196
3.197 - using Parent::direct;
3.198 Edge direct(const UEdge& edge, const Node& node) const {
3.199 return Edge(edge, node == Parent::source(edge));
3.200 }
3.201 @@ -764,7 +940,7 @@
3.202 return Parent::maxANodeId();
3.203 }
3.204 int maxId(Edge) const {
3.205 - return Parent::maxEdgeId();
3.206 + return maxEdgeId();
3.207 }
3.208 int maxId(UEdge) const {
3.209 return Parent::maxUEdgeId();
4.1 --- a/lemon/edge_set.h Tue May 09 14:28:02 2006 +0000
4.2 +++ b/lemon/edge_set.h Fri May 12 09:51:45 2006 +0000
4.3 @@ -337,11 +337,11 @@
4.4 /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
4.5 template <typename _Graph>
4.6 class ListUEdgeSet
4.7 - : public UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > {
4.8 + : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
4.9
4.10 public:
4.11
4.12 - typedef UEdgeSetExtender<UGraphBaseExtender<
4.13 + typedef UEdgeSetExtender<UndirGraphExtender<
4.14 ListEdgeSetBase<_Graph> > > Parent;
4.15
4.16 typedef typename Parent::Node Node;
4.17 @@ -669,11 +669,11 @@
4.18 /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
4.19 template <typename _Graph>
4.20 class SmartUEdgeSet
4.21 - : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
4.22 + : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
4.23
4.24 public:
4.25
4.26 - typedef UEdgeSetExtender<UGraphBaseExtender<
4.27 + typedef UEdgeSetExtender<UndirGraphExtender<
4.28 SmartEdgeSetBase<_Graph> > > Parent;
4.29
4.30 typedef typename Parent::Node Node;
5.1 --- a/lemon/full_graph.h Tue May 09 14:28:02 2006 +0000
5.2 +++ b/lemon/full_graph.h Fri May 12 09:51:45 2006 +0000
5.3 @@ -441,7 +441,7 @@
5.4
5.5 };
5.6
5.7 - typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
5.8 + typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
5.9 ExtendedFullUGraphBase;
5.10
5.11 /// \ingroup graphs
5.12 @@ -518,18 +518,18 @@
5.13 bool operator<(const Node i) const {return id<i.id;}
5.14 };
5.15
5.16 - class Edge {
5.17 + class UEdge {
5.18 friend class FullBpUGraphBase;
5.19 protected:
5.20 int id;
5.21
5.22 - Edge(int _id) { id = _id;}
5.23 + UEdge(int _id) { id = _id;}
5.24 public:
5.25 - Edge() {}
5.26 - Edge (Invalid) { id = -1; }
5.27 - bool operator==(const Edge i) const {return id==i.id;}
5.28 - bool operator!=(const Edge i) const {return id!=i.id;}
5.29 - bool operator<(const Edge i) const {return id<i.id;}
5.30 + UEdge() {}
5.31 + UEdge (Invalid) { id = -1; }
5.32 + bool operator==(const UEdge i) const {return id==i.id;}
5.33 + bool operator!=(const UEdge i) const {return id!=i.id;}
5.34 + bool operator<(const UEdge i) const {return id<i.id;}
5.35 };
5.36
5.37 void construct(int aNodeNum, int bNodeNum) {
5.38 @@ -568,27 +568,27 @@
5.39 }
5.40 }
5.41
5.42 - void first(Edge& edge) const {
5.43 + void first(UEdge& edge) const {
5.44 edge.id = _edgeNum - 1;
5.45 }
5.46 - void next(Edge& edge) const {
5.47 + void next(UEdge& edge) const {
5.48 --edge.id;
5.49 }
5.50
5.51 - void firstOut(Edge& edge, const Node& node) const {
5.52 + void firstFromANode(UEdge& edge, const Node& node) const {
5.53 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
5.54 edge.id = (node.id >> 1) * _bNodeNum;
5.55 }
5.56 - void nextOut(Edge& edge) const {
5.57 + void nextFromANode(UEdge& edge) const {
5.58 ++(edge.id);
5.59 if (edge.id % _bNodeNum == 0) edge.id = -1;
5.60 }
5.61
5.62 - void firstIn(Edge& edge, const Node& node) const {
5.63 + void firstFromBNode(UEdge& edge, const Node& node) const {
5.64 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
5.65 edge.id = (node.id >> 1);
5.66 }
5.67 - void nextIn(Edge& edge) const {
5.68 + void nextFromBNode(UEdge& edge) const {
5.69 edge.id += _bNodeNum;
5.70 if (edge.id >= _edgeNum) edge.id = -1;
5.71 }
5.72 @@ -604,13 +604,13 @@
5.73 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
5.74 }
5.75
5.76 - static int id(const Edge& edge) {
5.77 + static int id(const UEdge& edge) {
5.78 return edge.id;
5.79 }
5.80 - static Edge edgeFromId(int id) {
5.81 - return Edge(id);
5.82 + static UEdge uEdgeFromId(int id) {
5.83 + return UEdge(id);
5.84 }
5.85 - int maxEdgeId() const {
5.86 + int maxUEdgeId() const {
5.87 return _edgeNum - 1;
5.88 }
5.89
5.90 @@ -634,10 +634,10 @@
5.91 return _bNodeNum;
5.92 }
5.93
5.94 - Node aNode(const Edge& edge) const {
5.95 + Node aNode(const UEdge& edge) const {
5.96 return Node((edge.id / _bNodeNum) << 1);
5.97 }
5.98 - Node bNode(const Edge& edge) const {
5.99 + Node bNode(const UEdge& edge) const {
5.100 return Node(((edge.id % _bNodeNum) << 1) + 1);
5.101 }
5.102
5.103 @@ -663,13 +663,12 @@
5.104 int bNodeNum() const { return _bNodeNum; }
5.105
5.106 typedef True EdgeNumTag;
5.107 - int edgeNum() const { return _edgeNum; }
5.108 + int uEdgeNum() const { return _edgeNum; }
5.109
5.110 };
5.111
5.112
5.113 - typedef BpUGraphExtender< BpUGraphBaseExtender<
5.114 - FullBpUGraphBase> > ExtendedFullBpUGraphBase;
5.115 + typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
5.116
5.117
5.118 /// \ingroup graphs
6.1 --- a/lemon/grid_ugraph.h Tue May 09 14:28:02 2006 +0000
6.2 +++ b/lemon/grid_ugraph.h Fri May 12 09:51:45 2006 +0000
6.3 @@ -347,8 +347,8 @@
6.4 };
6.5
6.6
6.7 - typedef UGraphExtender<UGraphBaseExtender<
6.8 - GridUGraphBase> > ExtendedGridUGraphBase;
6.9 + typedef UGraphExtender<UndirGraphExtender<GridUGraphBase> >
6.10 + ExtendedGridUGraphBase;
6.11
6.12 /// \ingroup graphs
6.13 ///
7.1 --- a/lemon/list_graph.h Tue May 09 14:28:02 2006 +0000
7.2 +++ b/lemon/list_graph.h Fri May 12 09:51:45 2006 +0000
7.3 @@ -566,8 +566,8 @@
7.4
7.5 /**************** Undirected List Graph ****************/
7.6
7.7 - typedef UGraphExtender<UGraphBaseExtender<
7.8 - ListGraphBase> > ExtendedListUGraphBase;
7.9 + typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
7.10 + ExtendedListUGraphBase;
7.11
7.12 /// \addtogroup graphs
7.13 /// @{
7.14 @@ -651,7 +651,7 @@
7.15 int first_edge, next_node;
7.16 };
7.17
7.18 - struct EdgeT {
7.19 + struct UEdgeT {
7.20 int aNode, prev_out, next_out;
7.21 int bNode, prev_in, next_in;
7.22 };
7.23 @@ -659,7 +659,7 @@
7.24 std::vector<NodeT> aNodes;
7.25 std::vector<NodeT> bNodes;
7.26
7.27 - std::vector<EdgeT> edges;
7.28 + std::vector<UEdgeT> edges;
7.29
7.30 int first_anode;
7.31 int first_free_anode;
7.32 @@ -685,18 +685,18 @@
7.33 bool operator<(const Node i) const {return id<i.id;}
7.34 };
7.35
7.36 - class Edge {
7.37 + class UEdge {
7.38 friend class ListBpUGraphBase;
7.39 protected:
7.40 int id;
7.41
7.42 - explicit Edge(int _id) { id = _id;}
7.43 + explicit UEdge(int _id) { id = _id;}
7.44 public:
7.45 - Edge() {}
7.46 - Edge (Invalid) { id = -1; }
7.47 - bool operator==(const Edge i) const {return id==i.id;}
7.48 - bool operator!=(const Edge i) const {return id!=i.id;}
7.49 - bool operator<(const Edge i) const {return id<i.id;}
7.50 + UEdge() {}
7.51 + UEdge (Invalid) { id = -1; }
7.52 + bool operator==(const UEdge i) const {return id==i.id;}
7.53 + bool operator!=(const UEdge i) const {return id!=i.id;}
7.54 + bool operator<(const UEdge i) const {return id<i.id;}
7.55 };
7.56
7.57 ListBpUGraphBase()
7.58 @@ -740,7 +740,7 @@
7.59 }
7.60 }
7.61
7.62 - void first(Edge& edge) const {
7.63 + void first(UEdge& edge) const {
7.64 int aNodeId = first_anode;
7.65 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
7.66 aNodeId = aNodes[aNodeId].next_node != -1 ?
7.67 @@ -752,7 +752,7 @@
7.68 edge.id = -1;
7.69 }
7.70 }
7.71 - void next(Edge& edge) const {
7.72 + void next(UEdge& edge) const {
7.73 int aNodeId = edges[edge.id].aNode >> 1;
7.74 edge.id = edges[edge.id].next_out;
7.75 if (edge.id == -1) {
7.76 @@ -770,19 +770,19 @@
7.77 }
7.78 }
7.79
7.80 - void firstOut(Edge& edge, const Node& node) const {
7.81 + void firstFromANode(UEdge& edge, const Node& node) const {
7.82 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
7.83 edge.id = aNodes[node.id >> 1].first_edge;
7.84 }
7.85 - void nextOut(Edge& edge) const {
7.86 + void nextFromANode(UEdge& edge) const {
7.87 edge.id = edges[edge.id].next_out;
7.88 }
7.89
7.90 - void firstIn(Edge& edge, const Node& node) const {
7.91 + void firstFromBNode(UEdge& edge, const Node& node) const {
7.92 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
7.93 edge.id = bNodes[node.id >> 1].first_edge;
7.94 }
7.95 - void nextIn(Edge& edge) const {
7.96 + void nextFromBNode(UEdge& edge) const {
7.97 edge.id = edges[edge.id].next_in;
7.98 }
7.99
7.100 @@ -797,13 +797,13 @@
7.101 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
7.102 }
7.103
7.104 - static int id(const Edge& edge) {
7.105 + static int id(const UEdge& edge) {
7.106 return edge.id;
7.107 }
7.108 - static Edge edgeFromId(int id) {
7.109 - return Edge(id);
7.110 + static UEdge uEdgeFromId(int id) {
7.111 + return UEdge(id);
7.112 }
7.113 - int maxEdgeId() const {
7.114 + int maxUEdgeId() const {
7.115 return edges.size();
7.116 }
7.117
7.118 @@ -827,10 +827,10 @@
7.119 return bNodes.size();
7.120 }
7.121
7.122 - Node aNode(const Edge& edge) const {
7.123 + Node aNode(const UEdge& edge) const {
7.124 return Node(edges[edge.id].aNode);
7.125 }
7.126 - Node bNode(const Edge& edge) const {
7.127 + Node bNode(const UEdge& edge) const {
7.128 return Node(edges[edge.id].bNode);
7.129 }
7.130
7.131 @@ -874,7 +874,7 @@
7.132 return Node((bNodeId << 1) + 1);
7.133 }
7.134
7.135 - Edge addEdge(const Node& source, const Node& target) {
7.136 + UEdge addEdge(const Node& source, const Node& target) {
7.137 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
7.138 int edgeId;
7.139 if (first_free_edge != -1) {
7.140 @@ -882,7 +882,7 @@
7.141 first_free_edge = edges[edgeId].next_out;
7.142 } else {
7.143 edgeId = edges.size();
7.144 - edges.push_back(EdgeT());
7.145 + edges.push_back(UEdgeT());
7.146 }
7.147 if ((source.id & 1) == 0) {
7.148 edges[edgeId].aNode = source.id;
7.149 @@ -903,7 +903,7 @@
7.150 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
7.151 }
7.152 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
7.153 - return Edge(edgeId);
7.154 + return UEdge(edgeId);
7.155 }
7.156
7.157 void erase(const Node& node) {
7.158 @@ -918,7 +918,7 @@
7.159 }
7.160 }
7.161
7.162 - void erase(const Edge& edge) {
7.163 + void erase(const UEdge& edge) {
7.164 if (edges[edge.id].prev_out != -1) {
7.165 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
7.166 } else {
7.167 @@ -953,8 +953,7 @@
7.168 };
7.169
7.170
7.171 - typedef BpUGraphExtender< BpUGraphBaseExtender<
7.172 - ListBpUGraphBase> > ExtendedListBpUGraphBase;
7.173 + typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
7.174
7.175 /// \ingroup graphs
7.176 ///
8.1 --- a/lemon/smart_graph.h Tue May 09 14:28:02 2006 +0000
8.2 +++ b/lemon/smart_graph.h Fri May 12 09:51:45 2006 +0000
8.3 @@ -119,8 +119,16 @@
8.4 ///\return The ID of the edge \c e.
8.5 static int id(Edge e) { return e.n; }
8.6
8.7 + /// \brief Returns the node from its \c id.
8.8 + ///
8.9 + /// Returns the node from its \c id. If there is not node
8.10 + /// with the given id the effect of the function is undefinied.
8.11 static Node nodeFromId(int id) { return Node(id);}
8.12
8.13 + /// \brief Returns the edge from its \c id.
8.14 + ///
8.15 + /// Returns the edge from its \c id. If there is not edge
8.16 + /// with the given id the effect of the function is undefinied.
8.17 static Edge edgeFromId(int id) { return Edge(id);}
8.18
8.19 Node addNode() {
8.20 @@ -350,7 +358,7 @@
8.21
8.22 /**************** Undirected List Graph ****************/
8.23
8.24 - typedef UGraphExtender<UGraphBaseExtender<SmartGraphBase> >
8.25 + typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
8.26 ExtendedSmartUGraphBase;
8.27
8.28 /// \ingroup graphs
8.29 @@ -388,7 +396,7 @@
8.30 NodeT(int _first) : first(_first) {}
8.31 };
8.32
8.33 - struct EdgeT {
8.34 + struct UEdgeT {
8.35 int aNode, next_out;
8.36 int bNode, next_in;
8.37 };
8.38 @@ -396,7 +404,7 @@
8.39 std::vector<NodeT> aNodes;
8.40 std::vector<NodeT> bNodes;
8.41
8.42 - std::vector<EdgeT> edges;
8.43 + std::vector<UEdgeT> edges;
8.44
8.45 public:
8.46
8.47 @@ -414,18 +422,18 @@
8.48 bool operator<(const Node i) const {return id<i.id;}
8.49 };
8.50
8.51 - class Edge {
8.52 + class UEdge {
8.53 friend class SmartBpUGraphBase;
8.54 protected:
8.55 int id;
8.56
8.57 - Edge(int _id) { id = _id;}
8.58 + UEdge(int _id) { id = _id;}
8.59 public:
8.60 - Edge() {}
8.61 - Edge (Invalid) { id = -1; }
8.62 - bool operator==(const Edge i) const {return id==i.id;}
8.63 - bool operator!=(const Edge i) const {return id!=i.id;}
8.64 - bool operator<(const Edge i) const {return id<i.id;}
8.65 + UEdge() {}
8.66 + UEdge (Invalid) { id = -1; }
8.67 + bool operator==(const UEdge i) const {return id==i.id;}
8.68 + bool operator!=(const UEdge i) const {return id!=i.id;}
8.69 + bool operator<(const UEdge i) const {return id<i.id;}
8.70 };
8.71
8.72 void firstANode(Node& node) const {
8.73 @@ -458,26 +466,26 @@
8.74 }
8.75 }
8.76
8.77 - void first(Edge& edge) const {
8.78 + void first(UEdge& edge) const {
8.79 edge.id = edges.size() - 1;
8.80 }
8.81 - void next(Edge& edge) const {
8.82 + void next(UEdge& edge) const {
8.83 --edge.id;
8.84 }
8.85
8.86 - void firstOut(Edge& edge, const Node& node) const {
8.87 + void firstFromANode(UEdge& edge, const Node& node) const {
8.88 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
8.89 edge.id = aNodes[node.id >> 1].first;
8.90 }
8.91 - void nextOut(Edge& edge) const {
8.92 + void nextFromANode(UEdge& edge) const {
8.93 edge.id = edges[edge.id].next_out;
8.94 }
8.95
8.96 - void firstIn(Edge& edge, const Node& node) const {
8.97 + void firstFromBNode(UEdge& edge, const Node& node) const {
8.98 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
8.99 edge.id = bNodes[node.id >> 1].first;
8.100 }
8.101 - void nextIn(Edge& edge) const {
8.102 + void nextFromBNode(UEdge& edge) const {
8.103 edge.id = edges[edge.id].next_in;
8.104 }
8.105
8.106 @@ -492,13 +500,13 @@
8.107 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
8.108 }
8.109
8.110 - static int id(const Edge& edge) {
8.111 + static int id(const UEdge& edge) {
8.112 return edge.id;
8.113 }
8.114 - static Edge edgeFromId(int id) {
8.115 - return Edge(id);
8.116 + static UEdge uEdgeFromId(int id) {
8.117 + return UEdge(id);
8.118 }
8.119 - int maxEdgeId() const {
8.120 + int maxUEdgeId() const {
8.121 return edges.size();
8.122 }
8.123
8.124 @@ -522,10 +530,10 @@
8.125 return bNodes.size();
8.126 }
8.127
8.128 - Node aNode(const Edge& edge) const {
8.129 + Node aNode(const UEdge& edge) const {
8.130 return Node(edges[edge.id].aNode);
8.131 }
8.132 - Node bNode(const Edge& edge) const {
8.133 + Node bNode(const UEdge& edge) const {
8.134 return Node(edges[edge.id].bNode);
8.135 }
8.136
8.137 @@ -551,9 +559,9 @@
8.138 return Node(bNodes.size() * 2 - 1);
8.139 }
8.140
8.141 - Edge addEdge(const Node& source, const Node& target) {
8.142 + UEdge addEdge(const Node& source, const Node& target) {
8.143 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
8.144 - EdgeT edgeT;
8.145 + UEdgeT edgeT;
8.146 if ((source.id & 1) == 0) {
8.147 edgeT.aNode = source.id;
8.148 edgeT.bNode = target.id;
8.149 @@ -566,7 +574,7 @@
8.150 edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
8.151 bNodes[edgeT.bNode >> 1].first = edges.size();
8.152 edges.push_back(edgeT);
8.153 - return Edge(edges.size() - 1);
8.154 + return UEdge(edges.size() - 1);
8.155 }
8.156
8.157 void clear() {
8.158 @@ -581,13 +589,12 @@
8.159 int bNodeNum() const { return bNodes.size(); }
8.160
8.161 typedef True EdgeNumTag;
8.162 - int edgeNum() const { return edges.size(); }
8.163 + int uEdgeNum() const { return edges.size(); }
8.164
8.165 };
8.166
8.167
8.168 - typedef BpUGraphExtender< BpUGraphBaseExtender<
8.169 - SmartBpUGraphBase> > ExtendedSmartBpUGraphBase;
8.170 + typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
8.171
8.172 /// \ingroup graphs
8.173 ///