Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/full_graph.h
changeset 1909 2d806130e700
parent 1875 98698b69a902
child 1910 f95eea8c34b0
equal deleted inserted replaced
11:c51035a6397d 12:f1795a0cc47f 
    29 #include <lemon/utility.h>
 
    29 #include <lemon/utility.h>
 
    30 
    30 
    31 
    31 
    32 ///\ingroup graphs
 
    32 ///\ingroup graphs
 
    33 ///\file
 
    33 ///\file
 
    34 ///\brief FullGraph and UndirFullGraph classes.
 
    34 ///\brief FullGraph and FullUGraph classes.
 
    35 
    35 
    36 
    36 
    37 namespace lemon {
 
    37 namespace lemon {
 
    38 
    38 
    39   class FullGraphBase {
 
    39   class FullGraphBase {
 
   211 
   211 
   212     FullGraph(int n) { construct(n); }
 
   212     FullGraph(int n) { construct(n); }
 
   213   };
 
   213   };
 
   214 
   214 
   215 
   215 
   216   class UndirFullGraphBase {
 
   216   class FullUGraphBase {
 
   217     int _nodeNum;
 
   217     int _nodeNum;
 
   218     int _edgeNum;
 
   218     int _edgeNum;
 
   219   public:
 
   219   public:
 
   220 
   220 
   221     typedef UndirFullGraphBase Graph;
 
   221     typedef FullUGraphBase Graph;
 
   222 
   222 
   223     class Node;
 
   223     class Node;
 
   224     class Edge;
 
   224     class Edge;
 
   225 
   225 
   226   public:
 
   226   public:
 
   227 
   227 
   228     UndirFullGraphBase() {}
 
   228     FullUGraphBase() {}
 
   229 
   229 
   230 
   230 
   231     ///Creates a full graph with \c n nodes.
 
   231     ///Creates a full graph with \c n nodes.
 
   232     void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
 
   232     void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
 
   233     ///
 
   233     ///
 
   299 
   299 
   300     typedef True FindEdgeTag;
 
   300     typedef True FindEdgeTag;
 
   301     
   301     
   302       
   302       
   303     class Node {
 
   303     class Node {
 
   304       friend class UndirFullGraphBase;
 
   304       friend class FullUGraphBase;
 
   305 
   305 
   306     protected:
 
   306     protected:
 
   307       int id;
 
   307       int id;
 
   308       Node(int _id) { id = _id;}
 
   308       Node(int _id) { id = _id;}
 
   309     public:
 
   309     public:
 
   315     };
 
   315     };
 
   316     
   316     
   317 
   317 
   318 
   318 
   319     class Edge {
 
   319     class Edge {
 
   320       friend class UndirFullGraphBase;
 
   320       friend class FullUGraphBase;
 
   321       
   321       
   322     protected:
 
   322     protected:
 
   323       int id;  // _nodeNum * target + source;
 
   323       int id;  // _nodeNum * target + source;
 
   324 
   324 
   325       Edge(int _id) : id(_id) {}
 
   325       Edge(int _id) : id(_id) {}
 
   375       edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
 
   375       edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
 
   376     }
 
   376     }
 
   377 
   377 
   378   };
 
   378   };
 
   379 
   379 
   380   typedef StaticMappableUndirGraphExtender<
 
   380   typedef StaticMappableUGraphExtender<
 
   381     IterableUndirGraphExtender<
 
   381     IterableUGraphExtender<
 
   382     AlterableUndirGraphExtender<
 
   382     AlterableUGraphExtender<
 
   383     UndirGraphExtender<UndirFullGraphBase> > > > ExtendedUndirFullGraphBase;
 
   383     UGraphExtender<FullUGraphBase> > > > ExtendedFullUGraphBase;
 
   384 
   384 
   385   /// \ingroup graphs
 
   385   /// \ingroup graphs
 
   386   ///
 
   386   ///
 
   387   /// \brief An undirected full graph class.
 
   387   /// \brief An undirected full graph class.
 
   388   ///
 
   388   ///
 
   389   /// This is a simple and fast undirected full graph implementation.
 
   389   /// This is a simple and fast undirected full graph implementation.
 
   390   /// It is completely static, so you can neither add nor delete either
 
   390   /// It is completely static, so you can neither add nor delete either
 
   391   /// edges or nodes.
 
   391   /// edges or nodes.
 
   392   ///
 
   392   ///
 
   393   /// The main difference beetween the \e FullGraph and \e UndirFullGraph class
 
   393   /// The main difference beetween the \e FullGraph and \e FullUGraph class
 
   394   /// is that this class conforms to the undirected graph concept and
 
   394   /// is that this class conforms to the undirected graph concept and
 
   395   /// it does not contain the loop edges.
 
   395   /// it does not contain the loop edges.
 
   396   ///
 
   396   ///
 
   397   /// \sa FullGraph
 
   397   /// \sa FullGraph
 
   398   ///
 
   398   ///
 
   399   /// \author Balazs Dezso
 
   399   /// \author Balazs Dezso
 
   400   class UndirFullGraph : public ExtendedUndirFullGraphBase {
 
   400   class FullUGraph : public ExtendedFullUGraphBase {
 
   401   public:
 
   401   public:
 
   402     UndirFullGraph(int n) { construct(n); }
 
   402     FullUGraph(int n) { construct(n); }
 
   403   };
 
   403   };
 
   404 
   404 
   405 
   405 
   406   class FullUndirBipartiteGraphBase {
 
   406   class FullUBipartiteGraphBase {
 
   407   protected:
 
   407   protected:
 
   408 
   408 
   409     int _upperNodeNum;
 
   409     int _upperNodeNum;
 
   410     int _lowerNodeNum;
 
   410     int _lowerNodeNum;
 
   411 
   411 
   413 
   413 
   414   public:
 
   414   public:
 
   415 
   415 
   416     class NodeSetError : public LogicError {
 
   416     class NodeSetError : public LogicError {
 
   417       virtual const char* exceptionName() const { 
   417       virtual const char* exceptionName() const { 
   418 	return "lemon::FullUndirBipartiteGraph::NodeSetError";
 
   418 	return "lemon::FullUBipartiteGraph::NodeSetError";
 
   419       }
 
   419       }
 
   420     };
 
   420     };
 
   421   
   421   
   422     class Node {
 
   422     class Node {
 
   423       friend class FullUndirBipartiteGraphBase;
 
   423       friend class FullUBipartiteGraphBase;
 
   424     protected:
 
   424     protected:
 
   425       int id;
 
   425       int id;
 
   426 
   426 
   427       Node(int _id) : id(_id) {}
 
   427       Node(int _id) : id(_id) {}
 
   428     public:
 
   428     public:
 
   432       bool operator!=(const Node i) const {return id!=i.id;}
 
   432       bool operator!=(const Node i) const {return id!=i.id;}
 
   433       bool operator<(const Node i) const {return id<i.id;}
 
   433       bool operator<(const Node i) const {return id<i.id;}
 
   434     };
 
   434     };
 
   435 
   435 
   436     class Edge {
 
   436     class Edge {
 
   437       friend class FullUndirBipartiteGraphBase;
 
   437       friend class FullUBipartiteGraphBase;
 
   438     protected:
 
   438     protected:
 
   439       int id;
 
   439       int id;
 
   440 
   440 
   441       Edge(int _id) { id = _id;}
 
   441       Edge(int _id) { id = _id;}
 
   442     public:
 
   442     public:
 
   573     }
 
   573     }
 
   574 
   574 
   575   };
 
   575   };
 
   576 
   576 
   577 
   577 
   578   typedef StaticMappableUndirBipartiteGraphExtender<
 
   578   typedef StaticMappableUBipartiteGraphExtender<
 
   579     IterableUndirBipartiteGraphExtender<
 
   579     IterableUBipartiteGraphExtender<
 
   580     AlterableUndirBipartiteGraphExtender<
 
   580     AlterableUBipartiteGraphExtender<
 
   581     UndirBipartiteGraphExtender <
 
   581     UBipartiteGraphExtender <
 
   582     FullUndirBipartiteGraphBase> > > >
 
   582     FullUBipartiteGraphBase> > > >
 
   583   ExtendedFullUndirBipartiteGraphBase;
 
   583   ExtendedFullUBipartiteGraphBase;
 
   584 
   584 
   585 
   585 
   586   class FullUndirBipartiteGraph : 
   586   class FullUBipartiteGraph : 
   587     public ExtendedFullUndirBipartiteGraphBase {
 
   587     public ExtendedFullUBipartiteGraphBase {
 
   588   public:
 
   588   public:
 
   589     typedef ExtendedFullUndirBipartiteGraphBase Parent;
 
   589     typedef ExtendedFullUBipartiteGraphBase Parent;
 
   590     FullUndirBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
 
   590     FullUBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
 
   591       Parent::construct(upperNodeNum, lowerNodeNum);
 
   591       Parent::construct(upperNodeNum, lowerNodeNum);
 
   592     }
 
   592     }
 
   593   };
 
   593   };
 
   594 
   594 
   595 } //namespace lemon
 
   595 } //namespace lemon
lemon-0.x