# HG changeset patch # User deba # Date 1162571372 0 # Node ID 1ee6e8788cc754b26f8625bf9853f4f8add57c59 # Parent 38d985e822051e590019c5e50414bdfc573c33d3 First implementation of the static graph class It could be improved to get better running times on benchmarks diff -r 38d985e82205 -r 1ee6e8788cc7 lemon/Makefile.am --- a/lemon/Makefile.am Fri Nov 03 15:21:52 2006 +0000 +++ b/lemon/Makefile.am Fri Nov 03 16:29:32 2006 +0000 @@ -90,6 +90,7 @@ lemon/simann.h \ lemon/smart_graph.h \ lemon/ssp_min_cost_flow.h \ + lemon/static_graph.h \ lemon/sub_graph.h \ lemon/suurballe.h \ lemon/tabu_search.h \ diff -r 38d985e82205 -r 1ee6e8788cc7 lemon/static_graph.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/static_graph.h Fri Nov 03 16:29:32 2006 +0000 @@ -0,0 +1,262 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2006 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, 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_STATIC_GRAPH_H +#define LEMON_STATIC_GRAPH_H + +#include +#include + +namespace lemon { + + class StaticGraphBase { + public: + + StaticGraphBase() + : node_num(-1), edge_num(0), + node_first_out(0), node_first_in(0), + edge_source(0), edge_target(0), + edge_next_in(0), edge_next_out(0) {} + + ~StaticGraphBase() { + if (node_num != -1) { + delete[] node_first_out; + delete[] node_first_in; + delete[] edge_source; + delete[] edge_target; + delete[] edge_next_out; + delete[] edge_next_in; + } + } + + class Node { + friend class StaticGraphBase; + 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 StaticGraphBase; + protected: + int id; + Edge(int _id) : id(_id) {} + 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;} + }; + + Node source(const Edge& e) const { return Node(edge_source[e.id]); } + Node target(const Edge& e) const { return Node(edge_target[e.id]); } + + void first(Node& n) const { n.id = node_num - 1; } + void next(Node& n) const { --n.id; } + + void first(Edge& n) const { n.id = edge_num - 1; } + void next(Edge& n) const { --n.id; } + + void firstOut(Edge& e, const Node& n) const { + e.id = node_first_out[n.id] != node_first_out[n.id + 1] ? + node_first_out[n.id] : -1; + } + void nextOut(Edge& e) const { e.id = edge_next_out[e.id]; } + + void firstIn(Edge& e, const Node& n) const { e.id = node_first_in[n.id]; } + void nextIn(Edge& e) const { e.id = edge_next_in[e.id]; } + + + int id(const Node& n) const { return n.id; } + Node nodeFromId(int id) const { return Node(id); } + int maxNodeId() const { return node_num - 1; } + + int id(const Edge& e) const { return e.id; } + Edge edgeFromId(int id) const { return Edge(id); } + int maxEdgeId() const { return edge_num - 1; } + + typedef True NodeNumTag; + int nodeNum() const { return node_num; } + typedef True EdgeNumTag; + int edgeNum() const { return edge_num; } + + private: + + template + class EdgeLess { + public: + typedef typename Graph::Edge Edge; + + EdgeLess(const Graph &_graph, const NodeRefMap& _nodeRef) + : graph(_graph), nodeRef(_nodeRef) {} + + bool operator()(const Edge& left, const Edge& right) const { + return nodeRef[graph.target(left)] < nodeRef[graph.target(right)]; + } + private: + const Graph& graph; + const NodeRefMap& nodeRef; + }; + + public: + + typedef True CloneableTag; + + template + void clone(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) { + + if (node_num != -1) { + delete[] node_first_out; + delete[] node_first_in; + delete[] edge_source; + delete[] edge_target; + delete[] edge_next_out; + delete[] edge_next_in; + } + + typedef typename Graph::Node GNode; + typedef typename Graph::Edge GEdge; + + node_num = countNodes(graph); + edge_num = countEdges(graph); + + node_first_out = new int[node_num + 1]; + node_first_in = new int[node_num]; + + edge_source = new int[edge_num]; + edge_target = new int[edge_num]; + edge_next_out = new int[edge_num]; + edge_next_in = new int[edge_num]; + + int node_index = 0; + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { + nodeRef[n] = Node(node_index); + node_first_in[node_index] = -1; + ++node_index; + } + + EdgeLess edgeLess(graph, nodeRef); + + int edge_index = 0; + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { + int source = nodeRef[n].id; + std::vector edges; + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) { + edges.push_back(e); + } + if (!edges.empty()) { + node_first_out[source] = edge_index; + std::sort(edges.begin(), edges.end(), edgeLess); + for (typename std::vector::iterator it = edges.begin(); + it != edges.end(); ++it) { + int target = nodeRef[graph.target(*it)].id; + edgeRef[*it] = Edge(edge_index); + edge_source[edge_index] = source; + edge_target[edge_index] = target; + edge_next_in[edge_index] = node_first_in[target]; + node_first_in[target] = edge_index; + edge_next_out[edge_index] = edge_index + 1; + ++edge_index; + } + edge_next_out[edge_index - 1] = -1; + } else { + node_first_out[source] = edge_index; + } + } + node_first_out[node_num] = edge_num; + } + + protected: + + void fastFirstOut(Edge& e, const Node& n) const { + e.id = node_first_out[n.id]; + } + + static void fastNextOut(Edge& e) { + ++e.id; + } + void fastLastOut(Edge& e, const Node& n) const { + e.id = node_first_out[n.id + 1]; + } + + private: + int node_num; + int edge_num; + int *node_first_out; + int *node_first_in; + int *edge_source; + int *edge_target; + int *edge_next_in; + int *edge_next_out; + }; + + typedef GraphExtender ExtendedStaticGraphBase; + + + class StaticGraph : public ExtendedStaticGraphBase { + public: + + typedef ExtendedStaticGraphBase Parent; + + protected: + + using Parent::fastFirstOut; + using Parent::fastNextOut; + using Parent::fastLastOut; + + public: + + class OutEdgeIt : public Edge { + public: + + OutEdgeIt() { } + + OutEdgeIt(Invalid i) : Edge(i) { } + + OutEdgeIt(const StaticGraph& graph, const Node& node) { + graph.fastFirstOut(*this, node); + graph.fastLastOut(last, node); + if (last == *this) *this = INVALID; + } + + OutEdgeIt(const StaticGraph& graph, const Edge& edge) : Edge(edge) { + graph.fastLastOut(last, graph.source(edge)); + } + + OutEdgeIt& operator++() { + StaticGraph::fastNextOut(*this); + if (last == *this) *this = INVALID; + return *this; + } + + private: + Edge last; + }; + + }; + +} + +#endif