lemon/edge_set.h
changeset 639 72ac25ad276e
parent 559 c5fd2d996909
child 660 d9cf3b5858ae
equal deleted inserted replaced
2:823fedc41c04 3:47f839933b57
    31 
    31 
    32   template <typename GR>
    32   template <typename GR>
    33   class ListArcSetBase {
    33   class ListArcSetBase {
    34   public:
    34   public:
    35 
    35 
    36     typedef GR Graph;
       
    37     typedef typename GR::Node Node;
    36     typedef typename GR::Node Node;
    38     typedef typename GR::NodeIt NodeIt;
    37     typedef typename GR::NodeIt NodeIt;
    39 
    38 
    40   protected:
    39   protected:
    41 
    40 
   206       return _graph->notifier(Node());
   205       return _graph->notifier(Node());
   207     }
   206     }
   208 
   207 
   209     template <typename V>
   208     template <typename V>
   210     class NodeMap : public GR::template NodeMap<V> {
   209     class NodeMap : public GR::template NodeMap<V> {
       
   210       typedef typename GR::template NodeMap<V> Parent;
       
   211 
   211     public:
   212     public:
   212 
       
   213       typedef typename GR::template NodeMap<V> Parent;
       
   214 
   213 
   215       explicit NodeMap(const ListArcSetBase<GR>& arcset)
   214       explicit NodeMap(const ListArcSetBase<GR>& arcset)
   216         : Parent(*arcset._graph) {}
   215         : Parent(*arcset._graph) {}
   217 
   216 
   218       NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
   217       NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
   257   ///
   256   ///
   258   /// This class fully conforms to the \ref concepts::Digraph
   257   /// This class fully conforms to the \ref concepts::Digraph
   259   /// "Digraph" concept.
   258   /// "Digraph" concept.
   260   template <typename GR>
   259   template <typename GR>
   261   class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
   260   class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
   262 
       
   263   public:
       
   264 
       
   265     typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
   261     typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
       
   262 
       
   263   public:
   266 
   264 
   267     typedef typename Parent::Node Node;
   265     typedef typename Parent::Node Node;
   268     typedef typename Parent::Arc Arc;
   266     typedef typename Parent::Arc Arc;
   269 
       
   270     typedef GR Graph;
       
   271 
       
   272 
   267 
   273     typedef typename Parent::NodesImplBase NodesImplBase;
   268     typedef typename Parent::NodesImplBase NodesImplBase;
   274 
   269 
   275     void eraseNode(const Node& node) {
   270     void eraseNode(const Node& node) {
   276       Arc arc;
   271       Arc arc;
   290     void clearNodes() {
   285     void clearNodes() {
   291       Parent::clear();
   286       Parent::clear();
   292     }
   287     }
   293 
   288 
   294     class NodesImpl : public NodesImplBase {
   289     class NodesImpl : public NodesImplBase {
       
   290       typedef NodesImplBase Parent;
       
   291 
   295     public:
   292     public:
   296       typedef NodesImplBase Parent;
       
   297 
       
   298       NodesImpl(const GR& graph, ListArcSet& arcset)
   293       NodesImpl(const GR& graph, ListArcSet& arcset)
   299         : Parent(graph), _arcset(arcset) {}
   294         : Parent(graph), _arcset(arcset) {}
   300 
   295 
   301       virtual ~NodesImpl() {}
   296       virtual ~NodesImpl() {}
   302 
   297 
   352 
   347 
   353   template <typename GR>
   348   template <typename GR>
   354   class ListEdgeSetBase {
   349   class ListEdgeSetBase {
   355   public:
   350   public:
   356 
   351 
   357     typedef GR Graph;
       
   358     typedef typename GR::Node Node;
   352     typedef typename GR::Node Node;
   359     typedef typename GR::NodeIt NodeIt;
   353     typedef typename GR::NodeIt NodeIt;
   360 
   354 
   361   protected:
   355   protected:
   362 
   356 
   635       return _graph->notifier(Node());
   629       return _graph->notifier(Node());
   636     }
   630     }
   637 
   631 
   638     template <typename V>
   632     template <typename V>
   639     class NodeMap : public GR::template NodeMap<V> {
   633     class NodeMap : public GR::template NodeMap<V> {
       
   634       typedef typename GR::template NodeMap<V> Parent;
       
   635 
   640     public:
   636     public:
   641 
       
   642       typedef typename GR::template NodeMap<V> Parent;
       
   643 
   637 
   644       explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
   638       explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
   645         : Parent(*arcset._graph) {}
   639         : Parent(*arcset._graph) {}
   646 
   640 
   647       NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
   641       NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
   686   ///
   680   ///
   687   /// This class fully conforms to the \ref concepts::Graph "Graph"
   681   /// This class fully conforms to the \ref concepts::Graph "Graph"
   688   /// concept.
   682   /// concept.
   689   template <typename GR>
   683   template <typename GR>
   690   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
   684   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
   691 
       
   692   public:
       
   693 
       
   694     typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
   685     typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
       
   686 
       
   687   public:
   695 
   688 
   696     typedef typename Parent::Node Node;
   689     typedef typename Parent::Node Node;
   697     typedef typename Parent::Arc Arc;
   690     typedef typename Parent::Arc Arc;
   698     typedef typename Parent::Edge Edge;
   691     typedef typename Parent::Edge Edge;
   699 
       
   700     typedef GR Graph;
       
   701 
       
   702 
   692 
   703     typedef typename Parent::NodesImplBase NodesImplBase;
   693     typedef typename Parent::NodesImplBase NodesImplBase;
   704 
   694 
   705     void eraseNode(const Node& node) {
   695     void eraseNode(const Node& node) {
   706       Arc arc;
   696       Arc arc;
   715     void clearNodes() {
   705     void clearNodes() {
   716       Parent::clear();
   706       Parent::clear();
   717     }
   707     }
   718 
   708 
   719     class NodesImpl : public NodesImplBase {
   709     class NodesImpl : public NodesImplBase {
       
   710       typedef NodesImplBase Parent;
       
   711 
   720     public:
   712     public:
   721       typedef NodesImplBase Parent;
       
   722 
       
   723       NodesImpl(const GR& graph, ListEdgeSet& arcset)
   713       NodesImpl(const GR& graph, ListEdgeSet& arcset)
   724         : Parent(graph), _arcset(arcset) {}
   714         : Parent(graph), _arcset(arcset) {}
   725 
   715 
   726       virtual ~NodesImpl() {}
   716       virtual ~NodesImpl() {}
   727 
   717 
   777 
   767 
   778   template <typename GR>
   768   template <typename GR>
   779   class SmartArcSetBase {
   769   class SmartArcSetBase {
   780   public:
   770   public:
   781 
   771 
   782     typedef GR Graph;
   772     typedef typename GR::Node Node;
   783     typedef typename Graph::Node Node;
   773     typedef typename GR::NodeIt NodeIt;
   784     typedef typename Graph::NodeIt NodeIt;
       
   785 
   774 
   786   protected:
   775   protected:
   787 
   776 
   788     struct NodeT {
   777     struct NodeT {
   789       int first_out, first_in;
   778       int first_out, first_in;
   898       return _graph->notifier(Node());
   887       return _graph->notifier(Node());
   899     }
   888     }
   900 
   889 
   901     template <typename V>
   890     template <typename V>
   902     class NodeMap : public GR::template NodeMap<V> {
   891     class NodeMap : public GR::template NodeMap<V> {
       
   892       typedef typename GR::template NodeMap<V> Parent;
       
   893 
   903     public:
   894     public:
   904 
       
   905       typedef typename GR::template NodeMap<V> Parent;
       
   906 
   895 
   907       explicit NodeMap(const SmartArcSetBase<GR>& arcset)
   896       explicit NodeMap(const SmartArcSetBase<GR>& arcset)
   908         : Parent(*arcset._graph) { }
   897         : Parent(*arcset._graph) { }
   909 
   898 
   910       NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
   899       NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
   954   ///
   943   ///
   955   /// This class fully conforms to the \ref concepts::Digraph
   944   /// This class fully conforms to the \ref concepts::Digraph
   956   /// "Digraph" concept.
   945   /// "Digraph" concept.
   957   template <typename GR>
   946   template <typename GR>
   958   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
   947   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
   959 
       
   960   public:
       
   961 
       
   962     typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
   948     typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
       
   949 
       
   950   public:
   963 
   951 
   964     typedef typename Parent::Node Node;
   952     typedef typename Parent::Node Node;
   965     typedef typename Parent::Arc Arc;
   953     typedef typename Parent::Arc Arc;
   966 
       
   967     typedef GR Graph;
       
   968 
   954 
   969   protected:
   955   protected:
   970 
   956 
   971     typedef typename Parent::NodesImplBase NodesImplBase;
   957     typedef typename Parent::NodesImplBase NodesImplBase;
   972 
   958 
   981     void clearNodes() {
   967     void clearNodes() {
   982       Parent::clear();
   968       Parent::clear();
   983     }
   969     }
   984 
   970 
   985     class NodesImpl : public NodesImplBase {
   971     class NodesImpl : public NodesImplBase {
       
   972       typedef NodesImplBase Parent;
       
   973 
   986     public:
   974     public:
   987       typedef NodesImplBase Parent;
       
   988 
       
   989       NodesImpl(const GR& graph, SmartArcSet& arcset)
   975       NodesImpl(const GR& graph, SmartArcSet& arcset)
   990         : Parent(graph), _arcset(arcset) {}
   976         : Parent(graph), _arcset(arcset) {}
   991 
   977 
   992       virtual ~NodesImpl() {}
   978       virtual ~NodesImpl() {}
   993 
   979 
  1060 
  1046 
  1061   template <typename GR>
  1047   template <typename GR>
  1062   class SmartEdgeSetBase {
  1048   class SmartEdgeSetBase {
  1063   public:
  1049   public:
  1064 
  1050 
  1065     typedef GR Graph;
       
  1066     typedef typename GR::Node Node;
  1051     typedef typename GR::Node Node;
  1067     typedef typename GR::NodeIt NodeIt;
  1052     typedef typename GR::NodeIt NodeIt;
  1068 
  1053 
  1069   protected:
  1054   protected:
  1070 
  1055 
  1247       return _graph->notifier(Node());
  1232       return _graph->notifier(Node());
  1248     }
  1233     }
  1249 
  1234 
  1250     template <typename V>
  1235     template <typename V>
  1251     class NodeMap : public GR::template NodeMap<V> {
  1236     class NodeMap : public GR::template NodeMap<V> {
       
  1237       typedef typename GR::template NodeMap<V> Parent;
       
  1238 
  1252     public:
  1239     public:
  1253 
       
  1254       typedef typename GR::template NodeMap<V> Parent;
       
  1255 
  1240 
  1256       explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
  1241       explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
  1257         : Parent(*arcset._graph) { }
  1242         : Parent(*arcset._graph) { }
  1258 
  1243 
  1259       NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
  1244       NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
  1302   ///
  1287   ///
  1303   /// This class fully conforms to the \ref concepts::Graph
  1288   /// This class fully conforms to the \ref concepts::Graph
  1304   /// "Graph" concept.
  1289   /// "Graph" concept.
  1305   template <typename GR>
  1290   template <typename GR>
  1306   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
  1291   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
  1307 
       
  1308   public:
       
  1309 
       
  1310     typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
  1292     typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
       
  1293 
       
  1294   public:
  1311 
  1295 
  1312     typedef typename Parent::Node Node;
  1296     typedef typename Parent::Node Node;
  1313     typedef typename Parent::Arc Arc;
  1297     typedef typename Parent::Arc Arc;
  1314     typedef typename Parent::Edge Edge;
  1298     typedef typename Parent::Edge Edge;
  1315 
  1299 
  1316     typedef GR Graph;
       
  1317 
       
  1318   protected:
  1300   protected:
  1319 
  1301 
  1320     typedef typename Parent::NodesImplBase NodesImplBase;
  1302     typedef typename Parent::NodesImplBase NodesImplBase;
  1321 
  1303 
  1322     void eraseNode(const Node& node) {
  1304     void eraseNode(const Node& node) {
  1329     void clearNodes() {
  1311     void clearNodes() {
  1330       Parent::clear();
  1312       Parent::clear();
  1331     }
  1313     }
  1332 
  1314 
  1333     class NodesImpl : public NodesImplBase {
  1315     class NodesImpl : public NodesImplBase {
       
  1316       typedef NodesImplBase Parent;
       
  1317 
  1334     public:
  1318     public:
  1335       typedef NodesImplBase Parent;
       
  1336 
       
  1337       NodesImpl(const GR& graph, SmartEdgeSet& arcset)
  1319       NodesImpl(const GR& graph, SmartEdgeSet& arcset)
  1338         : Parent(graph), _arcset(arcset) {}
  1320         : Parent(graph), _arcset(arcset) {}
  1339 
  1321 
  1340       virtual ~NodesImpl() {}
  1322       virtual ~NodesImpl() {}
  1341 
  1323