1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/full_graph.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,248 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/full_graph.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, 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 +///\ingroup graphs
1.24 +///\file
1.25 +///\brief FullGraph and SymFullGraph classes.
1.26 +
1.27 +#include <vector>
1.28 +#include <climits>
1.29 +
1.30 +#include <lemon/invalid.h>
1.31 +
1.32 +#include <lemon/map_registry.h>
1.33 +#include <lemon/array_map.h>
1.34 +
1.35 +#include <lemon/map_defines.h>
1.36 +
1.37 +namespace lemon {
1.38 +
1.39 +/// \addtogroup graphs
1.40 +/// @{
1.41 +
1.42 + ///A full graph class.
1.43 +
1.44 + ///This is a simple and fast directed full graph implementation.
1.45 + ///It is completely static, so you can neither add nor delete either
1.46 + ///edges or nodes.
1.47 + ///Thus it conforms to
1.48 + ///the \ref skeleton::StaticGraph "StaticGraph" concept
1.49 + ///\sa skeleton::StaticGraph.
1.50 + ///\todo What about loops?
1.51 + ///\todo Don't we need SymEdgeMap?
1.52 + ///
1.53 + ///\author Alpar Juttner
1.54 + class FullGraph {
1.55 + int NodeNum;
1.56 + int EdgeNum;
1.57 + public:
1.58 +
1.59 + typedef FullGraph Graph;
1.60 +
1.61 + class Node;
1.62 + class Edge;
1.63 +
1.64 + class NodeIt;
1.65 + class EdgeIt;
1.66 + class OutEdgeIt;
1.67 + class InEdgeIt;
1.68 +
1.69 +
1.70 + // Create map registries.
1.71 + CREATE_MAP_REGISTRIES;
1.72 + // Create node and edge maps.
1.73 + CREATE_MAPS(ArrayMap);
1.74 +
1.75 + public:
1.76 +
1.77 + ///Creates a full graph with \c n nodes.
1.78 + FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
1.79 + ///
1.80 + FullGraph(const FullGraph &_g)
1.81 + : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
1.82 +
1.83 + ///Number of nodes.
1.84 + int nodeNum() const { return NodeNum; }
1.85 + ///Number of edges.
1.86 + int edgeNum() const { return EdgeNum; }
1.87 +
1.88 + /// Maximum node ID.
1.89 +
1.90 + /// Maximum node ID.
1.91 + ///\sa id(Node)
1.92 + int maxNodeId() const { return NodeNum-1; }
1.93 + /// Maximum edge ID.
1.94 +
1.95 + /// Maximum edge ID.
1.96 + ///\sa id(Edge)
1.97 + int maxEdgeId() const { return EdgeNum-1; }
1.98 +
1.99 + Node tail(Edge e) const { return e.n%NodeNum; }
1.100 + Node head(Edge e) const { return e.n/NodeNum; }
1.101 +
1.102 + NodeIt& first(NodeIt& v) const {
1.103 + v=NodeIt(*this); return v; }
1.104 + EdgeIt& first(EdgeIt& e) const {
1.105 + e=EdgeIt(*this); return e; }
1.106 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.107 + e=OutEdgeIt(*this,v); return e; }
1.108 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.109 + e=InEdgeIt(*this,v); return e; }
1.110 +
1.111 + /// Node ID.
1.112 +
1.113 + /// The ID of a valid Node is a nonnegative integer not greater than
1.114 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.115 + /// and the greatest node ID can be actually less then \ref maxNodeId().
1.116 + ///
1.117 + /// The ID of the \ref INVALID node is -1.
1.118 + ///\return The ID of the node \c v.
1.119 + static int id(Node v) { return v.n; }
1.120 + /// Edge ID.
1.121 +
1.122 + /// The ID of a valid Edge is a nonnegative integer not greater than
1.123 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.124 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.125 + ///
1.126 + /// The ID of the \ref INVALID edge is -1.
1.127 + ///\return The ID of the edge \c e.
1.128 + static int id(Edge e) { return e.n; }
1.129 +
1.130 + /// Finds an edge between two nodes.
1.131 +
1.132 + /// Finds an edge from node \c u to node \c v.
1.133 + ///
1.134 + /// If \c prev is \ref INVALID (this is the default value), then
1.135 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.136 + /// the next edge from \c u to \c v after \c prev.
1.137 + /// \return The found edge or INVALID if there is no such an edge.
1.138 + Edge findEdge(Node u,Node v, Edge prev = INVALID)
1.139 + {
1.140 + return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
1.141 + }
1.142 +
1.143 +
1.144 + class Node {
1.145 + friend class FullGraph;
1.146 + template <typename T> friend class NodeMap;
1.147 +
1.148 + friend class Edge;
1.149 + friend class OutEdgeIt;
1.150 + friend class InEdgeIt;
1.151 + friend class SymEdge;
1.152 +
1.153 + protected:
1.154 + int n;
1.155 + friend int FullGraph::id(Node v);
1.156 + Node(int nn) {n=nn;}
1.157 + public:
1.158 + Node() {}
1.159 + Node (Invalid) { n=-1; }
1.160 + bool operator==(const Node i) const {return n==i.n;}
1.161 + bool operator!=(const Node i) const {return n!=i.n;}
1.162 + bool operator<(const Node i) const {return n<i.n;}
1.163 + };
1.164 +
1.165 + class NodeIt : public Node {
1.166 + const FullGraph *G;
1.167 + friend class FullGraph;
1.168 + public:
1.169 + NodeIt() : Node() { }
1.170 + NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
1.171 + NodeIt(Invalid i) : Node(i) { }
1.172 + NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
1.173 + ///\todo Undocumented conversion Node -\> NodeIt.
1.174 + NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
1.175 + };
1.176 +
1.177 + class Edge {
1.178 + friend class FullGraph;
1.179 + template <typename T> friend class EdgeMap;
1.180 +
1.181 + friend class Node;
1.182 + friend class NodeIt;
1.183 + protected:
1.184 + int n; //NodeNum*head+tail;
1.185 + friend int FullGraph::id(Edge e);
1.186 +
1.187 + Edge(int nn) : n(nn) {}
1.188 + Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
1.189 + public:
1.190 + Edge() { }
1.191 + Edge (Invalid) { n=-1; }
1.192 + bool operator==(const Edge i) const {return n==i.n;}
1.193 + bool operator!=(const Edge i) const {return n!=i.n;}
1.194 + bool operator<(const Edge i) const {return n<i.n;}
1.195 + ///\bug This is a workaround until somebody tells me how to
1.196 + ///make class \c SymFullGraph::SymEdgeMap friend of Edge
1.197 + int &idref() {return n;}
1.198 + const int &idref() const {return n;}
1.199 + };
1.200 +
1.201 + class EdgeIt : public Edge {
1.202 + friend class FullGraph;
1.203 + public:
1.204 + EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
1.205 + EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
1.206 + EdgeIt (Invalid i) : Edge(i) { }
1.207 + EdgeIt() : Edge() { }
1.208 + EdgeIt& operator++() { --n; return *this; }
1.209 +
1.210 + ///\bug This is a workaround until somebody tells me how to
1.211 + ///make class \c SymFullGraph::SymEdgeMap friend of Edge
1.212 + int &idref() {return n;}
1.213 + };
1.214 +
1.215 + class OutEdgeIt : public Edge {
1.216 + const FullGraph *G;
1.217 + friend class FullGraph;
1.218 + public:
1.219 + OutEdgeIt() : Edge() { }
1.220 + OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
1.221 + OutEdgeIt (Invalid i) : Edge(i) { }
1.222 +
1.223 + OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
1.224 +
1.225 + OutEdgeIt& operator++()
1.226 + { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
1.227 +
1.228 + };
1.229 +
1.230 + class InEdgeIt : public Edge {
1.231 + const FullGraph *G;
1.232 + friend class FullGraph;
1.233 + public:
1.234 + InEdgeIt() : Edge() { }
1.235 + InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
1.236 + InEdgeIt (Invalid i) : Edge(i) { }
1.237 + InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
1.238 + InEdgeIt& operator++()
1.239 + { if(!((++n)%G->NodeNum)) n=-1; return *this; }
1.240 + };
1.241 +
1.242 + };
1.243 +
1.244 + /// @}
1.245 +
1.246 +} //namespace lemon
1.247 +
1.248 +
1.249 +
1.250 +
1.251 +#endif //LEMON_FULL_GRAPH_H