COIN-OR::LEMON - Graph Library

Changeset 1449:ac7e995e47e2 in lemon-0.x for lemon/kruskal.h


Ignore:
Timestamp:
06/07/05 18:13:21 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1929
Message:

Modify kruskal to work correctly with UndirGraphs?.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/kruskal.h

    r1435 r1449  
    2020#include <algorithm>
    2121#include <lemon/unionfind.h>
     22#include<lemon/utility.h>
    2223
    2324/**
     
    6768  ///
    6869  /// \return The cost of the found tree.
     70  ///
     71  /// \todo Discuss the case of undirected graphs: In this case the algorithm
     72  /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some
     73  /// people would expect. So, one should be careful not to add both of the
     74  /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>.
     75  /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
    6976
    7077  template <class GR, class IN, class OUT>
     
    167174    };
    168175
     176    template<class _GR>
     177    typename enable_if<typename _GR::UndirTag,void>::type
     178    fillWithEdges(const _GR& G, const Map& m,dummy<0> = 0)
     179    {
     180      for(typename GR::UndirEdgeIt e(G);e!=INVALID;++e)
     181        push_back(value_type(typename GR::Edge(e,true), m[e]));
     182    }
     183
     184    template<class _GR>
     185    typename disable_if<typename _GR::UndirTag,void>::type
     186    fillWithEdges(const _GR& G, const Map& m,dummy<1> = 1)
     187    {
     188      for(typename GR::EdgeIt e(G);e!=INVALID;++e)
     189        push_back(value_type(e, m[e]));
     190    }
     191   
     192   
    169193  public:
    170194
     
    174198
    175199    KruskalMapInput(GR const& G, Map const& m) {
    176       typedef typename GR::EdgeIt EdgeIt;
    177      
    178       for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
     200      fillWithEdges(G,m);
    179201      sort();
    180202    }
Note: See TracChangeset for help on using the changeset viewer.