COIN-OR::LEMON - Graph Library

Changeset 1019:4c89e925cfe2 in lemon-main


Ignore:
Timestamp:
11/14/10 20:06:23 (14 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

SmartBpGraph? implementation (#69)

Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

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

    r616 r1019  
    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::RedIt ItemIt;
     176
     177    typedef typename RedNodeNotifierIndicator<GR>::Type ItemNotifier;
     178
     179    template <typename V>
     180    class Map : public GR::template RedMap<V> {
     181      typedef typename GR::template RedMap<V> Parent;
     182
     183    public:
     184      typedef typename GR::template RedMap<V> Type;
     185      typedef typename Parent::Value Value;
     186
     187      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
     188      Map(const GR& _bpgraph, const Value& _value)
     189        : Parent(_bpgraph, _value) {}
     190
     191     };
     192
     193  };
     194
     195  template <typename GR, typename Enable = void>
     196  struct BlueNodeNotifierIndicator {
     197    typedef InvalidType Type;
     198  };
     199  template <typename GR>
     200  struct BlueNodeNotifierIndicator<
     201    GR,
     202    typename enable_if<typename GR::BlueNodeNotifier::Notifier, void>::type
     203  > {
     204    typedef typename GR::BlueNodeNotifier Type;
     205  };
     206
     207  template <typename GR>
     208  class ItemSetTraits<GR, typename GR::BlueNode> {
     209  public:
     210
     211    typedef GR BpGraph;
     212    typedef GR Graph;
     213    typedef GR Digraph;
     214
     215    typedef typename GR::BlueNode Item;
     216    typedef typename GR::BlueIt ItemIt;
     217
     218    typedef typename BlueNodeNotifierIndicator<GR>::Type ItemNotifier;
     219
     220    template <typename V>
     221    class Map : public GR::template BlueMap<V> {
     222      typedef typename GR::template BlueMap<V> Parent;
     223
     224    public:
     225      typedef typename GR::template BlueMap<V> Type;
     226      typedef typename Parent::Value Value;
     227
     228      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
     229      Map(const GR& _bpgraph, const Value& _value)
     230        : Parent(_bpgraph, _value) {}
     231
     232     };
    151233
    152234  };
  • lemon/core.h

    r1000 r1019  
    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 defined
     154  ///by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it creates
     155  ///\c RedNode, \c RedIt, \c BoolRedMap, \c IntRedMap, \c DoubleRedMap,
     156  ///\c BlueNode, \c BlueIt, \c BoolBlueMap, \c IntBlueMap, \c DoubleBlueMap.
     157  ///
     158  ///\note If the graph type is a dependent type, ie. the graph type depend
     159  ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
     160  ///macro.
     161#define BPGRAPH_TYPEDEFS(BpGraph)                                       \
     162  GRAPH_TYPEDEFS(BpGraph);                                              \
     163  typedef BpGraph::RedNode RedNode;                                     \
     164  typedef BpGraph::RedIt RedIt;                                         \
     165  typedef BpGraph::RedMap<bool> BoolRedMap;                             \
     166  typedef BpGraph::RedMap<int> IntRedMap;                               \
     167  typedef BpGraph::RedMap<double> DoubleRedMap                          \
     168  typedef BpGraph::BlueNode BlueNode;                                   \
     169  typedef BpGraph::BlueIt BlueIt;                                       \
     170  typedef BpGraph::BlueMap<bool> BoolBlueMap;                           \
     171  typedef BpGraph::BlueMap<int> IntBlueMap;                             \
     172  typedef BpGraph::BlueMap<double> DoubleBlueMap
     173
     174  ///Create convenience typedefs for the bipartite graph types and iterators
     175
     176  ///\see BPGRAPH_TYPEDEFS
     177  ///
     178  ///\note Use this macro, if the graph type is a dependent type,
     179  ///ie. the graph type depend on a template parameter.
     180#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)                              \
     181  TEMPLATE_GRAPH_TYPEDEFS(BpGraph);                                     \
     182  typedef typename BpGraph::RedNode RedNode;                            \
     183  typedef typename BpGraph::RedIt RedIt;                                \
     184  typedef typename BpGraph::template RedMap<bool> BoolRedMap;           \
     185  typedef typename BpGraph::template RedMap<int> IntRedMap;             \
     186  typedef typename BpGraph::template RedMap<double> DoubleRedMap;       \
     187  typedef typename BpGraph::BlueNode BlueNode;                          \
     188  typedef typename BpGraph::BlueIt BlueIt;                              \
     189  typedef typename BpGraph::template BlueMap<bool> BoolBlueMap;         \
     190  typedef typename BpGraph::template BlueMap<int> IntBlueMap;           \
     191  typedef typename BpGraph::template BlueMap<double> DoubleBlueMap
     192
    151193  /// \brief Function to count the items in a graph.
    152194  ///
     
    198240  inline int countNodes(const Graph& g) {
    199241    return _core_bits::CountNodesSelector<Graph>::count(g);
     242  }
     243
     244  namespace _graph_utils_bits {
     245   
     246    template <typename Graph, typename Enable = void>
     247    struct CountRedNodesSelector {
     248      static int count(const Graph &g) {
     249        return countItems<Graph, typename Graph::RedNode>(g);
     250      }
     251    };
     252
     253    template <typename Graph>
     254    struct CountRedNodesSelector<
     255      Graph, typename
     256      enable_if<typename Graph::NodeNumTag, void>::type>
     257    {
     258      static int count(const Graph &g) {
     259        return g.redNum();
     260      }
     261    };   
     262  }
     263
     264  /// \brief Function to count the red nodes in the graph.
     265  ///
     266  /// This function counts the red nodes in the graph.
     267  /// The complexity of the function is O(n) but for some
     268  /// graph structures it is specialized to run in O(1).
     269  ///
     270  /// If the graph contains a \e redNum() member function and a
     271  /// \e NodeNumTag tag then this function calls directly the member
     272  /// function to query the cardinality of the node set.
     273  template <typename Graph>
     274  inline int countRedNodes(const Graph& g) {
     275    return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
     276  }
     277
     278  namespace _graph_utils_bits {
     279   
     280    template <typename Graph, typename Enable = void>
     281    struct CountBlueNodesSelector {
     282      static int count(const Graph &g) {
     283        return countItems<Graph, typename Graph::BlueNode>(g);
     284      }
     285    };
     286
     287    template <typename Graph>
     288    struct CountBlueNodesSelector<
     289      Graph, typename
     290      enable_if<typename Graph::NodeNumTag, void>::type>
     291    {
     292      static int count(const Graph &g) {
     293        return g.blueNum();
     294      }
     295    };   
     296  }
     297
     298  /// \brief Function to count the blue nodes in the graph.
     299  ///
     300  /// This function counts the blue nodes in the graph.
     301  /// The complexity of the function is O(n) but for some
     302  /// graph structures it is specialized to run in O(1).
     303  ///
     304  /// If the graph contains a \e blueNum() member function and a
     305  /// \e NodeNumTag tag then this function calls directly the member
     306  /// function to query the cardinality of the node set.
     307  template <typename Graph>
     308  inline int countBlueNodes(const Graph& g) {
     309    return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
    200310  }
    201311
     
    12581368    /// The Digraph type
    12591369    typedef GR Digraph;
    1260 
     1370   
    12611371  protected:
    12621372
  • lemon/smart_graph.h

    r877 r1019  
    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
     833  public:
     834
     835    typedef SmartBpGraphBase Graph;
     836
     837    class Node;
     838    class Arc;
     839    class Edge;
     840
     841    class Node {
     842      friend class SmartBpGraphBase;
     843    protected:
     844
     845      int _id;
     846      explicit Node(int id) { _id = id;}
     847
     848    public:
     849      Node() {}
     850      Node (Invalid) { _id = -1; }
     851      bool operator==(const Node& node) const {return _id == node._id;}
     852      bool operator!=(const Node& node) const {return _id != node._id;}
     853      bool operator<(const Node& node) const {return _id < node._id;}
     854    };
     855
     856    class Edge {
     857      friend class SmartBpGraphBase;
     858    protected:
     859
     860      int _id;
     861      explicit Edge(int id) { _id = id;}
     862
     863    public:
     864      Edge() {}
     865      Edge (Invalid) { _id = -1; }
     866      bool operator==(const Edge& arc) const {return _id == arc._id;}
     867      bool operator!=(const Edge& arc) const {return _id != arc._id;}
     868      bool operator<(const Edge& arc) const {return _id < arc._id;}
     869    };
     870
     871    class Arc {
     872      friend class SmartBpGraphBase;
     873    protected:
     874
     875      int _id;
     876      explicit Arc(int id) { _id = id;}
     877
     878    public:
     879      operator Edge() const {
     880        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
     881      }
     882
     883      Arc() {}
     884      Arc (Invalid) { _id = -1; }
     885      bool operator==(const Arc& arc) const {return _id == arc._id;}
     886      bool operator!=(const Arc& arc) const {return _id != arc._id;}
     887      bool operator<(const Arc& arc) const {return _id < arc._id;}
     888    };
     889
     890
     891
     892    SmartBpGraphBase()
     893      : nodes(), arcs(), first_red(-1), first_blue(-1) {}
     894
     895    typedef True NodeNumTag;
     896    typedef True EdgeNumTag;
     897    typedef True ArcNumTag;
     898
     899    int nodeNum() const { return nodes.size(); }
     900    int redNum() const {
     901      return first_red == -1 ? 0 : nodes[first_red].partition_index + 1;
     902    }
     903    int blueNum() const {
     904      return first_blue == -1 ? 0 : nodes[first_blue].partition_index + 1;
     905    }
     906    int edgeNum() const { return arcs.size() / 2; }
     907    int arcNum() const { return arcs.size(); }
     908
     909    int maxNodeId() const { return nodes.size()-1; }
     910    int maxRedId() const {
     911      return first_red == -1 ? -1 : nodes[first_red].partition_index;
     912    }
     913    int maxBlueId() const {
     914      return first_blue == -1 ? -1 : nodes[first_blue].partition_index;
     915    }
     916    int maxEdgeId() const { return arcs.size() / 2 - 1; }
     917    int maxArcId() const { return arcs.size()-1; }
     918
     919    bool red(Node n) const { return nodes[n._id].red; }
     920    bool blue(Node n) const { return !nodes[n._id].red; }
     921
     922    Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
     923    Node target(Arc a) const { return Node(arcs[a._id].target); }
     924
     925    Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); }
     926    Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
     927
     928    Node u(Edge e) const { return redNode(e); }
     929    Node v(Edge e) const { return blueNode(e); }
     930
     931    static bool direction(Arc a) {
     932      return (a._id & 1) == 1;
     933    }
     934
     935    static Arc direct(Edge e, bool d) {
     936      return Arc(e._id * 2 + (d ? 1 : 0));
     937    }
     938
     939    void first(Node& node) const {
     940      node._id = nodes.size() - 1;
     941    }
     942
     943    static void next(Node& node) {
     944      --node._id;
     945    }
     946
     947    void firstRed(Node& node) const {
     948      node._id = first_red;
     949    }
     950
     951    void nextRed(Node& node) const {
     952      node._id = nodes[node._id].partition_next;
     953    }
     954
     955    void firstBlue(Node& node) const {
     956      node._id = first_blue;
     957    }
     958
     959    void nextBlue(Node& node) const {
     960      node._id = nodes[node._id].partition_next;
     961    }
     962
     963    void first(Arc& arc) const {
     964      arc._id = arcs.size() - 1;
     965    }
     966
     967    static void next(Arc& arc) {
     968      --arc._id;
     969    }
     970
     971    void first(Edge& arc) const {
     972      arc._id = arcs.size() / 2 - 1;
     973    }
     974
     975    static void next(Edge& arc) {
     976      --arc._id;
     977    }
     978
     979    void firstOut(Arc &arc, const Node& v) const {
     980      arc._id = nodes[v._id].first_out;
     981    }
     982    void nextOut(Arc &arc) const {
     983      arc._id = arcs[arc._id].next_out;
     984    }
     985
     986    void firstIn(Arc &arc, const Node& v) const {
     987      arc._id = ((nodes[v._id].first_out) ^ 1);
     988      if (arc._id == -2) arc._id = -1;
     989    }
     990    void nextIn(Arc &arc) const {
     991      arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);
     992      if (arc._id == -2) arc._id = -1;
     993    }
     994
     995    void firstInc(Edge &arc, bool& d, const Node& v) const {
     996      int de = nodes[v._id].first_out;
     997      if (de != -1) {
     998        arc._id = de / 2;
     999        d = ((de & 1) == 1);
     1000      } else {
     1001        arc._id = -1;
     1002        d = true;
     1003      }
     1004    }
     1005    void nextInc(Edge &arc, bool& d) const {
     1006      int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out);
     1007      if (de != -1) {
     1008        arc._id = de / 2;
     1009        d = ((de & 1) == 1);
     1010      } else {
     1011        arc._id = -1;
     1012        d = true;
     1013      }
     1014    }
     1015
     1016    static int id(Node v) { return v._id; }
     1017    int redId(Node v) const {
     1018      LEMON_DEBUG(nodes[v._id].red, "Node has to be red");
     1019      return nodes[v._id].partition_index;
     1020    }
     1021    int blueId(Node v) const {
     1022      LEMON_DEBUG(nodes[v._id].red, "Node has to be blue");
     1023      return nodes[v._id].partition_index;
     1024    }
     1025    static int id(Arc e) { return e._id; }
     1026    static int id(Edge e) { return e._id; }
     1027
     1028    static Node nodeFromId(int id) { return Node(id);}
     1029    static Arc arcFromId(int id) { return Arc(id);}
     1030    static Edge edgeFromId(int id) { return Edge(id);}
     1031
     1032    bool valid(Node n) const {
     1033      return n._id >= 0 && n._id < static_cast<int>(nodes.size());
     1034    }
     1035    bool valid(Arc a) const {
     1036      return a._id >= 0 && a._id < static_cast<int>(arcs.size());
     1037    }
     1038    bool valid(Edge e) const {
     1039      return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
     1040    }
     1041
     1042    Node addRedNode() {
     1043      int n = nodes.size();
     1044      nodes.push_back(NodeT());
     1045      nodes[n].first_out = -1;
     1046      nodes[n].red = true;
     1047      if (first_red == -1) {
     1048        nodes[n].partition_index = 0;
     1049      } else {
     1050        nodes[n].partition_index = nodes[first_red].partition_index + 1;
     1051      }
     1052      nodes[n].partition_next = first_red;
     1053      first_red = n;
     1054
     1055      return Node(n);
     1056    }
     1057
     1058    Node addBlueNode() {
     1059      int n = nodes.size();
     1060      nodes.push_back(NodeT());
     1061      nodes[n].first_out = -1;
     1062      nodes[n].red = false;
     1063      if (first_blue == -1) {
     1064        nodes[n].partition_index = 0;
     1065      } else {
     1066        nodes[n].partition_index = nodes[first_blue].partition_index + 1;
     1067      }
     1068      nodes[n].partition_next = first_blue;
     1069      first_blue = n;
     1070
     1071      return Node(n);
     1072    }
     1073
     1074    Edge addEdge(Node u, Node v) {
     1075      int n = arcs.size();
     1076      arcs.push_back(ArcT());
     1077      arcs.push_back(ArcT());
     1078
     1079      arcs[n].target = u._id;
     1080      arcs[n | 1].target = v._id;
     1081
     1082      arcs[n].next_out = nodes[v._id].first_out;
     1083      nodes[v._id].first_out = n;
     1084
     1085      arcs[n | 1].next_out = nodes[u._id].first_out;
     1086      nodes[u._id].first_out = (n | 1);
     1087
     1088      return Edge(n / 2);
     1089    }
     1090
     1091    void clear() {
     1092      arcs.clear();
     1093      nodes.clear();
     1094      first_red = -1;
     1095      first_blue = -1;
     1096    }
     1097
     1098  };
     1099
     1100  typedef BpGraphExtender<SmartBpGraphBase> ExtendedSmartBpGraphBase;
     1101
     1102  /// \ingroup graphs
     1103  ///
     1104  /// \brief A smart undirected graph class.
     1105  ///
     1106  /// \ref SmartBpGraph is a simple and fast graph implementation.
     1107  /// It is also quite memory efficient but at the price
     1108  /// that it does not support node and edge deletion
     1109  /// (except for the Snapshot feature).
     1110  ///
     1111  /// This type fully conforms to the \ref concepts::Graph "Graph concept"
     1112  /// and it also provides some additional functionalities.
     1113  /// Most of its member functions and nested classes are documented
     1114  /// only in the concept class.
     1115  ///
     1116  /// This class provides constant time counting for nodes, edges and arcs.
     1117  ///
     1118  /// \sa concepts::Graph
     1119  /// \sa SmartDigraph
     1120  class SmartBpGraph : public ExtendedSmartBpGraphBase {
     1121    typedef ExtendedSmartBpGraphBase Parent;
     1122
     1123  private:
     1124    /// Graphs are \e not copy constructible. Use GraphCopy instead.
     1125    SmartBpGraph(const SmartBpGraph &) : ExtendedSmartBpGraphBase() {};
     1126    /// \brief Assignment of a graph to another one is \e not allowed.
     1127    /// Use GraphCopy instead.
     1128    void operator=(const SmartBpGraph &) {}
     1129
     1130  public:
     1131
     1132    /// Constructor
     1133
     1134    /// Constructor.
     1135    ///
     1136    SmartBpGraph() {}
     1137
     1138    /// \brief Add a new red node to the graph.
     1139    ///
     1140    /// This function adds a red new node to the graph.
     1141    /// \return The new node.
     1142    Node addRedNode() { return Parent::addRedNode(); }
     1143
     1144    /// \brief Add a new blue node to the graph.
     1145    ///
     1146    /// This function adds a blue new node to the graph.
     1147    /// \return The new node.
     1148    Node addBlueNode() { return Parent::addBlueNode(); }
     1149
     1150    /// \brief Add a new edge to the graph.
     1151    ///
     1152    /// This function adds a new edge to the graph between nodes
     1153    /// \c u and \c v with inherent orientation from node \c u to
     1154    /// node \c v.
     1155    /// \return The new edge.
     1156    Edge addEdge(Node red, Node blue) {
     1157      LEMON_DEBUG(Parent::red(red) && Parent::blue(blue),
     1158                  "Edge has to be formed by a red and a blue nodes");
     1159      return Parent::addEdge(red, blue);
     1160    }
     1161
     1162    /// \brief Node validity check
     1163    ///
     1164    /// This function gives back \c true if the given node is valid,
     1165    /// i.e. it is a real node of the graph.
     1166    ///
     1167    /// \warning A removed node (using Snapshot) could become valid again
     1168    /// if new nodes are added to the graph.
     1169    bool valid(Node n) const { return Parent::valid(n); }
     1170
     1171    /// \brief Edge validity check
     1172    ///
     1173    /// This function gives back \c true if the given edge is valid,
     1174    /// i.e. it is a real edge of the graph.
     1175    ///
     1176    /// \warning A removed edge (using Snapshot) could become valid again
     1177    /// if new edges are added to the graph.
     1178    bool valid(Edge e) const { return Parent::valid(e); }
     1179
     1180    /// \brief Arc validity check
     1181    ///
     1182    /// This function gives back \c true if the given arc is valid,
     1183    /// i.e. it is a real arc of the graph.
     1184    ///
     1185    /// \warning A removed arc (using Snapshot) could become valid again
     1186    /// if new edges are added to the graph.
     1187    bool valid(Arc a) const { return Parent::valid(a); }
     1188
     1189    ///Clear the graph.
     1190
     1191    ///This function erases all nodes and arcs from the graph.
     1192    ///
     1193    void clear() {
     1194      Parent::clear();
     1195    }
     1196
     1197    /// Reserve memory for nodes.
     1198
     1199    /// Using this function, it is possible to avoid superfluous memory
     1200    /// allocation: if you know that the graph you want to build will
     1201    /// be large (e.g. it will contain millions of nodes and/or edges),
     1202    /// then it is worth reserving space for this amount before starting
     1203    /// to build the graph.
     1204    /// \sa reserveEdge()
     1205    void reserveNode(int n) { nodes.reserve(n); };
     1206
     1207    /// Reserve memory for edges.
     1208
     1209    /// Using this function, it is possible to avoid superfluous memory
     1210    /// allocation: if you know that the graph you want to build will
     1211    /// be large (e.g. it will contain millions of nodes and/or edges),
     1212    /// then it is worth reserving space for this amount before starting
     1213    /// to build the graph.
     1214    /// \sa reserveNode()
     1215    void reserveEdge(int m) { arcs.reserve(2 * m); };
     1216
     1217  public:
     1218
     1219    class Snapshot;
     1220
     1221  protected:
     1222
     1223    void saveSnapshot(Snapshot &s)
     1224    {
     1225      s._graph = this;
     1226      s.node_num = nodes.size();
     1227      s.arc_num = arcs.size();
     1228    }
     1229
     1230    void restoreSnapshot(const Snapshot &s)
     1231    {
     1232      while(s.arc_num<arcs.size()) {
     1233        int n=arcs.size()-1;
     1234        Edge arc=edgeFromId(n/2);
     1235        Parent::notifier(Edge()).erase(arc);
     1236        std::vector<Arc> dir;
     1237        dir.push_back(arcFromId(n));
     1238        dir.push_back(arcFromId(n-1));
     1239        Parent::notifier(Arc()).erase(dir);
     1240        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
     1241        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
     1242        arcs.pop_back();
     1243        arcs.pop_back();
     1244      }
     1245      while(s.node_num<nodes.size()) {
     1246        int n=nodes.size()-1;
     1247        Node node = nodeFromId(n);
     1248        if (Parent::red(node)) {
     1249          first_red = nodes[n].partition_next;
     1250          Parent::notifier(RedNode()).erase(node);         
     1251        } else {
     1252          first_blue = nodes[n].partition_next;
     1253          Parent::notifier(BlueNode()).erase(node);
     1254        }
     1255        Parent::notifier(Node()).erase(node);
     1256        nodes.pop_back();
     1257      }
     1258    }
     1259
     1260  public:
     1261
     1262    ///Class to make a snapshot of the graph and to restore it later.
     1263
     1264    ///Class to make a snapshot of the graph and to restore it later.
     1265    ///
     1266    ///The newly added nodes and edges can be removed using the
     1267    ///restore() function. This is the only way for deleting nodes and/or
     1268    ///edges from a SmartBpGraph structure.
     1269    ///
     1270    ///\note After a state is restored, you cannot restore a later state,
     1271    ///i.e. you cannot add the removed nodes and edges again using
     1272    ///another Snapshot instance.
     1273    ///
     1274    ///\warning The validity of the snapshot is not stored due to
     1275    ///performance reasons. If you do not use the snapshot correctly,
     1276    ///it can cause broken program, invalid or not restored state of
     1277    ///the graph or no change.
     1278    class Snapshot
     1279    {
     1280      SmartBpGraph *_graph;
     1281    protected:
     1282      friend class SmartBpGraph;
     1283      unsigned int node_num;
     1284      unsigned int arc_num;
     1285    public:
     1286      ///Default constructor.
     1287
     1288      ///Default constructor.
     1289      ///You have to call save() to actually make a snapshot.
     1290      Snapshot() : _graph(0) {}
     1291      ///Constructor that immediately makes a snapshot
     1292
     1293      /// This constructor immediately makes a snapshot of the given graph.
     1294      ///
     1295      Snapshot(SmartBpGraph &gr) {
     1296        gr.saveSnapshot(*this);
     1297      }
     1298
     1299      ///Make a snapshot.
     1300
     1301      ///This function makes a snapshot of the given graph.
     1302      ///It can be called more than once. In case of a repeated
     1303      ///call, the previous snapshot gets lost.
     1304      void save(SmartBpGraph &gr)
     1305      {
     1306        gr.saveSnapshot(*this);
     1307      }
     1308
     1309      ///Undo the changes until the last snapshot.
     1310
     1311      ///This function undos the changes until the last snapshot
     1312      ///created by save() or Snapshot(SmartBpGraph&).
     1313      void restore()
     1314      {
     1315        _graph->restoreSnapshot(*this);
     1316      }
     1317    };
     1318  };
     1319
    8141320} //namespace lemon
    8151321
  • test/bpgraph_test.cc

    r1018 r1019  
    1919#include <lemon/concepts/bpgraph.h>
    2020//#include <lemon/list_graph.h>
    21 //#include <lemon/smart_graph.h>
     21#include <lemon/smart_graph.h>
    2222//#include <lemon/full_graph.h>
    23 //#include <lemon/grid_graph.h>
    24 //#include <lemon/hypercube_graph.h>
    2523
    2624#include "test_tools.h"
     
    2927using namespace lemon;
    3028using namespace lemon::concepts;
     29
     30template <class BpGraph>
     31void checkBpGraphBuild() {
     32  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
     33
     34  BpGraph G;
     35  checkGraphNodeList(G, 0);
     36  checkGraphRedNodeList(G, 0);
     37  checkGraphBlueNodeList(G, 0);
     38  checkGraphEdgeList(G, 0);
     39  checkGraphArcList(G, 0);
     40
     41  G.reserveNode(3);
     42  G.reserveEdge(3);
     43
     44  Node
     45    rn1 = G.addRedNode();
     46  checkGraphNodeList(G, 1);
     47  checkGraphRedNodeList(G, 1);
     48  checkGraphBlueNodeList(G, 0);
     49  checkGraphEdgeList(G, 0);
     50  checkGraphArcList(G, 0);
     51
     52  Node
     53    bn1 = G.addBlueNode(),
     54    bn2 = G.addBlueNode();
     55  checkGraphNodeList(G, 3);
     56  checkGraphRedNodeList(G, 1);
     57  checkGraphBlueNodeList(G, 2);
     58  checkGraphEdgeList(G, 0);
     59  checkGraphArcList(G, 0);
     60
     61  Edge e1 = G.addEdge(rn1, bn2);
     62  check(G.redNode(e1) == rn1 && G.blueNode(e1) == bn2, "Wrong edge");
     63  check(G.u(e1) == rn1 && G.v(e1) == bn2, "Wrong edge");
     64
     65  checkGraphNodeList(G, 3);
     66  checkGraphRedNodeList(G, 1);
     67  checkGraphBlueNodeList(G, 2);
     68  checkGraphEdgeList(G, 1);
     69  checkGraphArcList(G, 2);
     70
     71  checkGraphIncEdgeArcLists(G, rn1, 1);
     72  checkGraphIncEdgeArcLists(G, bn1, 0);
     73  checkGraphIncEdgeArcLists(G, bn2, 1);
     74
     75  checkGraphConEdgeList(G, 1);
     76  checkGraphConArcList(G, 2);
     77
     78  Edge
     79    e2 = G.addEdge(rn1, bn1),
     80    e3 = G.addEdge(rn1, bn2);
     81
     82  checkGraphNodeList(G, 3);
     83  checkGraphRedNodeList(G, 1);
     84  checkGraphBlueNodeList(G, 2);
     85  checkGraphEdgeList(G, 3);
     86  checkGraphArcList(G, 6);
     87
     88  checkGraphIncEdgeArcLists(G, rn1, 3);
     89  checkGraphIncEdgeArcLists(G, bn1, 1);
     90  checkGraphIncEdgeArcLists(G, bn2, 2);
     91
     92  checkGraphConEdgeList(G, 3);
     93  checkGraphConArcList(G, 6);
     94
     95  checkArcDirections(G);
     96
     97  checkNodeIds(G);
     98  checkRedNodeIds(G);
     99  checkBlueNodeIds(G);
     100  checkArcIds(G);
     101  checkEdgeIds(G);
     102
     103  checkGraphNodeMap(G);
     104  checkGraphRedMap(G);
     105  checkGraphBlueMap(G);
     106  checkGraphArcMap(G);
     107  checkGraphEdgeMap(G);
     108}
     109
     110template <class Graph>
     111void checkBpGraphSnapshot() {
     112  TEMPLATE_BPGRAPH_TYPEDEFS(Graph);
     113
     114  Graph G;
     115  Node
     116    n1 = G.addRedNode(),
     117    n2 = G.addBlueNode(),
     118    n3 = G.addBlueNode();
     119  Edge
     120    e1 = G.addEdge(n1, n2),
     121    e2 = G.addEdge(n1, n3);
     122
     123  checkGraphNodeList(G, 3);
     124  checkGraphRedNodeList(G, 1);
     125  checkGraphBlueNodeList(G, 2);
     126  checkGraphEdgeList(G, 2);
     127  checkGraphArcList(G, 4);
     128
     129  typename Graph::Snapshot snapshot(G);
     130
     131  Node n4 = G.addRedNode();
     132  G.addEdge(n4, n2);
     133  G.addEdge(n4, n3);
     134
     135  checkGraphNodeList(G, 4);
     136  checkGraphRedNodeList(G, 2);
     137  checkGraphBlueNodeList(G, 2);
     138  checkGraphEdgeList(G, 4);
     139  checkGraphArcList(G, 8);
     140
     141  snapshot.restore();
     142
     143  checkGraphNodeList(G, 3);
     144  checkGraphRedNodeList(G, 1);
     145  checkGraphBlueNodeList(G, 2);
     146  checkGraphEdgeList(G, 2);
     147  checkGraphArcList(G, 4);
     148
     149  checkGraphIncEdgeArcLists(G, n1, 2);
     150  checkGraphIncEdgeArcLists(G, n2, 1);
     151  checkGraphIncEdgeArcLists(G, n3, 1);
     152
     153  checkGraphConEdgeList(G, 2);
     154  checkGraphConArcList(G, 4);
     155
     156  checkNodeIds(G);
     157  checkRedNodeIds(G);
     158  checkBlueNodeIds(G);
     159  checkArcIds(G);
     160  checkEdgeIds(G);
     161
     162  checkGraphNodeMap(G);
     163  checkGraphRedMap(G);
     164  checkGraphBlueMap(G);
     165  checkGraphArcMap(G);
     166  checkGraphEdgeMap(G);
     167
     168  G.addRedNode();
     169  snapshot.save(G);
     170
     171  G.addEdge(G.addRedNode(), G.addBlueNode());
     172
     173  snapshot.restore();
     174  snapshot.save(G);
     175
     176  checkGraphNodeList(G, 4);
     177  checkGraphRedNodeList(G, 2);
     178  checkGraphBlueNodeList(G, 2);
     179  checkGraphEdgeList(G, 2);
     180  checkGraphArcList(G, 4);
     181
     182  G.addEdge(G.addRedNode(), G.addBlueNode());
     183
     184  snapshot.restore();
     185
     186  checkGraphNodeList(G, 4);
     187  checkGraphRedNodeList(G, 2);
     188  checkGraphBlueNodeList(G, 2);
     189  checkGraphEdgeList(G, 2);
     190  checkGraphArcList(G, 4);
     191}
     192
     193template <typename Graph>
     194void checkBpGraphValidity() {
     195  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     196  Graph g;
     197
     198  Node
     199    n1 = g.addRedNode(),
     200    n2 = g.addBlueNode(),
     201    n3 = g.addBlueNode();
     202
     203  Edge
     204    e1 = g.addEdge(n1, n2),
     205    e2 = g.addEdge(n1, n3);
     206
     207  check(g.valid(n1), "Wrong validity check");
     208  check(g.valid(e1), "Wrong validity check");
     209  check(g.valid(g.direct(e1, true)), "Wrong validity check");
     210
     211  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
     212  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
     213  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
     214}
    31215
    32216void checkConcepts() {
     
    52236      ErasableBpGraphComponent<> >();
    53237
    54     checkConcept<ClearableGraphComponent<>,
    55       ClearableGraphComponent<> >();
     238    checkConcept<ClearableBpGraphComponent<>,
     239      ClearableBpGraphComponent<> >();
    56240
    57241  }
     
    59243    checkConcept<BpGraph, BpGraph>();
    60244  }
     245  { // Checking SmartBpGraph
     246    checkConcept<BpGraph, SmartBpGraph>();
     247    checkConcept<AlterableBpGraphComponent<>, SmartBpGraph>();
     248    checkConcept<ExtendableBpGraphComponent<>, SmartBpGraph>();
     249    checkConcept<ClearableBpGraphComponent<>, SmartBpGraph>();
     250  }
    61251}
    62252
    63253void checkGraphs() {
     254  { // Checking SmartGraph
     255    checkBpGraphBuild<SmartBpGraph>();
     256    checkBpGraphSnapshot<SmartBpGraph>();
     257    checkBpGraphValidity<SmartBpGraph>();
     258  }
    64259}
    65260
  • test/graph_test.h

    r440 r1019  
    4242
    4343  template<class Graph>
     44  void checkGraphRedNodeList(const Graph &G, int cnt)
     45  {
     46    typename Graph::RedIt n(G);
     47    for(int i=0;i<cnt;i++) {
     48      check(n!=INVALID,"Wrong red Node list linking.");
     49      ++n;
     50    }
     51    check(n==INVALID,"Wrong red Node list linking.");
     52    check(countRedNodes(G)==cnt,"Wrong red Node number.");
     53  }
     54
     55  template<class Graph>
     56  void checkGraphBlueNodeList(const Graph &G, int cnt)
     57  {
     58    typename Graph::BlueIt n(G);
     59    for(int i=0;i<cnt;i++) {
     60      check(n!=INVALID,"Wrong blue Node list linking.");
     61      ++n;
     62    }
     63    check(n==INVALID,"Wrong blue Node list linking.");
     64    check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
     65  }
     66
     67  template<class Graph>
    4468  void checkGraphArcList(const Graph &G, int cnt)
    4569  {
     
    167191  template <typename Graph>
    168192  void checkNodeIds(const Graph& G) {
     193    typedef typename Graph::Node Node;
    169194    std::set<int> values;
    170195    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
     
    174199      values.insert(G.id(n));
    175200    }
     201    check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id");
     202  }
     203
     204  template <typename Graph>
     205  void checkRedNodeIds(const Graph& G) {
     206    typedef typename Graph::RedNode RedNode;
     207    std::set<int> values;
     208    for (typename Graph::RedIt n(G); n != INVALID; ++n) {
     209      check(G.red(n), "Wrong partition");
     210      check(G.redId(n) == G.id(RedNode(n)), "Wrong id");
     211      check(values.find(G.redId(n)) == values.end(), "Wrong id");
     212      check(G.redId(n) <= G.maxRedId(), "Wrong maximum id");
     213      values.insert(G.id(n));
     214    }
     215    check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id");
     216  }
     217
     218  template <typename Graph>
     219  void checkBlueNodeIds(const Graph& G) {
     220    typedef typename Graph::BlueNode BlueNode;
     221    std::set<int> values;
     222    for (typename Graph::BlueIt n(G); n != INVALID; ++n) {
     223      check(G.blue(n), "Wrong partition");
     224      check(G.blueId(n) == G.id(BlueNode(n)), "Wrong id");
     225      check(values.find(G.blueId(n)) == values.end(), "Wrong id");
     226      check(G.blueId(n) <= G.maxBlueId(), "Wrong maximum id");
     227      values.insert(G.id(n));
     228    }
     229    check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id");
    176230  }
    177231
    178232  template <typename Graph>
    179233  void checkArcIds(const Graph& G) {
     234    typedef typename Graph::Arc Arc;
    180235    std::set<int> values;
    181236    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
     
    185240      values.insert(G.id(a));
    186241    }
     242    check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id");
    187243  }
    188244
    189245  template <typename Graph>
    190246  void checkEdgeIds(const Graph& G) {
     247    typedef typename Graph::Edge Edge;
    191248    std::set<int> values;
    192249    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
     
    196253      values.insert(G.id(e));
    197254    }
     255    check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id");
    198256  }
    199257
     
    229287
    230288  template <typename Graph>
     289  void checkGraphRedMap(const Graph& G) {
     290    typedef typename Graph::Node Node;
     291    typedef typename Graph::RedIt RedIt;
     292
     293    typedef typename Graph::template RedMap<int> IntRedMap;
     294    IntRedMap map(G, 42);
     295    for (RedIt it(G); it != INVALID; ++it) {
     296      check(map[it] == 42, "Wrong map constructor.");
     297    }
     298    int s = 0;
     299    for (RedIt it(G); it != INVALID; ++it) {
     300      map[it] = 0;
     301      check(map[it] == 0, "Wrong operator[].");
     302      map.set(it, s);
     303      check(map[it] == s, "Wrong set.");
     304      ++s;
     305    }
     306    s = s * (s - 1) / 2;
     307    for (RedIt it(G); it != INVALID; ++it) {
     308      s -= map[it];
     309    }
     310    check(s == 0, "Wrong sum.");
     311
     312    // map = constMap<Node>(12);
     313    // for (NodeIt it(G); it != INVALID; ++it) {
     314    //   check(map[it] == 12, "Wrong operator[].");
     315    // }
     316  }
     317
     318  template <typename Graph>
     319  void checkGraphBlueMap(const Graph& G) {
     320    typedef typename Graph::Node Node;
     321    typedef typename Graph::BlueIt BlueIt;
     322
     323    typedef typename Graph::template BlueMap<int> IntBlueMap;
     324    IntBlueMap map(G, 42);
     325    for (BlueIt it(G); it != INVALID; ++it) {
     326      check(map[it] == 42, "Wrong map constructor.");
     327    }
     328    int s = 0;
     329    for (BlueIt it(G); it != INVALID; ++it) {
     330      map[it] = 0;
     331      check(map[it] == 0, "Wrong operator[].");
     332      map.set(it, s);
     333      check(map[it] == s, "Wrong set.");
     334      ++s;
     335    }
     336    s = s * (s - 1) / 2;
     337    for (BlueIt it(G); it != INVALID; ++it) {
     338      s -= map[it];
     339    }
     340    check(s == 0, "Wrong sum.");
     341
     342    // map = constMap<Node>(12);
     343    // for (NodeIt it(G); it != INVALID; ++it) {
     344    //   check(map[it] == 12, "Wrong operator[].");
     345    // }
     346  }
     347
     348  template <typename Graph>
    231349  void checkGraphArcMap(const Graph& G) {
    232350    typedef typename Graph::Arc Arc;
Note: See TracChangeset for help on using the changeset viewer.