COIN-OR::LEMON - Graph Library

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


Ignore:
Files:
10 added
21 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r1000 r1017  
    9292SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
    9393
    94 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
     94IF(MSVC)
     95  SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
    9596    "Flags used by the C++ compiler during maintainer builds."
    96     FORCE )
    97 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
     97    )
     98  SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
    9899    "Flags used by the C compiler during maintainer builds."
    99     FORCE )
    100 SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     100    )
     101  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     102    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     103    "Flags used for linking binaries during maintainer builds."
     104    )
     105  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     106    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     107    "Flags used by the shared libraries linker during maintainer builds."
     108    )
     109ELSE()
     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
    101117    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    102118    "Flags used for linking binaries during maintainer builds."
    103     FORCE )
    104 SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     119    )
     120  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
    105121    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    106122    "Flags used by the shared libraries linker during maintainer builds."
    107     FORCE )
     123    )
     124ENDIF()
     125
    108126MARK_AS_ADVANCED(
    109127    CMAKE_CXX_FLAGS_MAINTAINER
  • doc/CMakeLists.txt

    r1040 r1041  
    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
    5152    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    5253    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
  • doc/groups.dox

    r1003 r1038  
    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
     567This group contains basic heuristic algorithms for the the symmetric
     568\e traveling \e salesman \e problem (TSP).
     569Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     570the problem is to find a shortest possible tour that visits each node exactly
     571once (i.e. the minimum cost Hamiltonian cycle).
     572
     573These 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.
     575Otherwise the algorithms could yield worse results.
     576
     577LEMON 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
     585solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     586
     587\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     588approximation factor: 3/2.
     589
     590\ref Opt2Tsp usually provides the best results in practice, but
     591it is the slowest method. It can also be used to improve given tours,
     592for example, the results of other algorithms.
     593
     594\image html tsp.png
     595\image latex tsp.eps "Traveling salesman problem" width=\textwidth
     596*/
    561597
    562598/**
  • doc/lgf.dox

    r950 r1024  
    6464\endcode
    6565
    66 The \c \@arcs section is very similar to the \c \@nodes section, it
    67 again starts with a header line describing the names of the maps, but
    68 the \c "label" map is not obligatory here. The following lines
    69 describe the arcs. The first two tokens of each line are the source
    70 and the target node of the arc, respectively, then come the map
     66The \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
     68graph. If a map is in both of these sections, then it can be used as a
     69regular 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
     83The \c \@arcs section is very similar to the \c \@nodes section,
     84it again starts with a header line describing the names of the maps,
     85but the \c "label" map is not obligatory here. The following lines
     86describe the arcs. The first two tokens of each line are
     87the source and the target node of the arc, respectively, then come the map
    7188values. The source and target tokens must be node labels.
    7289
  • lemon/bits/graph_extender.h

    r998 r1027  
    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
    7491330}
    7501331
  • lemon/bits/traits.h

    r616 r1026  
    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     };
    151233
    152234  };
  • lemon/concepts/graph.h

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

    r1010 r1028  
    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
    302468    /// \brief Skeleton class for \e idable directed graphs.
    303469    ///
     
    429595        const _Graph& graph;
    430596        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;
    431661      };
    432662    };
     
    9051135    };
    9061136
     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
    9071228    /// \brief Skeleton class for alterable directed graphs.
    9081229    ///
     
    9301251      ArcNotifier;
    9311252
     1253      mutable NodeNotifier node_notifier;
     1254      mutable ArcNotifier arc_notifier;
     1255
    9321256      /// \brief Return the node alteration notifier.
    9331257      ///
    9341258      /// This function gives back the node alteration notifier.
    9351259      NodeNotifier& notifier(Node) const {
    936          return NodeNotifier();
     1260        return node_notifier;
    9371261      }
    9381262
     
    9411265      /// This function gives back the arc alteration notifier.
    9421266      ArcNotifier& notifier(Arc) const {
    943         return ArcNotifier();
     1267        return arc_notifier;
    9441268      }
    9451269
     
    9771301
    9781302      typedef BAS Base;
     1303      typedef AlterableDigraphComponent<Base> Parent;
    9791304      typedef typename Base::Edge Edge;
    9801305
     
    9841309      EdgeNotifier;
    9851310
     1311      mutable EdgeNotifier edge_notifier;
     1312
     1313      using Parent::notifier;
     1314
    9861315      /// \brief Return the edge alteration notifier.
    9871316      ///
    9881317      /// This function gives back the edge alteration notifier.
    9891318      EdgeNotifier& notifier(Edge) const {
    990         return EdgeNotifier();
     1319        return edge_notifier;
    9911320      }
    9921321
     
    10021331        const _Graph& graph;
    10031332        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;
    10041395      };
    10051396    };
     
    13081699    };
    13091700
     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
    13101845    /// \brief Skeleton class for extendable directed graphs.
    13111846    ///
     
    13981933    };
    13991934
     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
    14001994    /// \brief Skeleton class for erasable directed graphs.
    14011995    ///
     
    14782072    };
    14792073
     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
    14802083    /// \brief Skeleton class for clearable directed graphs.
    14812084    ///
     
    15142117    /// This concept requires \ref AlterableGraphComponent.
    15152118    template <typename BAS = BaseGraphComponent>
    1516     class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
    1517     public:
    1518 
    1519       typedef BAS Base;
    1520 
    1521       /// \brief Erase all nodes and edges from the graph.
    1522       ///
    1523       /// This function erases all nodes and edges from the graph.
    1524       void clear() {}
    1525 
    1526       template <typename _Graph>
    1527       struct Constraints {
    1528         void constraints() {
    1529           checkConcept<Base, _Graph>();
    1530           graph.clear();
    1531         }
    1532 
    1533         _Graph& graph;
    1534         Constraints() {}
    1535       };
    1536     };
     2119    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
     2120
     2121    /// \brief Skeleton class for clearable undirected biparite graphs.
     2122    ///
     2123    /// This class describes the interface of clearable undirected
     2124    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
     2125    /// function for clearing the graph.  This concept requires \ref
     2126    /// AlterableBpGraphComponent.
     2127    template <typename BAS = BaseBpGraphComponent>
     2128    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
    15372129
    15382130  }
  • lemon/core.h

    r1000 r1027  
    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
    151194  /// \brief Function to count the items in a graph.
    152195  ///
     
    200243  }
    201244
     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
    202313  // Arc counting:
    203314
     
    441552      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    442553      static void copy(const From& from, Graph &to,
    443                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     554                       NodeRefMap& nodeRefMap,
     555                       EdgeRefMap& edgeRefMap) {
    444556        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);
    445594      }
    446595    };
     
    9901139  graphCopy(const From& from, To& to) {
    9911140    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);
    9921589  }
    9931590
     
    12581855    /// The Digraph type
    12591856    typedef GR Digraph;
    1260 
     1857   
    12611858  protected:
    12621859
  • lemon/cplex.cc

    r989 r1016  
    4141    int status;
    4242    _cnt = new int;
     43    (*_cnt) = 1;
    4344    _env = CPXopenCPLEX(&status);
    4445    if (_env == 0) {
  • lemon/cycle_canceling.h

    r1003 r1013  
    3636#include <lemon/bellman_ford.h>
    3737#include <lemon/howard_mmc.h>
     38#include <lemon/hartmann_orlin_mmc.h>
    3839
    3940namespace lemon {
     
    928929    // Execute the "Minimum Mean Cycle Canceling" method
    929930    void startMinMeanCycleCanceling() {
    930       typedef SimplePath<StaticDigraph> SPath;
     931      typedef Path<StaticDigraph> SPath;
    931932      typedef typename SPath::ArcIt SPathArcIt;
    932933      typedef typename HowardMmc<StaticDigraph, CostArcMap>
    933         ::template SetPath<SPath>::Create MMC;
     934        ::template SetPath<SPath>::Create HwMmc;
     935      typedef typename HartmannOrlinMmc<StaticDigraph, CostArcMap>
     936        ::template SetPath<SPath>::Create HoMmc;
     937
     938      const double HW_ITER_LIMIT_FACTOR = 1.0;
     939      const int HW_ITER_LIMIT_MIN_VALUE = 5;
     940
     941      const int hw_iter_limit =
     942          std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num),
     943                   HW_ITER_LIMIT_MIN_VALUE);
    934944
    935945      SPath cycle;
    936       MMC mmc(_sgr, _cost_map);
    937       mmc.cycle(cycle);
     946      HwMmc hw_mmc(_sgr, _cost_map);
     947      hw_mmc.cycle(cycle);
    938948      buildResidualNetwork();
    939       while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
    940         // Find the cycle
    941         mmc.findCycle();
    942 
     949      while (true) {
     950       
     951        typename HwMmc::TerminationCause hw_tc =
     952            hw_mmc.findCycleMean(hw_iter_limit);
     953        if (hw_tc == HwMmc::ITERATION_LIMIT) {
     954          // Howard's algorithm reached the iteration limit, start a
     955          // strongly polynomial algorithm instead
     956          HoMmc ho_mmc(_sgr, _cost_map);
     957          ho_mmc.cycle(cycle);
     958          // Find a minimum mean cycle (Hartmann-Orlin algorithm)
     959          if (!(ho_mmc.findCycleMean() && ho_mmc.cycleCost() < 0)) break;
     960          ho_mmc.findCycle();
     961        } else {
     962          // Find a minimum mean cycle (Howard algorithm)
     963          if (!(hw_tc == HwMmc::OPTIMAL && hw_mmc.cycleCost() < 0)) break;
     964          hw_mmc.findCycle();
     965        }
     966       
    943967        // Compute delta value
    944968        Value delta = INF;
     
    965989      const double LIMIT_FACTOR = 1.0;
    966990      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);
    967997
    968998      // Contruct auxiliary data vectors
     
    11381168          }
    11391169        } else {
    1140           typedef HowardMmc<StaticDigraph, CostArcMap> MMC;
     1170          typedef HowardMmc<StaticDigraph, CostArcMap> HwMmc;
     1171          typedef HartmannOrlinMmc<StaticDigraph, CostArcMap> HoMmc;
    11411172          typedef typename BellmanFord<StaticDigraph, CostArcMap>
    11421173            ::template SetDistMap<CostNodeMap>::Create BF;
    11431174
    11441175          // Set epsilon to the minimum cycle mean
     1176          Cost cycle_cost = 0;
     1177          int cycle_size = 1;
    11451178          buildResidualNetwork();
    1146           MMC mmc(_sgr, _cost_map);
    1147           mmc.findCycleMean();
    1148           epsilon = -mmc.cycleMean();
    1149           Cost cycle_cost = mmc.cycleCost();
    1150           int cycle_size = mmc.cycleSize();
     1179          HwMmc hw_mmc(_sgr, _cost_map);
     1180          if (hw_mmc.findCycleMean(hw_iter_limit) == HwMmc::ITERATION_LIMIT) {
     1181            // Howard's algorithm reached the iteration limit, start a
     1182            // strongly polynomial algorithm instead
     1183            HoMmc ho_mmc(_sgr, _cost_map);
     1184            ho_mmc.findCycleMean();
     1185            epsilon = -ho_mmc.cycleMean();
     1186            cycle_cost = ho_mmc.cycleCost();
     1187            cycle_size = ho_mmc.cycleSize();
     1188          } else {
     1189            // Set epsilon
     1190            epsilon = -hw_mmc.cycleMean();
     1191            cycle_cost = hw_mmc.cycleCost();
     1192            cycle_size = hw_mmc.cycleSize();
     1193          }
    11511194
    11521195          // Compute feasible potentials for the current epsilon
  • lemon/full_graph.h

    r877 r1025  
    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
    6241078
    6251079} //namespace lemon
  • lemon/howard_mmc.h

    r1002 r1012  
    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
    152169  private:
    153170
     
    325342    }
    326343
    327     /// \brief Find the minimum cycle mean.
     344    /// \brief Find the minimum cycle mean (or an upper bound).
    328345    ///
    329346    /// This function finds the minimum mean cost of the directed
    330     /// cycles in the digraph.
    331     ///
    332     /// \return \c true if a directed cycle exists in the digraph.
    333     bool findCycleMean() {
     347    /// cycles in the digraph (or an upper bound for it).
     348    ///
     349    /// By default, the function finds the exact minimum cycle mean,
     350    /// but an optional limit can also be specified for the number of
     351    /// iterations performed during the search process.
     352    /// The return value indicates if the optimal solution is found
     353    /// or the iteration limit is reached. In the latter case, an
     354    /// approximate solution is provided, which corresponds to a directed
     355    /// cycle whose mean cost is relatively small, but not necessarily
     356    /// minimal.
     357    ///
     358    /// \param limit  The maximum allowed number of iterations during
     359    /// the search process. Its default value implies that the algorithm
     360    /// runs until it finds the exact optimal solution.
     361    ///
     362    /// \return The termination cause of the search process.
     363    /// For more information, see \ref TerminationCause.
     364    TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max()) {
    334365      // Initialize and find strongly connected components
    335366      init();
     
    337368
    338369      // Find the minimum cycle mean in the components
     370      int iter_count = 0;
     371      bool iter_limit_reached = false;
    339372      for (int comp = 0; comp < _comp_num; ++comp) {
    340373        // Find the minimum mean cycle in the current component
    341374        if (!buildPolicyGraph(comp)) continue;
    342375        while (true) {
     376          if (++iter_count > limit) {
     377            iter_limit_reached = true;
     378            break;
     379          }
    343380          findPolicyCycle();
    344381          if (!computeNodeDistances()) break;
    345382        }
     383
    346384        // Update the best cycle (global minimum mean cycle)
    347385        if ( _curr_found && (!_best_found ||
     
    352390          _best_node = _curr_node;
    353391        }
    354       }
    355       return _best_found;
     392       
     393        if (iter_limit_reached) break;
     394      }
     395
     396      if (iter_limit_reached) {
     397        return ITERATION_LIMIT;
     398      } else {
     399        return _best_found ? OPTIMAL : NO_CYCLE;
     400      }
    356401    }
    357402
  • lemon/lgf_reader.h

    r966 r1030  
    155155    };
    156156
    157     template <typename Value>
     157    template <typename Value,
     158              typename Map = std::map<std::string, Value> >
    158159    struct MapLookUpConverter {
    159       const std::map<std::string, Value>& _map;
    160 
    161       MapLookUpConverter(const std::map<std::string, Value>& map)
     160      const Map& _map;
     161
     162      MapLookUpConverter(const Map& map)
    162163        : _map(map) {}
    163164
    164165      Value operator()(const std::string& str) {
    165         typename std::map<std::string, Value>::const_iterator it =
    166           _map.find(str);
     166        typename Map::const_iterator it = _map.find(str);
    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        }
    173206      }
    174207    };
     
    21292162  }
    21302163
     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
    21313230  class SectionReader;
    21323231
  • lemon/lgf_writer.h

    r877 r1030  
    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>
     194    template <typename Value,
     195              typename Map = std::map<Value, std::string> >
    195196    struct MapLookUpConverter {
    196       const std::map<Value, std::string>& _map;
    197 
    198       MapLookUpConverter(const std::map<Value, std::string>& map)
     197      const Map& _map;
     198
     199      MapLookUpConverter(const Map& map)
    199200        : _map(map) {}
    200201
    201       std::string operator()(const Value& str) {
    202         typename std::map<Value, std::string>::const_iterator it =
    203           _map.find(str);
     202      std::string operator()(const Value& value) {
     203        typename Map::const_iterator it = _map.find(value);
    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        }
    208237      }
    209238    };
     
    9871016  /// \ingroup lemon_io
    9881017  ///
    989   /// \brief \ref lgf-format "LGF" writer for directed graphs
     1018  /// \brief \ref lgf-format "LGF" writer for undirected graphs
    9901019  ///
    9911020  /// This utility writes an \ref lgf-format "LGF" file.
     
    10431072    /// \brief Constructor
    10441073    ///
    1045     /// Construct a directed graph writer, which writes to the given
    1046     /// output stream.
     1074    /// Construct an undirected graph writer, which writes to the
     1075    /// given output stream.
    10471076    GraphWriter(const GR& graph, std::ostream& os = std::cout)
    10481077      : _os(&os), local_os(false), _graph(graph),
     
    10511080    /// \brief Constructor
    10521081    ///
    1053     /// Construct a directed graph writer, which writes to the given
     1082    /// Construct a undirected graph writer, which writes to the given
    10541083    /// output file.
    10551084    GraphWriter(const GR& graph, const std::string& fn)
     
    10641093    /// \brief Constructor
    10651094    ///
    1066     /// Construct a directed graph writer, which writes to the given
     1095    /// Construct a undirected graph writer, which writes to the given
    10671096    /// output file.
    10681097    GraphWriter(const GR& graph, const char* fn)
     
    12901319    }
    12911320
    1292     /// \brief Add an additional caption to the \c \@arcs section
    1293     ///
    1294     /// Add an additional caption to the \c \@arcs section.
     1321    /// \brief Add an additional caption to the \c \@edges section
     1322    ///
     1323    /// Add an additional caption to the \c \@edges section.
    12951324    GraphWriter& edges(const std::string& caption) {
    12961325      _edges_caption = caption;
     
    16061635  GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn) {
    16071636    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);
    16082455    return tmp;
    16092456  }
  • lemon/list_graph.h

    r877 r1025  
    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  /// @}
    16022507} //namespace lemon
    16032508
  • lemon/smart_graph.h

    r877 r1025  
    406406    std::vector<ArcT> arcs;
    407407
    408     int first_free_arc;
    409 
    410408  public:
    411409
     
    812810  };
    813811
     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
    8141341} //namespace lemon
    8151342
  • test/CMakeLists.txt

    r1000 r1038  
    1717  bellman_ford_test
    1818  bfs_test
     19  bpgraph_test
    1920  circulation_test
    2021  connectivity_test
     
    3536  heap_test
    3637  kruskal_test
     38  lgf_reader_writer_test
    3739  lgf_test
    3840  maps_test
     
    5153  suurballe_test
    5254  time_measure_test
     55  tsp_test
    5356  unionfind_test
    5457)
  • test/graph_copy_test.cc

    r894 r1026  
    210210}
    211211
     212template <typename GR>
     213void 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
    212377
    213378int main() {
     
    217382  graph_copy_test<SmartGraph>();
    218383  graph_copy_test<ListGraph>();
     384  bpgraph_copy_test<SmartBpGraph>();
     385  bpgraph_copy_test<ListBpGraph>();
    219386
    220387  return 0;
  • test/graph_test.h

    r440 r1027  
    4242
    4343  template<class Graph>
     44  void checkGraphRedNodeList(const Graph &G, int cnt)
     45  {
     46    typename Graph::RedNodeIt n(G);
     47    for(int i=0;i<cnt;i++) {
     48      check(n!=INVALID,"Wrong red Node list linking.");
     49      check(G.red(n),"Wrong node set check.");
     50      check(!G.blue(n),"Wrong node set check.");
     51      typename Graph::Node nn = n;
     52      check(G.asRedNodeUnsafe(nn) == n,"Wrong node conversion.");
     53      check(G.asRedNode(nn) == n,"Wrong node conversion.");
     54      check(G.asBlueNode(nn) == INVALID,"Wrong node conversion.");
     55      ++n;
     56    }
     57    check(n==INVALID,"Wrong red Node list linking.");
     58    check(countRedNodes(G)==cnt,"Wrong red Node number.");
     59  }
     60
     61  template<class Graph>
     62  void checkGraphBlueNodeList(const Graph &G, int cnt)
     63  {
     64    typename Graph::BlueNodeIt n(G);
     65    for(int i=0;i<cnt;i++) {
     66      check(n!=INVALID,"Wrong blue Node list linking.");
     67      check(G.blue(n),"Wrong node set check.");
     68      check(!G.red(n),"Wrong node set check.");
     69      typename Graph::Node nn = n;
     70      check(G.asBlueNodeUnsafe(nn) == n,"Wrong node conversion.");
     71      check(G.asBlueNode(nn) == n,"Wrong node conversion.");
     72      check(G.asRedNode(nn) == INVALID,"Wrong node conversion.");
     73      ++n;
     74    }
     75    check(n==INVALID,"Wrong blue Node list linking.");
     76    check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
     77  }
     78
     79  template<class Graph>
    4480  void checkGraphArcList(const Graph &G, int cnt)
    4581  {
     
    167203  template <typename Graph>
    168204  void checkNodeIds(const Graph& G) {
     205    typedef typename Graph::Node Node;
    169206    std::set<int> values;
    170207    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
     
    174211      values.insert(G.id(n));
    175212    }
     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");
    176240  }
    177241
    178242  template <typename Graph>
    179243  void checkArcIds(const Graph& G) {
     244    typedef typename Graph::Arc Arc;
    180245    std::set<int> values;
    181246    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
     
    185250      values.insert(G.id(a));
    186251    }
     252    check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id");
    187253  }
    188254
    189255  template <typename Graph>
    190256  void checkEdgeIds(const Graph& G) {
     257    typedef typename Graph::Edge Edge;
    191258    std::set<int> values;
    192259    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
     
    196263      values.insert(G.id(e));
    197264    }
     265    check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id");
    198266  }
    199267
     
    229297
    230298  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>
    231359  void checkGraphArcMap(const Graph& G) {
    232360    typedef typename Graph::Arc Arc;
  • test/min_mean_cycle_test.cc

    r877 r1012  
    111111                 int cost, int size) {
    112112  MMC alg(gr, lm);
    113   alg.findCycleMean();
     113  check(alg.findCycleMean(), "Wrong result");
    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");
    213220  }
    214221
Note: See TracChangeset for help on using the changeset viewer.