1.1 --- a/doc/graphs.dox Mon Jun 26 15:40:35 2006 +0000
1.2 +++ b/doc/graphs.dox Wed Jun 28 15:06:24 2006 +0000
1.3 @@ -2,23 +2,20 @@
1.4
1.5 \page graphs Graphs
1.6
1.7 +\todo Write a new Graphs page. I think it should be contain the Graph,
1.8 +UGraph and BpUGraph concept. It should be describe the iterators and
1.9 +the basic functions and the differences of the implementations.
1.10 +
1.11 The primary data structures of LEMON are the graph classes. They all
1.12 provide a node list - edge list interface, i.e. they have
1.13 functionalities to list the nodes and the edges of the graph as well
1.14 as incoming and outgoing edges of a given node.
1.15
1.16 +Each graph should meet the \ref lemon::concept::Graph "Graph" concept.
1.17 +This concept does not make it possible to change the graph (i.e. it is
1.18 +not possible to add or delete edges or nodes). Most of the graph
1.19 +algorithms will run on these graphs.
1.20
1.21 -Each graph should meet the
1.22 -\ref lemon::concept::StaticGraph "StaticGraph" concept.
1.23 -This concept does not
1.24 -make it possible to change the graph (i.e. it is not possible to add
1.25 -or delete edges or nodes). Most of the graph algorithms will run on
1.26 -these graphs.
1.27 -
1.28 -The graphs meeting the
1.29 -\ref lemon::concept::ExtendableGraph "ExtendableGraph"
1.30 -concept allow node and
1.31 -edge addition. You can also "clear" such a graph (i.e. erase all edges and nodes ).
1.32
1.33 In case of graphs meeting the full feature
1.34 \ref lemon::concept::ErasableGraph "ErasableGraph"
1.35 @@ -36,7 +33,7 @@
1.36 so you cannot delete individual edges or nodes.
1.37 \li \ref lemon::FullGraph "FullGraph"
1.38 implements a complete graph. It is a
1.39 -\ref lemon::concept::StaticGraph "StaticGraph", so you cannot
1.40 +\ref lemon::concept::Graph "Graph", so you cannot
1.41 change the number of nodes once it is constructed. It is extremely memory
1.42 efficient: it uses constant amount of memory independently from the number of
1.43 the nodes of the graph. Of course, the size of the \ref maps-page "NodeMap"'s and
2.1 --- a/lemon/bellman_ford.h Mon Jun 26 15:40:35 2006 +0000
2.2 +++ b/lemon/bellman_ford.h Wed Jun 28 15:06:24 2006 +0000
2.3 @@ -164,7 +164,7 @@
2.4 /// is \ref ListGraph. The value of _Graph is not used directly by
2.5 /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
2.6 /// \param _LengthMap This read-only EdgeMap determines the lengths of the
2.7 - /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
2.8 + /// edges. The default map type is \ref concept::Graph::EdgeMap
2.9 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
2.10 /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
2.11 /// \param _Traits Traits class to set various data types used by the
3.1 --- a/lemon/concept/bpugraph.h Mon Jun 26 15:40:35 2006 +0000
3.2 +++ b/lemon/concept/bpugraph.h Wed Jun 28 15:06:24 2006 +0000
3.3 @@ -947,70 +947,6 @@
3.4
3.5 };
3.6
3.7 - /// \brief An empty non-static undirected graph class.
3.8 - ///
3.9 - /// This class provides everything that \ref BpUGraph does.
3.10 - /// Additionally it enables building graphs from scratch.
3.11 - class ExtendableBpUGraph : public BpUGraph {
3.12 - public:
3.13 -
3.14 - /// \brief Add a new ANode to the graph.
3.15 - ///
3.16 - /// Add a new ANode to the graph.
3.17 - /// \return the new node.
3.18 - Node addANode();
3.19 -
3.20 - /// \brief Add a new ANode to the graph.
3.21 - ///
3.22 - /// Add a new ANode to the graph.
3.23 - /// \return the new node.
3.24 - Node addBNode();
3.25 -
3.26 - /// \brief Add a new undirected edge to the graph.
3.27 - ///
3.28 - /// Add a new undirected edge to the graph. One of the nodes
3.29 - /// should be ANode and the other should be BNode.
3.30 - /// \pre The nodes are not in the same nodeset.
3.31 - /// \return the new edge.
3.32 - UEdge addEdge(const Node& from, const Node& to);
3.33 -
3.34 - /// \brief Resets the graph.
3.35 - ///
3.36 - /// This function deletes all undirected edges and nodes of the graph.
3.37 - /// It also frees the memory allocated to store them.
3.38 - void clear() { }
3.39 -
3.40 - template <typename Graph>
3.41 - struct Constraints {
3.42 - void constraints() {}
3.43 - };
3.44 -
3.45 - };
3.46 -
3.47 - /// \brief An empty erasable undirected graph class.
3.48 - ///
3.49 - /// This class is an extension of \ref ExtendableBpUGraph. It makes it
3.50 - /// possible to erase undirected edges or nodes.
3.51 - class ErasableBpUGraph : public ExtendableBpUGraph {
3.52 - public:
3.53 -
3.54 - /// \brief Deletes a node.
3.55 - ///
3.56 - /// Deletes a node.
3.57 - ///
3.58 - void erase(Node) { }
3.59 - /// \brief Deletes an undirected edge.
3.60 - ///
3.61 - /// Deletes an undirected edge.
3.62 - ///
3.63 - void erase(UEdge) { }
3.64 -
3.65 - template <typename Graph>
3.66 - struct Constraints {
3.67 - void constraints() {}
3.68 - };
3.69 -
3.70 - };
3.71
3.72 /// @}
3.73
4.1 --- a/lemon/concept/graph.h Mon Jun 26 15:40:35 2006 +0000
4.2 +++ b/lemon/concept/graph.h Wed Jun 28 15:06:24 2006 +0000
4.3 @@ -38,8 +38,8 @@
4.4
4.5 // \brief Modular static graph class.
4.6 //
4.7 - // It should be the same as the \c StaticGraph class.
4.8 - class _StaticGraph
4.9 + // It should be the same as the \c Graph class.
4.10 + class _Graph
4.11 : virtual public BaseGraphComponent,
4.12 public IterableGraphComponent, public MappableGraphComponent {
4.13 public:
4.14 @@ -56,49 +56,10 @@
4.15 };
4.16 };
4.17
4.18 - // \brief Modular extendable graph class.
4.19 - //
4.20 - // It should be the same as the \c ExtendableGraph class.
4.21 - class _ExtendableGraph
4.22 - : virtual public BaseGraphComponent, public _StaticGraph,
4.23 - public ExtendableGraphComponent, public ClearableGraphComponent {
4.24 - public:
4.25 - typedef BaseGraphComponent::Node Node;
4.26 - typedef BaseGraphComponent::Edge Edge;
4.27 -
4.28 - template <typename _Graph>
4.29 - struct Constraints {
4.30 - void constraints() {
4.31 - checkConcept<_StaticGraph, _Graph >();
4.32 - checkConcept<ExtendableGraphComponent, _Graph >();
4.33 - checkConcept<ClearableGraphComponent, _Graph >();
4.34 - }
4.35 - };
4.36 - };
4.37 -
4.38 - // \brief Modular erasable graph class.
4.39 - //
4.40 - // It should be the same as the \c ErasableGraph class.
4.41 - class _ErasableGraph
4.42 - : virtual public BaseGraphComponent, public _ExtendableGraph,
4.43 - public ErasableGraphComponent {
4.44 - public:
4.45 - typedef BaseGraphComponent::Node Node;
4.46 - typedef BaseGraphComponent::Edge Edge;
4.47 -
4.48 - template <typename _Graph>
4.49 - struct Constraints {
4.50 - void constraints() {
4.51 - checkConcept<_ExtendableGraph, _Graph >();
4.52 - checkConcept<ErasableGraphComponent, _Graph >();
4.53 - }
4.54 - };
4.55 - };
4.56 -
4.57 /// \addtogroup graph_concepts
4.58 /// @{
4.59
4.60 - /// An empty static graph class.
4.61 + /// An empty graph class.
4.62
4.63 /// This class provides all the common features of a graph structure,
4.64 /// however completely without implementations and real data structures
4.65 @@ -116,13 +77,7 @@
4.66 ///
4.67 /// \todo A pages describing the concept of concept description would
4.68 /// be nice.
4.69 - class StaticGraph
4.70 - {
4.71 -// ///Copy consructor.
4.72 -
4.73 -// ///\todo It is not clear, what we expect from a copy constructor.
4.74 -// ///E.g. How to assign the nodes/edges to each other? What about maps?
4.75 -// StaticGraph(const StaticGraph& g) { }
4.76 + class Graph {
4.77 public:
4.78 ///\e
4.79
4.80 @@ -130,7 +85,7 @@
4.81
4.82 /// Defalult constructor.
4.83 ///
4.84 - StaticGraph() { }
4.85 + Graph() { }
4.86
4.87 /// The base type of node iterators,
4.88 /// or in other words, the trivial node iterator.
4.89 @@ -213,14 +168,14 @@
4.90
4.91 /// Sets the iterator to the first node of \c g.
4.92 ///
4.93 - NodeIt(const StaticGraph&) { }
4.94 + NodeIt(const Graph&) { }
4.95 /// Node -> NodeIt conversion.
4.96
4.97 /// Sets the iterator to the node of \c the graph pointed by
4.98 /// the trivial iterator.
4.99 /// This feature necessitates that each time we
4.100 /// iterate the edge-set, the iteration order is the same.
4.101 - NodeIt(const StaticGraph&, const Node&) { }
4.102 + NodeIt(const Graph&, const Node&) { }
4.103 /// Next node.
4.104
4.105 /// Assign the iterator to the next node.
4.106 @@ -307,13 +262,13 @@
4.107
4.108 /// This constructor sets the iterator to the first outgoing edge of
4.109 /// the node.
4.110 - OutEdgeIt(const StaticGraph&, const Node&) { }
4.111 + OutEdgeIt(const Graph&, const Node&) { }
4.112 /// Edge -> OutEdgeIt conversion
4.113
4.114 /// Sets the iterator to the value of the trivial iterator.
4.115 /// This feature necessitates that each time we
4.116 /// iterate the edge-set, the iteration order is the same.
4.117 - OutEdgeIt(const StaticGraph&, const Edge&) { }
4.118 + OutEdgeIt(const Graph&, const Edge&) { }
4.119 ///Next outgoing edge
4.120
4.121 /// Assign the iterator to the next
4.122 @@ -354,13 +309,13 @@
4.123
4.124 /// This constructor set the iterator to the first incoming edge of
4.125 /// the node.
4.126 - InEdgeIt(const StaticGraph&, const Node&) { }
4.127 + InEdgeIt(const Graph&, const Node&) { }
4.128 /// Edge -> InEdgeIt conversion
4.129
4.130 /// Sets the iterator to the value of the trivial iterator \c e.
4.131 /// This feature necessitates that each time we
4.132 /// iterate the edge-set, the iteration order is the same.
4.133 - InEdgeIt(const StaticGraph&, const Edge&) { }
4.134 + InEdgeIt(const Graph&, const Edge&) { }
4.135 /// Next incoming edge
4.136
4.137 /// Assign the iterator to the next inedge of the corresponding node.
4.138 @@ -397,13 +352,13 @@
4.139
4.140 /// This constructor sets the iterator to the first edge of \c g.
4.141 ///@param g the graph
4.142 - EdgeIt(const StaticGraph& g) { ignore_unused_variable_warning(g); }
4.143 + EdgeIt(const Graph& g) { ignore_unused_variable_warning(g); }
4.144 /// Edge -> EdgeIt conversion
4.145
4.146 /// Sets the iterator to the value of the trivial iterator \c e.
4.147 /// This feature necessitates that each time we
4.148 /// iterate the edge-set, the iteration order is the same.
4.149 - EdgeIt(const StaticGraph&, const Edge&) { }
4.150 + EdgeIt(const Graph&, const Edge&) { }
4.151 ///Next edge
4.152
4.153 /// Assign the iterator to the next edge.
4.154 @@ -420,53 +375,17 @@
4.155 ///
4.156 Node source(Edge) const { return INVALID; }
4.157
4.158 -// /// Gives back the first Node in the iterating order.
4.159 -
4.160 -// /// Gives back the first Node in the iterating order.
4.161 -// ///
4.162 void first(Node&) const {}
4.163 -
4.164 -// /// Gives back the next Node in the iterating order.
4.165 -
4.166 -// /// Gives back the next Node in the iterating order.
4.167 -// ///
4.168 void next(Node&) const {}
4.169
4.170 -// /// Gives back the first Edge in the iterating order.
4.171 -
4.172 -// /// Gives back the first Edge in the iterating order.
4.173 -// ///
4.174 void first(Edge&) const {}
4.175 -// /// Gives back the next Edge in the iterating order.
4.176 -
4.177 -// /// Gives back the next Edge in the iterating order.
4.178 -// ///
4.179 void next(Edge&) const {}
4.180
4.181
4.182 -// /// Gives back the first of the Edges point to the given Node.
4.183 -
4.184 -// /// Gives back the first of the Edges point to the given Node.
4.185 -// ///
4.186 void firstIn(Edge&, const Node&) const {}
4.187 -
4.188 -// /// Gives back the next of the Edges points to the given Node.
4.189 -
4.190 -
4.191 -// /// Gives back the next of the Edges points to the given Node.
4.192 -// ///
4.193 void nextIn(Edge&) const {}
4.194
4.195 -// /// Gives back the first of the Edges start from the given Node.
4.196 -
4.197 -// /// Gives back the first of the Edges start from the given Node.
4.198 -// ///
4.199 void firstOut(Edge&, const Node&) const {}
4.200 -
4.201 -// /// Gives back the next of the Edges start from the given Node.
4.202 -
4.203 -// /// Gives back the next of the Edges start from the given Node.
4.204 -// ///
4.205 void nextOut(Edge&) const {}
4.206
4.207 /// \brief The base node of the iterator.
4.208 @@ -511,9 +430,9 @@
4.209 public:
4.210
4.211 ///\e
4.212 - NodeMap(const StaticGraph&) { }
4.213 + NodeMap(const Graph&) { }
4.214 ///\e
4.215 - NodeMap(const StaticGraph&, T) { }
4.216 + NodeMap(const Graph&, T) { }
4.217
4.218 ///Copy constructor
4.219 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
4.220 @@ -535,9 +454,9 @@
4.221 public:
4.222
4.223 ///\e
4.224 - EdgeMap(const StaticGraph&) { }
4.225 + EdgeMap(const Graph&) { }
4.226 ///\e
4.227 - EdgeMap(const StaticGraph&, T) { }
4.228 + EdgeMap(const Graph&, T) { }
4.229 ///Copy constructor
4.230 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
4.231 ///Assignment operator
4.232 @@ -545,72 +464,8 @@
4.233 // \todo fix this concept
4.234 };
4.235
4.236 - template <typename _Graph>
4.237 - struct Constraints : public _StaticGraph::Constraints<_Graph> {};
4.238 -
4.239 - };
4.240 -
4.241 - /// An empty non-static graph class.
4.242 -
4.243 - /// This class provides everything that \ref StaticGraph does.
4.244 - /// Additionally it enables building graphs from scratch.
4.245 - class ExtendableGraph : public StaticGraph
4.246 - {
4.247 - public:
4.248 - /// Defalult constructor.
4.249 -
4.250 - /// Defalult constructor.
4.251 - ///
4.252 - ExtendableGraph() { }
4.253 - ///Add a new node to the graph.
4.254 -
4.255 - /// \return the new node.
4.256 - ///
4.257 - Node addNode() { return INVALID; }
4.258 - ///Add a new edge to the graph.
4.259 -
4.260 - ///Add a new edge to the graph with source node \c s
4.261 - ///and target node \c t.
4.262 - ///\return the new edge.
4.263 - Edge addEdge(Node, Node) { return INVALID; }
4.264 -
4.265 - /// Resets the graph.
4.266 -
4.267 - /// This function deletes all edges and nodes of the graph.
4.268 - /// It also frees the memory allocated to store them.
4.269 - /// \todo It might belong to \ref ErasableGraph.
4.270 - void clear() { }
4.271 -
4.272 - template <typename _Graph>
4.273 - struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};
4.274 -
4.275 - };
4.276 -
4.277 - /// An empty erasable graph class.
4.278 -
4.279 - /// This class is an extension of \ref ExtendableGraph. It makes it
4.280 - /// possible to erase edges or nodes.
4.281 - class ErasableGraph : public ExtendableGraph
4.282 - {
4.283 - public:
4.284 - /// Defalult constructor.
4.285 -
4.286 - /// Defalult constructor.
4.287 - ///
4.288 - ErasableGraph() { }
4.289 - /// Deletes a node.
4.290 -
4.291 - /// Deletes node \c n node.
4.292 - ///
4.293 - void erase(Node) { }
4.294 - /// Deletes an edge.
4.295 -
4.296 - /// Deletes edge \c e edge.
4.297 - ///
4.298 - void erase(Edge) { }
4.299 -
4.300 - template <typename _Graph>
4.301 - struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
4.302 + template <typename RGraph>
4.303 + struct Constraints : public _Graph::Constraints<RGraph> {};
4.304
4.305 };
4.306
5.1 --- a/lemon/concept/graph_component.h Mon Jun 26 15:40:35 2006 +0000
5.2 +++ b/lemon/concept/graph_component.h Wed Jun 28 15:06:24 2006 +0000
5.3 @@ -458,7 +458,7 @@
5.4 /// This class provides beside the core graph features
5.5 /// core clear functions for the graph structure.
5.6 /// The most of the base graphs should be conform to this concept.
5.7 - class ClearableGraphComponent : virtual public BaseGraphComponent {
5.8 + class BaseClearableGraphComponent : virtual public BaseGraphComponent {
5.9 public:
5.10
5.11 /// Erase all the Nodes and Edges from the graph.
5.12 @@ -646,7 +646,7 @@
5.13
5.14 /// This class provides beside the core graph features
5.15 /// iterator based iterable interface for the graph structure.
5.16 - /// This concept is part of the StaticGraphConcept.
5.17 + /// This concept is part of the GraphConcept.
5.18 class IterableGraphComponent : virtual public BaseGraphComponent {
5.19
5.20 public:
5.21 @@ -817,7 +817,7 @@
5.22
5.23 /// This class provides beside the core graph features
5.24 /// map interface for the graph structure.
5.25 - /// This concept is part of the StaticGraphConcept.
5.26 + /// This concept is part of the GraphConcept.
5.27 class MappableGraphComponent : virtual public BaseGraphComponent {
5.28 public:
5.29
5.30 @@ -930,86 +930,160 @@
5.31 };
5.32 };
5.33
5.34 - /// \brief An empty extendable extended graph class.
5.35 - ///
5.36 - /// This class provides beside the core graph features
5.37 - /// item addition interface for the graph structure.
5.38 - /// The difference between this class and the
5.39 - /// \c BaseExtendableGraphComponent is that it should
5.40 - /// notify the item alteration observers.
5.41 - class ExtendableGraphComponent : virtual public BaseGraphComponent {
5.42 +
5.43 +// /// Skeleton class which describes an edge with direction in \ref
5.44 +// /// UGraph "undirected graph".
5.45 + template <typename UGraph>
5.46 + class UGraphEdge : public UGraph::UEdge {
5.47 + typedef typename UGraph::UEdge UEdge;
5.48 + typedef typename UGraph::Node Node;
5.49 public:
5.50
5.51 - typedef ExtendableGraphComponent Graph;
5.52 + /// \e
5.53 + UGraphEdge() {}
5.54
5.55 - typedef BaseGraphComponent::Node Node;
5.56 - typedef BaseGraphComponent::Edge Edge;
5.57 + /// \e
5.58 + UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
5.59
5.60 - /// \brief Add a node to the graph.
5.61 + /// \e
5.62 + UGraphEdge(Invalid) {}
5.63 +
5.64 + /// \brief Directed edge from undirected edge and a source node.
5.65 ///
5.66 - /// Add a node to the graph and notify the observers.
5.67 - Node addNode() {
5.68 - return INVALID;
5.69 - }
5.70 -
5.71 - /// \brief Add an edge to the graph.
5.72 + /// Constructs a directed edge from undirected edge and a source node.
5.73 ///
5.74 - /// Add an edge to the graph and notify the observers.
5.75 - Edge addEdge(const Node&, const Node&) {
5.76 - return INVALID;
5.77 + /// \note You have to specify the graph for this constructor.
5.78 + UGraphEdge(const UGraph &g,
5.79 + UEdge u_edge, Node n) {
5.80 + ignore_unused_variable_warning(u_edge);
5.81 + ignore_unused_variable_warning(g);
5.82 + ignore_unused_variable_warning(n);
5.83 }
5.84
5.85 - template <typename _Graph>
5.86 + /// \e
5.87 + UGraphEdge& operator=(UGraphEdge) { return *this; }
5.88 +
5.89 + /// \e
5.90 + bool operator==(UGraphEdge) const { return true; }
5.91 + /// \e
5.92 + bool operator!=(UGraphEdge) const { return false; }
5.93 +
5.94 + /// \e
5.95 + bool operator<(UGraphEdge) const { return false; }
5.96 +
5.97 + template <typename Edge>
5.98 struct Constraints {
5.99 void constraints() {
5.100 - checkConcept<BaseGraphComponent, _Graph >();
5.101 - typename _Graph::Node node_a, node_b;
5.102 - node_a = graph.addNode();
5.103 - node_b = graph.addNode();
5.104 - typename _Graph::Edge edge;
5.105 - edge = graph.addEdge(node_a, node_b);
5.106 + const_constraints();
5.107 }
5.108 - _Graph& graph;
5.109 + void const_constraints() const {
5.110 + /// \bug This should be is_base_and_derived ...
5.111 + UEdge ue = e;
5.112 + ue = e;
5.113 +
5.114 + Edge e_with_source(graph,ue,n);
5.115 + ignore_unused_variable_warning(e_with_source);
5.116 + }
5.117 + Edge e;
5.118 + UEdge ue;
5.119 + UGraph graph;
5.120 + Node n;
5.121 };
5.122 };
5.123 +
5.124
5.125 - /// \brief An empty erasable extended graph class.
5.126 - ///
5.127 - /// This class provides beside the core graph features
5.128 - /// item erase interface for the graph structure.
5.129 - /// The difference between this class and the
5.130 - /// \c BaseErasableGraphComponent is that it should
5.131 - /// notify the item alteration observers.
5.132 - class ErasableGraphComponent : virtual public BaseGraphComponent {
5.133 - public:
5.134 + struct BaseIterableUGraphConcept {
5.135
5.136 - typedef ErasableGraphComponent Graph;
5.137 + template <typename Graph>
5.138 + struct Constraints {
5.139
5.140 - typedef BaseGraphComponent::Node Node;
5.141 - typedef BaseGraphComponent::Edge Edge;
5.142 + typedef typename Graph::UEdge UEdge;
5.143 + typedef typename Graph::Edge Edge;
5.144 + typedef typename Graph::Node Node;
5.145
5.146 - /// \brief Erase the Node and notify the node alteration observers.
5.147 - ///
5.148 - /// Erase the Node and notify the node alteration observers.
5.149 - void erase(const Node&) {}
5.150 + void constraints() {
5.151 + checkConcept<BaseIterableGraphComponent, Graph>();
5.152 + checkConcept<GraphItem<>, UEdge>();
5.153 + //checkConcept<UGraphEdge<Graph>, Edge>();
5.154
5.155 - /// \brief Erase the Edge and notify the edge alteration observers.
5.156 - ///
5.157 - /// Erase the Edge and notify the edge alteration observers.
5.158 - void erase(const Edge&) {}
5.159 + graph.first(ue);
5.160 + graph.next(ue);
5.161
5.162 - template <typename _Graph>
5.163 + const_constraints();
5.164 + }
5.165 + void const_constraints() {
5.166 + Node n;
5.167 + n = graph.target(ue);
5.168 + n = graph.source(ue);
5.169 + n = graph.oppositeNode(n0, ue);
5.170 +
5.171 + bool b;
5.172 + b = graph.direction(e);
5.173 + Edge e = graph.direct(UEdge(), true);
5.174 + e = graph.direct(UEdge(), n);
5.175 +
5.176 + ignore_unused_variable_warning(b);
5.177 + }
5.178 +
5.179 + Graph graph;
5.180 + Edge e;
5.181 + Node n0;
5.182 + UEdge ue;
5.183 + };
5.184 +
5.185 + };
5.186 +
5.187 +
5.188 + struct IterableUGraphConcept {
5.189 +
5.190 + template <typename Graph>
5.191 struct Constraints {
5.192 void constraints() {
5.193 - checkConcept<BaseGraphComponent, _Graph >();
5.194 - typename _Graph::Node node;
5.195 - graph.erase(node);
5.196 - typename _Graph::Edge edge;
5.197 - graph.erase(edge);
5.198 + /// \todo we don't need the iterable component to be base iterable
5.199 + /// Don't we really???
5.200 + //checkConcept< BaseIterableUGraphConcept, Graph > ();
5.201 +
5.202 + checkConcept<IterableGraphComponent, Graph> ();
5.203 +
5.204 + typedef typename Graph::UEdge UEdge;
5.205 + typedef typename Graph::UEdgeIt UEdgeIt;
5.206 + typedef typename Graph::IncEdgeIt IncEdgeIt;
5.207 +
5.208 + checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
5.209 + checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
5.210 }
5.211 + };
5.212
5.213 - _Graph& graph;
5.214 + };
5.215 +
5.216 + struct MappableUGraphConcept {
5.217 +
5.218 + template <typename Graph>
5.219 + struct Constraints {
5.220 +
5.221 + struct Dummy {
5.222 + int value;
5.223 + Dummy() : value(0) {}
5.224 + Dummy(int _v) : value(_v) {}
5.225 + };
5.226 +
5.227 + void constraints() {
5.228 + checkConcept<MappableGraphComponent, Graph>();
5.229 +
5.230 + typedef typename Graph::template UEdgeMap<int> IntMap;
5.231 + checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
5.232 + IntMap >();
5.233 +
5.234 + typedef typename Graph::template UEdgeMap<bool> BoolMap;
5.235 + checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
5.236 + BoolMap >();
5.237 +
5.238 + typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
5.239 + checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
5.240 + DummyMap >();
5.241 + }
5.242 };
5.243 +
5.244 };
5.245
5.246 }
6.1 --- a/lemon/concept/ugraph.h Mon Jun 26 15:40:35 2006 +0000
6.2 +++ b/lemon/concept/ugraph.h Wed Jun 28 15:06:24 2006 +0000
6.3 @@ -18,7 +18,7 @@
6.4
6.5 ///\ingroup graph_concepts
6.6 ///\file
6.7 -///\brief Undirected graphs and components of.
6.8 +///\brief The concept of the undirected graphs.
6.9
6.10
6.11 #ifndef LEMON_CONCEPT_UGRAPH_H
6.12 @@ -31,191 +31,6 @@
6.13 namespace lemon {
6.14 namespace concept {
6.15
6.16 -// /// Skeleton class which describes an edge with direction in \ref
6.17 -// /// UGraph "undirected graph".
6.18 - template <typename UGraph>
6.19 - class UGraphEdge : public UGraph::UEdge {
6.20 - typedef typename UGraph::UEdge UEdge;
6.21 - typedef typename UGraph::Node Node;
6.22 - public:
6.23 -
6.24 - /// \e
6.25 - UGraphEdge() {}
6.26 -
6.27 - /// \e
6.28 - UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
6.29 -
6.30 - /// \e
6.31 - UGraphEdge(Invalid) {}
6.32 -
6.33 - /// \brief Directed edge from undirected edge and a source node.
6.34 - ///
6.35 - /// Constructs a directed edge from undirected edge and a source node.
6.36 - ///
6.37 - /// \note You have to specify the graph for this constructor.
6.38 - UGraphEdge(const UGraph &g,
6.39 - UEdge u_edge, Node n) {
6.40 - ignore_unused_variable_warning(u_edge);
6.41 - ignore_unused_variable_warning(g);
6.42 - ignore_unused_variable_warning(n);
6.43 - }
6.44 -
6.45 - /// \e
6.46 - UGraphEdge& operator=(UGraphEdge) { return *this; }
6.47 -
6.48 - /// \e
6.49 - bool operator==(UGraphEdge) const { return true; }
6.50 - /// \e
6.51 - bool operator!=(UGraphEdge) const { return false; }
6.52 -
6.53 - /// \e
6.54 - bool operator<(UGraphEdge) const { return false; }
6.55 -
6.56 - template <typename Edge>
6.57 - struct Constraints {
6.58 - void constraints() {
6.59 - const_constraints();
6.60 - }
6.61 - void const_constraints() const {
6.62 - /// \bug This should be is_base_and_derived ...
6.63 - UEdge ue = e;
6.64 - ue = e;
6.65 -
6.66 - Edge e_with_source(graph,ue,n);
6.67 - ignore_unused_variable_warning(e_with_source);
6.68 - }
6.69 - Edge e;
6.70 - UEdge ue;
6.71 - UGraph graph;
6.72 - Node n;
6.73 - };
6.74 - };
6.75 -
6.76 -
6.77 - struct BaseIterableUGraphConcept {
6.78 -
6.79 - template <typename Graph>
6.80 - struct Constraints {
6.81 -
6.82 - typedef typename Graph::UEdge UEdge;
6.83 - typedef typename Graph::Edge Edge;
6.84 - typedef typename Graph::Node Node;
6.85 -
6.86 - void constraints() {
6.87 - checkConcept<BaseIterableGraphComponent, Graph>();
6.88 - checkConcept<GraphItem<>, UEdge>();
6.89 - //checkConcept<UGraphEdge<Graph>, Edge>();
6.90 -
6.91 - graph.first(ue);
6.92 - graph.next(ue);
6.93 -
6.94 - const_constraints();
6.95 - }
6.96 - void const_constraints() {
6.97 - Node n;
6.98 - n = graph.target(ue);
6.99 - n = graph.source(ue);
6.100 - n = graph.oppositeNode(n0, ue);
6.101 -
6.102 - bool b;
6.103 - b = graph.direction(e);
6.104 - Edge e = graph.direct(UEdge(), true);
6.105 - e = graph.direct(UEdge(), n);
6.106 -
6.107 - ignore_unused_variable_warning(b);
6.108 - }
6.109 -
6.110 - Graph graph;
6.111 - Edge e;
6.112 - Node n0;
6.113 - UEdge ue;
6.114 - };
6.115 -
6.116 - };
6.117 -
6.118 -
6.119 - struct IterableUGraphConcept {
6.120 -
6.121 - template <typename Graph>
6.122 - struct Constraints {
6.123 - void constraints() {
6.124 - /// \todo we don't need the iterable component to be base iterable
6.125 - /// Don't we really???
6.126 - //checkConcept< BaseIterableUGraphConcept, Graph > ();
6.127 -
6.128 - checkConcept<IterableGraphComponent, Graph> ();
6.129 -
6.130 - typedef typename Graph::UEdge UEdge;
6.131 - typedef typename Graph::UEdgeIt UEdgeIt;
6.132 - typedef typename Graph::IncEdgeIt IncEdgeIt;
6.133 -
6.134 - checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
6.135 - checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
6.136 - }
6.137 - };
6.138 -
6.139 - };
6.140 -
6.141 - struct MappableUGraphConcept {
6.142 -
6.143 - template <typename Graph>
6.144 - struct Constraints {
6.145 -
6.146 - struct Dummy {
6.147 - int value;
6.148 - Dummy() : value(0) {}
6.149 - Dummy(int _v) : value(_v) {}
6.150 - };
6.151 -
6.152 - void constraints() {
6.153 - checkConcept<MappableGraphComponent, Graph>();
6.154 -
6.155 - typedef typename Graph::template UEdgeMap<int> IntMap;
6.156 - checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
6.157 - IntMap >();
6.158 -
6.159 - typedef typename Graph::template UEdgeMap<bool> BoolMap;
6.160 - checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
6.161 - BoolMap >();
6.162 -
6.163 - typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
6.164 - checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
6.165 - DummyMap >();
6.166 - }
6.167 - };
6.168 -
6.169 - };
6.170 -
6.171 - struct ExtendableUGraphConcept {
6.172 -
6.173 - template <typename Graph>
6.174 - struct Constraints {
6.175 - void constraints() {
6.176 - node_a = graph.addNode();
6.177 - uedge = graph.addEdge(node_a, node_b);
6.178 - }
6.179 - typename Graph::Node node_a, node_b;
6.180 - typename Graph::UEdge uedge;
6.181 - Graph graph;
6.182 - };
6.183 -
6.184 - };
6.185 -
6.186 - struct ErasableUGraphConcept {
6.187 -
6.188 - template <typename Graph>
6.189 - struct Constraints {
6.190 - void constraints() {
6.191 - graph.erase(n);
6.192 - graph.erase(e);
6.193 - }
6.194 - Graph graph;
6.195 - typename Graph::Node n;
6.196 - typename Graph::UEdge e;
6.197 - };
6.198 -
6.199 - };
6.200 -
6.201 /// \addtogroup graph_concepts
6.202 /// @{
6.203
6.204 @@ -231,13 +46,13 @@
6.205 /// run properly, of couse.
6.206 ///
6.207 /// In LEMON undirected graphs also fulfill the concept of directed
6.208 - /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For
6.209 - /// explanation of this and more see also the page \ref ugraphs,
6.210 - /// a tutorial about undirected graphs.
6.211 + /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
6.212 + /// explanation of this and more see also the page \ref graphs,
6.213 + /// a tutorial about graphs.
6.214 ///
6.215 /// You can assume that all undirected graph can be handled
6.216 - /// as a static directed graph. This way it is fully conform
6.217 - /// to the StaticGraph concept.
6.218 + /// as a directed graph. This way it is fully conform
6.219 + /// to the Graph concept.
6.220
6.221 class UGraph {
6.222 public:
6.223 @@ -799,74 +614,23 @@
6.224 /// \brief Target node of the directed edge.
6.225 Node target(Edge) const { return INVALID; }
6.226
6.227 -// /// \brief First node of the graph
6.228 -// ///
6.229 -// /// \note This method is part of so called \ref
6.230 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.231 -// /// be used in an end-user program.
6.232 void first(Node&) const {}
6.233 -// /// \brief Next node of the graph
6.234 -// ///
6.235 -// /// \note This method is part of so called \ref
6.236 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.237 -// /// be used in an end-user program.
6.238 void next(Node&) const {}
6.239
6.240 -// /// \brief First undirected edge of the graph
6.241 -// ///
6.242 -// /// \note This method is part of so called \ref
6.243 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.244 -// /// be used in an end-user program.
6.245 void first(UEdge&) const {}
6.246 -// /// \brief Next undirected edge of the graph
6.247 -// ///
6.248 -// /// \note This method is part of so called \ref
6.249 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.250 -// /// be used in an end-user program.
6.251 void next(UEdge&) const {}
6.252
6.253 -// /// \brief First directed edge of the graph
6.254 -// ///
6.255 -// /// \note This method is part of so called \ref
6.256 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.257 -// /// be used in an end-user program.
6.258 void first(Edge&) const {}
6.259 -// /// \brief Next directed edge of the graph
6.260 -// ///
6.261 -// /// \note This method is part of so called \ref
6.262 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.263 -// /// be used in an end-user program.
6.264 void next(Edge&) const {}
6.265
6.266 -// /// \brief First outgoing edge from a given node
6.267 -// ///
6.268 -// /// \note This method is part of so called \ref
6.269 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.270 -// /// be used in an end-user program.
6.271 void firstOut(Edge&, Node) const {}
6.272 -// /// \brief Next outgoing edge to a node
6.273 -// ///
6.274 -// /// \note This method is part of so called \ref
6.275 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.276 -// /// be used in an end-user program.
6.277 void nextOut(Edge&) const {}
6.278
6.279 -// /// \brief First incoming edge to a given node
6.280 -// ///
6.281 -// /// \note This method is part of so called \ref
6.282 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.283 -// /// be used in an end-user program.
6.284 void firstIn(Edge&, Node) const {}
6.285 -// /// \brief Next incoming edge to a node
6.286 -// ///
6.287 -// /// \note This method is part of so called \ref
6.288 -// /// developpers_interface "Developpers' interface", so it shouldn't
6.289 -// /// be used in an end-user program.
6.290 void nextIn(Edge&) const {}
6.291
6.292
6.293 void firstInc(UEdge &, bool &, const Node &) const {}
6.294 -
6.295 void nextInc(UEdge &, bool &) const {}
6.296
6.297 /// \brief Base node of the iterator
6.298 @@ -922,74 +686,6 @@
6.299
6.300 };
6.301
6.302 - /// \brief An empty non-static undirected graph class.
6.303 - ///
6.304 - /// This class provides everything that \ref UGraph does.
6.305 - /// Additionally it enables building graphs from scratch.
6.306 - class ExtendableUGraph : public UGraph {
6.307 - public:
6.308 -
6.309 - /// \brief Add a new node to the graph.
6.310 - ///
6.311 - /// Add a new node to the graph.
6.312 - /// \return the new node.
6.313 - Node addNode();
6.314 -
6.315 - /// \brief Add a new undirected edge to the graph.
6.316 - ///
6.317 - /// Add a new undirected edge to the graph.
6.318 - /// \return the new edge.
6.319 - UEdge addEdge(const Node& from, const Node& to);
6.320 -
6.321 - /// \brief Resets the graph.
6.322 - ///
6.323 - /// This function deletes all undirected edges and nodes of the graph.
6.324 - /// It also frees the memory allocated to store them.
6.325 - void clear() { }
6.326 -
6.327 - template <typename Graph>
6.328 - struct Constraints {
6.329 - void constraints() {
6.330 - checkConcept<BaseIterableUGraphConcept, Graph>();
6.331 - checkConcept<IterableUGraphConcept, Graph>();
6.332 - checkConcept<MappableUGraphConcept, Graph>();
6.333 -
6.334 - checkConcept<UGraph, Graph>();
6.335 - checkConcept<ExtendableUGraphConcept, Graph>();
6.336 - checkConcept<ClearableGraphComponent, Graph>();
6.337 - }
6.338 - };
6.339 -
6.340 - };
6.341 -
6.342 - /// \brief An empty erasable undirected graph class.
6.343 - ///
6.344 - /// This class is an extension of \ref ExtendableUGraph. It makes it
6.345 - /// possible to erase undirected edges or nodes.
6.346 - class ErasableUGraph : public ExtendableUGraph {
6.347 - public:
6.348 -
6.349 - /// \brief Deletes a node.
6.350 - ///
6.351 - /// Deletes a node.
6.352 - ///
6.353 - void erase(Node) { }
6.354 - /// \brief Deletes an undirected edge.
6.355 - ///
6.356 - /// Deletes an undirected edge.
6.357 - ///
6.358 - void erase(UEdge) { }
6.359 -
6.360 - template <typename Graph>
6.361 - struct Constraints {
6.362 - void constraints() {
6.363 - checkConcept<ExtendableUGraph, Graph>();
6.364 - checkConcept<ErasableUGraphConcept, Graph>();
6.365 - }
6.366 - };
6.367 -
6.368 - };
6.369 -
6.370 /// @}
6.371
6.372 }
7.1 --- a/lemon/dag_shortest_path.h Mon Jun 26 15:40:35 2006 +0000
7.2 +++ b/lemon/dag_shortest_path.h Wed Jun 28 15:06:24 2006 +0000
7.3 @@ -274,7 +274,7 @@
7.4 /// is \ref ListGraph. The value of _Graph is not used directly by
7.5 /// DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
7.6 /// \param _LengthMap This read-only EdgeMap determines the lengths of the
7.7 - /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
7.8 + /// edges. The default map type is \ref concept::Graph::EdgeMap
7.9 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
7.10 /// by DagShortestPath, it is only passed to \ref DagShortestPathDefaultTraits.
7.11 /// \param _Traits Traits class to set various data types used by the
8.1 --- a/lemon/dijkstra.h Mon Jun 26 15:40:35 2006 +0000
8.2 +++ b/lemon/dijkstra.h Wed Jun 28 15:06:24 2006 +0000
8.3 @@ -157,7 +157,7 @@
8.4 ///edges. It is read once for each edge, so the map may involve in
8.5 ///relatively time consuming process to compute the edge length if
8.6 ///it is necessary. The default map type is \ref
8.7 - ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
8.8 + ///concept::Graph::EdgeMap "Graph::EdgeMap<int>". The value
8.9 ///of LM is not used directly by Dijkstra, it is only passed to \ref
8.10 ///DijkstraDefaultTraits. \param TR Traits class to set
8.11 ///various data types used by the algorithm. The default traits
9.1 --- a/lemon/edge_set.h Mon Jun 26 15:40:35 2006 +0000
9.2 +++ b/lemon/edge_set.h Wed Jun 28 15:06:24 2006 +0000
9.3 @@ -238,11 +238,11 @@
9.4 /// original graph.
9.5 ///
9.6 /// \param _Graph The type of the graph which shares its node set with
9.7 - /// this class. Its interface must conform to the \ref concept::StaticGraph
9.8 - /// "StaticGraph" concept.
9.9 + /// this class. Its interface must conform to the \ref concept::Graph
9.10 + /// "Graph" concept.
9.11 ///
9.12 /// In the edge extension and removing it conforms to the
9.13 - /// \ref concept::ErasableGraph "ErasableGraph" concept.
9.14 + /// \ref concept::Graph "Graph" concept.
9.15 template <typename _Graph>
9.16 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
9.17
9.18 @@ -330,11 +330,11 @@
9.19 /// original graph.
9.20 ///
9.21 /// \param _Graph The type of the graph which shares its node set with
9.22 - /// this class. Its interface must conform to the \ref concept::StaticGraph
9.23 - /// "StaticGraph" concept.
9.24 + /// this class. Its interface must conform to the \ref concept::Graph
9.25 + /// "Graph" concept.
9.26 ///
9.27 /// In the edge extension and removing it conforms to the
9.28 - /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
9.29 + /// \ref concept::UGraph "UGraph" concept.
9.30 template <typename _Graph>
9.31 class ListUEdgeSet
9.32 : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
9.33 @@ -567,11 +567,11 @@
9.34 /// original graph.
9.35 ///
9.36 /// \param _Graph The type of the graph which shares its node set with
9.37 - /// this class. Its interface must conform to the \ref concept::StaticGraph
9.38 - /// "StaticGraph" concept.
9.39 + /// this class. Its interface must conform to the \ref concept::Graph
9.40 + /// "Graph" concept.
9.41 ///
9.42 /// In the edge extension and removing it conforms to the
9.43 - /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
9.44 + /// \ref concept::Graph "Graph" concept.
9.45 template <typename _Graph>
9.46 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
9.47
9.48 @@ -662,11 +662,11 @@
9.49 /// original graph.
9.50 ///
9.51 /// \param _Graph The type of the graph which shares its node set with
9.52 - /// this class. Its interface must conform to the \ref concept::StaticGraph
9.53 - /// "StaticGraph" concept.
9.54 + /// this class. Its interface must conform to the \ref concept::Graph
9.55 + /// "Graph" concept.
9.56 ///
9.57 /// In the edge extension and removing it conforms to the
9.58 - /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
9.59 + /// \ref concept::UGraph "UGraph" concept.
9.60 template <typename _Graph>
9.61 class SmartUEdgeSet
9.62 : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
10.1 --- a/lemon/floyd_warshall.h Mon Jun 26 15:40:35 2006 +0000
10.2 +++ b/lemon/floyd_warshall.h Wed Jun 28 15:06:24 2006 +0000
10.3 @@ -171,7 +171,7 @@
10.4 /// edges. It is read once for each edge, so the map may involve in
10.5 /// relatively time consuming process to compute the edge length if
10.6 /// it is necessary. The default map type is \ref
10.7 - /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
10.8 + /// concept::Graph::EdgeMap "Graph::EdgeMap<int>". The value
10.9 /// of _LengthMap is not used directly by FloydWarshall, it is only passed
10.10 /// to \ref FloydWarshallDefaultTraits. \param _Traits Traits class to set
10.11 /// various data types used by the algorithm. The default traits
11.1 --- a/lemon/full_graph.h Mon Jun 26 15:40:35 2006 +0000
11.2 +++ b/lemon/full_graph.h Wed Jun 28 15:06:24 2006 +0000
11.3 @@ -214,8 +214,8 @@
11.4 /// It is completely static, so you can neither add nor delete either
11.5 /// edges or nodes.
11.6 /// Thus it conforms to
11.7 - /// the \ref concept::StaticGraph "StaticGraph" concept
11.8 - /// \sa concept::StaticGraph.
11.9 + /// the \ref concept::Graph "Graph" concept
11.10 + /// \sa concept::Graph.
11.11 ///
11.12 /// \sa FullGraphBase
11.13 /// \sa FullUGraph
12.1 --- a/lemon/graph_adaptor.h Mon Jun 26 15:40:35 2006 +0000
12.2 +++ b/lemon/graph_adaptor.h Wed Jun 28 15:06:24 2006 +0000
12.3 @@ -2424,7 +2424,7 @@
12.4 /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
12.5 ///
12.6 /// This graph adaptor is fully conform to the
12.7 - /// \ref concept::StaticGraph "StaticGraph" concept and
12.8 + /// \ref concept::Graph "Graph" concept and
12.9 /// contains some additional member functions and types. The
12.10 /// documentation of some member functions may be found just in the
12.11 /// SplitGraphAdaptorBase class.
13.1 --- a/lemon/hypercube_graph.h Mon Jun 26 15:40:35 2006 +0000
13.2 +++ b/lemon/hypercube_graph.h Wed Jun 28 15:06:24 2006 +0000
13.3 @@ -249,7 +249,7 @@
13.4 /// reasons. This way the maximal dimension of this implementation
13.5 /// is 26.
13.6 ///
13.7 - /// The graph type is fully conform to the \ref concept::StaticGraph
13.8 + /// The graph type is fully conform to the \ref concept::Graph
13.9 /// concept but it does not conform to the \ref concept::UGraph.
13.10 ///
13.11 /// \see HyperCubeGraphBase
14.1 --- a/lemon/johnson.h Mon Jun 26 15:40:35 2006 +0000
14.2 +++ b/lemon/johnson.h Wed Jun 28 15:06:24 2006 +0000
14.3 @@ -206,7 +206,7 @@
14.4 /// edges. It is read once for each edge, so the map may involve in
14.5 /// relatively time consuming process to compute the edge length if
14.6 /// it is necessary. The default map type is \ref
14.7 - /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
14.8 + /// concept::Graph::EdgeMap "Graph::EdgeMap<int>". The value
14.9 /// of _LengthMap is not used directly by Johnson, it is only passed
14.10 /// to \ref JohnsonDefaultTraits. \param _Traits Traits class to set
14.11 /// various data types used by the algorithm. The default traits
15.1 --- a/lemon/kruskal.h Mon Jun 26 15:40:35 2006 +0000
15.2 +++ b/lemon/kruskal.h Wed Jun 28 15:06:24 2006 +0000
15.3 @@ -44,7 +44,7 @@
15.4 /// Due to hard C++ hacking, it accepts various input and output types.
15.5 ///
15.6 /// \param g The graph the algorithm runs on.
15.7 - /// It can be either \ref concept::StaticGraph "directed" or
15.8 + /// It can be either \ref concept::Graph "directed" or
15.9 /// \ref concept::UGraph "undirected".
15.10 /// If the graph is directed, the algorithm consider it to be
15.11 /// undirected by disregarding the direction of the edges.
16.1 --- a/lemon/list_graph.h Mon Jun 26 15:40:35 2006 +0000
16.2 +++ b/lemon/list_graph.h Wed Jun 28 15:06:24 2006 +0000
16.3 @@ -274,7 +274,7 @@
16.4 }
16.5
16.6 protected:
16.7 - void _changeTarget(Edge e, Node n)
16.8 + void changeTarget(Edge e, Node n)
16.9 {
16.10 if(edges[e.id].next_in != -1)
16.11 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
16.12 @@ -289,7 +289,7 @@
16.13 edges[e.id].next_in = nodes[n.id].first_in;
16.14 nodes[n.id].first_in = e.id;
16.15 }
16.16 - void _changeSource(Edge e, Node n)
16.17 + void changeSource(Edge e, Node n)
16.18 {
16.19 if(edges[e.id].next_out != -1)
16.20 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
16.21 @@ -316,16 +316,32 @@
16.22
16.23 ///This is a simple and fast erasable graph implementation.
16.24 ///
16.25 - ///It conforms to the
16.26 - ///\ref concept::ErasableGraph "ErasableGraph" concept and
16.27 - ///it also provides several additional useful extra functionalities.
16.28 - ///\sa concept::ErasableGraph.
16.29 + ///It conforms to the \ref concept::Graph "Graph" concept and it
16.30 + ///also provides several additional useful extra functionalities.
16.31 + ///The most of the member functions and nested classes are
16.32 + ///documented only in the concept class.
16.33 + ///\sa concept::Graph.
16.34
16.35 class ListGraph : public ExtendedListGraphBase {
16.36 public:
16.37
16.38 typedef ExtendedListGraphBase Parent;
16.39
16.40 + ///Add a new node to the graph.
16.41 +
16.42 + /// \return the new node.
16.43 + ///
16.44 + Node addNode() { return Parent::addNode(); }
16.45 +
16.46 + ///Add a new edge to the graph.
16.47 +
16.48 + ///Add a new edge to the graph with source node \c s
16.49 + ///and target node \c t.
16.50 + ///\return the new edge.
16.51 + Edge addEdge(const Node& s, const Node& t) {
16.52 + return Parent::addEdge(s, t);
16.53 + }
16.54 +
16.55 /// Changes the target of \c e to \c n
16.56
16.57 /// Changes the target of \c e to \c n
16.58 @@ -334,7 +350,7 @@
16.59 ///referencing the changed edge remain
16.60 ///valid. However <tt>InEdge</tt>s are invalidated.
16.61 void changeTarget(Edge e, Node n) {
16.62 - _changeTarget(e,n);
16.63 + Parent::changeTarget(e,n);
16.64 }
16.65 /// Changes the source of \c e to \c n
16.66
16.67 @@ -344,7 +360,7 @@
16.68 ///referencing the changed edge remain
16.69 ///valid. However <tt>OutEdge</tt>s are invalidated.
16.70 void changeSource(Edge e, Node n) {
16.71 - _changeSource(e,n);
16.72 + Parent::changeSource(e,n);
16.73 }
16.74
16.75 /// Invert the direction of an edge.
16.76 @@ -354,12 +370,12 @@
16.77 ///valid. However <tt>OutEdge</tt>s and <tt>InEdge</tt>s are invalidated.
16.78 void reverseEdge(Edge e) {
16.79 Node t=target(e);
16.80 - _changeTarget(e,source(e));
16.81 - _changeSource(e,t);
16.82 + changeTarget(e,source(e));
16.83 + changeSource(e,t);
16.84 }
16.85
16.86 - ///Using this it is possible to avoid the superfluous memory
16.87 - ///allocation.
16.88 + /// \brief Using this it is possible to avoid the superfluous memory
16.89 + /// allocation.
16.90
16.91 ///Using this it is possible to avoid the superfluous memory
16.92 ///allocation: if you know that the graph you want to build will
16.93 @@ -367,8 +383,8 @@
16.94 ///space for this amount before starting to build the graph.
16.95 void reserveNode(int n) { nodes.reserve(n); };
16.96
16.97 - ///Using this it is possible to avoid the superfluous memory
16.98 - ///allocation.
16.99 + /// \brief Using this it is possible to avoid the superfluous memory
16.100 + /// allocation.
16.101
16.102 ///Using this it is possible to avoid the superfluous memory
16.103 ///allocation: see the \ref reserveNode function.
16.104 @@ -598,6 +614,20 @@
16.105 class ListUGraph : public ExtendedListUGraphBase {
16.106 public:
16.107 typedef ExtendedListUGraphBase Parent;
16.108 + /// \brief Add a new node to the graph.
16.109 + ///
16.110 + /// \return the new node.
16.111 + ///
16.112 + Node addNode() { return Parent::addNode(); }
16.113 +
16.114 + /// \brief Add a new edge to the graph.
16.115 + ///
16.116 + /// Add a new edge to the graph with source node \c s
16.117 + /// and target node \c t.
16.118 + /// \return the new undirected edge.
16.119 + UEdge addEdge(const Node& s, const Node& t) {
16.120 + return Parent::addEdge(s, t);
16.121 + }
16.122 /// \brief Changes the target of \c e to \c n
16.123 ///
16.124 /// Changes the target of \c e to \c n
16.125 @@ -606,7 +636,7 @@
16.126 /// referencing the changed edge remain
16.127 /// valid. However <tt>InEdge</tt>'s are invalidated.
16.128 void changeTarget(UEdge e, Node n) {
16.129 - _changeTarget(e,n);
16.130 + Parent::changeTarget(e,n);
16.131 }
16.132 /// Changes the source of \c e to \c n
16.133 ///
16.134 @@ -616,7 +646,7 @@
16.135 ///referencing the changed edge remain
16.136 ///valid. However <tt>OutEdge</tt>'s are invalidated.
16.137 void changeSource(UEdge e, Node n) {
16.138 - _changeSource(e,n);
16.139 + Parent::changeSource(e,n);
16.140 }
16.141 /// \brief Contract two nodes.
16.142 ///
17.1 --- a/lemon/min_cost_arborescence.h Mon Jun 26 15:40:35 2006 +0000
17.2 +++ b/lemon/min_cost_arborescence.h Wed Jun 28 15:06:24 2006 +0000
17.3 @@ -110,7 +110,7 @@
17.4 /// edges. It is read once for each edge, so the map may involve in
17.5 /// relatively time consuming process to compute the edge cost if
17.6 /// it is necessary. The default map type is \ref
17.7 - /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
17.8 + /// concept::Graph::EdgeMap "Graph::EdgeMap<int>". The value
17.9 /// of _CostMap is not used directly by MinCostArborescence,
17.10 /// it is only passed to \ref MinCostArborescenceDefaultTraits.
17.11 /// \param _Traits Traits class to set various data types used
18.1 --- a/lemon/min_cut.h Mon Jun 26 15:40:35 2006 +0000
18.2 +++ b/lemon/min_cut.h Wed Jun 28 15:06:24 2006 +0000
18.3 @@ -179,7 +179,7 @@
18.4 /// the edges. It is read once for each edge, so the map may involve in
18.5 /// relatively time consuming process to compute the edge capacity if
18.6 /// it is necessary. The default map type is \ref
18.7 - /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
18.8 + /// concept::Graph::EdgeMap "Graph::EdgeMap<int>". The value
18.9 /// of CapacityMap is not used directly by search algorithm, it is only
18.10 /// passed to \ref MaxCardinalitySearchDefaultTraits.
18.11 /// \param _Traits Traits class to set various data types used by the
18.12 @@ -701,7 +701,7 @@
18.13 /// The graph type the algorithm runs on.
18.14 typedef _Graph Graph;
18.15
18.16 - /// The AuxGraph type which is an ErasableGraph
18.17 + /// The AuxGraph type which is an Graph
18.18 typedef ListUGraph AuxGraph;
18.19
18.20 /// \brief Instantiates a AuxGraph.
19.1 --- a/lemon/smart_graph.h Mon Jun 26 15:40:35 2006 +0000
19.2 +++ b/lemon/smart_graph.h Wed Jun 28 15:06:24 2006 +0000
19.3 @@ -239,8 +239,8 @@
19.4 ///that <b> it does support only limited (only stack-like)
19.5 ///node and edge deletions</b>.
19.6 ///It conforms to
19.7 - ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
19.8 - ///\sa concept::ExtendableGraph.
19.9 + ///the \ref concept::Graph "Graph" concept.
19.10 + ///\sa concept::Graph.
19.11 ///
19.12 ///\author Alpar Juttner
19.13 class SmartGraph : public ExtendedSmartGraphBase {
20.1 --- a/lemon/topology.h Mon Jun 26 15:40:35 2006 +0000
20.2 +++ b/lemon/topology.h Wed Jun 28 15:06:24 2006 +0000
20.3 @@ -244,7 +244,7 @@
20.4 /// \note By definition, the empty graph is strongly connected.
20.5 template <typename Graph>
20.6 bool stronglyConnected(const Graph& graph) {
20.7 - checkConcept<concept::StaticGraph, Graph>();
20.8 + checkConcept<concept::Graph, Graph>();
20.9
20.10 typedef typename Graph::Node Node;
20.11 typedef typename Graph::NodeIt NodeIt;
20.12 @@ -302,7 +302,7 @@
20.13 /// strongly connected components.
20.14 template <typename Graph>
20.15 int countStronglyConnectedComponents(const Graph& graph) {
20.16 - checkConcept<concept::StaticGraph, Graph>();
20.17 + checkConcept<concept::Graph, Graph>();
20.18
20.19 using namespace _topology_bits;
20.20
20.21 @@ -371,7 +371,7 @@
20.22 ///
20.23 template <typename Graph, typename NodeMap>
20.24 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
20.25 - checkConcept<concept::StaticGraph, Graph>();
20.26 + checkConcept<concept::Graph, Graph>();
20.27 typedef typename Graph::Node Node;
20.28 typedef typename Graph::NodeIt NodeIt;
20.29 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
20.30 @@ -434,7 +434,7 @@
20.31 /// \return The number of cut edges
20.32 template <typename Graph, typename EdgeMap>
20.33 int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
20.34 - checkConcept<concept::StaticGraph, Graph>();
20.35 + checkConcept<concept::Graph, Graph>();
20.36 typedef typename Graph::Node Node;
20.37 typedef typename Graph::Edge Edge;
20.38 typedef typename Graph::NodeIt NodeIt;
20.39 @@ -1205,7 +1205,7 @@
20.40 void topologicalSort(const Graph& graph, NodeMap& order) {
20.41 using namespace _topology_bits;
20.42
20.43 - checkConcept<concept::StaticGraph, Graph>();
20.44 + checkConcept<concept::Graph, Graph>();
20.45 checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
20.46
20.47 typedef typename Graph::Node Node;
20.48 @@ -1247,7 +1247,7 @@
20.49 bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
20.50 using namespace _topology_bits;
20.51
20.52 - checkConcept<concept::StaticGraph, Graph>();
20.53 + checkConcept<concept::Graph, Graph>();
20.54 checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
20.55
20.56 typedef typename Graph::Node Node;
20.57 @@ -1290,7 +1290,7 @@
20.58 template <typename Graph>
20.59 bool dag(const Graph& graph) {
20.60
20.61 - checkConcept<concept::StaticGraph, Graph>();
20.62 + checkConcept<concept::Graph, Graph>();
20.63
20.64 typedef typename Graph::Node Node;
20.65 typedef typename Graph::NodeIt NodeIt;
21.1 --- a/test/bfs_test.cc Mon Jun 26 15:40:35 2006 +0000
21.2 +++ b/test/bfs_test.cc Wed Jun 28 15:06:24 2006 +0000
21.3 @@ -29,7 +29,7 @@
21.4
21.5 void check_Bfs_Compile()
21.6 {
21.7 - typedef concept::StaticGraph Graph;
21.8 + typedef concept::Graph Graph;
21.9
21.10 typedef Graph::Edge Edge;
21.11 typedef Graph::Node Node;
21.12 @@ -66,7 +66,7 @@
21.13 void check_Bfs_Function_Compile()
21.14 {
21.15 typedef int VType;
21.16 - typedef concept::StaticGraph Graph;
21.17 + typedef concept::Graph Graph;
21.18
21.19 typedef Graph::Edge Edge;
21.20 typedef Graph::Node Node;
22.1 --- a/test/dfs_test.cc Mon Jun 26 15:40:35 2006 +0000
22.2 +++ b/test/dfs_test.cc Wed Jun 28 15:06:24 2006 +0000
22.3 @@ -29,7 +29,7 @@
22.4
22.5 void check_Dfs_SmartGraph_Compile()
22.6 {
22.7 - typedef concept::StaticGraph Graph;
22.8 + typedef concept::Graph Graph;
22.9
22.10 typedef Graph::Edge Edge;
22.11 typedef Graph::Node Node;
22.12 @@ -67,7 +67,7 @@
22.13 void check_Dfs_Function_Compile()
22.14 {
22.15 typedef int VType;
22.16 - typedef concept::StaticGraph Graph;
22.17 + typedef concept::Graph Graph;
22.18
22.19 typedef Graph::Edge Edge;
22.20 typedef Graph::Node Node;
23.1 --- a/test/dijkstra_test.cc Mon Jun 26 15:40:35 2006 +0000
23.2 +++ b/test/dijkstra_test.cc Wed Jun 28 15:06:24 2006 +0000
23.3 @@ -31,7 +31,7 @@
23.4 void check_Dijkstra_BinHeap_Compile()
23.5 {
23.6 typedef int VType;
23.7 - typedef concept::StaticGraph Graph;
23.8 + typedef concept::Graph Graph;
23.9
23.10 typedef Graph::Edge Edge;
23.11 typedef Graph::Node Node;
23.12 @@ -70,7 +70,7 @@
23.13 void check_Dijkstra_Function_Compile()
23.14 {
23.15 typedef int VType;
23.16 - typedef concept::StaticGraph Graph;
23.17 + typedef concept::Graph Graph;
23.18
23.19 typedef Graph::Edge Edge;
23.20 typedef Graph::Node Node;
24.1 --- a/test/edge_set_test.cc Mon Jun 26 15:40:35 2006 +0000
24.2 +++ b/test/edge_set_test.cc Wed Jun 28 15:06:24 2006 +0000
24.3 @@ -17,14 +17,14 @@
24.4 using namespace lemon;
24.5 using namespace lemon::concept;
24.6
24.7 -typedef SmartGraph Graph;
24.8 +typedef SmartGraph RGraph;
24.9
24.10 int main() {
24.11 { // checking edge_sets
24.12 - checkConcept<StaticGraph, ListEdgeSet<Graph> >();
24.13 - checkConcept<UGraph, ListUEdgeSet<Graph> >();
24.14 - checkConcept<StaticGraph, SmartEdgeSet<Graph> >();
24.15 - checkConcept<UGraph, SmartUEdgeSet<Graph> >();
24.16 + checkConcept<Graph, ListEdgeSet<RGraph> >();
24.17 + checkConcept<UGraph, ListUEdgeSet<RGraph> >();
24.18 + checkConcept<Graph, SmartEdgeSet<RGraph> >();
24.19 + checkConcept<UGraph, SmartUEdgeSet<RGraph> >();
24.20 }
24.21
24.22 std::cout << __FILE__ ": All tests passed.\n";
25.1 --- a/test/graph_adaptor_test.cc Mon Jun 26 15:40:35 2006 +0000
25.2 +++ b/test/graph_adaptor_test.cc Wed Jun 28 15:06:24 2006 +0000
25.3 @@ -46,22 +46,22 @@
25.4 int main()
25.5 {
25.6 {
25.7 - typedef StaticGraph Graph;
25.8 - checkConcept<StaticGraph, GraphAdaptor<Graph> >();
25.9 + typedef Graph Graph;
25.10 + checkConcept<Graph, GraphAdaptor<Graph> >();
25.11
25.12 - checkConcept<StaticGraph, RevGraphAdaptor<Graph> >();
25.13 + checkConcept<Graph, RevGraphAdaptor<Graph> >();
25.14
25.15 - checkConcept<StaticGraph, SubGraphAdaptor<Graph,
25.16 + checkConcept<Graph, SubGraphAdaptor<Graph,
25.17 Graph::NodeMap<bool> , Graph::EdgeMap<bool> > >();
25.18 - checkConcept<StaticGraph, NodeSubGraphAdaptor<Graph,
25.19 + checkConcept<Graph, NodeSubGraphAdaptor<Graph,
25.20 Graph::NodeMap<bool> > >();
25.21 - checkConcept<StaticGraph, EdgeSubGraphAdaptor<Graph,
25.22 + checkConcept<Graph, EdgeSubGraphAdaptor<Graph,
25.23 Graph::EdgeMap<bool> > >();
25.24
25.25 - checkConcept<StaticGraph, ResGraphAdaptor<Graph, int,
25.26 + checkConcept<Graph, ResGraphAdaptor<Graph, int,
25.27 Graph::EdgeMap<int>, Graph::EdgeMap<int> > >();
25.28
25.29 - checkConcept<StaticGraph, ErasingFirstGraphAdaptor<Graph,
25.30 + checkConcept<Graph, ErasingFirstGraphAdaptor<Graph,
25.31 Graph::NodeMap<Graph::Edge> > >();
25.32
25.33 checkConcept<UGraph, UndirGraphAdaptor<Graph> >();
25.34 @@ -73,7 +73,7 @@
25.35 checkConcept<UGraph, EdgeSubUGraphAdaptor<UGraph,
25.36 UGraph::UEdgeMap<bool> > >();
25.37
25.38 - checkConcept<StaticGraph, DirUGraphAdaptor<UGraph,
25.39 + checkConcept<Graph, DirUGraphAdaptor<UGraph,
25.40 UGraph::UEdgeMap<bool> > >();
25.41 }
25.42 std::cout << __FILE__ ": All tests passed.\n";
26.1 --- a/test/graph_factory_test.cc Mon Jun 26 15:40:35 2006 +0000
26.2 +++ b/test/graph_factory_test.cc Wed Jun 28 15:06:24 2006 +0000
26.3 @@ -70,20 +70,20 @@
26.4 }
26.5
26.6 //Compile Graph
26.7 -template void lemon::concept::checkCompileStaticGraph<concept::StaticGraph>
26.8 -(concept::StaticGraph &);
26.9 +template void lemon::concept::checkCompileGraph<concept::Graph>
26.10 +(concept::Graph &);
26.11
26.12 template
26.13 -void lemon::concept::checkCompileExtendableGraph<concept::ExtendableGraph>
26.14 -(concept::ExtendableGraph &);
26.15 +void lemon::concept::checkCompileGraph<concept::Graph>
26.16 +(concept::Graph &);
26.17
26.18 template
26.19 -void lemon::concept::checkCompileErasableGraph<concept::ErasableGraph>
26.20 -(concept::ErasableGraph &);
26.21 +void lemon::concept::checkCompileGraph<concept::Graph>
26.22 +(concept::Graph &);
26.23
26.24 //Compile SmartGraph
26.25 template
26.26 -void lemon::concept::checkCompileExtendableGraph<SmartGraph>(SmartGraph &);
26.27 +void lemon::concept::checkCompileGraph<SmartGraph>(SmartGraph &);
26.28 template
26.29 void lemon::concept::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
26.30
26.31 @@ -93,20 +93,20 @@
26.32
26.33 //Compile ListGraph
26.34 template
26.35 -void lemon::concept::checkCompileExtendableGraph<ListGraph>(ListGraph &);
26.36 +void lemon::concept::checkCompileGraph<ListGraph>(ListGraph &);
26.37 template
26.38 -void lemon::concept::checkCompileErasableGraph<ListGraph>(ListGraph &);
26.39 +void lemon::concept::checkCompileGraph<ListGraph>(ListGraph &);
26.40 template
26.41 void lemon::concept::checkCompileGraphFindEdge<ListGraph>(ListGraph &);
26.42
26.43
26.44 //Compile SymListGraph
26.45 //template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
26.46 -//template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
26.47 +//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
26.48 //template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
26.49
26.50 //Compile FullGraph
26.51 -template void lemon::concept::checkCompileStaticGraph<FullGraph>(FullGraph &);
26.52 +template void lemon::concept::checkCompileGraph<FullGraph>(FullGraph &);
26.53 template
26.54 void lemon::concept::checkCompileGraphFindEdge<FullGraph>(FullGraph &);
26.55
27.1 --- a/test/graph_test.cc Mon Jun 26 15:40:35 2006 +0000
27.2 +++ b/test/graph_test.cc Wed Jun 28 15:06:24 2006 +0000
27.3 @@ -43,41 +43,33 @@
27.4 checkConcept<IDableGraphComponent, IDableGraphComponent >();
27.5 checkConcept<MaxIDableGraphComponent, MaxIDableGraphComponent >();
27.6
27.7 - checkConcept<BaseExtendableGraphComponent, BaseExtendableGraphComponent >();
27.8 - checkConcept<BaseErasableGraphComponent, BaseErasableGraphComponent >();
27.9 -
27.10 checkConcept<IterableGraphComponent, IterableGraphComponent >();
27.11
27.12 checkConcept<MappableGraphComponent, MappableGraphComponent >();
27.13
27.14 - checkConcept<ExtendableGraphComponent, ExtendableGraphComponent >();
27.15 - checkConcept<ErasableGraphComponent, ErasableGraphComponent >();
27.16 - checkConcept<ClearableGraphComponent, ClearableGraphComponent >();
27.17 }
27.18 { // checking skeleton graphs
27.19 - checkConcept<StaticGraph, StaticGraph >();
27.20 - checkConcept<ExtendableGraph, ExtendableGraph >();
27.21 - checkConcept<ErasableGraph, ErasableGraph >();
27.22 + checkConcept<Graph, Graph >();
27.23 }
27.24 { // checking list graph
27.25 - checkConcept<ErasableGraph, ListGraph >();
27.26 + checkConcept<Graph, ListGraph >();
27.27
27.28 checkGraph<ListGraph>();
27.29 checkGraphNodeMap<ListGraph>();
27.30 checkGraphEdgeMap<ListGraph>();
27.31 }
27.32 { // checking smart graph
27.33 - checkConcept<ExtendableGraph, SmartGraph >();
27.34 + checkConcept<Graph, SmartGraph >();
27.35
27.36 checkGraph<SmartGraph>();
27.37 checkGraphNodeMap<SmartGraph>();
27.38 checkGraphEdgeMap<SmartGraph>();
27.39 }
27.40 { // checking full graph
27.41 - checkConcept<StaticGraph, FullGraph >();
27.42 + checkConcept<Graph, FullGraph >();
27.43 }
27.44 { // checking full graph
27.45 - checkConcept<StaticGraph, HyperCubeGraph >();
27.46 + checkConcept<Graph, HyperCubeGraph >();
27.47 }
27.48
27.49 std::cout << __FILE__ ": All tests passed.\n";
28.1 --- a/test/kruskal_test.cc Mon Jun 26 15:40:35 2006 +0000
28.2 +++ b/test/kruskal_test.cc Wed Jun 28 15:06:24 2006 +0000
28.3 @@ -32,10 +32,10 @@
28.4
28.5 void checkCompileKruskal()
28.6 {
28.7 - concept::WriteMap<concept::StaticGraph::Edge,bool> w;
28.8 + concept::WriteMap<concept::Graph::Edge,bool> w;
28.9
28.10 - kruskal(concept::StaticGraph(),
28.11 - concept::ReadMap<concept::StaticGraph::Edge,int>(),
28.12 + kruskal(concept::Graph(),
28.13 + concept::ReadMap<concept::Graph::Edge,int>(),
28.14 w);
28.15 }
28.16
29.1 --- a/test/preflow_test.cc Mon Jun 26 15:40:35 2006 +0000
29.2 +++ b/test/preflow_test.cc Wed Jun 28 15:06:24 2006 +0000
29.3 @@ -31,7 +31,7 @@
29.4 void check_Preflow()
29.5 {
29.6 typedef int VType;
29.7 - typedef concept::StaticGraph Graph;
29.8 + typedef concept::Graph Graph;
29.9
29.10 typedef Graph::Node Node;
29.11 typedef Graph::Edge Edge;
30.1 --- a/test/ugraph_test.cc Mon Jun 26 15:40:35 2006 +0000
30.2 +++ b/test/ugraph_test.cc Wed Jun 28 15:06:24 2006 +0000
30.3 @@ -33,10 +33,8 @@
30.4
30.5 void check_concepts() {
30.6 checkConcept<UGraph, ListUGraph>();
30.7 - checkConcept<ErasableUGraph, ListUGraph>();
30.8
30.9 checkConcept<UGraph, SmartUGraph>();
30.10 - checkConcept<ExtendableUGraph, SmartUGraph>();
30.11
30.12 checkConcept<UGraph, FullUGraph>();
30.13