1.1 --- a/lemon/bits/edge_set_extender.h Fri Oct 19 13:50:13 2007 +0000
1.2 +++ b/lemon/bits/edge_set_extender.h Fri Oct 19 15:21:07 2007 +0000
1.3 @@ -590,8 +590,10 @@
1.4 UEdge addEdge(const Node& from, const Node& to) {
1.5 UEdge uedge = Parent::addEdge(from, to);
1.6 notifier(UEdge()).add(uedge);
1.7 - notifier(Edge()).add(Parent::direct(uedge, true));
1.8 - notifier(Edge()).add(Parent::direct(uedge, false));
1.9 + std::vector<Edge> edges;
1.10 + edges.push_back(Parent::direct(uedge, true));
1.11 + edges.push_back(Parent::direct(uedge, false));
1.12 + notifier(Edge()).add(edges);
1.13 return uedge;
1.14 }
1.15
1.16 @@ -602,8 +604,10 @@
1.17 }
1.18
1.19 void erase(const UEdge& uedge) {
1.20 - notifier(Edge()).erase(Parent::direct(uedge, true));
1.21 - notifier(Edge()).erase(Parent::direct(uedge, false));
1.22 + std::vector<Edge> edges;
1.23 + edges.push_back(Parent::direct(uedge, true));
1.24 + edges.push_back(Parent::direct(uedge, false));
1.25 + notifier(Edge()).erase(edges);
1.26 notifier(UEdge()).erase(uedge);
1.27 Parent::erase(uedge);
1.28 }
2.1 --- a/lemon/edge_set.h Fri Oct 19 13:50:13 2007 +0000
2.2 +++ b/lemon/edge_set.h Fri Oct 19 15:21:07 2007 +0000
2.3 @@ -241,8 +241,6 @@
2.4 /// this class. Its interface must conform to the \ref concepts::Graph
2.5 /// "Graph" concept.
2.6 ///
2.7 - /// In the edge extension and removing it conforms to the
2.8 - /// \ref concepts::Graph "Graph" concept.
2.9 template <typename _Graph>
2.10 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
2.11
2.12 @@ -320,6 +318,315 @@
2.13
2.14 };
2.15
2.16 + template <typename _Graph>
2.17 + class ListUEdgeSetBase {
2.18 + public:
2.19 +
2.20 + typedef _Graph Graph;
2.21 + typedef typename Graph::Node Node;
2.22 + typedef typename Graph::NodeIt NodeIt;
2.23 +
2.24 + protected:
2.25 +
2.26 + struct NodeT {
2.27 + int first_out;
2.28 + NodeT() : first_out(-1) {}
2.29 + };
2.30 +
2.31 + typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
2.32 +
2.33 + NodesImplBase* nodes;
2.34 +
2.35 + struct EdgeT {
2.36 + Node target;
2.37 + int prev_out, next_out;
2.38 + EdgeT() : prev_out(-1), next_out(-1) {}
2.39 + };
2.40 +
2.41 + std::vector<EdgeT> edges;
2.42 +
2.43 + int first_edge;
2.44 + int first_free_edge;
2.45 +
2.46 + const Graph* graph;
2.47 +
2.48 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
2.49 + graph = &_graph;
2.50 + nodes = &_nodes;
2.51 + }
2.52 +
2.53 + public:
2.54 +
2.55 + class UEdge {
2.56 + friend class ListUEdgeSetBase;
2.57 + protected:
2.58 +
2.59 + int id;
2.60 + explicit UEdge(int _id) { id = _id;}
2.61 +
2.62 + public:
2.63 + UEdge() {}
2.64 + UEdge (Invalid) { id = -1; }
2.65 + bool operator==(const UEdge& edge) const {return id == edge.id;}
2.66 + bool operator!=(const UEdge& edge) const {return id != edge.id;}
2.67 + bool operator<(const UEdge& edge) const {return id < edge.id;}
2.68 + };
2.69 +
2.70 + class Edge {
2.71 + friend class ListUEdgeSetBase;
2.72 + protected:
2.73 + Edge(int _id) : id(_id) {}
2.74 + int id;
2.75 + public:
2.76 + operator UEdge() const { return uEdgeFromId(id / 2); }
2.77 +
2.78 + Edge() {}
2.79 + Edge(Invalid) : id(-1) {}
2.80 + bool operator==(const Edge& edge) const { return id == edge.id; }
2.81 + bool operator!=(const Edge& edge) const { return id != edge.id; }
2.82 + bool operator<(const Edge& edge) const { return id < edge.id; }
2.83 + };
2.84 +
2.85 + ListUEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
2.86 +
2.87 + UEdge addEdge(const Node& u, const Node& v) {
2.88 + int n;
2.89 +
2.90 + if (first_free_edge == -1) {
2.91 + n = edges.size();
2.92 + edges.push_back(EdgeT());
2.93 + edges.push_back(EdgeT());
2.94 + } else {
2.95 + n = first_free_edge;
2.96 + first_free_edge = edges[n].next_out;
2.97 + }
2.98 +
2.99 + edges[n].target = u;
2.100 + edges[n | 1].target = v;
2.101 +
2.102 + edges[n].next_out = (*nodes)[v].first_out;
2.103 + if ((*nodes)[v].first_out != -1) {
2.104 + edges[(*nodes)[v].first_out].prev_out = n;
2.105 + }
2.106 + (*nodes)[v].first_out = n;
2.107 + edges[n].prev_out = -1;
2.108 +
2.109 + if ((*nodes)[u].first_out != -1) {
2.110 + edges[(*nodes)[u].first_out].prev_out = (n | 1);
2.111 + }
2.112 + edges[n | 1].next_out = (*nodes)[u].first_out;
2.113 + (*nodes)[u].first_out = (n | 1);
2.114 + edges[n | 1].prev_out = -1;
2.115 +
2.116 + return UEdge(n / 2);
2.117 + }
2.118 +
2.119 + void erase(const UEdge& edge) {
2.120 + int n = edge.id * 2;
2.121 +
2.122 + if (edges[n].next_out != -1) {
2.123 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
2.124 + }
2.125 +
2.126 + if (edges[n].prev_out != -1) {
2.127 + edges[edges[n].prev_out].next_out = edges[n].next_out;
2.128 + } else {
2.129 + (*nodes)[edges[n | 1].target].first_out = edges[n].next_out;
2.130 + }
2.131 +
2.132 + if (edges[n | 1].next_out != -1) {
2.133 + edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
2.134 + }
2.135 +
2.136 + if (edges[n | 1].prev_out != -1) {
2.137 + edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
2.138 + } else {
2.139 + (*nodes)[edges[n].target].first_out = edges[n | 1].next_out;
2.140 + }
2.141 +
2.142 + edges[n].next_out = first_free_edge;
2.143 + first_free_edge = n;
2.144 +
2.145 + }
2.146 +
2.147 + void clear() {
2.148 + Node node;
2.149 + for (first(node); node != INVALID; next(node)) {
2.150 + (*nodes)[node].first_out = -1;
2.151 + }
2.152 + edges.clear();
2.153 + first_edge = -1;
2.154 + first_free_edge = -1;
2.155 + }
2.156 +
2.157 + void first(Node& node) const {
2.158 + graph->first(node);
2.159 + }
2.160 +
2.161 + void next(Node& node) const {
2.162 + graph->next(node);
2.163 + }
2.164 +
2.165 + void first(Edge& edge) const {
2.166 + Node node;
2.167 + first(node);
2.168 + while (node != INVALID && (*nodes)[node].first_out == -1) {
2.169 + next(node);
2.170 + }
2.171 + edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
2.172 + }
2.173 +
2.174 + void next(Edge& edge) const {
2.175 + if (edges[edge.id].next_out != -1) {
2.176 + edge.id = edges[edge.id].next_out;
2.177 + } else {
2.178 + Node node = edges[edge.id ^ 1].target;
2.179 + next(node);
2.180 + while(node != INVALID && (*nodes)[node].first_out == -1) {
2.181 + next(node);
2.182 + }
2.183 + edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
2.184 + }
2.185 + }
2.186 +
2.187 + void first(UEdge& uedge) const {
2.188 + Node node;
2.189 + first(node);
2.190 + while (node != INVALID) {
2.191 + uedge.id = (*nodes)[node].first_out;
2.192 + while ((uedge.id & 1) != 1) {
2.193 + uedge.id = edges[uedge.id].next_out;
2.194 + }
2.195 + if (uedge.id != -1) {
2.196 + uedge.id /= 2;
2.197 + return;
2.198 + }
2.199 + next(node);
2.200 + }
2.201 + uedge.id = -1;
2.202 + }
2.203 +
2.204 + void next(UEdge& uedge) const {
2.205 + Node node = edges[uedge.id * 2].target;
2.206 + uedge.id = edges[(uedge.id * 2) | 1].next_out;
2.207 + while ((uedge.id & 1) != 1) {
2.208 + uedge.id = edges[uedge.id].next_out;
2.209 + }
2.210 + if (uedge.id != -1) {
2.211 + uedge.id /= 2;
2.212 + return;
2.213 + }
2.214 + next(node);
2.215 + while (node != INVALID) {
2.216 + uedge.id = (*nodes)[node].first_out;
2.217 + while ((uedge.id & 1) != 1) {
2.218 + uedge.id = edges[uedge.id].next_out;
2.219 + }
2.220 + if (uedge.id != -1) {
2.221 + uedge.id /= 2;
2.222 + return;
2.223 + }
2.224 + next(node);
2.225 + }
2.226 + uedge.id = -1;
2.227 + }
2.228 +
2.229 + void firstOut(Edge& edge, const Node& node) const {
2.230 + edge.id = (*nodes)[node].first_out;
2.231 + }
2.232 +
2.233 + void nextOut(Edge& edge) const {
2.234 + edge.id = edges[edge.id].next_out;
2.235 + }
2.236 +
2.237 + void firstIn(Edge& edge, const Node& node) const {
2.238 + edge.id = (((*nodes)[node].first_out) ^ 1);
2.239 + if (edge.id == -2) edge.id = -1;
2.240 + }
2.241 +
2.242 + void nextIn(Edge& edge) const {
2.243 + edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
2.244 + if (edge.id == -2) edge.id = -1;
2.245 + }
2.246 +
2.247 + void firstInc(UEdge &edge, bool& dir, const Node& node) const {
2.248 + int de = (*nodes)[node].first_out;
2.249 + if (de != -1 ) {
2.250 + edge.id = de / 2;
2.251 + dir = ((de & 1) == 1);
2.252 + } else {
2.253 + edge.id = -1;
2.254 + dir = true;
2.255 + }
2.256 + }
2.257 + void nextInc(UEdge &edge, bool& dir) const {
2.258 + int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out);
2.259 + if (de != -1 ) {
2.260 + edge.id = de / 2;
2.261 + dir = ((de & 1) == 1);
2.262 + } else {
2.263 + edge.id = -1;
2.264 + dir = true;
2.265 + }
2.266 + }
2.267 +
2.268 + static bool direction(Edge edge) {
2.269 + return (edge.id & 1) == 1;
2.270 + }
2.271 +
2.272 + static Edge direct(UEdge uedge, bool dir) {
2.273 + return Edge(uedge.id * 2 + (dir ? 1 : 0));
2.274 + }
2.275 +
2.276 + int id(const Node& node) const { return graph->id(node); }
2.277 + static int id(Edge e) { return e.id; }
2.278 + static int id(UEdge e) { return e.id; }
2.279 +
2.280 + Node nodeFromId(int id) const { return graph->nodeFromId(id); }
2.281 + static Edge edgeFromId(int id) { return Edge(id);}
2.282 + static UEdge uEdgeFromId(int id) { return UEdge(id);}
2.283 +
2.284 + int maxNodeId() const { return graph->maxNodeId(); };
2.285 + int maxUEdgeId() const { return edges.size() / 2 - 1; }
2.286 + int maxEdgeId() const { return edges.size()-1; }
2.287 +
2.288 + Node source(Edge e) const { return edges[e.id ^ 1].target; }
2.289 + Node target(Edge e) const { return edges[e.id].target; }
2.290 +
2.291 + Node source(UEdge e) const { return edges[2 * e.id].target; }
2.292 + Node target(UEdge e) const { return edges[2 * e.id + 1].target; }
2.293 +
2.294 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
2.295 +
2.296 + NodeNotifier& notifier(Node) const {
2.297 + return graph->notifier(Node());
2.298 + }
2.299 +
2.300 + template <typename _Value>
2.301 + class NodeMap : public Graph::template NodeMap<_Value> {
2.302 + public:
2.303 +
2.304 + typedef typename _Graph::template NodeMap<_Value> Parent;
2.305 +
2.306 + explicit NodeMap(const ListUEdgeSetBase<Graph>& edgeset)
2.307 + : Parent(*edgeset.graph) {}
2.308 +
2.309 + NodeMap(const ListUEdgeSetBase<Graph>& edgeset, const _Value& value)
2.310 + : Parent(*edgeset.graph, value) {}
2.311 +
2.312 + NodeMap& operator=(const NodeMap& cmap) {
2.313 + return operator=<NodeMap>(cmap);
2.314 + }
2.315 +
2.316 + template <typename CMap>
2.317 + NodeMap& operator=(const CMap& cmap) {
2.318 + Parent::operator=(cmap);
2.319 + return *this;
2.320 + }
2.321 + };
2.322 +
2.323 + };
2.324 +
2.325 /// \ingroup semi_adaptors
2.326 ///
2.327 /// \brief Graph using a node set of another graph and an
2.328 @@ -336,13 +643,11 @@
2.329 /// In the edge extension and removing it conforms to the
2.330 /// \ref concepts::UGraph "UGraph" concept.
2.331 template <typename _Graph>
2.332 - class ListUEdgeSet
2.333 - : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
2.334 + class ListUEdgeSet : public UEdgeSetExtender<ListUEdgeSetBase<_Graph> > {
2.335
2.336 public:
2.337
2.338 - typedef UEdgeSetExtender<UndirGraphExtender<
2.339 - ListEdgeSetBase<_Graph> > > Parent;
2.340 + typedef UEdgeSetExtender<ListUEdgeSetBase<_Graph> > Parent;
2.341
2.342 typedef typename Parent::Node Node;
2.343 typedef typename Parent::Edge Edge;
2.344 @@ -661,6 +966,220 @@
2.345
2.346 };
2.347
2.348 +
2.349 + template <typename _Graph>
2.350 + class SmartUEdgeSetBase {
2.351 + public:
2.352 +
2.353 + typedef _Graph Graph;
2.354 + typedef typename Graph::Node Node;
2.355 + typedef typename Graph::NodeIt NodeIt;
2.356 +
2.357 + protected:
2.358 +
2.359 + struct NodeT {
2.360 + int first_out;
2.361 + NodeT() : first_out(-1) {}
2.362 + };
2.363 +
2.364 + typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
2.365 +
2.366 + NodesImplBase* nodes;
2.367 +
2.368 + struct EdgeT {
2.369 + Node target;
2.370 + int next_out;
2.371 + EdgeT() {}
2.372 + };
2.373 +
2.374 + std::vector<EdgeT> edges;
2.375 +
2.376 + const Graph* graph;
2.377 +
2.378 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
2.379 + graph = &_graph;
2.380 + nodes = &_nodes;
2.381 + }
2.382 +
2.383 + public:
2.384 +
2.385 + class UEdge {
2.386 + friend class SmartUEdgeSetBase;
2.387 + protected:
2.388 +
2.389 + int id;
2.390 + explicit UEdge(int _id) { id = _id;}
2.391 +
2.392 + public:
2.393 + UEdge() {}
2.394 + UEdge (Invalid) { id = -1; }
2.395 + bool operator==(const UEdge& edge) const {return id == edge.id;}
2.396 + bool operator!=(const UEdge& edge) const {return id != edge.id;}
2.397 + bool operator<(const UEdge& edge) const {return id < edge.id;}
2.398 + };
2.399 +
2.400 + class Edge {
2.401 + friend class SmartUEdgeSetBase;
2.402 + protected:
2.403 + Edge(int _id) : id(_id) {}
2.404 + int id;
2.405 + public:
2.406 + operator UEdge() const { return uEdgeFromId(id / 2); }
2.407 +
2.408 + Edge() {}
2.409 + Edge(Invalid) : id(-1) {}
2.410 + bool operator==(const Edge& edge) const { return id == edge.id; }
2.411 + bool operator!=(const Edge& edge) const { return id != edge.id; }
2.412 + bool operator<(const Edge& edge) const { return id < edge.id; }
2.413 + };
2.414 +
2.415 + SmartUEdgeSetBase() {}
2.416 +
2.417 + UEdge addEdge(const Node& u, const Node& v) {
2.418 + int n = edges.size();
2.419 + edges.push_back(EdgeT());
2.420 + edges.push_back(EdgeT());
2.421 +
2.422 + edges[n].target = u;
2.423 + edges[n | 1].target = v;
2.424 +
2.425 + edges[n].next_out = (*nodes)[v].first_out;
2.426 + (*nodes)[v].first_out = n;
2.427 +
2.428 + edges[n | 1].next_out = (*nodes)[u].first_out;
2.429 + (*nodes)[u].first_out = (n | 1);
2.430 +
2.431 + return UEdge(n / 2);
2.432 + }
2.433 +
2.434 + void clear() {
2.435 + Node node;
2.436 + for (first(node); node != INVALID; next(node)) {
2.437 + (*nodes)[node].first_out = -1;
2.438 + }
2.439 + edges.clear();
2.440 + }
2.441 +
2.442 + void first(Node& node) const {
2.443 + graph->first(node);
2.444 + }
2.445 +
2.446 + void next(Node& node) const {
2.447 + graph->next(node);
2.448 + }
2.449 +
2.450 + void first(Edge& edge) const {
2.451 + edge.id = edges.size() - 1;
2.452 + }
2.453 +
2.454 + void next(Edge& edge) const {
2.455 + --edge.id;
2.456 + }
2.457 +
2.458 + void first(UEdge& edge) const {
2.459 + edge.id = edges.size() / 2 - 1;
2.460 + }
2.461 +
2.462 + void next(UEdge& edge) const {
2.463 + --edge.id;
2.464 + }
2.465 +
2.466 + void firstOut(Edge& edge, const Node& node) const {
2.467 + edge.id = (*nodes)[node].first_out;
2.468 + }
2.469 +
2.470 + void nextOut(Edge& edge) const {
2.471 + edge.id = edges[edge.id].next_out;
2.472 + }
2.473 +
2.474 + void firstIn(Edge& edge, const Node& node) const {
2.475 + edge.id = (((*nodes)[node].first_out) ^ 1);
2.476 + if (edge.id == -2) edge.id = -1;
2.477 + }
2.478 +
2.479 + void nextIn(Edge& edge) const {
2.480 + edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
2.481 + if (edge.id == -2) edge.id = -1;
2.482 + }
2.483 +
2.484 + void firstInc(UEdge &edge, bool& dir, const Node& node) const {
2.485 + int de = (*nodes)[node].first_out;
2.486 + if (de != -1 ) {
2.487 + edge.id = de / 2;
2.488 + dir = ((de & 1) == 1);
2.489 + } else {
2.490 + edge.id = -1;
2.491 + dir = true;
2.492 + }
2.493 + }
2.494 + void nextInc(UEdge &edge, bool& dir) const {
2.495 + int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out);
2.496 + if (de != -1 ) {
2.497 + edge.id = de / 2;
2.498 + dir = ((de & 1) == 1);
2.499 + } else {
2.500 + edge.id = -1;
2.501 + dir = true;
2.502 + }
2.503 + }
2.504 +
2.505 + static bool direction(Edge edge) {
2.506 + return (edge.id & 1) == 1;
2.507 + }
2.508 +
2.509 + static Edge direct(UEdge uedge, bool dir) {
2.510 + return Edge(uedge.id * 2 + (dir ? 1 : 0));
2.511 + }
2.512 +
2.513 + int id(Node node) const { return graph->id(node); }
2.514 + static int id(Edge edge) { return edge.id; }
2.515 + static int id(UEdge edge) { return edge.id; }
2.516 +
2.517 + Node nodeFromId(int id) const { return graph->nodeFromId(id); }
2.518 + static Edge edgeFromId(int id) { return Edge(id); }
2.519 + static UEdge uEdgeFromId(int id) { return UEdge(id);}
2.520 +
2.521 + int maxNodeId() const { return graph->maxNodeId(); };
2.522 + int maxEdgeId() const { return edges.size() - 1; }
2.523 + int maxUEdgeId() const { return edges.size() / 2 - 1; }
2.524 +
2.525 + Node source(Edge e) const { return edges[e.id ^ 1].target; }
2.526 + Node target(Edge e) const { return edges[e.id].target; }
2.527 +
2.528 + Node source(UEdge e) const { return edges[2 * e.id].target; }
2.529 + Node target(UEdge e) const { return edges[2 * e.id + 1].target; }
2.530 +
2.531 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
2.532 +
2.533 + NodeNotifier& notifier(Node) const {
2.534 + return graph->notifier(Node());
2.535 + }
2.536 +
2.537 + template <typename _Value>
2.538 + class NodeMap : public Graph::template NodeMap<_Value> {
2.539 + public:
2.540 +
2.541 + typedef typename _Graph::template NodeMap<_Value> Parent;
2.542 +
2.543 + explicit NodeMap(const SmartUEdgeSetBase<Graph>& edgeset)
2.544 + : Parent(*edgeset.graph) { }
2.545 +
2.546 + NodeMap(const SmartUEdgeSetBase<Graph>& edgeset, const _Value& value)
2.547 + : Parent(*edgeset.graph, value) { }
2.548 +
2.549 + NodeMap& operator=(const NodeMap& cmap) {
2.550 + return operator=<NodeMap>(cmap);
2.551 + }
2.552 +
2.553 + template <typename CMap>
2.554 + NodeMap& operator=(const CMap& cmap) {
2.555 + Parent::operator=(cmap);
2.556 + return *this;
2.557 + }
2.558 + };
2.559 +
2.560 + };
2.561 +
2.562 /// \ingroup semi_adaptors
2.563 ///
2.564 /// \brief Graph using a node set of another graph and an
2.565 @@ -677,13 +1196,11 @@
2.566 /// In the edge extension and removing it conforms to the
2.567 /// \ref concepts::UGraph "UGraph" concept.
2.568 template <typename _Graph>
2.569 - class SmartUEdgeSet
2.570 - : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
2.571 + class SmartUEdgeSet : public UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > {
2.572
2.573 public:
2.574
2.575 - typedef UEdgeSetExtender<UndirGraphExtender<
2.576 - SmartEdgeSetBase<_Graph> > > Parent;
2.577 + typedef UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > Parent;
2.578
2.579 typedef typename Parent::Node Node;
2.580 typedef typename Parent::Edge Edge;
3.1 --- a/lemon/list_graph.h Fri Oct 19 13:50:13 2007 +0000
3.2 +++ b/lemon/list_graph.h Fri Oct 19 15:21:07 2007 +0000
3.3 @@ -977,17 +977,17 @@
3.4 edges[n | 1].target = v.id;
3.5
3.6 edges[n].next_out = nodes[v.id].first_out;
3.7 - edges[n | 1].next_out = nodes[u.id].first_out;
3.8 if (nodes[v.id].first_out != -1) {
3.9 edges[nodes[v.id].first_out].prev_out = n;
3.10 - }
3.11 + }
3.12 + edges[n].prev_out = -1;
3.13 + nodes[v.id].first_out = n;
3.14 +
3.15 + edges[n | 1].next_out = nodes[u.id].first_out;
3.16 if (nodes[u.id].first_out != -1) {
3.17 edges[nodes[u.id].first_out].prev_out = (n | 1);
3.18 }
3.19 -
3.20 - edges[n].prev_out = edges[n | 1].prev_out = -1;
3.21 -
3.22 - nodes[v.id].first_out = n;
3.23 + edges[n | 1].prev_out = -1;
3.24 nodes[u.id].first_out = (n | 1);
3.25
3.26 return UEdge(n / 2);
4.1 --- a/lemon/smart_graph.h Fri Oct 19 13:50:13 2007 +0000
4.2 +++ b/lemon/smart_graph.h Fri Oct 19 15:21:07 2007 +0000
4.3 @@ -185,10 +185,10 @@
4.4
4.5 typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
4.6
4.7 - /// \ingroup graphs
4.8 -
4.9 - ///A smart graph class.
4.10 -
4.11 + ///\ingroup graphs
4.12 + ///
4.13 + ///\brief A smart graph class.
4.14 + ///
4.15 ///This is a simple and fast graph implementation.
4.16 ///It is also quite memory efficient, but at the price
4.17 ///that <b> it does support only limited (only stack-like)
4.18 @@ -571,9 +571,9 @@
4.19 edges[n | 1].target = v.id;
4.20
4.21 edges[n].next_out = nodes[v.id].first_out;
4.22 - edges[n | 1].next_out = nodes[u.id].first_out;
4.23 -
4.24 nodes[v.id].first_out = n;
4.25 +
4.26 + edges[n | 1].next_out = nodes[u.id].first_out;
4.27 nodes[u.id].first_out = (n | 1);
4.28
4.29 return UEdge(n / 2);