COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 639:72ac25ad276e in lemon-main


Ignore:
Timestamp:
04/29/09 17:55:27 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
638:57e6f560fb13 (diff), 512:32fb28fc9d42 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • lemon/Makefile.am

    r512 r639  
    88
    99lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    11         lemon/base.cc \
    12         lemon/color.cc \
    13         lemon/random.cc \
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/lp_base.cc \
     14        lemon/lp_skeleton.cc \
     15        lemon/random.cc \
    1416        lemon/bits/windows.cc
    1517
    16 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    17 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     18nodist_lemon_HEADERS = lemon/config.h   
     19       
     20lemon_libemon_la_CXXFLAGS = \
     21        $(AM_CXXFLAGS) \
     22        $(GLPK_CFLAGS) \
     23        $(CPLEX_CFLAGS) \
     24        $(SOPLEX_CXXFLAGS) \
     25        $(CLP_CXXFLAGS) \
     26        $(CBC_CXXFLAGS)
    1827
    19 nodist_lemon_HEADERS = lemon/config.h
     28lemon_libemon_la_LDFLAGS = \
     29        $(GLPK_LIBS) \
     30        $(CPLEX_LIBS) \
     31        $(SOPLEX_LIBS) \
     32        $(CLP_LIBS) \
     33        $(CBC_LIBS)
     34
     35if HAVE_GLPK
     36lemon_libemon_la_SOURCES += lemon/glpk.cc
     37endif
     38
     39if HAVE_CPLEX
     40lemon_libemon_la_SOURCES += lemon/cplex.cc
     41endif
     42
     43if HAVE_SOPLEX
     44lemon_libemon_la_SOURCES += lemon/soplex.cc
     45endif
     46
     47if HAVE_CLP
     48lemon_libemon_la_SOURCES += lemon/clp.cc
     49endif
     50
     51if HAVE_CBC
     52lemon_libemon_la_SOURCES += lemon/cbc.cc
     53endif
    2054
    2155lemon_HEADERS += \
    22         lemon/arg_parser.h \
     56        lemon/adaptors.h \
     57        lemon/arg_parser.h \
    2358        lemon/assert.h \
    24         lemon/bfs.h \
    25         lemon/bin_heap.h \
    26         lemon/color.h \
     59        lemon/bfs.h \
     60        lemon/bin_heap.h \
     61        lemon/cbc.h \
     62        lemon/circulation.h \
     63        lemon/clp.h \
     64        lemon/color.h \
    2765        lemon/concept_check.h \
    28         lemon/counter.h \
     66        lemon/connectivity.h \
     67        lemon/counter.h \
    2968        lemon/core.h \
    30         lemon/dfs.h \
    31         lemon/dijkstra.h \
    32         lemon/dim2.h \
     69        lemon/cplex.h \
     70        lemon/dfs.h \
     71        lemon/dijkstra.h \
     72        lemon/dim2.h \
     73        lemon/dimacs.h \
     74        lemon/edge_set.h \
     75        lemon/elevator.h \
    3376        lemon/error.h \
    34         lemon/graph_to_eps.h \
     77        lemon/euler.h \
     78        lemon/full_graph.h \
     79        lemon/glpk.h \
     80        lemon/gomory_hu.h \
     81        lemon/graph_to_eps.h \
     82        lemon/grid_graph.h \
     83        lemon/hypercube_graph.h \
    3584        lemon/kruskal.h \
     85        lemon/hao_orlin.h \
    3686        lemon/lgf_reader.h \
    3787        lemon/lgf_writer.h \
    3888        lemon/list_graph.h \
     89        lemon/lp.h \
     90        lemon/lp_base.h \
     91        lemon/lp_skeleton.h \
     92        lemon/list_graph.h \
    3993        lemon/maps.h \
     94        lemon/matching.h \
    4095        lemon/math.h \
     96        lemon/min_cost_arborescence.h \
     97        lemon/nauty_reader.h \
     98        lemon/network_simplex.h \
    4199        lemon/path.h \
    42         lemon/random.h \
     100        lemon/preflow.h \
     101        lemon/radix_sort.h \
     102        lemon/random.h \
    43103        lemon/smart_graph.h \
    44         lemon/time_measure.h \
    45         lemon/tolerance.h \
     104        lemon/soplex.h \
     105        lemon/suurballe.h \
     106        lemon/time_measure.h \
     107        lemon/tolerance.h \
    46108        lemon/unionfind.h \
    47109        lemon/bits/windows.h
    … …  
    51113        lemon/bits/array_map.h \
    52114        lemon/bits/base_extender.h \
    53         lemon/bits/bezier.h \
     115        lemon/bits/bezier.h \
    54116        lemon/bits/default_map.h \
    55         lemon/bits/enable_if.h \
     117        lemon/bits/edge_set_extender.h \
     118        lemon/bits/enable_if.h \
     119        lemon/bits/graph_adaptor_extender.h \
    56120        lemon/bits/graph_extender.h \
    57121        lemon/bits/map_extender.h \
    58122        lemon/bits/path_dump.h \
     123        lemon/bits/solver_bits.h \
    59124        lemon/bits/traits.h \
     125        lemon/bits/variant.h \
    60126        lemon/bits/vector_map.h
    61127

  • lemon/Makefile.am

    r630 r639  
    1616        lemon/bits/windows.cc
    1717
    18 
     18nodist_lemon_HEADERS = lemon/config.h   
     19       
    1920lemon_libemon_la_CXXFLAGS = \
    2021        $(AM_CXXFLAGS) \
    … …  
    6364        lemon/color.h \
    6465        lemon/concept_check.h \
    65         lemon/config.h \
    6666        lemon/connectivity.h \
    6767        lemon/counter.h \

  • lemon/core.h

    r512 r639  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    10351035  ///\sa findArc()
    10361036  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    1037   template <typename _Graph>
    1038   class ConArcIt : public _Graph::Arc {
     1037  template <typename GR>
     1038  class ConArcIt : public GR::Arc {
     1039    typedef typename GR::Arc Parent;
     1040
    10391041  public:
    10401042
    1041     typedef _Graph Graph;
    1042     typedef typename Graph::Arc Parent;
    1043 
    1044     typedef typename Graph::Arc Arc;
    1045     typedef typename Graph::Node Node;
     1043    typedef typename GR::Arc Arc;
     1044    typedef typename GR::Node Node;
    10461045
    10471046    /// \brief Constructor.
    … …  
    10491048    /// Construct a new ConArcIt iterating on the arcs that
    10501049    /// connects nodes \c u and \c v.
    1051     ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
     1050    ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
    10521051      Parent::operator=(findArc(_graph, u, v));
    10531052    }
    … …  
    10561055    ///
    10571056    /// Construct a new ConArcIt that continues the iterating from arc \c a.
    1058     ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
     1057    ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
    10591058
    10601059    /// \brief Increment operator.
    … …  
    10671066    }
    10681067  private:
    1069     const Graph& _graph;
     1068    const GR& _graph;
    10701069  };
    10711070
    … …  
    11581157  ///
    11591158  ///\sa findEdge()
    1160   template <typename _Graph>
    1161   class ConEdgeIt : public _Graph::Edge {
     1159  template <typename GR>
     1160  class ConEdgeIt : public GR::Edge {
     1161    typedef typename GR::Edge Parent;
     1162
    11621163  public:
    11631164
    1164     typedef _Graph Graph;
    1165     typedef typename Graph::Edge Parent;
    1166 
    1167     typedef typename Graph::Edge Edge;
    1168     typedef typename Graph::Node Node;
     1165    typedef typename GR::Edge Edge;
     1166    typedef typename GR::Node Node;
    11691167
    11701168    /// \brief Constructor.
    … …  
    11721170    /// Construct a new ConEdgeIt iterating on the edges that
    11731171    /// connects nodes \c u and \c v.
    1174     ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
     1172    ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
    11751173      Parent::operator=(findEdge(_graph, _u, _v));
    11761174    }
    … …  
    11791177    ///
    11801178    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
    1181     ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
     1179    ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
    11821180
    11831181    /// \brief Increment operator.
    … …  
    11891187    }
    11901188  private:
    1191     const Graph& _graph;
     1189    const GR& _graph;
    11921190    Node _u, _v;
    11931191  };
    … …  
    12121210  ///queries.
    12131211  ///
    1214   ///\tparam G The type of the underlying digraph.
     1212  ///\tparam GR The type of the underlying digraph.
    12151213  ///
    12161214  ///\sa ArcLookUp
    12171215  ///\sa AllArcLookUp
    1218   template<class G>
     1216  template <typename GR>
    12191217  class DynArcLookUp
    1220     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
     1218    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
    12211219  {
     1220    typedef typename ItemSetTraits<GR, typename GR::Arc>
     1221    ::ItemNotifier::ObserverBase Parent;
     1222
     1223    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1224
    12221225  public:
    1223     typedef typename ItemSetTraits<G, typename G::Arc>
    1224     ::ItemNotifier::ObserverBase Parent;
    1225 
    1226     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1227     typedef G Digraph;
     1226
     1227    /// The Digraph type
     1228    typedef GR Digraph;
    12281229
    12291230  protected:
    12301231
    1231     class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
     1232    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1233      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
     1234
    12321235    public:
    12331236
    1234       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
    1235 
    1236       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
     1237      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    12371238
    12381239      virtual void add(const Node& node) {
    … …  
    12571258      }
    12581259    };
    1259 
    1260     const Digraph &_g;
    1261     AutoNodeMap _head;
    1262     typename Digraph::template ArcMap<Arc> _parent;
    1263     typename Digraph::template ArcMap<Arc> _left;
    1264     typename Digraph::template ArcMap<Arc> _right;
    12651260
    12661261    class ArcLess {
    … …  
    12741269    };
    12751270
     1271  protected:
     1272
     1273    const Digraph &_g;
     1274    AutoNodeMap _head;
     1275    typename Digraph::template ArcMap<Arc> _parent;
     1276    typename Digraph::template ArcMap<Arc> _left;
     1277    typename Digraph::template ArcMap<Arc> _right;
     1278
    12761279  public:
    12771280
    … …  
    13161319    virtual void clear() {
    13171320      for(NodeIt n(_g);n!=INVALID;++n) {
    1318         _head.set(n, INVALID);
     1321        _head[n] = INVALID;
    13191322      }
    13201323    }
    … …  
    13231326      Node s = _g.source(arc);
    13241327      Node t = _g.target(arc);
    1325       _left.set(arc, INVALID);
    1326       _right.set(arc, INVALID);
     1328      _left[arc] = INVALID;
     1329      _right[arc] = INVALID;
    13271330
    13281331      Arc e = _head[s];
    13291332      if (e == INVALID) {
    1330         _head.set(s, arc);
    1331         _parent.set(arc, INVALID);
     1333        _head[s] = arc;
     1334        _parent[arc] = INVALID;
    13321335        return;
    13331336      }
    … …  
    13351338        if (t < _g.target(e)) {
    13361339          if (_left[e] == INVALID) {
    1337             _left.set(e, arc);
    1338             _parent.set(arc, e);
     1340            _left[e] = arc;
     1341            _parent[arc] = e;
    13391342            splay(arc);
    13401343            return;
    … …  
    13441347        } else {
    13451348          if (_right[e] == INVALID) {
    1346             _right.set(e, arc);
    1347             _parent.set(arc, e);
     1349            _right[e] = arc;
     1350            _parent[arc] = e;
    13481351            splay(arc);
    13491352            return;
    … …  
    13581361      if (_left[arc] == INVALID) {
    13591362        if (_right[arc] != INVALID) {
    1360           _parent.set(_right[arc], _parent[arc]);
     1363          _parent[_right[arc]] = _parent[arc];
    13611364        }
    13621365        if (_parent[arc] != INVALID) {
    13631366          if (_left[_parent[arc]] == arc) {
    1364             _left.set(_parent[arc], _right[arc]);
     1367            _left[_parent[arc]] = _right[arc];
    13651368          } else {
    1366             _right.set(_parent[arc], _right[arc]);
     1369            _right[_parent[arc]] = _right[arc];
    13671370          }
    13681371        } else {
    1369           _head.set(_g.source(arc), _right[arc]);
     1372          _head[_g.source(arc)] = _right[arc];
    13701373        }
    13711374      } else if (_right[arc] == INVALID) {
    1372         _parent.set(_left[arc], _parent[arc]);
     1375        _parent[_left[arc]] = _parent[arc];
    13731376        if (_parent[arc] != INVALID) {
    13741377          if (_left[_parent[arc]] == arc) {
    1375             _left.set(_parent[arc], _left[arc]);
     1378            _left[_parent[arc]] = _left[arc];
    13761379          } else {
    1377             _right.set(_parent[arc], _left[arc]);
     1380            _right[_parent[arc]] = _left[arc];
    13781381          }
    13791382        } else {
    1380           _head.set(_g.source(arc), _left[arc]);
     1383          _head[_g.source(arc)] = _left[arc];
    13811384        }
    13821385      } else {
    … …  
    13881391          }
    13891392          Arc s = _parent[e];
    1390           _right.set(_parent[e], _left[e]);
     1393          _right[_parent[e]] = _left[e];
    13911394          if (_left[e] != INVALID) {
    1392             _parent.set(_left[e], _parent[e]);
     1395            _parent[_left[e]] = _parent[e];
    13931396          }
    13941397
    1395           _left.set(e, _left[arc]);
    1396           _parent.set(_left[arc], e);
    1397           _right.set(e, _right[arc]);
    1398           _parent.set(_right[arc], e);
    1399 
    1400           _parent.set(e, _parent[arc]);
     1398          _left[e] = _left[arc];
     1399          _parent[_left[arc]] = e;
     1400          _right[e] = _right[arc];
     1401          _parent[_right[arc]] = e;
     1402
     1403          _parent[e] = _parent[arc];
    14011404          if (_parent[arc] != INVALID) {
    14021405            if (_left[_parent[arc]] == arc) {
    1403               _left.set(_parent[arc], e);
     1406              _left[_parent[arc]] = e;
    14041407            } else {
    1405               _right.set(_parent[arc], e);
     1408              _right[_parent[arc]] = e;
    14061409            }
    14071410          }
    14081411          splay(s);
    14091412        } else {
    1410           _right.set(e, _right[arc]);
    1411           _parent.set(_right[arc], e);
    1412           _parent.set(e, _parent[arc]);
     1413          _right[e] = _right[arc];
     1414          _parent[_right[arc]] = e;
     1415          _parent[e] = _parent[arc];
    14131416
    14141417          if (_parent[arc] != INVALID) {
    14151418            if (_left[_parent[arc]] == arc) {
    1416               _left.set(_parent[arc], e);
     1419              _left[_parent[arc]] = e;
    14171420            } else {
    1418               _right.set(_parent[arc], e);
     1421              _right[_parent[arc]] = e;
    14191422            }
    14201423          } else {
    1421             _head.set(_g.source(arc), e);
     1424            _head[_g.source(arc)] = e;
    14221425          }
    14231426        }
    … …  
    14311434      if (a < m) {
    14321435        Arc left = refreshRec(v,a,m-1);
    1433         _left.set(me, left);
    1434         _parent.set(left, me);
     1436        _left[me] = left;
     1437        _parent[left] = me;
    14351438      } else {
    1436         _left.set(me, INVALID);
     1439        _left[me] = INVALID;
    14371440      }
    14381441      if (m < b) {
    14391442        Arc right = refreshRec(v,m+1,b);
    1440         _right.set(me, right);
    1441         _parent.set(right, me);
     1443        _right[me] = right;
     1444        _parent[right] = me;
    14421445      } else {
    1443         _right.set(me, INVALID);
     1446        _right[me] = INVALID;
    14441447      }
    14451448      return me;
    … …  
    14531456          std::sort(v.begin(),v.end(),ArcLess(_g));
    14541457          Arc head = refreshRec(v,0,v.size()-1);
    1455           _head.set(n, head);
    1456           _parent.set(head, INVALID);
    1457         }
    1458         else _head.set(n, INVALID);
     1458          _head[n] = head;
     1459          _parent[head] = INVALID;
     1460        }
     1461        else _head[n] = INVALID;
    14591462      }
    14601463    }
    … …  
    14621465    void zig(Arc v) {
    14631466      Arc w = _parent[v];
    1464       _parent.set(v, _parent[w]);
    1465       _parent.set(w, v);
    1466       _left.set(w, _right[v]);
    1467       _right.set(v, w);
     1467      _parent[v] = _parent[w];
     1468      _parent[w] = v;
     1469      _left[w] = _right[v];
     1470      _right[v] = w;
    14681471      if (_parent[v] != INVALID) {
    14691472        if (_right[_parent[v]] == w) {
    1470           _right.set(_parent[v], v);
     1473          _right[_parent[v]] = v;
    14711474        } else {
    1472           _left.set(_parent[v], v);
     1475          _left[_parent[v]] = v;
    14731476        }
    14741477      }
    14751478      if (_left[w] != INVALID){
    1476         _parent.set(_left[w], w);
     1479        _parent[_left[w]] = w;
    14771480      }
    14781481    }
    … …  
    14801483    void zag(Arc v) {
    14811484      Arc w = _parent[v];
    1482       _parent.set(v, _parent[w]);
    1483       _parent.set(w, v);
    1484       _right.set(w, _left[v]);
    1485       _left.set(v, w);
     1485      _parent[v] = _parent[w];
     1486      _parent[w] = v;
     1487      _right[w] = _left[v];
     1488      _left[v] = w;
    14861489      if (_parent[v] != INVALID){
    14871490        if (_left[_parent[v]] == w) {
    1488           _left.set(_parent[v], v);
     1491          _left[_parent[v]] = v;
    14891492        } else {
    1490           _right.set(_parent[v], v);
     1493          _right[_parent[v]] = v;
    14911494        }
    14921495      }
    14931496      if (_right[w] != INVALID){
    1494         _parent.set(_right[w], w);
     1497        _parent[_right[w]] = w;
    14951498      }
    14961499    }
    … …  
    16241627  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    16251628  ///
    1626   ///\tparam G The type of the underlying digraph.
     1629  ///\tparam GR The type of the underlying digraph.
    16271630  ///
    16281631  ///\sa DynArcLookUp
    16291632  ///\sa AllArcLookUp
    1630   template<class G>
     1633  template<class GR>
    16311634  class ArcLookUp
    16321635  {
     1636    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1637
    16331638  public:
    1634     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1635     typedef G Digraph;
     1639
     1640    /// The Digraph type
     1641    typedef GR Digraph;
    16361642
    16371643  protected:
    … …  
    17341740  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    17351741  ///
    1736   ///\tparam G The type of the underlying digraph.
     1742  ///\tparam GR The type of the underlying digraph.
    17371743  ///
    17381744  ///\sa DynArcLookUp
    17391745  ///\sa ArcLookUp
    1740   template<class G>
    1741   class AllArcLookUp : public ArcLookUp<G>
     1746  template<class GR>
     1747  class AllArcLookUp : public ArcLookUp<GR>
    17421748  {
    1743     using ArcLookUp<G>::_g;
    1744     using ArcLookUp<G>::_right;
    1745     using ArcLookUp<G>::_left;
    1746     using ArcLookUp<G>::_head;
    1747 
    1748     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1749     typedef G Digraph;
    1750 
    1751     typename Digraph::template ArcMap<Arc> _next;
     1749    using ArcLookUp<GR>::_g;
     1750    using ArcLookUp<GR>::_right;
     1751    using ArcLookUp<GR>::_left;
     1752    using ArcLookUp<GR>::_head;
     1753
     1754    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1755
     1756    typename GR::template ArcMap<Arc> _next;
    17521757
    17531758    Arc refreshNext(Arc head,Arc next=INVALID)
    … …  
    17681773
    17691774  public:
     1775
     1776    /// The Digraph type
     1777    typedef GR Digraph;
     1778
    17701779    ///Constructor
    17711780
    … …  
    17741783    ///It builds up the search database, which remains valid until the digraph
    17751784    ///changes.
    1776     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
     1785    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
    17771786
    17781787    ///Refresh the data structure at a node.
    … …  
    17841793    void refresh(Node n)
    17851794    {
    1786       ArcLookUp<G>::refresh(n);
     1795      ArcLookUp<GR>::refresh(n);
    17871796      refreshNext(_head[n]);
    17881797    }
    … …  
    18311840    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
    18321841#else
    1833     using ArcLookUp<G>::operator() ;
     1842    using ArcLookUp<GR>::operator() ;
    18341843    Arc operator()(Node s, Node t, Arc prev) const
    18351844    {

  • lemon/core.h

    r617 r639  
    2323#include <algorithm>
    2424
    25 #include <lemon/core.h>
     25#include <lemon/config.h>
    2626#include <lemon/bits/enable_if.h>
    2727#include <lemon/bits/traits.h>
Note: See TracChangeset for help on using the changeset viewer.