# HG changeset patch
# User alpar
# Date 1078940874 0
# Node ID 970b265696b0eb3dc0df3458e628dc18378a8d7c
# Parent  c5fbd2c1d75f99786f6c49b338f908242af81365
New graph interface

diff -r c5fbd2c1d75f -r 970b265696b0 src/work/alpar/smart_graph.h
--- a/src/work/alpar/smart_graph.h	Wed Mar 10 16:46:17 2004 +0000
+++ b/src/work/alpar/smart_graph.h	Wed Mar 10 17:47:54 2004 +0000
@@ -6,7 +6,7 @@
 #include <vector>
 #include <limits.h>
 
-struct _Invalid {} Invalid;
+#include <invalid.h>
 
 namespace hugo {
 
@@ -46,27 +46,27 @@
     template <typename T> class DynEdgeMap;
     template <typename T> class DynEdgeMap;
 
-    class NodeIt;
-    class EdgeIt;
+    class Node;
+    class Edge;
 
   protected:
-    mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
-    mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
+    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
+    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
     
   public:
 
-    class EachNodeIt;
-    class EachEdgeIt;
+    class NodeIt;
+    class EdgeIt;
     class OutEdgeIt;
     class InEdgeIt;
     
-    //     class NodeIt { int n; };
-    //     class EachNodeIt : public NodeIt { };
-    //     class EdgeIt { int n; };
-    //     class EachEdgeIt : public EdgeIt {};
-    //     class OutEdgeIt : public EdgeIt {};
-    //     class InEdgeIt : public EdgeIt {};
-    //     class SymEdgeIt;
+    //     class Node { int n; };
+    //     class NodeIt : public Node { };
+    //     class Edge { int n; };
+    //     class EdgeIt : public Edge {};
+    //     class OutEdgeIt : public Edge {};
+    //     class InEdgeIt : public Edge {};
+    //     class SymEdge;
     
     template <typename T> class NodeMap;
     template <typename T> class EdgeMap;
@@ -80,9 +80,9 @@
     
     ~SmartGraph()
     {
-      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
+      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
-      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
+      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
     }
 
@@ -93,24 +93,24 @@
     int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
 
     
-    NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
-    NodeIt head(EdgeIt e) const { return edges[e.n].head; }
+    Node tail(Edge e) const { return edges[e.n].tail; }
+    Node head(Edge e) const { return edges[e.n].head; }
 
-//     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
-//     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
-//     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
+//     Node aNode(const OutEdgeIt& e) const { return tail(e); }
+//     Node aNode(const InEdgeIt& e) const { return head(e); }
+//     //Node aNode(const SymEdge& e) const { return e.aNode(); }
 
-//     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
-//     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
-//     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
+//     Node bNode(const OutEdgeIt& e) const { return head(e); }
+//     Node bNode(const InEdgeIt& e) const { return tail(e); }
+//     //Node bNode(const SymEdge& e) const { return e.bNode(); }
 
-    EachNodeIt& getFirst(EachNodeIt& v) const { 
-      v=EachNodeIt(*this); return v; }
-    EachEdgeIt& getFirst(EachEdgeIt& e) const { 
-      e=EachEdgeIt(*this); return e; }
-    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const { 
+    NodeIt& first(NodeIt& v) const { 
+      v=NodeIt(*this); return v; }
+    EdgeIt& first(EdgeIt& e) const { 
+      e=EdgeIt(*this); return e; }
+    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
       e=OutEdgeIt(*this,v); return e; }
-    InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const { 
+    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
       e=InEdgeIt(*this,v); return e; }
 
     template< typename It >
@@ -121,51 +121,51 @@
     }
 
     template< typename It >
