COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [1041:0b0327c9b3ef:1040:60c0c3ed8d11] in lemon-main


Ignore:
Files:
10 deleted
21 edited

Legend:

Unmodified
Added
Removed

  • CMakeLists.txt

    r1017 r1000  
    9292SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
    9393
    94 IF(MSVC)
    95   SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     94SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
    9695    "Flags used by the C++ compiler during maintainer builds."
    97     )
    98   SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     96    FORCE )
     97SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
    9998    "Flags used by the C compiler during maintainer builds."
    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
     99    FORCE )
     100SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
    117101    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    118102    "Flags used for linking binaries during maintainer builds."
    119     )
    120   SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     103    FORCE )
     104SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
    121105    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    122106    "Flags used by the shared libraries linker during maintainer builds."
    123     )
    124 ENDIF()
    125 
     107    FORCE )
    126108MARK_AS_ADVANCED(
    127109    CMAKE_CXX_FLAGS_MAINTAINER

  • doc/CMakeLists.txt

    r1041 r1040  
    4949    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    5050    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
    5251    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    5352    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox

  • doc/groups.dox

    r1038 r1003  
    559559\image latex planar.eps "Plane graph" width=\textwidth
    560560*/
    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 */
    597561
    598562/**

  • doc/lgf.dox

    r1024 r950  
    6464\endcode
    6565
    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
     66The \c \@arcs section is very similar to the \c \@nodes section, it
     67again starts with a header line describing the names of the maps, but
     68the \c "label" map is not obligatory here. The following lines
     69describe the arcs. The first two tokens of each line are the source
     70and the target node of the arc, respectively, then come the map
    8871values. The source and target tokens must be node labels.
    8972

  • lemon/bits/graph_extender.h

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

  • lemon/bits/traits.h

    r1026 r616  
    149149        : Parent(_digraph, _value) {}
    150150    };
    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      };
    233151
    234152  };

  • lemon/concepts/graph.h

    r1018 r877  
    7373    class Graph {
    7474    private:
    75       /// Graphs are \e not copy constructible. Use GraphCopy instead.
     75      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
    7676      Graph(const Graph&) {}
    7777      /// \brief Assignment of a graph to another one is \e not allowed.
    78       /// Use GraphCopy instead.
     78      /// Use DigraphCopy instead.
    7979      void operator=(const Graph&) {}
    8080

  • lemon/concepts/graph_components.h

    r1028 r1010  
    300300    };
    301301
    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 
    468302    /// \brief Skeleton class for \e idable directed graphs.
    469303    ///
    … …  
    595429        const _Graph& graph;
    596430        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;
    661431      };
    662432    };
    … …  
    1135905    };
    1136906
    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 
    1228907    /// \brief Skeleton class for alterable directed graphs.
    1229908    ///
    … …  
    1251930      ArcNotifier;
    1252931
    1253       mutable NodeNotifier node_notifier;
    1254       mutable ArcNotifier arc_notifier;
    1255 
    1256932      /// \brief Return the node alteration notifier.
    1257933      ///
    1258934      /// This function gives back the node alteration notifier.
    1259935      NodeNotifier& notifier(Node) const {
    1260         return node_notifier;
     936         return NodeNotifier();
    1261937      }
    1262938
    … …  
    1265941      /// This function gives back the arc alteration notifier.
    1266942      ArcNotifier& notifier(Arc) const {
    1267         return arc_notifier;
     943        return ArcNotifier();
    1268944      }
    1269945
    … …  
    1301977
    1302978      typedef BAS Base;
    1303       typedef AlterableDigraphComponent<Base> Parent;
    1304979      typedef typename Base::Edge Edge;
    1305980
    … …  
    1309984      EdgeNotifier;
    1310985
    1311       mutable EdgeNotifier edge_notifier;
    1312 
    1313       using Parent::notifier;
    1314 
    1315986      /// \brief Return the edge alteration notifier.
    1316987      ///
    1317988      /// This function gives back the edge alteration notifier.
    1318989      EdgeNotifier& notifier(Edge) const {
    1319         return edge_notifier;
     990        return EdgeNotifier();
    1320991      }
    1321992
    … …  
    13311002        const _Graph& graph;
    13321003        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;
    13951004      };
    13961005    };
    … …  
    16991308    };
    17001309
    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 
    18451310    /// \brief Skeleton class for extendable directed graphs.
    18461311    ///
    … …  
    19331398    };
    19341399
    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 
    19941400    /// \brief Skeleton class for erasable directed graphs.
    19951401    ///
    … …  
    20721478    };
    20731479
    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 
    20831480    /// \brief Skeleton class for clearable directed graphs.
    20841481    ///
    … …  
    21171514    /// This concept requires \ref AlterableGraphComponent.
    21181515    template <typename BAS = BaseGraphComponent>
    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> {};
     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    };
    21291537
    21301538  }

  • lemon/core.h

    r1027 r1000  
    149149  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
    150150
    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 
    194151  /// \brief Function to count the items in a graph.
    195152  ///
    … …  
    243200  }
    244201
    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 
    313202  // Arc counting:
    314203
    … …  
    552441      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    553442      static void copy(const From& from, Graph &to,
    554                        NodeRefMap& nodeRefMap,
    555                        EdgeRefMap& edgeRefMap) {
     443                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    556444        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);
    594445      }
    595446    };
    … …  
    1139990  graphCopy(const From& from, To& to) {
    1140991    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);
    1589992  }
    1590993
    … …  
    18551258    /// The Digraph type
    18561259    typedef GR Digraph;
    1857    
     1260
    18581261  protected:
    18591262

  • lemon/cplex.cc

    r1016 r989  
    4141    int status;
    4242    _cnt = new int;
    43     (*_cnt) = 1;
    4443    _env = CPXopenCPLEX(&status);
    4544    if (_env == 0) {

  • lemon/cycle_canceling.h

    r1013 r1003  
    3636#include <lemon/bellman_ford.h>
    3737#include <lemon/howard_mmc.h>
    38 #include <lemon/hartmann_orlin_mmc.h>
    3938
    4039namespace lemon {
    … …  
    929928    // Execute the "Minimum Mean Cycle Canceling" method
    930929    void startMinMeanCycleCanceling() {
    931       typedef Path<StaticDigraph> SPath;
     930      typedef SimplePath<StaticDigraph> SPath;
    932931      typedef typename SPath::ArcIt SPathArcIt;
    933932      typedef typename HowardMmc<StaticDigraph, CostArcMap>
    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);
     933        ::template SetPath<SPath>::Create MMC;
    944934
    945935      SPath cycle;
    946       HwMmc hw_mmc(_sgr, _cost_map);
    947       hw_mmc.cycle(cycle);
     936      MMC mmc(_sgr, _cost_map);
     937      mmc.cycle(cycle);
    948938      buildResidualNetwork();
    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        
     939      while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
     940        // Find the cycle
     941        mmc.findCycle();
     942
    967943        // Compute delta value
    968944        Value delta = INF;
    … …  
    989965      const double LIMIT_FACTOR = 1.0;
    990966      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);
    997967
    998968      // Contruct auxiliary data vectors
    … …  
    11681138          }
    11691139        } else {
    1170           typedef HowardMmc<StaticDigraph, CostArcMap> HwMmc;
    1171           typedef HartmannOrlinMmc<StaticDigraph, CostArcMap> HoMmc;
     1140          typedef HowardMmc<StaticDigraph, CostArcMap> MMC;
    11721141          typedef typename BellmanFord<StaticDigraph, CostArcMap>
    11731142            ::template SetDistMap<CostNodeMap>::Create BF;
    11741143
    11751144          // Set epsilon to the minimum cycle mean
    1176           Cost cycle_cost = 0;
    1177           int cycle_size = 1;
    11781145          buildResidualNetwork();
    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           }
     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();
    11941151
    11951152          // Compute feasible potentials for the current epsilon

  • lemon/full_graph.h

    r1025 r877  
    622622  };
    623623
    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 
    1078624
    1079625} //namespace lemon

  • lemon/howard_mmc.h

    r1012 r1002  
    150150    typedef TR Traits;
    151151
    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 
    169152  private:
    170153
    … …  
    342325    }
    343326
    344     /// \brief Find the minimum cycle mean (or an upper bound).
     327    /// \brief Find the minimum cycle mean.
    345328    ///
    346329    /// This function finds the minimum mean cost of the directed
    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()) {
     330    /// cycles in the digraph.
     331    ///
     332    /// \return \c true if a directed cycle exists in the digraph.
     333    bool findCycleMean() {
    365334      // Initialize and find strongly connected components
    366335      init();
    … …  
    368337
    369338      // Find the minimum cycle mean in the components
    370       int iter_count = 0;
    371       bool iter_limit_reached = false;
    372339      for (int comp = 0; comp < _comp_num; ++comp) {
    373340        // Find the minimum mean cycle in the current component
    374341        if (!buildPolicyGraph(comp)) continue;
    375342        while (true) {
    376           if (++iter_count > limit) {
    377             iter_limit_reached = true;
    378             break;
    379           }
    380343          findPolicyCycle();
    381344          if (!computeNodeDistances()) break;
    382345        }
    383 
    384346        // Update the best cycle (global minimum mean cycle)
    385347        if ( _curr_found && (!_best_found ||
    … …  
    390352          _best_node = _curr_node;
    391353        }
    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       }
     354      }
     355      return _best_found;
    401356    }
    402357

  • lemon/lgf_reader.h

    r1030 r966  
    155155    };
    156156
    157     template <typename Value,
    158               typename Map = std::map<std::string, Value> >
     157    template <typename Value>
    159158    struct MapLookUpConverter {
    160       const Map& _map;
    161 
    162       MapLookUpConverter(const Map& map)
     159      const std::map<std::string, Value>& _map;
     160
     161      MapLookUpConverter(const std::map<std::string, Value>& map)
    163162        : _map(map) {}
    164163
    165164      Value operator()(const std::string& str) {
    166         typename Map::const_iterator it = _map.find(str);
     165        typename std::map<std::string, Value>::const_iterator it =
     166          _map.find(str);
    167167        if (it == _map.end()) {
    168168          std::ostringstream msg;
    … …  
    171171        }
    172172        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         }
    206173      }
    207174    };
    … …  
    21622129  }
    21632130
    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 
    32302131  class SectionReader;
    32312132

  • lemon/lgf_writer.h

    r1030 r877  
    186186      ValueStorage(const Value& value, const Converter& converter = Converter())
    187187        : _value(value), _converter(converter) {}
    188      
     188
    189189      virtual std::string get() {
    190190        return _converter(_value);
    … …  
    192192    };
    193193
    194     template <typename Value,
    195               typename Map = std::map<Value, std::string> >
     194    template <typename Value>
    196195    struct MapLookUpConverter {
    197       const Map& _map;
    198 
    199       MapLookUpConverter(const Map& map)
     196      const std::map<Value, std::string>& _map;
     197
     198      MapLookUpConverter(const std::map<Value, std::string>& map)
    200199        : _map(map) {}
    201200
    202       std::string operator()(const Value& value) {
    203         typename Map::const_iterator it = _map.find(value);
     201      std::string operator()(const Value& str) {
     202        typename std::map<Value, std::string>::const_iterator it =
     203          _map.find(str);
    204204        if (it == _map.end()) {
    205205          throw FormatError("Item not found");
    206206        }
    207207        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         }
    237208      }
    238209    };
    … …  
    1016987  /// \ingroup lemon_io
    1017988  ///
    1018   /// \brief \ref lgf-format "LGF" writer for undirected graphs
     989  /// \brief \ref lgf-format "LGF" writer for directed graphs
    1019990  ///
    1020991  /// This utility writes an \ref lgf-format "LGF" file.
    … …  
    10721043    /// \brief Constructor
    10731044    ///
    1074     /// Construct an undirected graph writer, which writes to the
    1075     /// given output stream.
     1045    /// Construct a directed graph writer, which writes to the given
     1046    /// output stream.
    10761047    GraphWriter(const GR& graph, std::ostream& os = std::cout)
    10771048      : _os(&os), local_os(false), _graph(graph),
    … …  
    10801051    /// \brief Constructor
    10811052    ///
    1082     /// Construct a undirected graph writer, which writes to the given
     1053    /// Construct a directed graph writer, which writes to the given
    10831054    /// output file.
    10841055    GraphWriter(const GR& graph, const std::string& fn)
    … …  
    10931064    /// \brief Constructor
    10941065    ///
    1095     /// Construct a undirected graph writer, which writes to the given
     1066    /// Construct a directed graph writer, which writes to the given
    10961067    /// output file.
    10971068    GraphWriter(const GR& graph, const char* fn)
    … …  
    13191290    }
    13201291
    1321     /// \brief Add an additional caption to the \c \@edges section
    1322     ///
    1323     /// Add an additional caption to the \c \@edges section.
     1292    /// \brief Add an additional caption to the \c \@arcs section
     1293    ///
     1294    /// Add an additional caption to the \c \@arcs section.
    13241295    GraphWriter& edges(const std::string& caption) {
    13251296      _edges_caption = caption;
    … …  
    16351606  GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn) {
    16361607    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);
    24551608    return tmp;
    24561609  }

  • lemon/list_graph.h

    r1025 r877  
    16001600
    16011601  /// @}
    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   /// @}
    25071602} //namespace lemon
    25081603

  • lemon/smart_graph.h

    r1025 r877  
    406406    std::vector<ArcT> arcs;
    407407
     408    int first_free_arc;
     409
    408410  public:
    409411
    … …  
    810812  };
    811813
    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 
    1341814} //namespace lemon
    1342815

  • test/CMakeLists.txt

    r1038 r1000  
    1717  bellman_ford_test
    1818  bfs_test
    19   bpgraph_test
    2019  circulation_test
    2120  connectivity_test
    … …  
    3635  heap_test
    3736  kruskal_test
    38   lgf_reader_writer_test
    3937  lgf_test
    4038  maps_test
    … …  
    5351  suurballe_test
    5452  time_measure_test
    55   tsp_test
    5653  unionfind_test
    5754)

  • test/graph_copy_test.cc

    r1026 r894  
    210210}
    211211
    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 
    377212
    378213int main() {
    … …  
    382217  graph_copy_test<SmartGraph>();
    383218  graph_copy_test<ListGraph>();
    384   bpgraph_copy_test<SmartBpGraph>();
    385   bpgraph_copy_test<ListBpGraph>();
    386219
    387220  return 0;

  • test/graph_test.h

    r1027 r440  
    3939    check(n==INVALID,"Wrong Node list linking.");
    4040    check(countNodes(G)==cnt,"Wrong Node number.");
    41   }
    42 
    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.");
    7741  }
    7842
    … …  
    203167  template <typename Graph>
    204168  void checkNodeIds(const Graph& G) {
    205     typedef typename Graph::Node Node;
    206169    std::set<int> values;
    207170    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
    … …  
    211174      values.insert(G.id(n));
    212175    }
    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");
    240176  }
    241177
    242178  template <typename Graph>
    243179  void checkArcIds(const Graph& G) {
    244     typedef typename Graph::Arc Arc;
    245180    std::set<int> values;
    246181    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
    … …  
    250185      values.insert(G.id(a));
    251186    }
    252     check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id");
    253187  }
    254188
    255189  template <typename Graph>
    256190  void checkEdgeIds(const Graph& G) {
    257     typedef typename Graph::Edge Edge;
    258191    std::set<int> values;
    259192    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
    … …  
    263196      values.insert(G.id(e));
    264197    }
    265     check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id");
    266198  }
    267199
    … …  
    297229
    298230  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>
    359231  void checkGraphArcMap(const Graph& G) {
    360232    typedef typename Graph::Arc Arc;

  • test/min_mean_cycle_test.cc

    r1012 r877  
    111111                 int cost, int size) {
    112112  MMC alg(gr, lm);
    113   check(alg.findCycleMean(), "Wrong result");
     113  alg.findCycleMean();
    114114  check(alg.cycleMean() == static_cast<double>(cost) / size,
    115115        "Wrong cycle mean");
    … …  
    211211    checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
    212212    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");
    220213  }
    221214
Note: See TracChangeset for help on using the changeset viewer.