lemon/euler.h
changeset 561 6e0525ec5355
parent 522 22f932bbb305
child 586 7c12061bd271
equal deleted inserted replaced
2:8a6da54f2a10 3:914755a39ad2
    52   ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
    52   ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
    53   ///    et.push_back(e);
    53   ///    et.push_back(e);
    54   ///\endcode
    54   ///\endcode
    55   ///If \c g is not Euler then the resulted tour will not be full or closed.
    55   ///If \c g is not Euler then the resulted tour will not be full or closed.
    56   ///\sa EulerIt
    56   ///\sa EulerIt
    57   template<class Digraph>
    57   template<typename GR>
    58   class DiEulerIt
    58   class DiEulerIt
    59   {
    59   {
    60     typedef typename Digraph::Node Node;
    60     typedef typename GR::Node Node;
    61     typedef typename Digraph::NodeIt NodeIt;
    61     typedef typename GR::NodeIt NodeIt;
    62     typedef typename Digraph::Arc Arc;
    62     typedef typename GR::Arc Arc;
    63     typedef typename Digraph::ArcIt ArcIt;
    63     typedef typename GR::ArcIt ArcIt;
    64     typedef typename Digraph::OutArcIt OutArcIt;
    64     typedef typename GR::OutArcIt OutArcIt;
    65     typedef typename Digraph::InArcIt InArcIt;
    65     typedef typename GR::InArcIt InArcIt;
    66 
    66 
    67     const Digraph &g;
    67     const GR &g;
    68     typename Digraph::template NodeMap<OutArcIt> nedge;
    68     typename GR::template NodeMap<OutArcIt> nedge;
    69     std::list<Arc> euler;
    69     std::list<Arc> euler;
    70 
    70 
    71   public:
    71   public:
    72 
    72 
    73     ///Constructor
    73     ///Constructor
    74 
    74 
    75     ///\param _g A digraph.
    75     ///\param gr A digraph.
    76     ///\param start The starting point of the tour. If it is not given
    76     ///\param start The starting point of the tour. If it is not given
    77     ///       the tour will start from the first node.
    77     ///       the tour will start from the first node.
    78     DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
    78     DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
    79       : g(_g), nedge(g)
    79       : g(gr), nedge(g)
    80     {
    80     {
    81       if(start==INVALID) start=NodeIt(g);
    81       if(start==INVALID) start=NodeIt(g);
    82       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
    82       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
    83       while(nedge[start]!=INVALID) {
    83       while(nedge[start]!=INVALID) {
    84         euler.push_back(nedge[start]);
    84         euler.push_back(nedge[start]);
   143   ///it still returns Arcs in order to indicate the direction of the tour.
   143   ///it still returns Arcs in order to indicate the direction of the tour.
   144   ///(But Arc will convert to Edges, of course).
   144   ///(But Arc will convert to Edges, of course).
   145   ///
   145   ///
   146   ///If \c g is not Euler then the resulted tour will not be full or closed.
   146   ///If \c g is not Euler then the resulted tour will not be full or closed.
   147   ///\sa EulerIt
   147   ///\sa EulerIt
   148   template<class Digraph>
   148   template<typename GR>
   149   class EulerIt
   149   class EulerIt
   150   {
   150   {
   151     typedef typename Digraph::Node Node;
   151     typedef typename GR::Node Node;
   152     typedef typename Digraph::NodeIt NodeIt;
   152     typedef typename GR::NodeIt NodeIt;
   153     typedef typename Digraph::Arc Arc;
   153     typedef typename GR::Arc Arc;
   154     typedef typename Digraph::Edge Edge;
   154     typedef typename GR::Edge Edge;
   155     typedef typename Digraph::ArcIt ArcIt;
   155     typedef typename GR::ArcIt ArcIt;
   156     typedef typename Digraph::OutArcIt OutArcIt;
   156     typedef typename GR::OutArcIt OutArcIt;
   157     typedef typename Digraph::InArcIt InArcIt;
   157     typedef typename GR::InArcIt InArcIt;
   158 
   158 
   159     const Digraph &g;
   159     const GR &g;
   160     typename Digraph::template NodeMap<OutArcIt> nedge;
   160     typename GR::template NodeMap<OutArcIt> nedge;
   161     typename Digraph::template EdgeMap<bool> visited;
   161     typename GR::template EdgeMap<bool> visited;
   162     std::list<Arc> euler;
   162     std::list<Arc> euler;
   163 
   163 
   164   public:
   164   public:
   165 
   165 
   166     ///Constructor
   166     ///Constructor
   167 
   167 
   168     ///\param _g An graph.
   168     ///\param gr An graph.
   169     ///\param start The starting point of the tour. If it is not given
   169     ///\param start The starting point of the tour. If it is not given
   170     ///       the tour will start from the first node.
   170     ///       the tour will start from the first node.
   171     EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
   171     EulerIt(const GR &gr, typename GR::Node start = INVALID)
   172       : g(_g), nedge(g), visited(g,false)
   172       : g(gr), nedge(g), visited(g, false)
   173     {
   173     {
   174       if(start==INVALID) start=NodeIt(g);
   174       if(start==INVALID) start=NodeIt(g);
   175       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
   175       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
   176       while(nedge[start]!=INVALID) {
   176       while(nedge[start]!=INVALID) {
   177         euler.push_back(nedge[start]);
   177         euler.push_back(nedge[start]);
   236   ///arcs are the same for each node.
   236   ///arcs are the same for each node.
   237   ///Similarly, an undirected graph is called \e Eulerian if
   237   ///Similarly, an undirected graph is called \e Eulerian if
   238   ///and only if it is connected and the number of incident arcs is even
   238   ///and only if it is connected and the number of incident arcs is even
   239   ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
   239   ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
   240   ///but still have an Euler tour</em>.
   240   ///but still have an Euler tour</em>.
   241   template<class Digraph>
   241   template<typename GR>
   242 #ifdef DOXYGEN
   242 #ifdef DOXYGEN
   243   bool
   243   bool
   244 #else
   244 #else
   245   typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
   245   typename enable_if<UndirectedTagIndicator<GR>,bool>::type
   246   eulerian(const Digraph &g)
   246   eulerian(const GR &g)
   247   {
   247   {
   248     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
   248     for(typename GR::NodeIt n(g);n!=INVALID;++n)
   249       if(countIncEdges(g,n)%2) return false;
   249       if(countIncEdges(g,n)%2) return false;
   250     return connected(g);
   250     return connected(g);
   251   }
   251   }
   252   template<class Digraph>
   252   template<class GR>
   253   typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
   253   typename disable_if<UndirectedTagIndicator<GR>,bool>::type
   254 #endif
   254 #endif
   255   eulerian(const Digraph &g)
   255   eulerian(const GR &g)
   256   {
   256   {
   257     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
   257     for(typename GR::NodeIt n(g);n!=INVALID;++n)
   258       if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   258       if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   259     return connected(Undirector<const Digraph>(g));
   259     return connected(Undirector<const GR>(g));
   260   }
   260   }
   261 
   261 
   262 }
   262 }
   263 
   263 
   264 #endif
   264 #endif