1.1 --- a/lemon/full_ugraph.h Fri Jun 30 12:14:36 2006 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,280 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * This file is a part of LEMON, a generic C++ optimization library
1.7 - *
1.8 - * Copyright (C) 2003-2006
1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 - *
1.12 - * Permission to use, modify and distribute this software is granted
1.13 - * provided that this copyright notice appears in all copies. For
1.14 - * precise terms see the accompanying LICENSE file.
1.15 - *
1.16 - * This software is provided "AS IS" with no warranty of any kind,
1.17 - * express or implied, and with no claim as to its suitability for any
1.18 - * purpose.
1.19 - *
1.20 - */
1.21 -
1.22 -#ifndef LEMON_FULL_UGRAPH_H
1.23 -#define LEMON_FULL_UGRAPH_H
1.24 -
1.25 -#include <cmath>
1.26 -
1.27 -#include <lemon/bits/base_extender.h>
1.28 -#include <lemon/bits/ugraph_extender.h>
1.29 -
1.30 -#include <lemon/bits/invalid.h>
1.31 -#include <lemon/bits/utility.h>
1.32 -
1.33 -
1.34 -///\ingroup graphs
1.35 -///\file
1.36 -///\brief FullUGraph classes.
1.37 -
1.38 -
1.39 -namespace lemon {
1.40 -
1.41 - /// \brief Base of the FullUGrpah.
1.42 - ///
1.43 - /// Base of the FullUGrpah.
1.44 - class FullUGraphBase {
1.45 - int _nodeNum;
1.46 - int _edgeNum;
1.47 - public:
1.48 -
1.49 - typedef FullUGraphBase Graph;
1.50 -
1.51 - class Node;
1.52 - class Edge;
1.53 -
1.54 - public:
1.55 -
1.56 - FullUGraphBase() {}
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) / 2; }
1.61 -
1.62 - /// \brief Returns the node with the given index.
1.63 - ///
1.64 - /// Returns the node with the given index. Because it is a
1.65 - /// static size graph the node's of the graph can be indiced
1.66 - /// by the range from 0 to \e nodeNum()-1 and the index of
1.67 - /// the node can accessed by the \e index() member.
1.68 - Node operator()(int index) const { return Node(index); }
1.69 -
1.70 - /// \brief Returns the index of the node.
1.71 - ///
1.72 - /// Returns the index of the node. Because it is a
1.73 - /// static size graph the node's of the graph can be indiced
1.74 - /// by the range from 0 to \e nodeNum()-1 and the index of
1.75 - /// the node can accessed by the \e index() member.
1.76 - int index(const Node& node) const { return node.id; }
1.77 -
1.78 - typedef True NodeNumTag;
1.79 - typedef True EdgeNumTag;
1.80 -
1.81 - ///Number of nodes.
1.82 - int nodeNum() const { return _nodeNum; }
1.83 - ///Number of edges.
1.84 - int edgeNum() const { return _edgeNum; }
1.85 -
1.86 - /// Maximum node ID.
1.87 -
1.88 - /// Maximum node ID.
1.89 - ///\sa id(Node)
1.90 - int maxNodeId() const { return _nodeNum-1; }
1.91 - /// Maximum edge ID.
1.92 -
1.93 - /// Maximum edge ID.
1.94 - ///\sa id(Edge)
1.95 - int maxEdgeId() const { return _edgeNum-1; }
1.96 -
1.97 - /// \brief Returns the node from its \c id.
1.98 - ///
1.99 - /// Returns the node from its \c id. If there is not node
1.100 - /// with the given id the effect of the function is undefinied.
1.101 - static Node nodeFromId(int id) { return Node(id);}
1.102 -
1.103 - /// \brief Returns the edge from its \c id.
1.104 - ///
1.105 - /// Returns the edge from its \c id. If there is not edge
1.106 - /// with the given id the effect of the function is undefinied.
1.107 - static Edge edgeFromId(int id) { return Edge(id);}
1.108 -
1.109 - Node source(Edge e) const {
1.110 - /// \todo we may do it faster
1.111 - return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
1.112 - }
1.113 -
1.114 - Node target(Edge e) const {
1.115 - int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
1.116 - return Node(e.id - (source) * (source - 1) / 2);
1.117 - }
1.118 -
1.119 -
1.120 - /// \brief Node ID.
1.121 - ///
1.122 - /// The ID of a valid Node is a nonnegative integer not greater than
1.123 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.124 - /// and the greatest node ID can be actually less then \ref maxNodeId().
1.125 - ///
1.126 - /// The ID of the \ref INVALID node is -1.
1.127 - /// \return The ID of the node \c v.
1.128 -
1.129 - static int id(Node v) { return v.id; }
1.130 -
1.131 - /// \brief Edge ID.
1.132 - ///
1.133 - /// The ID of a valid Edge is a nonnegative integer not greater than
1.134 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.135 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.136 - ///
1.137 - /// The ID of the \ref INVALID edge is -1.
1.138 - ///\return The ID of the edge \c e.
1.139 - static int id(Edge e) { return e.id; }
1.140 -
1.141 - /// \brief Finds an edge between two nodes.
1.142 - ///
1.143 - /// Finds an edge from node \c u to node \c v.
1.144 - ///
1.145 - /// If \c prev is \ref INVALID (this is the default value), then
1.146 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.147 - /// the next edge from \c u to \c v after \c prev.
1.148 - /// \return The found edge or INVALID if there is no such an edge.
1.149 - Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.150 - if (prev.id != -1 || u.id <= v.id) return Edge(-1);
1.151 - return Edge(u.id * (u.id - 1) / 2 + v.id);
1.152 - }
1.153 -
1.154 - typedef True FindEdgeTag;
1.155 -
1.156 -
1.157 - class Node {
1.158 - friend class FullUGraphBase;
1.159 -
1.160 - protected:
1.161 - int id;
1.162 - Node(int _id) { id = _id;}
1.163 - public:
1.164 - Node() {}
1.165 - Node (Invalid) { id = -1; }
1.166 - bool operator==(const Node node) const {return id == node.id;}
1.167 - bool operator!=(const Node node) const {return id != node.id;}
1.168 - bool operator<(const Node node) const {return id < node.id;}
1.169 - };
1.170 -
1.171 -
1.172 -
1.173 - class Edge {
1.174 - friend class FullUGraphBase;
1.175 -
1.176 - protected:
1.177 - int id; // _nodeNum * target + source;
1.178 -
1.179 - Edge(int _id) : id(_id) {}
1.180 -
1.181 - public:
1.182 - Edge() { }
1.183 - Edge (Invalid) { id = -1; }
1.184 - bool operator==(const Edge edge) const {return id == edge.id;}
1.185 - bool operator!=(const Edge edge) const {return id != edge.id;}
1.186 - bool operator<(const Edge edge) const {return id < edge.id;}
1.187 - };
1.188 -
1.189 - void first(Node& node) const {
1.190 - node.id = _nodeNum - 1;
1.191 - }
1.192 -
1.193 - static void next(Node& node) {
1.194 - --node.id;
1.195 - }
1.196 -
1.197 - void first(Edge& edge) const {
1.198 - edge.id = _edgeNum - 1;
1.199 - }
1.200 -
1.201 - static void next(Edge& edge) {
1.202 - --edge.id;
1.203 - }
1.204 -
1.205 - void firstOut(Edge& edge, const Node& node) const {
1.206 - int src = node.id;
1.207 - int trg = 0;
1.208 - edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
1.209 - }
1.210 -
1.211 - /// \todo with specialized iterators we can make faster iterating
1.212 - void nextOut(Edge& edge) const {
1.213 - int src = source(edge).id;
1.214 - int trg = target(edge).id;
1.215 - ++trg;
1.216 - edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
1.217 - }
1.218 -
1.219 - void firstIn(Edge& edge, const Node& node) const {
1.220 - int src = node.id + 1;
1.221 - int trg = node.id;
1.222 - edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
1.223 - }
1.224 -
1.225 - void nextIn(Edge& edge) const {
1.226 - int src = source(edge).id;
1.227 - int trg = target(edge).id;
1.228 - ++src;
1.229 - edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
1.230 - }
1.231 -
1.232 - };
1.233 -
1.234 - typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
1.235 - ExtendedFullUGraphBase;
1.236 -
1.237 - /// \ingroup graphs
1.238 - ///
1.239 - /// \brief An undirected full graph class.
1.240 - ///
1.241 - /// This is a simple and fast undirected full graph implementation.
1.242 - /// It is completely static, so you can neither add nor delete either
1.243 - /// edges or nodes.
1.244 - ///
1.245 - /// The main difference beetween the \e FullGraph and \e FullUGraph class
1.246 - /// is that this class conforms to the undirected graph concept and
1.247 - /// it does not contain the loop edges.
1.248 - ///
1.249 - /// \sa FullUGraphBase
1.250 - /// \sa FullGraph
1.251 - ///
1.252 - /// \author Balazs Dezso
1.253 - class FullUGraph : public ExtendedFullUGraphBase {
1.254 - public:
1.255 -
1.256 - typedef ExtendedFullUGraphBase Parent;
1.257 -
1.258 - /// \brief Constructor
1.259 - FullUGraph() { construct(0); }
1.260 -
1.261 - /// \brief Constructor
1.262 - FullUGraph(int n) { construct(n); }
1.263 -
1.264 - /// \brief Resize the graph
1.265 - ///
1.266 - /// Resize the graph. The function will fully destroy and build the graph.
1.267 - /// This cause that the maps of the graph will reallocated
1.268 - /// automatically and the previous values will be lost.
1.269 - void resize(int n) {
1.270 - Parent::getNotifier(Edge()).clear();
1.271 - Parent::getNotifier(UEdge()).clear();
1.272 - Parent::getNotifier(Node()).clear();
1.273 - construct(n);
1.274 - Parent::getNotifier(Node()).build();
1.275 - Parent::getNotifier(UEdge()).build();
1.276 - Parent::getNotifier(Edge()).build();
1.277 - }
1.278 - };
1.279 -
1.280 -} //namespace lemon
1.281 -
1.282 -
1.283 -#endif //LEMON_FULL_GRAPH_H