-    It first(NodeIt v) const { 
+    It first(Node v) const { 
       It e;
       getFirst(e, v);
       return e; 
     }
 
-    bool valid(EdgeIt e) const { return e.n!=-1; }
-    //    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
-    bool valid(NodeIt n) const { return n.n!=-1; }
+    bool valid(Edge e) const { return e.n!=-1; }
+    //    bool valid(EdgeIt e) const { return e.n<int(edges.size()); }
+    bool valid(Node n) const { return n.n!=-1; }
     
-    void setInvalid(EdgeIt &e) { e.n=-1; }
-    void setInvalid(NodeIt &n) { n.n=-1; }
+    void setInvalid(Edge &e) { e.n=-1; }
+    void setInvalid(Node &n) { n.n=-1; }
     
     template <typename It> It getNext(It it) const
     { It tmp(it); return next(tmp); }
     //{ It tmp; tmp.n=it.n+1; return tmp; }
 
-    NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
+    Node& next(Node& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
     OutEdgeIt& next(OutEdgeIt& it) const
     { it.n=edges[it.n].next_out; return it; }
     InEdgeIt& next(InEdgeIt& it) const
     { it.n=edges[it.n].next_in; return it; }
-    EachEdgeIt& next(EachEdgeIt& it) const { --it.n; return it; }
+    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
 
-    int id(NodeIt v) const { return v.n; }
-    int id(EdgeIt e) const { return e.n; }
+    int id(Node v) const { return v.n; }
+    int id(Edge e) const { return e.n; }
 
-    NodeIt addNode() {
-      NodeIt n; n.n=nodes.size();
+    Node addNode() {
+      Node n; n.n=nodes.size();
       nodes.push_back(NodeT()); //FIXME: Hmmm...
 
-      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
+      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
 	  i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
 
       return n;
     }
     
-    EdgeIt addEdge(NodeIt u, NodeIt v) {
-      EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
+    Edge addEdge(Node u, Node v) {
+      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
       edges[e.n].tail=u.n; edges[e.n].head=v.n;
       edges[e.n].next_out=nodes[u.n].first_out;
       edges[e.n].next_in=nodes[v.n].first_in;
       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
 
-      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
+      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
 
       return e;
@@ -173,79 +173,79 @@
 
     void clear() {nodes.clear();edges.clear();}
 
-    class NodeIt {
+    class Node {
       friend class SmartGraph;
       template <typename T> friend class NodeMap;
       template <typename T> friend class DynNodeMap;
       
-      friend class EdgeIt;
+      friend class Edge;
       friend class OutEdgeIt;
       friend class InEdgeIt;
-      friend class SymEdgeIt;
+      friend class SymEdge;
 
     protected:
       int n;
-      friend int SmartGraph::id(NodeIt v) const; 
-      NodeIt(int nn) {n=nn;}
+      friend int SmartGraph::id(Node v) const; 
+      Node(int nn) {n=nn;}
     public:
-      NodeIt() {}
-      NodeIt (_Invalid i) { n=-1; }
-      bool operator==(const NodeIt i) const {return n==i.n;}
-      bool operator!=(const NodeIt i) const {return n!=i.n;}
-      bool operator<(const NodeIt i) const {return n<i.n;}
+      Node() {}
+      Node (Invalid i) { n=-1; }
+      bool operator==(const Node i) const {return n==i.n;}
+      bool operator!=(const Node i) const {return n!=i.n;}
+      bool operator<(const Node i) const {return n<i.n;}
     };
     
-    class EachNodeIt : public NodeIt {
+    class NodeIt : public Node {
       friend class SmartGraph;
     public:
-      EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }
-      EachNodeIt() : NodeIt() { }
+      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
+      NodeIt() : Node() { }
     };
 
-    class EdgeIt {
+    class Edge {
       friend class SmartGraph;
       template <typename T> friend class EdgeMap;
       template <typename T> friend class DynEdgeMap;
       
+      friend class Node;
       friend class NodeIt;
-      friend class EachNodeIt;
     protected:
       int n;
-      friend int SmartGraph::id(EdgeIt e) const;
+      friend int SmartGraph::id(Edge e) const;
 
-      EdgeIt(int nn) {n=nn;}
+      Edge(int nn) {n=nn;}
     public:
-      EdgeIt() { }
-      EdgeIt (_Invalid i) { n=-1; }
-      bool operator==(const EdgeIt i) const {return n==i.n;}
-      bool operator!=(const EdgeIt i) const {return n!=i.n;}
-      bool operator<(const EdgeIt i) const {return n<i.n;}
+      Edge() { }
+      Edge (Invalid i) { n=-1; }
+      bool operator==(const Edge i) const {return n==i.n;}
+      bool operator!=(const Edge i) const {return n!=i.n;}
+      bool operator<(const Edge i) const {return n<i.n;}
     };
     
-    class EachEdgeIt : public EdgeIt {
+    class EdgeIt : public Edge {
       friend class SmartGraph;
     public:
-      EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }
-      EachEdgeIt (_Invalid i) : EdgeIt(i) { }
-      EachEdgeIt() : EdgeIt() { }
+      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
+      EdgeIt (Invalid i) : Edge(i) { }
+      EdgeIt() : Edge() { }
     };
     
-    class OutEdgeIt : public EdgeIt {
+    class OutEdgeIt : public Edge {
       friend class SmartGraph;
     public: 
-      OutEdgeIt() : EdgeIt() { }
-      OutEdgeIt (_Invalid i) : EdgeIt(i) { }
+      OutEdgeIt() : Edge() { }
+      OutEdgeIt (Invalid i) : Edge(i) { }
 
-      OutEdgeIt(const SmartGraph& G,const NodeIt v)
-	: EdgeIt(G.nodes[v.n].first_out) {}
+      OutEdgeIt(const SmartGraph& G,const Node v)
+	: Edge(G.nodes[v.n].first_out) {}
     };
     
-    class InEdgeIt : public EdgeIt {
+    class InEdgeIt : public Edge {
       friend class SmartGraph;
     public: 
-      InEdgeIt() : EdgeIt() { }
-      InEdgeIt (_Invalid i) : EdgeIt(i) { }
-      InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
+      InEdgeIt() : Edge() { }
+      InEdgeIt (Invalid i) : Edge(i) { }
+      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
     };
 
     // Map types
@@ -256,14 +256,14 @@
       std::vector<T> container;
     public:
       typedef T ValueType;
-      typedef NodeIt KeyType;
+      typedef Node KeyType;
       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
       NodeMap(const SmartGraph& _G, T a) : 
 	G(_G), container(G.maxNodeId(), a) { }
-      void set(NodeIt n, T a) { container[n.n]=a; }
-      T get(NodeIt n) const { return container[n.n]; }
-      T& operator[](NodeIt n) { return container[n.n]; }
-      const T& operator[](NodeIt n) const { return container[n.n]; }
+      void set(Node n, T a) { container[n.n]=a; }
+      T get(Node n) const { return container[n.n]; }
+      T& operator[](Node n) { return container[n.n]; }
+      const T& operator[](Node n) const { return container[n.n]; }
       void update() { container.resize(G.maxNodeId()); }
       void update(T a) { container.resize(G.maxNodeId(), a); }
     };
@@ -274,28 +274,28 @@
       std::vector<T> container;
     public:
       typedef T ValueType;
-      typedef EdgeIt KeyType;
+      typedef Edge KeyType;
       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
       EdgeMap(const SmartGraph& _G, T a) : 
 	G(_G), container(G.maxEdgeId(), a) { }
-      void set(EdgeIt e, T a) { container[e.n]=a; }
-      T get(EdgeIt e) const { return container[e.n]; }
-      T& operator[](EdgeIt e) { return container[e.n]; } 
-      const T& operator[](EdgeIt e) const { return container[e.n]; } 
+      void set(Edge e, T a) { container[e.n]=a; }
+      T get(Edge e) const { return container[e.n]; }
+      T& operator[](Edge e) { return container[e.n]; } 
+      const T& operator[](Edge e) const { return container[e.n]; } 
       void update() { container.resize(G.maxEdgeId()); }
       void update(T a) { container.resize(G.maxEdgeId(), a); }
     };
 
-    template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
+    template <typename T> class DynNodeMap : public DynMapBase<Node>
     {
       std::vector<T> container;
 
     public:
       typedef T ValueType;
-      typedef NodeIt KeyType;
+      typedef Node KeyType;
 
       DynNodeMap(const SmartGraph &_G) :
-	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
+	DynMapBase<Node>(_G), container(_G.maxNodeId())
       {
 	//FIXME: What if there are empty Id's?
 	//FIXME: Can I use 'this' in a constructor?
@@ -304,7 +304,7 @@
       ~DynNodeMap()
       {
 	if(G) {
-	  std::vector<DynMapBase<NodeIt>* >::iterator i;
+	  std::vector<DynMapBase<Node>* >::iterator i;
 	  for(i=G->dyn_node_maps.begin();
 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
@@ -316,38 +316,38 @@
 	}
       }
 
-      void add(const NodeIt k) 
+      void add(const Node k) 
       {
 	if(k.n>=container.size()) container.resize(k.n+1);
       }
-//       void erase(const NodeIt k)
+//       void erase(const Node k)
 //       {
 // 	//FIXME: Please implement me.
 //       }
-//       void erase(const EdgeIt k)
+//       void erase(const Edge k)
 //       {
 // 	//FIXME: Please implement me.
 //       }
       
-      void set(NodeIt n, T a) { container[n.n]=a; }
-      T get(NodeIt n) const { return container[n.n]; }
-      T& operator[](NodeIt n) { return container[n.n]; }
-      const T& operator[](NodeIt n) const { return container[n.n]; }
+      void set(Node n, T a) { container[n.n]=a; }
+      T get(Node n) const { return container[n.n]; }
+      T& operator[](Node n) { return container[n.n]; }
+      const T& operator[](Node n) const { return container[n.n]; }
 
       void update() {}    //Useless for DynMaps
       void update(T a) {}  //Useless for DynMaps
     };
     
-    template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
+    template <typename T> class DynEdgeMap : public DynMapBase<Edge>
     {
       std::vector<T> container;
 
     public:
       typedef T ValueType;
-      typedef EdgeIt KeyType;
+      typedef Edge KeyType;
 
       DynEdgeMap(const SmartGraph &_G) :
-	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
+	DynMapBase<Edge>(_G), container(_G.maxEdgeId())
       {
 	//FIXME: What if there are empty Id's?
 	//FIXME: Can I use 'this' in a constructor?
@@ -356,7 +356,7 @@
       ~DynEdgeMap()
       {
 	if(G) {
-	  std::vector<DynMapBase<EdgeIt>* >::iterator i;
+	  std::vector<DynMapBase<Edge>* >::iterator i;
 	  for(i=G->dyn_edge_maps.begin();
 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
@@ -368,19 +368,19 @@
 	}
       }
       
-      void add(const EdgeIt k) 
+      void add(const Edge k) 
       {
 	if(k.n>=int(container.size())) container.resize(k.n+1);
       }
-      void erase(const EdgeIt k)
+      void erase(const Edge k)
       {
 	//FIXME: Please implement me.
       }
       
-      void set(EdgeIt n, T a) { container[n.n]=a; }
-      T get(EdgeIt n) const { return container[n.n]; }
-      T& operator[](EdgeIt n) { return container[n.n]; }
-      const T& operator[](EdgeIt n) const { return container[n.n]; }
+      void set(Edge n, T a) { container[n.n]=a; }
+      T get(Edge n) const { return container[n.n]; }
+      T& operator[](Edge n) { return container[n.n]; }
+      const T& operator[](Edge n) const { return container[n.n]; }
 
       void update() {}    //Useless for DynMaps
       void update(T a) {}  //Useless for DynMaps
diff -r c5fbd2c1d75f -r 970b265696b0 src/work/alpar/smart_graph_demo.cc
--- a/src/work/alpar/smart_graph_demo.cc	Wed Mar 10 16:46:17 2004 +0000
+++ b/src/work/alpar/smart_graph_demo.cc	Wed Mar 10 17:47:54 2004 +0000
@@ -1,36 +1,67 @@
 #include<smart_graph.h>
+#include<emptygraph.h>
 
 #include <iostream>
+#include <vector>
 
 using namespace hugo;
 
-SmartGraph::OutEdgeIt safeFirstOut(const SmartGraph &G, SmartGraph::NodeIt n)
+//typedef SmartGraph Graph;
+typedef EmptyGraph Graph;
+
+
+Graph::OutEdgeIt safeFirstOut(const Graph &G, Graph::Node n)
 {
-  return G.valid(n) ? SmartGraph::OutEdgeIt(G,n):Invalid;
+  return G.valid(n) ? Graph::OutEdgeIt(G,n):INVALID;
 }
 
 int main()
 {
 
-  typedef SmartGraph::EdgeIt EdgeIt;
-  typedef SmartGraph::InEdgeIt InEdgeIt;
-  typedef SmartGraph::OutEdgeIt OutEdgeIt;
-  typedef SmartGraph::EachEdgeIt EachEdgeIt;
-  typedef SmartGraph::NodeIt NodeIt;
-  typedef SmartGraph::EachNodeIt EachNodeIt;
+  typedef Graph::Edge Edge;
+  typedef Graph::InEdgeIt InEdgeIt;
+  typedef Graph::OutEdgeIt OutEdgeIt;
+  typedef Graph::EdgeIt EdgeIt;
+  typedef Graph::Node Node;
+  typedef Graph::NodeIt NodeIt;
   
-  SmartGraph G;
-  EachNodeIt n;
+  Graph G;
+  NodeIt n;
 
 
-  //  std::cout.form("%s: %d\n","Sztring",15);
-
   for(int i=0;i<10;i++) G.addNode();
-  for(G.getFirst(n);G.valid(n);G.next(n)) 
-    for(EachNodeIt m(G);m!=Invalid;G.next(m)) 
+  for(G.first(n);G.valid(n);G.next(n)) 
+    for(NodeIt m(G);m!=INVALID;G.next(m)) 
       if(n!=m) G.addEdge(n,m);
 
   OutEdgeIt e = safeFirstOut(G,n);
-  OutEdgeIt f = safeFirstOut(G,EachNodeIt(G));
+  OutEdgeIt f = safeFirstOut(G,NodeIt(G));
+  
+
+  InEdgeIt i(INVALID), j;
+  InEdgeIt ii(i);
+  ii=G.first(i,n);
+  ii=G.next(i);
+  
+  OutEdgeIt o(INVALID), oo;
+  OutEdgeIt ooo(oo);
+  oo=G.first(o,n);
+  oo=G.next(o);
+  
+  EdgeIt ei(INVALID), eie;
+  EdgeIt eiee(ei);
+  eie=G.first(ei);
+  eie=G.next(ei);
+
+  Edge eee(i);
+  eee=o;
+  eee=eie;
+  
+  
+  bool tm;
+  tm = G.valid(n) && G.valid(i) && G.valid(o) && G.valid(ei);
+
+  std::vector<InEdgeIt> v(10);
+  std::vector<InEdgeIt> w(10,INVALID);
   
 }