COIN-OR::LEMON - Graph Library

Changeset 577:e8703f0a6e2f in lemon-0.x for src/work/marci/bfs_dfs_misc.h


Ignore:
Timestamp:
05/07/04 13:57:34 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@753
Message:

top-sort, dimacs mods.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/bfs_dfs_misc.h

    r552 r577  
    4040  /// I think the final version will work as an iterator
    4141  /// if the graph is not a acyclic, the na pre-topological order is obtained
    42   /// (see Schrijver's book)
    43   template<typename Graph>
    44   void topSort(const Graph& g, std::list<typename Graph::Node>& l) {
     42  /// (see Schrijver's book).
     43  /// PredMap have to be a writtable node-map.
     44  /// If the graph is directed and not acyclic,
     45  /// then going back from the returned node via the pred information, a
     46  /// cycle is obtained.
     47  template<typename Graph, typename PredMap>
     48  typename Graph::Node
     49  topSort(const Graph& g, std::list<typename Graph::Node>& l,
     50               PredMap& pred) {
    4551    l.clear();
    4652    typedef typename Graph::template NodeMap<bool> ReachedMap;
     53    typedef typename Graph::template NodeMap<bool> ExaminedMap;   
    4754    ReachedMap reached(g/*, false*/);
     55    ExaminedMap examined(g/*, false*/);
    4856    DfsIterator<Graph, ReachedMap> dfs(g, reached);
    4957    FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
    5058      if (!reached[n]) {
    5159        dfs.pushAndSetReached(n);
     60        pred.set(n, INVALID);
    5261        while (!dfs.finished()) {
    5362          ++dfs;
     63          if (dfs.isBNodeNewlyReached()) {
     64            ///\bug hugo 0.2-ben Edge kell
     65            pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
     66          } else {
     67            ///\bug ugyanaz
     68            if (g.valid(typename Graph::OutEdgeIt(dfs)) &&
     69                !examined[dfs.bNode()]) {
     70              ///\bug hugo 0.2-ben Edge kell
     71              pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
     72              return dfs.aNode();
     73            }
     74          }
    5475          if (dfs.isANodeExamined()) {
    5576            l.push_back(dfs.aNode());
     77            examined.set(dfs.aNode(), true);
    5678          }
    5779        }
    5880      }
    5981    }
     82    return INVALID;
    6083  }
    6184} //namespace hugo
Note: See TracChangeset for help on using the changeset viewer.