COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/bits/graph_extender.h

    r1270 r1159  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    747747  };
    748748
    749   // \ingroup _graphbits
    750   //
    751   // \brief Extender for the BpGraphs
    752   template <typename Base>
    753   class BpGraphExtender : public Base {
    754     typedef Base Parent;
    755 
    756   public:
    757 
    758     typedef BpGraphExtender BpGraph;
    759 
    760     typedef True UndirectedTag;
    761 
    762     typedef typename Parent::Node Node;
    763     typedef typename Parent::RedNode RedNode;
    764     typedef typename Parent::BlueNode BlueNode;
    765     typedef typename Parent::Arc Arc;
    766     typedef typename Parent::Edge Edge;
    767 
    768     // BpGraph extension
    769 
    770     using Parent::first;
    771     using Parent::next;
    772     using Parent::id;
    773 
    774     int maxId(Node) const {
    775       return Parent::maxNodeId();
    776     }
    777 
    778     int maxId(RedNode) const {
    779       return Parent::maxRedId();
    780     }
    781 
    782     int maxId(BlueNode) const {
    783       return Parent::maxBlueId();
    784     }
    785 
    786     int maxId(Arc) const {
    787       return Parent::maxArcId();
    788     }
    789 
    790     int maxId(Edge) const {
    791       return Parent::maxEdgeId();
    792     }
    793 
    794     static Node fromId(int id, Node) {
    795       return Parent::nodeFromId(id);
    796     }
    797 
    798     static Arc fromId(int id, Arc) {
    799       return Parent::arcFromId(id);
    800     }
    801 
    802     static Edge fromId(int id, Edge) {
    803       return Parent::edgeFromId(id);
    804     }
    805 
    806     Node u(Edge e) const { return this->redNode(e); }
    807     Node v(Edge e) const { return this->blueNode(e); }
    808 
    809     Node oppositeNode(const Node &n, const Edge &e) const {
    810       if( n == u(e))
    811         return v(e);
    812       else if( n == v(e))
    813         return u(e);
    814       else
    815         return INVALID;
    816     }
    817 
    818     Arc oppositeArc(const Arc &arc) const {
    819       return Parent::direct(arc, !Parent::direction(arc));
    820     }
    821 
    822     using Parent::direct;
    823     Arc direct(const Edge &edge, const Node &node) const {
    824       return Parent::direct(edge, Parent::redNode(edge) == node);
    825     }
    826 
    827     RedNode asRedNode(const Node& node) const {
    828       if (node == INVALID || Parent::blue(node)) {
    829         return INVALID;
    830       } else {
    831         return Parent::asRedNodeUnsafe(node);
    832       }
    833     }
    834 
    835     BlueNode asBlueNode(const Node& node) const {
    836       if (node == INVALID || Parent::red(node)) {
    837         return INVALID;
    838       } else {
    839         return Parent::asBlueNodeUnsafe(node);
    840       }
    841     }
    842 
    843     // Alterable extension
    844 
    845     typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
    846     typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
    847     typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
    848     typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
    849     typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
    850 
    851 
    852   protected:
    853 
    854     mutable NodeNotifier node_notifier;
    855     mutable RedNodeNotifier red_node_notifier;
    856     mutable BlueNodeNotifier blue_node_notifier;
    857     mutable ArcNotifier arc_notifier;
    858     mutable EdgeNotifier edge_notifier;
    859 
    860   public:
    861 
    862     NodeNotifier& notifier(Node) const {
    863       return node_notifier;
    864     }
    865 
    866     RedNodeNotifier& notifier(RedNode) const {
    867       return red_node_notifier;
    868     }
    869 
    870     BlueNodeNotifier& notifier(BlueNode) const {
    871       return blue_node_notifier;
    872     }
    873 
    874     ArcNotifier& notifier(Arc) const {
    875       return arc_notifier;
    876     }
    877 
    878     EdgeNotifier& notifier(Edge) const {
    879       return edge_notifier;
    880     }
    881 
    882 
    883 
    884     class NodeIt : public Node {
    885       const BpGraph* _graph;
    886     public:
    887 
    888       NodeIt() {}
    889 
    890       NodeIt(Invalid i) : Node(i) { }
    891 
    892       explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
    893         _graph->first(static_cast<Node&>(*this));
    894       }
    895 
    896       NodeIt(const BpGraph& graph, const Node& node)
    897         : Node(node), _graph(&graph) {}
    898 
    899       NodeIt& operator++() {
    900         _graph->next(*this);
    901         return *this;
    902       }
    903 
    904     };
    905 
    906     class RedNodeIt : public RedNode {
    907       const BpGraph* _graph;
    908     public:
    909 
    910       RedNodeIt() {}
    911 
    912       RedNodeIt(Invalid i) : RedNode(i) { }
    913 
    914       explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
    915         _graph->first(static_cast<RedNode&>(*this));
    916       }
    917 
    918       RedNodeIt(const BpGraph& graph, const RedNode& node)
    919         : RedNode(node), _graph(&graph) {}
    920 
    921       RedNodeIt& operator++() {
    922         _graph->next(static_cast<RedNode&>(*this));
    923         return *this;
    924       }
    925 
    926     };
    927 
    928     class BlueNodeIt : public BlueNode {
    929       const BpGraph* _graph;
    930     public:
    931 
    932       BlueNodeIt() {}
    933 
    934       BlueNodeIt(Invalid i) : BlueNode(i) { }
    935 
    936       explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
    937         _graph->first(static_cast<BlueNode&>(*this));
    938       }
    939 
    940       BlueNodeIt(const BpGraph& graph, const BlueNode& node)
    941         : BlueNode(node), _graph(&graph) {}
    942 
    943       BlueNodeIt& operator++() {
    944         _graph->next(static_cast<BlueNode&>(*this));
    945         return *this;
    946       }
    947 
    948     };
    949 
    950 
    951     class ArcIt : public Arc {
    952       const BpGraph* _graph;
    953     public:
    954 
    955       ArcIt() { }
    956 
    957       ArcIt(Invalid i) : Arc(i) { }
    958 
    959       explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
    960         _graph->first(static_cast<Arc&>(*this));
    961       }
    962 
    963       ArcIt(const BpGraph& graph, const Arc& arc) :
    964         Arc(arc), _graph(&graph) { }
    965 
    966       ArcIt& operator++() {
    967         _graph->next(*this);
    968         return *this;
    969       }
    970 
    971     };
    972 
    973 
    974     class OutArcIt : public Arc {
    975       const BpGraph* _graph;
    976     public:
    977 
    978       OutArcIt() { }
    979 
    980       OutArcIt(Invalid i) : Arc(i) { }
    981 
    982       OutArcIt(const BpGraph& graph, const Node& node)
    983         : _graph(&graph) {
    984         _graph->firstOut(*this, node);
    985       }
    986 
    987       OutArcIt(const BpGraph& graph, const Arc& arc)
    988         : Arc(arc), _graph(&graph) {}
    989 
    990       OutArcIt& operator++() {
    991         _graph->nextOut(*this);
    992         return *this;
    993       }
    994 
    995     };
    996 
    997 
    998     class InArcIt : public Arc {
    999       const BpGraph* _graph;
    1000     public:
    1001 
    1002       InArcIt() { }
    1003 
    1004       InArcIt(Invalid i) : Arc(i) { }
    1005 
    1006       InArcIt(const BpGraph& graph, const Node& node)
    1007         : _graph(&graph) {
    1008         _graph->firstIn(*this, node);
    1009       }
    1010 
    1011       InArcIt(const BpGraph& graph, const Arc& arc) :
    1012         Arc(arc), _graph(&graph) {}
    1013 
    1014       InArcIt& operator++() {
    1015         _graph->nextIn(*this);
    1016         return *this;
    1017       }
    1018 
    1019     };
    1020 
    1021 
    1022     class EdgeIt : public Parent::Edge {
    1023       const BpGraph* _graph;
    1024     public:
    1025 
    1026       EdgeIt() { }
    1027 
    1028       EdgeIt(Invalid i) : Edge(i) { }
    1029 
    1030       explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
    1031         _graph->first(static_cast<Edge&>(*this));
    1032       }
    1033 
    1034       EdgeIt(const BpGraph& graph, const Edge& edge) :
    1035         Edge(edge), _graph(&graph) { }
    1036 
    1037       EdgeIt& operator++() {
    1038         _graph->next(*this);
    1039         return *this;
    1040       }
    1041 
    1042     };
    1043 
    1044     class IncEdgeIt : public Parent::Edge {
    1045       friend class BpGraphExtender;
    1046       const BpGraph* _graph;
    1047       bool _direction;
    1048     public:
    1049 
    1050       IncEdgeIt() { }
    1051 
    1052       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
    1053 
    1054       IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
    1055         _graph->firstInc(*this, _direction, node);
    1056       }
    1057 
    1058       IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
    1059         : _graph(&graph), Edge(edge) {
    1060         _direction = (_graph->source(edge) == node);
    1061       }
    1062 
    1063       IncEdgeIt& operator++() {
    1064         _graph->nextInc(*this, _direction);
    1065         return *this;
    1066       }
    1067     };
    1068 
    1069     // \brief Base node of the iterator
    1070     //
    1071     // Returns the base node (ie. the source in this case) of the iterator
    1072     Node baseNode(const OutArcIt &arc) const {
    1073       return Parent::source(static_cast<const Arc&>(arc));
    1074     }
    1075     // \brief Running node of the iterator
    1076     //
    1077     // Returns the running node (ie. the target in this case) of the
    1078     // iterator
    1079     Node runningNode(const OutArcIt &arc) const {
    1080       return Parent::target(static_cast<const Arc&>(arc));
    1081     }
    1082 
    1083     // \brief Base node of the iterator
    1084     //
    1085     // Returns the base node (ie. the target in this case) of the iterator
    1086     Node baseNode(const InArcIt &arc) const {
    1087       return Parent::target(static_cast<const Arc&>(arc));
    1088     }
    1089     // \brief Running node of the iterator
    1090     //
    1091     // Returns the running node (ie. the source in this case) of the
    1092     // iterator
    1093     Node runningNode(const InArcIt &arc) const {
    1094       return Parent::source(static_cast<const Arc&>(arc));
    1095     }
    1096 
    1097     // Base node of the iterator
    1098     //
    1099     // Returns the base node of the iterator
    1100     Node baseNode(const IncEdgeIt &edge) const {
    1101       return edge._direction ? this->u(edge) : this->v(edge);
    1102     }
    1103     // Running node of the iterator
    1104     //
    1105     // Returns the running node of the iterator
    1106     Node runningNode(const IncEdgeIt &edge) const {
    1107       return edge._direction ? this->v(edge) : this->u(edge);
    1108     }
    1109 
    1110     // Mappable extension
    1111 
    1112     template <typename _Value>
    1113     class NodeMap
    1114       : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
    1115       typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
    1116 
    1117     public:
    1118       explicit NodeMap(const BpGraph& bpgraph)
    1119         : Parent(bpgraph) {}
    1120       NodeMap(const BpGraph& bpgraph, const _Value& value)
    1121         : Parent(bpgraph, value) {}
    1122 
    1123     private:
    1124       NodeMap& operator=(const NodeMap& cmap) {
    1125         return operator=<NodeMap>(cmap);
    1126       }
    1127 
    1128       template <typename CMap>
    1129       NodeMap& operator=(const CMap& cmap) {
    1130         Parent::operator=(cmap);
    1131         return *this;
    1132       }
    1133 
    1134     };
    1135 
    1136     template <typename _Value>
    1137     class RedNodeMap
    1138       : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
    1139       typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
    1140 
    1141     public:
    1142       explicit RedNodeMap(const BpGraph& bpgraph)
    1143         : Parent(bpgraph) {}
    1144       RedNodeMap(const BpGraph& bpgraph, const _Value& value)
    1145         : Parent(bpgraph, value) {}
    1146 
    1147     private:
    1148       RedNodeMap& operator=(const RedNodeMap& cmap) {
    1149         return operator=<RedNodeMap>(cmap);
    1150       }
    1151 
    1152       template <typename CMap>
    1153       RedNodeMap& operator=(const CMap& cmap) {
    1154         Parent::operator=(cmap);
    1155         return *this;
    1156       }
    1157 
    1158     };
    1159 
    1160     template <typename _Value>
    1161     class BlueNodeMap
    1162       : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
    1163       typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
    1164 
    1165     public:
    1166       explicit BlueNodeMap(const BpGraph& bpgraph)
    1167         : Parent(bpgraph) {}
    1168       BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
    1169         : Parent(bpgraph, value) {}
    1170 
    1171     private:
    1172       BlueNodeMap& operator=(const BlueNodeMap& cmap) {
    1173         return operator=<BlueNodeMap>(cmap);
    1174       }
    1175 
    1176       template <typename CMap>
    1177       BlueNodeMap& operator=(const CMap& cmap) {
    1178         Parent::operator=(cmap);
    1179         return *this;
    1180       }
    1181 
    1182     };
    1183 
    1184     template <typename _Value>
    1185     class ArcMap
    1186       : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
    1187       typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
    1188 
    1189     public:
    1190       explicit ArcMap(const BpGraph& graph)
    1191         : Parent(graph) {}
    1192       ArcMap(const BpGraph& graph, const _Value& value)
    1193         : Parent(graph, value) {}
    1194 
    1195     private:
    1196       ArcMap& operator=(const ArcMap& cmap) {
    1197         return operator=<ArcMap>(cmap);
    1198       }
    1199 
    1200       template <typename CMap>
    1201       ArcMap& operator=(const CMap& cmap) {
    1202         Parent::operator=(cmap);
    1203         return *this;
    1204       }
    1205     };
    1206 
    1207 
    1208     template <typename _Value>
    1209     class EdgeMap
    1210       : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
    1211       typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
    1212 
    1213     public:
    1214       explicit EdgeMap(const BpGraph& graph)
    1215         : Parent(graph) {}
    1216 
    1217       EdgeMap(const BpGraph& graph, const _Value& value)
    1218         : Parent(graph, value) {}
    1219 
    1220     private:
    1221       EdgeMap& operator=(const EdgeMap& cmap) {
    1222         return operator=<EdgeMap>(cmap);
    1223       }
    1224 
    1225       template <typename CMap>
    1226       EdgeMap& operator=(const CMap& cmap) {
    1227         Parent::operator=(cmap);
    1228         return *this;
    1229       }
    1230 
    1231     };
    1232 
    1233     // Alteration extension
    1234 
    1235     RedNode addRedNode() {
    1236       RedNode node = Parent::addRedNode();
    1237       notifier(RedNode()).add(node);
    1238       notifier(Node()).add(node);
    1239       return node;
    1240     }
    1241 
    1242     BlueNode addBlueNode() {
    1243       BlueNode node = Parent::addBlueNode();
    1244       notifier(BlueNode()).add(node);
    1245       notifier(Node()).add(node);
    1246       return node;
    1247     }
    1248 
    1249     Edge addEdge(const RedNode& from, const BlueNode& to) {
    1250       Edge edge = Parent::addEdge(from, to);
    1251       notifier(Edge()).add(edge);
    1252       std::vector<Arc> av;
    1253       av.push_back(Parent::direct(edge, true));
    1254       av.push_back(Parent::direct(edge, false));
    1255       notifier(Arc()).add(av);
    1256       return edge;
    1257     }
    1258 
    1259     void clear() {
    1260       notifier(Arc()).clear();
    1261       notifier(Edge()).clear();
    1262       notifier(Node()).clear();
    1263       notifier(BlueNode()).clear();
    1264       notifier(RedNode()).clear();
    1265       Parent::clear();
    1266     }
    1267 
    1268     template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
    1269     void build(const BpGraph& graph, NodeRefMap& nodeRef,
    1270                EdgeRefMap& edgeRef) {
    1271       Parent::build(graph, nodeRef, edgeRef);
    1272       notifier(RedNode()).build();
    1273       notifier(BlueNode()).build();
    1274       notifier(Node()).build();
    1275       notifier(Edge()).build();
    1276       notifier(Arc()).build();
    1277     }
    1278 
    1279     void erase(const Node& node) {
    1280       Arc arc;
    1281       Parent::firstOut(arc, node);
    1282       while (arc != INVALID ) {
    1283         erase(arc);
    1284         Parent::firstOut(arc, node);
    1285       }
    1286 
    1287       Parent::firstIn(arc, node);
    1288       while (arc != INVALID ) {
    1289         erase(arc);
    1290         Parent::firstIn(arc, node);
    1291       }
    1292 
    1293       if (Parent::red(node)) {
    1294         notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
    1295       } else {
    1296         notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
    1297       }
    1298 
    1299       notifier(Node()).erase(node);
    1300       Parent::erase(node);
    1301     }
    1302 
    1303     void erase(const Edge& edge) {
    1304       std::vector<Arc> av;
    1305       av.push_back(Parent::direct(edge, true));
    1306       av.push_back(Parent::direct(edge, false));
    1307       notifier(Arc()).erase(av);
    1308       notifier(Edge()).erase(edge);
    1309       Parent::erase(edge);
    1310     }
    1311 
    1312     BpGraphExtender() {
    1313       red_node_notifier.setContainer(*this);
    1314       blue_node_notifier.setContainer(*this);
    1315       node_notifier.setContainer(*this);
    1316       arc_notifier.setContainer(*this);
    1317       edge_notifier.setContainer(*this);
    1318     }
    1319 
    1320     ~BpGraphExtender() {
    1321       edge_notifier.clear();
    1322       arc_notifier.clear();
    1323       node_notifier.clear();
    1324       blue_node_notifier.clear();
    1325       red_node_notifier.clear();
    1326     }
    1327 
    1328   };
    1329 
    1330749}
    1331750
Note: See TracChangeset for help on using the changeset viewer.