COIN-OR::LEMON - Graph Library

Changeset 2020:332245399dc6 in lemon-0.x for lemon/graph_utils.h


Ignore:
Timestamp:
03/30/06 10:38:41 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2658
Message:

Rewritten countItems and findEdges

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r2006 r2020  
    103103  /// it iterates on all of the items.
    104104
    105   template <typename Graph, typename ItemIt>
     105  template <typename Graph, typename Item>
    106106  inline int countItems(const Graph& g) {
     107    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
    107108    int num = 0;
    108109    for (ItemIt it(g); it != INVALID; ++it) {
     
    114115  // Node counting:
    115116
    116   template <typename Graph>
    117   inline typename enable_if<typename Graph::NodeNumTag, int>::type
    118   _countNodes(const Graph &g) {
    119     return g.nodeNum();
    120   }
    121 
    122   template <typename Graph>
    123   inline int _countNodes(Wrap<Graph> w) {
    124     return countItems<Graph, typename Graph::NodeIt>(w.value);
     117  namespace _graph_utils_bits {
     118   
     119    template <typename Graph, typename Enable = void>
     120    struct CountNodesSelector {
     121      static int count(const Graph &g) {
     122        return countItems<Graph, typename Graph::Node>(g);
     123      }
     124    };
     125
     126    template <typename Graph>
     127    struct CountNodesSelector<
     128      Graph, typename
     129      enable_if<typename Graph::NodeNumTag, void>::type>
     130    {
     131      static int count(const Graph &g) {
     132        return g.nodeNum();
     133      }
     134    };   
    125135  }
    126136
     
    135145  template <typename Graph>
    136146  inline int countNodes(const Graph& g) {
    137     return _countNodes<Graph>(g);
    138   }
     147    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
     148  }
     149
    139150
    140151  // Edge counting:
    141152
    142   template <typename Graph>
    143   inline typename enable_if<typename Graph::EdgeNumTag, int>::type
    144   _countEdges(const Graph &g) {
    145     return g.edgeNum();
    146   }
    147 
    148   template <typename Graph>
    149   inline int _countEdges(Wrap<Graph> w) {
    150     return countItems<Graph, typename Graph::EdgeIt>(w.value);
     153  namespace _graph_utils_bits {
     154   
     155    template <typename Graph, typename Enable = void>
     156    struct CountEdgesSelector {
     157      static int count(const Graph &g) {
     158        return countItems<Graph, typename Graph::Edge>(g);
     159      }
     160    };
     161
     162    template <typename Graph>
     163    struct CountEdgesSelector<
     164      Graph,
     165      typename enable_if<typename Graph::EdgeNumTag, void>::type>
     166    {
     167      static int count(const Graph &g) {
     168        return g.edgeNum();
     169      }
     170    };   
    151171  }
    152172
     
    159179  template <typename Graph>
    160180  inline int countEdges(const Graph& g) {
    161     return _countEdges<Graph>(g);
     181    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
    162182  }
    163183
    164184  // Undirected edge counting:
    165 
    166   template <typename Graph>
    167   inline
    168   typename enable_if<typename Graph::EdgeNumTag, int>::type
    169   _countUEdges(const Graph &g) {
    170     return g.uEdgeNum();
    171   }
    172 
    173   template <typename Graph>
    174   inline int _countUEdges(Wrap<Graph> w) {
    175     return countItems<Graph, typename Graph::UEdgeIt>(w.value);
     185  namespace _graph_utils_bits {
     186   
     187    template <typename Graph, typename Enable = void>
     188    struct CountUEdgesSelector {
     189      static int count(const Graph &g) {
     190        return countItems<Graph, typename Graph::UEdge>(g);
     191      }
     192    };
     193
     194    template <typename Graph>
     195    struct CountUEdgesSelector<
     196      Graph,
     197      typename enable_if<typename Graph::EdgeNumTag, void>::type>
     198    {
     199      static int count(const Graph &g) {
     200        return g.uEdgeNum();
     201      }
     202    };   
    176203  }
    177204
     
    184211  template <typename Graph>
    185212  inline int countUEdges(const Graph& g) {
    186     return _countUEdges<Graph>(g);
    187   }
    188 
     213    return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
     214
     215  }
    189216
    190217
     
    225252  }
    226253
    227 
    228   template <typename Graph>
    229   inline
    230   typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
    231   _findEdge(const Graph &g,
    232             typename Graph::Node u, typename Graph::Node v,
    233             typename Graph::Edge prev = INVALID) {
    234     return g.findEdge(u, v, prev);
    235   }
    236 
    237   template <typename Graph>
    238   inline typename Graph::Edge
    239   _findEdge(Wrap<Graph> w,
    240             typename Graph::Node u,
    241             typename Graph::Node v,
    242             typename Graph::Edge prev = INVALID) {
    243     const Graph& g = w.value;
    244     if (prev == INVALID) {
    245       typename Graph::OutEdgeIt e(g, u);
    246       while (e != INVALID && g.target(e) != v) ++e;
    247       return e;
    248     } else {
    249       typename Graph::OutEdgeIt e(g, prev); ++e;
    250       while (e != INVALID && g.target(e) != v) ++e;
    251       return e;
    252     }
     254  namespace _graph_utils_bits {
     255   
     256    template <typename Graph, typename Enable = void>
     257    struct FindEdgeSelector {
     258      typedef typename Graph::Node Node;
     259      typedef typename Graph::Edge Edge;
     260      static Edge find(const Graph &g, Node u, Node v, Edge e) {
     261        if (e == INVALID) {
     262          g.firstOut(e, u);
     263        } else {
     264          g.nextOut(e);
     265        }
     266        while (e != INVALID && g.target(e) != v) {
     267          g.nextOut(e);
     268        }
     269        return e;
     270      }
     271    };
     272
     273    template <typename Graph>
     274    struct FindEdgeSelector<
     275      Graph,
     276      typename enable_if<typename Graph::FindEdgeTag, void>::type>
     277    {
     278      typedef typename Graph::Node Node;
     279      typedef typename Graph::Edge Edge;
     280      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
     281        return g.findEdge(u, v, prev);
     282      }
     283    };   
    253284  }
    254285
     
    268299  /// }
    269300  ///\endcode
    270   // /// \todo We may want to use the "GraphBase"
    271   // /// interface here...
    272301  template <typename Graph>
    273302  inline typename Graph::Edge findEdge(const Graph &g,
     
    275304                                       typename Graph::Node v,
    276305                                       typename Graph::Edge prev = INVALID) {
    277     return _findEdge<Graph>(g, u, v, prev);
     306    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
    278307  }
    279308
     
    326355  };
    327356
    328   template <typename Graph>
    329   inline
    330   typename enable_if<
    331     typename Graph::FindEdgeTag,
    332     typename Graph::UEdge>::type
    333   _findUEdge(const Graph &g,
    334             typename Graph::Node u, typename Graph::Node v,
    335             typename Graph::UEdge prev = INVALID) {
    336     return g.findUEdge(u, v, prev);
    337   }
    338 
    339   template <typename Graph>
    340   inline typename Graph::UEdge
    341   _findUEdge(Wrap<Graph> w,
    342             typename Graph::Node u,
    343             typename Graph::Node v,
    344             typename Graph::UEdge prev = INVALID) {
    345     const Graph& g = w.value;
    346     if (prev == INVALID) {
    347       typename Graph::OutEdgeIt e(g, u);
    348       while (e != INVALID && g.target(e) != v) ++e;
    349       return e;
    350     } else {
    351       typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
    352       while (e != INVALID && g.target(e) != v) ++e;
    353       return e;
    354     }
     357  namespace _graph_utils_bits {
     358   
     359    template <typename Graph, typename Enable = void>
     360    struct FindUEdgeSelector {
     361      typedef typename Graph::Node Node;
     362      typedef typename Graph::UEdge UEdge;
     363      static UEdge find(const Graph &g, Node u, Node v, UEdge e) {
     364        bool b;
     365        if (u != v) {
     366          if (e == INVALID) {
     367            g.firstInc(e, u, b);
     368          } else {
     369            b = g.source(e) == u;
     370            g.nextInc(e, b);
     371          }
     372          while (e != INVALID && g.target(e) != v) {
     373            g.nextInc(e, b);
     374          }
     375        } else {
     376          if (e == INVALID) {
     377            g.firstInc(e, u, b);
     378          } else {
     379            b = true;
     380            g.nextInc(e, b);
     381          }
     382          while (e != INVALID && (!b || g.target(e) != v)) {
     383            g.nextInc(e, b);
     384          }
     385        }
     386        return e;
     387      }
     388    };
     389
     390    template <typename Graph>
     391    struct FindUEdgeSelector<
     392      Graph,
     393      typename enable_if<typename Graph::FindEdgeTag, void>::type>
     394    {
     395      typedef typename Graph::Node Node;
     396      typedef typename Graph::UEdge UEdge;
     397      static UEdge find(const Graph &g, Node u, Node v, UEdge prev) {
     398        return g.findUEdge(u, v, prev);
     399      }
     400    };   
    355401  }
    356402
     
    358404  ///
    359405  /// Finds an uedge from node \c u to node \c v in graph \c g.
     406  /// If the node \c u and node \c v is equal then each loop edge
     407  /// will be enumerated.
    360408  ///
    361409  /// If \c prev is \ref INVALID (this is the default value), then
     
    371419  /// }
    372420  ///\endcode
    373   // /// \todo We may want to use the "GraphBase"
    374   // /// interface here...
    375421  template <typename Graph>
    376   inline typename Graph::UEdge
    377   findUEdge(const Graph &g,
    378                 typename Graph::Node u,
    379                 typename Graph::Node v,
    380                 typename Graph::UEdge prev = INVALID) {
    381     return _findUEdge<Graph>(g, u, v, prev);
     422  inline typename Graph::UEdge findEdge(const Graph &g,
     423                                        typename Graph::Node u,
     424                                        typename Graph::Node v,
     425                                        typename Graph::UEdge prev = INVALID) {
     426    return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, prev);
    382427  }
    383428
Note: See TracChangeset for help on using the changeset viewer.