COIN-OR::LEMON - Graph Library

Changeset 617:dc17013b0e52 in lemon-0.x


Ignore:
Timestamp:
05/11/04 23:26:29 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@802
Message:

bip matching comparison

Location:
src/work
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/makefile

    r577 r617  
    11INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
    2 CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
     2CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
    33
    44BINARIES ?= bin_heap_demo
  • src/work/marci/leda/leda_graph_wrapper.h

    r616 r617  
    1717#include <hugo/invalid.h>
    1818
    19 /// The namespace of HugoLib
    2019namespace hugo {
    2120
    22   // @defgroup empty_graph The LedaGraphWrapper class
    23   // @{
    24 
    25   /// A graph wrapperstructure for wrapping LEDA graphs in HUGO.
    26  
    27   /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph
    28   /// and then the generic algorithms and wrappers of HUGO can be used
     21  /// \brief A graph wrapper structure for wrapping LEDA graphs in HUGO.
     22  ///
     23  /// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs
     24  /// to satisfy HUGO graph concepts.
     25  /// Then the generic HUGOlib algorithms and wrappers can be used
    2926  /// with LEDA graphs.
    30   /// This class provides all the common features of a grapf structure,
    31   /// however completely without implementations or real data structures
    32   /// behind the interface.
    33   /// All graph algorithms should compile with this class, but it will not
    34   /// run properly, of course.
    35   ///
    36   /// It can be used for checking the interface compatibility,
    37   /// or it can serve as a skeleton of a new graph structure.
    38   ///
    39   /// Also, you will find here the full documentation of a certain graph
    40   /// feature, the documentation of a real graph imlementation
    41   /// like @ref ListGraph or
    42   /// @ref SmartGraph will just refer to this structure.
     27  /// \ingroup gwrapper
    4328  template<typename Graph>
    4429  class LedaGraphWrapper
    4530  {
    4631  protected:
    47     Graph* _graph;
    48     LedaGraphWrapper() : _graph(0) { }
    49     void setGraph(Graph& __graph) { _graph=&__graph; }
     32    Graph* l_graph;
     33    LedaGraphWrapper() : l_graph(0) { }
     34    void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }
    5035  public:
    5136   
    5237        //LedaGraphWrapper() { }
    53     LedaGraphWrapper(Graph& __graph) : _graph(&__graph) { }
    54     LedaGraphWrapper(const LedaGraphWrapper &G) : _graph(G._graph) { }
     38    LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }
     39    LedaGraphWrapper(const LedaGraphWrapper &G) : l_graph(G.l_graph) { }
    5540
    5641    template <typename T> class NodeMap;
     
    7358    protected:
    7459      template <typename T> friend class NodeMap;
    75       leda_node _n;
     60      leda_node l_n;
    7661    public: //FIXME
    77       Node(leda_node __n) : _n(__n) { }
     62      Node(leda_node _l_n) : l_n(_l_n) { }
    7863    public:
    7964      /// @warning The default constructor sets the iterator
     
    8166      Node() {}   //FIXME
    8267      /// Initialize the iterator to be invalid
    83       Node(Invalid) : _n(0) { }
     68      Node(Invalid) : l_n(0) { }
    8469      //Node(const Node &) {}
    85       bool operator==(Node n) const { return _n==n._n; } //FIXME
    86       bool operator!=(Node n) const { return _n!=n._n; } //FIXME
    87       operator leda_node () { return _n; }
     70      bool operator==(Node n) const { return l_n==n.l_n; } //FIXME
     71      bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME
     72      operator leda_node () { return l_n; }
    8873    };
    8974   
     
    9782      NodeIt(Invalid i) : Node(i) {}
    9883      /// Sets the iterator to the first node of \c G.
    99       NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
     84      NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }
    10085      //NodeIt(const NodeIt &) {} //FIXME
    10186    };
     
    10691    protected:
    10792      template <typename T> friend class EdgeMap;
    108       leda_edge _e;
     93      leda_edge l_e;
    10994    public: //FIXME
    110       Edge(leda_edge __e) : _e(__e) { }
     95      Edge(leda_edge _l_e) : l_e(_l_e) { }
    11196    public:
    11297      /// @warning The default constructor sets the iterator
     
    11499      Edge() {}   //FIXME
    115100      /// Initialize the iterator to be invalid
    116       Edge(Invalid) : _e(0) {}
     101      Edge(Invalid) : l_e(0) {}
    117102      //Edge(const Edge &) {}
    118       bool operator==(Edge e) const { return _e==e._e; } //FIXME
    119       bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
    120       operator leda_edge () { return _e; }
     103      bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME
     104      bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME
     105      operator leda_edge () { return l_e; }
    121106    };
    122107   
     
    136121      ///@param n the node
    137122      ///@param G the graph
    138       OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
     123      OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }
    139124    };
    140125
     
    146131      /// Initialize the iterator to be invalid
    147132      InEdgeIt(Invalid i) : Edge(i) {}
    148       InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
     133      InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }
    149134    };
    150135
     
    157142      /// Initialize the iterator to be invalid
    158143      EdgeIt(Invalid i) : Edge(i) {}
    159       EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
     144      EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }
    160145    };
    161146
     
    190175    /// Go to the next node.
    191176    NodeIt &next(NodeIt &i) const {
    192       i._n=_graph->succ_node(i._n);
     177      i.l_n=l_graph->succ_node(i.l_n);
    193178      return i;
    194179    }
    195180    /// Go to the next incoming edge.
    196181    InEdgeIt &next(InEdgeIt &i) const {
    197       i._e=_graph->in_succ(i._e);
     182      i.l_e=l_graph->in_succ(i.l_e);
    198183      return i;
    199184    }
    200185    /// Go to the next outgoing edge.
    201186    OutEdgeIt &next(OutEdgeIt &i) const {
    202       i._e=_graph->adj_succ(i._e);
     187      i.l_e=l_graph->adj_succ(i.l_e);
    203188      return i;
    204189    }
     
    206191    /// Go to the next edge.
    207192    EdgeIt &next(EdgeIt &i) const {     
    208       i._e=_graph->succ_edge(i._e);
     193      i.l_e=l_graph->succ_edge(i.l_e);
    209194      return i;
    210195    }
     
    226211    ///Gives back the head node of an edge.
    227212    Node head(Edge e) const {
    228       return Node(_graph->target(e._e));
     213      return Node(l_graph->target(e.l_e));
    229214    }
    230215    ///Gives back the tail node of an edge.
    231216    Node tail(Edge e) const {
    232       return Node(_graph->source(e._e));
     217      return Node(l_graph->source(e.l_e));
    233218    }
    234219 
     
    242227
    243228    /// Checks if a node iterator is valid
    244     bool valid(Node n) const { return n._n; }
     229    bool valid(Node n) const { return n.l_n; }
    245230    /// Checks if an edge iterator is valid
    246     bool valid(Edge e) const { return e._e; }
     231    bool valid(Edge e) const { return e.l_e; }
    247232
    248233    ///Gives back the \e id of a node.
    249     int id(Node n) const { return n._n->id(); }
     234    int id(Node n) const { return n.l_n->id(); }
    250235    ///Gives back the \e id of an edge.
    251     int id(Edge e) const { return e._e->id(); }
     236    int id(Edge e) const { return e.l_e->id(); }
    252237
    253238    //void setInvalid(Node &) const {};
    254239    //void setInvalid(Edge &) const {};
    255240 
    256     Node addNode() const { return Node(_graph->new_node()); }
     241    Node addNode() const { return Node(l_graph->new_node()); }
    257242    Edge addEdge(Node tail, Node head) const {
    258       return Edge(_graph->new_edge(tail._n, head._n));
    259     }
    260    
    261     void erase(Node n) const { _graph->del_node(n._n); }
    262     void erase(Edge e) const { _graph->del_edge(e._e); }
    263 
    264     void clear() const { _graph->clear(); }
    265 
    266     int nodeNum() const { return _graph->number_of_nodes(); }
    267     int edgeNum() const { return _graph->number_of_edges(); }
     243      return Edge(l_graph->new_edge(tail.l_n, head.l_n));
     244    }
     245   
     246    void erase(Node n) const { l_graph->del_node(n.l_n); }
     247    void erase(Edge e) const { l_graph->del_edge(e.l_e); }
     248
     249    void clear() const { l_graph->clear(); }
     250
     251    int nodeNum() const { return l_graph->number_of_nodes(); }
     252    int edgeNum() const { return l_graph->number_of_edges(); }
    268253
    269254    ///Read/write map from the nodes to type \c T.
     
    275260      typedef Node KeyType;
    276261
    277       NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
    278       NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
    279 
    280       void set(Node i, T t) { leda_stuff[i._n]=t; }
    281       T get(Node i) const { return leda_stuff[i._n]; }  //FIXME: Is it necessary
    282       T &operator[](Node i) { return leda_stuff[i._n]; }
    283       const T &operator[](Node i) const { return leda_stuff[i._n]; }
     262      NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
     263      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
     264
     265      void set(Node i, T t) { leda_stuff[i.l_n]=t; }
     266      T get(Node i) const { return leda_stuff[i.l_n]; }  //FIXME: Is it necessary
     267      T &operator[](Node i) { return leda_stuff[i.l_n]; }
     268      const T &operator[](Node i) const { return leda_stuff[i.l_n]; }
    284269
    285270      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
    286       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
     271      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
    287272    };
    288273
     
    295280      typedef Edge KeyType;
    296281
    297       EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
    298       EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
    299 
    300       void set(Edge i, T t) { leda_stuff[i._e]=t; }
    301       T get(Edge i) const { return leda_stuff[i._e]; }  //FIXME: Is it necessary
    302       T &operator[](Edge i) { return leda_stuff[i._e]; }
    303       const T &operator[](Edge i) const { return leda_stuff[i._e]; }
     282      EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
     283      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
     284
     285      void set(Edge i, T t) { leda_stuff[i.l_e]=t; }
     286      T get(Edge i) const { return leda_stuff[i.l_e]; }  //FIXME: Is it necessary
     287      T &operator[](Edge i) { return leda_stuff[i.l_e]; }
     288      const T &operator[](Edge i) const { return leda_stuff[i.l_e]; }
    304289
    305290      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
    306       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
     291      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
    307292    };
    308293
    309294  };
    310295
     296
     297  /// \brief LEDA graph template.
     298  ///
     299  /// This graph stucture uses LEDA graphs for physical storage.
     300  /// \ingroup graphs
    311301  template<typename Graph>
    312302  class LedaGraph : public LedaGraphWrapper<Graph> {
     
    320310  };
    321311
    322   // @}
    323 
    324312} //namespace hugo
    325313
    326 
    327 
    328 // class EmptyBipGraph : public EmptyGraph
    329 // {
    330 //   class ANode {};
    331 //   class BNode {};
    332 
    333 //   ANode &next(ANode &) {}
    334 //   BNode &next(BNode &) {}
    335 
    336 //   ANode &getFirst(ANode &) const {}
    337 //   BNode &getFirst(BNode &) const {}
    338 
    339 //   enum NodeClass { A = 0, B = 1 };
    340 //   NodeClass getClass(Node n) {}
    341 
    342 // }
    343 
    344314#endif // HUGO_LEDA_GRAPH_WRAPPER_H
  • src/work/marci/leda/makefile

    r616 r617  
    55LDFLAGS = -L$(LEDAROOT) -lG -lL -lm
    66
    7 BINARIES = bipartite_matching_leda bipartite_matching_leda_gen
     7BINARIES = bipartite_matching_leda bipartite_matching_leda_gen comparison
    88
    99include ../../makefile
Note: See TracChangeset for help on using the changeset viewer.