deba@2293: /* -*- C++ -*- deba@2293: * deba@2293: * This file is a part of LEMON, a generic C++ optimization library deba@2293: * alpar@2553: * Copyright (C) 2003-2008 deba@2293: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2293: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2293: * deba@2293: * Permission to use, modify and distribute this software is granted deba@2293: * provided that this copyright notice appears in all copies. For deba@2293: * precise terms see the accompanying LICENSE file. deba@2293: * deba@2293: * This software is provided "AS IS" with no warranty of any kind, deba@2293: * express or implied, and with no claim as to its suitability for any deba@2293: * purpose. deba@2293: * deba@2293: */ deba@2293: deba@2293: #ifndef LEMON_STATIC_GRAPH_H deba@2293: #define LEMON_STATIC_GRAPH_H deba@2293: deba@2293: #include deba@2293: #include deba@2293: deba@2293: namespace lemon { deba@2293: deba@2293: class StaticGraphBase { deba@2293: public: deba@2293: deba@2293: StaticGraphBase() deba@2293: : node_num(-1), edge_num(0), deba@2293: node_first_out(0), node_first_in(0), deba@2293: edge_source(0), edge_target(0), deba@2293: edge_next_in(0), edge_next_out(0) {} deba@2293: deba@2293: ~StaticGraphBase() { deba@2293: if (node_num != -1) { deba@2293: delete[] node_first_out; deba@2293: delete[] node_first_in; deba@2293: delete[] edge_source; deba@2293: delete[] edge_target; deba@2293: delete[] edge_next_out; deba@2293: delete[] edge_next_in; deba@2293: } deba@2293: } deba@2293: deba@2293: class Node { deba@2293: friend class StaticGraphBase; deba@2293: protected: deba@2293: int id; deba@2293: Node(int _id) : id(_id) {} deba@2293: public: deba@2293: Node() {} deba@2293: Node (Invalid) : id(-1) {} deba@2293: bool operator==(const Node& node) const {return id == node.id;} deba@2293: bool operator!=(const Node& node) const {return id != node.id;} deba@2293: bool operator<(const Node& node) const {return id < node.id;} deba@2293: }; deba@2293: deba@2293: class Edge { deba@2293: friend class StaticGraphBase; deba@2293: protected: deba@2293: int id; deba@2293: Edge(int _id) : id(_id) {} deba@2293: public: deba@2293: Edge() { } deba@2293: Edge (Invalid) { id = -1; } deba@2293: bool operator==(const Edge& edge) const {return id == edge.id;} deba@2293: bool operator!=(const Edge& edge) const {return id != edge.id;} deba@2293: bool operator<(const Edge& edge) const {return id < edge.id;} deba@2293: }; deba@2293: deba@2293: Node source(const Edge& e) const { return Node(edge_source[e.id]); } deba@2293: Node target(const Edge& e) const { return Node(edge_target[e.id]); } deba@2293: deba@2293: void first(Node& n) const { n.id = node_num - 1; } deba@2293: void next(Node& n) const { --n.id; } deba@2293: deba@2293: void first(Edge& n) const { n.id = edge_num - 1; } deba@2293: void next(Edge& n) const { --n.id; } deba@2293: deba@2293: void firstOut(Edge& e, const Node& n) const { deba@2293: e.id = node_first_out[n.id] != node_first_out[n.id + 1] ? deba@2293: node_first_out[n.id] : -1; deba@2293: } deba@2293: void nextOut(Edge& e) const { e.id = edge_next_out[e.id]; } deba@2293: deba@2293: void firstIn(Edge& e, const Node& n) const { e.id = node_first_in[n.id]; } deba@2293: void nextIn(Edge& e) const { e.id = edge_next_in[e.id]; } deba@2293: deba@2293: deba@2293: int id(const Node& n) const { return n.id; } deba@2293: Node nodeFromId(int id) const { return Node(id); } deba@2293: int maxNodeId() const { return node_num - 1; } deba@2293: deba@2293: int id(const Edge& e) const { return e.id; } deba@2293: Edge edgeFromId(int id) const { return Edge(id); } deba@2293: int maxEdgeId() const { return edge_num - 1; } deba@2293: deba@2293: typedef True NodeNumTag; deba@2293: int nodeNum() const { return node_num; } deba@2293: typedef True EdgeNumTag; deba@2293: int edgeNum() const { return edge_num; } deba@2293: deba@2293: private: deba@2293: deba@2293: template deba@2293: class EdgeLess { deba@2293: public: deba@2293: typedef typename Graph::Edge Edge; deba@2293: deba@2293: EdgeLess(const Graph &_graph, const NodeRefMap& _nodeRef) deba@2293: : graph(_graph), nodeRef(_nodeRef) {} deba@2293: deba@2293: bool operator()(const Edge& left, const Edge& right) const { deba@2293: return nodeRef[graph.target(left)] < nodeRef[graph.target(right)]; deba@2293: } deba@2293: private: deba@2293: const Graph& graph; deba@2293: const NodeRefMap& nodeRef; deba@2293: }; deba@2293: deba@2293: public: deba@2293: deba@2329: typedef True BuildTag; deba@2293: deba@2293: template deba@2329: void build(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) { deba@2293: deba@2293: if (node_num != -1) { deba@2293: delete[] node_first_out; deba@2293: delete[] node_first_in; deba@2293: delete[] edge_source; deba@2293: delete[] edge_target; deba@2293: delete[] edge_next_out; deba@2293: delete[] edge_next_in; deba@2293: } deba@2293: deba@2293: typedef typename Graph::Node GNode; deba@2293: typedef typename Graph::Edge GEdge; deba@2293: deba@2293: node_num = countNodes(graph); deba@2293: edge_num = countEdges(graph); deba@2293: deba@2293: node_first_out = new int[node_num + 1]; deba@2293: node_first_in = new int[node_num]; deba@2293: deba@2293: edge_source = new int[edge_num]; deba@2293: edge_target = new int[edge_num]; deba@2293: edge_next_out = new int[edge_num]; deba@2293: edge_next_in = new int[edge_num]; deba@2293: deba@2293: int node_index = 0; deba@2293: for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { deba@2293: nodeRef[n] = Node(node_index); deba@2293: node_first_in[node_index] = -1; deba@2293: ++node_index; deba@2293: } deba@2293: deba@2293: EdgeLess edgeLess(graph, nodeRef); deba@2293: deba@2293: int edge_index = 0; deba@2293: for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { deba@2293: int source = nodeRef[n].id; deba@2293: std::vector edges; deba@2293: for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { deba@2293: edges.push_back(e); deba@2293: } deba@2293: if (!edges.empty()) { deba@2293: node_first_out[source] = edge_index; deba@2293: std::sort(edges.begin(), edges.end(), edgeLess); deba@2293: for (typename std::vector::iterator it = edges.begin(); deba@2293: it != edges.end(); ++it) { deba@2293: int target = nodeRef[graph.target(*it)].id; deba@2293: edgeRef[*it] = Edge(edge_index); deba@2293: edge_source[edge_index] = source; deba@2293: edge_target[edge_index] = target; deba@2293: edge_next_in[edge_index] = node_first_in[target]; deba@2293: node_first_in[target] = edge_index; deba@2293: edge_next_out[edge_index] = edge_index + 1; deba@2293: ++edge_index; deba@2293: } deba@2293: edge_next_out[edge_index - 1] = -1; deba@2293: } else { deba@2293: node_first_out[source] = edge_index; deba@2293: } deba@2293: } deba@2293: node_first_out[node_num] = edge_num; deba@2293: } deba@2293: deba@2293: protected: deba@2293: deba@2293: void fastFirstOut(Edge& e, const Node& n) const { deba@2293: e.id = node_first_out[n.id]; deba@2293: } deba@2293: deba@2293: static void fastNextOut(Edge& e) { deba@2293: ++e.id; deba@2293: } deba@2293: void fastLastOut(Edge& e, const Node& n) const { deba@2293: e.id = node_first_out[n.id + 1]; deba@2293: } deba@2293: deba@2293: private: deba@2293: int node_num; deba@2293: int edge_num; deba@2293: int *node_first_out; deba@2293: int *node_first_in; deba@2293: int *edge_source; deba@2293: int *edge_target; deba@2293: int *edge_next_in; deba@2293: int *edge_next_out; deba@2293: }; deba@2293: deba@2293: typedef GraphExtender ExtendedStaticGraphBase; deba@2293: deba@2293: deba@2293: class StaticGraph : public ExtendedStaticGraphBase { deba@2293: public: deba@2293: deba@2293: typedef ExtendedStaticGraphBase Parent; deba@2293: deba@2293: protected: deba@2293: deba@2293: using Parent::fastFirstOut; deba@2293: using Parent::fastNextOut; deba@2293: using Parent::fastLastOut; deba@2293: deba@2293: public: deba@2293: deba@2293: class OutEdgeIt : public Edge { deba@2293: public: deba@2293: deba@2293: OutEdgeIt() { } deba@2293: deba@2293: OutEdgeIt(Invalid i) : Edge(i) { } deba@2293: deba@2293: OutEdgeIt(const StaticGraph& graph, const Node& node) { deba@2293: graph.fastFirstOut(*this, node); deba@2293: graph.fastLastOut(last, node); deba@2293: if (last == *this) *this = INVALID; deba@2293: } deba@2293: deba@2293: OutEdgeIt(const StaticGraph& graph, const Edge& edge) : Edge(edge) { deba@2293: graph.fastLastOut(last, graph.source(edge)); deba@2293: } deba@2293: deba@2293: OutEdgeIt& operator++() { deba@2293: StaticGraph::fastNextOut(*this); deba@2293: if (last == *this) *this = INVALID; deba@2293: return *this; deba@2293: } deba@2293: deba@2293: private: deba@2293: Edge last; deba@2293: }; deba@2293: deba@2293: }; deba@2293: deba@2293: } deba@2293: deba@2293: #endif