# HG changeset patch
# User deba
# Date 1128334673 0
# Node ID 4c593a4096dab1961cdb42a0463e1d9afa6b6c27
# Parent 4e03a355d2eaa82b3e2c9afa379ef4b9ee193450
Preliminary SplitGraphAdaptor
And some other improvments
diff -r 4e03a355d2ea -r 4c593a4096da lemon/graph_adaptor.h
--- a/lemon/graph_adaptor.h Mon Oct 03 10:16:45 2005 +0000
+++ b/lemon/graph_adaptor.h Mon Oct 03 10:17:53 2005 +0000
@@ -65,8 +65,6 @@
class GraphAdaptorBase {
public:
typedef _Graph Graph;
- /// \todo Is it needed?
- typedef Graph BaseGraph;
typedef Graph ParentGraph;
protected:
@@ -93,12 +91,25 @@
Node source(const Edge& e) const { return graph->source(e); }
Node target(const Edge& e) const { return graph->target(e); }
+ typedef NodeNumTagIndicator<Graph> NodeNumTag;
int nodeNum() const { return graph->nodeNum(); }
+
+ typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
int edgeNum() const { return graph->edgeNum(); }
+
+ typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+ Edge findEdge(const Node& source, const Node& target,
+ const Edge& prev = INVALID) {
+ return graph->findEdge(source, target, prev);
+ }
- Node addNode() const { return Node(graph->addNode()); }
+ Node addNode() const {
+ return Node(graph->addNode());
+ }
+
Edge addEdge(const Node& source, const Node& target) const {
- return Edge(graph->addEdge(source, target)); }
+ return Edge(graph->addEdge(source, target));
+ }
void erase(const Node& i) const { graph->erase(i); }
void erase(const Edge& i) const { graph->erase(i); }
@@ -156,11 +167,9 @@
typedef typename Parent::Node Node;
typedef typename Parent::Edge Edge;
- // using Parent::first;
void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
- // using Parent::next;
void nextIn(Edge& i) const { Parent::nextOut(i); }
void nextOut(Edge& i) const { Parent::nextIn(i); }
@@ -304,25 +313,8 @@
/// Returns true if \c n is hidden.
bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
- /// \warning This is a linear time operation and works only if s
- /// \c Graph::NodeIt is defined.
- /// \todo assign tags.
- int nodeNum() const {
- int i=0;
- Node n;
- for (first(n); n!=INVALID; next(n)) ++i;
- return i;
- }
-
- /// \warning This is a linear time operation and works only if
- /// \c Graph::EdgeIt is defined.
- /// \todo assign tags.
- int edgeNum() const {
- int i=0;
- Edge e;
- for (first(e); e!=INVALID; next(e)) ++i;
- return i;
- }
+ typedef False NodeNumTag;
+ typedef False EdgeNumTag;
};
template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
@@ -413,25 +405,8 @@
/// Returns true if \c n is hidden.
bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
- /// \warning This is a linear time operation and works only if s
- /// \c Graph::NodeIt is defined.
- /// \todo assign tags.
- int nodeNum() const {
- int i=0;
- Node n;
- for (first(n); n!=INVALID; next(n)) ++i;
- return i;
- }
-
- /// \warning This is a linear time operation and works only if
- /// \c Graph::EdgeIt is defined.
- /// \todo assign tags.
- int edgeNum() const {
- int i=0;
- Edge e;
- for (first(e); e!=INVALID; next(e)) ++i;
- return i;
- }
+ typedef False NodeNumTag;
+ typedef False EdgeNumTag;
};
/*! \brief A graph adaptor for hiding nodes and edges from a graph.
@@ -440,7 +415,8 @@
parts of the lib. Use them at you own risk.
SubGraphAdaptor shows the graph with filtered node-set and
- edge-set.
+ edge-set. If the \c checked parameter is true then it filters the edgeset
+ to do not get invalid edges without source or target.
Let \f$G=(V, A)\f$ be a directed graph
and suppose that the graph instance \c g of type ListGraph implements
\f$G\f$.
@@ -453,10 +429,11 @@
SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
only on edges leaving and entering a specific node which have true value.
- We have to note that this does not mean that an
- induced subgraph is obtained, the node-iterator cares only the filter
- on the node-set, and the edge-iterators care only the filter on the
- edge-set.
+ If the \c checked template parameter is false then we have to note that
+ the node-iterator cares only the filter on the node-set, and the
+ edge-iterator cares only the filter on the edge-set. This way the edge-map
+ should filter all edges which's source or target is filtered by the
+ node-filter.
\code
typedef ListGraph Graph;
Graph g;
@@ -519,8 +496,9 @@
An adaptor for hiding nodes from a graph.
This adaptor specializes SubGraphAdaptor in the way that only the node-set
- can be filtered. Note that this does not mean of considering induced
- subgraph, the edge-iterators consider the original edge-set.
+ can be filtered. In usual case the checked parameter is true, we get the
+ induced subgraph. But if the checked parameter is false then we can only
+ filter only isolated nodes.
\author Marton Makai
*/
template<typename Graph, typename NodeFilterMap, bool checked = true>
@@ -703,9 +681,6 @@
typedef typename Parent::UndirEdge UndirEdge;
typedef typename Parent::Edge Edge;
- /// \bug Why cant an edge say that it is forward or not???
- /// By this, a pointer to the graph have to be stored
- /// The implementation
template <typename T>
class EdgeMap {
protected:
@@ -1122,7 +1097,6 @@
int edgeNum() const {
return 2*this->graph->edgeNum();
}
- // KEEP_MAPS(Parent, BidirGraphAdaptor);
};
@@ -1331,6 +1305,371 @@
};
template <typename _Graph>
+ class SplitGraphAdaptorBase
+ : public GraphAdaptorBase<_Graph> {
+ public:
+ typedef GraphAdaptorBase<_Graph> Parent;
+
+ class Node;
+ class Edge;
+ template <typename T> class NodeMap;
+ template <typename T> class EdgeMap;
+
+
+ class Node : public Parent::Node {
+ friend class SplitGraphAdaptorBase;
+ template <typename T> friend class NodeMap;
+ typedef typename Parent::Node NodeParent;
+ private:
+
+ bool entry;
+ Node(typename Parent::Node _node, bool _entry)
+ : Parent::Node(_node), entry(_entry) {}
+
+ public:
+ Node() {}
+ Node(Invalid) : NodeParent(INVALID), entry(true) {}
+
+ bool operator==(const Node& node) const {
+ return NodeParent::operator==(node) && entry == node.entry;
+ }
+
+ bool operator!=(const Node& node) const {
+ return !(*this == node);
+ }
+
+ bool operator<(const Node& node) const {
+ return NodeParent::operator<(node) ||
+ (NodeParent::operator==(node) && entry < node.entry);
+ }
+ };
+
+ /// \todo May we want VARIANT/union type
+ class Edge : public Parent::Edge {
+ friend class SplitGraphAdaptorBase;
+ template <typename T> friend class EdgeMap;
+ private:
+ typedef typename Parent::Edge EdgeParent;
+ typedef typename Parent::Node NodeParent;
+ NodeParent bind;
+
+ Edge(const EdgeParent& edge, const NodeParent& node)
+ : EdgeParent(edge), bind(node) {}
+ public:
+ Edge() {}
+ Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
+
+ bool operator==(const Edge& edge) const {
+ return EdgeParent::operator==(edge) && bind == edge.bind;
+ }
+
+ bool operator!=(const Edge& edge) const {
+ return !(*this == edge);
+ }
+
+ bool operator<(const Edge& edge) const {
+ return EdgeParent::operator<(edge) ||
+ (EdgeParent::operator==(edge) && bind < edge.bind);
+ }
+ };
+
+ void first(Node& node) const {
+ Parent::first(node);
+ node.entry = true;
+ }
+
+ void next(Node& node) const {
+ if (node.entry) {
+ node.entry = false;
+ } else {
+ node.entry = true;
+ Parent::next(node);
+ }
+ }
+
+ void first(Edge& edge) const {
+ Parent::first(edge);
+ if ((typename Parent::Edge&)edge == INVALID) {
+ Parent::first(edge.bind);
+ } else {
+ edge.bind = INVALID;
+ }
+ }
+
+ void next(Edge& edge) const {
+ if ((typename Parent::Edge&)edge != INVALID) {
+ Parent::next(edge);
+ if ((typename Parent::Edge&)edge == INVALID) {
+ Parent::first(edge.bind);
+ }
+ } else {
+ Parent::next(edge.bind);
+ }
+ }
+
+ void firstIn(Edge& edge, const Node& node) const {
+ if (node.entry) {
+ Parent::firstIn(edge, node);
+ edge.bind = INVALID;
+ } else {
+ (typename Parent::Edge&)edge = INVALID;
+ edge.bind = node;
+ }
+ }
+
+ void nextIn(Edge& edge) const {
+ if ((typename Parent::Edge&)edge != INVALID) {
+ Parent::nextIn(edge);
+ } else {
+ edge.bind = INVALID;
+ }
+ }
+
+ void firstOut(Edge& edge, const Node& node) const {
+ if (!node.entry) {
+ Parent::firstOut(edge, node);
+ edge.bind = INVALID;
+ } else {
+ (typename Parent::Edge&)edge = INVALID;
+ edge.bind = node;
+ }
+ }
+
+ void nextOut(Edge& edge) const {
+ if ((typename Parent::Edge&)edge != INVALID) {
+ Parent::nextOut(edge);
+ } else {
+ edge.bind = INVALID;
+ }
+ }
+
+ Node source(const Edge& edge) const {
+ if ((typename Parent::Edge&)edge != INVALID) {
+ return Node(Parent::source(edge), false);
+ } else {
+ return Node(edge.bind, true);
+ }
+ }
+
+ Node target(const Edge& edge) const {
+ if ((typename Parent::Edge&)edge != INVALID) {
+ return Node(Parent::target(edge), true);
+ } else {
+ return Node(edge.bind, false);
+ }
+ }
+
+ static bool entryNode(const Node& node) {
+ return node.entry;
+ }
+
+ static bool exitNode(const Node& node) {
+ return !node.entry;
+ }
+
+ static Node getEntry(const typename Parent::Node& node) {
+ return Node(node, true);
+ }
+
+ static Node getExit(const typename Parent::Node& node) {
+ return Node(node, false);
+ }
+
+ static bool originalEdge(const Edge& edge) {
+ return (typename Parent::Edge&)edge != INVALID;
+ }
+
+ static bool bindingEdge(const Edge& edge) {
+ return edge.bind != INVALID;
+ }
+
+ static Node getBindedNode(const Edge& edge) {
+ return edge.bind;
+ }
+
+ int nodeNum() const {
+ return Parent::nodeNum() * 2;
+ }
+
+ typedef CompileTimeAnd<typename Parent::NodeNumTag,
+ typename Parent::EdgeNumTag> EdgeNumTag;
+
+ int edgeNum() const {
+ return Parent::edgeNum() + Parent::nodeNum();
+ }
+
+ Edge findEdge(const Node& source, const Node& target,
+ const Edge& prev = INVALID) const {
+ if (exitNode(source) && entryNode(target)) {
+ return Parent::findEdge(source, target, prev);
+ } else {
+ if (prev == INVALID && entryNode(source) && exitNode(target) &&
+ (typename Parent::Node&)source == (typename Parent::Node&)target) {
+ return Edge(INVALID, source);
+ } else {
+ return INVALID;
+ }
+ }
+ }
+
+ template <typename T>
+ class NodeMap : public MapBase<Node, T> {
+ typedef typename Parent::template NodeMap<T> NodeImpl;
+ public:
+ NodeMap(const SplitGraphAdaptorBase& _graph)
+ : entry(_graph), exit(_graph) {}
+ NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
+ : entry(_graph, t), exit(_graph, t) {}
+
+ void set(const Node& key, const T& val) {
+ if (key.entry) { entry.set(key, val); }
+ else {exit.set(key, val); }
+ }
+
+ typename ReferenceMapTraits<NodeImpl>::Reference
+ operator[](const Node& key) {
+ if (key.entry) { return entry[key]; }
+ else { return exit[key]; }
+ }
+
+ T operator[](const Node& key) const {
+ if (key.entry) { return entry[key]; }
+ else { return exit[key]; }
+ }
+
+ private:
+ NodeImpl entry, exit;
+ };
+
+ template <typename T>
+ class EdgeMap : public MapBase<Edge, T> {
+ typedef typename Parent::template NodeMap<T> NodeImpl;
+ typedef typename Parent::template EdgeMap<T> EdgeImpl;
+ public:
+ EdgeMap(const SplitGraphAdaptorBase& _graph)
+ : bind(_graph), orig(_graph) {}
+ EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
+ : bind(_graph, t), orig(_graph, t) {}
+
+ void set(const Edge& key, const T& val) {
+ if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
+ else {bind.set(key.bind, val); }
+ }
+
+ typename ReferenceMapTraits<EdgeImpl>::Reference
+ operator[](const Edge& key) {
+ if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
+ else {return bind[key.bind]; }
+ }
+
+ T operator[](const Edge& key) const {
+ if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
+ else {return bind[key.bind]; }
+ }
+
+ private:
+ typename Parent::template NodeMap<T> bind;
+ typename Parent::template EdgeMap<T> orig;
+ };
+
+ template <typename EntryMap, typename ExitMap>
+ class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
+ public:
+ typedef MapBase<Node, typename EntryMap::Value> Parent;
+
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
+ : entryMap(_entryMap), exitMap(_exitMap) {}
+
+ Value& operator[](const Key& key) {
+ if (key.entry) {
+ return entryMap[key];
+ } else {
+ return exitMap[key];
+ }
+ }
+
+ Value operator[](const Key& key) const {
+ if (key.entry) {
+ return entryMap[key];
+ } else {
+ return exitMap[key];
+ }
+ }
+
+ void set(const Key& key, const Value& value) {
+ if (key.entry) {
+ entryMap.set(key, value);
+ } else {
+ exitMap.set(key, value);
+ }
+ }
+
+ private:
+
+ EntryMap& entryMap;
+ ExitMap& exitMap;
+
+ };
+
+ template <typename EdgeMap, typename NodeMap>
+ class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
+ public:
+ typedef MapBase<Edge, typename EdgeMap::Value> Parent;
+
+ typedef typename Parent::Key Key;
+ typedef typename Parent::Value Value;
+
+ CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
+ : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
+
+ void set(const Edge& edge, const Value& val) {
+ if (SplitGraphAdaptorBase::originalEdge(edge)) {
+ edgeMap.set(edge, val);
+ } else {
+ nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
+ }
+ }
+
+ Value operator[](const Key& edge) const {
+ if (SplitGraphAdaptorBase::originalEdge(edge)) {
+ return edgeMap[edge];
+ } else {
+ return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
+ }
+ }
+
+ Value& operator[](const Key& edge) {
+ if (SplitGraphAdaptorBase::originalEdge(edge)) {
+ return edgeMap[edge];
+ } else {
+ return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
+ }
+ }
+
+ private:
+ EdgeMap& edgeMap;
+ NodeMap& nodeMap;
+ };
+
+ };
+
+ template <typename _Graph>
+ class SplitGraphAdaptor
+ : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
+ public:
+ typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
+
+ SplitGraphAdaptor(_Graph& graph) {
+ Parent::setGraph(graph);
+ }
+
+
+ };
+
+ template <typename _Graph>
class NewEdgeSetAdaptorBase {
public: