# Changeset 2115:4cd528a30ec1 in lemon-0.x

Ignore:
Timestamp:
06/30/06 14:14:36 (17 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2821
Message:

Splitted graph files

Files:
15 edited
2 copied

Unmodified
Removed
• ## demo/coloring.cc

 r2038 #include #include #include #include #include
• ## demo/strongly_connected_orientation.cc

 r2084 #include #include #include #include #include
• ## demo/topology_demo.cc

 r1956 #include #include #include #include
• ## doc/graphs.dox

 r2111 provide a node list - edge list interface, i.e. they have functionalities to list the nodes and the edges of the graph as well as  incoming and outgoing edges of a given node. as  incoming and outgoing edges of a given node. This functionalities are defined in the \ref lemon::concept::Graph "Graph" concept. Each graph should meet the \ref lemon::concept::Graph "Graph" concept. This concept does not make it possible to change the graph (i.e. it is not possible to add or delete edges or nodes). Most of the graph algorithms will run on these graphs. The next important graph type concept is the undirected graph concept what is defined in the \ref lemon::concept::UGraph "UGraph" concept class. Each undirected graphs provide node - undirected edge list interfaces. In addition the undirected graphs can be used as directed graphs so they are also conform to the \ref lemon::concept::Graph "Graph" concept. Usually the graphs can be sorted to two group, the first is the general topology graph types which can store any graph and the second are the special topology graphs like the \ref FullUGraph or the \ref GridUGraph. In case of graphs meeting the full feature \ref lemon::concept::ErasableGraph "ErasableGraph" concept you can also erase individual edges and nodes in arbitrary order. The implemented graph structures are the following. \li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets the \ref lemon::concept::ErasableGraph "ErasableGraph" concept
• ## lemon/Makefile.am

 r2108 lemon/floyd_warshall.h \ lemon/fredman_tarjan.h \ lemon/full_bpugraph.h \ lemon/full_graph.h \ lemon/full_ugraph.h \ lemon/graph_adaptor.h \ lemon/graph_reader.h \ lemon/lemon_reader.h \ lemon/lemon_writer.h \ lemon/list_bpugraph.h \ lemon/list_graph.h \ lemon/list_ugraph.h \ lemon/lp.h \ lemon/lp_base.h \ lemon/refptr.h \ lemon/simann.h \ lemon/smart_bpugraph.h \ lemon/smart_graph.h \ lemon/smart_ugraph.h \ lemon/sub_graph.h \ lemon/suurballe.h \ lemon/bits/array_map.h \ lemon/bits/base_extender.h \ lemon/bits/bpugraph_extender.h \ lemon/bits/default_map.h \ lemon/bits/edge_set_extender.h \ lemon/bits/mingw32_time.h \ lemon/bits/traits.h \ lemon/bits/ugraph_extender.h \ lemon/bits/utility.h \ lemon/bits/vector_map.h

• ## lemon/edge_set.h

 r2111 #include #include #include /// \ingroup graphs
• ## lemon/full_graph.h

 r2111 #include #include #include ///\ingroup graphs ///\file ///\brief FullGraph and FullUGraph classes. ///\brief FullGraph class. }; /// \brief Base of the FullUGrpah. /// /// Base of the FullUGrpah. class FullUGraphBase { int _nodeNum; int _edgeNum; public: typedef FullUGraphBase Graph; class Node; class Edge; public: FullUGraphBase() {} ///Creates a full graph with \c n nodes. void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e nodeNum()-1 and the index of /// the node can accessed by the \e index() member. Node operator()(int index) const { return Node(index); } /// \brief Returns the index of the node. /// /// Returns the index of the node. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e nodeNum()-1 and the index of /// the node can accessed by the \e index() member. int index(const Node& node) const { return node.id; } 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 maxNodeId() const { return _nodeNum-1; } /// Maximum edge ID. /// Maximum edge ID. ///\sa id(Edge) int maxEdgeId() const { return _edgeNum-1; } /// \brief Returns the node from its \c id. /// /// Returns the node from its \c id. If there is not node /// with the given id the effect of the function is undefinied. static Node nodeFromId(int id) { return Node(id);} /// \brief Returns the edge from its \c id. /// /// Returns the edge from its \c id. If there is not edge /// with the given id the effect of the function is undefinied. static Edge edgeFromId(int id) { return Edge(id);} Node source(Edge e) const { /// \todo we may do it faster return Node(((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 Node(e.id - (source) * (source - 1) / 2); } /// \brief 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; } /// \brief 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; } /// \brief 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) const { if (prev.id != -1 || u.id <= v.id) return Edge(-1); return Edge(u.id * (u.id - 1) / 2 + v.id); } typedef True FindEdgeTag; class Node { friend class FullUGraphBase; 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 FullUGraphBase; protected: int id;  // _nodeNum * target + source; 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;} }; 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 { int src = node.id; int trg = 0; edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); } /// \todo with specialized iterators we can make faster iterating void nextOut(Edge& edge) const { int src = source(edge).id; int trg = target(edge).id; ++trg; edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1); } void firstIn(Edge& edge, const Node& node) const { int src = node.id + 1; int trg = node.id; edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); } void nextIn(Edge& edge) const { int src = source(edge).id; int trg = target(edge).id; ++src; edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1); } }; typedef UGraphExtender > ExtendedFullUGraphBase; /// \ingroup graphs /// /// \brief An undirected full graph class. /// /// This is a simple and fast undirected full graph implementation. /// It is completely static, so you can neither add nor delete either /// edges or nodes. /// /// The main difference beetween the \e FullGraph and \e FullUGraph class /// is that this class conforms to the undirected graph concept and /// it does not contain the loop edges. /// /// \sa FullUGraphBase /// \sa FullGraph /// /// \author Balazs Dezso class FullUGraph : public ExtendedFullUGraphBase { public: typedef ExtendedFullUGraphBase Parent; /// \brief Constructor FullUGraph() { construct(0); } /// \brief Constructor FullUGraph(int n) { construct(n); } /// \brief Resize the graph /// /// Resize the graph. The function will fully destroy and build the graph. /// This cause that the maps of the graph will reallocated /// automatically and the previous values will be lost. void resize(int n) { Parent::getNotifier(Edge()).clear(); Parent::getNotifier(UEdge()).clear(); Parent::getNotifier(Node()).clear(); construct(n); Parent::getNotifier(Node()).build(); Parent::getNotifier(UEdge()).build(); Parent::getNotifier(Edge()).build(); } }; class FullBpUGraphBase { protected: int _aNodeNum; int _bNodeNum; int _edgeNum; public: class NodeSetError : public LogicError { virtual const char* exceptionName() const { return "lemon::FullBpUGraph::NodeSetError"; } }; class Node { friend class FullBpUGraphBase; protected: int id; Node(int _id) : id(_id) {} public: Node() {} Node(Invalid) { id = -1; } bool operator==(const Node i) const {return id==i.id;} bool operator!=(const Node i) const {return id!=i.id;} bool operator<(const Node i) const {return id 0) { node.id = 2 * _aNodeNum - 2; } else { node.id = 2 * _bNodeNum - 1; } } void next(Node& node) const { node.id -= 2; if (node.id == -2) { node.id = 2 * _bNodeNum - 1; } } void first(UEdge& edge) const { edge.id = _edgeNum - 1; } void next(UEdge& edge) const { --edge.id; } void firstFromANode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); edge.id = (node.id >> 1) * _bNodeNum; } void nextFromANode(UEdge& edge) const { ++(edge.id); if (edge.id % _bNodeNum == 0) edge.id = -1; } void firstFromBNode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); edge.id = (node.id >> 1); } void nextFromBNode(UEdge& edge) const { edge.id += _bNodeNum; if (edge.id >= _edgeNum) edge.id = -1; } static int id(const Node& node) { return node.id; } static Node nodeFromId(int id) { return Node(id); } int maxNodeId() const { return _aNodeNum > _bNodeNum ? _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1; } static int id(const UEdge& edge) { return edge.id; } static UEdge uEdgeFromId(int id) { return UEdge(id); } int maxUEdgeId() const { return _edgeNum - 1; } static int aNodeId(const Node& node) { return node.id >> 1; } static Node fromANodeId(int id) { return Node(id << 1); } int maxANodeId() const { return _aNodeNum; } static int bNodeId(const Node& node) { return node.id >> 1; } static Node fromBNodeId(int id) { return Node((id << 1) + 1); } int maxBNodeId() const { return _bNodeNum; } Node aNode(const UEdge& edge) const { return Node((edge.id / _bNodeNum) << 1); } Node bNode(const UEdge& edge) const { return Node(((edge.id % _bNodeNum) << 1) + 1); } static bool aNode(const Node& node) { return (node.id & 1) == 0; } static bool bNode(const Node& node) { return (node.id & 1) == 1; } static Node aNode(int index) { return Node(index << 1); } static Node bNode(int index) { return Node((index << 1) + 1); } typedef True NodeNumTag; int nodeNum() const { return _aNodeNum + _bNodeNum; } int aNodeNum() const { return _aNodeNum; } int bNodeNum() const { return _bNodeNum; } typedef True EdgeNumTag; int uEdgeNum() const { return _edgeNum; } }; typedef BpUGraphExtender ExtendedFullBpUGraphBase; /// \ingroup graphs /// /// \brief An undirected full bipartite graph class. /// /// This is a simple and fast bipartite undirected full graph implementation. /// It is completely static, so you can neither add nor delete either /// edges or nodes. /// /// \sa FullUGraphBase /// \sa FullGraph /// /// \author Balazs Dezso class FullBpUGraph : public ExtendedFullBpUGraphBase { public: typedef ExtendedFullBpUGraphBase Parent; FullBpUGraph() { Parent::construct(0, 0); } FullBpUGraph(int aNodeNum, int bNodeNum) { Parent::construct(aNodeNum, bNodeNum); } /// \brief Resize the graph /// void resize(int n, int m) { Parent::getNotifier(Edge()).clear(); Parent::getNotifier(UEdge()).clear(); Parent::getNotifier(Node()).clear(); Parent::getNotifier(ANode()).clear(); Parent::getNotifier(BNode()).clear(); construct(n, m); Parent::getNotifier(ANode()).build(); Parent::getNotifier(BNode()).build(); Parent::getNotifier(Node()).build(); Parent::getNotifier(UEdge()).build(); Parent::getNotifier(Edge()).build(); } }; } //namespace lemon
• ## lemon/grid_ugraph.h

 r2076 #include #include #include #include

• ## lemon/min_cut.h

 r2111 #include #include #include #include template #else template , typename _Traits =
• ## lemon/smart_graph.h

 r2111 ///\ingroup graphs ///\file ///\brief SmartGraph and SmartUGraph classes. ///\brief SmartGraph class. #include #include #include #include #include #include #include /**************** Undirected List Graph ****************/ typedef UGraphExtender > ExtendedSmartUGraphBase; /// \ingroup graphs /// /// \brief A smart undirected graph class. /// /// This is a simple and fast undirected graph implementation. /// It is also quite memory efficient, but at the price /// that it does support only limited (only stack-like) /// node and edge deletions. /// Except from this it conforms to /// the \ref concept::UGraph "UGraph" concept. /// \sa concept::UGraph. /// /// \todo Snapshot hasn't been implemented yet. /// class SmartUGraph : public ExtendedSmartUGraphBase { }; class SmartBpUGraphBase { public: class NodeSetError : public LogicError { virtual const char* exceptionName() const { return "lemon::SmartBpUGraph::NodeSetError"; } }; protected: struct NodeT { int first; NodeT() {} NodeT(int _first) : first(_first) {} }; struct UEdgeT { int aNode, next_out; int bNode, next_in; }; std::vector aNodes; std::vector bNodes; std::vector edges; public: class Node { friend class SmartBpUGraphBase; protected: int id; Node(int _id) : id(_id) {} public: Node() {} Node(Invalid) { id = -1; } bool operator==(const Node i) const {return id==i.id;} bool operator!=(const Node i) const {return id!=i.id;} bool operator<(const Node i) const {return id 0) { node.id = 2 * aNodes.size() - 2; } else { node.id = 2 * bNodes.size() - 1; } } void next(Node& node) const { node.id -= 2; if (node.id == -2) { node.id = 2 * bNodes.size() - 1; } } void first(UEdge& edge) const { edge.id = edges.size() - 1; } void next(UEdge& edge) const { --edge.id; } void firstFromANode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); edge.id = aNodes[node.id >> 1].first; } void nextFromANode(UEdge& edge) const { edge.id = edges[edge.id].next_out; } void firstFromBNode(UEdge& edge, const Node& node) const { LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); edge.id = bNodes[node.id >> 1].first; } void nextFromBNode(UEdge& edge) const { edge.id = edges[edge.id].next_in; } static int id(const Node& node) { return node.id; } static Node nodeFromId(int id) { return Node(id); } int maxNodeId() const { return aNodes.size() > bNodes.size() ? aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; } static int id(const UEdge& edge) { return edge.id; } static UEdge uEdgeFromId(int id) { return UEdge(id); } int maxUEdgeId() const { return edges.size(); } static int aNodeId(const Node& node) { return node.id >> 1; } static Node fromANodeId(int id) { return Node(id << 1); } int maxANodeId() const { return aNodes.size(); } static int bNodeId(const Node& node) { return node.id >> 1; } static Node fromBNodeId(int id) { return Node((id << 1) + 1); } int maxBNodeId() const { return bNodes.size(); } Node aNode(const UEdge& edge) const { return Node(edges[edge.id].aNode); } Node bNode(const UEdge& edge) const { return Node(edges[edge.id].bNode); } static bool aNode(const Node& node) { return (node.id & 1) == 0; } static bool bNode(const Node& node) { return (node.id & 1) == 1; } Node addANode() { NodeT nodeT; nodeT.first = -1; aNodes.push_back(nodeT); return Node(aNodes.size() * 2 - 2); } Node addBNode() { NodeT nodeT; nodeT.first = -1; bNodes.push_back(nodeT); return Node(bNodes.size() * 2 - 1); } UEdge addEdge(const Node& source, const Node& target) { LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); UEdgeT edgeT; if ((source.id & 1) == 0) { edgeT.aNode = source.id; edgeT.bNode = target.id; } else { edgeT.aNode = target.id; edgeT.bNode = source.id; } edgeT.next_out = aNodes[edgeT.aNode >> 1].first; aNodes[edgeT.aNode >> 1].first = edges.size(); edgeT.next_in = bNodes[edgeT.bNode >> 1].first; bNodes[edgeT.bNode >> 1].first = edges.size(); edges.push_back(edgeT); return UEdge(edges.size() - 1); } void clear() { aNodes.clear(); bNodes.clear(); edges.clear(); } typedef True NodeNumTag; int nodeNum() const { return aNodes.size() + bNodes.size(); } int aNodeNum() const { return aNodes.size(); } int bNodeNum() const { return bNodes.size(); } typedef True EdgeNumTag; int uEdgeNum() const { return edges.size(); } }; typedef BpUGraphExtender ExtendedSmartBpUGraphBase; /// \ingroup graphs /// /// \brief A smart bipartite undirected graph class. /// /// This is a simple and fast bipartite undirected graph implementation. /// It is also quite memory efficient, but at the price /// that it does not support node and edge deletions. /// Except from this it conforms to /// the \ref concept::BpUGraph "BpUGraph" concept. /// \sa concept::BpUGraph. /// class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; /// @} } //namespace lemon
• ## test/bipartite_matching_test.cc

 r2058 #include #include #include #include
• ## test/max_matching_test.cc

 r1993 #include "test_tools.h" #include #include #include
• ## test/ugraph_test.cc

 r2111 #include #include #include #include #include #include #include #include #include
Note: See TracChangeset for help on using the changeset viewer.