# HG changeset patch
# User klao
# Date 1099605891 0
# Node ID 289d80c33f04b70a1ed3fa3f95daf59eed864d8e
# Parent 908a1a6f0752748cab01ac97ff121bf840b779c3
* Somewhat less redundant and a bit more correct graph concepts.
* graph_wrapper_test does not compile
diff -r 908a1a6f0752 -r 289d80c33f04 src/lemon/concept/graph.h
--- a/src/lemon/concept/graph.h Thu Nov 04 21:28:55 2004 +0000
+++ b/src/lemon/concept/graph.h Thu Nov 04 22:04:51 2004 +0000
@@ -765,26 +765,6 @@
/************* New GraphBase stuff **************/
- /// \bug The nodes and edges are not allowed to inherit from the
- /// same baseclass.
-
- class BaseGraphItem {
- public:
- BaseGraphItem() {}
- BaseGraphItem(Invalid) {}
-
- // We explicitely list these:
- BaseGraphItem(BaseGraphItem const&) {}
- BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
-
- bool operator==(BaseGraphItem) const { return false; }
- bool operator!=(BaseGraphItem) const { return false; }
-
- // Technical requirement. Do we really need this?
- bool operator<(BaseGraphItem) const { return false; }
- };
-
-
/// A minimal GraphBase concept
/// This class describes a minimal concept which can be extended to a
@@ -794,11 +774,14 @@
GraphBase() {}
+ /// \bug Should we demand that Node and Edge be subclasses of the
+ /// Graph class???
- /// \bug Nodes and Edges are comparable each other
-
- class Node : public BaseGraphItem {};
- class Edge : public BaseGraphItem {};
+ typedef GraphItem<'n'> Node;
+ typedef GraphItem<'e'> Edge;
+
+// class Node : public BaseGraphItem<'n'> {};
+// class Edge : public BaseGraphItem<'e'> {};
// Graph operation
void firstNode(Node &n) const { }
@@ -840,27 +823,13 @@
- /**************** Concept checking classes ****************/
- template<typename BGI>
- struct BaseGraphItemConcept {
- void constraints() {
- BGI i1;
- BGI i2 = i1;
- BGI i3 = INVALID;
-
- i1 = i3;
- if( i1 == i3 ) {
- if ( i2 != i3 && i3 < i2 )
- return;
- }
- }
- };
+ /**************** The full-featured graph concepts ****************/
-
class StaticGraph
- : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
+ : virtual public BaseGraphComponent,
+ public IterableGraphComponent, public MappableGraphComponent {
public:
typedef BaseGraphComponent::Node Node;
typedef BaseGraphComponent::Edge Edge;
@@ -869,15 +838,14 @@
template <typename Graph>
struct StaticGraphConcept {
void constraints() {
- function_requires<BaseGraphComponentConcept<Graph> >();
function_requires<IterableGraphComponentConcept<Graph> >();
function_requires<MappableGraphComponentConcept<Graph> >();
}
- Graph& graph;
};
class ExtendableGraph
- : virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
+ : virtual public BaseGraphComponent, public StaticGraph,
+ public ExtendableGraphComponent, public ClearableGraphComponent {
public:
typedef BaseGraphComponent::Node Node;
typedef BaseGraphComponent::Edge Edge;
@@ -890,11 +858,11 @@
function_requires<ExtendableGraphComponentConcept<Graph> >();
function_requires<ClearableGraphComponentConcept<Graph> >();
}
- Graph& graph;
};
class ErasableGraph
- : virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
+ : virtual public BaseGraphComponent, public ExtendableGraph,
+ public ErasableGraphComponent {
public:
typedef BaseGraphComponent::Node Node;
typedef BaseGraphComponent::Edge Edge;
@@ -906,7 +874,6 @@
function_requires<ExtendableGraphConcept<Graph> >();
function_requires<ErasableGraphComponentConcept<Graph> >();
}
- Graph& graph;
};
// @}
diff -r 908a1a6f0752 -r 289d80c33f04 src/lemon/concept/graph_component.h
--- a/src/lemon/concept/graph_component.h Thu Nov 04 21:28:55 2004 +0000
+++ b/src/lemon/concept/graph_component.h Thu Nov 04 22:04:51 2004 +0000
@@ -28,10 +28,107 @@
namespace lemon {
namespace concept {
+
+ /**************** Graph iterator concepts ****************/
+
+ /// Skeleton class for graph Node and Edge
+
+ /// \note Because Node and Edge are forbidden to inherit from the same
+ /// base class, this is a template. For Node you shoul instantiate it
+ /// with character 'n' and for Edge with 'e'.
+
+ template<char Ch>
+ class GraphItem {
+ public:
+ GraphItem() {}
+ GraphItem(Invalid) {}
+
+ // We explicitely list these:
+ GraphItem(GraphItem const&) {}
+ GraphItem& operator=(GraphItem const&) { return *this; }
+
+ bool operator==(GraphItem) const { return false; }
+ bool operator!=(GraphItem) const { return false; }
+
+ // Technical requirement. Do we really need this?
+ bool operator<(GraphItem) const { return false; }
+ };
+
+
+ template<typename GI>
+ struct GraphItemConcept {
+ void constraints() {
+ GI i1;
+ GI i2 = i1;
+ GI i3 = INVALID;
+
+ i1 = i2 = i3;
+
+ bool b;
+ b = (ia == ib) && (ia != ib) && (ia < ib);
+ b = (ia == INVALID) && (ib != INVALID);
+ }
+
+ const GI &ia;
+ const GI &ib;
+ };
+
+
+ template<typename Iter, typename Graph, typename BaseItem>
+ struct GraphIteratorConcept {
+ void constraints() {
+ function_requires< GraphItemConcept<Iter> >();
+ Iter it1(g);
+
+ /// \todo Do we need NodeIt(Node) kind of constructor?
+ // Iter it2(bj);
+ Iter it2;
+
+ it2 = ++it1;
+ ++it2 = it1;
+ ++(++it1);
+ /// \bug This should be: is_base_and_derived<BaseItem, Iter>
+ BaseItem bi = it1;
+ bi = it2;
+ }
+
+ BaseItem bj;
+ Graph g;
+ };
+
+ template<typename Iter, typename Graph>
+ struct GraphIncIteratorConcept {
+ typedef typename Graph::Node Node;
+ typedef typename Graph::Edge Edge;
+ void constraints() {
+ function_requires< GraphItemConcept<Iter> >();
+ Iter it1(graph, node);
+ /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
+ // Iter it2(edge);
+ Iter it2;
+
+ it2 = ++it1;
+ ++it2 = it1;
+ ++(++it1);
+ Edge e = it1;
+ e = it2;
+ }
+
+ Edge edge;
+ Node node;
+ Graph graph;
+ };
+
+
+
/// An empty base graph class.
- /// This class provides the most minimal features of a graph structure.
- /// All the graph concepts have to be conform to this base graph.
+ /// This class provides the minimal set of features needed for a graph
+ /// structure. All graph concepts have to be conform to this base
+ /// graph.
+ ///
+ /// \bug This is not true. The minimal graph concept is the
+ /// BaseIterableGraphComponent.
class BaseGraphComponent {
public:
@@ -70,14 +167,14 @@
/// Two iterators are equal if and only if they represents the
/// same node in the graph or both are invalid.
- bool operator==(const Node&) { return true;}
+ bool operator==(const Node&) const { return true;}
/// Inequality operator.
/// \sa operator==(const Node& n)
///
- bool operator!=(const Node&) { return true;}
+ bool operator!=(const Node&) const { return true;}
/// Comparison operator.
@@ -85,7 +182,7 @@
///
/// This ordering can be different from the iterating order of nodes.
/// \todo Possibly we don't need it.
- bool operator<(const Node&) { return true;}
+ bool operator<(const Node&) const { return true;}
};
/// Edge class of the graph.
@@ -120,14 +217,14 @@
/// Two iterators are equal if and only if they represents the
/// same edge in the graph or both are invalid.
- bool operator==(const Edge&) { return true;}
+ bool operator==(const Edge&) const { return true;}
/// Inequality operator.
/// \sa operator==(const Edge& n)
///
- bool operator!=(const Edge&) { return true;}
+ bool operator!=(const Edge&) const { return true;}
/// Comparison operator.
@@ -135,7 +232,7 @@
///
/// This ordering can be different from the iterating order of edges.
/// \todo Possibly we don't need it.
- bool operator<(const Edge&) { return true;}
+ bool operator<(const Edge&) const { return true;}
};
///Gives back the head node of an edge.
@@ -151,6 +248,7 @@
Node tail(const Edge&) const { return INVALID;}
};
+
/// Concept check structure for BaseGraph.
/// Concept check structure for BaseGraph.
@@ -162,24 +260,8 @@
typedef typename Graph::Edge Edge;
void constraints() {
- {
- Node ni;
- Node nj(ni);
- Node nk(INVALID);
- ni = nj;
- bool b; b = true;
- b = (ni == INVALID); b = (ni != INVALID);
- b = (ni==nj); b = (ni != nj); b=( ni < nj);
- }
- {
- Edge ei;
- Edge ej(ei);
- Edge ek(INVALID);
- ei = ej;
- bool b; b = true;
- b = (ei == INVALID); b = (ei != INVALID);
- b = (ei==ej); b = (ei != ej); b=( ei < ej);
- }
+ function_requires< GraphItemConcept<Node> >();
+ function_requires< GraphItemConcept<Edge> >();
{
const Graph& const_graph = graph;
Node n;
@@ -262,29 +344,29 @@
template <typename Graph>
struct BaseIterableGraphComponentConcept {
- void constraints() {
- const Graph& const_graph = graph;
+ void constraints() {
+ function_requires< BaseGraphComponentConcept<Graph> >();
typename Graph::Node node;
typename Graph::Edge edge;
{
- const_graph.first(node);
- const_graph.next(node);
+ graph.first(node);
+ graph.next(node);
}
{
- const_graph.first(edge);
- const_graph.next(edge);
+ graph.first(edge);
+ graph.next(edge);
}
{
- const_graph.firstIn(edge, node);
- const_graph.nextIn(edge);
+ graph.firstIn(edge, node);
+ graph.nextIn(edge);
}
{
- const_graph.firstOut(edge, node);
- const_graph.nextOut(edge);
+ graph.firstOut(edge, node);
+ graph.nextOut(edge);
}
}
- Graph& graph;
+ const Graph& graph;
};
/// An empty idable base graph class.
@@ -322,16 +404,16 @@
struct IDableGraphComponentConcept {
void constraints() {
- const Graph& const_graph = graph;
+ function_requires< BaseGraphComponentConcept<Graph> >();
typename Graph::Node node;
- int nid = const_graph.id(node);
- nid = const_graph.id(node);
+ int nid = graph.id(node);
+ nid = graph.id(node);
typename Graph::Edge edge;
- int eid = const_graph.id(edge);
- eid = const_graph.id(edge);
+ int eid = graph.id(edge);
+ eid = graph.id(edge);
}
- Graph& graph;
+ const Graph& graph;
};
@@ -365,14 +447,14 @@
struct MaxIDableGraphComponentConcept {
void constraints() {
- const Graph& const_graph = graph;
- int nid = const_graph.maxEdgeId();
+ function_requires< BaseGraphComponentConcept<Graph> >();
+ int nid = graph.maxEdgeId();
ignore_unused_variable_warning(nid);
- int eid = const_graph.maxNodeId();
+ int eid = graph.maxNodeId();
ignore_unused_variable_warning(eid);
}
- Graph& graph;
+ const Graph& graph;
};
/// An empty extendable base graph class.
@@ -411,6 +493,7 @@
template <typename Graph>
struct BaseExtendableGraphComponentConcept {
void constraints() {
+ function_requires< BaseGraphComponentConcept<Graph> >();
typename Graph::Node node_a, node_b;
node_a = graph.addNode();
typename Graph::Edge edge;
@@ -452,6 +535,7 @@
template <typename Graph>
struct BaseErasableGraphComponentConcept {
void constraints() {
+ function_requires< BaseGraphComponentConcept<Graph> >();
typename Graph::Node node;
graph.erase(node);
typename Graph::Edge edge;
@@ -483,6 +567,7 @@
template <typename Graph>
struct BaseClearableGraphComponentConcept {
void constraints() {
+ function_requires< BaseGraphComponentConcept<Graph> >();
graph.clear();
}
@@ -490,7 +575,8 @@
};
- class IterableGraphComponent : virtual public BaseGraphComponent {
+ class IterableGraphComponent :
+ virtual public BaseIterableGraphComponent {
public:
@@ -503,52 +589,56 @@
public:
NodeIt() {}
NodeIt(Invalid) {}
- NodeIt(const Graph&) {}
+ // explicit NodeIt(Node) {}
+ explicit NodeIt(const Graph&) {}
NodeIt& operator++() { return *this; }
// Node operator*() const { return INVALID; }
- bool operator==(const NodeIt&) { return true;}
- bool operator!=(const NodeIt&) { return true;}
+ bool operator==(const NodeIt&) const { return true;}
+ bool operator!=(const NodeIt&) const { return true;}
};
class EdgeIt : public Edge {
public:
EdgeIt() {}
EdgeIt(Invalid) {}
- EdgeIt(const Graph&) {}
+ // explicit EdgeIt(Edge) {}
+ explicit EdgeIt(const Graph&) {}
EdgeIt& operator++() { return *this; }
// Edge operator*() const { return INVALID; }
- bool operator==(const EdgeIt&) { return true;}
- bool operator!=(const EdgeIt&) { return true;}
+ bool operator==(const EdgeIt&) const { return true;}
+ bool operator!=(const EdgeIt&) const { return true;}
};
class InEdgeIt : public Edge {
public:
InEdgeIt() {}
InEdgeIt(Invalid) {}
- InEdgeIt(const Graph&, const Node&) {}
+ // explicit InEdgeIt(Edge) {}
+ explicit InEdgeIt(const Graph&, const Node&) {}
InEdgeIt& operator++() { return *this; }
// Edge operator*() const { return INVALID; }
- bool operator==(const InEdgeIt&) { return true;}
- bool operator!=(const InEdgeIt&) { return true;}
+ bool operator==(const InEdgeIt&) const { return true;}
+ bool operator!=(const InEdgeIt&) const { return true;}
};
class OutEdgeIt : public Edge {
public:
OutEdgeIt() {}
OutEdgeIt(Invalid) {}
- OutEdgeIt(const Graph&, const Node&) {}
+ // explicit OutEdgeIt(Edge) {}
+ explicit OutEdgeIt(const Graph&, const Node&) {}
OutEdgeIt& operator++() { return *this; }
// Edge operator*() const { return INVALID; }
- bool operator==(const OutEdgeIt&) { return true;}
- bool operator!=(const OutEdgeIt&) { return true;}
+ bool operator==(const OutEdgeIt&) const { return true;}
+ bool operator!=(const OutEdgeIt&) const { return true;}
};
};
@@ -557,7 +647,8 @@
struct IterableGraphComponentConcept {
void constraints() {
-
+ function_requires< BaseIterableGraphComponentConcept<Graph> >();
+
typedef typename Graph::Node Node;
typedef typename Graph::NodeIt NodeIt;
typedef typename Graph::Edge Edge;
@@ -565,68 +656,10 @@
typedef typename Graph::InEdgeIt InEdgeIt;
typedef typename Graph::OutEdgeIt OutEdgeIt;
- {
- NodeIt it;
- NodeIt jt(it);
- NodeIt kt(INVALID);
- NodeIt lt(graph);
- it = jt;
- jt = ++it;
- bool b;
- b = (it == INVALID);
- b = (it != INVALID);
- b = (it == jt);
- b = (it != jt);
- Node node = it;
- node = it;
- }
- {
- EdgeIt it;
- EdgeIt jt(it);
- EdgeIt kt(INVALID);
- EdgeIt lt(graph);
- it = jt;
- jt = ++it;
- bool b;
- b = (it == INVALID);
- b = (it != INVALID);
- b = (it == jt);
- b = (it != jt);
- Edge edge = it;
- edge = it;
- }
- {
- InEdgeIt it;
- InEdgeIt jt(it);
- InEdgeIt kt(INVALID);
- Node node;
- InEdgeIt lt(graph, node);
- it = jt;
- jt = ++it;
- bool b;
- b = (it == INVALID);
- b = (it != INVALID);
- b = (it == jt);
- b = (it != jt);
- Edge edge = it;
- edge = it;
- }
- {
- OutEdgeIt it;
- OutEdgeIt jt(it);
- OutEdgeIt kt(INVALID);
- Node node;
- OutEdgeIt lt(graph, node);
- it = jt;
- jt = ++it;
- bool b;
- b = (it == INVALID);
- b = (it != INVALID);
- b = (it == jt);
- b = (it != jt);
- Edge edge = it;
- edge = it;
- }
+ function_requires< GraphIteratorConcept<NodeIt, Graph, Node> >();
+ function_requires< GraphIteratorConcept<EdgeIt, Graph, Edge> >();
+ function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
+ function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
}
Graph& graph;
};
@@ -636,11 +669,11 @@
typedef IdMappableGraphComponent Graph;
+ public:
+
typedef BaseGraphComponent::Node Node;
typedef BaseGraphComponent::Edge Edge;
- public:
-
class NodeIdMap : public ReadMap<Node, int> {
public:
NodeIdMap(const Graph&) {}
@@ -658,6 +691,7 @@
template <typename Graph>
struct IdMappableGraphComponentConcept {
void constraints() {
+ function_requires< BaseGraphComponentConcept<Graph> >();
{
typedef typename Graph::EdgeIdMap EdgeIdMap;
function_requires<ReadMapConcept<EdgeIdMap> >();
@@ -719,6 +753,7 @@
};
void constraints() {
+ function_requires< BaseGraphComponentConcept<Graph> >();
{ // int map test
typedef typename Graph::template NodeMap<int> IntNodeMap;
function_requires<GraphMapConcept<IntNodeMap,Graph> >();
@@ -767,6 +802,7 @@
template <typename Graph>
struct ExtendableGraphComponentConcept {
void constraints() {
+ function_requires< BaseGraphComponentConcept<Graph> >();
typename Graph::Node node_a, node_b;
node_a = graph.addNode();
typename Graph::Edge edge;
@@ -791,6 +827,7 @@
template <typename Graph>
struct ErasableGraphComponentConcept {
void constraints() {
+ function_requires< BaseGraphComponentConcept<Graph> >();
typename Graph::Node node;
graph.erase(node);
typename Graph::Edge edge;
@@ -815,6 +852,7 @@
template <typename Graph>
struct ClearableGraphComponentConcept {
void constraints() {
+ function_requires< BaseGraphComponentConcept<Graph> >();
graph.clear();
}
Graph& graph;
diff -r 908a1a6f0752 -r 289d80c33f04 src/test/Makefile.am
--- a/src/test/Makefile.am Thu Nov 04 21:28:55 2004 +0000
+++ b/src/test/Makefile.am Thu Nov 04 22:04:51 2004 +0000
@@ -17,7 +17,6 @@
graph_utils_test \
kruskal_test \
min_cost_flow_test \
- new_graph_test \
suurballe_test \
path_test \
preflow_test \
@@ -25,7 +24,6 @@
test_tools_pass \
time_measure_test \
unionfind_test \
- graph_wrapper_test \
xy_test
TESTS = $(check_PROGRAMS)
@@ -39,7 +37,6 @@
graph_wrapper_test_SOURCES = graph_wrapper_test.cc
kruskal_test_SOURCES = kruskal_test.cc
min_cost_flow_test_SOURCES = min_cost_flow_test.cc
-new_graph_test_SOURCES = new_graph_test.cc
suurballe_test_SOURCES = suurballe_test.cc
path_test_SOURCES = path_test.cc
preflow_test_SOURCES = preflow_test.cc
diff -r 908a1a6f0752 -r 289d80c33f04 src/test/new_graph_test.cc
--- a/src/test/new_graph_test.cc Thu Nov 04 21:28:55 2004 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-/* -*- C++ -*-
- * src/test/new_graph_test.cc - Part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Combinatorial Optimization Research Group, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#include <lemon/concept/graph.h>
-// #include <boost/concept_check.hpp>
-
-using namespace lemon::concept;
-
-// Borrowed from boost:
-template <class T> inline void ignore_unused_variable_warning(const T&) { }
-
-int main()
-{
- // This is the "right" way to check a concept:
- // boost::function_requires< BaseGraphItemConcept<BaseGraphItem> >();
-
- // which is equivalent (considering compile-time checks) to
- // BaseGraphItemConcept<BaseGraphItem> bgic;
- // bgic.constraints();
- // but not actually call or intatiates anything...
- // It's doing aproximately this:
- typedef BaseGraphItemConcept<BaseGraphItem> CC;
- void (CC::*x)() = &CC::constraints;
- ignore_unused_variable_warning(x);
- // But even more hackish...
-}