/* -*- C++ -*- * src/lemon/full_graph.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Combinatorial Optimization Research Group, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #ifndef LEMON_FULL_GRAPH_H #define LEMON_FULL_GRAPH_H #include #include #include #include #include #include ///\ingroup graphs ///\file ///\brief FullGraph and SymFullGraph classes. namespace lemon { /// \addtogroup graphs /// @{ class FullGraphBase { int NodeNum; int EdgeNum; public: typedef FullGraphBase Graph; class Node; class Edge; public: FullGraphBase() {} ///Creates a full graph with \c n nodes. void construct(int n) { NodeNum = n; EdgeNum = n * n; } /// // FullGraphBase(const FullGraphBase &_g) // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } typedef True NodeNumTag; typedef True EdgeNumTag; ///Number of nodes. int nodeNum() const { return NodeNum; } ///Number of edges. int edgeNum() const { return EdgeNum; } /// Maximum node ID. /// Maximum node ID. ///\sa id(Node) int maxId(Node = INVALID) const { return NodeNum-1; } /// Maximum edge ID. /// Maximum edge ID. ///\sa id(Edge) int maxId(Edge = INVALID) const { return EdgeNum-1; } Node source(Edge e) const { return e.id % NodeNum; } Node target(Edge e) const { return e.id / NodeNum; } /// Node ID. /// The ID of a valid Node is a nonnegative integer not greater than /// \ref maxNodeId(). The range of the ID's is not surely continuous /// and the greatest node ID can be actually less then \ref maxNodeId(). /// /// The ID of the \ref INVALID node is -1. ///\return The ID of the node \c v. static int id(Node v) { return v.id; } /// Edge ID. /// The ID of a valid Edge is a nonnegative integer not greater than /// \ref maxEdgeId(). The range of the ID's is not surely continuous /// and the greatest edge ID can be actually less then \ref maxEdgeId(). /// /// The ID of the \ref INVALID edge is -1. ///\return The ID of the edge \c e. static int id(Edge e) { return e.id; } static Node fromId(int id, Node) { return Node(id);} static Edge fromId(int id, Edge) { return Edge(id);} /// Finds an edge between two nodes. /// Finds an edge from node \c u to node \c v. /// /// If \c prev is \ref INVALID (this is the default value), then /// It finds the first edge from \c u to \c v. Otherwise it looks for /// the next edge from \c u to \c v after \c prev. /// \return The found edge or INVALID if there is no such an edge. Edge findEdge(Node u,Node v, Edge prev = INVALID) { return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; } class Node { friend class FullGraphBase; protected: int id; Node(int _id) { id = _id;} public: Node() {} Node (Invalid) { id = -1; } bool operator==(const Node node) const {return id == node.id;} bool operator!=(const Node node) const {return id != node.id;} bool operator<(const Node node) const {return id < node.id;} }; class Edge { friend class FullGraphBase; protected: int id; // NodeNum * target + source; Edge(int _id) : id(_id) {} Edge(const FullGraphBase& _graph, int source, int target) : id(_graph.NodeNum * target+source) {} public: Edge() { } Edge (Invalid) { id = -1; } bool operator==(const Edge edge) const {return id == edge.id;} bool operator!=(const Edge edge) const {return id != edge.id;} bool operator<(const Edge edge) const {return id < edge.id;} }; void first(Node& node) const { node.id = NodeNum-1; } static void next(Node& node) { --node.id; } void first(Edge& edge) const { edge.id = EdgeNum-1; } static void next(Edge& edge) { --edge.id; } void firstOut(Edge& edge, const Node& node) const { edge.id = EdgeNum + node.id - NodeNum; } void nextOut(Edge& edge) const { edge.id -= NodeNum; if (edge.id < 0) edge.id = -1; } void firstIn(Edge& edge, const Node& node) const { edge.id = node.id * NodeNum; } void nextIn(Edge& edge) const { ++edge.id; if (edge.id % NodeNum == 0) edge.id = -1; } }; typedef AlterableGraphExtender AlterableFullGraphBase; typedef IterableGraphExtender IterableFullGraphBase; typedef DefaultMappableGraphExtender MappableFullGraphBase; ///A full graph class. ///This is a simple and fast directed full graph implementation. ///It is completely static, so you can neither add nor delete either ///edges or nodes. ///Thus it conforms to ///the \ref concept::StaticGraph "StaticGraph" concept ///\sa concept::StaticGraph. /// ///\author Alpar Juttner class FullGraph : public MappableFullGraphBase { public: FullGraph(int n) { construct(n); } }; // Base graph class for UndirFullGraph. class UndirFullGraphBase { int NodeNum; int EdgeNum; public: typedef UndirFullGraphBase Graph; class Node; class Edge; public: UndirFullGraphBase() {} ///Creates a full graph with \c n nodes. void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; } /// // FullGraphBase(const FullGraphBase &_g) // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } typedef True NodeNumTag; typedef True EdgeNumTag; ///Number of nodes. int nodeNum() const { return NodeNum; } ///Number of edges. int edgeNum() const { return EdgeNum; } /// Maximum node ID. /// Maximum node ID. ///\sa id(Node) int maxId(Node = INVALID) const { return NodeNum-1; } /// Maximum edge ID. /// Maximum edge ID. ///\sa id(Edge) int maxId(Edge = INVALID) const { return EdgeNum-1; } Node source(Edge e) const { /// \todo we may do it faster return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; } Node target(Edge e) const { int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; return e.id - (source) * (source - 1) / 2; } /// Node ID. /// The ID of a valid Node is a nonnegative integer not greater than /// \ref maxNodeId(). The range of the ID's is not surely continuous /// and the greatest node ID can be actually less then \ref maxNodeId(). /// /// The ID of the \ref INVALID node is -1. ///\return The ID of the node \c v. static int id(Node v) { return v.id; } /// Edge ID. /// The ID of a valid Edge is a nonnegative integer not greater than /// \ref maxEdgeId(). The range of the ID's is not surely continuous /// and the greatest edge ID can be actually less then \ref maxEdgeId(). /// /// The ID of the \ref INVALID edge is -1. ///\return The ID of the edge \c e. static int id(Edge e) { return e.id; } /// Finds an edge between two nodes. /// Finds an edge from node \c u to node \c v. /// /// If \c prev is \ref INVALID (this is the default value), then /// It finds the first edge from \c u to \c v. Otherwise it looks for /// the next edge from \c u to \c v after \c prev. /// \return The found edge or INVALID if there is no such an edge. Edge findEdge(Node u,Node v, Edge prev = INVALID) { return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; } class Node { friend class UndirFullGraphBase; protected: int id; Node(int _id) { id = _id;} public: Node() {} Node (Invalid) { id = -1; } bool operator==(const Node node) const {return id == node.id;} bool operator!=(const Node node) const {return id != node.id;} bool operator<(const Node node) const {return id < node.id;} }; class Edge { friend class UndirFullGraphBase; protected: int id; // NodeNum * target + source; Edge(int _id) : id(_id) {} Edge(const UndirFullGraphBase& _graph, int source, int target) : id(_graph.NodeNum * target+source) {} public: Edge() { } Edge (Invalid) { id = -1; } bool operator==(const Edge edge) const {return id == edge.id;} bool operator!=(const Edge edge) const {return id != edge.id;} bool operator<(const Edge edge) const {return id < edge.id;} }; void first(Node& node) const { node.id = NodeNum-1; } static void next(Node& node) { --node.id; } void first(Edge& edge) const { edge.id = EdgeNum-1; } static void next(Edge& edge) { --edge.id; } void firstOut(Edge& edge, const Node& node) const { edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1; } /// \todo with specialized iterators we can make faster iterating void nextOut(Edge& e) const { int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; int target = e.id - (source) * (source - 1) / 2; ++target; e.id = target < source ? source * (source - 1) / 2 + target : -1; } void firstIn(Edge& edge, const Node& node) const { edge.id = node.id * (node.id + 1) / 2 - 1; } void nextIn(Edge& e) const { int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; int target = e.id - (source) * (source - 1) / 2; ++target; ++source; e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1; } }; /// \todo UndirFullGraph from the UndirFullGraphBase /// @} } //namespace lemon #endif //LEMON_FULL_GRAPH_H