COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 951:0f1fe84ff36c in lemon-0.x for src


Ignore:
Timestamp:
10/30/04 20:51:00 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1331
Message:
  • SmallGraph? is also a class instead of being a typedef. (For the sake of doxygen.)
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/lemon/full_graph.h

    r946 r951  
    3737/// \addtogroup graphs
    3838/// @{
     39
     40  class FullGraphBase {
     41    int NodeNum;
     42    int EdgeNum;
     43  public:
     44
     45    typedef FullGraphBase Graph;
     46
     47    class Node;
     48    class Edge;
     49
     50  public:
     51
     52    FullGraphBase() {}
     53
     54
     55    ///Creates a full graph with \c n nodes.
     56    void construct(int n) { NodeNum = n; EdgeNum = n * n; }
     57    ///
     58    //    FullGraphBase(const FullGraphBase &_g)
     59    //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
     60   
     61    ///Number of nodes.
     62    int nodeNum() const { return NodeNum; }
     63    ///Number of edges.
     64    int edgeNum() const { return EdgeNum; }
     65
     66    /// Maximum node ID.
     67   
     68    /// Maximum node ID.
     69    ///\sa id(Node)
     70    int maxNodeId() const { return NodeNum-1; }
     71    /// Maximum edge ID.
     72   
     73    /// Maximum edge ID.
     74    ///\sa id(Edge)
     75    int maxEdgeId() const { return EdgeNum-1; }
     76
     77    Node tail(Edge e) const { return e.id % NodeNum; }
     78    Node head(Edge e) const { return e.id / NodeNum; }
     79
     80
     81    /// Node ID.
     82   
     83    /// The ID of a valid Node is a nonnegative integer not greater than
     84    /// \ref maxNodeId(). The range of the ID's is not surely continuous
     85    /// and the greatest node ID can be actually less then \ref maxNodeId().
     86    ///
     87    /// The ID of the \ref INVALID node is -1.
     88    ///\return The ID of the node \c v.
     89
     90    static int id(Node v) { return v.id; }
     91    /// Edge ID.
     92   
     93    /// The ID of a valid Edge is a nonnegative integer not greater than
     94    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
     95    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
     96    ///
     97    /// The ID of the \ref INVALID edge is -1.
     98    ///\return The ID of the edge \c e.
     99    static int id(Edge e) { return e.id; }
     100
     101    /// Finds an edge between two nodes.
     102   
     103    /// Finds an edge from node \c u to node \c v.
     104    ///
     105    /// If \c prev is \ref INVALID (this is the default value), then
     106    /// It finds the first edge from \c u to \c v. Otherwise it looks for
     107    /// the next edge from \c u to \c v after \c prev.
     108    /// \return The found edge or INVALID if there is no such an edge.
     109    Edge findEdge(Node u,Node v, Edge prev = INVALID)
     110    {
     111      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
     112    }
     113   
     114     
     115    class Node {
     116      friend class FullGraphBase;
     117
     118    protected:
     119      int id;
     120      Node(int _id) { id = _id;}
     121    public:
     122      Node() {}
     123      Node (Invalid) { id = -1; }
     124      bool operator==(const Node node) const {return id == node.id;}
     125      bool operator!=(const Node node) const {return id != node.id;}
     126      bool operator<(const Node node) const {return id < node.id;}
     127    };
     128   
     129
     130
     131    class Edge {
     132      friend class FullGraphBase;
     133     
     134    protected:
     135      int id;  // NodeNum * head + tail;
     136
     137      Edge(int _id) : id(_id) {}
     138
     139      Edge(const FullGraphBase& _graph, int tail, int head)
     140        : id(_graph.NodeNum * head+tail) {}
     141    public:
     142      Edge() { }
     143      Edge (Invalid) { id = -1; }
     144      bool operator==(const Edge edge) const {return id == edge.id;}
     145      bool operator!=(const Edge edge) const {return id != edge.id;}
     146      bool operator<(const Edge edge) const {return id < edge.id;}
     147    };
     148
     149    void first(Node& node) const {
     150      node.id = NodeNum-1;
     151    }
     152
     153    static void next(Node& node) {
     154      --node.id;
     155    }
     156
     157    void first(Edge& edge) const {
     158      edge.id = EdgeNum-1;
     159    }
     160
     161    static void next(Edge& edge) {
     162      --edge.id;
     163    }
     164
     165    void firstOut(Edge& edge, const Node& node) const {
     166      edge.id = EdgeNum + node.id - NodeNum;
     167    }
     168
     169    void nextOut(Edge& edge) const {
     170      edge.id -= NodeNum;
     171      if (edge.id < 0) edge.id = -1;
     172    }
     173
     174    void firstIn(Edge& edge, const Node& node) const {
     175      edge.id = node.id * NodeNum;
     176    }
     177   
     178    void nextIn(Edge& edge) const {
     179      ++edge.id;
     180      if (edge.id % NodeNum == 0) edge.id = -1;
     181    }
     182
     183  };
     184
     185
     186  typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
     187  typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
     188  typedef IdMappableGraphExtender<IterableFullGraphBase> IdMappableFullGraphBase;
     189  typedef DefaultMappableGraphExtender<IdMappableFullGraphBase> MappableFullGraphBase;
    39190
    40191  ///A full graph class.
    … …  
    50201  ///
    51202  ///\author Alpar Juttner
    52   class FullGraphBase {
    53     int NodeNum;
    54     int EdgeNum;
    55   public:
    56 
    57     typedef FullGraphBase Graph;
    58 
    59     class Node;
    60     class Edge;
    61 
    62   public:
    63 
    64     FullGraphBase() {}
    65 
    66 
    67     ///Creates a full graph with \c n nodes.
    68     void construct(int n) { NodeNum = n; EdgeNum = n * n; }
    69     ///
    70     //    FullGraphBase(const FullGraphBase &_g)
    71     //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
    72    
    73     ///Number of nodes.
    74     int nodeNum() const { return NodeNum; }
    75     ///Number of edges.
    76     int edgeNum() const { return EdgeNum; }
    77 
    78     /// Maximum node ID.
    79    
    80     /// Maximum node ID.
    81     ///\sa id(Node)
    82     int maxNodeId() const { return NodeNum-1; }
    83     /// Maximum edge ID.
    84    
    85     /// Maximum edge ID.
    86     ///\sa id(Edge)
    87     int maxEdgeId() const { return EdgeNum-1; }
    88 
    89     Node tail(Edge e) const { return e.id % NodeNum; }
    90     Node head(Edge e) const { return e.id / NodeNum; }
    91 
    92 
    93     /// Node ID.
    94    
    95     /// The ID of a valid Node is a nonnegative integer not greater than
    96     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    97     /// and the greatest node ID can be actually less then \ref maxNodeId().
    98     ///
    99     /// The ID of the \ref INVALID node is -1.
    100     ///\return The ID of the node \c v.
    101 
    102     static int id(Node v) { return v.id; }
    103     /// Edge ID.
    104    
    105     /// The ID of a valid Edge is a nonnegative integer not greater than
    106     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    107     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    108     ///
    109     /// The ID of the \ref INVALID edge is -1.
    110     ///\return The ID of the edge \c e.
    111     static int id(Edge e) { return e.id; }
    112 
    113     /// Finds an edge between two nodes.
    114    
    115     /// Finds an edge from node \c u to node \c v.
    116     ///
    117     /// If \c prev is \ref INVALID (this is the default value), then
    118     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    119     /// the next edge from \c u to \c v after \c prev.
    120     /// \return The found edge or INVALID if there is no such an edge.
    121     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    122     {
    123       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
    124     }
    125    
    126      
    127     class Node {
    128       friend class FullGraphBase;
    129 
    130     protected:
    131       int id;
    132       Node(int _id) { id = _id;}
    133     public:
    134       Node() {}
    135       Node (Invalid) { id = -1; }
    136       bool operator==(const Node node) const {return id == node.id;}
    137       bool operator!=(const Node node) const {return id != node.id;}
    138       bool operator<(const Node node) const {return id < node.id;}
    139     };
    140    
    141 
    142 
    143     class Edge {
    144       friend class FullGraphBase;
    145      
    146     protected:
    147       int id;  // NodeNum * head + tail;
    148 
    149       Edge(int _id) : id(_id) {}
    150 
    151       Edge(const FullGraphBase& _graph, int tail, int head)
    152         : id(_graph.NodeNum * head+tail) {}
    153     public:
    154       Edge() { }
    155       Edge (Invalid) { id = -1; }
    156       bool operator==(const Edge edge) const {return id == edge.id;}
    157       bool operator!=(const Edge edge) const {return id != edge.id;}
    158       bool operator<(const Edge edge) const {return id < edge.id;}
    159     };
    160 
    161     void first(Node& node) const {
    162       node.id = NodeNum-1;
    163     }
    164 
    165     static void next(Node& node) {
    166       --node.id;
    167     }
    168 
    169     void first(Edge& edge) const {
    170       edge.id = EdgeNum-1;
    171     }
    172 
    173     static void next(Edge& edge) {
    174       --edge.id;
    175     }
    176 
    177     void firstOut(Edge& edge, const Node& node) const {
    178       edge.id = EdgeNum + node.id - NodeNum;
    179     }
    180 
    181     void nextOut(Edge& edge) const {
    182       edge.id -= NodeNum;
    183       if (edge.id < 0) edge.id = -1;
    184     }
    185 
    186     void firstIn(Edge& edge, const Node& node) const {
    187       edge.id = node.id * NodeNum;
    188     }
    189    
    190     void nextIn(Edge& edge) const {
    191       ++edge.id;
    192       if (edge.id % NodeNum == 0) edge.id = -1;
    193     }
    194 
    195   };
    196 
    197 
    198   typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
    199   typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
    200   typedef IdMappableGraphExtender<IterableFullGraphBase> IdMappableFullGraphBase;
    201   typedef DefaultMappableGraphExtender<IdMappableFullGraphBase> MappableFullGraphBase;
    202 
    203203  class FullGraph : public MappableFullGraphBase {
    204204  public:
Note: See TracChangeset for help on using the changeset viewer.