COIN-OR::LEMON - Graph Library

Changeset 937:d4e911acef3d in lemon-0.x for src/lemon/list_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/list_graph.h

    r921 r937  
    3030#include <lemon/array_map.h>
    3131
    32 #include <lemon/sym_map.h>
    33 
    3432#include <lemon/map_defines.h>
    3533
     
    105103        first_free_edge(_g.first_free_edge) {}
    106104   
     105    /// \bug In the vector can be hole if a node is erased from the graph.
    107106    ///Number of nodes.
    108107    int nodeNum() const { return nodes.size(); }
     
    439438  ///\todo this date structure need some reconsiderations. Maybe it
    440439  ///should be implemented independently from ListGraph.
    441  
     440  /* 
    442441  class SymListGraph : public ListGraph
    443442  {
     
    484483      ListGraph::erase(e);
    485484    }   
     485    };*/
     486
     487  class SymListGraph : public ListGraph {
     488    typedef ListGraph Parent;
     489  public:
     490
     491    typedef SymListGraph Graph;
     492
     493    typedef ListGraph::Node Node;
     494    typedef ListGraph::NodeIt NodeIt;
     495
     496    class SymEdge;
     497    class SymEdgeIt;
     498
     499    class Edge;
     500    class EdgeIt;
     501    class OutEdgeIt;
     502    class InEdgeIt;
     503
     504    template <typename Value>
     505    class NodeMap : public Parent::NodeMap<Value> {     
     506    public:
     507      NodeMap(const SymListGraph& g)
     508        : SymListGraph::Parent::NodeMap<Value>(g) {}
     509      NodeMap(const SymListGraph& g, Value v)
     510        : SymListGraph::Parent::NodeMap<Value>(g, v) {}
     511      template<typename TT>
     512      NodeMap(const NodeMap<TT>& copy)
     513        : SymListGraph::Parent::NodeMap<Value>(copy) { }           
     514    };
     515
     516    template <typename Value>
     517    class SymEdgeMap : public Parent::EdgeMap<Value> {
     518    public:
     519      typedef SymEdge KeyType;
     520
     521      SymEdgeMap(const SymListGraph& g)
     522        : SymListGraph::Parent::EdgeMap<Value>(g) {}
     523      SymEdgeMap(const SymListGraph& g, Value v)
     524        : SymListGraph::Parent::EdgeMap<Value>(g, v) {}
     525      template<typename TT>
     526      SymEdgeMap(const SymEdgeMap<TT>& copy)
     527        : SymListGraph::Parent::EdgeMap<Value>(copy) { }
     528     
     529    };
     530
     531    // Create edge map registry.
     532    CREATE_EDGE_MAP_REGISTRY;
     533    // Create edge maps.
     534    CREATE_EDGE_MAP(ArrayMap);
     535
     536    class Edge {
     537      friend class SymListGraph;
     538      friend class SymListGraph::EdgeIt;
     539      friend class SymListGraph::OutEdgeIt;
     540      friend class SymListGraph::InEdgeIt;
     541     
     542    protected:
     543      int id;
     544
     545      Edge(int pid) { id = pid; }
     546
     547    public:
     548      /// An Edge with id \c n.
     549
     550      Edge() { }
     551      Edge (Invalid) { id = -1; }
     552
     553      operator SymEdge(){ return SymEdge(id >> 1);}
     554     
     555      bool operator==(const Edge i) const {return id == i.id;}
     556      bool operator!=(const Edge i) const {return id != i.id;}
     557      bool operator<(const Edge i) const {return id < i.id;}
     558      //      ///Validity check
     559      //      operator bool() { return n!=-1; }
     560    };
     561
     562    class SymEdge : public ListGraph::Edge {
     563      friend class SymListGraph;
     564      friend class SymListGraph::Edge;
     565      typedef ListGraph::Edge Parent;
     566
     567    protected:     
     568      SymEdge(int pid) : Parent(pid) {}
     569    public:
     570
     571      SymEdge() { }
     572      SymEdge(const ListGraph::Edge& i) : Parent(i) {}
     573      SymEdge (Invalid) : Parent(INVALID) {}
     574
     575    };
     576
     577    class OutEdgeIt {
     578      Parent::OutEdgeIt out;
     579      Parent::InEdgeIt in;     
     580    public:
     581      OutEdgeIt() {}
     582      OutEdgeIt(const SymListGraph& g, Edge e) {
     583        if ((e.id & 1) == 0) { 
     584          out = Parent::OutEdgeIt(g, SymEdge(e));
     585          in = Parent::InEdgeIt(g, g.tail(e));
     586        } else {
     587          out = Parent::OutEdgeIt(INVALID);
     588          in = Parent::InEdgeIt(g, SymEdge(e));
     589        }
     590      }
     591      OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
     592
     593      OutEdgeIt(const SymListGraph& g, const Node v)
     594        : out(g, v), in(g, v) {}
     595      OutEdgeIt &operator++() {
     596        if (out != INVALID) {
     597          ++out;
     598        } else {
     599          ++in;
     600        }
     601        return *this;
     602      }
     603
     604      operator Edge() const {
     605        if (out == INVALID && in == INVALID) return INVALID;
     606        return out != INVALID ? forward(out) : backward(in);
     607      }
     608
     609      bool operator==(const Edge i) const {return Edge(*this) == i;}
     610      bool operator!=(const Edge i) const {return Edge(*this) != i;}
     611      bool operator<(const Edge i) const {return Edge(*this) < i;}
     612    };
     613
     614    class InEdgeIt {
     615      Parent::OutEdgeIt out;
     616      Parent::InEdgeIt in;     
     617    public:
     618      InEdgeIt() {}
     619      InEdgeIt(const SymListGraph& g, Edge e) {
     620        if ((e.id & 1) == 0) { 
     621          out = Parent::OutEdgeIt(g, SymEdge(e));
     622          in = Parent::InEdgeIt(g, g.tail(e));
     623        } else {
     624          out = Parent::OutEdgeIt(INVALID);
     625          in = Parent::InEdgeIt(g, SymEdge(e));
     626        }
     627      }
     628      InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
     629
     630      InEdgeIt(const SymListGraph& g, const Node v)
     631        : out(g, v), in(g, v) {}
     632
     633      InEdgeIt &operator++() {
     634        if (out != INVALID) {
     635          ++out;
     636        } else {
     637          ++in;
     638        }
     639        return *this;
     640      }
     641
     642      operator Edge() const {
     643        if (out == INVALID && in == INVALID) return INVALID;
     644        return out != INVALID ? backward(out) : forward(in);
     645      }
     646
     647      bool operator==(const Edge i) const {return Edge(*this) == i;}
     648      bool operator!=(const Edge i) const {return Edge(*this) != i;}
     649      bool operator<(const Edge i) const {return Edge(*this) < i;}
     650    };
     651
     652    class SymEdgeIt : public Parent::EdgeIt {
     653
     654    public:
     655      SymEdgeIt() {}
     656
     657      SymEdgeIt(const SymListGraph& g)
     658        : SymListGraph::Parent::EdgeIt(g) {}
     659
     660      SymEdgeIt(const SymListGraph& g, SymEdge e)
     661        : SymListGraph::Parent::EdgeIt(g, e) {}
     662
     663      SymEdgeIt(Invalid i)
     664        : SymListGraph::Parent::EdgeIt(INVALID) {}
     665
     666      SymEdgeIt& operator++() {
     667        SymListGraph::Parent::EdgeIt::operator++();
     668        return *this;
     669      }
     670
     671      operator SymEdge() const {
     672        return SymEdge
     673          (static_cast<const SymListGraph::Parent::EdgeIt&>(*this));
     674      }
     675      bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
     676      bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
     677      bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
     678    };
     679
     680    class EdgeIt {
     681      SymEdgeIt it;
     682      bool fw;
     683    public:
     684      EdgeIt(const SymListGraph& g) : it(g), fw(true) {}
     685      EdgeIt (Invalid i) : it(i) { }
     686      EdgeIt(const SymListGraph& g, Edge e)
     687        : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
     688      EdgeIt() { }
     689      EdgeIt& operator++() {
     690        fw = !fw;
     691        if (fw) ++it;
     692        return *this;
     693      }
     694      operator Edge() const {
     695        if (it == INVALID) return INVALID;
     696        return fw ? forward(it) : backward(it);
     697      }
     698      bool operator==(const Edge i) const {return Edge(*this) == i;}
     699      bool operator!=(const Edge i) const {return Edge(*this) != i;}
     700      bool operator<(const Edge i) const {return Edge(*this) < i;}
     701
     702    };
     703
     704    ///Number of nodes.
     705    int nodeNum() const { return Parent::nodeNum(); }
     706    ///Number of edges.
     707    int edgeNum() const { return 2*Parent::edgeNum(); }
     708    ///Number of symmetric edges.
     709    int symEdgeNum() const { return Parent::edgeNum(); }
     710
     711    ///Set the expected maximum number of edges.
     712
     713    ///With this function, it is possible to set the expected number of edges.
     714    ///The use of this fasten the building of the graph and makes
     715    ///it possible to avoid the superfluous memory allocation.
     716    void reserveSymEdge(int n) { Parent::reserveEdge(n); };
     717   
     718    /// Maximum node ID.
     719   
     720    /// Maximum node ID.
     721    ///\sa id(Node)
     722    int maxNodeId() const { return Parent::maxNodeId(); }
     723    /// Maximum edge ID.
     724   
     725    /// Maximum edge ID.
     726    ///\sa id(Edge)
     727    int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
     728    /// Maximum symmetric edge ID.
     729   
     730    /// Maximum symmetric edge ID.
     731    ///\sa id(SymEdge)
     732    int maxSymEdgeId() const { return Parent::maxEdgeId(); }
     733
     734
     735    Node tail(Edge e) const {
     736      return (e.id & 1) == 0 ?
     737        Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
     738    }
     739
     740    Node head(Edge e) const {
     741      return (e.id & 1) == 0 ?
     742        Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
     743    }
     744
     745    Node tail(SymEdge e) const {
     746      return Parent::tail(e);
     747    }
     748
     749    Node head(SymEdge e) const {
     750      return Parent::head(e);
     751    }
     752
     753    NodeIt& first(NodeIt& v) const {
     754      v=NodeIt(*this); return v; }
     755    EdgeIt& first(EdgeIt& e) const {
     756      e=EdgeIt(*this); return e; }
     757    SymEdgeIt& first(SymEdgeIt& e) const {
     758      e=SymEdgeIt(*this); return e; }
     759    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
     760      e=OutEdgeIt(*this,v); return e; }
     761    InEdgeIt& first(InEdgeIt& e, const Node v) const {
     762      e=InEdgeIt(*this,v); return e; }
     763
     764    /// Node ID.
     765   
     766    /// The ID of a valid Node is a nonnegative integer not greater than
     767    /// \ref maxNodeId(). The range of the ID's is not surely continuous
     768    /// and the greatest node ID can be actually less then \ref maxNodeId().
     769    ///
     770    /// The ID of the \ref INVALID node is -1.
     771    ///\return The ID of the node \c v.
     772    static int id(Node v) { return Parent::id(v); }
     773    /// Edge ID.
     774   
     775    /// The ID of a valid Edge is a nonnegative integer not greater than
     776    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
     777    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
     778    ///
     779    /// The ID of the \ref INVALID edge is -1.
     780    ///\return The ID of the edge \c e.
     781    static int id(Edge e) { return e.id; }
     782
     783    /// The ID of a valid SymEdge is a nonnegative integer not greater than
     784    /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
     785    /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
     786    ///
     787    /// The ID of the \ref INVALID symmetric edge is -1.
     788    ///\return The ID of the edge \c e.
     789    static int id(SymEdge e) { return Parent::id(e); }
     790
     791    /// Adds a new node to the graph.
     792
     793    /// \warning It adds the new node to the front of the list.
     794    /// (i.e. the lastly added node becomes the first.)
     795    Node addNode() {
     796      return Parent::addNode();
     797    }
     798   
     799    SymEdge addEdge(Node u, Node v) {
     800      SymEdge se = Parent::addEdge(u, v);
     801      edge_maps.add(forward(se));
     802      edge_maps.add(backward(se));
     803      return se;
     804    }
     805   
     806    /// Finds an edge between two nodes.
     807
     808    /// Finds an edge from node \c u to node \c v.
     809    ///
     810    /// If \c prev is \ref INVALID (this is the default value), then
     811    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     812    /// the next edge from \c u to \c v after \c prev.
     813    /// \return The found edge or INVALID if there is no such an edge.
     814    Edge findEdge(Node u, Node v, Edge prev = INVALID)
     815    {     
     816      if (prev == INVALID || id(prev) & 1 == 0) {
     817        SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
     818        if (se != INVALID) return forward(se);
     819      } else {
     820        SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
     821        if (se != INVALID) return backward(se);
     822      }
     823      return INVALID;
     824    }
     825
     826//     /// Finds an symmetric edge between two nodes.
     827
     828//     /// Finds an symmetric edge from node \c u to node \c v.
     829//     ///
     830//     /// If \c prev is \ref INVALID (this is the default value), then
     831//     /// It finds the first edge from \c u to \c v. Otherwise it looks for
     832//     /// the next edge from \c u to \c v after \c prev.
     833//     /// \return The found edge or INVALID if there is no such an edge.
     834
     835//     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
     836//     {     
     837//       if (prev == INVALID || id(prev) & 1 == 0) {
     838//      SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
     839//      if (se != INVALID) return se;
     840//       } else {
     841//      SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
     842//      if (se != INVALID) return se;   
     843//       }
     844//       return INVALID;
     845//     }
     846   
     847  public:
     848
     849    void erase(Node n) {     
     850      for (OutEdgeIt it(*this, n); it != INVALID; ++it) {
     851        edge_maps.erase(it);
     852        edge_maps.erase(opposite(it));
     853      }
     854      Parent::erase(n);
     855    }
     856   
     857    void erase(SymEdge e) {
     858      edge_maps.erase(forward(e));
     859      edge_maps.erase(backward(e));
     860      Parent::erase(e);
     861    };
     862
     863    void clear() {
     864      edge_maps.clear();
     865      Parent::clear();
     866    }
     867
     868    static Edge opposite(Edge e) {
     869      return Edge(id(e) ^ 1);
     870    }
     871
     872    static Edge forward(SymEdge e) {
     873      return Edge(id(e) << 1);
     874    }
     875
     876    static Edge backward(SymEdge e) {
     877      return Edge((id(e) << 1) | 1);
     878    }
     879
    486880  };
    487 
    488881
    489882  ///A graph class containing only nodes.
Note: See TracChangeset for help on using the changeset viewer.