Changes in / [1040:60c0c3ed8d11:1041:0b0327c9b3ef] in lemon-main
- Files:
-
- 10 added
- 21 edited
Legend:
- Unmodified
- Added
- Removed
-
CMakeLists.txt
r1000 r1017 92 92 SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}") 93 93 94 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING 94 IF(MSVC) 95 SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING 95 96 "Flags used by the C++ compiler during maintainer builds." 96 FORCE)97 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING97 ) 98 SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING 98 99 "Flags used by the C compiler during maintainer builds." 99 FORCE ) 100 SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER 100 ) 101 SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER 102 "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING 103 "Flags used for linking binaries during maintainer builds." 104 ) 105 SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER 106 "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING 107 "Flags used by the shared libraries linker during maintainer builds." 108 ) 109 ELSE() 110 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING 111 "Flags used by the C++ compiler during maintainer builds." 112 ) 113 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING 114 "Flags used by the C compiler during maintainer builds." 115 ) 116 SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER 101 117 "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING 102 118 "Flags used for linking binaries during maintainer builds." 103 FORCE)104 SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER119 ) 120 SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER 105 121 "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING 106 122 "Flags used by the shared libraries linker during maintainer builds." 107 FORCE ) 123 ) 124 ENDIF() 125 108 126 MARK_AS_ADVANCED( 109 127 CMAKE_CXX_FLAGS_MAINTAINER -
doc/CMakeLists.txt
r1040 r1041 49 49 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps 50 50 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 51 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps 51 52 COMMAND ${CMAKE_COMMAND} -E remove_directory html 52 53 COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox -
doc/groups.dox
r1003 r1038 559 559 \image latex planar.eps "Plane graph" width=\textwidth 560 560 */ 561 562 /** 563 @defgroup tsp Traveling Salesman Problem 564 @ingroup algs 565 \brief Algorithms for the symmetric traveling salesman problem 566 567 This group contains basic heuristic algorithms for the the symmetric 568 \e traveling \e salesman \e problem (TSP). 569 Given an \ref FullGraph "undirected full graph" with a cost map on its edges, 570 the problem is to find a shortest possible tour that visits each node exactly 571 once (i.e. the minimum cost Hamiltonian cycle). 572 573 These TSP algorithms are intended to be used with a \e metric \e cost 574 \e function, i.e. the edge costs should satisfy the triangle inequality. 575 Otherwise the algorithms could yield worse results. 576 577 LEMON provides five well-known heuristics for solving symmetric TSP: 578 - \ref NearestNeighborTsp Neareast neighbor algorithm 579 - \ref GreedyTsp Greedy algorithm 580 - \ref InsertionTsp Insertion heuristic (with four selection methods) 581 - \ref ChristofidesTsp Christofides algorithm 582 - \ref Opt2Tsp 2-opt algorithm 583 584 \ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest 585 solution methods. Furthermore, \ref InsertionTsp is usually quite effective. 586 587 \ref ChristofidesTsp is somewhat slower, but it has the best guaranteed 588 approximation factor: 3/2. 589 590 \ref Opt2Tsp usually provides the best results in practice, but 591 it is the slowest method. It can also be used to improve given tours, 592 for example, the results of other algorithms. 593 594 \image html tsp.png 595 \image latex tsp.eps "Traveling salesman problem" width=\textwidth 596 */ 561 597 562 598 /** -
doc/lgf.dox
r950 r1024 64 64 \endcode 65 65 66 The \c \@arcs section is very similar to the \c \@nodes section, it 67 again starts with a header line describing the names of the maps, but 68 the \c "label" map is not obligatory here. The following lines 69 describe the arcs. The first two tokens of each line are the source 70 and the target node of the arc, respectively, then come the map 66 The \e LGF files can also contain bipartite graphs, in this case a 67 \c @red_nodes and a \c @blue_nodes sections describe the node set of the 68 graph. If a map is in both of these sections, then it can be used as a 69 regular node map. 70 71 \code 72 @red_nodes 73 label only_red_map name 74 1 "cherry" "John" 75 2 "Santa Claus" "Jack" 76 3 "blood" "Jason" 77 @blue_nodes 78 label name 79 4 "Elisabeth" 80 5 "Eve" 81 \endcode 82 83 The \c \@arcs section is very similar to the \c \@nodes section, 84 it again starts with a header line describing the names of the maps, 85 but the \c "label" map is not obligatory here. The following lines 86 describe the arcs. The first two tokens of each line are 87 the source and the target node of the arc, respectively, then come the map 71 88 values. The source and target tokens must be node labels. 72 89 -
lemon/bits/graph_extender.h
r998 r1027 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::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 749 1330 } 750 1331 -
lemon/bits/traits.h
r616 r1026 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::RedNodeIt ItemIt; 176 177 typedef typename RedNodeNotifierIndicator<GR>::Type ItemNotifier; 178 179 template <typename V> 180 class Map : public GR::template RedNodeMap<V> { 181 typedef typename GR::template RedNodeMap<V> Parent; 182 183 public: 184 typedef typename GR::template RedNodeMap<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::BlueNodeIt ItemIt; 217 218 typedef typename BlueNodeNotifierIndicator<GR>::Type ItemNotifier; 219 220 template <typename V> 221 class Map : public GR::template BlueNodeMap<V> { 222 typedef typename GR::template BlueNodeMap<V> Parent; 223 224 public: 225 typedef typename GR::template BlueNodeMap<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/concepts/graph.h
r877 r1018 73 73 class Graph { 74 74 private: 75 /// Graphs are \e not copy constructible. Use DigraphCopy instead.75 /// Graphs are \e not copy constructible. Use GraphCopy instead. 76 76 Graph(const Graph&) {} 77 77 /// \brief Assignment of a graph to another one is \e not allowed. 78 /// Use DigraphCopy instead.78 /// Use GraphCopy instead. 79 79 void operator=(const Graph&) {} 80 80 -
lemon/concepts/graph_components.h
r1010 r1028 300 300 }; 301 301 302 /// \brief Base skeleton class for undirected bipartite graphs. 303 /// 304 /// This class describes the base interface of undirected 305 /// bipartite graph types. All bipartite graph %concepts have to 306 /// conform to this class. It extends the interface of \ref 307 /// BaseGraphComponent with an \c Edge type and functions to get 308 /// the end nodes of edges, to convert from arcs to edges and to 309 /// get both direction of edges. 310 class BaseBpGraphComponent : public BaseGraphComponent { 311 public: 312 313 typedef BaseBpGraphComponent BpGraph; 314 315 typedef BaseDigraphComponent::Node Node; 316 typedef BaseDigraphComponent::Arc Arc; 317 318 /// \brief Class to represent red nodes. 319 /// 320 /// This class represents the red nodes of the graph. The red 321 /// nodes can also be used as normal nodes. 322 class RedNode : public Node { 323 typedef Node Parent; 324 325 public: 326 /// \brief Default constructor. 327 /// 328 /// Default constructor. 329 /// \warning The default constructor is not required to set 330 /// the item to some well-defined value. So you should consider it 331 /// as uninitialized. 332 RedNode() {} 333 334 /// \brief Copy constructor. 335 /// 336 /// Copy constructor. 337 RedNode(const RedNode &) : Parent() {} 338 339 /// \brief Constructor for conversion from \c INVALID. 340 /// 341 /// Constructor for conversion from \c INVALID. 342 /// It initializes the item to be invalid. 343 /// \sa Invalid for more details. 344 RedNode(Invalid) {} 345 }; 346 347 /// \brief Class to represent blue nodes. 348 /// 349 /// This class represents the blue nodes of the graph. The blue 350 /// nodes can also be used as normal nodes. 351 class BlueNode : public Node { 352 typedef Node Parent; 353 354 public: 355 /// \brief Default constructor. 356 /// 357 /// Default constructor. 358 /// \warning The default constructor is not required to set 359 /// the item to some well-defined value. So you should consider it 360 /// as uninitialized. 361 BlueNode() {} 362 363 /// \brief Copy constructor. 364 /// 365 /// Copy constructor. 366 BlueNode(const BlueNode &) : Parent() {} 367 368 /// \brief Constructor for conversion from \c INVALID. 369 /// 370 /// Constructor for conversion from \c INVALID. 371 /// It initializes the item to be invalid. 372 /// \sa Invalid for more details. 373 BlueNode(Invalid) {} 374 375 /// \brief Constructor for conversion from a node. 376 /// 377 /// Constructor for conversion from a node. The conversion can 378 /// be invalid, since the Node can be member of the red 379 /// set. 380 BlueNode(const Node&) {} 381 }; 382 383 /// \brief Gives back %true for red nodes. 384 /// 385 /// Gives back %true for red nodes. 386 bool red(const Node&) const { return true; } 387 388 /// \brief Gives back %true for blue nodes. 389 /// 390 /// Gives back %true for blue nodes. 391 bool blue(const Node&) const { return true; } 392 393 /// \brief Gives back the red end node of the edge. 394 /// 395 /// Gives back the red end node of the edge. 396 RedNode redNode(const Edge&) const { return RedNode(); } 397 398 /// \brief Gives back the blue end node of the edge. 399 /// 400 /// Gives back the blue end node of the edge. 401 BlueNode blueNode(const Edge&) const { return BlueNode(); } 402 403 /// \brief Converts the node to red node object. 404 /// 405 /// This function converts unsafely the node to red node 406 /// object. It should be called only if the node is from the red 407 /// partition or INVALID. 408 RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); } 409 410 /// \brief Converts the node to blue node object. 411 /// 412 /// This function converts unsafely the node to blue node 413 /// object. It should be called only if the node is from the red 414 /// partition or INVALID. 415 BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); } 416 417 /// \brief Converts the node to red node object. 418 /// 419 /// This function converts safely the node to red node 420 /// object. If the node is not from the red partition, then it 421 /// returns INVALID. 422 RedNode asRedNode(const Node&) const { return RedNode(); } 423 424 /// \brief Converts the node to blue node object. 425 /// 426 /// This function converts unsafely the node to blue node 427 /// object. If the node is not from the blue partition, then it 428 /// returns INVALID. 429 BlueNode asBlueNode(const Node&) const { return BlueNode(); } 430 431 template <typename _BpGraph> 432 struct Constraints { 433 typedef typename _BpGraph::Node Node; 434 typedef typename _BpGraph::RedNode RedNode; 435 typedef typename _BpGraph::BlueNode BlueNode; 436 typedef typename _BpGraph::Arc Arc; 437 typedef typename _BpGraph::Edge Edge; 438 439 void constraints() { 440 checkConcept<BaseGraphComponent, _BpGraph>(); 441 checkConcept<GraphItem<'n'>, RedNode>(); 442 checkConcept<GraphItem<'n'>, BlueNode>(); 443 { 444 Node n; 445 RedNode rn; 446 BlueNode bn; 447 Node rnan = rn; 448 Node bnan = bn; 449 Edge e; 450 bool b; 451 b = bpgraph.red(rnan); 452 b = bpgraph.blue(bnan); 453 rn = bpgraph.redNode(e); 454 bn = bpgraph.blueNode(e); 455 rn = bpgraph.asRedNodeUnsafe(rnan); 456 bn = bpgraph.asBlueNodeUnsafe(bnan); 457 rn = bpgraph.asRedNode(rnan); 458 bn = bpgraph.asBlueNode(bnan); 459 ignore_unused_variable_warning(b); 460 } 461 } 462 463 const _BpGraph& bpgraph; 464 }; 465 466 }; 467 302 468 /// \brief Skeleton class for \e idable directed graphs. 303 469 /// … … 429 595 const _Graph& graph; 430 596 Constraints() {} 597 }; 598 }; 599 600 /// \brief Skeleton class for \e idable undirected bipartite graphs. 601 /// 602 /// This class describes the interface of \e idable undirected 603 /// bipartite graphs. It extends \ref IDableGraphComponent with 604 /// the core ID functions of undirected bipartite graphs. Beside 605 /// the regular node ids, this class also provides ids within the 606 /// the red and blue sets of the nodes. This concept is part of 607 /// the BpGraph concept. 608 template <typename BAS = BaseBpGraphComponent> 609 class IDableBpGraphComponent : public IDableGraphComponent<BAS> { 610 public: 611 612 typedef BAS Base; 613 typedef IDableGraphComponent<BAS> Parent; 614 typedef typename Base::Node Node; 615 typedef typename Base::RedNode RedNode; 616 typedef typename Base::BlueNode BlueNode; 617 618 using Parent::id; 619 620 /// \brief Return a unique integer id for the given node in the red set. 621 /// 622 /// Return a unique integer id for the given node in the red set. 623 int id(const RedNode&) const { return -1; } 624 625 /// \brief Return a unique integer id for the given node in the blue set. 626 /// 627 /// Return a unique integer id for the given node in the blue set. 628 int id(const BlueNode&) const { return -1; } 629 630 /// \brief Return an integer greater or equal to the maximum 631 /// node id in the red set. 632 /// 633 /// Return an integer greater or equal to the maximum 634 /// node id in the red set. 635 int maxRedId() const { return -1; } 636 637 /// \brief Return an integer greater or equal to the maximum 638 /// node id in the blue set. 639 /// 640 /// Return an integer greater or equal to the maximum 641 /// node id in the blue set. 642 int maxBlueId() const { return -1; } 643 644 template <typename _BpGraph> 645 struct Constraints { 646 647 void constraints() { 648 checkConcept<IDableGraphComponent<Base>, _BpGraph>(); 649 typename _BpGraph::Node node; 650 typename _BpGraph::RedNode red; 651 typename _BpGraph::BlueNode blue; 652 int rid = bpgraph.id(red); 653 int bid = bpgraph.id(blue); 654 rid = bpgraph.maxRedId(); 655 bid = bpgraph.maxBlueId(); 656 ignore_unused_variable_warning(rid); 657 ignore_unused_variable_warning(bid); 658 } 659 660 const _BpGraph& bpgraph; 431 661 }; 432 662 }; … … 905 1135 }; 906 1136 1137 /// \brief Skeleton class for iterable undirected bipartite graphs. 1138 /// 1139 /// This class describes the interface of iterable undirected 1140 /// bipartite graphs. It extends \ref IterableGraphComponent with 1141 /// the core iterable interface of undirected bipartite graphs. 1142 /// This concept is part of the BpGraph concept. 1143 template <typename BAS = BaseBpGraphComponent> 1144 class IterableBpGraphComponent : public IterableGraphComponent<BAS> { 1145 public: 1146 1147 typedef BAS Base; 1148 typedef typename Base::Node Node; 1149 typedef typename Base::RedNode RedNode; 1150 typedef typename Base::BlueNode BlueNode; 1151 typedef typename Base::Arc Arc; 1152 typedef typename Base::Edge Edge; 1153 1154 typedef IterableBpGraphComponent BpGraph; 1155 1156 using IterableGraphComponent<BAS>::first; 1157 using IterableGraphComponent<BAS>::next; 1158 1159 /// \name Base Iteration 1160 /// 1161 /// This interface provides functions for iteration on red and blue nodes. 1162 /// 1163 /// @{ 1164 1165 /// \brief Return the first red node. 1166 /// 1167 /// This function gives back the first red node in the iteration order. 1168 void first(RedNode&) const {} 1169 1170 /// \brief Return the next red node. 1171 /// 1172 /// This function gives back the next red node in the iteration order. 1173 void next(RedNode&) const {} 1174 1175 /// \brief Return the first blue node. 1176 /// 1177 /// This function gives back the first blue node in the iteration order. 1178 void first(BlueNode&) const {} 1179 1180 /// \brief Return the next blue node. 1181 /// 1182 /// This function gives back the next blue node in the iteration order. 1183 void next(BlueNode&) const {} 1184 1185 1186 /// @} 1187 1188 /// \name Class Based Iteration 1189 /// 1190 /// This interface provides iterator classes for red and blue nodes. 1191 /// 1192 /// @{ 1193 1194 /// \brief This iterator goes through each red node. 1195 /// 1196 /// This iterator goes through each red node. 1197 typedef GraphItemIt<BpGraph, RedNode> RedNodeIt; 1198 1199 /// \brief This iterator goes through each blue node. 1200 /// 1201 /// This iterator goes through each blue node. 1202 typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt; 1203 1204 /// @} 1205 1206 template <typename _BpGraph> 1207 struct Constraints { 1208 void constraints() { 1209 checkConcept<IterableGraphComponent<Base>, _BpGraph>(); 1210 1211 typename _BpGraph::RedNode rn(INVALID); 1212 bpgraph.first(rn); 1213 bpgraph.next(rn); 1214 typename _BpGraph::BlueNode bn(INVALID); 1215 bpgraph.first(bn); 1216 bpgraph.next(bn); 1217 1218 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>, 1219 typename _BpGraph::RedNodeIt>(); 1220 checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>, 1221 typename _BpGraph::BlueNodeIt>(); 1222 } 1223 1224 const _BpGraph& bpgraph; 1225 }; 1226 }; 1227 907 1228 /// \brief Skeleton class for alterable directed graphs. 908 1229 /// … … 930 1251 ArcNotifier; 931 1252 1253 mutable NodeNotifier node_notifier; 1254 mutable ArcNotifier arc_notifier; 1255 932 1256 /// \brief Return the node alteration notifier. 933 1257 /// 934 1258 /// This function gives back the node alteration notifier. 935 1259 NodeNotifier& notifier(Node) const { 936 return NodeNotifier();1260 return node_notifier; 937 1261 } 938 1262 … … 941 1265 /// This function gives back the arc alteration notifier. 942 1266 ArcNotifier& notifier(Arc) const { 943 return ArcNotifier();1267 return arc_notifier; 944 1268 } 945 1269 … … 977 1301 978 1302 typedef BAS Base; 1303 typedef AlterableDigraphComponent<Base> Parent; 979 1304 typedef typename Base::Edge Edge; 980 1305 … … 984 1309 EdgeNotifier; 985 1310 1311 mutable EdgeNotifier edge_notifier; 1312 1313 using Parent::notifier; 1314 986 1315 /// \brief Return the edge alteration notifier. 987 1316 /// 988 1317 /// This function gives back the edge alteration notifier. 989 1318 EdgeNotifier& notifier(Edge) const { 990 return EdgeNotifier();1319 return edge_notifier; 991 1320 } 992 1321 … … 1002 1331 const _Graph& graph; 1003 1332 Constraints() {} 1333 }; 1334 }; 1335 1336 /// \brief Skeleton class for alterable undirected bipartite graphs. 1337 /// 1338 /// This class describes the interface of alterable undirected 1339 /// bipartite graphs. It extends \ref AlterableGraphComponent with 1340 /// the alteration notifier interface of bipartite graphs. It 1341 /// implements an observer-notifier pattern for the red and blue 1342 /// nodes. More obsevers can be registered into the notifier and 1343 /// whenever an alteration occured in the graph all the observers 1344 /// will be notified about it. 1345 template <typename BAS = BaseBpGraphComponent> 1346 class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> { 1347 public: 1348 1349 typedef BAS Base; 1350 typedef AlterableGraphComponent<Base> Parent; 1351 typedef typename Base::RedNode RedNode; 1352 typedef typename Base::BlueNode BlueNode; 1353 1354 1355 /// Red node alteration notifier class. 1356 typedef AlterationNotifier<AlterableBpGraphComponent, RedNode> 1357 RedNodeNotifier; 1358 1359 /// Blue node alteration notifier class. 1360 typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode> 1361 BlueNodeNotifier; 1362 1363 mutable RedNodeNotifier red_node_notifier; 1364 mutable BlueNodeNotifier blue_node_notifier; 1365 1366 using Parent::notifier; 1367 1368 /// \brief Return the red node alteration notifier. 1369 /// 1370 /// This function gives back the red node alteration notifier. 1371 RedNodeNotifier& notifier(RedNode) const { 1372 return red_node_notifier; 1373 } 1374 1375 /// \brief Return the blue node alteration notifier. 1376 /// 1377 /// This function gives back the blue node alteration notifier. 1378 BlueNodeNotifier& notifier(BlueNode) const { 1379 return blue_node_notifier; 1380 } 1381 1382 template <typename _BpGraph> 1383 struct Constraints { 1384 void constraints() { 1385 checkConcept<AlterableGraphComponent<Base>, _BpGraph>(); 1386 typename _BpGraph::RedNodeNotifier& rnn 1387 = bpgraph.notifier(typename _BpGraph::RedNode()); 1388 typename _BpGraph::BlueNodeNotifier& bnn 1389 = bpgraph.notifier(typename _BpGraph::BlueNode()); 1390 ignore_unused_variable_warning(rnn); 1391 ignore_unused_variable_warning(bnn); 1392 } 1393 1394 const _BpGraph& bpgraph; 1004 1395 }; 1005 1396 }; … … 1308 1699 }; 1309 1700 1701 /// \brief Skeleton class for mappable undirected bipartite graphs. 1702 /// 1703 /// This class describes the interface of mappable undirected 1704 /// bipartite graphs. It extends \ref MappableGraphComponent with 1705 /// the standard graph map class for red and blue nodes (\c 1706 /// RedNodeMap and BlueNodeMap). This concept is part of the 1707 /// BpGraph concept. 1708 template <typename BAS = BaseBpGraphComponent> 1709 class MappableBpGraphComponent : public MappableGraphComponent<BAS> { 1710 public: 1711 1712 typedef BAS Base; 1713 typedef typename Base::Node Node; 1714 1715 typedef MappableBpGraphComponent BpGraph; 1716 1717 /// \brief Standard graph map for the red nodes. 1718 /// 1719 /// Standard graph map for the red nodes. 1720 /// It conforms to the ReferenceMap concept. 1721 template <typename V> 1722 class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> { 1723 typedef GraphMap<MappableBpGraphComponent, Node, V> Parent; 1724 1725 public: 1726 /// \brief Construct a new map. 1727 /// 1728 /// Construct a new map for the graph. 1729 explicit RedNodeMap(const MappableBpGraphComponent& graph) 1730 : Parent(graph) {} 1731 1732 /// \brief Construct a new map with default value. 1733 /// 1734 /// Construct a new map for the graph and initalize the values. 1735 RedNodeMap(const MappableBpGraphComponent& graph, const V& value) 1736 : Parent(graph, value) {} 1737 1738 private: 1739 /// \brief Copy constructor. 1740 /// 1741 /// Copy Constructor. 1742 RedNodeMap(const RedNodeMap& nm) : Parent(nm) {} 1743 1744 /// \brief Assignment operator. 1745 /// 1746 /// Assignment operator. 1747 template <typename CMap> 1748 RedNodeMap& operator=(const CMap&) { 1749 checkConcept<ReadMap<Node, V>, CMap>(); 1750 return *this; 1751 } 1752 1753 }; 1754 1755 /// \brief Standard graph map for the blue nodes. 1756 /// 1757 /// Standard graph map for the blue nodes. 1758 /// It conforms to the ReferenceMap concept. 1759 template <typename V> 1760 class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> { 1761 typedef GraphMap<MappableBpGraphComponent, Node, V> Parent; 1762 1763 public: 1764 /// \brief Construct a new map. 1765 /// 1766 /// Construct a new map for the graph. 1767 explicit BlueNodeMap(const MappableBpGraphComponent& graph) 1768 : Parent(graph) {} 1769 1770 /// \brief Construct a new map with default value. 1771 /// 1772 /// Construct a new map for the graph and initalize the values. 1773 BlueNodeMap(const MappableBpGraphComponent& graph, const V& value) 1774 : Parent(graph, value) {} 1775 1776 private: 1777 /// \brief Copy constructor. 1778 /// 1779 /// Copy Constructor. 1780 BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {} 1781 1782 /// \brief Assignment operator. 1783 /// 1784 /// Assignment operator. 1785 template <typename CMap> 1786 BlueNodeMap& operator=(const CMap&) { 1787 checkConcept<ReadMap<Node, V>, CMap>(); 1788 return *this; 1789 } 1790 1791 }; 1792 1793 1794 template <typename _BpGraph> 1795 struct Constraints { 1796 1797 struct Dummy { 1798 int value; 1799 Dummy() : value(0) {} 1800 Dummy(int _v) : value(_v) {} 1801 }; 1802 1803 void constraints() { 1804 checkConcept<MappableGraphComponent<Base>, _BpGraph>(); 1805 1806 { // int map test 1807 typedef typename _BpGraph::template RedNodeMap<int> 1808 IntRedNodeMap; 1809 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>, 1810 IntRedNodeMap >(); 1811 } { // bool map test 1812 typedef typename _BpGraph::template RedNodeMap<bool> 1813 BoolRedNodeMap; 1814 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>, 1815 BoolRedNodeMap >(); 1816 } { // Dummy map test 1817 typedef typename _BpGraph::template RedNodeMap<Dummy> 1818 DummyRedNodeMap; 1819 checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>, 1820 DummyRedNodeMap >(); 1821 } 1822 1823 { // int map test 1824 typedef typename _BpGraph::template BlueNodeMap<int> 1825 IntBlueNodeMap; 1826 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>, 1827 IntBlueNodeMap >(); 1828 } { // bool map test 1829 typedef typename _BpGraph::template BlueNodeMap<bool> 1830 BoolBlueNodeMap; 1831 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>, 1832 BoolBlueNodeMap >(); 1833 } { // Dummy map test 1834 typedef typename _BpGraph::template BlueNodeMap<Dummy> 1835 DummyBlueNodeMap; 1836 checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>, 1837 DummyBlueNodeMap >(); 1838 } 1839 } 1840 1841 const _BpGraph& bpgraph; 1842 }; 1843 }; 1844 1310 1845 /// \brief Skeleton class for extendable directed graphs. 1311 1846 /// … … 1398 1933 }; 1399 1934 1935 /// \brief Skeleton class for extendable undirected bipartite graphs. 1936 /// 1937 /// This class describes the interface of extendable undirected 1938 /// bipartite graphs. It extends \ref BaseGraphComponent with 1939 /// functions for adding nodes and edges to the graph. This 1940 /// concept requires \ref AlterableBpGraphComponent. 1941 template <typename BAS = BaseBpGraphComponent> 1942 class ExtendableBpGraphComponent : public BAS { 1943 public: 1944 1945 typedef BAS Base; 1946 typedef typename Base::Node Node; 1947 typedef typename Base::RedNode RedNode; 1948 typedef typename Base::BlueNode BlueNode; 1949 typedef typename Base::Edge Edge; 1950 1951 /// \brief Add a new red node to the digraph. 1952 /// 1953 /// This function adds a red new node to the digraph. 1954 RedNode addRedNode() { 1955 return INVALID; 1956 } 1957 1958 /// \brief Add a new blue node to the digraph. 1959 /// 1960 /// This function adds a blue new node to the digraph. 1961 BlueNode addBlueNode() { 1962 return INVALID; 1963 } 1964 1965 /// \brief Add a new edge connecting the given two nodes. 1966 /// 1967 /// This function adds a new edge connecting the given two nodes 1968 /// of the graph. The first node has to be a red node, and the 1969 /// second one a blue node. 1970 Edge addEdge(const RedNode&, const BlueNode&) { 1971 return INVALID; 1972 } 1973 Edge addEdge(const BlueNode&, const RedNode&) { 1974 return INVALID; 1975 } 1976 1977 template <typename _BpGraph> 1978 struct Constraints { 1979 void constraints() { 1980 checkConcept<Base, _BpGraph>(); 1981 typename _BpGraph::RedNode red_node; 1982 typename _BpGraph::BlueNode blue_node; 1983 red_node = bpgraph.addRedNode(); 1984 blue_node = bpgraph.addBlueNode(); 1985 typename _BpGraph::Edge edge; 1986 edge = bpgraph.addEdge(red_node, blue_node); 1987 edge = bpgraph.addEdge(blue_node, red_node); 1988 } 1989 1990 _BpGraph& bpgraph; 1991 }; 1992 }; 1993 1400 1994 /// \brief Skeleton class for erasable directed graphs. 1401 1995 /// … … 1478 2072 }; 1479 2073 2074 /// \brief Skeleton class for erasable undirected graphs. 2075 /// 2076 /// This class describes the interface of erasable undirected 2077 /// bipartite graphs. It extends \ref BaseBpGraphComponent with 2078 /// functions for removing nodes and edges from the graph. This 2079 /// concept requires \ref AlterableBpGraphComponent. 2080 template <typename BAS = BaseBpGraphComponent> 2081 class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {}; 2082 1480 2083 /// \brief Skeleton class for clearable directed graphs. 1481 2084 /// … … 1514 2117 /// This concept requires \ref AlterableGraphComponent. 1515 2118 template <typename BAS = BaseGraphComponent> 1516 class ClearableGraphComponent : public ClearableDigraphComponent<BAS> { 1517 public: 1518 1519 typedef BAS Base; 1520 1521 /// \brief Erase all nodes and edges from the graph. 1522 /// 1523 /// This function erases all nodes and edges from the graph. 1524 void clear() {} 1525 1526 template <typename _Graph> 1527 struct Constraints { 1528 void constraints() { 1529 checkConcept<Base, _Graph>(); 1530 graph.clear(); 1531 } 1532 1533 _Graph& graph; 1534 Constraints() {} 1535 }; 1536 }; 2119 class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {}; 2120 2121 /// \brief Skeleton class for clearable undirected biparite graphs. 2122 /// 2123 /// This class describes the interface of clearable undirected 2124 /// bipartite graphs. It extends \ref BaseBpGraphComponent with a 2125 /// function for clearing the graph. This concept requires \ref 2126 /// AlterableBpGraphComponent. 2127 template <typename BAS = BaseBpGraphComponent> 2128 class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {}; 1537 2129 1538 2130 } -
lemon/core.h
r1000 r1027 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 154 ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it 155 ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap, 156 ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt, 157 ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap. 158 /// 159 ///\note If the graph type is a dependent type, ie. the graph type depend 160 ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS() 161 ///macro. 162 #define BPGRAPH_TYPEDEFS(BpGraph) \ 163 GRAPH_TYPEDEFS(BpGraph); \ 164 typedef BpGraph::RedNode RedNode; \ 165 typedef BpGraph::RedNodeIt RedNodeIt; \ 166 typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap; \ 167 typedef BpGraph::RedNodeMap<int> IntRedNodeMap; \ 168 typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap; \ 169 typedef BpGraph::BlueNode BlueNode; \ 170 typedef BpGraph::BlueNodeIt BlueNodeIt; \ 171 typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap; \ 172 typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap; \ 173 typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap 174 175 ///Create convenience typedefs for the bipartite graph types and iterators 176 177 ///\see BPGRAPH_TYPEDEFS 178 /// 179 ///\note Use this macro, if the graph type is a dependent type, 180 ///ie. the graph type depend on a template parameter. 181 #define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph) \ 182 TEMPLATE_GRAPH_TYPEDEFS(BpGraph); \ 183 typedef typename BpGraph::RedNode RedNode; \ 184 typedef typename BpGraph::RedNodeIt RedNodeIt; \ 185 typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap; \ 186 typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap; \ 187 typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap; \ 188 typedef typename BpGraph::BlueNode BlueNode; \ 189 typedef typename BpGraph::BlueNodeIt BlueNodeIt; \ 190 typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap; \ 191 typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap; \ 192 typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap 193 151 194 /// \brief Function to count the items in a graph. 152 195 /// … … 200 243 } 201 244 245 namespace _graph_utils_bits { 246 247 template <typename Graph, typename Enable = void> 248 struct CountRedNodesSelector { 249 static int count(const Graph &g) { 250 return countItems<Graph, typename Graph::RedNode>(g); 251 } 252 }; 253 254 template <typename Graph> 255 struct CountRedNodesSelector< 256 Graph, typename 257 enable_if<typename Graph::NodeNumTag, void>::type> 258 { 259 static int count(const Graph &g) { 260 return g.redNum(); 261 } 262 }; 263 } 264 265 /// \brief Function to count the red nodes in the graph. 266 /// 267 /// This function counts the red nodes in the graph. 268 /// The complexity of the function is O(n) but for some 269 /// graph structures it is specialized to run in O(1). 270 /// 271 /// If the graph contains a \e redNum() member function and a 272 /// \e NodeNumTag tag then this function calls directly the member 273 /// function to query the cardinality of the node set. 274 template <typename Graph> 275 inline int countRedNodes(const Graph& g) { 276 return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g); 277 } 278 279 namespace _graph_utils_bits { 280 281 template <typename Graph, typename Enable = void> 282 struct CountBlueNodesSelector { 283 static int count(const Graph &g) { 284 return countItems<Graph, typename Graph::BlueNode>(g); 285 } 286 }; 287 288 template <typename Graph> 289 struct CountBlueNodesSelector< 290 Graph, typename 291 enable_if<typename Graph::NodeNumTag, void>::type> 292 { 293 static int count(const Graph &g) { 294 return g.blueNum(); 295 } 296 }; 297 } 298 299 /// \brief Function to count the blue nodes in the graph. 300 /// 301 /// This function counts the blue nodes in the graph. 302 /// The complexity of the function is O(n) but for some 303 /// graph structures it is specialized to run in O(1). 304 /// 305 /// If the graph contains a \e blueNum() member function and a 306 /// \e NodeNumTag tag then this function calls directly the member 307 /// function to query the cardinality of the node set. 308 template <typename Graph> 309 inline int countBlueNodes(const Graph& g) { 310 return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g); 311 } 312 202 313 // Arc counting: 203 314 … … 441 552 template <typename From, typename NodeRefMap, typename EdgeRefMap> 442 553 static void copy(const From& from, Graph &to, 443 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 554 NodeRefMap& nodeRefMap, 555 EdgeRefMap& edgeRefMap) { 444 556 to.build(from, nodeRefMap, edgeRefMap); 557 } 558 }; 559 560 template <typename BpGraph, typename Enable = void> 561 struct BpGraphCopySelector { 562 template <typename From, typename RedNodeRefMap, 563 typename BlueNodeRefMap, typename EdgeRefMap> 564 static void copy(const From& from, BpGraph &to, 565 RedNodeRefMap& redNodeRefMap, 566 BlueNodeRefMap& blueNodeRefMap, 567 EdgeRefMap& edgeRefMap) { 568 to.clear(); 569 for (typename From::RedNodeIt it(from); it != INVALID; ++it) { 570 redNodeRefMap[it] = to.addRedNode(); 571 } 572 for (typename From::BlueNodeIt it(from); it != INVALID; ++it) { 573 blueNodeRefMap[it] = to.addBlueNode(); 574 } 575 for (typename From::EdgeIt it(from); it != INVALID; ++it) { 576 edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)], 577 blueNodeRefMap[from.blueNode(it)]); 578 } 579 } 580 }; 581 582 template <typename BpGraph> 583 struct BpGraphCopySelector< 584 BpGraph, 585 typename enable_if<typename BpGraph::BuildTag, void>::type> 586 { 587 template <typename From, typename RedNodeRefMap, 588 typename BlueNodeRefMap, typename EdgeRefMap> 589 static void copy(const From& from, BpGraph &to, 590 RedNodeRefMap& redNodeRefMap, 591 BlueNodeRefMap& blueNodeRefMap, 592 EdgeRefMap& edgeRefMap) { 593 to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap); 445 594 } 446 595 }; … … 990 1139 graphCopy(const From& from, To& to) { 991 1140 return GraphCopy<From, To>(from, to); 1141 } 1142 1143 /// \brief Class to copy a bipartite graph. 1144 /// 1145 /// Class to copy a bipartite graph to another graph (duplicate a 1146 /// graph). The simplest way of using it is through the 1147 /// \c bpGraphCopy() function. 1148 /// 1149 /// This class not only make a copy of a bipartite graph, but it can 1150 /// create references and cross references between the nodes, edges 1151 /// and arcs of the two graphs, and it can copy maps for using with 1152 /// the newly created graph. 1153 /// 1154 /// To make a copy from a graph, first an instance of BpGraphCopy 1155 /// should be created, then the data belongs to the graph should 1156 /// assigned to copy. In the end, the \c run() member should be 1157 /// called. 1158 /// 1159 /// The next code copies a graph with several data: 1160 ///\code 1161 /// BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph); 1162 /// // Create references for the nodes 1163 /// OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph); 1164 /// cg.nodeRef(nr); 1165 /// // Create cross references (inverse) for the edges 1166 /// NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph); 1167 /// cg.edgeCrossRef(ecr); 1168 /// // Copy a red node map 1169 /// OrigBpGraph::RedNodeMap<double> ormap(orig_graph); 1170 /// NewBpGraph::RedNodeMap<double> nrmap(new_graph); 1171 /// cg.redNodeMap(ormap, nrmap); 1172 /// // Copy a node 1173 /// OrigBpGraph::Node on; 1174 /// NewBpGraph::Node nn; 1175 /// cg.node(on, nn); 1176 /// // Execute copying 1177 /// cg.run(); 1178 ///\endcode 1179 template <typename From, typename To> 1180 class BpGraphCopy { 1181 private: 1182 1183 typedef typename From::Node Node; 1184 typedef typename From::RedNode RedNode; 1185 typedef typename From::BlueNode BlueNode; 1186 typedef typename From::NodeIt NodeIt; 1187 typedef typename From::Arc Arc; 1188 typedef typename From::ArcIt ArcIt; 1189 typedef typename From::Edge Edge; 1190 typedef typename From::EdgeIt EdgeIt; 1191 1192 typedef typename To::Node TNode; 1193 typedef typename To::RedNode TRedNode; 1194 typedef typename To::BlueNode TBlueNode; 1195 typedef typename To::Arc TArc; 1196 typedef typename To::Edge TEdge; 1197 1198 typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap; 1199 typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap; 1200 typedef typename From::template EdgeMap<TEdge> EdgeRefMap; 1201 1202 struct NodeRefMap { 1203 NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref, 1204 const BlueNodeRefMap& blue_node_ref) 1205 : _from(from), _red_node_ref(red_node_ref), 1206 _blue_node_ref(blue_node_ref) {} 1207 1208 typedef typename From::Node Key; 1209 typedef typename To::Node Value; 1210 1211 Value operator[](const Key& key) const { 1212 if (_from.red(key)) { 1213 return _red_node_ref[_from.asRedNodeUnsafe(key)]; 1214 } else { 1215 return _blue_node_ref[_from.asBlueNodeUnsafe(key)]; 1216 } 1217 } 1218 1219 const From& _from; 1220 const RedNodeRefMap& _red_node_ref; 1221 const BlueNodeRefMap& _blue_node_ref; 1222 }; 1223 1224 struct ArcRefMap { 1225 ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref) 1226 : _from(from), _to(to), _edge_ref(edge_ref) {} 1227 1228 typedef typename From::Arc Key; 1229 typedef typename To::Arc Value; 1230 1231 Value operator[](const Key& key) const { 1232 return _to.direct(_edge_ref[key], _from.direction(key)); 1233 } 1234 1235 const From& _from; 1236 const To& _to; 1237 const EdgeRefMap& _edge_ref; 1238 }; 1239 1240 public: 1241 1242 /// \brief Constructor of BpGraphCopy. 1243 /// 1244 /// Constructor of BpGraphCopy for copying the content of the 1245 /// \c from graph into the \c to graph. 1246 BpGraphCopy(const From& from, To& to) 1247 : _from(from), _to(to) {} 1248 1249 /// \brief Destructor of BpGraphCopy 1250 /// 1251 /// Destructor of BpGraphCopy. 1252 ~BpGraphCopy() { 1253 for (int i = 0; i < int(_node_maps.size()); ++i) { 1254 delete _node_maps[i]; 1255 } 1256 for (int i = 0; i < int(_red_maps.size()); ++i) { 1257 delete _red_maps[i]; 1258 } 1259 for (int i = 0; i < int(_blue_maps.size()); ++i) { 1260 delete _blue_maps[i]; 1261 } 1262 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1263 delete _arc_maps[i]; 1264 } 1265 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1266 delete _edge_maps[i]; 1267 } 1268 } 1269 1270 /// \brief Copy the node references into the given map. 1271 /// 1272 /// This function copies the node references into the given map. 1273 /// The parameter should be a map, whose key type is the Node type of 1274 /// the source graph, while the value type is the Node type of the 1275 /// destination graph. 1276 template <typename NodeRef> 1277 BpGraphCopy& nodeRef(NodeRef& map) { 1278 _node_maps.push_back(new _core_bits::RefCopy<From, Node, 1279 NodeRefMap, NodeRef>(map)); 1280 return *this; 1281 } 1282 1283 /// \brief Copy the node cross references into the given map. 1284 /// 1285 /// This function copies the node cross references (reverse references) 1286 /// into the given map. The parameter should be a map, whose key type 1287 /// is the Node type of the destination graph, while the value type is 1288 /// the Node type of the source graph. 1289 template <typename NodeCrossRef> 1290 BpGraphCopy& nodeCrossRef(NodeCrossRef& map) { 1291 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, 1292 NodeRefMap, NodeCrossRef>(map)); 1293 return *this; 1294 } 1295 1296 /// \brief Make a copy of the given node map. 1297 /// 1298 /// This function makes a copy of the given node map for the newly 1299 /// created graph. 1300 /// The key type of the new map \c tmap should be the Node type of the 1301 /// destination graph, and the key type of the original map \c map 1302 /// should be the Node type of the source graph. 1303 template <typename FromMap, typename ToMap> 1304 BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { 1305 _node_maps.push_back(new _core_bits::MapCopy<From, Node, 1306 NodeRefMap, FromMap, ToMap>(map, tmap)); 1307 return *this; 1308 } 1309 1310 /// \brief Make a copy of the given node. 1311 /// 1312 /// This function makes a copy of the given node. 1313 BpGraphCopy& node(const Node& node, TNode& tnode) { 1314 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 1315 NodeRefMap, TNode>(node, tnode)); 1316 return *this; 1317 } 1318 1319 /// \brief Copy the red node references into the given map. 1320 /// 1321 /// This function copies the red node references into the given 1322 /// map. The parameter should be a map, whose key type is the 1323 /// Node type of the source graph with the red item set, while the 1324 /// value type is the Node type of the destination graph. 1325 template <typename RedRef> 1326 BpGraphCopy& redRef(RedRef& map) { 1327 _red_maps.push_back(new _core_bits::RefCopy<From, RedNode, 1328 RedNodeRefMap, RedRef>(map)); 1329 return *this; 1330 } 1331 1332 /// \brief Copy the red node cross references into the given map. 1333 /// 1334 /// This function copies the red node cross references (reverse 1335 /// references) into the given map. The parameter should be a map, 1336 /// whose key type is the Node type of the destination graph with 1337 /// the red item set, while the value type is the Node type of the 1338 /// source graph. 1339 template <typename RedCrossRef> 1340 BpGraphCopy& redCrossRef(RedCrossRef& map) { 1341 _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode, 1342 RedNodeRefMap, RedCrossRef>(map)); 1343 return *this; 1344 } 1345 1346 /// \brief Make a copy of the given red node map. 1347 /// 1348 /// This function makes a copy of the given red node map for the newly 1349 /// created graph. 1350 /// The key type of the new map \c tmap should be the Node type of 1351 /// the destination graph with the red items, and the key type of 1352 /// the original map \c map should be the Node type of the source 1353 /// graph. 1354 template <typename FromMap, typename ToMap> 1355 BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) { 1356 _red_maps.push_back(new _core_bits::MapCopy<From, RedNode, 1357 RedNodeRefMap, FromMap, ToMap>(map, tmap)); 1358 return *this; 1359 } 1360 1361 /// \brief Make a copy of the given red node. 1362 /// 1363 /// This function makes a copy of the given red node. 1364 BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) { 1365 _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode, 1366 RedNodeRefMap, TRedNode>(node, tnode)); 1367 return *this; 1368 } 1369 1370 /// \brief Copy the blue node references into the given map. 1371 /// 1372 /// This function copies the blue node references into the given 1373 /// map. The parameter should be a map, whose key type is the 1374 /// Node type of the source graph with the blue item set, while the 1375 /// value type is the Node type of the destination graph. 1376 template <typename BlueRef> 1377 BpGraphCopy& blueRef(BlueRef& map) { 1378 _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode, 1379 BlueNodeRefMap, BlueRef>(map)); 1380 return *this; 1381 } 1382 1383 /// \brief Copy the blue node cross references into the given map. 1384 /// 1385 /// This function copies the blue node cross references (reverse 1386 /// references) into the given map. The parameter should be a map, 1387 /// whose key type is the Node type of the destination graph with 1388 /// the blue item set, while the value type is the Node type of the 1389 /// source graph. 1390 template <typename BlueCrossRef> 1391 BpGraphCopy& blueCrossRef(BlueCrossRef& map) { 1392 _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode, 1393 BlueNodeRefMap, BlueCrossRef>(map)); 1394 return *this; 1395 } 1396 1397 /// \brief Make a copy of the given blue node map. 1398 /// 1399 /// This function makes a copy of the given blue node map for the newly 1400 /// created graph. 1401 /// The key type of the new map \c tmap should be the Node type of 1402 /// the destination graph with the blue items, and the key type of 1403 /// the original map \c map should be the Node type of the source 1404 /// graph. 1405 template <typename FromMap, typename ToMap> 1406 BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) { 1407 _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode, 1408 BlueNodeRefMap, FromMap, ToMap>(map, tmap)); 1409 return *this; 1410 } 1411 1412 /// \brief Make a copy of the given blue node. 1413 /// 1414 /// This function makes a copy of the given blue node. 1415 BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) { 1416 _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode, 1417 BlueNodeRefMap, TBlueNode>(node, tnode)); 1418 return *this; 1419 } 1420 1421 /// \brief Copy the arc references into the given map. 1422 /// 1423 /// This function copies the arc references into the given map. 1424 /// The parameter should be a map, whose key type is the Arc type of 1425 /// the source graph, while the value type is the Arc type of the 1426 /// destination graph. 1427 template <typename ArcRef> 1428 BpGraphCopy& arcRef(ArcRef& map) { 1429 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, 1430 ArcRefMap, ArcRef>(map)); 1431 return *this; 1432 } 1433 1434 /// \brief Copy the arc cross references into the given map. 1435 /// 1436 /// This function copies the arc cross references (reverse references) 1437 /// into the given map. The parameter should be a map, whose key type 1438 /// is the Arc type of the destination graph, while the value type is 1439 /// the Arc type of the source graph. 1440 template <typename ArcCrossRef> 1441 BpGraphCopy& arcCrossRef(ArcCrossRef& map) { 1442 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, 1443 ArcRefMap, ArcCrossRef>(map)); 1444 return *this; 1445 } 1446 1447 /// \brief Make a copy of the given arc map. 1448 /// 1449 /// This function makes a copy of the given arc map for the newly 1450 /// created graph. 1451 /// The key type of the new map \c tmap should be the Arc type of the 1452 /// destination graph, and the key type of the original map \c map 1453 /// should be the Arc type of the source graph. 1454 template <typename FromMap, typename ToMap> 1455 BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) { 1456 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 1457 ArcRefMap, FromMap, ToMap>(map, tmap)); 1458 return *this; 1459 } 1460 1461 /// \brief Make a copy of the given arc. 1462 /// 1463 /// This function makes a copy of the given arc. 1464 BpGraphCopy& arc(const Arc& arc, TArc& tarc) { 1465 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 1466 ArcRefMap, TArc>(arc, tarc)); 1467 return *this; 1468 } 1469 1470 /// \brief Copy the edge references into the given map. 1471 /// 1472 /// This function copies the edge references into the given map. 1473 /// The parameter should be a map, whose key type is the Edge type of 1474 /// the source graph, while the value type is the Edge type of the 1475 /// destination graph. 1476 template <typename EdgeRef> 1477 BpGraphCopy& edgeRef(EdgeRef& map) { 1478 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge, 1479 EdgeRefMap, EdgeRef>(map)); 1480 return *this; 1481 } 1482 1483 /// \brief Copy the edge cross references into the given map. 1484 /// 1485 /// This function copies the edge cross references (reverse references) 1486 /// into the given map. The parameter should be a map, whose key type 1487 /// is the Edge type of the destination graph, while the value type is 1488 /// the Edge type of the source graph. 1489 template <typename EdgeCrossRef> 1490 BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) { 1491 _edge_maps.push_back(new _core_bits::CrossRefCopy<From, 1492 Edge, EdgeRefMap, EdgeCrossRef>(map)); 1493 return *this; 1494 } 1495 1496 /// \brief Make a copy of the given edge map. 1497 /// 1498 /// This function makes a copy of the given edge map for the newly 1499 /// created graph. 1500 /// The key type of the new map \c tmap should be the Edge type of the 1501 /// destination graph, and the key type of the original map \c map 1502 /// should be the Edge type of the source graph. 1503 template <typename FromMap, typename ToMap> 1504 BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) { 1505 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, 1506 EdgeRefMap, FromMap, ToMap>(map, tmap)); 1507 return *this; 1508 } 1509 1510 /// \brief Make a copy of the given edge. 1511 /// 1512 /// This function makes a copy of the given edge. 1513 BpGraphCopy& edge(const Edge& edge, TEdge& tedge) { 1514 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, 1515 EdgeRefMap, TEdge>(edge, tedge)); 1516 return *this; 1517 } 1518 1519 /// \brief Execute copying. 1520 /// 1521 /// This function executes the copying of the graph along with the 1522 /// copying of the assigned data. 1523 void run() { 1524 RedNodeRefMap redNodeRefMap(_from); 1525 BlueNodeRefMap blueNodeRefMap(_from); 1526 NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap); 1527 EdgeRefMap edgeRefMap(_from); 1528 ArcRefMap arcRefMap(_from, _to, edgeRefMap); 1529 _core_bits::BpGraphCopySelector<To>:: 1530 copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap); 1531 for (int i = 0; i < int(_node_maps.size()); ++i) { 1532 _node_maps[i]->copy(_from, nodeRefMap); 1533 } 1534 for (int i = 0; i < int(_red_maps.size()); ++i) { 1535 _red_maps[i]->copy(_from, redNodeRefMap); 1536 } 1537 for (int i = 0; i < int(_blue_maps.size()); ++i) { 1538 _blue_maps[i]->copy(_from, blueNodeRefMap); 1539 } 1540 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1541 _edge_maps[i]->copy(_from, edgeRefMap); 1542 } 1543 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1544 _arc_maps[i]->copy(_from, arcRefMap); 1545 } 1546 } 1547 1548 private: 1549 1550 const From& _from; 1551 To& _to; 1552 1553 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 1554 _node_maps; 1555 1556 std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* > 1557 _red_maps; 1558 1559 std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* > 1560 _blue_maps; 1561 1562 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 1563 _arc_maps; 1564 1565 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 1566 _edge_maps; 1567 1568 }; 1569 1570 /// \brief Copy a graph to another graph. 1571 /// 1572 /// This function copies a graph to another graph. 1573 /// The complete usage of it is detailed in the BpGraphCopy class, 1574 /// but a short example shows a basic work: 1575 ///\code 1576 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run(); 1577 ///\endcode 1578 /// 1579 /// After the copy the \c nr map will contain the mapping from the 1580 /// nodes of the \c from graph to the nodes of the \c to graph and 1581 /// \c ecr will contain the mapping from the edges of the \c to graph 1582 /// to the edges of the \c from graph. 1583 /// 1584 /// \see BpGraphCopy 1585 template <typename From, typename To> 1586 BpGraphCopy<From, To> 1587 bpGraphCopy(const From& from, To& to) { 1588 return BpGraphCopy<From, To>(from, to); 992 1589 } 993 1590 … … 1258 1855 /// The Digraph type 1259 1856 typedef GR Digraph; 1260 1857 1261 1858 protected: 1262 1859 -
lemon/cplex.cc
r989 r1016 41 41 int status; 42 42 _cnt = new int; 43 (*_cnt) = 1; 43 44 _env = CPXopenCPLEX(&status); 44 45 if (_env == 0) { -
lemon/cycle_canceling.h
r1003 r1013 36 36 #include <lemon/bellman_ford.h> 37 37 #include <lemon/howard_mmc.h> 38 #include <lemon/hartmann_orlin_mmc.h> 38 39 39 40 namespace lemon { … … 928 929 // Execute the "Minimum Mean Cycle Canceling" method 929 930 void startMinMeanCycleCanceling() { 930 typedef SimplePath<StaticDigraph> SPath;931 typedef Path<StaticDigraph> SPath; 931 932 typedef typename SPath::ArcIt SPathArcIt; 932 933 typedef typename HowardMmc<StaticDigraph, CostArcMap> 933 ::template SetPath<SPath>::Create MMC; 934 ::template SetPath<SPath>::Create HwMmc; 935 typedef typename HartmannOrlinMmc<StaticDigraph, CostArcMap> 936 ::template SetPath<SPath>::Create HoMmc; 937 938 const double HW_ITER_LIMIT_FACTOR = 1.0; 939 const int HW_ITER_LIMIT_MIN_VALUE = 5; 940 941 const int hw_iter_limit = 942 std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num), 943 HW_ITER_LIMIT_MIN_VALUE); 934 944 935 945 SPath cycle; 936 MMCmmc(_sgr, _cost_map);937 mmc.cycle(cycle);946 HwMmc hw_mmc(_sgr, _cost_map); 947 hw_mmc.cycle(cycle); 938 948 buildResidualNetwork(); 939 while (mmc.findCycleMean() && mmc.cycleCost() < 0) { 940 // Find the cycle 941 mmc.findCycle(); 942 949 while (true) { 950 951 typename HwMmc::TerminationCause hw_tc = 952 hw_mmc.findCycleMean(hw_iter_limit); 953 if (hw_tc == HwMmc::ITERATION_LIMIT) { 954 // Howard's algorithm reached the iteration limit, start a 955 // strongly polynomial algorithm instead 956 HoMmc ho_mmc(_sgr, _cost_map); 957 ho_mmc.cycle(cycle); 958 // Find a minimum mean cycle (Hartmann-Orlin algorithm) 959 if (!(ho_mmc.findCycleMean() && ho_mmc.cycleCost() < 0)) break; 960 ho_mmc.findCycle(); 961 } else { 962 // Find a minimum mean cycle (Howard algorithm) 963 if (!(hw_tc == HwMmc::OPTIMAL && hw_mmc.cycleCost() < 0)) break; 964 hw_mmc.findCycle(); 965 } 966 943 967 // Compute delta value 944 968 Value delta = INF; … … 965 989 const double LIMIT_FACTOR = 1.0; 966 990 const int MIN_LIMIT = 5; 991 const double HW_ITER_LIMIT_FACTOR = 1.0; 992 const int HW_ITER_LIMIT_MIN_VALUE = 5; 993 994 const int hw_iter_limit = 995 std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num), 996 HW_ITER_LIMIT_MIN_VALUE); 967 997 968 998 // Contruct auxiliary data vectors … … 1138 1168 } 1139 1169 } else { 1140 typedef HowardMmc<StaticDigraph, CostArcMap> MMC; 1170 typedef HowardMmc<StaticDigraph, CostArcMap> HwMmc; 1171 typedef HartmannOrlinMmc<StaticDigraph, CostArcMap> HoMmc; 1141 1172 typedef typename BellmanFord<StaticDigraph, CostArcMap> 1142 1173 ::template SetDistMap<CostNodeMap>::Create BF; 1143 1174 1144 1175 // Set epsilon to the minimum cycle mean 1176 Cost cycle_cost = 0; 1177 int cycle_size = 1; 1145 1178 buildResidualNetwork(); 1146 MMC mmc(_sgr, _cost_map); 1147 mmc.findCycleMean(); 1148 epsilon = -mmc.cycleMean(); 1149 Cost cycle_cost = mmc.cycleCost(); 1150 int cycle_size = mmc.cycleSize(); 1179 HwMmc hw_mmc(_sgr, _cost_map); 1180 if (hw_mmc.findCycleMean(hw_iter_limit) == HwMmc::ITERATION_LIMIT) { 1181 // Howard's algorithm reached the iteration limit, start a 1182 // strongly polynomial algorithm instead 1183 HoMmc ho_mmc(_sgr, _cost_map); 1184 ho_mmc.findCycleMean(); 1185 epsilon = -ho_mmc.cycleMean(); 1186 cycle_cost = ho_mmc.cycleCost(); 1187 cycle_size = ho_mmc.cycleSize(); 1188 } else { 1189 // Set epsilon 1190 epsilon = -hw_mmc.cycleMean(); 1191 cycle_cost = hw_mmc.cycleCost(); 1192 cycle_size = hw_mmc.cycleSize(); 1193 } 1151 1194 1152 1195 // Compute feasible potentials for the current epsilon -
lemon/full_graph.h
r877 r1025 622 622 }; 623 623 624 class FullBpGraphBase { 625 626 protected: 627 628 int _red_num, _blue_num; 629 int _node_num, _edge_num; 630 631 public: 632 633 typedef FullBpGraphBase Graph; 634 635 class Node; 636 class Arc; 637 class Edge; 638 639 class Node { 640 friend class FullBpGraphBase; 641 protected: 642 643 int _id; 644 explicit Node(int id) { _id = id;} 645 646 public: 647 Node() {} 648 Node (Invalid) { _id = -1; } 649 bool operator==(const Node& node) const {return _id == node._id;} 650 bool operator!=(const Node& node) const {return _id != node._id;} 651 bool operator<(const Node& node) const {return _id < node._id;} 652 }; 653 654 class RedNode : public Node { 655 friend class FullBpGraphBase; 656 protected: 657 658 explicit RedNode(int pid) : Node(pid) {} 659 660 public: 661 RedNode() {} 662 RedNode(const RedNode& node) : Node(node) {} 663 RedNode(Invalid) : Node(INVALID){} 664 }; 665 666 class BlueNode : public Node { 667 friend class FullBpGraphBase; 668 protected: 669 670 explicit BlueNode(int pid) : Node(pid) {} 671 672 public: 673 BlueNode() {} 674 BlueNode(const BlueNode& node) : Node(node) {} 675 BlueNode(Invalid) : Node(INVALID){} 676 }; 677 678 class Edge { 679 friend class FullBpGraphBase; 680 protected: 681 682 int _id; 683 explicit Edge(int id) { _id = id;} 684 685 public: 686 Edge() {} 687 Edge (Invalid) { _id = -1; } 688 bool operator==(const Edge& arc) const {return _id == arc._id;} 689 bool operator!=(const Edge& arc) const {return _id != arc._id;} 690 bool operator<(const Edge& arc) const {return _id < arc._id;} 691 }; 692 693 class Arc { 694 friend class FullBpGraphBase; 695 protected: 696 697 int _id; 698 explicit Arc(int id) { _id = id;} 699 700 public: 701 operator Edge() const { 702 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 703 } 704 705 Arc() {} 706 Arc (Invalid) { _id = -1; } 707 bool operator==(const Arc& arc) const {return _id == arc._id;} 708 bool operator!=(const Arc& arc) const {return _id != arc._id;} 709 bool operator<(const Arc& arc) const {return _id < arc._id;} 710 }; 711 712 713 protected: 714 715 FullBpGraphBase() 716 : _red_num(0), _blue_num(0), _node_num(0), _edge_num(0) {} 717 718 void construct(int redNum, int blueNum) { 719 _red_num = redNum; _blue_num = blueNum; 720 _node_num = redNum + blueNum; _edge_num = redNum * blueNum; 721 } 722 723 public: 724 725 typedef True NodeNumTag; 726 typedef True EdgeNumTag; 727 typedef True ArcNumTag; 728 729 int nodeNum() const { return _node_num; } 730 int redNum() const { return _red_num; } 731 int blueNum() const { return _blue_num; } 732 int edgeNum() const { return _edge_num; } 733 int arcNum() const { return 2 * _edge_num; } 734 735 int maxNodeId() const { return _node_num - 1; } 736 int maxRedId() const { return _red_num - 1; } 737 int maxBlueId() const { return _blue_num - 1; } 738 int maxEdgeId() const { return _edge_num - 1; } 739 int maxArcId() const { return 2 * _edge_num - 1; } 740 741 bool red(Node n) const { return n._id < _red_num; } 742 bool blue(Node n) const { return n._id >= _red_num; } 743 744 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); } 745 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); } 746 747 Node source(Arc a) const { 748 if (a._id & 1) { 749 return Node((a._id >> 1) % _red_num); 750 } else { 751 return Node((a._id >> 1) / _red_num + _red_num); 752 } 753 } 754 Node target(Arc a) const { 755 if (a._id & 1) { 756 return Node((a._id >> 1) / _red_num + _red_num); 757 } else { 758 return Node((a._id >> 1) % _red_num); 759 } 760 } 761 762 RedNode redNode(Edge e) const { 763 return RedNode(e._id % _red_num); 764 } 765 BlueNode blueNode(Edge e) const { 766 return BlueNode(e._id / _red_num + _red_num); 767 } 768 769 static bool direction(Arc a) { 770 return (a._id & 1) == 1; 771 } 772 773 static Arc direct(Edge e, bool d) { 774 return Arc(e._id * 2 + (d ? 1 : 0)); 775 } 776 777 void first(Node& node) const { 778 node._id = _node_num - 1; 779 } 780 781 static void next(Node& node) { 782 --node._id; 783 } 784 785 void first(RedNode& node) const { 786 node._id = _red_num - 1; 787 } 788 789 static void next(RedNode& node) { 790 --node._id; 791 } 792 793 void first(BlueNode& node) const { 794 if (_red_num == _node_num) node._id = -1; 795 else node._id = _node_num - 1; 796 } 797 798 void next(BlueNode& node) const { 799 if (node._id == _red_num) node._id = -1; 800 else --node._id; 801 } 802 803 void first(Arc& arc) const { 804 arc._id = 2 * _edge_num - 1; 805 } 806 807 static void next(Arc& arc) { 808 --arc._id; 809 } 810 811 void first(Edge& arc) const { 812 arc._id = _edge_num - 1; 813 } 814 815 static void next(Edge& arc) { 816 --arc._id; 817 } 818 819 void firstOut(Arc &a, const Node& v) const { 820 if (v._id < _red_num) { 821 a._id = 2 * (v._id + _red_num * (_blue_num - 1)) + 1; 822 } else { 823 a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num)); 824 } 825 } 826 void nextOut(Arc &a) const { 827 if (a._id & 1) { 828 a._id -= 2 * _red_num; 829 if (a._id < 0) a._id = -1; 830 } else { 831 if (a._id % (2 * _red_num) == 0) a._id = -1; 832 else a._id -= 2; 833 } 834 } 835 836 void firstIn(Arc &a, const Node& v) const { 837 if (v._id < _red_num) { 838 a._id = 2 * (v._id + _red_num * (_blue_num - 1)); 839 } else { 840 a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num)) + 1; 841 } 842 } 843 void nextIn(Arc &a) const { 844 if (a._id & 1) { 845 if (a._id % (2 * _red_num) == 1) a._id = -1; 846 else a._id -= 2; 847 } else { 848 a._id -= 2 * _red_num; 849 if (a._id < 0) a._id = -1; 850 } 851 } 852 853 void firstInc(Edge &e, bool& d, const Node& v) const { 854 if (v._id < _red_num) { 855 d = true; 856 e._id = v._id + _red_num * (_blue_num - 1); 857 } else { 858 d = false; 859 e._id = _red_num - 1 + _red_num * (v._id - _red_num); 860 } 861 } 862 void nextInc(Edge &e, bool& d) const { 863 if (d) { 864 e._id -= _red_num; 865 if (e._id < 0) e._id = -1; 866 } else { 867 if (e._id % _red_num == 0) e._id = -1; 868 else --e._id; 869 } 870 } 871 872 static int id(const Node& v) { return v._id; } 873 int id(const RedNode& v) const { return v._id; } 874 int id(const BlueNode& v) const { return v._id - _red_num; } 875 static int id(Arc e) { return e._id; } 876 static int id(Edge e) { return e._id; } 877 878 static Node nodeFromId(int id) { return Node(id);} 879 static Arc arcFromId(int id) { return Arc(id);} 880 static Edge edgeFromId(int id) { return Edge(id);} 881 882 bool valid(Node n) const { 883 return n._id >= 0 && n._id < _node_num; 884 } 885 bool valid(Arc a) const { 886 return a._id >= 0 && a._id < 2 * _edge_num; 887 } 888 bool valid(Edge e) const { 889 return e._id >= 0 && e._id < _edge_num; 890 } 891 892 RedNode redNode(int index) const { 893 return RedNode(index); 894 } 895 896 int index(RedNode n) const { 897 return n._id; 898 } 899 900 BlueNode blueNode(int index) const { 901 return BlueNode(index + _red_num); 902 } 903 904 int index(BlueNode n) const { 905 return n._id - _red_num; 906 } 907 908 void clear() { 909 _red_num = 0; _blue_num = 0; 910 _node_num = 0; _edge_num = 0; 911 } 912 913 Edge edge(const Node& u, const Node& v) const { 914 if (u._id < _red_num) { 915 if (v._id < _red_num) { 916 return Edge(-1); 917 } else { 918 return Edge(u._id + _red_num * (v._id - _red_num)); 919 } 920 } else { 921 if (v._id < _red_num) { 922 return Edge(v._id + _red_num * (u._id - _red_num)); 923 } else { 924 return Edge(-1); 925 } 926 } 927 } 928 929 Arc arc(const Node& u, const Node& v) const { 930 if (u._id < _red_num) { 931 if (v._id < _red_num) { 932 return Arc(-1); 933 } else { 934 return Arc(2 * (u._id + _red_num * (v._id - _red_num)) + 1); 935 } 936 } else { 937 if (v._id < _red_num) { 938 return Arc(2 * (v._id + _red_num * (u._id - _red_num))); 939 } else { 940 return Arc(-1); 941 } 942 } 943 } 944 945 typedef True FindEdgeTag; 946 typedef True FindArcTag; 947 948 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { 949 return prev != INVALID ? INVALID : edge(u, v); 950 } 951 952 Arc findArc(Node s, Node t, Arc prev = INVALID) const { 953 return prev != INVALID ? INVALID : arc(s, t); 954 } 955 956 }; 957 958 typedef BpGraphExtender<FullBpGraphBase> ExtendedFullBpGraphBase; 959 960 /// \ingroup graphs 961 /// 962 /// \brief An undirected full bipartite graph class. 963 /// 964 /// FullBpGraph is a simple and fast implmenetation of undirected 965 /// full bipartite graphs. It contains an edge between every 966 /// red-blue pairs of nodes, therefore the number of edges is 967 /// <tt>nr*nb</tt>. This class is completely static and it needs 968 /// constant memory space. Thus you can neither add nor delete 969 /// nodes or edges, however the structure can be resized using 970 /// resize(). 971 /// 972 /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept". 973 /// Most of its member functions and nested classes are documented 974 /// only in the concept class. 975 /// 976 /// This class provides constant time counting for nodes, edges and arcs. 977 /// 978 /// \sa FullGraph 979 class FullBpGraph : public ExtendedFullBpGraphBase { 980 public: 981 982 typedef ExtendedFullBpGraphBase Parent; 983 984 /// \brief Default constructor. 985 /// 986 /// Default constructor. The number of nodes and edges will be zero. 987 FullBpGraph() { construct(0, 0); } 988 989 /// \brief Constructor 990 /// 991 /// Constructor. 992 /// \param redNum The number of the red nodes. 993 /// \param blueNum The number of the blue nodes. 994 FullBpGraph(int redNum, int blueNum) { construct(redNum, blueNum); } 995 996 /// \brief Resizes the graph 997 /// 998 /// This function resizes the graph. It fully destroys and 999 /// rebuilds the structure, therefore the maps of the graph will be 1000 /// reallocated automatically and the previous values will be lost. 1001 void resize(int redNum, int blueNum) { 1002 Parent::notifier(Arc()).clear(); 1003 Parent::notifier(Edge()).clear(); 1004 Parent::notifier(Node()).clear(); 1005 Parent::notifier(BlueNode()).clear(); 1006 Parent::notifier(RedNode()).clear(); 1007 construct(redNum, blueNum); 1008 Parent::notifier(RedNode()).build(); 1009 Parent::notifier(BlueNode()).build(); 1010 Parent::notifier(Node()).build(); 1011 Parent::notifier(Edge()).build(); 1012 Parent::notifier(Arc()).build(); 1013 } 1014 1015 using Parent::redNode; 1016 using Parent::blueNode; 1017 1018 /// \brief Returns the red node with the given index. 1019 /// 1020 /// Returns the red node with the given index. Since this 1021 /// structure is completely static, the red nodes can be indexed 1022 /// with integers from the range <tt>[0..redNum()-1]</tt>. 1023 /// \sa redIndex() 1024 RedNode redNode(int index) const { return Parent::redNode(index); } 1025 1026 /// \brief Returns the index of the given red node. 1027 /// 1028 /// Returns the index of the given red node. Since this structure 1029 /// is completely static, the red nodes can be indexed with 1030 /// integers from the range <tt>[0..redNum()-1]</tt>. 1031 /// 1032 /// \sa operator()() 1033 int index(RedNode node) const { return Parent::index(node); } 1034 1035 /// \brief Returns the blue node with the given index. 1036 /// 1037 /// Returns the blue node with the given index. Since this 1038 /// structure is completely static, the blue nodes can be indexed 1039 /// with integers from the range <tt>[0..blueNum()-1]</tt>. 1040 /// \sa blueIndex() 1041 BlueNode blueNode(int index) const { return Parent::blueNode(index); } 1042 1043 /// \brief Returns the index of the given blue node. 1044 /// 1045 /// Returns the index of the given blue node. Since this structure 1046 /// is completely static, the blue nodes can be indexed with 1047 /// integers from the range <tt>[0..blueNum()-1]</tt>. 1048 /// 1049 /// \sa operator()() 1050 int index(BlueNode node) const { return Parent::index(node); } 1051 1052 /// \brief Returns the edge which connects the given nodes. 1053 /// 1054 /// Returns the edge which connects the given nodes. 1055 Edge edge(const Node& u, const Node& v) const { 1056 return Parent::edge(u, v); 1057 } 1058 1059 /// \brief Returns the arc which connects the given nodes. 1060 /// 1061 /// Returns the arc which connects the given nodes. 1062 Arc arc(const Node& u, const Node& v) const { 1063 return Parent::arc(u, v); 1064 } 1065 1066 /// \brief Number of nodes. 1067 int nodeNum() const { return Parent::nodeNum(); } 1068 /// \brief Number of red nodes. 1069 int redNum() const { return Parent::redNum(); } 1070 /// \brief Number of blue nodes. 1071 int blueNum() const { return Parent::blueNum(); } 1072 /// \brief Number of arcs. 1073 int arcNum() const { return Parent::arcNum(); } 1074 /// \brief Number of edges. 1075 int edgeNum() const { return Parent::edgeNum(); } 1076 }; 1077 624 1078 625 1079 } //namespace lemon -
lemon/howard_mmc.h
r1002 r1012 150 150 typedef TR Traits; 151 151 152 /// \brief Constants for the causes of search termination. 153 /// 154 /// Enum type containing constants for the different causes of search 155 /// termination. The \ref findCycleMean() function returns one of 156 /// these values. 157 enum TerminationCause { 158 159 /// No directed cycle can be found in the digraph. 160 NO_CYCLE = 0, 161 162 /// Optimal solution (minimum cycle mean) is found. 163 OPTIMAL = 1, 164 165 /// The iteration count limit is reached. 166 ITERATION_LIMIT 167 }; 168 152 169 private: 153 170 … … 325 342 } 326 343 327 /// \brief Find the minimum cycle mean .344 /// \brief Find the minimum cycle mean (or an upper bound). 328 345 /// 329 346 /// This function finds the minimum mean cost of the directed 330 /// cycles in the digraph. 331 /// 332 /// \return \c true if a directed cycle exists in the digraph. 333 bool findCycleMean() { 347 /// cycles in the digraph (or an upper bound for it). 348 /// 349 /// By default, the function finds the exact minimum cycle mean, 350 /// but an optional limit can also be specified for the number of 351 /// iterations performed during the search process. 352 /// The return value indicates if the optimal solution is found 353 /// or the iteration limit is reached. In the latter case, an 354 /// approximate solution is provided, which corresponds to a directed 355 /// cycle whose mean cost is relatively small, but not necessarily 356 /// minimal. 357 /// 358 /// \param limit The maximum allowed number of iterations during 359 /// the search process. Its default value implies that the algorithm 360 /// runs until it finds the exact optimal solution. 361 /// 362 /// \return The termination cause of the search process. 363 /// For more information, see \ref TerminationCause. 364 TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max()) { 334 365 // Initialize and find strongly connected components 335 366 init(); … … 337 368 338 369 // Find the minimum cycle mean in the components 370 int iter_count = 0; 371 bool iter_limit_reached = false; 339 372 for (int comp = 0; comp < _comp_num; ++comp) { 340 373 // Find the minimum mean cycle in the current component 341 374 if (!buildPolicyGraph(comp)) continue; 342 375 while (true) { 376 if (++iter_count > limit) { 377 iter_limit_reached = true; 378 break; 379 } 343 380 findPolicyCycle(); 344 381 if (!computeNodeDistances()) break; 345 382 } 383 346 384 // Update the best cycle (global minimum mean cycle) 347 385 if ( _curr_found && (!_best_found || … … 352 390 _best_node = _curr_node; 353 391 } 354 } 355 return _best_found; 392 393 if (iter_limit_reached) break; 394 } 395 396 if (iter_limit_reached) { 397 return ITERATION_LIMIT; 398 } else { 399 return _best_found ? OPTIMAL : NO_CYCLE; 400 } 356 401 } 357 402 -
lemon/lgf_reader.h
r966 r1030 155 155 }; 156 156 157 template <typename Value> 157 template <typename Value, 158 typename Map = std::map<std::string, Value> > 158 159 struct MapLookUpConverter { 159 const std::map<std::string, Value>& _map;160 161 MapLookUpConverter(const std::map<std::string, Value>& map)160 const Map& _map; 161 162 MapLookUpConverter(const Map& map) 162 163 : _map(map) {} 163 164 164 165 Value operator()(const std::string& str) { 165 typename std::map<std::string, Value>::const_iterator it = 166 _map.find(str); 166 typename Map::const_iterator it = _map.find(str); 167 167 if (it == _map.end()) { 168 168 std::ostringstream msg; … … 171 171 } 172 172 return it->second; 173 } 174 }; 175 176 template <typename Value, 177 typename Map1 = std::map<std::string, Value>, 178 typename Map2 = std::map<std::string, Value> > 179 struct DoubleMapLookUpConverter { 180 const Map1& _map1; 181 const Map2& _map2; 182 183 DoubleMapLookUpConverter(const Map1& map1, const Map2& map2) 184 : _map1(map1), _map2(map2) {} 185 186 Value operator()(const std::string& str) { 187 typename Map1::const_iterator it1 = _map1.find(str); 188 typename Map2::const_iterator it2 = _map2.find(str); 189 if (it1 == _map1.end()) { 190 if (it2 == _map2.end()) { 191 std::ostringstream msg; 192 msg << "Item not found: " << str; 193 throw FormatError(msg.str()); 194 } else { 195 return it2->second; 196 } 197 } else { 198 if (it2 == _map2.end()) { 199 return it1->second; 200 } else { 201 std::ostringstream msg; 202 msg << "Item is ambigous: " << str; 203 throw FormatError(msg.str()); 204 } 205 } 173 206 } 174 207 }; … … 2129 2162 } 2130 2163 2164 template <typename BGR> 2165 class BpGraphReader; 2166 2167 template <typename TBGR> 2168 BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is = std::cin); 2169 template <typename TBGR> 2170 BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn); 2171 template <typename TBGR> 2172 BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn); 2173 2174 /// \ingroup lemon_io 2175 /// 2176 /// \brief \ref lgf-format "LGF" reader for bipartite graphs 2177 /// 2178 /// This utility reads an \ref lgf-format "LGF" file. 2179 /// 2180 /// It can be used almost the same way as \c GraphReader, but it 2181 /// reads the red and blue nodes from separate sections, and these 2182 /// sections can contain different set of maps. 2183 /// 2184 /// The red and blue node maps are read from the corresponding 2185 /// sections. If a map is defined with the same name in both of 2186 /// these sections, then it can be read as a node map. 2187 template <typename BGR> 2188 class BpGraphReader { 2189 public: 2190 2191 typedef BGR Graph; 2192 2193 private: 2194 2195 TEMPLATE_BPGRAPH_TYPEDEFS(BGR); 2196 2197 std::istream* _is; 2198 bool local_is; 2199 std::string _filename; 2200 2201 BGR& _graph; 2202 2203 std::string _nodes_caption; 2204 std::string _edges_caption; 2205 std::string _attributes_caption; 2206 2207 typedef std::map<std::string, RedNode> RedNodeIndex; 2208 RedNodeIndex _red_node_index; 2209 typedef std::map<std::string, BlueNode> BlueNodeIndex; 2210 BlueNodeIndex _blue_node_index; 2211 typedef std::map<std::string, Edge> EdgeIndex; 2212 EdgeIndex _edge_index; 2213 2214 typedef std::vector<std::pair<std::string, 2215 _reader_bits::MapStorageBase<RedNode>*> > RedNodeMaps; 2216 RedNodeMaps _red_node_maps; 2217 typedef std::vector<std::pair<std::string, 2218 _reader_bits::MapStorageBase<BlueNode>*> > BlueNodeMaps; 2219 BlueNodeMaps _blue_node_maps; 2220 2221 typedef std::vector<std::pair<std::string, 2222 _reader_bits::MapStorageBase<Edge>*> > EdgeMaps; 2223 EdgeMaps _edge_maps; 2224 2225 typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 2226 Attributes; 2227 Attributes _attributes; 2228 2229 bool _use_nodes; 2230 bool _use_edges; 2231 2232 bool _skip_nodes; 2233 bool _skip_edges; 2234 2235 int line_num; 2236 std::istringstream line; 2237 2238 public: 2239 2240 /// \brief Constructor 2241 /// 2242 /// Construct an undirected graph reader, which reads from the given 2243 /// input stream. 2244 BpGraphReader(BGR& graph, std::istream& is = std::cin) 2245 : _is(&is), local_is(false), _graph(graph), 2246 _use_nodes(false), _use_edges(false), 2247 _skip_nodes(false), _skip_edges(false) {} 2248 2249 /// \brief Constructor 2250 /// 2251 /// Construct an undirected graph reader, which reads from the given 2252 /// file. 2253 BpGraphReader(BGR& graph, const std::string& fn) 2254 : _is(new std::ifstream(fn.c_str())), local_is(true), 2255 _filename(fn), _graph(graph), 2256 _use_nodes(false), _use_edges(false), 2257 _skip_nodes(false), _skip_edges(false) { 2258 if (!(*_is)) { 2259 delete _is; 2260 throw IoError("Cannot open file", fn); 2261 } 2262 } 2263 2264 /// \brief Constructor 2265 /// 2266 /// Construct an undirected graph reader, which reads from the given 2267 /// file. 2268 BpGraphReader(BGR& graph, const char* fn) 2269 : _is(new std::ifstream(fn)), local_is(true), 2270 _filename(fn), _graph(graph), 2271 _use_nodes(false), _use_edges(false), 2272 _skip_nodes(false), _skip_edges(false) { 2273 if (!(*_is)) { 2274 delete _is; 2275 throw IoError("Cannot open file", fn); 2276 } 2277 } 2278 2279 /// \brief Destructor 2280 ~BpGraphReader() { 2281 for (typename RedNodeMaps::iterator it = _red_node_maps.begin(); 2282 it != _red_node_maps.end(); ++it) { 2283 delete it->second; 2284 } 2285 2286 for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin(); 2287 it != _blue_node_maps.end(); ++it) { 2288 delete it->second; 2289 } 2290 2291 for (typename EdgeMaps::iterator it = _edge_maps.begin(); 2292 it != _edge_maps.end(); ++it) { 2293 delete it->second; 2294 } 2295 2296 for (typename Attributes::iterator it = _attributes.begin(); 2297 it != _attributes.end(); ++it) { 2298 delete it->second; 2299 } 2300 2301 if (local_is) { 2302 delete _is; 2303 } 2304 2305 } 2306 2307 private: 2308 template <typename TBGR> 2309 friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is); 2310 template <typename TBGR> 2311 friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, 2312 const std::string& fn); 2313 template <typename TBGR> 2314 friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn); 2315 2316 BpGraphReader(BpGraphReader& other) 2317 : _is(other._is), local_is(other.local_is), _graph(other._graph), 2318 _use_nodes(other._use_nodes), _use_edges(other._use_edges), 2319 _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) { 2320 2321 other._is = 0; 2322 other.local_is = false; 2323 2324 _red_node_index.swap(other._red_node_index); 2325 _blue_node_index.swap(other._blue_node_index); 2326 _edge_index.swap(other._edge_index); 2327 2328 _red_node_maps.swap(other._red_node_maps); 2329 _blue_node_maps.swap(other._blue_node_maps); 2330 _edge_maps.swap(other._edge_maps); 2331 _attributes.swap(other._attributes); 2332 2333 _nodes_caption = other._nodes_caption; 2334 _edges_caption = other._edges_caption; 2335 _attributes_caption = other._attributes_caption; 2336 2337 } 2338 2339 BpGraphReader& operator=(const BpGraphReader&); 2340 2341 public: 2342 2343 /// \name Reading Rules 2344 /// @{ 2345 2346 /// \brief Node map reading rule 2347 /// 2348 /// Add a node map reading rule to the reader. 2349 template <typename Map> 2350 BpGraphReader& nodeMap(const std::string& caption, Map& map) { 2351 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>(); 2352 _reader_bits::MapStorageBase<RedNode>* red_storage = 2353 new _reader_bits::MapStorage<RedNode, Map>(map); 2354 _red_node_maps.push_back(std::make_pair(caption, red_storage)); 2355 _reader_bits::MapStorageBase<BlueNode>* blue_storage = 2356 new _reader_bits::MapStorage<BlueNode, Map>(map); 2357 _blue_node_maps.push_back(std::make_pair(caption, blue_storage)); 2358 return *this; 2359 } 2360 2361 /// \brief Node map reading rule 2362 /// 2363 /// Add a node map reading rule with specialized converter to the 2364 /// reader. 2365 template <typename Map, typename Converter> 2366 BpGraphReader& nodeMap(const std::string& caption, Map& map, 2367 const Converter& converter = Converter()) { 2368 checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>(); 2369 _reader_bits::MapStorageBase<RedNode>* red_storage = 2370 new _reader_bits::MapStorage<RedNode, Map, Converter>(map, converter); 2371 _red_node_maps.push_back(std::make_pair(caption, red_storage)); 2372 _reader_bits::MapStorageBase<BlueNode>* blue_storage = 2373 new _reader_bits::MapStorage<BlueNode, Map, Converter>(map, converter); 2374 _blue_node_maps.push_back(std::make_pair(caption, blue_storage)); 2375 return *this; 2376 } 2377 2378 /// Add a red node map reading rule to the reader. 2379 template <typename Map> 2380 BpGraphReader& redNodeMap(const std::string& caption, Map& map) { 2381 checkConcept<concepts::WriteMap<RedNode, typename Map::Value>, Map>(); 2382 _reader_bits::MapStorageBase<RedNode>* storage = 2383 new _reader_bits::MapStorage<RedNode, Map>(map); 2384 _red_node_maps.push_back(std::make_pair(caption, storage)); 2385 return *this; 2386 } 2387 2388 /// \brief Red node map reading rule 2389 /// 2390 /// Add a red node map node reading rule with specialized converter to 2391 /// the reader. 2392 template <typename Map, typename Converter> 2393 BpGraphReader& redNodeMap(const std::string& caption, Map& map, 2394 const Converter& converter = Converter()) { 2395 checkConcept<concepts::WriteMap<RedNode, typename Map::Value>, Map>(); 2396 _reader_bits::MapStorageBase<RedNode>* storage = 2397 new _reader_bits::MapStorage<RedNode, Map, Converter>(map, converter); 2398 _red_node_maps.push_back(std::make_pair(caption, storage)); 2399 return *this; 2400 } 2401 2402 /// Add a blue node map reading rule to the reader. 2403 template <typename Map> 2404 BpGraphReader& blueNodeMap(const std::string& caption, Map& map) { 2405 checkConcept<concepts::WriteMap<BlueNode, typename Map::Value>, Map>(); 2406 _reader_bits::MapStorageBase<BlueNode>* storage = 2407 new _reader_bits::MapStorage<BlueNode, Map>(map); 2408 _blue_node_maps.push_back(std::make_pair(caption, storage)); 2409 return *this; 2410 } 2411 2412 /// \brief Blue node map reading rule 2413 /// 2414 /// Add a blue node map reading rule with specialized converter to 2415 /// the reader. 2416 template <typename Map, typename Converter> 2417 BpGraphReader& blueNodeMap(const std::string& caption, Map& map, 2418 const Converter& converter = Converter()) { 2419 checkConcept<concepts::WriteMap<BlueNode, typename Map::Value>, Map>(); 2420 _reader_bits::MapStorageBase<BlueNode>* storage = 2421 new _reader_bits::MapStorage<BlueNode, Map, Converter>(map, converter); 2422 _blue_node_maps.push_back(std::make_pair(caption, storage)); 2423 return *this; 2424 } 2425 2426 /// \brief Edge map reading rule 2427 /// 2428 /// Add an edge map reading rule to the reader. 2429 template <typename Map> 2430 BpGraphReader& edgeMap(const std::string& caption, Map& map) { 2431 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>(); 2432 _reader_bits::MapStorageBase<Edge>* storage = 2433 new _reader_bits::MapStorage<Edge, Map>(map); 2434 _edge_maps.push_back(std::make_pair(caption, storage)); 2435 return *this; 2436 } 2437 2438 /// \brief Edge map reading rule 2439 /// 2440 /// Add an edge map reading rule with specialized converter to the 2441 /// reader. 2442 template <typename Map, typename Converter> 2443 BpGraphReader& edgeMap(const std::string& caption, Map& map, 2444 const Converter& converter = Converter()) { 2445 checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>(); 2446 _reader_bits::MapStorageBase<Edge>* storage = 2447 new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter); 2448 _edge_maps.push_back(std::make_pair(caption, storage)); 2449 return *this; 2450 } 2451 2452 /// \brief Arc map reading rule 2453 /// 2454 /// Add an arc map reading rule to the reader. 2455 template <typename Map> 2456 BpGraphReader& arcMap(const std::string& caption, Map& map) { 2457 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>(); 2458 _reader_bits::MapStorageBase<Edge>* forward_storage = 2459 new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map); 2460 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 2461 _reader_bits::MapStorageBase<Edge>* backward_storage = 2462 new _reader_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map); 2463 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); 2464 return *this; 2465 } 2466 2467 /// \brief Arc map reading rule 2468 /// 2469 /// Add an arc map reading rule with specialized converter to the 2470 /// reader. 2471 template <typename Map, typename Converter> 2472 BpGraphReader& arcMap(const std::string& caption, Map& map, 2473 const Converter& converter = Converter()) { 2474 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>(); 2475 _reader_bits::MapStorageBase<Edge>* forward_storage = 2476 new _reader_bits::GraphArcMapStorage<BGR, true, Map, Converter> 2477 (_graph, map, converter); 2478 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 2479 _reader_bits::MapStorageBase<Edge>* backward_storage = 2480 new _reader_bits::GraphArcMapStorage<BGR, false, Map, Converter> 2481 (_graph, map, converter); 2482 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); 2483 return *this; 2484 } 2485 2486 /// \brief Attribute reading rule 2487 /// 2488 /// Add an attribute reading rule to the reader. 2489 template <typename Value> 2490 BpGraphReader& attribute(const std::string& caption, Value& value) { 2491 _reader_bits::ValueStorageBase* storage = 2492 new _reader_bits::ValueStorage<Value>(value); 2493 _attributes.insert(std::make_pair(caption, storage)); 2494 return *this; 2495 } 2496 2497 /// \brief Attribute reading rule 2498 /// 2499 /// Add an attribute reading rule with specialized converter to the 2500 /// reader. 2501 template <typename Value, typename Converter> 2502 BpGraphReader& attribute(const std::string& caption, Value& value, 2503 const Converter& converter = Converter()) { 2504 _reader_bits::ValueStorageBase* storage = 2505 new _reader_bits::ValueStorage<Value, Converter>(value, converter); 2506 _attributes.insert(std::make_pair(caption, storage)); 2507 return *this; 2508 } 2509 2510 /// \brief Node reading rule 2511 /// 2512 /// Add a node reading rule to reader. 2513 BpGraphReader& node(const std::string& caption, Node& node) { 2514 typedef _reader_bits::DoubleMapLookUpConverter< 2515 Node, RedNodeIndex, BlueNodeIndex> Converter; 2516 Converter converter(_red_node_index, _blue_node_index); 2517 _reader_bits::ValueStorageBase* storage = 2518 new _reader_bits::ValueStorage<Node, Converter>(node, converter); 2519 _attributes.insert(std::make_pair(caption, storage)); 2520 return *this; 2521 } 2522 2523 /// \brief Red node reading rule 2524 /// 2525 /// Add a red node reading rule to reader. 2526 BpGraphReader& redNode(const std::string& caption, RedNode& node) { 2527 typedef _reader_bits::MapLookUpConverter<RedNode> Converter; 2528 Converter converter(_red_node_index); 2529 _reader_bits::ValueStorageBase* storage = 2530 new _reader_bits::ValueStorage<RedNode, Converter>(node, converter); 2531 _attributes.insert(std::make_pair(caption, storage)); 2532 return *this; 2533 } 2534 2535 /// \brief Blue node reading rule 2536 /// 2537 /// Add a blue node reading rule to reader. 2538 BpGraphReader& blueNode(const std::string& caption, BlueNode& node) { 2539 typedef _reader_bits::MapLookUpConverter<BlueNode> Converter; 2540 Converter converter(_blue_node_index); 2541 _reader_bits::ValueStorageBase* storage = 2542 new _reader_bits::ValueStorage<BlueNode, Converter>(node, converter); 2543 _attributes.insert(std::make_pair(caption, storage)); 2544 return *this; 2545 } 2546 2547 /// \brief Edge reading rule 2548 /// 2549 /// Add an edge reading rule to reader. 2550 BpGraphReader& edge(const std::string& caption, Edge& edge) { 2551 typedef _reader_bits::MapLookUpConverter<Edge> Converter; 2552 Converter converter(_edge_index); 2553 _reader_bits::ValueStorageBase* storage = 2554 new _reader_bits::ValueStorage<Edge, Converter>(edge, converter); 2555 _attributes.insert(std::make_pair(caption, storage)); 2556 return *this; 2557 } 2558 2559 /// \brief Arc reading rule 2560 /// 2561 /// Add an arc reading rule to reader. 2562 BpGraphReader& arc(const std::string& caption, Arc& arc) { 2563 typedef _reader_bits::GraphArcLookUpConverter<BGR> Converter; 2564 Converter converter(_graph, _edge_index); 2565 _reader_bits::ValueStorageBase* storage = 2566 new _reader_bits::ValueStorage<Arc, Converter>(arc, converter); 2567 _attributes.insert(std::make_pair(caption, storage)); 2568 return *this; 2569 } 2570 2571 /// @} 2572 2573 /// \name Select Section by Name 2574 /// @{ 2575 2576 /// \brief Set \c \@nodes section to be read 2577 /// 2578 /// Set \c \@nodes section to be read. 2579 BpGraphReader& nodes(const std::string& caption) { 2580 _nodes_caption = caption; 2581 return *this; 2582 } 2583 2584 /// \brief Set \c \@edges section to be read 2585 /// 2586 /// Set \c \@edges section to be read. 2587 BpGraphReader& edges(const std::string& caption) { 2588 _edges_caption = caption; 2589 return *this; 2590 } 2591 2592 /// \brief Set \c \@attributes section to be read 2593 /// 2594 /// Set \c \@attributes section to be read. 2595 BpGraphReader& attributes(const std::string& caption) { 2596 _attributes_caption = caption; 2597 return *this; 2598 } 2599 2600 /// @} 2601 2602 /// \name Using Previously Constructed Node or Edge Set 2603 /// @{ 2604 2605 /// \brief Use previously constructed node set 2606 /// 2607 /// Use previously constructed node set, and specify the node 2608 /// label map. 2609 template <typename Map> 2610 BpGraphReader& useNodes(const Map& map) { 2611 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>(); 2612 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 2613 _use_nodes = true; 2614 _writer_bits::DefaultConverter<typename Map::Value> converter; 2615 for (RedNodeIt n(_graph); n != INVALID; ++n) { 2616 _red_node_index.insert(std::make_pair(converter(map[n]), n)); 2617 } 2618 for (BlueNodeIt n(_graph); n != INVALID; ++n) { 2619 _blue_node_index.insert(std::make_pair(converter(map[n]), n)); 2620 } 2621 return *this; 2622 } 2623 2624 /// \brief Use previously constructed node set 2625 /// 2626 /// Use previously constructed node set, and specify the node 2627 /// label map and a functor which converts the label map values to 2628 /// \c std::string. 2629 template <typename Map, typename Converter> 2630 BpGraphReader& useNodes(const Map& map, 2631 const Converter& converter = Converter()) { 2632 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>(); 2633 LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 2634 _use_nodes = true; 2635 for (RedNodeIt n(_graph); n != INVALID; ++n) { 2636 _red_node_index.insert(std::make_pair(converter(map[n]), n)); 2637 } 2638 for (BlueNodeIt n(_graph); n != INVALID; ++n) { 2639 _blue_node_index.insert(std::make_pair(converter(map[n]), n)); 2640 } 2641 return *this; 2642 } 2643 2644 /// \brief Use previously constructed edge set 2645 /// 2646 /// Use previously constructed edge set, and specify the edge 2647 /// label map. 2648 template <typename Map> 2649 BpGraphReader& useEdges(const Map& map) { 2650 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>(); 2651 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member"); 2652 _use_edges = true; 2653 _writer_bits::DefaultConverter<typename Map::Value> converter; 2654 for (EdgeIt a(_graph); a != INVALID; ++a) { 2655 _edge_index.insert(std::make_pair(converter(map[a]), a)); 2656 } 2657 return *this; 2658 } 2659 2660 /// \brief Use previously constructed edge set 2661 /// 2662 /// Use previously constructed edge set, and specify the edge 2663 /// label map and a functor which converts the label map values to 2664 /// \c std::string. 2665 template <typename Map, typename Converter> 2666 BpGraphReader& useEdges(const Map& map, 2667 const Converter& converter = Converter()) { 2668 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>(); 2669 LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member"); 2670 _use_edges = true; 2671 for (EdgeIt a(_graph); a != INVALID; ++a) { 2672 _edge_index.insert(std::make_pair(converter(map[a]), a)); 2673 } 2674 return *this; 2675 } 2676 2677 /// \brief Skip the reading of node section 2678 /// 2679 /// Omit the reading of the node section. This implies that each node 2680 /// map reading rule will be abandoned, and the nodes of the graph 2681 /// will not be constructed, which usually cause that the edge set 2682 /// could not be read due to lack of node name 2683 /// could not be read due to lack of node name resolving. 2684 /// Therefore \c skipEdges() function should also be used, or 2685 /// \c useNodes() should be used to specify the label of the nodes. 2686 BpGraphReader& skipNodes() { 2687 LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 2688 _skip_nodes = true; 2689 return *this; 2690 } 2691 2692 /// \brief Skip the reading of edge section 2693 /// 2694 /// Omit the reading of the edge section. This implies that each edge 2695 /// map reading rule will be abandoned, and the edges of the graph 2696 /// will not be constructed. 2697 BpGraphReader& skipEdges() { 2698 LEMON_ASSERT(!_skip_edges, "Skip edges already set"); 2699 _skip_edges = true; 2700 return *this; 2701 } 2702 2703 /// @} 2704 2705 private: 2706 2707 bool readLine() { 2708 std::string str; 2709 while(++line_num, std::getline(*_is, str)) { 2710 line.clear(); line.str(str); 2711 char c; 2712 if (line >> std::ws >> c && c != '#') { 2713 line.putback(c); 2714 return true; 2715 } 2716 } 2717 return false; 2718 } 2719 2720 bool readSuccess() { 2721 return static_cast<bool>(*_is); 2722 } 2723 2724 void skipSection() { 2725 char c; 2726 while (readSuccess() && line >> c && c != '@') { 2727 readLine(); 2728 } 2729 if (readSuccess()) { 2730 line.putback(c); 2731 } 2732 } 2733 2734 void readRedNodes() { 2735 2736 std::vector<int> map_index(_red_node_maps.size()); 2737 int map_num, label_index; 2738 2739 char c; 2740 if (!readLine() || !(line >> c) || c == '@') { 2741 if (readSuccess() && line) line.putback(c); 2742 if (!_red_node_maps.empty()) 2743 throw FormatError("Cannot find map names"); 2744 return; 2745 } 2746 line.putback(c); 2747 2748 { 2749 std::map<std::string, int> maps; 2750 2751 std::string map; 2752 int index = 0; 2753 while (_reader_bits::readToken(line, map)) { 2754 if (maps.find(map) != maps.end()) { 2755 std::ostringstream msg; 2756 msg << "Multiple occurence of red node map: " << map; 2757 throw FormatError(msg.str()); 2758 } 2759 maps.insert(std::make_pair(map, index)); 2760 ++index; 2761 } 2762 2763 for (int i = 0; i < static_cast<int>(_red_node_maps.size()); ++i) { 2764 std::map<std::string, int>::iterator jt = 2765 maps.find(_red_node_maps[i].first); 2766 if (jt == maps.end()) { 2767 std::ostringstream msg; 2768 msg << "Map not found: " << _red_node_maps[i].first; 2769 throw FormatError(msg.str()); 2770 } 2771 map_index[i] = jt->second; 2772 } 2773 2774 { 2775 std::map<std::string, int>::iterator jt = maps.find("label"); 2776 if (jt != maps.end()) { 2777 label_index = jt->second; 2778 } else { 2779 label_index = -1; 2780 } 2781 } 2782 map_num = maps.size(); 2783 } 2784 2785 while (readLine() && line >> c && c != '@') { 2786 line.putback(c); 2787 2788 std::vector<std::string> tokens(map_num); 2789 for (int i = 0; i < map_num; ++i) { 2790 if (!_reader_bits::readToken(line, tokens[i])) { 2791 std::ostringstream msg; 2792 msg << "Column not found (" << i + 1 << ")"; 2793 throw FormatError(msg.str()); 2794 } 2795 } 2796 if (line >> std::ws >> c) 2797 throw FormatError("Extra character at the end of line"); 2798 2799 RedNode n; 2800 if (!_use_nodes) { 2801 n = _graph.addRedNode(); 2802 if (label_index != -1) 2803 _red_node_index.insert(std::make_pair(tokens[label_index], n)); 2804 } else { 2805 if (label_index == -1) 2806 throw FormatError("Label map not found"); 2807 typename std::map<std::string, RedNode>::iterator it = 2808 _red_node_index.find(tokens[label_index]); 2809 if (it == _red_node_index.end()) { 2810 std::ostringstream msg; 2811 msg << "Node with label not found: " << tokens[label_index]; 2812 throw FormatError(msg.str()); 2813 } 2814 n = it->second; 2815 } 2816 2817 for (int i = 0; i < static_cast<int>(_red_node_maps.size()); ++i) { 2818 _red_node_maps[i].second->set(n, tokens[map_index[i]]); 2819 } 2820 2821 } 2822 if (readSuccess()) { 2823 line.putback(c); 2824 } 2825 } 2826 2827 void readBlueNodes() { 2828 2829 std::vector<int> map_index(_blue_node_maps.size()); 2830 int map_num, label_index; 2831 2832 char c; 2833 if (!readLine() || !(line >> c) || c == '@') { 2834 if (readSuccess() && line) line.putback(c); 2835 if (!_blue_node_maps.empty()) 2836 throw FormatError("Cannot find map names"); 2837 return; 2838 } 2839 line.putback(c); 2840 2841 { 2842 std::map<std::string, int> maps; 2843 2844 std::string map; 2845 int index = 0; 2846 while (_reader_bits::readToken(line, map)) { 2847 if (maps.find(map) != maps.end()) { 2848 std::ostringstream msg; 2849 msg << "Multiple occurence of blue node map: " << map; 2850 throw FormatError(msg.str()); 2851 } 2852 maps.insert(std::make_pair(map, index)); 2853 ++index; 2854 } 2855 2856 for (int i = 0; i < static_cast<int>(_blue_node_maps.size()); ++i) { 2857 std::map<std::string, int>::iterator jt = 2858 maps.find(_blue_node_maps[i].first); 2859 if (jt == maps.end()) { 2860 std::ostringstream msg; 2861 msg << "Map not found: " << _blue_node_maps[i].first; 2862 throw FormatError(msg.str()); 2863 } 2864 map_index[i] = jt->second; 2865 } 2866 2867 { 2868 std::map<std::string, int>::iterator jt = maps.find("label"); 2869 if (jt != maps.end()) { 2870 label_index = jt->second; 2871 } else { 2872 label_index = -1; 2873 } 2874 } 2875 map_num = maps.size(); 2876 } 2877 2878 while (readLine() && line >> c && c != '@') { 2879 line.putback(c); 2880 2881 std::vector<std::string> tokens(map_num); 2882 for (int i = 0; i < map_num; ++i) { 2883 if (!_reader_bits::readToken(line, tokens[i])) { 2884 std::ostringstream msg; 2885 msg << "Column not found (" << i + 1 << ")"; 2886 throw FormatError(msg.str()); 2887 } 2888 } 2889 if (line >> std::ws >> c) 2890 throw FormatError("Extra character at the end of line"); 2891 2892 BlueNode n; 2893 if (!_use_nodes) { 2894 n = _graph.addBlueNode(); 2895 if (label_index != -1) 2896 _blue_node_index.insert(std::make_pair(tokens[label_index], n)); 2897 } else { 2898 if (label_index == -1) 2899 throw FormatError("Label map not found"); 2900 typename std::map<std::string, BlueNode>::iterator it = 2901 _blue_node_index.find(tokens[label_index]); 2902 if (it == _blue_node_index.end()) { 2903 std::ostringstream msg; 2904 msg << "Node with label not found: " << tokens[label_index]; 2905 throw FormatError(msg.str()); 2906 } 2907 n = it->second; 2908 } 2909 2910 for (int i = 0; i < static_cast<int>(_blue_node_maps.size()); ++i) { 2911 _blue_node_maps[i].second->set(n, tokens[map_index[i]]); 2912 } 2913 2914 } 2915 if (readSuccess()) { 2916 line.putback(c); 2917 } 2918 } 2919 2920 void readEdges() { 2921 2922 std::vector<int> map_index(_edge_maps.size()); 2923 int map_num, label_index; 2924 2925 char c; 2926 if (!readLine() || !(line >> c) || c == '@') { 2927 if (readSuccess() && line) line.putback(c); 2928 if (!_edge_maps.empty()) 2929 throw FormatError("Cannot find map names"); 2930 return; 2931 } 2932 line.putback(c); 2933 2934 { 2935 std::map<std::string, int> maps; 2936 2937 std::string map; 2938 int index = 0; 2939 while (_reader_bits::readToken(line, map)) { 2940 if (maps.find(map) != maps.end()) { 2941 std::ostringstream msg; 2942 msg << "Multiple occurence of edge map: " << map; 2943 throw FormatError(msg.str()); 2944 } 2945 maps.insert(std::make_pair(map, index)); 2946 ++index; 2947 } 2948 2949 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) { 2950 std::map<std::string, int>::iterator jt = 2951 maps.find(_edge_maps[i].first); 2952 if (jt == maps.end()) { 2953 std::ostringstream msg; 2954 msg << "Map not found: " << _edge_maps[i].first; 2955 throw FormatError(msg.str()); 2956 } 2957 map_index[i] = jt->second; 2958 } 2959 2960 { 2961 std::map<std::string, int>::iterator jt = maps.find("label"); 2962 if (jt != maps.end()) { 2963 label_index = jt->second; 2964 } else { 2965 label_index = -1; 2966 } 2967 } 2968 map_num = maps.size(); 2969 } 2970 2971 while (readLine() && line >> c && c != '@') { 2972 line.putback(c); 2973 2974 std::string source_token; 2975 std::string target_token; 2976 2977 if (!_reader_bits::readToken(line, source_token)) 2978 throw FormatError("Red node not found"); 2979 2980 if (!_reader_bits::readToken(line, target_token)) 2981 throw FormatError("Blue node not found"); 2982 2983 std::vector<std::string> tokens(map_num); 2984 for (int i = 0; i < map_num; ++i) { 2985 if (!_reader_bits::readToken(line, tokens[i])) { 2986 std::ostringstream msg; 2987 msg << "Column not found (" << i + 1 << ")"; 2988 throw FormatError(msg.str()); 2989 } 2990 } 2991 if (line >> std::ws >> c) 2992 throw FormatError("Extra character at the end of line"); 2993 2994 Edge e; 2995 if (!_use_edges) { 2996 typename RedNodeIndex::iterator rit = 2997 _red_node_index.find(source_token); 2998 if (rit == _red_node_index.end()) { 2999 std::ostringstream msg; 3000 msg << "Item not found: " << source_token; 3001 throw FormatError(msg.str()); 3002 } 3003 RedNode source = rit->second; 3004 typename BlueNodeIndex::iterator it = 3005 _blue_node_index.find(target_token); 3006 if (it == _blue_node_index.end()) { 3007 std::ostringstream msg; 3008 msg << "Item not found: " << target_token; 3009 throw FormatError(msg.str()); 3010 } 3011 BlueNode target = it->second; 3012 3013 // It is checked that source is red and 3014 // target is blue, so this should be safe: 3015 e = _graph.addEdge(source, target); 3016 if (label_index != -1) 3017 _edge_index.insert(std::make_pair(tokens[label_index], e)); 3018 } else { 3019 if (label_index == -1) 3020 throw FormatError("Label map not found"); 3021 typename std::map<std::string, Edge>::iterator it = 3022 _edge_index.find(tokens[label_index]); 3023 if (it == _edge_index.end()) { 3024 std::ostringstream msg; 3025 msg << "Edge with label not found: " << tokens[label_index]; 3026 throw FormatError(msg.str()); 3027 } 3028 e = it->second; 3029 } 3030 3031 for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) { 3032 _edge_maps[i].second->set(e, tokens[map_index[i]]); 3033 } 3034 3035 } 3036 if (readSuccess()) { 3037 line.putback(c); 3038 } 3039 } 3040 3041 void readAttributes() { 3042 3043 std::set<std::string> read_attr; 3044 3045 char c; 3046 while (readLine() && line >> c && c != '@') { 3047 line.putback(c); 3048 3049 std::string attr, token; 3050 if (!_reader_bits::readToken(line, attr)) 3051 throw FormatError("Attribute name not found"); 3052 if (!_reader_bits::readToken(line, token)) 3053 throw FormatError("Attribute value not found"); 3054 if (line >> c) 3055 throw FormatError("Extra character at the end of line"); 3056 3057 { 3058 std::set<std::string>::iterator it = read_attr.find(attr); 3059 if (it != read_attr.end()) { 3060 std::ostringstream msg; 3061 msg << "Multiple occurence of attribute: " << attr; 3062 throw FormatError(msg.str()); 3063 } 3064 read_attr.insert(attr); 3065 } 3066 3067 { 3068 typename Attributes::iterator it = _attributes.lower_bound(attr); 3069 while (it != _attributes.end() && it->first == attr) { 3070 it->second->set(token); 3071 ++it; 3072 } 3073 } 3074 3075 } 3076 if (readSuccess()) { 3077 line.putback(c); 3078 } 3079 for (typename Attributes::iterator it = _attributes.begin(); 3080 it != _attributes.end(); ++it) { 3081 if (read_attr.find(it->first) == read_attr.end()) { 3082 std::ostringstream msg; 3083 msg << "Attribute not found: " << it->first; 3084 throw FormatError(msg.str()); 3085 } 3086 } 3087 } 3088 3089 public: 3090 3091 /// \name Execution of the Reader 3092 /// @{ 3093 3094 /// \brief Start the batch processing 3095 /// 3096 /// This function starts the batch processing 3097 void run() { 3098 3099 LEMON_ASSERT(_is != 0, "This reader assigned to an other reader"); 3100 3101 bool red_nodes_done = _skip_nodes; 3102 bool blue_nodes_done = _skip_nodes; 3103 bool edges_done = _skip_edges; 3104 bool attributes_done = false; 3105 3106 line_num = 0; 3107 readLine(); 3108 skipSection(); 3109 3110 while (readSuccess()) { 3111 try { 3112 char c; 3113 std::string section, caption; 3114 line >> c; 3115 _reader_bits::readToken(line, section); 3116 _reader_bits::readToken(line, caption); 3117 3118 if (line >> c) 3119 throw FormatError("Extra character at the end of line"); 3120 3121 if (section == "red_nodes" && !red_nodes_done) { 3122 if (_nodes_caption.empty() || _nodes_caption == caption) { 3123 readRedNodes(); 3124 red_nodes_done = true; 3125 } 3126 } else if (section == "blue_nodes" && !blue_nodes_done) { 3127 if (_nodes_caption.empty() || _nodes_caption == caption) { 3128 readBlueNodes(); 3129 blue_nodes_done = true; 3130 } 3131 } else if ((section == "edges" || section == "arcs") && 3132 !edges_done) { 3133 if (_edges_caption.empty() || _edges_caption == caption) { 3134 readEdges(); 3135 edges_done = true; 3136 } 3137 } else if (section == "attributes" && !attributes_done) { 3138 if (_attributes_caption.empty() || _attributes_caption == caption) { 3139 readAttributes(); 3140 attributes_done = true; 3141 } 3142 } else { 3143 readLine(); 3144 skipSection(); 3145 } 3146 } catch (FormatError& error) { 3147 error.line(line_num); 3148 error.file(_filename); 3149 throw; 3150 } 3151 } 3152 3153 if (!red_nodes_done) { 3154 throw FormatError("Section @red_nodes not found"); 3155 } 3156 3157 if (!blue_nodes_done) { 3158 throw FormatError("Section @blue_nodes not found"); 3159 } 3160 3161 if (!edges_done) { 3162 throw FormatError("Section @edges not found"); 3163 } 3164 3165 if (!attributes_done && !_attributes.empty()) { 3166 throw FormatError("Section @attributes not found"); 3167 } 3168 3169 } 3170 3171 /// @} 3172 3173 }; 3174 3175 /// \ingroup lemon_io 3176 /// 3177 /// \brief Return a \ref BpGraphReader class 3178 /// 3179 /// This function just returns a \ref BpGraphReader class. 3180 /// 3181 /// With this function a graph can be read from an 3182 /// \ref lgf-format "LGF" file or input stream with several maps and 3183 /// attributes. For example, there is bipartite weighted matching problem 3184 /// on a graph, i.e. a graph with a \e weight map on the edges. This 3185 /// graph can be read with the following code: 3186 /// 3187 ///\code 3188 ///ListBpGraph graph; 3189 ///ListBpGraph::EdgeMap<int> weight(graph); 3190 ///bpGraphReader(graph, std::cin). 3191 /// edgeMap("weight", weight). 3192 /// run(); 3193 ///\endcode 3194 /// 3195 /// For a complete documentation, please see the \ref BpGraphReader 3196 /// class documentation. 3197 /// \warning Don't forget to put the \ref BpGraphReader::run() "run()" 3198 /// to the end of the parameter list. 3199 /// \relates BpGraphReader 3200 /// \sa bpGraphReader(TBGR& graph, const std::string& fn) 3201 /// \sa bpGraphReader(TBGR& graph, const char* fn) 3202 template <typename TBGR> 3203 BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is) { 3204 BpGraphReader<TBGR> tmp(graph, is); 3205 return tmp; 3206 } 3207 3208 /// \brief Return a \ref BpGraphReader class 3209 /// 3210 /// This function just returns a \ref BpGraphReader class. 3211 /// \relates BpGraphReader 3212 /// \sa bpGraphReader(TBGR& graph, std::istream& is) 3213 template <typename TBGR> 3214 BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn) { 3215 BpGraphReader<TBGR> tmp(graph, fn); 3216 return tmp; 3217 } 3218 3219 /// \brief Return a \ref BpGraphReader class 3220 /// 3221 /// This function just returns a \ref BpGraphReader class. 3222 /// \relates BpGraphReader 3223 /// \sa bpGraphReader(TBGR& graph, std::istream& is) 3224 template <typename TBGR> 3225 BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char* fn) { 3226 BpGraphReader<TBGR> tmp(graph, fn); 3227 return tmp; 3228 } 3229 2131 3230 class SectionReader; 2132 3231 -
lemon/lgf_writer.h
r877 r1030 186 186 ValueStorage(const Value& value, const Converter& converter = Converter()) 187 187 : _value(value), _converter(converter) {} 188 188 189 189 virtual std::string get() { 190 190 return _converter(_value); … … 192 192 }; 193 193 194 template <typename Value> 194 template <typename Value, 195 typename Map = std::map<Value, std::string> > 195 196 struct MapLookUpConverter { 196 const std::map<Value, std::string>& _map;197 198 MapLookUpConverter(const std::map<Value, std::string>& map)197 const Map& _map; 198 199 MapLookUpConverter(const Map& map) 199 200 : _map(map) {} 200 201 201 std::string operator()(const Value& str) { 202 typename std::map<Value, std::string>::const_iterator it = 203 _map.find(str); 202 std::string operator()(const Value& value) { 203 typename Map::const_iterator it = _map.find(value); 204 204 if (it == _map.end()) { 205 205 throw FormatError("Item not found"); 206 206 } 207 207 return it->second; 208 } 209 }; 210 211 template <typename Value, 212 typename Map1 = std::map<Value, std::string>, 213 typename Map2 = std::map<Value, std::string> > 214 struct DoubleMapLookUpConverter { 215 const Map1& _map1; 216 const Map2& _map2; 217 218 DoubleMapLookUpConverter(const Map1& map1, const Map2& map2) 219 : _map1(map1), _map2(map2) {} 220 221 std::string operator()(const Value& value) { 222 typename Map1::const_iterator it1 = _map1.find(value); 223 typename Map1::const_iterator it2 = _map2.find(value); 224 if (it1 == _map1.end()) { 225 if (it2 == _map2.end()) { 226 throw FormatError("Item not found"); 227 } else { 228 return it2->second; 229 } 230 } else { 231 if (it2 == _map2.end()) { 232 return it1->second; 233 } else { 234 throw FormatError("Item is ambigous"); 235 } 236 } 208 237 } 209 238 }; … … 987 1016 /// \ingroup lemon_io 988 1017 /// 989 /// \brief \ref lgf-format "LGF" writer for directed graphs1018 /// \brief \ref lgf-format "LGF" writer for undirected graphs 990 1019 /// 991 1020 /// This utility writes an \ref lgf-format "LGF" file. … … 1043 1072 /// \brief Constructor 1044 1073 /// 1045 /// Construct a directed graph writer, which writes to the given1046 /// output stream.1074 /// Construct an undirected graph writer, which writes to the 1075 /// given output stream. 1047 1076 GraphWriter(const GR& graph, std::ostream& os = std::cout) 1048 1077 : _os(&os), local_os(false), _graph(graph), … … 1051 1080 /// \brief Constructor 1052 1081 /// 1053 /// Construct a directed graph writer, which writes to the given1082 /// Construct a undirected graph writer, which writes to the given 1054 1083 /// output file. 1055 1084 GraphWriter(const GR& graph, const std::string& fn) … … 1064 1093 /// \brief Constructor 1065 1094 /// 1066 /// Construct a directed graph writer, which writes to the given1095 /// Construct a undirected graph writer, which writes to the given 1067 1096 /// output file. 1068 1097 GraphWriter(const GR& graph, const char* fn) … … 1290 1319 } 1291 1320 1292 /// \brief Add an additional caption to the \c \@ arcs section1293 /// 1294 /// Add an additional caption to the \c \@ arcs section.1321 /// \brief Add an additional caption to the \c \@edges section 1322 /// 1323 /// Add an additional caption to the \c \@edges section. 1295 1324 GraphWriter& edges(const std::string& caption) { 1296 1325 _edges_caption = caption; … … 1606 1635 GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn) { 1607 1636 GraphWriter<TGR> tmp(graph, fn); 1637 return tmp; 1638 } 1639 1640 template <typename BGR> 1641 class BpGraphWriter; 1642 1643 template <typename TBGR> 1644 BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, 1645 std::ostream& os = std::cout); 1646 template <typename TBGR> 1647 BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const std::string& fn); 1648 template <typename TBGR> 1649 BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char* fn); 1650 1651 /// \ingroup lemon_io 1652 /// 1653 /// \brief \ref lgf-format "LGF" writer for undirected bipartite graphs 1654 /// 1655 /// This utility writes an \ref lgf-format "LGF" file. 1656 /// 1657 /// It can be used almost the same way as \c GraphWriter, but it 1658 /// reads the red and blue nodes from separate sections, and these 1659 /// sections can contain different set of maps. 1660 /// 1661 /// The red and blue node maps are written to the corresponding 1662 /// sections. The node maps are written to both of these sections 1663 /// with the same map name. 1664 template <typename BGR> 1665 class BpGraphWriter { 1666 public: 1667 1668 typedef BGR BpGraph; 1669 TEMPLATE_BPGRAPH_TYPEDEFS(BGR); 1670 1671 private: 1672 1673 1674 std::ostream* _os; 1675 bool local_os; 1676 1677 const BGR& _graph; 1678 1679 std::string _nodes_caption; 1680 std::string _edges_caption; 1681 std::string _attributes_caption; 1682 1683 typedef std::map<Node, std::string> RedNodeIndex; 1684 RedNodeIndex _red_node_index; 1685 typedef std::map<Node, std::string> BlueNodeIndex; 1686 BlueNodeIndex _blue_node_index; 1687 typedef std::map<Edge, std::string> EdgeIndex; 1688 EdgeIndex _edge_index; 1689 1690 typedef std::vector<std::pair<std::string, 1691 _writer_bits::MapStorageBase<RedNode>* > > RedNodeMaps; 1692 RedNodeMaps _red_node_maps; 1693 typedef std::vector<std::pair<std::string, 1694 _writer_bits::MapStorageBase<BlueNode>* > > BlueNodeMaps; 1695 BlueNodeMaps _blue_node_maps; 1696 1697 typedef std::vector<std::pair<std::string, 1698 _writer_bits::MapStorageBase<Edge>* > >EdgeMaps; 1699 EdgeMaps _edge_maps; 1700 1701 typedef std::vector<std::pair<std::string, 1702 _writer_bits::ValueStorageBase*> > Attributes; 1703 Attributes _attributes; 1704 1705 bool _skip_nodes; 1706 bool _skip_edges; 1707 1708 public: 1709 1710 /// \brief Constructor 1711 /// 1712 /// Construct a bipartite graph writer, which writes to the given 1713 /// output stream. 1714 BpGraphWriter(const BGR& graph, std::ostream& os = std::cout) 1715 : _os(&os), local_os(false), _graph(graph), 1716 _skip_nodes(false), _skip_edges(false) {} 1717 1718 /// \brief Constructor 1719 /// 1720 /// Construct a bipartite graph writer, which writes to the given 1721 /// output file. 1722 BpGraphWriter(const BGR& graph, const std::string& fn) 1723 : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph), 1724 _skip_nodes(false), _skip_edges(false) { 1725 if (!(*_os)) { 1726 delete _os; 1727 throw IoError("Cannot write file", fn); 1728 } 1729 } 1730 1731 /// \brief Constructor 1732 /// 1733 /// Construct a bipartite graph writer, which writes to the given 1734 /// output file. 1735 BpGraphWriter(const BGR& graph, const char* fn) 1736 : _os(new std::ofstream(fn)), local_os(true), _graph(graph), 1737 _skip_nodes(false), _skip_edges(false) { 1738 if (!(*_os)) { 1739 delete _os; 1740 throw IoError("Cannot write file", fn); 1741 } 1742 } 1743 1744 /// \brief Destructor 1745 ~BpGraphWriter() { 1746 for (typename RedNodeMaps::iterator it = _red_node_maps.begin(); 1747 it != _red_node_maps.end(); ++it) { 1748 delete it->second; 1749 } 1750 1751 for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin(); 1752 it != _blue_node_maps.end(); ++it) { 1753 delete it->second; 1754 } 1755 1756 for (typename EdgeMaps::iterator it = _edge_maps.begin(); 1757 it != _edge_maps.end(); ++it) { 1758 delete it->second; 1759 } 1760 1761 for (typename Attributes::iterator it = _attributes.begin(); 1762 it != _attributes.end(); ++it) { 1763 delete it->second; 1764 } 1765 1766 if (local_os) { 1767 delete _os; 1768 } 1769 } 1770 1771 private: 1772 1773 template <typename TBGR> 1774 friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, 1775 std::ostream& os); 1776 template <typename TBGR> 1777 friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, 1778 const std::string& fn); 1779 template <typename TBGR> 1780 friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char *fn); 1781 1782 BpGraphWriter(BpGraphWriter& other) 1783 : _os(other._os), local_os(other.local_os), _graph(other._graph), 1784 _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) { 1785 1786 other._os = 0; 1787 other.local_os = false; 1788 1789 _red_node_index.swap(other._red_node_index); 1790 _blue_node_index.swap(other._blue_node_index); 1791 _edge_index.swap(other._edge_index); 1792 1793 _red_node_maps.swap(other._red_node_maps); 1794 _blue_node_maps.swap(other._blue_node_maps); 1795 _edge_maps.swap(other._edge_maps); 1796 _attributes.swap(other._attributes); 1797 1798 _nodes_caption = other._nodes_caption; 1799 _edges_caption = other._edges_caption; 1800 _attributes_caption = other._attributes_caption; 1801 } 1802 1803 BpGraphWriter& operator=(const BpGraphWriter&); 1804 1805 public: 1806 1807 /// \name Writing Rules 1808 /// @{ 1809 1810 /// \brief Node map writing rule 1811 /// 1812 /// Add a node map writing rule to the writer. 1813 template <typename Map> 1814 BpGraphWriter& nodeMap(const std::string& caption, const Map& map) { 1815 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>(); 1816 _writer_bits::MapStorageBase<RedNode>* red_storage = 1817 new _writer_bits::MapStorage<RedNode, Map>(map); 1818 _red_node_maps.push_back(std::make_pair(caption, red_storage)); 1819 _writer_bits::MapStorageBase<BlueNode>* blue_storage = 1820 new _writer_bits::MapStorage<BlueNode, Map>(map); 1821 _blue_node_maps.push_back(std::make_pair(caption, blue_storage)); 1822 return *this; 1823 } 1824 1825 /// \brief Node map writing rule 1826 /// 1827 /// Add a node map writing rule with specialized converter to the 1828 /// writer. 1829 template <typename Map, typename Converter> 1830 BpGraphWriter& nodeMap(const std::string& caption, const Map& map, 1831 const Converter& converter = Converter()) { 1832 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>(); 1833 _writer_bits::MapStorageBase<RedNode>* red_storage = 1834 new _writer_bits::MapStorage<RedNode, Map, Converter>(map, converter); 1835 _red_node_maps.push_back(std::make_pair(caption, red_storage)); 1836 _writer_bits::MapStorageBase<BlueNode>* blue_storage = 1837 new _writer_bits::MapStorage<BlueNode, Map, Converter>(map, converter); 1838 _blue_node_maps.push_back(std::make_pair(caption, blue_storage)); 1839 return *this; 1840 } 1841 1842 /// \brief Red node map writing rule 1843 /// 1844 /// Add a red node map writing rule to the writer. 1845 template <typename Map> 1846 BpGraphWriter& redNodeMap(const std::string& caption, const Map& map) { 1847 checkConcept<concepts::ReadMap<RedNode, typename Map::Value>, Map>(); 1848 _writer_bits::MapStorageBase<RedNode>* storage = 1849 new _writer_bits::MapStorage<RedNode, Map>(map); 1850 _red_node_maps.push_back(std::make_pair(caption, storage)); 1851 return *this; 1852 } 1853 1854 /// \brief Red node map writing rule 1855 /// 1856 /// Add a red node map writing rule with specialized converter to the 1857 /// writer. 1858 template <typename Map, typename Converter> 1859 BpGraphWriter& redNodeMap(const std::string& caption, const Map& map, 1860 const Converter& converter = Converter()) { 1861 checkConcept<concepts::ReadMap<RedNode, typename Map::Value>, Map>(); 1862 _writer_bits::MapStorageBase<RedNode>* storage = 1863 new _writer_bits::MapStorage<RedNode, Map, Converter>(map, converter); 1864 _red_node_maps.push_back(std::make_pair(caption, storage)); 1865 return *this; 1866 } 1867 1868 /// \brief Blue node map writing rule 1869 /// 1870 /// Add a blue node map writing rule to the writer. 1871 template <typename Map> 1872 BpGraphWriter& blueNodeMap(const std::string& caption, const Map& map) { 1873 checkConcept<concepts::ReadMap<BlueNode, typename Map::Value>, Map>(); 1874 _writer_bits::MapStorageBase<BlueNode>* storage = 1875 new _writer_bits::MapStorage<BlueNode, Map>(map); 1876 _blue_node_maps.push_back(std::make_pair(caption, storage)); 1877 return *this; 1878 } 1879 1880 /// \brief Blue node map writing rule 1881 /// 1882 /// Add a blue node map writing rule with specialized converter to the 1883 /// writer. 1884 template <typename Map, typename Converter> 1885 BpGraphWriter& blueNodeMap(const std::string& caption, const Map& map, 1886 const Converter& converter = Converter()) { 1887 checkConcept<concepts::ReadMap<BlueNode, typename Map::Value>, Map>(); 1888 _writer_bits::MapStorageBase<BlueNode>* storage = 1889 new _writer_bits::MapStorage<BlueNode, Map, Converter>(map, converter); 1890 _blue_node_maps.push_back(std::make_pair(caption, storage)); 1891 return *this; 1892 } 1893 1894 /// \brief Edge map writing rule 1895 /// 1896 /// Add an edge map writing rule to the writer. 1897 template <typename Map> 1898 BpGraphWriter& edgeMap(const std::string& caption, const Map& map) { 1899 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>(); 1900 _writer_bits::MapStorageBase<Edge>* storage = 1901 new _writer_bits::MapStorage<Edge, Map>(map); 1902 _edge_maps.push_back(std::make_pair(caption, storage)); 1903 return *this; 1904 } 1905 1906 /// \brief Edge map writing rule 1907 /// 1908 /// Add an edge map writing rule with specialized converter to the 1909 /// writer. 1910 template <typename Map, typename Converter> 1911 BpGraphWriter& edgeMap(const std::string& caption, const Map& map, 1912 const Converter& converter = Converter()) { 1913 checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>(); 1914 _writer_bits::MapStorageBase<Edge>* storage = 1915 new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter); 1916 _edge_maps.push_back(std::make_pair(caption, storage)); 1917 return *this; 1918 } 1919 1920 /// \brief Arc map writing rule 1921 /// 1922 /// Add an arc map writing rule to the writer. 1923 template <typename Map> 1924 BpGraphWriter& arcMap(const std::string& caption, const Map& map) { 1925 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>(); 1926 _writer_bits::MapStorageBase<Edge>* forward_storage = 1927 new _writer_bits::GraphArcMapStorage<BGR, true, Map>(_graph, map); 1928 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 1929 _writer_bits::MapStorageBase<Edge>* backward_storage = 1930 new _writer_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map); 1931 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); 1932 return *this; 1933 } 1934 1935 /// \brief Arc map writing rule 1936 /// 1937 /// Add an arc map writing rule with specialized converter to the 1938 /// writer. 1939 template <typename Map, typename Converter> 1940 BpGraphWriter& arcMap(const std::string& caption, const Map& map, 1941 const Converter& converter = Converter()) { 1942 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>(); 1943 _writer_bits::MapStorageBase<Edge>* forward_storage = 1944 new _writer_bits::GraphArcMapStorage<BGR, true, Map, Converter> 1945 (_graph, map, converter); 1946 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 1947 _writer_bits::MapStorageBase<Edge>* backward_storage = 1948 new _writer_bits::GraphArcMapStorage<BGR, false, Map, Converter> 1949 (_graph, map, converter); 1950 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); 1951 return *this; 1952 } 1953 1954 /// \brief Attribute writing rule 1955 /// 1956 /// Add an attribute writing rule to the writer. 1957 template <typename Value> 1958 BpGraphWriter& attribute(const std::string& caption, const Value& value) { 1959 _writer_bits::ValueStorageBase* storage = 1960 new _writer_bits::ValueStorage<Value>(value); 1961 _attributes.push_back(std::make_pair(caption, storage)); 1962 return *this; 1963 } 1964 1965 /// \brief Attribute writing rule 1966 /// 1967 /// Add an attribute writing rule with specialized converter to the 1968 /// writer. 1969 template <typename Value, typename Converter> 1970 BpGraphWriter& attribute(const std::string& caption, const Value& value, 1971 const Converter& converter = Converter()) { 1972 _writer_bits::ValueStorageBase* storage = 1973 new _writer_bits::ValueStorage<Value, Converter>(value, converter); 1974 _attributes.push_back(std::make_pair(caption, storage)); 1975 return *this; 1976 } 1977 1978 /// \brief Node writing rule 1979 /// 1980 /// Add a node writing rule to the writer. 1981 BpGraphWriter& node(const std::string& caption, const Node& node) { 1982 typedef _writer_bits::DoubleMapLookUpConverter< 1983 Node, RedNodeIndex, BlueNodeIndex> Converter; 1984 Converter converter(_red_node_index, _blue_node_index); 1985 _writer_bits::ValueStorageBase* storage = 1986 new _writer_bits::ValueStorage<Node, Converter>(node, converter); 1987 _attributes.push_back(std::make_pair(caption, storage)); 1988 return *this; 1989 } 1990 1991 /// \brief Red node writing rule 1992 /// 1993 /// Add a red node writing rule to the writer. 1994 BpGraphWriter& redNode(const std::string& caption, const RedNode& node) { 1995 typedef _writer_bits::MapLookUpConverter<Node> Converter; 1996 Converter converter(_red_node_index); 1997 _writer_bits::ValueStorageBase* storage = 1998 new _writer_bits::ValueStorage<Node, Converter>(node, converter); 1999 _attributes.push_back(std::make_pair(caption, storage)); 2000 return *this; 2001 } 2002 2003 /// \brief Blue node writing rule 2004 /// 2005 /// Add a blue node writing rule to the writer. 2006 BpGraphWriter& blueNode(const std::string& caption, const BlueNode& node) { 2007 typedef _writer_bits::MapLookUpConverter<Node> Converter; 2008 Converter converter(_blue_node_index); 2009 _writer_bits::ValueStorageBase* storage = 2010 new _writer_bits::ValueStorage<Node, Converter>(node, converter); 2011 _attributes.push_back(std::make_pair(caption, storage)); 2012 return *this; 2013 } 2014 2015 /// \brief Edge writing rule 2016 /// 2017 /// Add an edge writing rule to writer. 2018 BpGraphWriter& edge(const std::string& caption, const Edge& edge) { 2019 typedef _writer_bits::MapLookUpConverter<Edge> Converter; 2020 Converter converter(_edge_index); 2021 _writer_bits::ValueStorageBase* storage = 2022 new _writer_bits::ValueStorage<Edge, Converter>(edge, converter); 2023 _attributes.push_back(std::make_pair(caption, storage)); 2024 return *this; 2025 } 2026 2027 /// \brief Arc writing rule 2028 /// 2029 /// Add an arc writing rule to writer. 2030 BpGraphWriter& arc(const std::string& caption, const Arc& arc) { 2031 typedef _writer_bits::GraphArcLookUpConverter<BGR> Converter; 2032 Converter converter(_graph, _edge_index); 2033 _writer_bits::ValueStorageBase* storage = 2034 new _writer_bits::ValueStorage<Arc, Converter>(arc, converter); 2035 _attributes.push_back(std::make_pair(caption, storage)); 2036 return *this; 2037 } 2038 2039 /// \name Section Captions 2040 /// @{ 2041 2042 /// \brief Add an additional caption to the \c \@red_nodes and 2043 /// \c \@blue_nodes section 2044 /// 2045 /// Add an additional caption to the \c \@red_nodes and \c 2046 /// \@blue_nodes section. 2047 BpGraphWriter& nodes(const std::string& caption) { 2048 _nodes_caption = caption; 2049 return *this; 2050 } 2051 2052 /// \brief Add an additional caption to the \c \@edges section 2053 /// 2054 /// Add an additional caption to the \c \@edges section. 2055 BpGraphWriter& edges(const std::string& caption) { 2056 _edges_caption = caption; 2057 return *this; 2058 } 2059 2060 /// \brief Add an additional caption to the \c \@attributes section 2061 /// 2062 /// Add an additional caption to the \c \@attributes section. 2063 BpGraphWriter& attributes(const std::string& caption) { 2064 _attributes_caption = caption; 2065 return *this; 2066 } 2067 2068 /// \name Skipping Section 2069 /// @{ 2070 2071 /// \brief Skip writing the node set 2072 /// 2073 /// The \c \@red_nodes and \c \@blue_nodes section will not be 2074 /// written to the stream. 2075 BpGraphWriter& skipNodes() { 2076 LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member"); 2077 _skip_nodes = true; 2078 return *this; 2079 } 2080 2081 /// \brief Skip writing edge set 2082 /// 2083 /// The \c \@edges section will not be written to the stream. 2084 BpGraphWriter& skipEdges() { 2085 LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member"); 2086 _skip_edges = true; 2087 return *this; 2088 } 2089 2090 /// @} 2091 2092 private: 2093 2094 void writeRedNodes() { 2095 _writer_bits::MapStorageBase<RedNode>* label = 0; 2096 for (typename RedNodeMaps::iterator it = _red_node_maps.begin(); 2097 it != _red_node_maps.end(); ++it) { 2098 if (it->first == "label") { 2099 label = it->second; 2100 break; 2101 } 2102 } 2103 2104 *_os << "@red_nodes"; 2105 if (!_nodes_caption.empty()) { 2106 _writer_bits::writeToken(*_os << ' ', _nodes_caption); 2107 } 2108 *_os << std::endl; 2109 2110 if (label == 0) { 2111 *_os << "label" << '\t'; 2112 } 2113 for (typename RedNodeMaps::iterator it = _red_node_maps.begin(); 2114 it != _red_node_maps.end(); ++it) { 2115 _writer_bits::writeToken(*_os, it->first) << '\t'; 2116 } 2117 *_os << std::endl; 2118 2119 std::vector<RedNode> nodes; 2120 for (RedNodeIt n(_graph); n != INVALID; ++n) { 2121 nodes.push_back(n); 2122 } 2123 2124 if (label == 0) { 2125 IdMap<BGR, Node> id_map(_graph); 2126 _writer_bits::MapLess<IdMap<BGR, Node> > id_less(id_map); 2127 std::sort(nodes.begin(), nodes.end(), id_less); 2128 } else { 2129 label->sort(nodes); 2130 } 2131 2132 for (int i = 0; i < static_cast<int>(nodes.size()); ++i) { 2133 RedNode n = nodes[i]; 2134 if (label == 0) { 2135 std::ostringstream os; 2136 os << _graph.id(static_cast<Node>(n)); 2137 _writer_bits::writeToken(*_os, os.str()); 2138 *_os << '\t'; 2139 _red_node_index.insert(std::make_pair(n, os.str())); 2140 } 2141 for (typename RedNodeMaps::iterator it = _red_node_maps.begin(); 2142 it != _red_node_maps.end(); ++it) { 2143 std::string value = it->second->get(n); 2144 _writer_bits::writeToken(*_os, value); 2145 if (it->first == "label") { 2146 _red_node_index.insert(std::make_pair(n, value)); 2147 } 2148 *_os << '\t'; 2149 } 2150 *_os << std::endl; 2151 } 2152 } 2153 2154 void writeBlueNodes() { 2155 _writer_bits::MapStorageBase<BlueNode>* label = 0; 2156 for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin(); 2157 it != _blue_node_maps.end(); ++it) { 2158 if (it->first == "label") { 2159 label = it->second; 2160 break; 2161 } 2162 } 2163 2164 *_os << "@blue_nodes"; 2165 if (!_nodes_caption.empty()) { 2166 _writer_bits::writeToken(*_os << ' ', _nodes_caption); 2167 } 2168 *_os << std::endl; 2169 2170 if (label == 0) { 2171 *_os << "label" << '\t'; 2172 } 2173 for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin(); 2174 it != _blue_node_maps.end(); ++it) { 2175 _writer_bits::writeToken(*_os, it->first) << '\t'; 2176 } 2177 *_os << std::endl; 2178 2179 std::vector<BlueNode> nodes; 2180 for (BlueNodeIt n(_graph); n != INVALID; ++n) { 2181 nodes.push_back(n); 2182 } 2183 2184 if (label == 0) { 2185 IdMap<BGR, Node> id_map(_graph); 2186 _writer_bits::MapLess<IdMap<BGR, Node> > id_less(id_map); 2187 std::sort(nodes.begin(), nodes.end(), id_less); 2188 } else { 2189 label->sort(nodes); 2190 } 2191 2192 for (int i = 0; i < static_cast<int>(nodes.size()); ++i) { 2193 BlueNode n = nodes[i]; 2194 if (label == 0) { 2195 std::ostringstream os; 2196 os << _graph.id(static_cast<Node>(n)); 2197 _writer_bits::writeToken(*_os, os.str()); 2198 *_os << '\t'; 2199 _blue_node_index.insert(std::make_pair(n, os.str())); 2200 } 2201 for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin(); 2202 it != _blue_node_maps.end(); ++it) { 2203 std::string value = it->second->get(n); 2204 _writer_bits::writeToken(*_os, value); 2205 if (it->first == "label") { 2206 _blue_node_index.insert(std::make_pair(n, value)); 2207 } 2208 *_os << '\t'; 2209 } 2210 *_os << std::endl; 2211 } 2212 } 2213 2214 void createRedNodeIndex() { 2215 _writer_bits::MapStorageBase<RedNode>* label = 0; 2216 for (typename RedNodeMaps::iterator it = _red_node_maps.begin(); 2217 it != _red_node_maps.end(); ++it) { 2218 if (it->first == "label") { 2219 label = it->second; 2220 break; 2221 } 2222 } 2223 2224 if (label == 0) { 2225 for (RedNodeIt n(_graph); n != INVALID; ++n) { 2226 std::ostringstream os; 2227 os << _graph.id(n); 2228 _red_node_index.insert(std::make_pair(n, os.str())); 2229 } 2230 } else { 2231 for (RedNodeIt n(_graph); n != INVALID; ++n) { 2232 std::string value = label->get(n); 2233 _red_node_index.insert(std::make_pair(n, value)); 2234 } 2235 } 2236 } 2237 2238 void createBlueNodeIndex() { 2239 _writer_bits::MapStorageBase<BlueNode>* label = 0; 2240 for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin(); 2241 it != _blue_node_maps.end(); ++it) { 2242 if (it->first == "label") { 2243 label = it->second; 2244 break; 2245 } 2246 } 2247 2248 if (label == 0) { 2249 for (BlueNodeIt n(_graph); n != INVALID; ++n) { 2250 std::ostringstream os; 2251 os << _graph.id(n); 2252 _blue_node_index.insert(std::make_pair(n, os.str())); 2253 } 2254 } else { 2255 for (BlueNodeIt n(_graph); n != INVALID; ++n) { 2256 std::string value = label->get(n); 2257 _blue_node_index.insert(std::make_pair(n, value)); 2258 } 2259 } 2260 } 2261 2262 void writeEdges() { 2263 _writer_bits::MapStorageBase<Edge>* label = 0; 2264 for (typename EdgeMaps::iterator it = _edge_maps.begin(); 2265 it != _edge_maps.end(); ++it) { 2266 if (it->first == "label") { 2267 label = it->second; 2268 break; 2269 } 2270 } 2271 2272 *_os << "@edges"; 2273 if (!_edges_caption.empty()) { 2274 _writer_bits::writeToken(*_os << ' ', _edges_caption); 2275 } 2276 *_os << std::endl; 2277 2278 *_os << '\t' << '\t'; 2279 if (label == 0) { 2280 *_os << "label" << '\t'; 2281 } 2282 for (typename EdgeMaps::iterator it = _edge_maps.begin(); 2283 it != _edge_maps.end(); ++it) { 2284 _writer_bits::writeToken(*_os, it->first) << '\t'; 2285 } 2286 *_os << std::endl; 2287 2288 std::vector<Edge> edges; 2289 for (EdgeIt n(_graph); n != INVALID; ++n) { 2290 edges.push_back(n); 2291 } 2292 2293 if (label == 0) { 2294 IdMap<BGR, Edge> id_map(_graph); 2295 _writer_bits::MapLess<IdMap<BGR, Edge> > id_less(id_map); 2296 std::sort(edges.begin(), edges.end(), id_less); 2297 } else { 2298 label->sort(edges); 2299 } 2300 2301 for (int i = 0; i < static_cast<int>(edges.size()); ++i) { 2302 Edge e = edges[i]; 2303 _writer_bits::writeToken(*_os, _red_node_index. 2304 find(_graph.redNode(e))->second); 2305 *_os << '\t'; 2306 _writer_bits::writeToken(*_os, _blue_node_index. 2307 find(_graph.blueNode(e))->second); 2308 *_os << '\t'; 2309 if (label == 0) { 2310 std::ostringstream os; 2311 os << _graph.id(e); 2312 _writer_bits::writeToken(*_os, os.str()); 2313 *_os << '\t'; 2314 _edge_index.insert(std::make_pair(e, os.str())); 2315 } 2316 for (typename EdgeMaps::iterator it = _edge_maps.begin(); 2317 it != _edge_maps.end(); ++it) { 2318 std::string value = it->second->get(e); 2319 _writer_bits::writeToken(*_os, value); 2320 if (it->first == "label") { 2321 _edge_index.insert(std::make_pair(e, value)); 2322 } 2323 *_os << '\t'; 2324 } 2325 *_os << std::endl; 2326 } 2327 } 2328 2329 void createEdgeIndex() { 2330 _writer_bits::MapStorageBase<Edge>* label = 0; 2331 for (typename EdgeMaps::iterator it = _edge_maps.begin(); 2332 it != _edge_maps.end(); ++it) { 2333 if (it->first == "label") { 2334 label = it->second; 2335 break; 2336 } 2337 } 2338 2339 if (label == 0) { 2340 for (EdgeIt e(_graph); e != INVALID; ++e) { 2341 std::ostringstream os; 2342 os << _graph.id(e); 2343 _edge_index.insert(std::make_pair(e, os.str())); 2344 } 2345 } else { 2346 for (EdgeIt e(_graph); e != INVALID; ++e) { 2347 std::string value = label->get(e); 2348 _edge_index.insert(std::make_pair(e, value)); 2349 } 2350 } 2351 } 2352 2353 void writeAttributes() { 2354 if (_attributes.empty()) return; 2355 *_os << "@attributes"; 2356 if (!_attributes_caption.empty()) { 2357 _writer_bits::writeToken(*_os << ' ', _attributes_caption); 2358 } 2359 *_os << std::endl; 2360 for (typename Attributes::iterator it = _attributes.begin(); 2361 it != _attributes.end(); ++it) { 2362 _writer_bits::writeToken(*_os, it->first) << ' '; 2363 _writer_bits::writeToken(*_os, it->second->get()); 2364 *_os << std::endl; 2365 } 2366 } 2367 2368 public: 2369 2370 /// \name Execution of the Writer 2371 /// @{ 2372 2373 /// \brief Start the batch processing 2374 /// 2375 /// This function starts the batch processing. 2376 void run() { 2377 if (!_skip_nodes) { 2378 writeRedNodes(); 2379 writeBlueNodes(); 2380 } else { 2381 createRedNodeIndex(); 2382 createBlueNodeIndex(); 2383 } 2384 if (!_skip_edges) { 2385 writeEdges(); 2386 } else { 2387 createEdgeIndex(); 2388 } 2389 writeAttributes(); 2390 } 2391 2392 /// \brief Give back the stream of the writer 2393 /// 2394 /// Give back the stream of the writer 2395 std::ostream& ostream() { 2396 return *_os; 2397 } 2398 2399 /// @} 2400 }; 2401 2402 /// \ingroup lemon_io 2403 /// 2404 /// \brief Return a \ref BpGraphWriter class 2405 /// 2406 /// This function just returns a \ref BpGraphWriter class. 2407 /// 2408 /// With this function a bipartite graph can be write to a file or output 2409 /// stream in \ref lgf-format "LGF" format with several maps and 2410 /// attributes. For example, with the following code a bipartite 2411 /// weighted matching problem can be written to the standard output, 2412 /// i.e. a graph with a \e weight map on the edges: 2413 /// 2414 ///\code 2415 ///ListBpGraph graph; 2416 ///ListBpGraph::EdgeMap<int> weight(graph); 2417 /// // Setting the weight map 2418 ///bpGraphWriter(graph, std::cout). 2419 /// edgeMap("weight", weight). 2420 /// run(); 2421 ///\endcode 2422 /// 2423 /// For a complete documentation, please see the \ref BpGraphWriter 2424 /// class documentation. 2425 /// \warning Don't forget to put the \ref BpGraphWriter::run() "run()" 2426 /// to the end of the parameter list. 2427 /// \relates BpGraphWriter 2428 /// \sa bpGraphWriter(const TBGR& graph, const std::string& fn) 2429 /// \sa bpGraphWriter(const TBGR& graph, const char* fn) 2430 template <typename TBGR> 2431 BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, std::ostream& os) { 2432 BpGraphWriter<TBGR> tmp(graph, os); 2433 return tmp; 2434 } 2435 2436 /// \brief Return a \ref BpGraphWriter class 2437 /// 2438 /// This function just returns a \ref BpGraphWriter class. 2439 /// \relates BpGraphWriter 2440 /// \sa graphWriter(const TBGR& graph, std::ostream& os) 2441 template <typename TBGR> 2442 BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const std::string& fn) { 2443 BpGraphWriter<TBGR> tmp(graph, fn); 2444 return tmp; 2445 } 2446 2447 /// \brief Return a \ref BpGraphWriter class 2448 /// 2449 /// This function just returns a \ref BpGraphWriter class. 2450 /// \relates BpGraphWriter 2451 /// \sa graphWriter(const TBGR& graph, std::ostream& os) 2452 template <typename TBGR> 2453 BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char* fn) { 2454 BpGraphWriter<TBGR> tmp(graph, fn); 1608 2455 return tmp; 1609 2456 } -
lemon/list_graph.h
r877 r1025 1600 1600 1601 1601 /// @} 1602 1603 class ListBpGraphBase { 1604 1605 protected: 1606 1607 struct NodeT { 1608 int first_out; 1609 int prev, next; 1610 int partition_prev, partition_next; 1611 int partition_index; 1612 bool red; 1613 }; 1614 1615 struct ArcT { 1616 int target; 1617 int prev_out, next_out; 1618 }; 1619 1620 std::vector<NodeT> nodes; 1621 1622 int first_node, first_red, first_blue; 1623 int max_red, max_blue; 1624 1625 int first_free_red, first_free_blue; 1626 1627 std::vector<ArcT> arcs; 1628 1629 int first_free_arc; 1630 1631 public: 1632 1633 typedef ListBpGraphBase BpGraph; 1634 1635 class Node { 1636 friend class ListBpGraphBase; 1637 protected: 1638 1639 int id; 1640 explicit Node(int pid) { id = pid;} 1641 1642 public: 1643 Node() {} 1644 Node (Invalid) { id = -1; } 1645 bool operator==(const Node& node) const {return id == node.id;} 1646 bool operator!=(const Node& node) const {return id != node.id;} 1647 bool operator<(const Node& node) const {return id < node.id;} 1648 }; 1649 1650 class RedNode : public Node { 1651 friend class ListBpGraphBase; 1652 protected: 1653 1654 explicit RedNode(int pid) : Node(pid) {} 1655 1656 public: 1657 RedNode() {} 1658 RedNode(const RedNode& node) : Node(node) {} 1659 RedNode(Invalid) : Node(INVALID){} 1660 }; 1661 1662 class BlueNode : public Node { 1663 friend class ListBpGraphBase; 1664 protected: 1665 1666 explicit BlueNode(int pid) : Node(pid) {} 1667 1668 public: 1669 BlueNode() {} 1670 BlueNode(const BlueNode& node) : Node(node) {} 1671 BlueNode(Invalid) : Node(INVALID){} 1672 }; 1673 1674 class Edge { 1675 friend class ListBpGraphBase; 1676 protected: 1677 1678 int id; 1679 explicit Edge(int pid) { id = pid;} 1680 1681 public: 1682 Edge() {} 1683 Edge (Invalid) { id = -1; } 1684 bool operator==(const Edge& edge) const {return id == edge.id;} 1685 bool operator!=(const Edge& edge) const {return id != edge.id;} 1686 bool operator<(const Edge& edge) const {return id < edge.id;} 1687 }; 1688 1689 class Arc { 1690 friend class ListBpGraphBase; 1691 protected: 1692 1693 int id; 1694 explicit Arc(int pid) { id = pid;} 1695 1696 public: 1697 operator Edge() const { 1698 return id != -1 ? edgeFromId(id / 2) : INVALID; 1699 } 1700 1701 Arc() {} 1702 Arc (Invalid) { id = -1; } 1703 bool operator==(const Arc& arc) const {return id == arc.id;} 1704 bool operator!=(const Arc& arc) const {return id != arc.id;} 1705 bool operator<(const Arc& arc) const {return id < arc.id;} 1706 }; 1707 1708 ListBpGraphBase() 1709 : nodes(), first_node(-1), 1710 first_red(-1), first_blue(-1), 1711 max_red(-1), max_blue(-1), 1712 first_free_red(-1), first_free_blue(-1), 1713 arcs(), first_free_arc(-1) {} 1714 1715 1716 bool red(Node n) const { return nodes[n.id].red; } 1717 bool blue(Node n) const { return !nodes[n.id].red; } 1718 1719 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); } 1720 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); } 1721 1722 int maxNodeId() const { return nodes.size()-1; } 1723 int maxRedId() const { return max_red; } 1724 int maxBlueId() const { return max_blue; } 1725 int maxEdgeId() const { return arcs.size() / 2 - 1; } 1726 int maxArcId() const { return arcs.size()-1; } 1727 1728 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } 1729 Node target(Arc e) const { return Node(arcs[e.id].target); } 1730 1731 RedNode redNode(Edge e) const { 1732 return RedNode(arcs[2 * e.id].target); 1733 } 1734 BlueNode blueNode(Edge e) const { 1735 return BlueNode(arcs[2 * e.id + 1].target); 1736 } 1737 1738 static bool direction(Arc e) { 1739 return (e.id & 1) == 1; 1740 } 1741 1742 static Arc direct(Edge e, bool d) { 1743 return Arc(e.id * 2 + (d ? 1 : 0)); 1744 } 1745 1746 void first(Node& node) const { 1747 node.id = first_node; 1748 } 1749 1750 void next(Node& node) const { 1751 node.id = nodes[node.id].next; 1752 } 1753 1754 void first(RedNode& node) const { 1755 node.id = first_red; 1756 } 1757 1758 void next(RedNode& node) const { 1759 node.id = nodes[node.id].partition_next; 1760 } 1761 1762 void first(BlueNode& node) const { 1763 node.id = first_blue; 1764 } 1765 1766 void next(BlueNode& node) const { 1767 node.id = nodes[node.id].partition_next; 1768 } 1769 1770 void first(Arc& e) const { 1771 int n = first_node; 1772 while (n != -1 && nodes[n].first_out == -1) { 1773 n = nodes[n].next; 1774 } 1775 e.id = (n == -1) ? -1 : nodes[n].first_out; 1776 } 1777 1778 void next(Arc& e) const { 1779 if (arcs[e.id].next_out != -1) { 1780 e.id = arcs[e.id].next_out; 1781 } else { 1782 int n = nodes[arcs[e.id ^ 1].target].next; 1783 while(n != -1 && nodes[n].first_out == -1) { 1784 n = nodes[n].next; 1785 } 1786 e.id = (n == -1) ? -1 : nodes[n].first_out; 1787 } 1788 } 1789 1790 void first(Edge& e) const { 1791 int n = first_node; 1792 while (n != -1) { 1793 e.id = nodes[n].first_out; 1794 while ((e.id & 1) != 1) { 1795 e.id = arcs[e.id].next_out; 1796 } 1797 if (e.id != -1) { 1798 e.id /= 2; 1799 return; 1800 } 1801 n = nodes[n].next; 1802 } 1803 e.id = -1; 1804 } 1805 1806 void next(Edge& e) const { 1807 int n = arcs[e.id * 2].target; 1808 e.id = arcs[(e.id * 2) | 1].next_out; 1809 while ((e.id & 1) != 1) { 1810 e.id = arcs[e.id].next_out; 1811 } 1812 if (e.id != -1) { 1813 e.id /= 2; 1814 return; 1815 } 1816 n = nodes[n].next; 1817 while (n != -1) { 1818 e.id = nodes[n].first_out; 1819 while ((e.id & 1) != 1) { 1820 e.id = arcs[e.id].next_out; 1821 } 1822 if (e.id != -1) { 1823 e.id /= 2; 1824 return; 1825 } 1826 n = nodes[n].next; 1827 } 1828 e.id = -1; 1829 } 1830 1831 void firstOut(Arc &e, const Node& v) const { 1832 e.id = nodes[v.id].first_out; 1833 } 1834 void nextOut(Arc &e) const { 1835 e.id = arcs[e.id].next_out; 1836 } 1837 1838 void firstIn(Arc &e, const Node& v) const { 1839 e.id = ((nodes[v.id].first_out) ^ 1); 1840 if (e.id == -2) e.id = -1; 1841 } 1842 void nextIn(Arc &e) const { 1843 e.id = ((arcs[e.id ^ 1].next_out) ^ 1); 1844 if (e.id == -2) e.id = -1; 1845 } 1846 1847 void firstInc(Edge &e, bool& d, const Node& v) const { 1848 int a = nodes[v.id].first_out; 1849 if (a != -1 ) { 1850 e.id = a / 2; 1851 d = ((a & 1) == 1); 1852 } else { 1853 e.id = -1; 1854 d = true; 1855 } 1856 } 1857 void nextInc(Edge &e, bool& d) const { 1858 int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); 1859 if (a != -1 ) { 1860 e.id = a / 2; 1861 d = ((a & 1) == 1); 1862 } else { 1863 e.id = -1; 1864 d = true; 1865 } 1866 } 1867 1868 static int id(Node v) { return v.id; } 1869 int id(RedNode v) const { return nodes[v.id].partition_index; } 1870 int id(BlueNode v) const { return nodes[v.id].partition_index; } 1871 static int id(Arc e) { return e.id; } 1872 static int id(Edge e) { return e.id; } 1873 1874 static Node nodeFromId(int id) { return Node(id);} 1875 static Arc arcFromId(int id) { return Arc(id);} 1876 static Edge edgeFromId(int id) { return Edge(id);} 1877 1878 bool valid(Node n) const { 1879 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 1880 nodes[n.id].prev != -2; 1881 } 1882 1883 bool valid(Arc a) const { 1884 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 1885 arcs[a.id].prev_out != -2; 1886 } 1887 1888 bool valid(Edge e) const { 1889 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && 1890 arcs[2 * e.id].prev_out != -2; 1891 } 1892 1893 RedNode addRedNode() { 1894 int n; 1895 1896 if(first_free_red==-1) { 1897 n = nodes.size(); 1898 nodes.push_back(NodeT()); 1899 nodes[n].partition_index = ++max_red; 1900 nodes[n].red = true; 1901 } else { 1902 n = first_free_red; 1903 first_free_red = nodes[n].next; 1904 } 1905 1906 nodes[n].next = first_node; 1907 if (first_node != -1) nodes[first_node].prev = n; 1908 first_node = n; 1909 nodes[n].prev = -1; 1910 1911 nodes[n].partition_next = first_red; 1912 if (first_red != -1) nodes[first_red].partition_prev = n; 1913 first_red = n; 1914 nodes[n].partition_prev = -1; 1915 1916 nodes[n].first_out = -1; 1917 1918 return RedNode(n); 1919 } 1920 1921 BlueNode addBlueNode() { 1922 int n; 1923 1924 if(first_free_blue==-1) { 1925 n = nodes.size(); 1926 nodes.push_back(NodeT()); 1927 nodes[n].partition_index = ++max_blue; 1928 nodes[n].red = false; 1929 } else { 1930 n = first_free_blue; 1931 first_free_blue = nodes[n].next; 1932 } 1933 1934 nodes[n].next = first_node; 1935 if (first_node != -1) nodes[first_node].prev = n; 1936 first_node = n; 1937 nodes[n].prev = -1; 1938 1939 nodes[n].partition_next = first_blue; 1940 if (first_blue != -1) nodes[first_blue].partition_prev = n; 1941 first_blue = n; 1942 nodes[n].partition_prev = -1; 1943 1944 nodes[n].first_out = -1; 1945 1946 return BlueNode(n); 1947 } 1948 1949 Edge addEdge(Node u, Node v) { 1950 int n; 1951 1952 if (first_free_arc == -1) { 1953 n = arcs.size(); 1954 arcs.push_back(ArcT()); 1955 arcs.push_back(ArcT()); 1956 } else { 1957 n = first_free_arc; 1958 first_free_arc = arcs[n].next_out; 1959 } 1960 1961 arcs[n].target = u.id; 1962 arcs[n | 1].target = v.id; 1963 1964 arcs[n].next_out = nodes[v.id].first_out; 1965 if (nodes[v.id].first_out != -1) { 1966 arcs[nodes[v.id].first_out].prev_out = n; 1967 } 1968 arcs[n].prev_out = -1; 1969 nodes[v.id].first_out = n; 1970 1971 arcs[n | 1].next_out = nodes[u.id].first_out; 1972 if (nodes[u.id].first_out != -1) { 1973 arcs[nodes[u.id].first_out].prev_out = (n | 1); 1974 } 1975 arcs[n | 1].prev_out = -1; 1976 nodes[u.id].first_out = (n | 1); 1977 1978 return Edge(n / 2); 1979 } 1980 1981 void erase(const Node& node) { 1982 int n = node.id; 1983 1984 if(nodes[n].next != -1) { 1985 nodes[nodes[n].next].prev = nodes[n].prev; 1986 } 1987 1988 if(nodes[n].prev != -1) { 1989 nodes[nodes[n].prev].next = nodes[n].next; 1990 } else { 1991 first_node = nodes[n].next; 1992 } 1993 1994 if (nodes[n].partition_next != -1) { 1995 nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev; 1996 } 1997 1998 if (nodes[n].partition_prev != -1) { 1999 nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next; 2000 } else { 2001 if (nodes[n].red) { 2002 first_red = nodes[n].partition_next; 2003 } else { 2004 first_blue = nodes[n].partition_next; 2005 } 2006 } 2007 2008 if (nodes[n].red) { 2009 nodes[n].next = first_free_red; 2010 first_free_red = n; 2011 } else { 2012 nodes[n].next = first_free_blue; 2013 first_free_blue = n; 2014 } 2015 nodes[n].prev = -2; 2016 } 2017 2018 void erase(const Edge& edge) { 2019 int n = edge.id * 2; 2020 2021 if (arcs[n].next_out != -1) { 2022 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; 2023 } 2024 2025 if (arcs[n].prev_out != -1) { 2026 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; 2027 } else { 2028 nodes[arcs[n | 1].target].first_out = arcs[n].next_out; 2029 } 2030 2031 if (arcs[n | 1].next_out != -1) { 2032 arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out; 2033 } 2034 2035 if (arcs[n | 1].prev_out != -1) { 2036 arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out; 2037 } else { 2038 nodes[arcs[n].target].first_out = arcs[n | 1].next_out; 2039 } 2040 2041 arcs[n].next_out = first_free_arc; 2042 first_free_arc = n; 2043 arcs[n].prev_out = -2; 2044 arcs[n | 1].prev_out = -2; 2045 2046 } 2047 2048 void clear() { 2049 arcs.clear(); 2050 nodes.clear(); 2051 first_node = first_free_arc = first_red = first_blue = 2052 max_red = max_blue = first_free_red = first_free_blue = -1; 2053 } 2054 2055 protected: 2056 2057 void changeRed(Edge e, RedNode n) { 2058 if(arcs[(2 * e.id) | 1].next_out != -1) { 2059 arcs[arcs[(2 * e.id) | 1].next_out].prev_out = 2060 arcs[(2 * e.id) | 1].prev_out; 2061 } 2062 if(arcs[(2 * e.id) | 1].prev_out != -1) { 2063 arcs[arcs[(2 * e.id) | 1].prev_out].next_out = 2064 arcs[(2 * e.id) | 1].next_out; 2065 } else { 2066 nodes[arcs[2 * e.id].target].first_out = 2067 arcs[(2 * e.id) | 1].next_out; 2068 } 2069 2070 if (nodes[n.id].first_out != -1) { 2071 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); 2072 } 2073 arcs[2 * e.id].target = n.id; 2074 arcs[(2 * e.id) | 1].prev_out = -1; 2075 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out; 2076 nodes[n.id].first_out = ((2 * e.id) | 1); 2077 } 2078 2079 void changeBlue(Edge e, BlueNode n) { 2080 if(arcs[2 * e.id].next_out != -1) { 2081 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; 2082 } 2083 if(arcs[2 * e.id].prev_out != -1) { 2084 arcs[arcs[2 * e.id].prev_out].next_out = 2085 arcs[2 * e.id].next_out; 2086 } else { 2087 nodes[arcs[(2 * e.id) | 1].target].first_out = 2088 arcs[2 * e.id].next_out; 2089 } 2090 2091 if (nodes[n.id].first_out != -1) { 2092 arcs[nodes[n.id].first_out].prev_out = 2 * e.id; 2093 } 2094 arcs[(2 * e.id) | 1].target = n.id; 2095 arcs[2 * e.id].prev_out = -1; 2096 arcs[2 * e.id].next_out = nodes[n.id].first_out; 2097 nodes[n.id].first_out = 2 * e.id; 2098 } 2099 2100 }; 2101 2102 typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase; 2103 2104 2105 /// \addtogroup graphs 2106 /// @{ 2107 2108 ///A general undirected graph structure. 2109 2110 ///\ref ListBpGraph is a versatile and fast undirected graph 2111 ///implementation based on linked lists that are stored in 2112 ///\c std::vector structures. 2113 /// 2114 ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept" 2115 ///and it also provides several useful additional functionalities. 2116 ///Most of its member functions and nested classes are documented 2117 ///only in the concept class. 2118 /// 2119 ///This class provides only linear time counting for nodes, edges and arcs. 2120 /// 2121 ///\sa concepts::BpGraph 2122 ///\sa ListDigraph 2123 class ListBpGraph : public ExtendedListBpGraphBase { 2124 typedef ExtendedListBpGraphBase Parent; 2125 2126 private: 2127 /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead. 2128 ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase() {}; 2129 /// \brief Assignment of a graph to another one is \e not allowed. 2130 /// Use BpGraphCopy instead. 2131 void operator=(const ListBpGraph &) {} 2132 public: 2133 /// Constructor 2134 2135 /// Constructor. 2136 /// 2137 ListBpGraph() {} 2138 2139 typedef Parent::OutArcIt IncEdgeIt; 2140 2141 /// \brief Add a new red node to the graph. 2142 /// 2143 /// This function adds a red new node to the graph. 2144 /// \return The new node. 2145 RedNode addRedNode() { return Parent::addRedNode(); } 2146 2147 /// \brief Add a new blue node to the graph. 2148 /// 2149 /// This function adds a blue new node to the graph. 2150 /// \return The new node. 2151 BlueNode addBlueNode() { return Parent::addBlueNode(); } 2152 2153 /// \brief Add a new edge to the graph. 2154 /// 2155 /// This function adds a new edge to the graph between nodes 2156 /// \c u and \c v with inherent orientation from node \c u to 2157 /// node \c v. 2158 /// \return The new edge. 2159 Edge addEdge(RedNode u, BlueNode v) { 2160 return Parent::addEdge(u, v); 2161 } 2162 Edge addEdge(BlueNode v, RedNode u) { 2163 return Parent::addEdge(u, v); 2164 } 2165 2166 ///\brief Erase a node from the graph. 2167 /// 2168 /// This function erases the given node along with its incident arcs 2169 /// from the graph. 2170 /// 2171 /// \note All iterators referencing the removed node or the incident 2172 /// edges are invalidated, of course. 2173 void erase(Node n) { Parent::erase(n); } 2174 2175 ///\brief Erase an edge from the graph. 2176 /// 2177 /// This function erases the given edge from the graph. 2178 /// 2179 /// \note All iterators referencing the removed edge are invalidated, 2180 /// of course. 2181 void erase(Edge e) { Parent::erase(e); } 2182 /// Node validity check 2183 2184 /// This function gives back \c true if the given node is valid, 2185 /// i.e. it is a real node of the graph. 2186 /// 2187 /// \warning A removed node could become valid again if new nodes are 2188 /// added to the graph. 2189 bool valid(Node n) const { return Parent::valid(n); } 2190 /// Edge validity check 2191 2192 /// This function gives back \c true if the given edge is valid, 2193 /// i.e. it is a real edge of the graph. 2194 /// 2195 /// \warning A removed edge could become valid again if new edges are 2196 /// added to the graph. 2197 bool valid(Edge e) const { return Parent::valid(e); } 2198 /// Arc validity check 2199 2200 /// This function gives back \c true if the given arc is valid, 2201 /// i.e. it is a real arc of the graph. 2202 /// 2203 /// \warning A removed arc could become valid again if new edges are 2204 /// added to the graph. 2205 bool valid(Arc a) const { return Parent::valid(a); } 2206 2207 /// \brief Change the red node of an edge. 2208 /// 2209 /// This function changes the red node of the given edge \c e to \c n. 2210 /// 2211 ///\note \c EdgeIt and \c ArcIt iterators referencing the 2212 ///changed edge are invalidated and all other iterators whose 2213 ///base node is the changed node are also invalidated. 2214 /// 2215 ///\warning This functionality cannot be used together with the 2216 ///Snapshot feature. 2217 void changeRed(Edge e, RedNode n) { 2218 Parent::changeRed(e, n); 2219 } 2220 /// \brief Change the blue node of an edge. 2221 /// 2222 /// This function changes the blue node of the given edge \c e to \c n. 2223 /// 2224 ///\note \c EdgeIt iterators referencing the changed edge remain 2225 ///valid, but \c ArcIt iterators referencing the changed edge and 2226 ///all other iterators whose base node is the changed node are also 2227 ///invalidated. 2228 /// 2229 ///\warning This functionality cannot be used together with the 2230 ///Snapshot feature. 2231 void changeBlue(Edge e, BlueNode n) { 2232 Parent::changeBlue(e, n); 2233 } 2234 2235 ///Clear the graph. 2236 2237 ///This function erases all nodes and arcs from the graph. 2238 /// 2239 ///\note All iterators of the graph are invalidated, of course. 2240 void clear() { 2241 Parent::clear(); 2242 } 2243 2244 /// Reserve memory for nodes. 2245 2246 /// Using this function, it is possible to avoid superfluous memory 2247 /// allocation: if you know that the graph you want to build will 2248 /// be large (e.g. it will contain millions of nodes and/or edges), 2249 /// then it is worth reserving space for this amount before starting 2250 /// to build the graph. 2251 /// \sa reserveEdge() 2252 void reserveNode(int n) { nodes.reserve(n); }; 2253 2254 /// Reserve memory for edges. 2255 2256 /// Using this function, it is possible to avoid superfluous memory 2257 /// allocation: if you know that the graph you want to build will 2258 /// be large (e.g. it will contain millions of nodes and/or edges), 2259 /// then it is worth reserving space for this amount before starting 2260 /// to build the graph. 2261 /// \sa reserveNode() 2262 void reserveEdge(int m) { arcs.reserve(2 * m); }; 2263 2264 /// \brief Class to make a snapshot of the graph and restore 2265 /// it later. 2266 /// 2267 /// Class to make a snapshot of the graph and restore it later. 2268 /// 2269 /// The newly added nodes and edges can be removed 2270 /// using the restore() function. 2271 /// 2272 /// \note After a state is restored, you cannot restore a later state, 2273 /// i.e. you cannot add the removed nodes and edges again using 2274 /// another Snapshot instance. 2275 /// 2276 /// \warning Node and edge deletions and other modifications 2277 /// (e.g. changing the end-nodes of edges or contracting nodes) 2278 /// cannot be restored. These events invalidate the snapshot. 2279 /// However, the edges and nodes that were added to the graph after 2280 /// making the current snapshot can be removed without invalidating it. 2281 class Snapshot { 2282 protected: 2283 2284 typedef Parent::NodeNotifier NodeNotifier; 2285 2286 class NodeObserverProxy : public NodeNotifier::ObserverBase { 2287 public: 2288 2289 NodeObserverProxy(Snapshot& _snapshot) 2290 : snapshot(_snapshot) {} 2291 2292 using NodeNotifier::ObserverBase::attach; 2293 using NodeNotifier::ObserverBase::detach; 2294 using NodeNotifier::ObserverBase::attached; 2295 2296 protected: 2297 2298 virtual void add(const Node& node) { 2299 snapshot.addNode(node); 2300 } 2301 virtual void add(const std::vector<Node>& nodes) { 2302 for (int i = nodes.size() - 1; i >= 0; ++i) { 2303 snapshot.addNode(nodes[i]); 2304 } 2305 } 2306 virtual void erase(const Node& node) { 2307 snapshot.eraseNode(node); 2308 } 2309 virtual void erase(const std::vector<Node>& nodes) { 2310 for (int i = 0; i < int(nodes.size()); ++i) { 2311 snapshot.eraseNode(nodes[i]); 2312 } 2313 } 2314 virtual void build() { 2315 Node node; 2316 std::vector<Node> nodes; 2317 for (notifier()->first(node); node != INVALID; 2318 notifier()->next(node)) { 2319 nodes.push_back(node); 2320 } 2321 for (int i = nodes.size() - 1; i >= 0; --i) { 2322 snapshot.addNode(nodes[i]); 2323 } 2324 } 2325 virtual void clear() { 2326 Node node; 2327 for (notifier()->first(node); node != INVALID; 2328 notifier()->next(node)) { 2329 snapshot.eraseNode(node); 2330 } 2331 } 2332 2333 Snapshot& snapshot; 2334 }; 2335 2336 class EdgeObserverProxy : public EdgeNotifier::ObserverBase { 2337 public: 2338 2339 EdgeObserverProxy(Snapshot& _snapshot) 2340 : snapshot(_snapshot) {} 2341 2342 using EdgeNotifier::ObserverBase::attach; 2343 using EdgeNotifier::ObserverBase::detach; 2344 using EdgeNotifier::ObserverBase::attached; 2345 2346 protected: 2347 2348 virtual void add(const Edge& edge) { 2349 snapshot.addEdge(edge); 2350 } 2351 virtual void add(const std::vector<Edge>& edges) { 2352 for (int i = edges.size() - 1; i >= 0; ++i) { 2353 snapshot.addEdge(edges[i]); 2354 } 2355 } 2356 virtual void erase(const Edge& edge) { 2357 snapshot.eraseEdge(edge); 2358 } 2359 virtual void erase(const std::vector<Edge>& edges) { 2360 for (int i = 0; i < int(edges.size()); ++i) { 2361 snapshot.eraseEdge(edges[i]); 2362 } 2363 } 2364 virtual void build() { 2365 Edge edge; 2366 std::vector<Edge> edges; 2367 for (notifier()->first(edge); edge != INVALID; 2368 notifier()->next(edge)) { 2369 edges.push_back(edge); 2370 } 2371 for (int i = edges.size() - 1; i >= 0; --i) { 2372 snapshot.addEdge(edges[i]); 2373 } 2374 } 2375 virtual void clear() { 2376 Edge edge; 2377 for (notifier()->first(edge); edge != INVALID; 2378 notifier()->next(edge)) { 2379 snapshot.eraseEdge(edge); 2380 } 2381 } 2382 2383 Snapshot& snapshot; 2384 }; 2385 2386 ListBpGraph *graph; 2387 2388 NodeObserverProxy node_observer_proxy; 2389 EdgeObserverProxy edge_observer_proxy; 2390 2391 std::list<Node> added_nodes; 2392 std::list<Edge> added_edges; 2393 2394 2395 void addNode(const Node& node) { 2396 added_nodes.push_front(node); 2397 } 2398 void eraseNode(const Node& node) { 2399 std::list<Node>::iterator it = 2400 std::find(added_nodes.begin(), added_nodes.end(), node); 2401 if (it == added_nodes.end()) { 2402 clear(); 2403 edge_observer_proxy.detach(); 2404 throw NodeNotifier::ImmediateDetach(); 2405 } else { 2406 added_nodes.erase(it); 2407 } 2408 } 2409 2410 void addEdge(const Edge& edge) { 2411 added_edges.push_front(edge); 2412 } 2413 void eraseEdge(const Edge& edge) { 2414 std::list<Edge>::iterator it = 2415 std::find(added_edges.begin(), added_edges.end(), edge); 2416 if (it == added_edges.end()) { 2417 clear(); 2418 node_observer_proxy.detach(); 2419 throw EdgeNotifier::ImmediateDetach(); 2420 } else { 2421 added_edges.erase(it); 2422 } 2423 } 2424 2425 void attach(ListBpGraph &_graph) { 2426 graph = &_graph; 2427 node_observer_proxy.attach(graph->notifier(Node())); 2428 edge_observer_proxy.attach(graph->notifier(Edge())); 2429 } 2430 2431 void detach() { 2432 node_observer_proxy.detach(); 2433 edge_observer_proxy.detach(); 2434 } 2435 2436 bool attached() const { 2437 return node_observer_proxy.attached(); 2438 } 2439 2440 void clear() { 2441 added_nodes.clear(); 2442 added_edges.clear(); 2443 } 2444 2445 public: 2446 2447 /// \brief Default constructor. 2448 /// 2449 /// Default constructor. 2450 /// You have to call save() to actually make a snapshot. 2451 Snapshot() 2452 : graph(0), node_observer_proxy(*this), 2453 edge_observer_proxy(*this) {} 2454 2455 /// \brief Constructor that immediately makes a snapshot. 2456 /// 2457 /// This constructor immediately makes a snapshot of the given graph. 2458 Snapshot(ListBpGraph &gr) 2459 : node_observer_proxy(*this), 2460 edge_observer_proxy(*this) { 2461 attach(gr); 2462 } 2463 2464 /// \brief Make a snapshot. 2465 /// 2466 /// This function makes a snapshot of the given graph. 2467 /// It can be called more than once. In case of a repeated 2468 /// call, the previous snapshot gets lost. 2469 void save(ListBpGraph &gr) { 2470 if (attached()) { 2471 detach(); 2472 clear(); 2473 } 2474 attach(gr); 2475 } 2476 2477 /// \brief Undo the changes until the last snapshot. 2478 /// 2479 /// This function undos the changes until the last snapshot 2480 /// created by save() or Snapshot(ListBpGraph&). 2481 /// 2482 /// \warning This method invalidates the snapshot, i.e. repeated 2483 /// restoring is not supported unless you call save() again. 2484 void restore() { 2485 detach(); 2486 for(std::list<Edge>::iterator it = added_edges.begin(); 2487 it != added_edges.end(); ++it) { 2488 graph->erase(*it); 2489 } 2490 for(std::list<Node>::iterator it = added_nodes.begin(); 2491 it != added_nodes.end(); ++it) { 2492 graph->erase(*it); 2493 } 2494 clear(); 2495 } 2496 2497 /// \brief Returns \c true if the snapshot is valid. 2498 /// 2499 /// This function returns \c true if the snapshot is valid. 2500 bool valid() const { 2501 return attached(); 2502 } 2503 }; 2504 }; 2505 2506 /// @} 1602 2507 } //namespace lemon 1603 2508 -
lemon/smart_graph.h
r877 r1025 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 int max_red, max_blue; 833 834 public: 835 836 typedef SmartBpGraphBase Graph; 837 838 class Node; 839 class Arc; 840 class Edge; 841 842 class Node { 843 friend class SmartBpGraphBase; 844 protected: 845 846 int _id; 847 explicit Node(int id) { _id = id;} 848 849 public: 850 Node() {} 851 Node (Invalid) { _id = -1; } 852 bool operator==(const Node& node) const {return _id == node._id;} 853 bool operator!=(const Node& node) const {return _id != node._id;} 854 bool operator<(const Node& node) const {return _id < node._id;} 855 }; 856 857 class RedNode : public Node { 858 friend class SmartBpGraphBase; 859 protected: 860 861 explicit RedNode(int pid) : Node(pid) {} 862 863 public: 864 RedNode() {} 865 RedNode(const RedNode& node) : Node(node) {} 866 RedNode(Invalid) : Node(INVALID){} 867 }; 868 869 class BlueNode : public Node { 870 friend class SmartBpGraphBase; 871 protected: 872 873 explicit BlueNode(int pid) : Node(pid) {} 874 875 public: 876 BlueNode() {} 877 BlueNode(const BlueNode& node) : Node(node) {} 878 BlueNode(Invalid) : Node(INVALID){} 879 }; 880 881 class Edge { 882 friend class SmartBpGraphBase; 883 protected: 884 885 int _id; 886 explicit Edge(int id) { _id = id;} 887 888 public: 889 Edge() {} 890 Edge (Invalid) { _id = -1; } 891 bool operator==(const Edge& arc) const {return _id == arc._id;} 892 bool operator!=(const Edge& arc) const {return _id != arc._id;} 893 bool operator<(const Edge& arc) const {return _id < arc._id;} 894 }; 895 896 class Arc { 897 friend class SmartBpGraphBase; 898 protected: 899 900 int _id; 901 explicit Arc(int id) { _id = id;} 902 903 public: 904 operator Edge() const { 905 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 906 } 907 908 Arc() {} 909 Arc (Invalid) { _id = -1; } 910 bool operator==(const Arc& arc) const {return _id == arc._id;} 911 bool operator!=(const Arc& arc) const {return _id != arc._id;} 912 bool operator<(const Arc& arc) const {return _id < arc._id;} 913 }; 914 915 916 917 SmartBpGraphBase() 918 : nodes(), arcs(), first_red(-1), first_blue(-1), 919 max_red(-1), max_blue(-1) {} 920 921 typedef True NodeNumTag; 922 typedef True EdgeNumTag; 923 typedef True ArcNumTag; 924 925 int nodeNum() const { return nodes.size(); } 926 int redNum() const { return max_red + 1; } 927 int blueNum() const { return max_blue + 1; } 928 int edgeNum() const { return arcs.size() / 2; } 929 int arcNum() const { return arcs.size(); } 930 931 int maxNodeId() const { return nodes.size()-1; } 932 int maxRedId() const { return max_red; } 933 int maxBlueId() const { return max_blue; } 934 int maxEdgeId() const { return arcs.size() / 2 - 1; } 935 int maxArcId() const { return arcs.size()-1; } 936 937 bool red(Node n) const { return nodes[n._id].red; } 938 bool blue(Node n) const { return !nodes[n._id].red; } 939 940 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); } 941 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); } 942 943 Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); } 944 Node target(Arc a) const { return Node(arcs[a._id].target); } 945 946 RedNode redNode(Edge e) const { 947 return RedNode(arcs[2 * e._id].target); 948 } 949 BlueNode blueNode(Edge e) const { 950 return BlueNode(arcs[2 * e._id + 1].target); 951 } 952 953 static bool direction(Arc a) { 954 return (a._id & 1) == 1; 955 } 956 957 static Arc direct(Edge e, bool d) { 958 return Arc(e._id * 2 + (d ? 1 : 0)); 959 } 960 961 void first(Node& node) const { 962 node._id = nodes.size() - 1; 963 } 964 965 static void next(Node& node) { 966 --node._id; 967 } 968 969 void first(RedNode& node) const { 970 node._id = first_red; 971 } 972 973 void next(RedNode& node) const { 974 node._id = nodes[node._id].partition_next; 975 } 976 977 void first(BlueNode& node) const { 978 node._id = first_blue; 979 } 980 981 void next(BlueNode& node) const { 982 node._id = nodes[node._id].partition_next; 983 } 984 985 void first(Arc& arc) const { 986 arc._id = arcs.size() - 1; 987 } 988 989 static void next(Arc& arc) { 990 --arc._id; 991 } 992 993 void first(Edge& arc) const { 994 arc._id = arcs.size() / 2 - 1; 995 } 996 997 static void next(Edge& arc) { 998 --arc._id; 999 } 1000 1001 void firstOut(Arc &arc, const Node& v) const { 1002 arc._id = nodes[v._id].first_out; 1003 } 1004 void nextOut(Arc &arc) const { 1005 arc._id = arcs[arc._id].next_out; 1006 } 1007 1008 void firstIn(Arc &arc, const Node& v) const { 1009 arc._id = ((nodes[v._id].first_out) ^ 1); 1010 if (arc._id == -2) arc._id = -1; 1011 } 1012 void nextIn(Arc &arc) const { 1013 arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1); 1014 if (arc._id == -2) arc._id = -1; 1015 } 1016 1017 void firstInc(Edge &arc, bool& d, const Node& v) const { 1018 int de = nodes[v._id].first_out; 1019 if (de != -1) { 1020 arc._id = de / 2; 1021 d = ((de & 1) == 1); 1022 } else { 1023 arc._id = -1; 1024 d = true; 1025 } 1026 } 1027 void nextInc(Edge &arc, bool& d) const { 1028 int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); 1029 if (de != -1) { 1030 arc._id = de / 2; 1031 d = ((de & 1) == 1); 1032 } else { 1033 arc._id = -1; 1034 d = true; 1035 } 1036 } 1037 1038 static int id(Node v) { return v._id; } 1039 int id(RedNode v) const { return nodes[v._id].partition_index; } 1040 int id(BlueNode v) const { return nodes[v._id].partition_index; } 1041 static int id(Arc e) { return e._id; } 1042 static int id(Edge e) { return e._id; } 1043 1044 static Node nodeFromId(int id) { return Node(id);} 1045 static Arc arcFromId(int id) { return Arc(id);} 1046 static Edge edgeFromId(int id) { return Edge(id);} 1047 1048 bool valid(Node n) const { 1049 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 1050 } 1051 bool valid(Arc a) const { 1052 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 1053 } 1054 bool valid(Edge e) const { 1055 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 1056 } 1057 1058 RedNode addRedNode() { 1059 int n = nodes.size(); 1060 nodes.push_back(NodeT()); 1061 nodes[n].first_out = -1; 1062 nodes[n].red = true; 1063 nodes[n].partition_index = ++max_red; 1064 nodes[n].partition_next = first_red; 1065 first_red = n; 1066 1067 return RedNode(n); 1068 } 1069 1070 BlueNode addBlueNode() { 1071 int n = nodes.size(); 1072 nodes.push_back(NodeT()); 1073 nodes[n].first_out = -1; 1074 nodes[n].red = false; 1075 nodes[n].partition_index = ++max_blue; 1076 nodes[n].partition_next = first_blue; 1077 first_blue = n; 1078 1079 return BlueNode(n); 1080 } 1081 1082 Edge addEdge(RedNode u, BlueNode v) { 1083 int n = arcs.size(); 1084 arcs.push_back(ArcT()); 1085 arcs.push_back(ArcT()); 1086 1087 arcs[n].target = u._id; 1088 arcs[n | 1].target = v._id; 1089 1090 arcs[n].next_out = nodes[v._id].first_out; 1091 nodes[v._id].first_out = n; 1092 1093 arcs[n | 1].next_out = nodes[u._id].first_out; 1094 nodes[u._id].first_out = (n | 1); 1095 1096 return Edge(n / 2); 1097 } 1098 1099 void clear() { 1100 arcs.clear(); 1101 nodes.clear(); 1102 first_red = -1; 1103 first_blue = -1; 1104 max_blue = -1; 1105 max_red = -1; 1106 } 1107 1108 }; 1109 1110 typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase; 1111 1112 /// \ingroup graphs 1113 /// 1114 /// \brief A smart undirected bipartite graph class. 1115 /// 1116 /// \ref SmartBpGraph is a simple and fast bipartite graph implementation. 1117 /// It is also quite memory efficient but at the price 1118 /// that it does not support node and edge deletion 1119 /// (except for the Snapshot feature). 1120 /// 1121 /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept" 1122 /// and it also provides some additional functionalities. 1123 /// Most of its member functions and nested classes are documented 1124 /// only in the concept class. 1125 /// 1126 /// This class provides constant time counting for nodes, edges and arcs. 1127 /// 1128 /// \sa concepts::BpGraph 1129 /// \sa SmartGraph 1130 class SmartBpGraph : public ExtendedSmartBpGraphBase { 1131 typedef ExtendedSmartBpGraphBase Parent; 1132 1133 private: 1134 /// Graphs are \e not copy constructible. Use GraphCopy instead. 1135 SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {}; 1136 /// \brief Assignment of a graph to another one is \e not allowed. 1137 /// Use GraphCopy instead. 1138 void operator=(const SmartBpGraph &) {} 1139 1140 public: 1141 1142 /// Constructor 1143 1144 /// Constructor. 1145 /// 1146 SmartBpGraph() {} 1147 1148 /// \brief Add a new red node to the graph. 1149 /// 1150 /// This function adds a red new node to the graph. 1151 /// \return The new node. 1152 RedNode addRedNode() { return Parent::addRedNode(); } 1153 1154 /// \brief Add a new blue node to the graph. 1155 /// 1156 /// This function adds a blue new node to the graph. 1157 /// \return The new node. 1158 BlueNode addBlueNode() { return Parent::addBlueNode(); } 1159 1160 /// \brief Add a new edge to the graph. 1161 /// 1162 /// This function adds a new edge to the graph between nodes 1163 /// \c u and \c v with inherent orientation from node \c u to 1164 /// node \c v. 1165 /// \return The new edge. 1166 Edge addEdge(RedNode u, BlueNode v) { 1167 return Parent::addEdge(u, v); 1168 } 1169 Edge addEdge(BlueNode v, RedNode u) { 1170 return Parent::addEdge(u, v); 1171 } 1172 1173 /// \brief Node validity check 1174 /// 1175 /// This function gives back \c true if the given node is valid, 1176 /// i.e. it is a real node of the graph. 1177 /// 1178 /// \warning A removed node (using Snapshot) could become valid again 1179 /// if new nodes are added to the graph. 1180 bool valid(Node n) const { return Parent::valid(n); } 1181 1182 /// \brief Edge validity check 1183 /// 1184 /// This function gives back \c true if the given edge is valid, 1185 /// i.e. it is a real edge of the graph. 1186 /// 1187 /// \warning A removed edge (using Snapshot) could become valid again 1188 /// if new edges are added to the graph. 1189 bool valid(Edge e) const { return Parent::valid(e); } 1190 1191 /// \brief Arc validity check 1192 /// 1193 /// This function gives back \c true if the given arc is valid, 1194 /// i.e. it is a real arc of the graph. 1195 /// 1196 /// \warning A removed arc (using Snapshot) could become valid again 1197 /// if new edges are added to the graph. 1198 bool valid(Arc a) const { return Parent::valid(a); } 1199 1200 ///Clear the graph. 1201 1202 ///This function erases all nodes and arcs from the graph. 1203 /// 1204 void clear() { 1205 Parent::clear(); 1206 } 1207 1208 /// Reserve memory for nodes. 1209 1210 /// Using this function, it is possible to avoid superfluous memory 1211 /// allocation: if you know that the graph you want to build will 1212 /// be large (e.g. it will contain millions of nodes and/or edges), 1213 /// then it is worth reserving space for this amount before starting 1214 /// to build the graph. 1215 /// \sa reserveEdge() 1216 void reserveNode(int n) { nodes.reserve(n); }; 1217 1218 /// Reserve memory for edges. 1219 1220 /// Using this function, it is possible to avoid superfluous memory 1221 /// allocation: if you know that the graph you want to build will 1222 /// be large (e.g. it will contain millions of nodes and/or edges), 1223 /// then it is worth reserving space for this amount before starting 1224 /// to build the graph. 1225 /// \sa reserveNode() 1226 void reserveEdge(int m) { arcs.reserve(2 * m); }; 1227 1228 public: 1229 1230 class Snapshot; 1231 1232 protected: 1233 1234 void saveSnapshot(Snapshot &s) 1235 { 1236 s._graph = this; 1237 s.node_num = nodes.size(); 1238 s.arc_num = arcs.size(); 1239 } 1240 1241 void restoreSnapshot(const Snapshot &s) 1242 { 1243 while(s.arc_num<arcs.size()) { 1244 int n=arcs.size()-1; 1245 Edge arc=edgeFromId(n/2); 1246 Parent::notifier(Edge()).erase(arc); 1247 std::vector<Arc> dir; 1248 dir.push_back(arcFromId(n)); 1249 dir.push_back(arcFromId(n-1)); 1250 Parent::notifier(Arc()).erase(dir); 1251 nodes[arcs[n-1].target].first_out=arcs[n].next_out; 1252 nodes[arcs[n].target].first_out=arcs[n-1].next_out; 1253 arcs.pop_back(); 1254 arcs.pop_back(); 1255 } 1256 while(s.node_num<nodes.size()) { 1257 int n=nodes.size()-1; 1258 Node node = nodeFromId(n); 1259 if (Parent::red(node)) { 1260 first_red = nodes[n].partition_next; 1261 if (first_red != -1) { 1262 max_red = nodes[first_red].partition_index; 1263 } else { 1264 max_red = -1; 1265 } 1266 Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node)); 1267 } else { 1268 first_blue = nodes[n].partition_next; 1269 if (first_blue != -1) { 1270 max_blue = nodes[first_blue].partition_index; 1271 } else { 1272 max_blue = -1; 1273 } 1274 Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node)); 1275 } 1276 Parent::notifier(Node()).erase(node); 1277 nodes.pop_back(); 1278 } 1279 } 1280 1281 public: 1282 1283 ///Class to make a snapshot of the graph and to restore it later. 1284 1285 ///Class to make a snapshot of the graph and to restore it later. 1286 /// 1287 ///The newly added nodes and edges can be removed using the 1288 ///restore() function. This is the only way for deleting nodes and/or 1289 ///edges from a SmartBpGraph structure. 1290 /// 1291 ///\note After a state is restored, you cannot restore a later state, 1292 ///i.e. you cannot add the removed nodes and edges again using 1293 ///another Snapshot instance. 1294 /// 1295 ///\warning The validity of the snapshot is not stored due to 1296 ///performance reasons. If you do not use the snapshot correctly, 1297 ///it can cause broken program, invalid or not restored state of 1298 ///the graph or no change. 1299 class Snapshot 1300 { 1301 SmartBpGraph *_graph; 1302 protected: 1303 friend class SmartBpGraph; 1304 unsigned int node_num; 1305 unsigned int arc_num; 1306 public: 1307 ///Default constructor. 1308 1309 ///Default constructor. 1310 ///You have to call save() to actually make a snapshot. 1311 Snapshot() : _graph(0) {} 1312 ///Constructor that immediately makes a snapshot 1313 1314 /// This constructor immediately makes a snapshot of the given graph. 1315 /// 1316 Snapshot(SmartBpGraph &gr) { 1317 gr.saveSnapshot(*this); 1318 } 1319 1320 ///Make a snapshot. 1321 1322 ///This function makes a snapshot of the given graph. 1323 ///It can be called more than once. In case of a repeated 1324 ///call, the previous snapshot gets lost. 1325 void save(SmartBpGraph &gr) 1326 { 1327 gr.saveSnapshot(*this); 1328 } 1329 1330 ///Undo the changes until the last snapshot. 1331 1332 ///This function undos the changes until the last snapshot 1333 ///created by save() or Snapshot(SmartBpGraph&). 1334 void restore() 1335 { 1336 _graph->restoreSnapshot(*this); 1337 } 1338 }; 1339 }; 1340 814 1341 } //namespace lemon 815 1342 -
test/CMakeLists.txt
r1000 r1038 17 17 bellman_ford_test 18 18 bfs_test 19 bpgraph_test 19 20 circulation_test 20 21 connectivity_test … … 35 36 heap_test 36 37 kruskal_test 38 lgf_reader_writer_test 37 39 lgf_test 38 40 maps_test … … 51 53 suurballe_test 52 54 time_measure_test 55 tsp_test 53 56 unionfind_test 54 57 ) -
test/graph_copy_test.cc
r894 r1026 210 210 } 211 211 212 template <typename GR> 213 void bpgraph_copy_test() { 214 const int nn = 10; 215 216 // Build a graph 217 SmartBpGraph from; 218 SmartBpGraph::NodeMap<int> fnm(from); 219 SmartBpGraph::RedNodeMap<int> frnm(from); 220 SmartBpGraph::BlueNodeMap<int> fbnm(from); 221 SmartBpGraph::ArcMap<int> fam(from); 222 SmartBpGraph::EdgeMap<int> fem(from); 223 SmartBpGraph::Node fn = INVALID; 224 SmartBpGraph::RedNode frn = INVALID; 225 SmartBpGraph::BlueNode fbn = INVALID; 226 SmartBpGraph::Arc fa = INVALID; 227 SmartBpGraph::Edge fe = INVALID; 228 229 std::vector<SmartBpGraph::RedNode> frnv; 230 for (int i = 0; i < nn; ++i) { 231 SmartBpGraph::RedNode node = from.addRedNode(); 232 frnv.push_back(node); 233 fnm[node] = i * i; 234 frnm[node] = i + i; 235 if (i == 0) { 236 fn = node; 237 frn = node; 238 } 239 } 240 241 std::vector<SmartBpGraph::BlueNode> fbnv; 242 for (int i = 0; i < nn; ++i) { 243 SmartBpGraph::BlueNode node = from.addBlueNode(); 244 fbnv.push_back(node); 245 fnm[node] = i * i; 246 fbnm[node] = i + i; 247 if (i == 0) fbn = node; 248 } 249 250 for (int i = 0; i < nn; ++i) { 251 for (int j = 0; j < nn; ++j) { 252 SmartBpGraph::Edge edge = from.addEdge(frnv[i], fbnv[j]); 253 fem[edge] = i * i + j * j; 254 fam[from.direct(edge, true)] = i + j * j; 255 fam[from.direct(edge, false)] = i * i + j; 256 if (i == 0 && j == 0) fa = from.direct(edge, true); 257 if (i == 0 && j == 0) fe = edge; 258 } 259 } 260 261 // Test graph copy 262 GR to; 263 typename GR::template NodeMap<int> tnm(to); 264 typename GR::template RedNodeMap<int> trnm(to); 265 typename GR::template BlueNodeMap<int> tbnm(to); 266 typename GR::template ArcMap<int> tam(to); 267 typename GR::template EdgeMap<int> tem(to); 268 typename GR::Node tn; 269 typename GR::RedNode trn; 270 typename GR::BlueNode tbn; 271 typename GR::Arc ta; 272 typename GR::Edge te; 273 274 SmartBpGraph::NodeMap<typename GR::Node> nr(from); 275 SmartBpGraph::RedNodeMap<typename GR::RedNode> rnr(from); 276 SmartBpGraph::BlueNodeMap<typename GR::BlueNode> bnr(from); 277 SmartBpGraph::ArcMap<typename GR::Arc> ar(from); 278 SmartBpGraph::EdgeMap<typename GR::Edge> er(from); 279 280 typename GR::template NodeMap<SmartBpGraph::Node> ncr(to); 281 typename GR::template RedNodeMap<SmartBpGraph::RedNode> rncr(to); 282 typename GR::template BlueNodeMap<SmartBpGraph::BlueNode> bncr(to); 283 typename GR::template ArcMap<SmartBpGraph::Arc> acr(to); 284 typename GR::template EdgeMap<SmartBpGraph::Edge> ecr(to); 285 286 bpGraphCopy(from, to). 287 nodeMap(fnm, tnm). 288 redNodeMap(frnm, trnm).blueNodeMap(fbnm, tbnm). 289 arcMap(fam, tam).edgeMap(fem, tem). 290 nodeRef(nr).redRef(rnr).blueRef(bnr). 291 arcRef(ar).edgeRef(er). 292 nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr). 293 arcCrossRef(acr).edgeCrossRef(ecr). 294 node(fn, tn).redNode(frn, trn).blueNode(fbn, tbn). 295 arc(fa, ta).edge(fe, te).run(); 296 297 check(countNodes(from) == countNodes(to), "Wrong copy."); 298 check(countRedNodes(from) == countRedNodes(to), "Wrong copy."); 299 check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy."); 300 check(countEdges(from) == countEdges(to), "Wrong copy."); 301 check(countArcs(from) == countArcs(to), "Wrong copy."); 302 303 for (SmartBpGraph::NodeIt it(from); it != INVALID; ++it) { 304 check(ncr[nr[it]] == it, "Wrong copy."); 305 check(fnm[it] == tnm[nr[it]], "Wrong copy."); 306 } 307 308 for (SmartBpGraph::RedNodeIt it(from); it != INVALID; ++it) { 309 check(ncr[nr[it]] == it, "Wrong copy."); 310 check(fnm[it] == tnm[nr[it]], "Wrong copy."); 311 check(rnr[it] == nr[it], "Wrong copy."); 312 check(rncr[rnr[it]] == it, "Wrong copy."); 313 check(frnm[it] == trnm[rnr[it]], "Wrong copy."); 314 check(to.red(rnr[it]), "Wrong copy."); 315 } 316 317 for (SmartBpGraph::BlueNodeIt it(from); it != INVALID; ++it) { 318 check(ncr[nr[it]] == it, "Wrong copy."); 319 check(fnm[it] == tnm[nr[it]], "Wrong copy."); 320 check(bnr[it] == nr[it], "Wrong copy."); 321 check(bncr[bnr[it]] == it, "Wrong copy."); 322 check(fbnm[it] == tbnm[bnr[it]], "Wrong copy."); 323 check(to.blue(bnr[it]), "Wrong copy."); 324 } 325 326 for (SmartBpGraph::ArcIt it(from); it != INVALID; ++it) { 327 check(acr[ar[it]] == it, "Wrong copy."); 328 check(fam[it] == tam[ar[it]], "Wrong copy."); 329 check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy."); 330 check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy."); 331 } 332 333 for (SmartBpGraph::EdgeIt it(from); it != INVALID; ++it) { 334 check(ecr[er[it]] == it, "Wrong copy."); 335 check(fem[it] == tem[er[it]], "Wrong copy."); 336 check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]), 337 "Wrong copy."); 338 check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]), 339 "Wrong copy."); 340 check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])), 341 "Wrong copy."); 342 } 343 344 for (typename GR::NodeIt it(to); it != INVALID; ++it) { 345 check(nr[ncr[it]] == it, "Wrong copy."); 346 } 347 for (typename GR::RedNodeIt it(to); it != INVALID; ++it) { 348 check(rncr[it] == ncr[it], "Wrong copy."); 349 check(rnr[rncr[it]] == it, "Wrong copy."); 350 } 351 for (typename GR::BlueNodeIt it(to); it != INVALID; ++it) { 352 check(bncr[it] == ncr[it], "Wrong copy."); 353 check(bnr[bncr[it]] == it, "Wrong copy."); 354 } 355 for (typename GR::ArcIt it(to); it != INVALID; ++it) { 356 check(ar[acr[it]] == it, "Wrong copy."); 357 } 358 for (typename GR::EdgeIt it(to); it != INVALID; ++it) { 359 check(er[ecr[it]] == it, "Wrong copy."); 360 } 361 check(tn == nr[fn], "Wrong copy."); 362 check(trn == rnr[frn], "Wrong copy."); 363 check(tbn == bnr[fbn], "Wrong copy."); 364 check(ta == ar[fa], "Wrong copy."); 365 check(te == er[fe], "Wrong copy."); 366 367 // Test repeated copy 368 bpGraphCopy(from, to).run(); 369 370 check(countNodes(from) == countNodes(to), "Wrong copy."); 371 check(countRedNodes(from) == countRedNodes(to), "Wrong copy."); 372 check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy."); 373 check(countEdges(from) == countEdges(to), "Wrong copy."); 374 check(countArcs(from) == countArcs(to), "Wrong copy."); 375 } 376 212 377 213 378 int main() { … … 217 382 graph_copy_test<SmartGraph>(); 218 383 graph_copy_test<ListGraph>(); 384 bpgraph_copy_test<SmartBpGraph>(); 385 bpgraph_copy_test<ListBpGraph>(); 219 386 220 387 return 0; -
test/graph_test.h
r440 r1027 42 42 43 43 template<class Graph> 44 void checkGraphRedNodeList(const Graph &G, int cnt) 45 { 46 typename Graph::RedNodeIt n(G); 47 for(int i=0;i<cnt;i++) { 48 check(n!=INVALID,"Wrong red Node list linking."); 49 check(G.red(n),"Wrong node set check."); 50 check(!G.blue(n),"Wrong node set check."); 51 typename Graph::Node nn = n; 52 check(G.asRedNodeUnsafe(nn) == n,"Wrong node conversion."); 53 check(G.asRedNode(nn) == n,"Wrong node conversion."); 54 check(G.asBlueNode(nn) == INVALID,"Wrong node conversion."); 55 ++n; 56 } 57 check(n==INVALID,"Wrong red Node list linking."); 58 check(countRedNodes(G)==cnt,"Wrong red Node number."); 59 } 60 61 template<class Graph> 62 void checkGraphBlueNodeList(const Graph &G, int cnt) 63 { 64 typename Graph::BlueNodeIt n(G); 65 for(int i=0;i<cnt;i++) { 66 check(n!=INVALID,"Wrong blue Node list linking."); 67 check(G.blue(n),"Wrong node set check."); 68 check(!G.red(n),"Wrong node set check."); 69 typename Graph::Node nn = n; 70 check(G.asBlueNodeUnsafe(nn) == n,"Wrong node conversion."); 71 check(G.asBlueNode(nn) == n,"Wrong node conversion."); 72 check(G.asRedNode(nn) == INVALID,"Wrong node conversion."); 73 ++n; 74 } 75 check(n==INVALID,"Wrong blue Node list linking."); 76 check(countBlueNodes(G)==cnt,"Wrong blue Node number."); 77 } 78 79 template<class Graph> 44 80 void checkGraphArcList(const Graph &G, int cnt) 45 81 { … … 167 203 template <typename Graph> 168 204 void checkNodeIds(const Graph& G) { 205 typedef typename Graph::Node Node; 169 206 std::set<int> values; 170 207 for (typename Graph::NodeIt n(G); n != INVALID; ++n) { … … 174 211 values.insert(G.id(n)); 175 212 } 213 check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id"); 214 } 215 216 template <typename Graph> 217 void checkRedNodeIds(const Graph& G) { 218 typedef typename Graph::RedNode RedNode; 219 std::set<int> values; 220 for (typename Graph::RedNodeIt n(G); n != INVALID; ++n) { 221 check(G.red(n), "Wrong partition"); 222 check(values.find(G.id(n)) == values.end(), "Wrong id"); 223 check(G.id(n) <= G.maxRedId(), "Wrong maximum id"); 224 values.insert(G.id(n)); 225 } 226 check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id"); 227 } 228 229 template <typename Graph> 230 void checkBlueNodeIds(const Graph& G) { 231 typedef typename Graph::BlueNode BlueNode; 232 std::set<int> values; 233 for (typename Graph::BlueNodeIt n(G); n != INVALID; ++n) { 234 check(G.blue(n), "Wrong partition"); 235 check(values.find(G.id(n)) == values.end(), "Wrong id"); 236 check(G.id(n) <= G.maxBlueId(), "Wrong maximum id"); 237 values.insert(G.id(n)); 238 } 239 check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id"); 176 240 } 177 241 178 242 template <typename Graph> 179 243 void checkArcIds(const Graph& G) { 244 typedef typename Graph::Arc Arc; 180 245 std::set<int> values; 181 246 for (typename Graph::ArcIt a(G); a != INVALID; ++a) { … … 185 250 values.insert(G.id(a)); 186 251 } 252 check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id"); 187 253 } 188 254 189 255 template <typename Graph> 190 256 void checkEdgeIds(const Graph& G) { 257 typedef typename Graph::Edge Edge; 191 258 std::set<int> values; 192 259 for (typename Graph::EdgeIt e(G); e != INVALID; ++e) { … … 196 263 values.insert(G.id(e)); 197 264 } 265 check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id"); 198 266 } 199 267 … … 229 297 230 298 template <typename Graph> 299 void checkGraphRedNodeMap(const Graph& G) { 300 typedef typename Graph::Node Node; 301 typedef typename Graph::RedNodeIt RedNodeIt; 302 303 typedef typename Graph::template RedNodeMap<int> IntRedNodeMap; 304 IntRedNodeMap map(G, 42); 305 for (RedNodeIt it(G); it != INVALID; ++it) { 306 check(map[it] == 42, "Wrong map constructor."); 307 } 308 int s = 0; 309 for (RedNodeIt it(G); it != INVALID; ++it) { 310 map[it] = 0; 311 check(map[it] == 0, "Wrong operator[]."); 312 map.set(it, s); 313 check(map[it] == s, "Wrong set."); 314 ++s; 315 } 316 s = s * (s - 1) / 2; 317 for (RedNodeIt it(G); it != INVALID; ++it) { 318 s -= map[it]; 319 } 320 check(s == 0, "Wrong sum."); 321 322 // map = constMap<Node>(12); 323 // for (NodeIt it(G); it != INVALID; ++it) { 324 // check(map[it] == 12, "Wrong operator[]."); 325 // } 326 } 327 328 template <typename Graph> 329 void checkGraphBlueNodeMap(const Graph& G) { 330 typedef typename Graph::Node Node; 331 typedef typename Graph::BlueNodeIt BlueNodeIt; 332 333 typedef typename Graph::template BlueNodeMap<int> IntBlueNodeMap; 334 IntBlueNodeMap map(G, 42); 335 for (BlueNodeIt it(G); it != INVALID; ++it) { 336 check(map[it] == 42, "Wrong map constructor."); 337 } 338 int s = 0; 339 for (BlueNodeIt it(G); it != INVALID; ++it) { 340 map[it] = 0; 341 check(map[it] == 0, "Wrong operator[]."); 342 map.set(it, s); 343 check(map[it] == s, "Wrong set."); 344 ++s; 345 } 346 s = s * (s - 1) / 2; 347 for (BlueNodeIt it(G); it != INVALID; ++it) { 348 s -= map[it]; 349 } 350 check(s == 0, "Wrong sum."); 351 352 // map = constMap<Node>(12); 353 // for (NodeIt it(G); it != INVALID; ++it) { 354 // check(map[it] == 12, "Wrong operator[]."); 355 // } 356 } 357 358 template <typename Graph> 231 359 void checkGraphArcMap(const Graph& G) { 232 360 typedef typename Graph::Arc Arc; -
test/min_mean_cycle_test.cc
r877 r1012 111 111 int cost, int size) { 112 112 MMC alg(gr, lm); 113 alg.findCycleMean();113 check(alg.findCycleMean(), "Wrong result"); 114 114 check(alg.cycleMean() == static_cast<double>(cost) / size, 115 115 "Wrong cycle mean"); … … 211 211 checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1); 212 212 checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1); 213 214 // Howard with iteration limit 215 HowardMmc<GR, IntArcMap> mmc(gr, l1); 216 check((mmc.findCycleMean(2) == HowardMmc<GR, IntArcMap>::ITERATION_LIMIT), 217 "Wrong termination cause"); 218 check((mmc.findCycleMean(4) == HowardMmc<GR, IntArcMap>::OPTIMAL), 219 "Wrong termination cause"); 213 220 } 214 221
Note: See TracChangeset
for help on using the changeset viewer.