1.1 --- a/src/lemon/full_graph.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,385 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/full_graph.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef LEMON_FULL_GRAPH_H
1.21 -#define LEMON_FULL_GRAPH_H
1.22 -
1.23 -#include <cmath>
1.24 -
1.25 -
1.26 -#include <lemon/bits/iterable_graph_extender.h>
1.27 -#include <lemon/bits/alteration_notifier.h>
1.28 -#include <lemon/bits/default_map.h>
1.29 -
1.30 -#include <lemon/invalid.h>
1.31 -#include <lemon/utility.h>
1.32 -
1.33 -
1.34 -///\ingroup graphs
1.35 -///\file
1.36 -///\brief FullGraph and SymFullGraph classes.
1.37 -
1.38 -
1.39 -namespace lemon {
1.40 -
1.41 -/// \addtogroup graphs
1.42 -/// @{
1.43 -
1.44 - class FullGraphBase {
1.45 - int NodeNum;
1.46 - int EdgeNum;
1.47 - public:
1.48 -
1.49 - typedef FullGraphBase Graph;
1.50 -
1.51 - class Node;
1.52 - class Edge;
1.53 -
1.54 - public:
1.55 -
1.56 - FullGraphBase() {}
1.57 -
1.58 -
1.59 - ///Creates a full graph with \c n nodes.
1.60 - void construct(int n) { NodeNum = n; EdgeNum = n * n; }
1.61 - ///
1.62 - // FullGraphBase(const FullGraphBase &_g)
1.63 - // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
1.64 -
1.65 - typedef True NodeNumTag;
1.66 - typedef True EdgeNumTag;
1.67 -
1.68 - ///Number of nodes.
1.69 - int nodeNum() const { return NodeNum; }
1.70 - ///Number of edges.
1.71 - int edgeNum() const { return EdgeNum; }
1.72 -
1.73 - /// Maximum node ID.
1.74 -
1.75 - /// Maximum node ID.
1.76 - ///\sa id(Node)
1.77 - int maxId(Node = INVALID) const { return NodeNum-1; }
1.78 - /// Maximum edge ID.
1.79 -
1.80 - /// Maximum edge ID.
1.81 - ///\sa id(Edge)
1.82 - int maxId(Edge = INVALID) const { return EdgeNum-1; }
1.83 -
1.84 - Node source(Edge e) const { return e.id % NodeNum; }
1.85 - Node target(Edge e) const { return e.id / NodeNum; }
1.86 -
1.87 -
1.88 - /// Node ID.
1.89 -
1.90 - /// The ID of a valid Node is a nonnegative integer not greater than
1.91 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.92 - /// and the greatest node ID can be actually less then \ref maxNodeId().
1.93 - ///
1.94 - /// The ID of the \ref INVALID node is -1.
1.95 - ///\return The ID of the node \c v.
1.96 -
1.97 - static int id(Node v) { return v.id; }
1.98 - /// Edge ID.
1.99 -
1.100 - /// The ID of a valid Edge is a nonnegative integer not greater than
1.101 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.102 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.103 - ///
1.104 - /// The ID of the \ref INVALID edge is -1.
1.105 - ///\return The ID of the edge \c e.
1.106 - static int id(Edge e) { return e.id; }
1.107 -
1.108 - static Node fromId(int id, Node) { return Node(id);}
1.109 -
1.110 - static Edge fromId(int id, Edge) { return Edge(id);}
1.111 -
1.112 - /// Finds an edge between two nodes.
1.113 -
1.114 - /// Finds an edge from node \c u to node \c v.
1.115 - ///
1.116 - /// If \c prev is \ref INVALID (this is the default value), then
1.117 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.118 - /// the next edge from \c u to \c v after \c prev.
1.119 - /// \return The found edge or INVALID if there is no such an edge.
1.120 - Edge findEdge(Node u,Node v, Edge prev = INVALID)
1.121 - {
1.122 - return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
1.123 - }
1.124 -
1.125 -
1.126 - class Node {
1.127 - friend class FullGraphBase;
1.128 -
1.129 - protected:
1.130 - int id;
1.131 - Node(int _id) { id = _id;}
1.132 - public:
1.133 - Node() {}
1.134 - Node (Invalid) { id = -1; }
1.135 - bool operator==(const Node node) const {return id == node.id;}
1.136 - bool operator!=(const Node node) const {return id != node.id;}
1.137 - bool operator<(const Node node) const {return id < node.id;}
1.138 - };
1.139 -
1.140 -
1.141 -
1.142 - class Edge {
1.143 - friend class FullGraphBase;
1.144 -
1.145 - protected:
1.146 - int id; // NodeNum * target + source;
1.147 -
1.148 - Edge(int _id) : id(_id) {}
1.149 -
1.150 - Edge(const FullGraphBase& _graph, int source, int target)
1.151 - : id(_graph.NodeNum * target+source) {}
1.152 - public:
1.153 - Edge() { }
1.154 - Edge (Invalid) { id = -1; }
1.155 - bool operator==(const Edge edge) const {return id == edge.id;}
1.156 - bool operator!=(const Edge edge) const {return id != edge.id;}
1.157 - bool operator<(const Edge edge) const {return id < edge.id;}
1.158 - };
1.159 -
1.160 - void first(Node& node) const {
1.161 - node.id = NodeNum-1;
1.162 - }
1.163 -
1.164 - static void next(Node& node) {
1.165 - --node.id;
1.166 - }
1.167 -
1.168 - void first(Edge& edge) const {
1.169 - edge.id = EdgeNum-1;
1.170 - }
1.171 -
1.172 - static void next(Edge& edge) {
1.173 - --edge.id;
1.174 - }
1.175 -
1.176 - void firstOut(Edge& edge, const Node& node) const {
1.177 - edge.id = EdgeNum + node.id - NodeNum;
1.178 - }
1.179 -
1.180 - void nextOut(Edge& edge) const {
1.181 - edge.id -= NodeNum;
1.182 - if (edge.id < 0) edge.id = -1;
1.183 - }
1.184 -
1.185 - void firstIn(Edge& edge, const Node& node) const {
1.186 - edge.id = node.id * NodeNum;
1.187 - }
1.188 -
1.189 - void nextIn(Edge& edge) const {
1.190 - ++edge.id;
1.191 - if (edge.id % NodeNum == 0) edge.id = -1;
1.192 - }
1.193 -
1.194 - };
1.195 -
1.196 -
1.197 - typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
1.198 - typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
1.199 - typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase;
1.200 -
1.201 - ///A full graph class.
1.202 -
1.203 - ///This is a simple and fast directed full graph implementation.
1.204 - ///It is completely static, so you can neither add nor delete either
1.205 - ///edges or nodes.
1.206 - ///Thus it conforms to
1.207 - ///the \ref concept::StaticGraph "StaticGraph" concept
1.208 - ///\sa concept::StaticGraph.
1.209 - ///
1.210 - ///\author Alpar Juttner
1.211 - class FullGraph : public MappableFullGraphBase {
1.212 - public:
1.213 -
1.214 - FullGraph(int n) { construct(n); }
1.215 - };
1.216 -
1.217 -
1.218 - // Base graph class for UndirFullGraph.
1.219 - class UndirFullGraphBase {
1.220 - int NodeNum;
1.221 - int EdgeNum;
1.222 - public:
1.223 -
1.224 - typedef UndirFullGraphBase Graph;
1.225 -
1.226 - class Node;
1.227 - class Edge;
1.228 -
1.229 - public:
1.230 -
1.231 - UndirFullGraphBase() {}
1.232 -
1.233 -
1.234 - ///Creates a full graph with \c n nodes.
1.235 - void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; }
1.236 - ///
1.237 - // FullGraphBase(const FullGraphBase &_g)
1.238 - // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
1.239 -
1.240 - typedef True NodeNumTag;
1.241 - typedef True EdgeNumTag;
1.242 -
1.243 - ///Number of nodes.
1.244 - int nodeNum() const { return NodeNum; }
1.245 - ///Number of edges.
1.246 - int edgeNum() const { return EdgeNum; }
1.247 -
1.248 - /// Maximum node ID.
1.249 -
1.250 - /// Maximum node ID.
1.251 - ///\sa id(Node)
1.252 - int maxId(Node = INVALID) const { return NodeNum-1; }
1.253 - /// Maximum edge ID.
1.254 -
1.255 - /// Maximum edge ID.
1.256 - ///\sa id(Edge)
1.257 - int maxId(Edge = INVALID) const { return EdgeNum-1; }
1.258 -
1.259 - Node source(Edge e) const {
1.260 - /// \todo we may do it faster
1.261 - return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;
1.262 - }
1.263 -
1.264 - Node target(Edge e) const {
1.265 - int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
1.266 - return e.id - (source) * (source - 1) / 2;
1.267 - }
1.268 -
1.269 -
1.270 - /// Node ID.
1.271 -
1.272 - /// The ID of a valid Node is a nonnegative integer not greater than
1.273 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.274 - /// and the greatest node ID can be actually less then \ref maxNodeId().
1.275 - ///
1.276 - /// The ID of the \ref INVALID node is -1.
1.277 - ///\return The ID of the node \c v.
1.278 -
1.279 - static int id(Node v) { return v.id; }
1.280 - /// Edge ID.
1.281 -
1.282 - /// The ID of a valid Edge is a nonnegative integer not greater than
1.283 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.284 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.285 - ///
1.286 - /// The ID of the \ref INVALID edge is -1.
1.287 - ///\return The ID of the edge \c e.
1.288 - static int id(Edge e) { return e.id; }
1.289 -
1.290 - /// Finds an edge between two nodes.
1.291 -
1.292 - /// Finds an edge from node \c u to node \c v.
1.293 - ///
1.294 - /// If \c prev is \ref INVALID (this is the default value), then
1.295 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.296 - /// the next edge from \c u to \c v after \c prev.
1.297 - /// \return The found edge or INVALID if there is no such an edge.
1.298 - Edge findEdge(Node u,Node v, Edge prev = INVALID)
1.299 - {
1.300 - return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
1.301 - }
1.302 -
1.303 -
1.304 - class Node {
1.305 - friend class UndirFullGraphBase;
1.306 -
1.307 - protected:
1.308 - int id;
1.309 - Node(int _id) { id = _id;}
1.310 - public:
1.311 - Node() {}
1.312 - Node (Invalid) { id = -1; }
1.313 - bool operator==(const Node node) const {return id == node.id;}
1.314 - bool operator!=(const Node node) const {return id != node.id;}
1.315 - bool operator<(const Node node) const {return id < node.id;}
1.316 - };
1.317 -
1.318 -
1.319 -
1.320 - class Edge {
1.321 - friend class UndirFullGraphBase;
1.322 -
1.323 - protected:
1.324 - int id; // NodeNum * target + source;
1.325 -
1.326 - Edge(int _id) : id(_id) {}
1.327 -
1.328 - Edge(const UndirFullGraphBase& _graph, int source, int target)
1.329 - : id(_graph.NodeNum * target+source) {}
1.330 - public:
1.331 - Edge() { }
1.332 - Edge (Invalid) { id = -1; }
1.333 - bool operator==(const Edge edge) const {return id == edge.id;}
1.334 - bool operator!=(const Edge edge) const {return id != edge.id;}
1.335 - bool operator<(const Edge edge) const {return id < edge.id;}
1.336 - };
1.337 -
1.338 - void first(Node& node) const {
1.339 - node.id = NodeNum-1;
1.340 - }
1.341 -
1.342 - static void next(Node& node) {
1.343 - --node.id;
1.344 - }
1.345 -
1.346 - void first(Edge& edge) const {
1.347 - edge.id = EdgeNum-1;
1.348 - }
1.349 -
1.350 - static void next(Edge& edge) {
1.351 - --edge.id;
1.352 - }
1.353 -
1.354 - void firstOut(Edge& edge, const Node& node) const {
1.355 - edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
1.356 - }
1.357 -
1.358 - /// \todo with specialized iterators we can make faster iterating
1.359 - void nextOut(Edge& e) const {
1.360 - int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
1.361 - int target = e.id - (source) * (source - 1) / 2;
1.362 - ++target;
1.363 - e.id = target < source ? source * (source - 1) / 2 + target : -1;
1.364 - }
1.365 -
1.366 - void firstIn(Edge& edge, const Node& node) const {
1.367 - edge.id = node.id * (node.id + 1) / 2 - 1;
1.368 - }
1.369 -
1.370 - void nextIn(Edge& e) const {
1.371 - int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
1.372 - int target = e.id - (source) * (source - 1) / 2; ++target;
1.373 - ++source;
1.374 - e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1;
1.375 - }
1.376 -
1.377 - };
1.378 -
1.379 - /// \todo UndirFullGraph from the UndirFullGraphBase
1.380 -
1.381 -
1.382 -
1.383 - /// @}
1.384 -
1.385 -} //namespace lemon
1.386 -
1.387 -
1.388 -#endif //LEMON_FULL_GRAPH_H