COIN-OR::LEMON - Graph Library

Changeset 1233:f3d856bf1ebf in lemon-0.x


Ignore:
Timestamp:
03/21/05 12:40:08 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1660
Message:

Several serious bugs fixed

Location:
src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/dfs.h

    r1220 r1233  
    526526        _reached->set(m,true);
    527527        //        _pred_node->set(m,G->source(e));
    528         _stack[++_stack_head] = OutEdgeIt(*G, m);
     528        ++_stack_head;
     529        _stack[_stack_head] = OutEdgeIt(*G, m);
    529530        _dist->set(m,_stack_head);
    530531      }
     
    588589    void start(Node dest)
    589590    {
    590       while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge();
     591      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
     592        processNextEdge();
    591593    }
    592594   
     
    598600    ///with addSource() before using this function.
    599601    ///
    600     ///\param nm must be a bool (or convertible) node map. The algorithm
    601     ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
     602    ///\param nm must be a bool (or convertible) edge map. The algorithm
     603    ///will stop when it reaches a edge \c v with <tt>nm[v]==true</tt>.
     604    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c mn is an edge map,
     605    ///not a node map.
    602606    template<class NM>
    603607      void start(const NM &nm)
    604608      {
    605         while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge();
     609        while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
    606610      }
    607611   
     
    644648      addSource(s);
    645649      start(t);
    646       return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
     650      return reached(t)?_stack_head+1:0;
    647651    }
    648652   
  • src/test/dfs_test.cc

    r1220 r1233  
    110110      check(u==dfs_test.predNode(v),"Wrong tree.");
    111111      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
    112             "Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) );
     112            "Wrong distance. (" << dfs_test.dist(u) << "->"
     113            <<dfs_test.dist(v) << ')');
    113114    }
    114115  }
Note: See TracChangeset for help on using the changeset viewer.