Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/static_graph.h
changeset 821 f4b5c2d5449d
parent 820 cf360f758f25
child 822 6cab2ab9d8e7
equal deleted inserted replaced
0:ead92c174edd 1:f7ca06333d70 
    30 
    30 
    31   class StaticDigraphBase {
 
    31   class StaticDigraphBase {
 
    32   public:
 
    32   public:
 
    33 
    33 
    34     StaticDigraphBase() 
    34     StaticDigraphBase() 
    35       : node_num(-1), arc_num(0), 
    35       : built(false), node_num(0), arc_num(0), 
    36         node_first_out(NULL), node_first_in(NULL),
 
    36         node_first_out(NULL), node_first_in(NULL),
 
    37         arc_source(NULL), arc_target(NULL), 
    37         arc_source(NULL), arc_target(NULL), 
    38         arc_next_in(NULL), arc_next_out(NULL) {}
 
    38         arc_next_in(NULL), arc_next_out(NULL) {}
 
    39     
    39     
    40     ~StaticDigraphBase() {
 
    40     ~StaticDigraphBase() {
 
    41       if (node_num != -1) {
 
    41       if (built) {
 
    42         delete[] node_first_out;
 
    42         delete[] node_first_out;
 
    43         delete[] node_first_in;
 
    43         delete[] node_first_in;
 
    44         delete[] arc_source;
 
    44         delete[] arc_source;
 
    45         delete[] arc_target;
 
    45         delete[] arc_target;
 
    46         delete[] arc_next_out;
 
    46         delete[] arc_next_out;
 
   126     
   126     
   127   public:
 
   127   public:
 
   128 
   128 
   129     typedef True BuildTag;
 
   129     typedef True BuildTag;
 
   130     
   130     
   131     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
 
   131     void clear() {
 
   132     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
 
   132       if (built) {
 
   133 
       
   134       if (node_num != -1) {
 
       
   135         delete[] node_first_out;
 
   133         delete[] node_first_out;
 
   136         delete[] node_first_in;
 
   134         delete[] node_first_in;
 
   137         delete[] arc_source;
 
   135         delete[] arc_source;
 
   138         delete[] arc_target;
 
   136         delete[] arc_target;
 
   139         delete[] arc_next_out;
 
   137         delete[] arc_next_out;
 
   140         delete[] arc_next_in;
 
   138         delete[] arc_next_in;
 
   141       }
 
   139       }
 
   142 
   140       built = false;
 
       
   141       node_num = 0;
 
       
   142       arc_num = 0;
 
       
   143     }
 
       
   144     
       
   145     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
 
       
   146     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
 
   143       typedef typename Digraph::Node GNode;
 
   147       typedef typename Digraph::Node GNode;
 
   144       typedef typename Digraph::Arc GArc;
 
   148       typedef typename Digraph::Arc GArc;
 
       
   149 
       
   150       built = true;
 
   145 
   151 
   146       node_num = countNodes(digraph);
 
   152       node_num = countNodes(digraph);
 
   147       arc_num = countArcs(digraph);
 
   153       arc_num = countArcs(digraph);
 
   148 
   154 
   149       node_first_out = new int[node_num + 1];
 
   155       node_first_out = new int[node_num + 1];
 
   203     }
 
   209     }
 
   204     void fastLastOut(Arc& e, const Node& n) const {
 
   210     void fastLastOut(Arc& e, const Node& n) const {
 
   205       e.id = node_first_out[n.id + 1];
 
   211       e.id = node_first_out[n.id + 1];
 
   206     }
 
   212     }
 
   207 
   213 
   208   private:
 
   214   protected:
 
       
   215     bool built;
 
   209     int node_num;
 
   216     int node_num;
 
   210     int arc_num;
 
   217     int arc_num;
 
   211     int *node_first_out;
 
   218     int *node_first_out;
 
   212     int *node_first_in;
 
   219     int *node_first_in;
 
   213     int *arc_source;
 
   220     int *arc_source;
 
   221 
   228 
   222   class StaticDigraph : public ExtendedStaticDigraphBase {
 
   229   class StaticDigraph : public ExtendedStaticDigraphBase {
 
   223   public:
 
   230   public:
 
   224 
   231 
   225     typedef ExtendedStaticDigraphBase Parent;
 
   232     typedef ExtendedStaticDigraphBase Parent;
 
       
   233   
       
   234   public:
 
       
   235   
       
   236     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
 
       
   237     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
 
       
   238       if (built) Parent::clear();
 
       
   239       Parent::build(digraph, nodeRef, arcRef);
 
       
   240     }
 
       
   241   
   226 
   242 
   227   protected:
 
   243   protected:
 
   228 
   244 
   229     using Parent::fastFirstOut;
 
   245     using Parent::fastFirstOut;
 
   230     using Parent::fastNextOut;
 
   246     using Parent::fastNextOut;
 
   259 
   275 
   260     private:
 
   276     private:
 
   261       Arc last;
 
   277       Arc last;
 
   262     };
 
   278     };
 
   263 
   279 
       
   280     Node baseNode(const OutArcIt &arc) const {
 
       
   281       return Parent::source(static_cast<const Arc&>(arc));
 
       
   282     }
 
       
   283 
       
   284     Node runningNode(const OutArcIt &arc) const {
 
       
   285       return Parent::target(static_cast<const Arc&>(arc));
 
       
   286     }
 
       
   287 
       
   288     Node baseNode(const InArcIt &arc) const {
 
       
   289       return Parent::target(static_cast<const Arc&>(arc));
 
       
   290     }
 
       
   291 
       
   292     Node runningNode(const InArcIt &arc) const {
 
       
   293       return Parent::source(static_cast<const Arc&>(arc));
 
       
   294     }
 
       
   295 
   264   };
 
   296   };
 
   265 
   297 
   266 }
 
   298 }
 
   267 
   299 
   268 #endif
 
   300 #endif
lemon