Changeset 1187:4c89e925cfe2 in lemon for lemon
 Timestamp:
 11/14/10 20:06:23 (9 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 lemon
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bits/graph_extender.h
r1159 r1187 747 747 }; 748 748 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::Arc Arc; 764 typedef typename Parent::Edge Edge; 765 766 // BpGraph extension 767 768 class RedNode : public Node { 769 public: 770 RedNode() {} 771 RedNode(const RedNode& node) : Node(node) {} 772 RedNode(Invalid) : Node(INVALID){} 773 RedNode(const Node& node) : Node(node) {} 774 }; 775 class BlueNode : public Node { 776 public: 777 BlueNode() {} 778 BlueNode(const BlueNode& node) : Node(node) {} 779 BlueNode(Invalid) : Node(INVALID){} 780 BlueNode(const Node& node) : Node(node) {} 781 }; 782 783 using Parent::first; 784 using Parent::next; 785 786 void first(RedNode& node) const { 787 Parent::firstRed(node); 788 } 789 790 void next(RedNode& node) const { 791 Parent::nextRed(node); 792 } 793 794 void first(BlueNode& node) const { 795 Parent::firstBlue(node); 796 } 797 798 void next(BlueNode& node) const { 799 Parent::nextBlue(node); 800 } 801 802 using Parent::id; 803 804 int id(const RedNode& node) const { 805 return Parent::redId(node); 806 } 807 808 int id(const BlueNode& node) const { 809 return Parent::blueId(node); 810 } 811 812 int maxId(Node) const { 813 return Parent::maxNodeId(); 814 } 815 816 int maxId(RedNode) const { 817 return Parent::maxRedId(); 818 } 819 820 int maxId(BlueNode) const { 821 return Parent::maxBlueId(); 822 } 823 824 int maxId(Arc) const { 825 return Parent::maxArcId(); 826 } 827 828 int maxId(Edge) const { 829 return Parent::maxEdgeId(); 830 } 831 832 static Node fromId(int id, Node) { 833 return Parent::nodeFromId(id); 834 } 835 836 static Arc fromId(int id, Arc) { 837 return Parent::arcFromId(id); 838 } 839 840 static Edge fromId(int id, Edge) { 841 return Parent::edgeFromId(id); 842 } 843 844 Node oppositeNode(const Node &n, const Edge &e) const { 845 if( n == Parent::u(e)) 846 return Parent::v(e); 847 else if( n == Parent::v(e)) 848 return Parent::u(e); 849 else 850 return INVALID; 851 } 852 853 Arc oppositeArc(const Arc &arc) const { 854 return Parent::direct(arc, !Parent::direction(arc)); 855 } 856 857 using Parent::direct; 858 Arc direct(const Edge &edge, const Node &node) const { 859 return Parent::direct(edge, Parent::u(edge) == node); 860 } 861 862 // Alterable extension 863 864 typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier; 865 typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier; 866 typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier; 867 typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier; 868 typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier; 869 870 871 protected: 872 873 mutable NodeNotifier node_notifier; 874 mutable RedNodeNotifier red_node_notifier; 875 mutable BlueNodeNotifier blue_node_notifier; 876 mutable ArcNotifier arc_notifier; 877 mutable EdgeNotifier edge_notifier; 878 879 public: 880 881 NodeNotifier& notifier(Node) const { 882 return node_notifier; 883 } 884 885 RedNodeNotifier& notifier(RedNode) const { 886 return red_node_notifier; 887 } 888 889 BlueNodeNotifier& notifier(BlueNode) const { 890 return blue_node_notifier; 891 } 892 893 ArcNotifier& notifier(Arc) const { 894 return arc_notifier; 895 } 896 897 EdgeNotifier& notifier(Edge) const { 898 return edge_notifier; 899 } 900 901 902 903 class NodeIt : public Node { 904 const BpGraph* _graph; 905 public: 906 907 NodeIt() {} 908 909 NodeIt(Invalid i) : Node(i) { } 910 911 explicit NodeIt(const BpGraph& graph) : _graph(&graph) { 912 _graph>first(static_cast<Node&>(*this)); 913 } 914 915 NodeIt(const BpGraph& graph, const Node& node) 916 : Node(node), _graph(&graph) {} 917 918 NodeIt& operator++() { 919 _graph>next(*this); 920 return *this; 921 } 922 923 }; 924 925 class RedIt : public Node { 926 const BpGraph* _graph; 927 public: 928 929 RedIt() {} 930 931 RedIt(Invalid i) : Node(i) { } 932 933 explicit RedIt(const BpGraph& graph) : _graph(&graph) { 934 _graph>firstRed(static_cast<Node&>(*this)); 935 } 936 937 RedIt(const BpGraph& graph, const Node& node) 938 : Node(node), _graph(&graph) { 939 LEMON_DEBUG(_graph>red(node), "Node has to be red."); 940 } 941 942 RedIt& operator++() { 943 _graph>nextRed(*this); 944 return *this; 945 } 946 947 }; 948 949 class BlueIt : public Node { 950 const BpGraph* _graph; 951 public: 952 953 BlueIt() {} 954 955 BlueIt(Invalid i) : Node(i) { } 956 957 explicit BlueIt(const BpGraph& graph) : _graph(&graph) { 958 _graph>firstBlue(static_cast<Node&>(*this)); 959 } 960 961 BlueIt(const BpGraph& graph, const Node& node) 962 : Node(node), _graph(&graph) { 963 LEMON_DEBUG(_graph>blue(node), "Node has to be blue."); 964 } 965 966 BlueIt& operator++() { 967 _graph>nextBlue(*this); 968 return *this; 969 } 970 971 }; 972 973 974 class ArcIt : public Arc { 975 const BpGraph* _graph; 976 public: 977 978 ArcIt() { } 979 980 ArcIt(Invalid i) : Arc(i) { } 981 982 explicit ArcIt(const BpGraph& graph) : _graph(&graph) { 983 _graph>first(static_cast<Arc&>(*this)); 984 } 985 986 ArcIt(const BpGraph& graph, const Arc& arc) : 987 Arc(arc), _graph(&graph) { } 988 989 ArcIt& operator++() { 990 _graph>next(*this); 991 return *this; 992 } 993 994 }; 995 996 997 class OutArcIt : public Arc { 998 const BpGraph* _graph; 999 public: 1000 1001 OutArcIt() { } 1002 1003 OutArcIt(Invalid i) : Arc(i) { } 1004 1005 OutArcIt(const BpGraph& graph, const Node& node) 1006 : _graph(&graph) { 1007 _graph>firstOut(*this, node); 1008 } 1009 1010 OutArcIt(const BpGraph& graph, const Arc& arc) 1011 : Arc(arc), _graph(&graph) {} 1012 1013 OutArcIt& operator++() { 1014 _graph>nextOut(*this); 1015 return *this; 1016 } 1017 1018 }; 1019 1020 1021 class InArcIt : public Arc { 1022 const BpGraph* _graph; 1023 public: 1024 1025 InArcIt() { } 1026 1027 InArcIt(Invalid i) : Arc(i) { } 1028 1029 InArcIt(const BpGraph& graph, const Node& node) 1030 : _graph(&graph) { 1031 _graph>firstIn(*this, node); 1032 } 1033 1034 InArcIt(const BpGraph& graph, const Arc& arc) : 1035 Arc(arc), _graph(&graph) {} 1036 1037 InArcIt& operator++() { 1038 _graph>nextIn(*this); 1039 return *this; 1040 } 1041 1042 }; 1043 1044 1045 class EdgeIt : public Parent::Edge { 1046 const BpGraph* _graph; 1047 public: 1048 1049 EdgeIt() { } 1050 1051 EdgeIt(Invalid i) : Edge(i) { } 1052 1053 explicit EdgeIt(const BpGraph& graph) : _graph(&graph) { 1054 _graph>first(static_cast<Edge&>(*this)); 1055 } 1056 1057 EdgeIt(const BpGraph& graph, const Edge& edge) : 1058 Edge(edge), _graph(&graph) { } 1059 1060 EdgeIt& operator++() { 1061 _graph>next(*this); 1062 return *this; 1063 } 1064 1065 }; 1066 1067 class IncEdgeIt : public Parent::Edge { 1068 friend class BpGraphExtender; 1069 const BpGraph* _graph; 1070 bool _direction; 1071 public: 1072 1073 IncEdgeIt() { } 1074 1075 IncEdgeIt(Invalid i) : Edge(i), _direction(false) { } 1076 1077 IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) { 1078 _graph>firstInc(*this, _direction, node); 1079 } 1080 1081 IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node) 1082 : _graph(&graph), Edge(edge) { 1083 _direction = (_graph>source(edge) == node); 1084 } 1085 1086 IncEdgeIt& operator++() { 1087 _graph>nextInc(*this, _direction); 1088 return *this; 1089 } 1090 }; 1091 1092 // \brief Base node of the iterator 1093 // 1094 // Returns the base node (ie. the source in this case) of the iterator 1095 Node baseNode(const OutArcIt &arc) const { 1096 return Parent::source(static_cast<const Arc&>(arc)); 1097 } 1098 // \brief Running node of the iterator 1099 // 1100 // Returns the running node (ie. the target in this case) of the 1101 // iterator 1102 Node runningNode(const OutArcIt &arc) const { 1103 return Parent::target(static_cast<const Arc&>(arc)); 1104 } 1105 1106 // \brief Base node of the iterator 1107 // 1108 // Returns the base node (ie. the target in this case) of the iterator 1109 Node baseNode(const InArcIt &arc) const { 1110 return Parent::target(static_cast<const Arc&>(arc)); 1111 } 1112 // \brief Running node of the iterator 1113 // 1114 // Returns the running node (ie. the source in this case) of the 1115 // iterator 1116 Node runningNode(const InArcIt &arc) const { 1117 return Parent::source(static_cast<const Arc&>(arc)); 1118 } 1119 1120 // Base node of the iterator 1121 // 1122 // Returns the base node of the iterator 1123 Node baseNode(const IncEdgeIt &edge) const { 1124 return edge._direction ? this>u(edge) : this>v(edge); 1125 } 1126 // Running node of the iterator 1127 // 1128 // Returns the running node of the iterator 1129 Node runningNode(const IncEdgeIt &edge) const { 1130 return edge._direction ? this>v(edge) : this>u(edge); 1131 } 1132 1133 // Mappable extension 1134 1135 template <typename _Value> 1136 class NodeMap 1137 : public MapExtender<DefaultMap<BpGraph, Node, _Value> > { 1138 typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent; 1139 1140 public: 1141 explicit NodeMap(const BpGraph& bpgraph) 1142 : Parent(bpgraph) {} 1143 NodeMap(const BpGraph& bpgraph, const _Value& value) 1144 : Parent(bpgraph, value) {} 1145 1146 private: 1147 NodeMap& operator=(const NodeMap& cmap) { 1148 return operator=<NodeMap>(cmap); 1149 } 1150 1151 template <typename CMap> 1152 NodeMap& operator=(const CMap& cmap) { 1153 Parent::operator=(cmap); 1154 return *this; 1155 } 1156 1157 }; 1158 1159 template <typename _Value> 1160 class RedMap 1161 : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > { 1162 typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent; 1163 1164 public: 1165 explicit RedMap(const BpGraph& bpgraph) 1166 : Parent(bpgraph) {} 1167 RedMap(const BpGraph& bpgraph, const _Value& value) 1168 : Parent(bpgraph, value) {} 1169 1170 private: 1171 RedMap& operator=(const RedMap& cmap) { 1172 return operator=<RedMap>(cmap); 1173 } 1174 1175 template <typename CMap> 1176 RedMap& operator=(const CMap& cmap) { 1177 Parent::operator=(cmap); 1178 return *this; 1179 } 1180 1181 }; 1182 1183 template <typename _Value> 1184 class BlueMap 1185 : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > { 1186 typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent; 1187 1188 public: 1189 explicit BlueMap(const BpGraph& bpgraph) 1190 : Parent(bpgraph) {} 1191 BlueMap(const BpGraph& bpgraph, const _Value& value) 1192 : Parent(bpgraph, value) {} 1193 1194 private: 1195 BlueMap& operator=(const BlueMap& cmap) { 1196 return operator=<BlueMap>(cmap); 1197 } 1198 1199 template <typename CMap> 1200 BlueMap& operator=(const CMap& cmap) { 1201 Parent::operator=(cmap); 1202 return *this; 1203 } 1204 1205 }; 1206 1207 template <typename _Value> 1208 class ArcMap 1209 : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > { 1210 typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent; 1211 1212 public: 1213 explicit ArcMap(const BpGraph& graph) 1214 : Parent(graph) {} 1215 ArcMap(const BpGraph& graph, const _Value& value) 1216 : Parent(graph, value) {} 1217 1218 private: 1219 ArcMap& operator=(const ArcMap& cmap) { 1220 return operator=<ArcMap>(cmap); 1221 } 1222 1223 template <typename CMap> 1224 ArcMap& operator=(const CMap& cmap) { 1225 Parent::operator=(cmap); 1226 return *this; 1227 } 1228 }; 1229 1230 1231 template <typename _Value> 1232 class EdgeMap 1233 : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > { 1234 typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent; 1235 1236 public: 1237 explicit EdgeMap(const BpGraph& graph) 1238 : Parent(graph) {} 1239 1240 EdgeMap(const BpGraph& graph, const _Value& value) 1241 : Parent(graph, value) {} 1242 1243 private: 1244 EdgeMap& operator=(const EdgeMap& cmap) { 1245 return operator=<EdgeMap>(cmap); 1246 } 1247 1248 template <typename CMap> 1249 EdgeMap& operator=(const CMap& cmap) { 1250 Parent::operator=(cmap); 1251 return *this; 1252 } 1253 1254 }; 1255 1256 // Alteration extension 1257 1258 Node addRedNode() { 1259 Node node = Parent::addRedNode(); 1260 notifier(RedNode()).add(node); 1261 notifier(Node()).add(node); 1262 return node; 1263 } 1264 1265 Node addBlueNode() { 1266 Node node = Parent::addBlueNode(); 1267 notifier(BlueNode()).add(node); 1268 notifier(Node()).add(node); 1269 return node; 1270 } 1271 1272 Edge addEdge(const Node& from, const Node& to) { 1273 Edge edge = Parent::addEdge(from, to); 1274 notifier(Edge()).add(edge); 1275 std::vector<Arc> av; 1276 av.push_back(Parent::direct(edge, true)); 1277 av.push_back(Parent::direct(edge, false)); 1278 notifier(Arc()).add(av); 1279 return edge; 1280 } 1281 1282 void clear() { 1283 notifier(Arc()).clear(); 1284 notifier(Edge()).clear(); 1285 notifier(Node()).clear(); 1286 notifier(BlueNode()).clear(); 1287 notifier(RedNode()).clear(); 1288 Parent::clear(); 1289 } 1290 1291 template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap> 1292 void build(const BpGraph& graph, NodeRefMap& nodeRef, 1293 EdgeRefMap& edgeRef) { 1294 Parent::build(graph, nodeRef, edgeRef); 1295 notifier(RedNode()).build(); 1296 notifier(BlueNode()).build(); 1297 notifier(Node()).build(); 1298 notifier(Edge()).build(); 1299 notifier(Arc()).build(); 1300 } 1301 1302 void erase(const Node& node) { 1303 Arc arc; 1304 Parent::firstOut(arc, node); 1305 while (arc != INVALID ) { 1306 erase(arc); 1307 Parent::firstOut(arc, node); 1308 } 1309 1310 Parent::firstIn(arc, node); 1311 while (arc != INVALID ) { 1312 erase(arc); 1313 Parent::firstIn(arc, node); 1314 } 1315 1316 if (Parent::red(node)) { 1317 notifier(RedNode()).erase(node); 1318 } else { 1319 notifier(BlueNode()).erase(node); 1320 } 1321 1322 notifier(Node()).erase(node); 1323 Parent::erase(node); 1324 } 1325 1326 void erase(const Edge& edge) { 1327 std::vector<Arc> av; 1328 av.push_back(Parent::direct(edge, true)); 1329 av.push_back(Parent::direct(edge, false)); 1330 notifier(Arc()).erase(av); 1331 notifier(Edge()).erase(edge); 1332 Parent::erase(edge); 1333 } 1334 1335 BpGraphExtender() { 1336 red_node_notifier.setContainer(*this); 1337 blue_node_notifier.setContainer(*this); 1338 node_notifier.setContainer(*this); 1339 arc_notifier.setContainer(*this); 1340 edge_notifier.setContainer(*this); 1341 } 1342 1343 ~BpGraphExtender() { 1344 edge_notifier.clear(); 1345 arc_notifier.clear(); 1346 node_notifier.clear(); 1347 blue_node_notifier.clear(); 1348 red_node_notifier.clear(); 1349 } 1350 1351 }; 1352 749 1353 } 750 1354 
lemon/bits/traits.h
r663 r1187 149 149 : Parent(_digraph, _value) {} 150 150 }; 151 152 }; 153 154 template <typename GR, typename Enable = void> 155 struct RedNodeNotifierIndicator { 156 typedef InvalidType Type; 157 }; 158 template <typename GR> 159 struct RedNodeNotifierIndicator< 160 GR, 161 typename enable_if<typename GR::RedNodeNotifier::Notifier, void>::type 162 > { 163 typedef typename GR::RedNodeNotifier Type; 164 }; 165 166 template <typename GR> 167 class ItemSetTraits<GR, typename GR::RedNode> { 168 public: 169 170 typedef GR BpGraph; 171 typedef GR Graph; 172 typedef GR Digraph; 173 174 typedef typename GR::RedNode Item; 175 typedef typename GR::RedIt ItemIt; 176 177 typedef typename RedNodeNotifierIndicator<GR>::Type ItemNotifier; 178 179 template <typename V> 180 class Map : public GR::template RedMap<V> { 181 typedef typename GR::template RedMap<V> Parent; 182 183 public: 184 typedef typename GR::template RedMap<V> Type; 185 typedef typename Parent::Value Value; 186 187 Map(const GR& _bpgraph) : Parent(_bpgraph) {} 188 Map(const GR& _bpgraph, const Value& _value) 189 : Parent(_bpgraph, _value) {} 190 191 }; 192 193 }; 194 195 template <typename GR, typename Enable = void> 196 struct BlueNodeNotifierIndicator { 197 typedef InvalidType Type; 198 }; 199 template <typename GR> 200 struct BlueNodeNotifierIndicator< 201 GR, 202 typename enable_if<typename GR::BlueNodeNotifier::Notifier, void>::type 203 > { 204 typedef typename GR::BlueNodeNotifier Type; 205 }; 206 207 template <typename GR> 208 class ItemSetTraits<GR, typename GR::BlueNode> { 209 public: 210 211 typedef GR BpGraph; 212 typedef GR Graph; 213 typedef GR Digraph; 214 215 typedef typename GR::BlueNode Item; 216 typedef typename GR::BlueIt ItemIt; 217 218 typedef typename BlueNodeNotifierIndicator<GR>::Type ItemNotifier; 219 220 template <typename V> 221 class Map : public GR::template BlueMap<V> { 222 typedef typename GR::template BlueMap<V> Parent; 223 224 public: 225 typedef typename GR::template BlueMap<V> Type; 226 typedef typename Parent::Value Value; 227 228 Map(const GR& _bpgraph) : Parent(_bpgraph) {} 229 Map(const GR& _bpgraph, const Value& _value) 230 : Parent(_bpgraph, _value) {} 231 232 }; 151 233 152 234 }; 
lemon/core.h
r1162 r1187 149 149 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap 150 150 151 ///Create convenience typedefs for the bipartite graph types and iterators 152 153 ///This \c \#define creates the same convenient type definitions as defined 154 ///by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it creates 155 ///\c RedNode, \c RedIt, \c BoolRedMap, \c IntRedMap, \c DoubleRedMap, 156 ///\c BlueNode, \c BlueIt, \c BoolBlueMap, \c IntBlueMap, \c DoubleBlueMap. 157 /// 158 ///\note If the graph type is a dependent type, ie. the graph type depend 159 ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS() 160 ///macro. 161 #define BPGRAPH_TYPEDEFS(BpGraph) \ 162 GRAPH_TYPEDEFS(BpGraph); \ 163 typedef BpGraph::RedNode RedNode; \ 164 typedef BpGraph::RedIt RedIt; \ 165 typedef BpGraph::RedMap<bool> BoolRedMap; \ 166 typedef BpGraph::RedMap<int> IntRedMap; \ 167 typedef BpGraph::RedMap<double> DoubleRedMap \ 168 typedef BpGraph::BlueNode BlueNode; \ 169 typedef BpGraph::BlueIt BlueIt; \ 170 typedef BpGraph::BlueMap<bool> BoolBlueMap; \ 171 typedef BpGraph::BlueMap<int> IntBlueMap; \ 172 typedef BpGraph::BlueMap<double> DoubleBlueMap 173 174 ///Create convenience typedefs for the bipartite graph types and iterators 175 176 ///\see BPGRAPH_TYPEDEFS 177 /// 178 ///\note Use this macro, if the graph type is a dependent type, 179 ///ie. the graph type depend on a template parameter. 180 #define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph) \ 181 TEMPLATE_GRAPH_TYPEDEFS(BpGraph); \ 182 typedef typename BpGraph::RedNode RedNode; \ 183 typedef typename BpGraph::RedIt RedIt; \ 184 typedef typename BpGraph::template RedMap<bool> BoolRedMap; \ 185 typedef typename BpGraph::template RedMap<int> IntRedMap; \ 186 typedef typename BpGraph::template RedMap<double> DoubleRedMap; \ 187 typedef typename BpGraph::BlueNode BlueNode; \ 188 typedef typename BpGraph::BlueIt BlueIt; \ 189 typedef typename BpGraph::template BlueMap<bool> BoolBlueMap; \ 190 typedef typename BpGraph::template BlueMap<int> IntBlueMap; \ 191 typedef typename BpGraph::template BlueMap<double> DoubleBlueMap 192 151 193 /// \brief Function to count the items in a graph. 152 194 /// … … 198 240 inline int countNodes(const Graph& g) { 199 241 return _core_bits::CountNodesSelector<Graph>::count(g); 242 } 243 244 namespace _graph_utils_bits { 245 246 template <typename Graph, typename Enable = void> 247 struct CountRedNodesSelector { 248 static int count(const Graph &g) { 249 return countItems<Graph, typename Graph::RedNode>(g); 250 } 251 }; 252 253 template <typename Graph> 254 struct CountRedNodesSelector< 255 Graph, typename 256 enable_if<typename Graph::NodeNumTag, void>::type> 257 { 258 static int count(const Graph &g) { 259 return g.redNum(); 260 } 261 }; 262 } 263 264 /// \brief Function to count the red nodes in the graph. 265 /// 266 /// This function counts the red nodes in the graph. 267 /// The complexity of the function is O(n) but for some 268 /// graph structures it is specialized to run in O(1). 269 /// 270 /// If the graph contains a \e redNum() member function and a 271 /// \e NodeNumTag tag then this function calls directly the member 272 /// function to query the cardinality of the node set. 273 template <typename Graph> 274 inline int countRedNodes(const Graph& g) { 275 return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g); 276 } 277 278 namespace _graph_utils_bits { 279 280 template <typename Graph, typename Enable = void> 281 struct CountBlueNodesSelector { 282 static int count(const Graph &g) { 283 return countItems<Graph, typename Graph::BlueNode>(g); 284 } 285 }; 286 287 template <typename Graph> 288 struct CountBlueNodesSelector< 289 Graph, typename 290 enable_if<typename Graph::NodeNumTag, void>::type> 291 { 292 static int count(const Graph &g) { 293 return g.blueNum(); 294 } 295 }; 296 } 297 298 /// \brief Function to count the blue nodes in the graph. 299 /// 300 /// This function counts the blue nodes in the graph. 301 /// The complexity of the function is O(n) but for some 302 /// graph structures it is specialized to run in O(1). 303 /// 304 /// If the graph contains a \e blueNum() member function and a 305 /// \e NodeNumTag tag then this function calls directly the member 306 /// function to query the cardinality of the node set. 307 template <typename Graph> 308 inline int countBlueNodes(const Graph& g) { 309 return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g); 200 310 } 201 311 … … 1258 1368 /// The Digraph type 1259 1369 typedef GR Digraph; 1260 1370 1261 1371 protected: 1262 1372 
lemon/smart_graph.h
r956 r1187 406 406 std::vector<ArcT> arcs; 407 407 408 int first_free_arc;409 410 408 public: 411 409 … … 812 810 }; 813 811 812 class SmartBpGraphBase { 813 814 protected: 815 816 struct NodeT { 817 int first_out; 818 int partition_next; 819 int partition_index; 820 bool red; 821 }; 822 823 struct ArcT { 824 int target; 825 int next_out; 826 }; 827 828 std::vector<NodeT> nodes; 829 std::vector<ArcT> arcs; 830 831 int first_red, first_blue; 832 833 public: 834 835 typedef SmartBpGraphBase Graph; 836 837 class Node; 838 class Arc; 839 class Edge; 840 841 class Node { 842 friend class SmartBpGraphBase; 843 protected: 844 845 int _id; 846 explicit Node(int id) { _id = id;} 847 848 public: 849 Node() {} 850 Node (Invalid) { _id = 1; } 851 bool operator==(const Node& node) const {return _id == node._id;} 852 bool operator!=(const Node& node) const {return _id != node._id;} 853 bool operator<(const Node& node) const {return _id < node._id;} 854 }; 855 856 class Edge { 857 friend class SmartBpGraphBase; 858 protected: 859 860 int _id; 861 explicit Edge(int id) { _id = id;} 862 863 public: 864 Edge() {} 865 Edge (Invalid) { _id = 1; } 866 bool operator==(const Edge& arc) const {return _id == arc._id;} 867 bool operator!=(const Edge& arc) const {return _id != arc._id;} 868 bool operator<(const Edge& arc) const {return _id < arc._id;} 869 }; 870 871 class Arc { 872 friend class SmartBpGraphBase; 873 protected: 874 875 int _id; 876 explicit Arc(int id) { _id = id;} 877 878 public: 879 operator Edge() const { 880 return _id != 1 ? edgeFromId(_id / 2) : INVALID; 881 } 882 883 Arc() {} 884 Arc (Invalid) { _id = 1; } 885 bool operator==(const Arc& arc) const {return _id == arc._id;} 886 bool operator!=(const Arc& arc) const {return _id != arc._id;} 887 bool operator<(const Arc& arc) const {return _id < arc._id;} 888 }; 889 890 891 892 SmartBpGraphBase() 893 : nodes(), arcs(), first_red(1), first_blue(1) {} 894 895 typedef True NodeNumTag; 896 typedef True EdgeNumTag; 897 typedef True ArcNumTag; 898 899 int nodeNum() const { return nodes.size(); } 900 int redNum() const { 901 return first_red == 1 ? 0 : nodes[first_red].partition_index + 1; 902 } 903 int blueNum() const { 904 return first_blue == 1 ? 0 : nodes[first_blue].partition_index + 1; 905 } 906 int edgeNum() const { return arcs.size() / 2; } 907 int arcNum() const { return arcs.size(); } 908 909 int maxNodeId() const { return nodes.size()1; } 910 int maxRedId() const { 911 return first_red == 1 ? 1 : nodes[first_red].partition_index; 912 } 913 int maxBlueId() const { 914 return first_blue == 1 ? 1 : nodes[first_blue].partition_index; 915 } 916 int maxEdgeId() const { return arcs.size() / 2  1; } 917 int maxArcId() const { return arcs.size()1; } 918 919 bool red(Node n) const { return nodes[n._id].red; } 920 bool blue(Node n) const { return !nodes[n._id].red; } 921 922 Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); } 923 Node target(Arc a) const { return Node(arcs[a._id].target); } 924 925 Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); } 926 Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); } 927 928 Node u(Edge e) const { return redNode(e); } 929 Node v(Edge e) const { return blueNode(e); } 930 931 static bool direction(Arc a) { 932 return (a._id & 1) == 1; 933 } 934 935 static Arc direct(Edge e, bool d) { 936 return Arc(e._id * 2 + (d ? 1 : 0)); 937 } 938 939 void first(Node& node) const { 940 node._id = nodes.size()  1; 941 } 942 943 static void next(Node& node) { 944 node._id; 945 } 946 947 void firstRed(Node& node) const { 948 node._id = first_red; 949 } 950 951 void nextRed(Node& node) const { 952 node._id = nodes[node._id].partition_next; 953 } 954 955 void firstBlue(Node& node) const { 956 node._id = first_blue; 957 } 958 959 void nextBlue(Node& node) const { 960 node._id = nodes[node._id].partition_next; 961 } 962 963 void first(Arc& arc) const { 964 arc._id = arcs.size()  1; 965 } 966 967 static void next(Arc& arc) { 968 arc._id; 969 } 970 971 void first(Edge& arc) const { 972 arc._id = arcs.size() / 2  1; 973 } 974 975 static void next(Edge& arc) { 976 arc._id; 977 } 978 979 void firstOut(Arc &arc, const Node& v) const { 980 arc._id = nodes[v._id].first_out; 981 } 982 void nextOut(Arc &arc) const { 983 arc._id = arcs[arc._id].next_out; 984 } 985 986 void firstIn(Arc &arc, const Node& v) const { 987 arc._id = ((nodes[v._id].first_out) ^ 1); 988 if (arc._id == 2) arc._id = 1; 989 } 990 void nextIn(Arc &arc) const { 991 arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1); 992 if (arc._id == 2) arc._id = 1; 993 } 994 995 void firstInc(Edge &arc, bool& d, const Node& v) const { 996 int de = nodes[v._id].first_out; 997 if (de != 1) { 998 arc._id = de / 2; 999 d = ((de & 1) == 1); 1000 } else { 1001 arc._id = 1; 1002 d = true; 1003 } 1004 } 1005 void nextInc(Edge &arc, bool& d) const { 1006 int de = (arcs[(arc._id * 2)  (d ? 1 : 0)].next_out); 1007 if (de != 1) { 1008 arc._id = de / 2; 1009 d = ((de & 1) == 1); 1010 } else { 1011 arc._id = 1; 1012 d = true; 1013 } 1014 } 1015 1016 static int id(Node v) { return v._id; } 1017 int redId(Node v) const { 1018 LEMON_DEBUG(nodes[v._id].red, "Node has to be red"); 1019 return nodes[v._id].partition_index; 1020 } 1021 int blueId(Node v) const { 1022 LEMON_DEBUG(nodes[v._id].red, "Node has to be blue"); 1023 return nodes[v._id].partition_index; 1024 } 1025 static int id(Arc e) { return e._id; } 1026 static int id(Edge e) { return e._id; } 1027 1028 static Node nodeFromId(int id) { return Node(id);} 1029 static Arc arcFromId(int id) { return Arc(id);} 1030 static Edge edgeFromId(int id) { return Edge(id);} 1031 1032 bool valid(Node n) const { 1033 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 1034 } 1035 bool valid(Arc a) const { 1036 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 1037 } 1038 bool valid(Edge e) const { 1039 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 1040 } 1041 1042 Node addRedNode() { 1043 int n = nodes.size(); 1044 nodes.push_back(NodeT()); 1045 nodes[n].first_out = 1; 1046 nodes[n].red = true; 1047 if (first_red == 1) { 1048 nodes[n].partition_index = 0; 1049 } else { 1050 nodes[n].partition_index = nodes[first_red].partition_index + 1; 1051 } 1052 nodes[n].partition_next = first_red; 1053 first_red = n; 1054 1055 return Node(n); 1056 } 1057 1058 Node addBlueNode() { 1059 int n = nodes.size(); 1060 nodes.push_back(NodeT()); 1061 nodes[n].first_out = 1; 1062 nodes[n].red = false; 1063 if (first_blue == 1) { 1064 nodes[n].partition_index = 0; 1065 } else { 1066 nodes[n].partition_index = nodes[first_blue].partition_index + 1; 1067 } 1068 nodes[n].partition_next = first_blue; 1069 first_blue = n; 1070 1071 return Node(n); 1072 } 1073 1074 Edge addEdge(Node u, Node v) { 1075 int n = arcs.size(); 1076 arcs.push_back(ArcT()); 1077 arcs.push_back(ArcT()); 1078 1079 arcs[n].target = u._id; 1080 arcs[n  1].target = v._id; 1081 1082 arcs[n].next_out = nodes[v._id].first_out; 1083 nodes[v._id].first_out = n; 1084 1085 arcs[n  1].next_out = nodes[u._id].first_out; 1086 nodes[u._id].first_out = (n  1); 1087 1088 return Edge(n / 2); 1089 } 1090 1091 void clear() { 1092 arcs.clear(); 1093 nodes.clear(); 1094 first_red = 1; 1095 first_blue = 1; 1096 } 1097 1098 }; 1099 1100 typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase; 1101 1102 /// \ingroup graphs 1103 /// 1104 /// \brief A smart undirected graph class. 1105 /// 1106 /// \ref SmartBpGraph is a simple and fast graph implementation. 1107 /// It is also quite memory efficient but at the price 1108 /// that it does not support node and edge deletion 1109 /// (except for the Snapshot feature). 1110 /// 1111 /// This type fully conforms to the \ref concepts::Graph "Graph concept" 1112 /// and it also provides some additional functionalities. 1113 /// Most of its member functions and nested classes are documented 1114 /// only in the concept class. 1115 /// 1116 /// This class provides constant time counting for nodes, edges and arcs. 1117 /// 1118 /// \sa concepts::Graph 1119 /// \sa SmartDigraph 1120 class SmartBpGraph : public ExtendedSmartBpGraphBase { 1121 typedef ExtendedSmartBpGraphBase Parent; 1122 1123 private: 1124 /// Graphs are \e not copy constructible. Use GraphCopy instead. 1125 SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {}; 1126 /// \brief Assignment of a graph to another one is \e not allowed. 1127 /// Use GraphCopy instead. 1128 void operator=(const SmartBpGraph &) {} 1129 1130 public: 1131 1132 /// Constructor 1133 1134 /// Constructor. 1135 /// 1136 SmartBpGraph() {} 1137 1138 /// \brief Add a new red node to the graph. 1139 /// 1140 /// This function adds a red new node to the graph. 1141 /// \return The new node. 1142 Node addRedNode() { return Parent::addRedNode(); } 1143 1144 /// \brief Add a new blue node to the graph. 1145 /// 1146 /// This function adds a blue new node to the graph. 1147 /// \return The new node. 1148 Node addBlueNode() { return Parent::addBlueNode(); } 1149 1150 /// \brief Add a new edge to the graph. 1151 /// 1152 /// This function adds a new edge to the graph between nodes 1153 /// \c u and \c v with inherent orientation from node \c u to 1154 /// node \c v. 1155 /// \return The new edge. 1156 Edge addEdge(Node red, Node blue) { 1157 LEMON_DEBUG(Parent::red(red) && Parent::blue(blue), 1158 "Edge has to be formed by a red and a blue nodes"); 1159 return Parent::addEdge(red, blue); 1160 } 1161 1162 /// \brief Node validity check 1163 /// 1164 /// This function gives back \c true if the given node is valid, 1165 /// i.e. it is a real node of the graph. 1166 /// 1167 /// \warning A removed node (using Snapshot) could become valid again 1168 /// if new nodes are added to the graph. 1169 bool valid(Node n) const { return Parent::valid(n); } 1170 1171 /// \brief Edge validity check 1172 /// 1173 /// This function gives back \c true if the given edge is valid, 1174 /// i.e. it is a real edge of the graph. 1175 /// 1176 /// \warning A removed edge (using Snapshot) could become valid again 1177 /// if new edges are added to the graph. 1178 bool valid(Edge e) const { return Parent::valid(e); } 1179 1180 /// \brief Arc validity check 1181 /// 1182 /// This function gives back \c true if the given arc is valid, 1183 /// i.e. it is a real arc of the graph. 1184 /// 1185 /// \warning A removed arc (using Snapshot) could become valid again 1186 /// if new edges are added to the graph. 1187 bool valid(Arc a) const { return Parent::valid(a); } 1188 1189 ///Clear the graph. 1190 1191 ///This function erases all nodes and arcs from the graph. 1192 /// 1193 void clear() { 1194 Parent::clear(); 1195 } 1196 1197 /// Reserve memory for nodes. 1198 1199 /// Using this function, it is possible to avoid superfluous memory 1200 /// allocation: if you know that the graph you want to build will 1201 /// be large (e.g. it will contain millions of nodes and/or edges), 1202 /// then it is worth reserving space for this amount before starting 1203 /// to build the graph. 1204 /// \sa reserveEdge() 1205 void reserveNode(int n) { nodes.reserve(n); }; 1206 1207 /// Reserve memory for edges. 1208 1209 /// Using this function, it is possible to avoid superfluous memory 1210 /// allocation: if you know that the graph you want to build will 1211 /// be large (e.g. it will contain millions of nodes and/or edges), 1212 /// then it is worth reserving space for this amount before starting 1213 /// to build the graph. 1214 /// \sa reserveNode() 1215 void reserveEdge(int m) { arcs.reserve(2 * m); }; 1216 1217 public: 1218 1219 class Snapshot; 1220 1221 protected: 1222 1223 void saveSnapshot(Snapshot &s) 1224 { 1225 s._graph = this; 1226 s.node_num = nodes.size(); 1227 s.arc_num = arcs.size(); 1228 } 1229 1230 void restoreSnapshot(const Snapshot &s) 1231 { 1232 while(s.arc_num<arcs.size()) { 1233 int n=arcs.size()1; 1234 Edge arc=edgeFromId(n/2); 1235 Parent::notifier(Edge()).erase(arc); 1236 std::vector<Arc> dir; 1237 dir.push_back(arcFromId(n)); 1238 dir.push_back(arcFromId(n1)); 1239 Parent::notifier(Arc()).erase(dir); 1240 nodes[arcs[n1].target].first_out=arcs[n].next_out; 1241 nodes[arcs[n].target].first_out=arcs[n1].next_out; 1242 arcs.pop_back(); 1243 arcs.pop_back(); 1244 } 1245 while(s.node_num<nodes.size()) { 1246 int n=nodes.size()1; 1247 Node node = nodeFromId(n); 1248 if (Parent::red(node)) { 1249 first_red = nodes[n].partition_next; 1250 Parent::notifier(RedNode()).erase(node); 1251 } else { 1252 first_blue = nodes[n].partition_next; 1253 Parent::notifier(BlueNode()).erase(node); 1254 } 1255 Parent::notifier(Node()).erase(node); 1256 nodes.pop_back(); 1257 } 1258 } 1259 1260 public: 1261 1262 ///Class to make a snapshot of the graph and to restore it later. 1263 1264 ///Class to make a snapshot of the graph and to restore it later. 1265 /// 1266 ///The newly added nodes and edges can be removed using the 1267 ///restore() function. This is the only way for deleting nodes and/or 1268 ///edges from a SmartBpGraph structure. 1269 /// 1270 ///\note After a state is restored, you cannot restore a later state, 1271 ///i.e. you cannot add the removed nodes and edges again using 1272 ///another Snapshot instance. 1273 /// 1274 ///\warning The validity of the snapshot is not stored due to 1275 ///performance reasons. If you do not use the snapshot correctly, 1276 ///it can cause broken program, invalid or not restored state of 1277 ///the graph or no change. 1278 class Snapshot 1279 { 1280 SmartBpGraph *_graph; 1281 protected: 1282 friend class SmartBpGraph; 1283 unsigned int node_num; 1284 unsigned int arc_num; 1285 public: 1286 ///Default constructor. 1287 1288 ///Default constructor. 1289 ///You have to call save() to actually make a snapshot. 1290 Snapshot() : _graph(0) {} 1291 ///Constructor that immediately makes a snapshot 1292 1293 /// This constructor immediately makes a snapshot of the given graph. 1294 /// 1295 Snapshot(SmartBpGraph &gr) { 1296 gr.saveSnapshot(*this); 1297 } 1298 1299 ///Make a snapshot. 1300 1301 ///This function makes a snapshot of the given graph. 1302 ///It can be called more than once. In case of a repeated 1303 ///call, the previous snapshot gets lost. 1304 void save(SmartBpGraph &gr) 1305 { 1306 gr.saveSnapshot(*this); 1307 } 1308 1309 ///Undo the changes until the last snapshot. 1310 1311 ///This function undos the changes until the last snapshot 1312 ///created by save() or Snapshot(SmartBpGraph&). 1313 void restore() 1314 { 1315 _graph>restoreSnapshot(*this); 1316 } 1317 }; 1318 }; 1319 814 1320 } //namespace lemon 815 1321
Note: See TracChangeset
for help on using the changeset viewer.