# HG changeset patch # User deba # Date 1159529127 0 # Node ID 590c1b663a2777fb0ab6e8165c8e61fe87a71634 # Parent a24939ee343c2048fb3cb0b35f5ce5f8f3f8118b Exporting interface to the Graph class Some documentation improvements diff -r a24939ee343c -r 590c1b663a27 doc/images/grid_ugraph.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/images/grid_ugraph.eps Fri Sep 29 11:25:27 2006 +0000 @@ -0,0 +1,303 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: Grid undirected graph +%%Copyright: (C) 2006 LEMON Project +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Sep 29 11:55:56 2006 +%%BoundingBox: 0 0 596 842 +%%DocumentPaperSizes: a4 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth + newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub + lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto + 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke + 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nmale { + 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth + newpath 5 index 5 index moveto + 5 index 4 index 1 mul 1.5 mul add + 5 index 5 index 3 sqrt 1.5 mul mul add + 1 index 1 index lineto + 1 index 1 index 7 index sub moveto + 1 index 1 index lineto + exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto + stroke + 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +15 60.1011 translate +7.8206 dup scale +1.14018 1.14018 translate +%Edges: +gsave +70 80 70 90 0 0 0 0.342053 l +70 70 70 80 0 0 0 0.342053 l +70 60 70 70 0 0 0 0.342053 l +70 50 70 60 0 0 0 0.342053 l +70 40 70 50 0 0 0 0.342053 l +70 30 70 40 0 0 0 0.342053 l +70 20 70 30 0 0 0 0.342053 l +70 10 70 20 0 0 0 0.342053 l +70 0 70 10 0 0 0 0.342053 l +60 80 60 90 0 0 0 0.342053 l +60 70 60 80 0 0 0 0.342053 l +60 60 60 70 0 0 0 0.342053 l +60 50 60 60 0 0 0 0.342053 l +60 40 60 50 0 0 0 0.342053 l +60 30 60 40 0 0 0 0.342053 l +60 20 60 30 0 0 0 0.342053 l +60 10 60 20 0 0 0 0.342053 l +60 0 60 10 0 0 0 0.342053 l +50 80 50 90 0 0 0 0.342053 l +50 70 50 80 0 0 0 0.342053 l +50 60 50 70 0 0 0 0.342053 l +50 50 50 60 0 0 0 0.342053 l +50 40 50 50 0 0 0 0.342053 l +50 30 50 40 0 0 0 0.342053 l +50 20 50 30 0 0 0 0.342053 l +50 10 50 20 0 0 0 0.342053 l +50 0 50 10 0 0 0 0.342053 l +40 80 40 90 0 0 0 0.342053 l +40 70 40 80 0 0 0 0.342053 l +40 60 40 70 0 0 0 0.342053 l +40 50 40 60 0 0 0 0.342053 l +40 40 40 50 0 0 0 0.342053 l +40 30 40 40 0 0 0 0.342053 l +40 20 40 30 0 0 0 0.342053 l +40 10 40 20 0 0 0 0.342053 l +40 0 40 10 0 0 0 0.342053 l +30 80 30 90 0 0 0 0.342053 l +30 70 30 80 0 0 0 0.342053 l +30 60 30 70 0 0 0 0.342053 l +30 50 30 60 0 0 0 0.342053 l +30 40 30 50 0 0 0 0.342053 l +30 30 30 40 0 0 0 0.342053 l +30 20 30 30 0 0 0 0.342053 l +30 10 30 20 0 0 0 0.342053 l +30 0 30 10 0 0 0 0.342053 l +20 80 20 90 0 0 0 0.342053 l +20 70 20 80 0 0 0 0.342053 l +20 60 20 70 0 0 0 0.342053 l +20 50 20 60 0 0 0 0.342053 l +20 40 20 50 0 0 0 0.342053 l +20 30 20 40 0 0 0 0.342053 l +20 20 20 30 0 0 0 0.342053 l +20 10 20 20 0 0 0 0.342053 l +20 0 20 10 0 0 0 0.342053 l +10 80 10 90 0 0 0 0.342053 l +10 70 10 80 0 0 0 0.342053 l +10 60 10 70 0 0 0 0.342053 l +10 50 10 60 0 0 0 0.342053 l +10 40 10 50 0 0 0 0.342053 l +10 30 10 40 0 0 0 0.342053 l +10 20 10 30 0 0 0 0.342053 l +10 10 10 20 0 0 0 0.342053 l +10 0 10 10 0 0 0 0.342053 l +0 80 0 90 0 0 0 0.342053 l +0 70 0 80 0 0 0 0.342053 l +0 60 0 70 0 0 0 0.342053 l +0 50 0 60 0 0 0 0.342053 l +0 40 0 50 0 0 0 0.342053 l +0 30 0 40 0 0 0 0.342053 l +0 20 0 30 0 0 0 0.342053 l +0 10 0 20 0 0 0 0.342053 l +0 0 0 10 0 0 0 0.342053 l +60 90 70 90 0 0 0 0.342053 l +60 80 70 80 0 0 0 0.342053 l +60 70 70 70 0 0 0 0.342053 l +60 60 70 60 0 0 0 0.342053 l +60 50 70 50 0 0 0 0.342053 l +60 40 70 40 0 0 0 0.342053 l +60 30 70 30 0 0 0 0.342053 l +60 20 70 20 0 0 0 0.342053 l +60 10 70 10 0 0 0 0.342053 l +60 0 70 0 0 0 0 0.342053 l +50 90 60 90 0 0 0 0.342053 l +50 80 60 80 0 0 0 0.342053 l +50 70 60 70 0 0 0 0.342053 l +50 60 60 60 0 0 0 0.342053 l +50 50 60 50 0 0 0 0.342053 l +50 40 60 40 0 0 0 0.342053 l +50 30 60 30 0 0 0 0.342053 l +50 20 60 20 0 0 0 0.342053 l +50 10 60 10 0 0 0 0.342053 l +50 0 60 0 0 0 0 0.342053 l +40 90 50 90 0 0 0 0.342053 l +40 80 50 80 0 0 0 0.342053 l +40 70 50 70 0 0 0 0.342053 l +40 60 50 60 0 0 0 0.342053 l +40 50 50 50 0 0 0 0.342053 l +40 40 50 40 0 0 0 0.342053 l +40 30 50 30 0 0 0 0.342053 l +40 20 50 20 0 0 0 0.342053 l +40 10 50 10 0 0 0 0.342053 l +40 0 50 0 0 0 0 0.342053 l +30 90 40 90 0 0 0 0.342053 l +30 80 40 80 0 0 0 0.342053 l +30 70 40 70 0 0 0 0.342053 l +30 60 40 60 0 0 0 0.342053 l +30 50 40 50 0 0 0 0.342053 l +30 40 40 40 0 0 0 0.342053 l +30 30 40 30 0 0 0 0.342053 l +30 20 40 20 0 0 0 0.342053 l +30 10 40 10 0 0 0 0.342053 l +30 0 40 0 0 0 0 0.342053 l +20 90 30 90 0 0 0 0.342053 l +20 80 30 80 0 0 0 0.342053 l +20 70 30 70 0 0 0 0.342053 l +20 60 30 60 0 0 0 0.342053 l +20 50 30 50 0 0 0 0.342053 l +20 40 30 40 0 0 0 0.342053 l +20 30 30 30 0 0 0 0.342053 l +20 20 30 20 0 0 0 0.342053 l +20 10 30 10 0 0 0 0.342053 l +20 0 30 0 0 0 0 0.342053 l +10 90 20 90 0 0 0 0.342053 l +10 80 20 80 0 0 0 0.342053 l +10 70 20 70 0 0 0 0.342053 l +10 60 20 60 0 0 0 0.342053 l +10 50 20 50 0 0 0 0.342053 l +10 40 20 40 0 0 0 0.342053 l +10 30 20 30 0 0 0 0.342053 l +10 20 20 20 0 0 0 0.342053 l +10 10 20 10 0 0 0 0.342053 l +10 0 20 0 0 0 0 0.342053 l +0 90 10 90 0 0 0 0.342053 l +0 80 10 80 0 0 0 0.342053 l +0 70 10 70 0 0 0 0.342053 l +0 60 10 60 0 0 0 0.342053 l +0 50 10 50 0 0 0 0.342053 l +0 40 10 40 0 0 0 0.342053 l +0 30 10 30 0 0 0 0.342053 l +0 20 10 20 0 0 0 0.342053 l +0 10 10 10 0 0 0 0.342053 l +0 0 10 0 0 0 0 0.342053 l +grestore +%Nodes: +gsave +70 90 1.14018 1 1 1 nc +70 80 1.14018 1 1 1 nc +70 70 1.14018 1 1 1 nc +70 60 1.14018 1 1 1 nc +70 50 1.14018 1 1 1 nc +70 40 1.14018 1 1 1 nc +70 30 1.14018 1 1 1 nc +70 20 1.14018 1 1 1 nc +70 10 1.14018 1 1 1 nc +70 0 1.14018 1 1 1 nc +60 90 1.14018 1 1 1 nc +60 80 1.14018 1 1 1 nc +60 70 1.14018 1 1 1 nc +60 60 1.14018 1 1 1 nc +60 50 1.14018 1 1 1 nc +60 40 1.14018 1 1 1 nc +60 30 1.14018 1 1 1 nc +60 20 1.14018 1 1 1 nc +60 10 1.14018 1 1 1 nc +60 0 1.14018 1 1 1 nc +50 90 1.14018 1 1 1 nc +50 80 1.14018 1 1 1 nc +50 70 1.14018 1 1 1 nc +50 60 1.14018 1 1 1 nc +50 50 1.14018 1 1 1 nc +50 40 1.14018 1 1 1 nc +50 30 1.14018 1 1 1 nc +50 20 1.14018 1 1 1 nc +50 10 1.14018 1 1 1 nc +50 0 1.14018 1 1 1 nc +40 90 1.14018 1 1 1 nc +40 80 1.14018 1 1 1 nc +40 70 1.14018 1 1 1 nc +40 60 1.14018 1 1 1 nc +40 50 1.14018 1 1 1 nc +40 40 1.14018 1 1 1 nc +40 30 1.14018 1 1 1 nc +40 20 1.14018 1 1 1 nc +40 10 1.14018 1 1 1 nc +40 0 1.14018 1 1 1 nc +30 90 1.14018 1 1 1 nc +30 80 1.14018 1 1 1 nc +30 70 1.14018 1 1 1 nc +30 60 1.14018 1 1 1 nc +30 50 1.14018 1 1 1 nc +30 40 1.14018 1 1 1 nc +30 30 1.14018 1 1 1 nc +30 20 1.14018 1 1 1 nc +30 10 1.14018 1 1 1 nc +30 0 1.14018 1 1 1 nc +20 90 1.14018 1 1 1 nc +20 80 1.14018 1 1 1 nc +20 70 1.14018 1 1 1 nc +20 60 1.14018 1 1 1 nc +20 50 1.14018 1 1 1 nc +20 40 1.14018 1 1 1 nc +20 30 1.14018 1 1 1 nc +20 20 1.14018 1 1 1 nc +20 10 1.14018 1 1 1 nc +20 0 1.14018 1 1 1 nc +10 90 1.14018 1 1 1 nc +10 80 1.14018 1 1 1 nc +10 70 1.14018 1 1 1 nc +10 60 1.14018 1 1 1 nc +10 50 1.14018 1 1 1 nc +10 40 1.14018 1 1 1 nc +10 30 1.14018 1 1 1 nc +10 20 1.14018 1 1 1 nc +10 10 1.14018 1 1 1 nc +10 0 1.14018 1 1 1 nc +0 90 1.14018 1 1 1 nc +0 80 1.14018 1 1 1 nc +0 70 1.14018 1 1 1 nc +0 60 1.14018 1 1 1 nc +0 50 1.14018 1 1 1 nc +0 40 1.14018 1 1 1 nc +0 30 1.14018 1 1 1 nc +0 20 1.14018 1 1 1 nc +0 10 1.14018 1 1 1 nc +0 0 1.14018 1 1 1 nc +grestore +grestore +showpage diff -r a24939ee343c -r 590c1b663a27 doc/images/grid_ugraph.png Binary file doc/images/grid_ugraph.png has changed diff -r a24939ee343c -r 590c1b663a27 lemon/full_graph.h --- a/lemon/full_graph.h Fri Sep 29 11:23:54 2006 +0000 +++ b/lemon/full_graph.h Fri Sep 29 11:25:27 2006 +0000 @@ -35,9 +35,6 @@ namespace lemon { - /// \brief Base of the FullGrpah. - /// - /// Base of the FullGrpah. class FullGraphBase { int _nodeNum; int _edgeNum; @@ -48,71 +45,35 @@ class Node; class Edge; - public: + protected: FullGraphBase() {} + void construct(int n) { _nodeNum = n; _edgeNum = n * n; } - ///Creates a full graph with \c n nodes. - void construct(int n) { _nodeNum = n; _edgeNum = n * n; } + public: 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 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 nodeFromId(int id) { return Node(id);} @@ -121,14 +82,6 @@ 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; } @@ -217,7 +170,6 @@ /// the \ref concept::Graph "Graph" concept /// \sa concept::Graph. /// - /// \sa FullGraphBase /// \sa FullUGraph /// /// \author Alpar Juttner @@ -245,12 +197,37 @@ Parent::getNotifier(Node()).build(); 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; int _edgeNum; @@ -261,59 +238,32 @@ class Node; class Edge; - public: + protected: 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. + public: + + Node operator()(int index) const { return Node(index); } + int index(const Node& node) const { return node.id; } - /// \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);} Node source(Edge e) const { @@ -326,36 +276,9 @@ 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); @@ -456,7 +379,6 @@ /// 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 @@ -485,6 +407,55 @@ Parent::getNotifier(UEdge()).build(); 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); + } + } }; @@ -496,6 +467,16 @@ int _edgeNum; + protected: + + FullBpUGraphBase() {} + + void construct(int aNodeNum, int bNodeNum) { + _aNodeNum = aNodeNum; + _bNodeNum = bNodeNum; + _edgeNum = aNodeNum * bNodeNum; + } + public: class NodeSetError : public LogicError { @@ -533,10 +514,20 @@ bool operator<(const UEdge i) const {return 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)); + } } void firstANode(Node& node) const { @@ -650,13 +641,6 @@ 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; } @@ -666,6 +650,18 @@ typedef True EdgeNumTag; 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)); + } + } + }; @@ -680,9 +676,6 @@ /// 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 { @@ -700,6 +693,7 @@ /// \brief Resize the graph /// + /// Resize the graph void resize(int n, int m) { Parent::getNotifier(Edge()).clear(); Parent::getNotifier(UEdge()).clear(); @@ -713,6 +707,72 @@ Parent::getNotifier(UEdge()).build(); 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); + } }; } //namespace lemon diff -r a24939ee343c -r 590c1b663a27 lemon/grid_ugraph.h --- a/lemon/grid_ugraph.h Fri Sep 29 11:23:54 2006 +0000 +++ b/lemon/grid_ugraph.h Fri Sep 29 11:25:27 2006 +0000 @@ -34,13 +34,6 @@ 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 { public: @@ -56,19 +49,12 @@ 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; _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; _edgeLimit = _nodeNum - 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) { return Edge(n.id); @@ -77,10 +63,6 @@ } } - /// \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) { return Edge(n.id - _width); @@ -89,10 +71,6 @@ } } - /// \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) { return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1); @@ -101,10 +79,6 @@ } } - /// \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) { return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1; @@ -123,39 +97,24 @@ }; - /// \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 && j < height(), IndexError()); return Node(i + j * _width); } - /// \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; } @@ -163,25 +122,12 @@ 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 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) { return e.id; @@ -191,9 +137,6 @@ } } - /// \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) { return e.id + _width; @@ -203,24 +146,7 @@ } } - /// 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 nodeFromId(int id) { return Node(id);} @@ -229,14 +155,6 @@ 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; if (v.id - u.id == _width) return Edge(u.id); @@ -360,6 +278,9 @@ /// 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: ///\code /// GridUGraph graph(w, h); @@ -375,7 +296,6 @@ /// "Undirected Graph" concept. /// /// \author Balazs Dezso - /// \see GridUGraphBase class GridUGraph : public ExtendedGridUGraphBase { public: @@ -476,6 +396,41 @@ Parent::getNotifier(Edge()).build(); } + /// \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. /// /// Gives back the edge goes down from the node. If there is not diff -r a24939ee343c -r 590c1b663a27 lemon/hypercube_graph.h --- a/lemon/hypercube_graph.h Fri Sep 29 11:23:54 2006 +0000 +++ b/lemon/hypercube_graph.h Fri Sep 29 11:25:27 2006 +0000 @@ -34,13 +34,6 @@ 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 { public: @@ -56,9 +49,6 @@ protected: - /// \brief Creates a hypercube graph with the given size. - /// - /// Creates a hypercube graph with the given size. void construct(int dim) { _dim = dim; _nodeNum = 1 << dim; @@ -70,54 +60,21 @@ typedef True NodeNumTag; 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; } static Node nodeFromId(int id) { return Node(id);} @@ -192,39 +149,22 @@ } } - /// \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); } @@ -252,16 +192,59 @@ /// The graph type is fully conform to the \ref concept::Graph /// 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. /// /// It makes possible to give back a linear combination