Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/full_graph.h
- Timestamp:
- 10/28/04 00:38:50 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/full_graph.h
r921 r946 18 18 #define LEMON_FULL_GRAPH_H 19 19 20 21 #include <lemon/idmappable_graph_extender.h> 22 23 #include <lemon/iterable_graph_extender.h> 24 25 #include <lemon/alteration_observer_registry.h> 26 #include <lemon/default_map.h> 27 20 28 ///\ingroup graphs 21 29 ///\file 22 30 ///\brief FullGraph and SymFullGraph classes. 23 31 24 #include <vector>25 #include <climits>26 32 27 33 #include <lemon/invalid.h> 28 29 #include <lemon/map_registry.h>30 #include <lemon/array_map.h>31 32 #include <lemon/map_defines.h>33 34 34 35 namespace lemon { … … 49 50 /// 50 51 ///\author Alpar Juttner 51 class FullGraph {52 class FullGraphBase { 52 53 int NodeNum; 53 54 int EdgeNum; 54 55 public: 55 56 56 typedef FullGraph Graph;57 typedef FullGraphBase Graph; 57 58 58 59 class Node; 59 60 class Edge; 60 61 61 class NodeIt;62 class EdgeIt;63 class OutEdgeIt;64 class InEdgeIt;65 66 67 // Create map registries.68 CREATE_MAP_REGISTRIES;69 // Create node and edge maps.70 CREATE_MAPS(ArrayMap);71 72 62 public: 73 63 64 FullGraphBase() {} 65 66 74 67 ///Creates a full graph with \c n nodes. 75 FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) {}76 /// 77 FullGraph(const FullGraph&_g)78 : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }68 void construct(int n) { NodeNum = n; EdgeNum = n * n; } 69 /// 70 // FullGraphBase(const FullGraphBase &_g) 71 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } 79 72 80 73 ///Number of nodes. … … 94 87 int maxEdgeId() const { return EdgeNum-1; } 95 88 96 Node tail(Edge e) const { return e.n%NodeNum; } 97 Node head(Edge e) const { return e.n/NodeNum; } 98 99 NodeIt& first(NodeIt& v) const { 100 v=NodeIt(*this); return v; } 101 EdgeIt& first(EdgeIt& e) const { 102 e=EdgeIt(*this); return e; } 103 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 104 e=OutEdgeIt(*this,v); return e; } 105 InEdgeIt& first(InEdgeIt& e, const Node v) const { 106 e=InEdgeIt(*this,v); return e; } 89 Node tail(Edge e) const { return e.id % NodeNum; } 90 Node head(Edge e) const { return e.id / NodeNum; } 91 107 92 108 93 /// Node ID. … … 114 99 /// The ID of the \ref INVALID node is -1. 115 100 ///\return The ID of the node \c v. 116 static int id(Node v) { return v.n; } 101 102 static int id(Node v) { return v.id; } 117 103 /// Edge ID. 118 104 … … 123 109 /// The ID of the \ref INVALID edge is -1. 124 110 ///\return The ID of the edge \c e. 125 static int id(Edge e) { return e. n; }111 static int id(Edge e) { return e.id; } 126 112 127 113 /// Finds an edge between two nodes. … … 135 121 Edge findEdge(Node u,Node v, Edge prev = INVALID) 136 122 { 137 return prev. n == -1 ? Edge(*this, u.n, v.n) : INVALID;123 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; 138 124 } 139 125 140 126 141 127 class Node { 142 friend class FullGraph; 143 template <typename T> friend class NodeMap; 144 145 friend class Edge; 146 friend class OutEdgeIt; 147 friend class InEdgeIt; 148 friend class SymEdge; 128 friend class FullGraphBase; 149 129 150 130 protected: 151 int n; 152 friend int FullGraph::id(Node v); 153 Node(int nn) {n=nn;} 131 int id; 132 Node(int _id) { id = _id;} 154 133 public: 155 134 Node() {} 156 Node (Invalid) { n=-1; }157 bool operator==(const Node i) const {return n==i.n;}158 bool operator!=(const Node i) const {return n!=i.n;}159 bool operator<(const Node i) const {return n<i.n;}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;} 160 139 }; 161 140 162 class NodeIt : public Node { 163 const FullGraph *G; 164 friend class FullGraph; 165 public: 166 NodeIt() : Node() { } 167 NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { } 168 NodeIt(Invalid i) : Node(i) { } 169 NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { } 170 ///\todo Undocumented conversion Node -\> NodeIt. 171 NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; } 172 }; 141 173 142 174 143 class Edge { 175 friend class FullGraph; 176 template <typename T> friend class EdgeMap; 144 friend class FullGraphBase; 177 145 178 friend class Node;179 friend class NodeIt;180 146 protected: 181 int n; //NodeNum*head+tail; 182 friend int FullGraph::id(Edge e); 183 184 Edge(int nn) : n(nn) {} 185 Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {} 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) {} 186 153 public: 187 154 Edge() { } 188 Edge (Invalid) { n=-1; } 189 bool operator==(const Edge i) const {return n==i.n;} 190 bool operator!=(const Edge i) const {return n!=i.n;} 191 bool operator<(const Edge i) const {return n<i.n;} 192 ///\bug This is a workaround until somebody tells me how to 193 ///make class \c SymFullGraph::SymEdgeMap friend of Edge 194 int &idref() {return n;} 195 const int &idref() const {return n;} 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;} 196 159 }; 197 198 class EdgeIt : public Edge { 199 friend class FullGraph; 200 public: 201 EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { } 202 EdgeIt(const FullGraph&, Edge e) : Edge(e) { } 203 EdgeIt (Invalid i) : Edge(i) { } 204 EdgeIt() : Edge() { } 205 EdgeIt& operator++() { --n; return *this; } 206 207 ///\bug This is a workaround until somebody tells me how to 208 ///make class \c SymFullGraph::SymEdgeMap friend of Edge 209 int &idref() {return n;} 210 }; 211 212 class OutEdgeIt : public Edge { 213 const FullGraph *G; 214 friend class FullGraph; 215 public: 216 OutEdgeIt() : Edge() { } 217 OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { } 218 OutEdgeIt (Invalid i) : Edge(i) { } 219 220 OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {} 221 222 OutEdgeIt& operator++() 223 { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; } 224 225 }; 226 227 class InEdgeIt : public Edge { 228 const FullGraph *G; 229 friend class FullGraph; 230 public: 231 InEdgeIt() : Edge() { } 232 InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { } 233 InEdgeIt (Invalid i) : Edge(i) { } 234 InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {} 235 InEdgeIt& operator++() 236 { if(!((++n)%G->NodeNum)) n=-1; return *this; } 237 }; 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 } 238 194 239 195 }; 240 196 197 198 typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase; 199 typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase; 200 typedef IdMappableGraphExtender<IterableFullGraphBase> IdMappableFullGraphBase; 201 typedef DefaultMappableGraphExtender<IdMappableFullGraphBase> MappableFullGraphBase; 202 203 class FullGraph : public MappableFullGraphBase { 204 public: 205 206 FullGraph(int n) { construct(n); } 207 }; 208 209 template <> 210 int countNodes<FullGraph>(const FullGraph& graph) { 211 return graph.nodeNum(); 212 } 213 214 template <> 215 int countEdges<FullGraph>(const FullGraph& graph) { 216 return graph.edgeNum(); 217 } 218 241 219 /// @} 242 220
Note: See TracChangeset
for help on using the changeset viewer.