COIN-OR::LEMON - Graph Library

Changeset 937:d4e911acef3d in lemon-0.x for src/lemon/smart_graph.h


Ignore:
Timestamp:
10/04/04 19:13:21 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1264
Message:

Revert backport changes -r1230.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/smart_graph.h

    r921 r937  
    2727#include <lemon/invalid.h>
    2828
     29
    2930#include <lemon/array_map.h>
    30 #include <lemon/sym_map.h>
    3131
    3232#include <lemon/map_registry.h>
     
    299299  };
    300300
     301
     302
     303  class SymSmartGraph : public SmartGraph {
     304    typedef SmartGraph Parent;
     305  public:
     306
     307    typedef SymSmartGraph Graph;
     308
     309    typedef SmartGraph::Node Node;
     310    typedef SmartGraph::NodeIt NodeIt;
     311
     312    class SymEdge;
     313    class SymEdgeIt;
     314
     315    class Edge;
     316    class EdgeIt;
     317    class OutEdgeIt;
     318    class InEdgeIt;
     319
     320    template <typename Value>
     321    class NodeMap : public Parent::NodeMap<Value> {     
     322    public:
     323      NodeMap(const SymSmartGraph& g)
     324        : SymSmartGraph::Parent::NodeMap<Value>(g) {}
     325      NodeMap(const SymSmartGraph& g, Value v)
     326        : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
     327      template<typename TT>
     328      NodeMap(const NodeMap<TT>& copy)
     329        : SymSmartGraph::Parent::NodeMap<Value>(copy) { }           
     330    };
     331
     332    template <typename Value>
     333    class SymEdgeMap : public Parent::EdgeMap<Value> {
     334    public:
     335      typedef SymEdge KeyType;
     336
     337      SymEdgeMap(const SymSmartGraph& g)
     338        : SymSmartGraph::Parent::EdgeMap<Value>(g) {}
     339      SymEdgeMap(const SymSmartGraph& g, Value v)
     340        : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
     341      template<typename TT>
     342      SymEdgeMap(const SymEdgeMap<TT>& copy)
     343        : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
     344     
     345    };
     346
     347    // Create edge map registry.
     348    CREATE_EDGE_MAP_REGISTRY;
     349    // Create edge maps.
     350    CREATE_EDGE_MAP(ArrayMap);
     351
     352    class Edge {
     353      friend class SymSmartGraph;
     354      friend class SymSmartGraph::EdgeIt;
     355      friend class SymSmartGraph::OutEdgeIt;
     356      friend class SymSmartGraph::InEdgeIt;
     357     
     358    protected:
     359      int id;
     360
     361      Edge(int pid) { id = pid; }
     362
     363    public:
     364      /// An Edge with id \c n.
     365
     366      Edge() { }
     367      Edge (Invalid) { id = -1; }
     368
     369      operator SymEdge(){ return SymEdge(id >> 1);}
     370     
     371      bool operator==(const Edge i) const {return id == i.id;}
     372      bool operator!=(const Edge i) const {return id != i.id;}
     373      bool operator<(const Edge i) const {return id < i.id;}
     374      //      ///Validity check
     375      //      operator bool() { return n!=-1; }
     376    };
     377
     378    class SymEdge : public SmartGraph::Edge {
     379      friend class SymSmartGraph;
     380      friend class SymSmartGraph::Edge;
     381      typedef SmartGraph::Edge Parent;
     382
     383    protected:     
     384      SymEdge(int pid) : Parent(pid) {}
     385    public:
     386
     387      SymEdge() { }
     388      SymEdge(const SmartGraph::Edge& i) : Parent(i) {}
     389      SymEdge (Invalid) : Parent(INVALID) {}
     390
     391    };
     392
     393    class OutEdgeIt {
     394      Parent::OutEdgeIt out;
     395      Parent::InEdgeIt in;     
     396    public:
     397      OutEdgeIt() {}
     398      OutEdgeIt(const SymSmartGraph& g, Edge e) {
     399        if ((e.id & 1) == 0) { 
     400          out = Parent::OutEdgeIt(g, SymEdge(e));
     401          in = Parent::InEdgeIt(g, g.tail(e));
     402        } else {
     403          out = Parent::OutEdgeIt(INVALID);
     404          in = Parent::InEdgeIt(g, SymEdge(e));
     405        }
     406      }
     407      OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
     408
     409      OutEdgeIt(const SymSmartGraph& g, const Node v)
     410        : out(g, v), in(g, v) {}
     411      OutEdgeIt &operator++() {
     412        if (out != INVALID) {
     413          ++out;
     414        } else {
     415          ++in;
     416        }
     417        return *this;
     418      }
     419
     420      operator Edge() const {
     421        if (out == INVALID && in == INVALID) return INVALID;
     422        return out != INVALID ? forward(out) : backward(in);
     423      }
     424
     425      bool operator==(const Edge i) const {return Edge(*this) == i;}
     426      bool operator!=(const Edge i) const {return Edge(*this) != i;}
     427      bool operator<(const Edge i) const {return Edge(*this) < i;}
     428    };
     429
     430    class InEdgeIt {
     431      Parent::OutEdgeIt out;
     432      Parent::InEdgeIt in;     
     433    public:
     434      InEdgeIt() {}
     435      InEdgeIt(const SymSmartGraph& g, Edge e) {
     436        if ((e.id & 1) == 0) { 
     437          out = Parent::OutEdgeIt(g, SymEdge(e));
     438          in = Parent::InEdgeIt(g, g.tail(e));
     439        } else {
     440          out = Parent::OutEdgeIt(INVALID);
     441          in = Parent::InEdgeIt(g, SymEdge(e));
     442        }
     443      }
     444      InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
     445
     446      InEdgeIt(const SymSmartGraph& g, const Node v)
     447        : out(g, v), in(g, v) {}
     448
     449      InEdgeIt &operator++() {
     450        if (out != INVALID) {
     451          ++out;
     452        } else {
     453          ++in;
     454        }
     455        return *this;
     456      }
     457
     458      operator Edge() const {
     459        if (out == INVALID && in == INVALID) return INVALID;
     460        return out != INVALID ? backward(out) : forward(in);
     461      }
     462
     463      bool operator==(const Edge i) const {return Edge(*this) == i;}
     464      bool operator!=(const Edge i) const {return Edge(*this) != i;}
     465      bool operator<(const Edge i) const {return Edge(*this) < i;}
     466    };
     467
     468    class SymEdgeIt : public Parent::EdgeIt {
     469
     470    public:
     471      SymEdgeIt() {}
     472
     473      SymEdgeIt(const SymSmartGraph& g)
     474        : SymSmartGraph::Parent::EdgeIt(g) {}
     475
     476      SymEdgeIt(const SymSmartGraph& g, SymEdge e)
     477        : SymSmartGraph::Parent::EdgeIt(g, e) {}
     478
     479      SymEdgeIt(Invalid i)
     480        : SymSmartGraph::Parent::EdgeIt(INVALID) {}
     481
     482      SymEdgeIt& operator++() {
     483        SymSmartGraph::Parent::EdgeIt::operator++();
     484        return *this;
     485      }
     486
     487      operator SymEdge() const {
     488        return SymEdge
     489          (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
     490      }
     491      bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
     492      bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
     493      bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
     494    };
     495
     496    class EdgeIt {
     497      SymEdgeIt it;
     498      bool fw;
     499    public:
     500      EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
     501      EdgeIt (Invalid i) : it(i) { }
     502      EdgeIt(const SymSmartGraph& g, Edge e)
     503        : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
     504      EdgeIt() { }
     505      EdgeIt& operator++() {
     506        fw = !fw;
     507        if (fw) ++it;
     508        return *this;
     509      }
     510      operator Edge() const {
     511        if (it == INVALID) return INVALID;
     512        return fw ? forward(it) : backward(it);
     513      }
     514      bool operator==(const Edge i) const {return Edge(*this) == i;}
     515      bool operator!=(const Edge i) const {return Edge(*this) != i;}
     516      bool operator<(const Edge i) const {return Edge(*this) < i;}
     517
     518    };
     519
     520    ///Number of nodes.
     521    int nodeNum() const { return Parent::nodeNum(); }
     522    ///Number of edges.
     523    int edgeNum() const { return 2*Parent::edgeNum(); }
     524    ///Number of symmetric edges.
     525    int symEdgeNum() const { return Parent::edgeNum(); }
     526
     527    /// Maximum node ID.
     528   
     529    /// Maximum node ID.
     530    ///\sa id(Node)
     531    int maxNodeId() const { return Parent::maxNodeId(); }
     532    /// Maximum edge ID.
     533   
     534    /// Maximum edge ID.
     535    ///\sa id(Edge)
     536    int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
     537    /// Maximum symmetric edge ID.
     538   
     539    /// Maximum symmetric edge ID.
     540    ///\sa id(SymEdge)
     541    int maxSymEdgeId() const { return Parent::maxEdgeId(); }
     542
     543
     544    Node tail(Edge e) const {
     545      return (e.id & 1) == 0 ?
     546        Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
     547    }
     548
     549    Node head(Edge e) const {
     550      return (e.id & 1) == 0 ?
     551        Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
     552    }
     553
     554    Node tail(SymEdge e) const {
     555      return Parent::tail(e);
     556    }
     557
     558    Node head(SymEdge e) const {
     559      return Parent::head(e);
     560    }
     561
     562    NodeIt& first(NodeIt& v) const {
     563      v=NodeIt(*this); return v; }
     564    EdgeIt& first(EdgeIt& e) const {
     565      e=EdgeIt(*this); return e; }
     566    SymEdgeIt& first(SymEdgeIt& e) const {
     567      e=SymEdgeIt(*this); return e; }
     568    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
     569      e=OutEdgeIt(*this,v); return e; }
     570    InEdgeIt& first(InEdgeIt& e, const Node v) const {
     571      e=InEdgeIt(*this,v); return e; }
     572
     573    /// Node ID.
     574   
     575    /// The ID of a valid Node is a nonnegative integer not greater than
     576    /// \ref maxNodeId(). The range of the ID's is not surely continuous
     577    /// and the greatest node ID can be actually less then \ref maxNodeId().
     578    ///
     579    /// The ID of the \ref INVALID node is -1.
     580    ///\return The ID of the node \c v.
     581    static int id(Node v) { return Parent::id(v); }
     582    /// Edge ID.
     583   
     584    /// The ID of a valid Edge is a nonnegative integer not greater than
     585    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
     586    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
     587    ///
     588    /// The ID of the \ref INVALID edge is -1.
     589    ///\return The ID of the edge \c e.
     590    static int id(Edge e) { return e.id; }
     591
     592    /// The ID of a valid SymEdge is a nonnegative integer not greater than
     593    /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
     594    /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
     595    ///
     596    /// The ID of the \ref INVALID symmetric edge is -1.
     597    ///\return The ID of the edge \c e.
     598    static int id(SymEdge e) { return Parent::id(e); }
     599
     600    /// Adds a new node to the graph.
     601
     602    /// \warning It adds the new node to the front of the list.
     603    /// (i.e. the lastly added node becomes the first.)
     604    Node addNode() {
     605      return Parent::addNode();
     606    }
     607   
     608    SymEdge addEdge(Node u, Node v) {
     609      SymEdge se = Parent::addEdge(u, v);
     610      edge_maps.add(forward(se));
     611      edge_maps.add(backward(se));
     612      return se;
     613    }
     614   
     615    /// Finds an edge between two nodes.
     616
     617    /// Finds an edge from node \c u to node \c v.
     618    ///
     619    /// If \c prev is \ref INVALID (this is the default value), then
     620    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     621    /// the next edge from \c u to \c v after \c prev.
     622    /// \return The found edge or INVALID if there is no such an edge.
     623    Edge findEdge(Node u, Node v, Edge prev = INVALID)
     624    {     
     625      if (prev == INVALID || id(prev) & 1 == 0) {
     626        SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
     627        if (se != INVALID) return forward(se);
     628      } else {
     629        SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
     630        if (se != INVALID) return backward(se);
     631      }
     632      return INVALID;
     633    }
     634
     635//     /// Finds an symmetric edge between two nodes.
     636
     637//     /// Finds an symmetric edge from node \c u to node \c v.
     638//     ///
     639//     /// If \c prev is \ref INVALID (this is the default value), then
     640//     /// It finds the first edge from \c u to \c v. Otherwise it looks for
     641//     /// the next edge from \c u to \c v after \c prev.
     642//     /// \return The found edge or INVALID if there is no such an edge.
     643
     644//     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
     645//     {     
     646//       if (prev == INVALID || id(prev) & 1 == 0) {
     647//      SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
     648//      if (se != INVALID) return se;
     649//       } else {
     650//      SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
     651//      if (se != INVALID) return se;   
     652//       }
     653//       return INVALID;
     654//     }
     655   
     656  public:
     657
     658    void clear() {
     659      edge_maps.clear();
     660      Parent::clear();
     661    }
     662
     663    static Edge opposite(Edge e) {
     664      return Edge(id(e) ^ 1);
     665    }
     666
     667    static Edge forward(SymEdge e) {
     668      return Edge(id(e) << 1);
     669    }
     670
     671    static Edge backward(SymEdge e) {
     672      return Edge((id(e) << 1) | 1);
     673    }
     674
     675  };
    301676  ///Graph for bidirectional edges.
    302677
     
    319694  //\sa SmartGraph.
    320695
    321   class SymSmartGraph : public SmartGraph
     696  /*  class SymSmartGraph : public SmartGraph
    322697  {
    323698  public:
     
    354729   
    355730
    356   };
     731    };*/
    357732 
    358733  /// @} 
Note: See TracChangeset for help on using the changeset viewer.