Changeset 3:272a5677bd6d in lemon-0.x for src/work

Timestamp:

12/13/03 16:44:50 (21 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@15

Message:

• Marci type iterator constructors
• src/demo/bfsdemo.cc: demo for bfs.h
• cosmetical changes

Location:

src/work

Files:

• bfsdemo.cc (added)
• graphdemo.cc (modified) (3 diffs)
• makefile (modified) (1 diff)

src/work/graphdemo.cc

@@ -27 +27 @@
 typedef Graph<NodeData,EdgeData> TestGraph;
 
-/*
-struct isVis_map {};
-bool Get(isVis_map p,TestGraph::NodeIterator i) { return i->isVis;}
-void Set(isVis_map p,TestGraph::NodeIterator i,bool b) {  i->isVis=b;}
-*/
-
-class my_bfs_maps
-{
-public:
-  //isVis_map visited;  //node->bool (RW)
-  class_element_map<TestGraph::NodeIterator,
-                    TestGraph::NodeType,
-                    bool,
-                    &NodeData::isVis> visited;
-  struct _tree_map_t {
-    typedef TestGraph::EdgeIterator value_type;
-    void Set(const TestGraph::NodeIterator &n,const value_type &t)
-    {
-      cout << t.From()->id << "->" << t.To()->id << '\n';
-    }
-  } tree;
-  do_nothing_map dist;   //node->int (W)
-  do_nothing_map priority; //node->int (W)
-  //priority_map priority; //node->int (W)
-};
-
-
-
-
-class IGraph 
-{
-public:
-
-  //  struct NodeType {bfs_node_data<TestGraph> bfs;};
-  struct NodeType {bool isVis;};
-
-  vector<NodeType> nodes;
-  
-  class NodeIterator 
-  {
-  public:
-    IGraph *G;
-    int n;
-    NodeIterator &operator ++() { n++; return *this;}
-    NodeType &operator *() const { return G->nodes[n];}
-    NodeType *operator ->() const { return &(G->nodes[n]);}
-    bool isValid() const {return n<=5000;}
-    int Index() {return n;} //csak a kiirashoz kell
-  };
-
-  void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
-
-  class OutEdgeIterator 
-  {    
-  public:
-    IGraph *G;
-    int f,t;
-    int gcd() { int a=f;int b=t;int c;while(c=a%b) {a=b;b=c;} ; return b;}
-    OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
-    bool isValid() const {return t<=5000;}
-    NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
-    NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
-    NodeIterator Anode() const {return From();}
-    NodeIterator Bnode() const {return To();}
-  };
-
-  typedef OutEdgeIterator EdgeIterator;
-  void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
-  {i.G=this;i.f=n.n;i.t=0;++i;}
-
-  IGraph() : nodes(5000) {}
-};
-
-class IMaps_t
-{
-public:
-//     class_element_map<IGraph::NodeIterator,
-//                  IGraph::NodeType,
-//                  bool,
-//                  &IGraph::NodeType::isVis> visited;
-  struct _visited_map_t {
-    typedef bool value_type;
-    void Set(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
-    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
-  } visited;
-  struct _tree_map_t {
-    typedef IGraph::EdgeIterator value_type;
-    void Set(const IGraph::NodeIterator &n,const value_type &t)
-    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
-  } tree;
-  do_nothing_map dist;   //node->int (W)
-  do_nothing_map priority; //node->int (W)
-};
-
-void main()
+int main()
 {
   TestGraph G;
-  TestGraph::NodeIterator n,m,o,p,q;
-  TestGraph::OutEdgeIterator e,f,g,h;
-  int i,j,k;
+  TestGraph::NodeIterator n,m;
+  TestGraph::OutEdgeIterator e;
+  int i;
 
   
@@ -170 +76 @@
    
   ;
-  for(n=G.First();n.isValid();++n)
+  for(n=G.First();n.isValid();++n) //Demo
     {
       e=G.First(n);
       while(e.isValid())
-        if((e->id)%2) G.Delete(e++);
+        if((e->id)%2) G.Delete(e++);  //it may be nice to have a postfix ++
         else ++e;
     }
@@ -193 +99 @@
     }
   
-  n=G.First();
-
-
-  //G.Clean();
-
-  cout << "\n\n\n BFS \n\n\n";
-  //my_bfs_maps Maps;
-  //  bfs_static_maps<TestGraph> Maps(&NodeData::bfs);
+  // For Marci's sake
   
-  /// bfs(G,n,Maps);
-
-  cout << '\n';
-
-  IGraph IG;
-  IMaps_t IMaps;
-
-  IGraph::NodeIterator in;
-  IG.GetFirst(in);
-  ++in;
-  bfs(IG,in,IMaps);
-  
-  
+  {
+    G.Clean();
+    
+    for(int i=1;i<=10;i++) G.AddNode()->id=i;
+    
+    
+    {  //I would'n say I'm really happy with this.
+      int i;
+      for(TestGraph::NodeIterator n(G);n.isValid();n++)
+        for(TestGraph::NodeIterator m(G);m.isValid();++m)
+          if(n!=m) G.AddEdge(n,m)->id=++i;
+    }
+    
+    for(TestGraph::NodeIterator n(G);n.isValid();++n) //Demo
+      {
+        TestGraph::OutEdgeIterator e(G,n);
+        while(e.isValid())
+          if((e->id)%2) G.Delete(e++);  //it may be nice to have a postfix ++
+          else ++e;
+      }
+    
+    for(TestGraph::AllEdgeIterator a(G);a.isValid();++a)
+      cout << a->id << ": " << a.From()->id << "->" << a.To()->id << "   ";
+    
+    cout << "\n\n\n";
+    
+    for(TestGraph::NodeIterator n(G);n.isValid();++n)
+      {
+        cout << n->id << "->";
+        for(TestGraph::OutEdgeIterator e(G,n);e.isValid();++e)
+          cout << e->id << ":" << e.To()->id << ' ';
+        cout << '\n';
+      }
+  }
 }

src/work/makefile

@@ -1 @@
-graphdemo: graphdemo.cc ../include/graph.h ../include/bfs.h \
+CXXFLAGS=-g -Wall -I../include
+
+none:
+        @echo 'Please use one of these forms:'
+        @echo '   make all'
+        @echo '   make clean'
+        @echo '   make graphdemo'
+        @echo '   make bfsdemo'
+
+all: graphdemo bfsdemo
+
+clean:
+        rm graphdemo bfsdemo
+graphdemo: graphdemo.cc ../include/graph.h \
         ../include/oldgraph.h makefile
-        g++ -g -I../include -o graphdemo graphdemo.cc
+        g++ $(CXXFLAGS) -o graphdemo graphdemo.cc
+
+bfsdemo: bfsdemo.cc ../include/graph.h ../include/bfs.h \
+        ../include/oldgraph.h makefile
+        g++ $(CXXFLAGS) -o bfsdemo bfsdemo.cc