# Changeset 2223:590c1b663a27 in lemon-0.x

Ignore:
Timestamp:
09/29/06 13:25:27 (13 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2963
Message:

Exporting interface to the Graph class
Some documentation improvements

Files:
3 edited

Unmodified
Removed
• ## lemon/full_graph.h

 r2162 namespace lemon { /// \brief Base of the FullGrpah. /// /// Base of the FullGrpah. class FullGraphBase { int _nodeNum; class Edge; protected: FullGraphBase() {} void construct(int n) { _nodeNum = n; _edgeNum = n * n; } public: FullGraphBase() {} ///Creates a full graph with \c n nodes. void construct(int n) { _nodeNum = n; _edgeNum = n * n; } typedef True NodeNumTag; typedef True EdgeNumTag; /// \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; } ///Number of nodes. Edge edge(const Node& u, const Node& v) const { return Edge(*this, u.id, v.id); } 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; } /// 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; } typedef True FindEdgeTag; /// 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 { return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; /// \sa concept::Graph. /// /// \sa FullGraphBase /// \sa FullUGraph /// Parent::getNotifier(Edge()).build(); } /// \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 Parent::operator()(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 Parent::index(node); } /// \brief Returns the edge connects the given nodes. /// /// Returns the edge connects the given nodes. Edge edge(const Node& u, const Node& v) const { return Parent::edge(u, v); } /// \brief Number of nodes. int nodeNum() const { return Parent::nodeNum(); } /// \brief Number of edges. int edgeNum() const { return Parent::edgeNum(); } }; /// \brief Base of the FullUGrpah. /// /// Base of the FullUGrpah. class FullUGraphBase { int _nodeNum; class Edge; protected: FullUGraphBase() {} void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; } 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; } Edge edge(const Node& u, const Node& v) const { return Edge(u.id * (u.id - 1) / 2 + v.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);} } /// \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); /// it does not contain the loop edges. /// /// \sa FullUGraphBase /// \sa FullGraph /// Parent::getNotifier(Edge()).build(); } /// \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 Parent::operator()(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 Parent::index(node); } /// \brief Number of nodes. int nodeNum() const { return Parent::nodeNum(); } /// \brief Number of edges. int edgeNum() const { return Parent::edgeNum(); } /// \brief Number of undirected edges. int uEdgeNum() const { return Parent::uEdgeNum(); } /// \brief Returns the edge connects the given nodes. /// /// Returns the edge connects the given nodes. Edge edge(const Node& u, const Node& v) const { if (Parent::index(u) > Parent::index(v)) { return Parent::direct(Parent::edge(u, v), true); } else if (Parent::index(u) == Parent::index(v)) { return INVALID; } else { return Parent::direct(Parent::edge(v, u), false); } } /// \brief Returns the undirected edge connects the given nodes. /// /// Returns the undirected edge connects the given nodes. UEdge uEdge(const Node& u, const Node& v) const { if (Parent::index(u) > Parent::index(v)) { return Parent::edge(u, v); } else if (Parent::index(u) == Parent::index(v)) { return INVALID; } else { return Parent::edge(v, u); } } }; int _edgeNum; protected: FullBpUGraphBase() {} void construct(int aNodeNum, int bNodeNum) { _aNodeNum = aNodeNum; _bNodeNum = bNodeNum; _edgeNum = aNodeNum * bNodeNum; } public: }; void construct(int aNodeNum, int bNodeNum) { _aNodeNum = aNodeNum; _bNodeNum = bNodeNum; _edgeNum = aNodeNum * bNodeNum; Node aNode(int index) const { return Node(index << 1); } Node bNode(int index) const { return Node((index << 1) + 1); } int aNodeIndex(const Node& node) const { return node.id >> 1; } int bNodeIndex(const Node& node) const { return node.id >> 1; } UEdge uEdge(const Node& u, const Node& v) const { if (((u.id ^ v.id) & 1) != 1) { return UEdge(-1); } else if ((u.id & 1) == 0) { return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1)); } else { return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1)); } } } static Node aNode(int index) { return Node(index << 1); } static Node bNode(int index) { return Node((index << 1) + 1); } typedef True NodeNumTag; int uEdgeNum() const { return _edgeNum; } typedef True FindEdgeTag; UEdge findUEdge(Node u, Node v, UEdge prev = INVALID) const { if (prev.id != -1 || ((u.id ^ v.id) & 1) != 1) { return UEdge(-1); } else if ((u.id & 1) == 0) { return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1)); } else { return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1)); } } }; /// It is completely static, so you can neither add nor delete either /// edges or nodes. /// /// \sa FullUGraphBase /// \sa FullGraph /// /// \author Balazs Dezso /// \brief Resize the graph /// /// Resize the graph void resize(int n, int m) { Parent::getNotifier(Edge()).clear(); Parent::getNotifier(Edge()).build(); } /// \brief Number of nodes. int nodeNum() const { return Parent::nodeNum(); } /// \brief Number of A-nodes. int aNodeNum() const { return Parent::aNodeNum(); } /// \brief Number of B-nodes. int bNodeNum() const { return Parent::bNodeNum(); } /// \brief Number of edges. int edgeNum() const { return Parent::edgeNum(); } /// \brief Number of undirected edges. int uEdgeNum() const { return Parent::uEdgeNum(); } using Parent::aNode; using Parent::bNode; /// \brief Returns the A-node with the given index. /// /// Returns the A-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 aNodeNum()-1 and the index of /// the node can accessed by the \e aNodeIndex() member. Node aNode(int index) const { return Parent::aNode(index); } /// \brief Returns the B-node with the given index. /// /// Returns the B-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 bNodeNum()-1 and the index of /// the node can accessed by the \e bNodeIndex() member. Node bNode(int index) const { return Parent::bNode(index); } /// \brief Returns the index of the A-node. /// /// Returns the index of the A-node. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e aNodeNum()-1 and the index of /// the node can accessed by the \e aNodeIndex() member. int aNodeIndex(const Node& node) const { return Parent::aNodeIndex(node); } /// \brief Returns the index of the B-node. /// /// Returns the index of the B-node. Because it is a /// static size graph the node's of the graph can be indiced /// by the range from 0 to \e bNodeNum()-1 and the index of /// the node can accessed by the \e bNodeIndex() member. int bNodeIndex(const Node& node) const { return Parent::bNodeIndex(node); } /// \brief Returns the edge connects the given nodes. /// /// Returns the edge connects the given nodes. Edge edge(const Node& u, const Node& v) const { UEdge uedge = Parent::uEdge(u, v); if (uedge != INVALID) { return Parent::direct(uedge, Parent::aNode(u)); } else { return INVALID; } } /// \brief Returns the undirected edge connects the given nodes. /// /// Returns the undirected edge connects the given nodes. UEdge uEdge(const Node& u, const Node& v) const { return Parent::uEdge(u, v); } };
• ## lemon/grid_ugraph.h

 r2207 namespace lemon { /// \brief Base graph for GridUGraph. /// /// Base graph for grid graph. It describes some member functions /// which can be used in the GridUGraph. /// /// \warning Always use the GridUGraph instead of this. /// \see GridUGraph class GridUGraphBase { protected: /// \brief Creates a grid graph with the given size. /// /// Creates a grid graph with the given size. void construct(int width, int height) { _height = height; _width = width; } /// \brief Gives back the edge goes down from the node. /// /// Gives back the edge goes down from the node. If there is not /// outgoing edge then it gives back INVALID. Edge _down(Node n) const { if (n.id < _nodeNum - _width) { } /// \brief Gives back the edge comes from up into the node. /// /// Gives back the edge comes from up into the node. If there is not /// incoming edge then it gives back INVALID. Edge _up(Node n) const { if (n.id >= _width) { } /// \brief Gives back the edge goes right from the node. /// /// Gives back the edge goes right from the node. If there is not /// outgoing edge then it gives back INVALID. Edge _right(Node n) const { if (n.id % _width < _width - 1) { } /// \brief Gives back the edge comes from left into the node. /// /// Gives back the edge comes left up into the node. If there is not /// incoming edge then it gives back INVALID. Edge _left(Node n) const { if (n.id % _width > 0) { /// \brief The node on the given position. /// /// Gives back the node on the given position. Node operator()(int i, int j) const { LEMON_ASSERT(0 <= i && i < width() && 0 <= j  && } /// \brief Gives back the row index of the node. /// /// Gives back the row index of the node. int row(Node n) const { return n.id / _width; } /// \brief Gives back the coloumn index of the node. /// /// Gives back the coloumn index of the node. int col(Node n) const { return n.id % _width; } /// \brief Gives back the width of the graph. /// /// Gives back the width of the graph. int width() const { return _width; } /// \brief Gives back the height of the graph. /// /// Gives back the height of the graph. int height() const { return _height; 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 Gives back the source node of an edge. /// /// Gives back the source node of an edge. Node source(Edge e) const { if (e.id < _edgeLimit) { } /// \brief Gives back the target node of an edge. /// /// Gives back the target node of an edge. Node target(Edge e) const { if (e.id < _edgeLimit) { } /// 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; } typedef True FindEdgeTag; /// 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 != INVALID) return INVALID; /// Two nodes are connected in the graph if the indices differ only /// on one position and only one is the difference. /// /// \image html grid_ugraph.png /// \image latex grid_ugraph.eps "Grid graph" width=\textwidth /// /// The graph can be indiced in the following way: /// /// \author Balazs Dezso /// \see GridUGraphBase class GridUGraph : public ExtendedGridUGraphBase { public: } /// \brief The node on the given position. /// /// Gives back the node on the given position. Node operator()(int i, int j) const { return Parent::operator()(i, j); } /// \brief Gives back the row index of the node. /// /// Gives back the row index of the node. int row(Node n) const { return Parent::row(n); } /// \brief Gives back the coloumn index of the node. /// /// Gives back the coloumn index of the node. int col(Node n) const { return Parent::col(n); } /// \brief Gives back the width of the graph. /// /// Gives back the width of the graph. int width() const { return Parent::width(); } /// \brief Gives back the height of the graph. /// /// Gives back the height of the graph. int height() const { return Parent::height(); } /// \brief Gives back the edge goes down from the node. ///
• ## lemon/hypercube_graph.h

 r2207 namespace lemon { /// \brief Base graph for HyperCubeGraph. /// /// Base graph for hyper-cube graph. It describes some member functions /// which can be used in the HyperCubeGraph. /// /// \warning Always use the HyperCubeGraph instead of this. /// \see HyperCubeGraph class HyperCubeGraphBase { protected: /// \brief Creates a hypercube graph with the given size. /// /// Creates a hypercube graph with the given size. void construct(int dim) { _dim = dim; typedef True EdgeNumTag; ///Number of nodes. int nodeNum() const { return _nodeNum; } ///Number of edges. int edgeNum() const { return _nodeNum * _dim; } /// 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 Gives back the source node of an edge. /// /// Gives back the source node of an edge. Node source(Edge e) const { return e.id / _dim; } /// \brief Gives back the target node of an edge. /// /// Gives back the target node of an edge. Node target(Edge e) const { return (e.id / _dim) ^ ( 1 << (e.id % _dim)); } /// 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; } } /// \brief Gives back the number of the dimensions. /// /// Gives back the number of the dimensions. int dimension() const { return _dim; } /// \brief Returns true if the n'th bit of the node is one. /// /// Returns true if the n'th bit of the node is one. bool projection(Node node, int n) const { return (bool)(node.id & (1 << n)); } /// \brief The dimension id of the edge. /// /// It returns the dimension id of the edge. It can /// be in the ${0, 1, dim-1}$ intervall. int dimension(Edge edge) const { return edge.id % _dim; } /// \brief Gives back the index of the node. /// /// Gives back the index of the node. The lower bits of the /// integer describe the node. int index(Node node) const { return node.id; } /// \brief Gives back the node by its index. /// ///  Gives back the node by its index. Node operator()(int index) const { return Node(index); /// concept but it does not conform to the \ref concept::UGraph. /// /// \see HyperCubeGraphBase /// \author Balazs Dezso class HyperCubeGraph : public ExtendedHyperCubeGraphBase { public: typedef ExtendedHyperCubeGraphBase Parent; /// \brief Construct a graph with \c dim dimension. /// /// Construct a graph with \c dim dimension. HyperCubeGraph(int dim) { construct(dim); } /// \brief Gives back the number of the dimensions. /// /// Gives back the number of the dimensions. int dimension() const { return Parent::dimension(); } /// \brief Returns true if the n'th bit of the node is one. /// /// Returns true if the n'th bit of the node is one. bool projection(Node node, int n) const { return Parent::projection(node, n); } /// \brief The dimension id of the edge. /// /// It returns the dimension id of the edge. It can /// be in the \f$\{0, 1, \dots, dim-1\} \f$ intervall. int dimension(Edge edge) const { return Parent::dimension(edge); } /// \brief Gives back the index of the node. /// /// Gives back the index of the node. The lower bits of the /// integer describes the node. int index(Node node) const { return Parent::index(node); } /// \brief Gives back the node by its index. /// /// Gives back the node by its index. Node operator()(int index) const { return Parent::operator()(index); } /// \brief Number of nodes. int nodeNum() const { return Parent::nodeNum(); } /// \brief Number of edges. int edgeNum() const { return Parent::edgeNum(); } /// \brief Linear combination map.
Note: See TracChangeset for help on using the changeset viewer.