Changeset 951:0f1fe84ff36c in lemon0.x
 Timestamp:
 10/30/04 20:51:00 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1331
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/full_graph.h
r946 r951 37 37 /// \addtogroup graphs 38 38 /// @{ 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 NodeNum1; } 71 /// Maximum edge ID. 72 73 /// Maximum edge ID. 74 ///\sa id(Edge) 75 int maxEdgeId() const { return EdgeNum1; } 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 = NodeNum1; 151 } 152 153 static void next(Node& node) { 154 node.id; 155 } 156 157 void first(Edge& edge) const { 158 edge.id = EdgeNum1; 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; 39 190 40 191 ///A full graph class. … … 50 201 /// 51 202 ///\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 NodeNum1; }83 /// Maximum edge ID.84 85 /// Maximum edge ID.86 ///\sa id(Edge)87 int maxEdgeId() const { return EdgeNum1; }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 than96 /// \ref maxNodeId(). The range of the ID's is not surely continuous97 /// 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 than106 /// \ref maxEdgeId(). The range of the ID's is not surely continuous107 /// 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), then118 /// It finds the first edge from \c u to \c v. Otherwise it looks for119 /// 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 = NodeNum1;163 }164 165 static void next(Node& node) {166 node.id;167 }168 169 void first(Edge& edge) const {170 edge.id = EdgeNum1;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 203 203 class FullGraph : public MappableFullGraphBase { 204 204 public:
Note: See TracChangeset
for help on using the changeset viewer.