318 Parent::initalize(graph, nodes); |
316 Parent::initalize(graph, nodes); |
319 } |
317 } |
320 |
318 |
321 }; |
319 }; |
322 |
320 |
|
321 template <typename _Graph> |
|
322 class ListUEdgeSetBase { |
|
323 public: |
|
324 |
|
325 typedef _Graph Graph; |
|
326 typedef typename Graph::Node Node; |
|
327 typedef typename Graph::NodeIt NodeIt; |
|
328 |
|
329 protected: |
|
330 |
|
331 struct NodeT { |
|
332 int first_out; |
|
333 NodeT() : first_out(-1) {} |
|
334 }; |
|
335 |
|
336 typedef DefaultMap<Graph, Node, NodeT> NodesImplBase; |
|
337 |
|
338 NodesImplBase* nodes; |
|
339 |
|
340 struct EdgeT { |
|
341 Node target; |
|
342 int prev_out, next_out; |
|
343 EdgeT() : prev_out(-1), next_out(-1) {} |
|
344 }; |
|
345 |
|
346 std::vector<EdgeT> edges; |
|
347 |
|
348 int first_edge; |
|
349 int first_free_edge; |
|
350 |
|
351 const Graph* graph; |
|
352 |
|
353 void initalize(const Graph& _graph, NodesImplBase& _nodes) { |
|
354 graph = &_graph; |
|
355 nodes = &_nodes; |
|
356 } |
|
357 |
|
358 public: |
|
359 |
|
360 class UEdge { |
|
361 friend class ListUEdgeSetBase; |
|
362 protected: |
|
363 |
|
364 int id; |
|
365 explicit UEdge(int _id) { id = _id;} |
|
366 |
|
367 public: |
|
368 UEdge() {} |
|
369 UEdge (Invalid) { id = -1; } |
|
370 bool operator==(const UEdge& edge) const {return id == edge.id;} |
|
371 bool operator!=(const UEdge& edge) const {return id != edge.id;} |
|
372 bool operator<(const UEdge& edge) const {return id < edge.id;} |
|
373 }; |
|
374 |
|
375 class Edge { |
|
376 friend class ListUEdgeSetBase; |
|
377 protected: |
|
378 Edge(int _id) : id(_id) {} |
|
379 int id; |
|
380 public: |
|
381 operator UEdge() const { return uEdgeFromId(id / 2); } |
|
382 |
|
383 Edge() {} |
|
384 Edge(Invalid) : id(-1) {} |
|
385 bool operator==(const Edge& edge) const { return id == edge.id; } |
|
386 bool operator!=(const Edge& edge) const { return id != edge.id; } |
|
387 bool operator<(const Edge& edge) const { return id < edge.id; } |
|
388 }; |
|
389 |
|
390 ListUEdgeSetBase() : first_edge(-1), first_free_edge(-1) {} |
|
391 |
|
392 UEdge addEdge(const Node& u, const Node& v) { |
|
393 int n; |
|
394 |
|
395 if (first_free_edge == -1) { |
|
396 n = edges.size(); |
|
397 edges.push_back(EdgeT()); |
|
398 edges.push_back(EdgeT()); |
|
399 } else { |
|
400 n = first_free_edge; |
|
401 first_free_edge = edges[n].next_out; |
|
402 } |
|
403 |
|
404 edges[n].target = u; |
|
405 edges[n | 1].target = v; |
|
406 |
|
407 edges[n].next_out = (*nodes)[v].first_out; |
|
408 if ((*nodes)[v].first_out != -1) { |
|
409 edges[(*nodes)[v].first_out].prev_out = n; |
|
410 } |
|
411 (*nodes)[v].first_out = n; |
|
412 edges[n].prev_out = -1; |
|
413 |
|
414 if ((*nodes)[u].first_out != -1) { |
|
415 edges[(*nodes)[u].first_out].prev_out = (n | 1); |
|
416 } |
|
417 edges[n | 1].next_out = (*nodes)[u].first_out; |
|
418 (*nodes)[u].first_out = (n | 1); |
|
419 edges[n | 1].prev_out = -1; |
|
420 |
|
421 return UEdge(n / 2); |
|
422 } |
|
423 |
|
424 void erase(const UEdge& edge) { |
|
425 int n = edge.id * 2; |
|
426 |
|
427 if (edges[n].next_out != -1) { |
|
428 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
|
429 } |
|
430 |
|
431 if (edges[n].prev_out != -1) { |
|
432 edges[edges[n].prev_out].next_out = edges[n].next_out; |
|
433 } else { |
|
434 (*nodes)[edges[n | 1].target].first_out = edges[n].next_out; |
|
435 } |
|
436 |
|
437 if (edges[n | 1].next_out != -1) { |
|
438 edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out; |
|
439 } |
|
440 |
|
441 if (edges[n | 1].prev_out != -1) { |
|
442 edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out; |
|
443 } else { |
|
444 (*nodes)[edges[n].target].first_out = edges[n | 1].next_out; |
|
445 } |
|
446 |
|
447 edges[n].next_out = first_free_edge; |
|
448 first_free_edge = n; |
|
449 |
|
450 } |
|
451 |
|
452 void clear() { |
|
453 Node node; |
|
454 for (first(node); node != INVALID; next(node)) { |
|
455 (*nodes)[node].first_out = -1; |
|
456 } |
|
457 edges.clear(); |
|
458 first_edge = -1; |
|
459 first_free_edge = -1; |
|
460 } |
|
461 |
|
462 void first(Node& node) const { |
|
463 graph->first(node); |
|
464 } |
|
465 |
|
466 void next(Node& node) const { |
|
467 graph->next(node); |
|
468 } |
|
469 |
|
470 void first(Edge& edge) const { |
|
471 Node node; |
|
472 first(node); |
|
473 while (node != INVALID && (*nodes)[node].first_out == -1) { |
|
474 next(node); |
|
475 } |
|
476 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out; |
|
477 } |
|
478 |
|
479 void next(Edge& edge) const { |
|
480 if (edges[edge.id].next_out != -1) { |
|
481 edge.id = edges[edge.id].next_out; |
|
482 } else { |
|
483 Node node = edges[edge.id ^ 1].target; |
|
484 next(node); |
|
485 while(node != INVALID && (*nodes)[node].first_out == -1) { |
|
486 next(node); |
|
487 } |
|
488 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out; |
|
489 } |
|
490 } |
|
491 |
|
492 void first(UEdge& uedge) const { |
|
493 Node node; |
|
494 first(node); |
|
495 while (node != INVALID) { |
|
496 uedge.id = (*nodes)[node].first_out; |
|
497 while ((uedge.id & 1) != 1) { |
|
498 uedge.id = edges[uedge.id].next_out; |
|
499 } |
|
500 if (uedge.id != -1) { |
|
501 uedge.id /= 2; |
|
502 return; |
|
503 } |
|
504 next(node); |
|
505 } |
|
506 uedge.id = -1; |
|
507 } |
|
508 |
|
509 void next(UEdge& uedge) const { |
|
510 Node node = edges[uedge.id * 2].target; |
|
511 uedge.id = edges[(uedge.id * 2) | 1].next_out; |
|
512 while ((uedge.id & 1) != 1) { |
|
513 uedge.id = edges[uedge.id].next_out; |
|
514 } |
|
515 if (uedge.id != -1) { |
|
516 uedge.id /= 2; |
|
517 return; |
|
518 } |
|
519 next(node); |
|
520 while (node != INVALID) { |
|
521 uedge.id = (*nodes)[node].first_out; |
|
522 while ((uedge.id & 1) != 1) { |
|
523 uedge.id = edges[uedge.id].next_out; |
|
524 } |
|
525 if (uedge.id != -1) { |
|
526 uedge.id /= 2; |
|
527 return; |
|
528 } |
|
529 next(node); |
|
530 } |
|
531 uedge.id = -1; |
|
532 } |
|
533 |
|
534 void firstOut(Edge& edge, const Node& node) const { |
|
535 edge.id = (*nodes)[node].first_out; |
|
536 } |
|
537 |
|
538 void nextOut(Edge& edge) const { |
|
539 edge.id = edges[edge.id].next_out; |
|
540 } |
|
541 |
|
542 void firstIn(Edge& edge, const Node& node) const { |
|
543 edge.id = (((*nodes)[node].first_out) ^ 1); |
|
544 if (edge.id == -2) edge.id = -1; |
|
545 } |
|
546 |
|
547 void nextIn(Edge& edge) const { |
|
548 edge.id = ((edges[edge.id ^ 1].next_out) ^ 1); |
|
549 if (edge.id == -2) edge.id = -1; |
|
550 } |
|
551 |
|
552 void firstInc(UEdge &edge, bool& dir, const Node& node) const { |
|
553 int de = (*nodes)[node].first_out; |
|
554 if (de != -1 ) { |
|
555 edge.id = de / 2; |
|
556 dir = ((de & 1) == 1); |
|
557 } else { |
|
558 edge.id = -1; |
|
559 dir = true; |
|
560 } |
|
561 } |
|
562 void nextInc(UEdge &edge, bool& dir) const { |
|
563 int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out); |
|
564 if (de != -1 ) { |
|
565 edge.id = de / 2; |
|
566 dir = ((de & 1) == 1); |
|
567 } else { |
|
568 edge.id = -1; |
|
569 dir = true; |
|
570 } |
|
571 } |
|
572 |
|
573 static bool direction(Edge edge) { |
|
574 return (edge.id & 1) == 1; |
|
575 } |
|
576 |
|
577 static Edge direct(UEdge uedge, bool dir) { |
|
578 return Edge(uedge.id * 2 + (dir ? 1 : 0)); |
|
579 } |
|
580 |
|
581 int id(const Node& node) const { return graph->id(node); } |
|
582 static int id(Edge e) { return e.id; } |
|
583 static int id(UEdge e) { return e.id; } |
|
584 |
|
585 Node nodeFromId(int id) const { return graph->nodeFromId(id); } |
|
586 static Edge edgeFromId(int id) { return Edge(id);} |
|
587 static UEdge uEdgeFromId(int id) { return UEdge(id);} |
|
588 |
|
589 int maxNodeId() const { return graph->maxNodeId(); }; |
|
590 int maxUEdgeId() const { return edges.size() / 2 - 1; } |
|
591 int maxEdgeId() const { return edges.size()-1; } |
|
592 |
|
593 Node source(Edge e) const { return edges[e.id ^ 1].target; } |
|
594 Node target(Edge e) const { return edges[e.id].target; } |
|
595 |
|
596 Node source(UEdge e) const { return edges[2 * e.id].target; } |
|
597 Node target(UEdge e) const { return edges[2 * e.id + 1].target; } |
|
598 |
|
599 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; |
|
600 |
|
601 NodeNotifier& notifier(Node) const { |
|
602 return graph->notifier(Node()); |
|
603 } |
|
604 |
|
605 template <typename _Value> |
|
606 class NodeMap : public Graph::template NodeMap<_Value> { |
|
607 public: |
|
608 |
|
609 typedef typename _Graph::template NodeMap<_Value> Parent; |
|
610 |
|
611 explicit NodeMap(const ListUEdgeSetBase<Graph>& edgeset) |
|
612 : Parent(*edgeset.graph) {} |
|
613 |
|
614 NodeMap(const ListUEdgeSetBase<Graph>& edgeset, const _Value& value) |
|
615 : Parent(*edgeset.graph, value) {} |
|
616 |
|
617 NodeMap& operator=(const NodeMap& cmap) { |
|
618 return operator=<NodeMap>(cmap); |
|
619 } |
|
620 |
|
621 template <typename CMap> |
|
622 NodeMap& operator=(const CMap& cmap) { |
|
623 Parent::operator=(cmap); |
|
624 return *this; |
|
625 } |
|
626 }; |
|
627 |
|
628 }; |
|
629 |
323 /// \ingroup semi_adaptors |
630 /// \ingroup semi_adaptors |
324 /// |
631 /// |
325 /// \brief Graph using a node set of another graph and an |
632 /// \brief Graph using a node set of another graph and an |
326 /// own uedge set. |
633 /// own uedge set. |
327 /// |
634 /// |
659 return nodes.attached(); |
964 return nodes.attached(); |
660 } |
965 } |
661 |
966 |
662 }; |
967 }; |
663 |
968 |
|
969 |
|
970 template <typename _Graph> |
|
971 class SmartUEdgeSetBase { |
|
972 public: |
|
973 |
|
974 typedef _Graph Graph; |
|
975 typedef typename Graph::Node Node; |
|
976 typedef typename Graph::NodeIt NodeIt; |
|
977 |
|
978 protected: |
|
979 |
|
980 struct NodeT { |
|
981 int first_out; |
|
982 NodeT() : first_out(-1) {} |
|
983 }; |
|
984 |
|
985 typedef DefaultMap<Graph, Node, NodeT> NodesImplBase; |
|
986 |
|
987 NodesImplBase* nodes; |
|
988 |
|
989 struct EdgeT { |
|
990 Node target; |
|
991 int next_out; |
|
992 EdgeT() {} |
|
993 }; |
|
994 |
|
995 std::vector<EdgeT> edges; |
|
996 |
|
997 const Graph* graph; |
|
998 |
|
999 void initalize(const Graph& _graph, NodesImplBase& _nodes) { |
|
1000 graph = &_graph; |
|
1001 nodes = &_nodes; |
|
1002 } |
|
1003 |
|
1004 public: |
|
1005 |
|
1006 class UEdge { |
|
1007 friend class SmartUEdgeSetBase; |
|
1008 protected: |
|
1009 |
|
1010 int id; |
|
1011 explicit UEdge(int _id) { id = _id;} |
|
1012 |
|
1013 public: |
|
1014 UEdge() {} |
|
1015 UEdge (Invalid) { id = -1; } |
|
1016 bool operator==(const UEdge& edge) const {return id == edge.id;} |
|
1017 bool operator!=(const UEdge& edge) const {return id != edge.id;} |
|
1018 bool operator<(const UEdge& edge) const {return id < edge.id;} |
|
1019 }; |
|
1020 |
|
1021 class Edge { |
|
1022 friend class SmartUEdgeSetBase; |
|
1023 protected: |
|
1024 Edge(int _id) : id(_id) {} |
|
1025 int id; |
|
1026 public: |
|
1027 operator UEdge() const { return uEdgeFromId(id / 2); } |
|
1028 |
|
1029 Edge() {} |
|
1030 Edge(Invalid) : id(-1) {} |
|
1031 bool operator==(const Edge& edge) const { return id == edge.id; } |
|
1032 bool operator!=(const Edge& edge) const { return id != edge.id; } |
|
1033 bool operator<(const Edge& edge) const { return id < edge.id; } |
|
1034 }; |
|
1035 |
|
1036 SmartUEdgeSetBase() {} |
|
1037 |
|
1038 UEdge addEdge(const Node& u, const Node& v) { |
|
1039 int n = edges.size(); |
|
1040 edges.push_back(EdgeT()); |
|
1041 edges.push_back(EdgeT()); |
|
1042 |
|
1043 edges[n].target = u; |
|
1044 edges[n | 1].target = v; |
|
1045 |
|
1046 edges[n].next_out = (*nodes)[v].first_out; |
|
1047 (*nodes)[v].first_out = n; |
|
1048 |
|
1049 edges[n | 1].next_out = (*nodes)[u].first_out; |
|
1050 (*nodes)[u].first_out = (n | 1); |
|
1051 |
|
1052 return UEdge(n / 2); |
|
1053 } |
|
1054 |
|
1055 void clear() { |
|
1056 Node node; |
|
1057 for (first(node); node != INVALID; next(node)) { |
|
1058 (*nodes)[node].first_out = -1; |
|
1059 } |
|
1060 edges.clear(); |
|
1061 } |
|
1062 |
|
1063 void first(Node& node) const { |
|
1064 graph->first(node); |
|
1065 } |
|
1066 |
|
1067 void next(Node& node) const { |
|
1068 graph->next(node); |
|
1069 } |
|
1070 |
|
1071 void first(Edge& edge) const { |
|
1072 edge.id = edges.size() - 1; |
|
1073 } |
|
1074 |
|
1075 void next(Edge& edge) const { |
|
1076 --edge.id; |
|
1077 } |
|
1078 |
|
1079 void first(UEdge& edge) const { |
|
1080 edge.id = edges.size() / 2 - 1; |
|
1081 } |
|
1082 |
|
1083 void next(UEdge& edge) const { |
|
1084 --edge.id; |
|
1085 } |
|
1086 |
|
1087 void firstOut(Edge& edge, const Node& node) const { |
|
1088 edge.id = (*nodes)[node].first_out; |
|
1089 } |
|
1090 |
|
1091 void nextOut(Edge& edge) const { |
|
1092 edge.id = edges[edge.id].next_out; |
|
1093 } |
|
1094 |
|
1095 void firstIn(Edge& edge, const Node& node) const { |
|
1096 edge.id = (((*nodes)[node].first_out) ^ 1); |
|
1097 if (edge.id == -2) edge.id = -1; |
|
1098 } |
|
1099 |
|
1100 void nextIn(Edge& edge) const { |
|
1101 edge.id = ((edges[edge.id ^ 1].next_out) ^ 1); |
|
1102 if (edge.id == -2) edge.id = -1; |
|
1103 } |
|
1104 |
|
1105 void firstInc(UEdge &edge, bool& dir, const Node& node) const { |
|
1106 int de = (*nodes)[node].first_out; |
|
1107 if (de != -1 ) { |
|
1108 edge.id = de / 2; |
|
1109 dir = ((de & 1) == 1); |
|
1110 } else { |
|
1111 edge.id = -1; |
|
1112 dir = true; |
|
1113 } |
|
1114 } |
|
1115 void nextInc(UEdge &edge, bool& dir) const { |
|
1116 int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out); |
|
1117 if (de != -1 ) { |
|
1118 edge.id = de / 2; |
|
1119 dir = ((de & 1) == 1); |
|
1120 } else { |
|
1121 edge.id = -1; |
|
1122 dir = true; |
|
1123 } |
|
1124 } |
|
1125 |
|
1126 static bool direction(Edge edge) { |
|
1127 return (edge.id & 1) == 1; |
|
1128 } |
|
1129 |
|
1130 static Edge direct(UEdge uedge, bool dir) { |
|
1131 return Edge(uedge.id * 2 + (dir ? 1 : 0)); |
|
1132 } |
|
1133 |
|
1134 int id(Node node) const { return graph->id(node); } |
|
1135 static int id(Edge edge) { return edge.id; } |
|
1136 static int id(UEdge edge) { return edge.id; } |
|
1137 |
|
1138 Node nodeFromId(int id) const { return graph->nodeFromId(id); } |
|
1139 static Edge edgeFromId(int id) { return Edge(id); } |
|
1140 static UEdge uEdgeFromId(int id) { return UEdge(id);} |
|
1141 |
|
1142 int maxNodeId() const { return graph->maxNodeId(); }; |
|
1143 int maxEdgeId() const { return edges.size() - 1; } |
|
1144 int maxUEdgeId() const { return edges.size() / 2 - 1; } |
|
1145 |
|
1146 Node source(Edge e) const { return edges[e.id ^ 1].target; } |
|
1147 Node target(Edge e) const { return edges[e.id].target; } |
|
1148 |
|
1149 Node source(UEdge e) const { return edges[2 * e.id].target; } |
|
1150 Node target(UEdge e) const { return edges[2 * e.id + 1].target; } |
|
1151 |
|
1152 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; |
|
1153 |
|
1154 NodeNotifier& notifier(Node) const { |
|
1155 return graph->notifier(Node()); |
|
1156 } |
|
1157 |
|
1158 template <typename _Value> |
|
1159 class NodeMap : public Graph::template NodeMap<_Value> { |
|
1160 public: |
|
1161 |
|
1162 typedef typename _Graph::template NodeMap<_Value> Parent; |
|
1163 |
|
1164 explicit NodeMap(const SmartUEdgeSetBase<Graph>& edgeset) |
|
1165 : Parent(*edgeset.graph) { } |
|
1166 |
|
1167 NodeMap(const SmartUEdgeSetBase<Graph>& edgeset, const _Value& value) |
|
1168 : Parent(*edgeset.graph, value) { } |
|
1169 |
|
1170 NodeMap& operator=(const NodeMap& cmap) { |
|
1171 return operator=<NodeMap>(cmap); |
|
1172 } |
|
1173 |
|
1174 template <typename CMap> |
|
1175 NodeMap& operator=(const CMap& cmap) { |
|
1176 Parent::operator=(cmap); |
|
1177 return *this; |
|
1178 } |
|
1179 }; |
|
1180 |
|
1181 }; |
|
1182 |
664 /// \ingroup semi_adaptors |
1183 /// \ingroup semi_adaptors |
665 /// |
1184 /// |
666 /// \brief Graph using a node set of another graph and an |
1185 /// \brief Graph using a node set of another graph and an |
667 /// own uedge set. |
1186 /// own uedge set. |
668 /// |
1187 /// |