COIN-OR::LEMON - Graph Library

Changeset 774:4297098d9677 in lemon-0.x for src/hugo/smart_graph.h


Ignore:
Timestamp:
08/30/04 14:01:47 (17 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1066
Message:

Merge back the whole branches/hugo++ to trunk.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/smart_graph.h

    r753 r774  
    122122    Node head(Edge e) const { return edges[e.n].head; }
    123123
    124     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
    125     Node aNode(InEdgeIt e) const { return edges[e.n].head; }
    126 
    127     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
    128     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
    129 
    130124    NodeIt& first(NodeIt& v) const {
    131125      v=NodeIt(*this); return v; }
     
    137131      e=InEdgeIt(*this,v); return e; }
    138132
    139 //     template< typename It >
    140 //     It first() const { It e; first(e); return e; }
    141 
    142 //     template< typename It >
    143 //     It first(Node v) const { It e; first(e,v); return e; }
    144 
    145     static bool valid(Edge e) { return e.n!=-1; }
    146     static bool valid(Node n) { return n.n!=-1; }
    147    
    148     ///\deprecated Use
    149     ///\code
    150     ///  e=INVALID;
    151     ///\endcode
    152     ///instead.
    153     static void setInvalid(Edge &e) { e.n=-1; }
    154     ///\deprecated Use
    155     ///\code
    156     ///  e=INVALID;
    157     ///\endcode
    158     ///instead.
    159     static void setInvalid(Node &n) { n.n=-1; }
    160    
    161     template <typename It> It getNext(It it) const
    162     { It tmp(it); return next(tmp); }
    163 
    164     NodeIt& next(NodeIt& it) const {
    165       it.n=(it.n+2)%(nodes.size()+1)-1;
    166       return it;
    167     }
    168     OutEdgeIt& next(OutEdgeIt& it) const
    169     { it.n=edges[it.n].next_out; return it; }
    170     InEdgeIt& next(InEdgeIt& it) const
    171     { it.n=edges[it.n].next_in; return it; }
    172     EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
    173 
    174133    static int id(Node v) { return v.n; }
    175134    static int id(Edge e) { return e.n; }
     
    198157    }
    199158
     159    /// Finds an edge between two nodes.
     160
     161    /// Finds an edge from node \c u to node \c v.
     162    ///
     163    /// If \c prev is \ref INVALID (this is the default value), then
     164    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     165    /// the next edge from \c u to \c v after \c prev.
     166    /// \return The found edge or INVALID if there is no such an edge.
     167    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     168    {
     169      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
     170      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
     171      prev.n=e;
     172      return prev;
     173    }
     174   
    200175    void clear() {nodes.clear();edges.clear();}
    201176
     
    219194      bool operator!=(const Node i) const {return n!=i.n;}
    220195      bool operator<(const Node i) const {return n<i.n;}
     196      //      ///Validity check
     197      //      operator bool() { return n!=-1; }
    221198    };
    222199   
    223200    class NodeIt : public Node {
     201      const SmartGraph *G;
    224202      friend class SmartGraph;
    225203    public:
    226204      NodeIt() : Node() { }
     205      NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
    227206      NodeIt(Invalid i) : Node(i) { }
    228       NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
    229       ///\todo Undocumented conversion Node -\> NodeIt.
    230       NodeIt(const SmartGraph& G, const Node &n) : Node(n) { }
     207      NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
     208      NodeIt &operator++() {
     209        n=(n+2)%(G->nodes.size()+1)-1;
     210        return *this;
     211      }
     212//       ///Validity check
     213//       operator bool() { return Node::operator bool(); }     
    231214    };
    232215
     
    258241      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
    259242      int &idref() {return n;}
    260       const int &idref() const {return n;}
    261     };
     243      const int &idref() const {return n;}
     244//       ///Validity check
     245//       operator bool() { return n!=-1; }
     246   };
    262247   
    263248    class EdgeIt : public Edge {
     249      const SmartGraph *G;
    264250      friend class SmartGraph;
    265251    public:
    266       EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
     252      EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
     253      EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    267254      EdgeIt (Invalid i) : Edge(i) { }
    268255      EdgeIt() : Edge() { }
     
    270257      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
    271258      int &idref() {return n;}
     259      EdgeIt &operator++() { --n; return *this; }
     260//       ///Validity check
     261//       operator bool() { return Edge::operator bool(); }     
    272262    };
    273263   
    274264    class OutEdgeIt : public Edge {
     265      const SmartGraph *G;
    275266      friend class SmartGraph;
    276267    public:
    277268      OutEdgeIt() : Edge() { }
     269      OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    278270      OutEdgeIt (Invalid i) : Edge(i) { }
    279271
    280       OutEdgeIt(const SmartGraph& G,const Node v)
    281         : Edge(G.nodes[v.n].first_out) {}
     272      OutEdgeIt(const SmartGraph& _G,const Node v)
     273        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
     274      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
     275//       ///Validity check
     276//       operator bool() { return Edge::operator bool(); }     
    282277    };
    283278   
    284279    class InEdgeIt : public Edge {
     280      const SmartGraph *G;
    285281      friend class SmartGraph;
    286282    public:
    287283      InEdgeIt() : Edge() { }
     284      InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    288285      InEdgeIt (Invalid i) : Edge(i) { }
    289       InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
     286      InEdgeIt(const SmartGraph& _G,Node v)
     287        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
     288      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
     289//       ///Validity check
     290//       operator bool() { return Edge::operator bool(); }     
    290291    };
    291292
Note: See TracChangeset for help on using the changeset viewer.