Changeset 774:4297098d9677 in lemon-0.x for src/work

Timestamp:

08/30/04 14:01:47 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Merge back the whole branches/hugo++ to trunk.

Location:

src/work

Files:

• marci/bfs_dfs.h (modified) (7 diffs)
• marci/iterator_bfs_demo.cc (modified) (12 diffs)
• sage_graph.h (modified) (7 diffs)

src/work/marci/bfs_dfs.h

@@ -61 +61 @@
         bfs_queue.push(s);
         graph->first(actual_edge, s);
-        if (graph->valid(actual_edge)) { 
-          Node w=graph->bNode(actual_edge);
+        if (actual_edge!=INVALID) { 
+          Node w=graph->head(actual_edge);
           if (!reached[w]) {
             bfs_queue.push(w);
@@ -79 +79 @@
     BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
     operator++() { 
-      if (graph->valid(actual_edge)) { 
-        graph->next(actual_edge);
-        if (graph->valid(actual_edge)) {
-          Node w=graph->bNode(actual_edge);
+      if (actual_edge!=INVALID) { 
+        ++actual_edge;
+        if (actual_edge!=INVALID) {
+          Node w=graph->head(actual_edge);
           if (!reached[w]) {
             bfs_queue.push(w);
@@ -95 +95 @@
         if (!bfs_queue.empty()) {
           graph->first(actual_edge, bfs_queue.front());
-          if (graph->valid(actual_edge)) {
-            Node w=graph->bNode(actual_edge);
+          if (actual_edge!=INVALID) {
+            Node w=graph->head(actual_edge);
             if (!reached[w]) {
               bfs_queue.push(w);
@@ -118 +118 @@
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     /// Returns if a-node is examined.
-    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
+    bool isANodeExamined() const { return actual_edge==INVALID; }
     /// Returns a-node of the actual edge, so does if the edge is invalid.
     Node aNode() const { return bfs_queue.front(); }
@@ -238 +238 @@
       actual_edge=dfs_stack.top();
       //actual_node=G.aNode(actual_edge);
-      if (graph->valid(actual_edge)/*.valid()*/) { 
-        Node w=graph->bNode(actual_edge);
+      if (actual_edge!=INVALID/*.valid()*/) { 
+        Node w=graph->head(actual_edge);
         actual_node=w;
         if (!reached[w]) {
@@ -248 +248 @@
           b_node_newly_reached=true;
         } else {
-          actual_node=graph->aNode(actual_edge);
-          graph->next(dfs_stack.top());
+          actual_node=graph->tail(actual_edge);
+          ++dfs_stack.top();
           b_node_newly_reached=false;
         }
@@ -267 +267 @@
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     /// Returns if a-node is examined.
-    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
+    bool isANodeExamined() const { return actual_edge==INVALID; }
     /// Returns a-node of the actual edge, so does if the edge is invalid.
     Node aNode() const { return actual_node; /*FIXME*/}

src/work/marci/iterator_bfs_demo.cc

@@ -5 +5 @@
 
 #include <sage_graph.h>
-//#include <smart_graph.h>
+#include <hugo/smart_graph.h>
 #include <bfs_dfs.h>
 #include <hugo/graph_wrapper.h>
@@ -29 +29 @@
 int main (int, char*[])
 {
-  //typedef SmartGraph Graph;
-  typedef SageGraph Graph;
+  typedef SmartGraph Graph;
+  //typedef SageGraph Graph;
 
   typedef Graph::Node Node;
@@ -92 +92 @@
     
     cout << "bfs and dfs iterator demo on the directed graph" << endl;
-    for(Graph::NodeIt n(G); G.valid(n); G.next(n)) { 
+    for(Graph::NodeIt n(G); n!=INVALID; ++n) { 
       cout << node_name[n] << ": ";
       cout << "out edges: ";
-      for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e)) 
+      for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e) 
         cout << edge_name[e] << " ";
       cout << "in edges: ";
-      for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e)) 
+      for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e) 
         cout << edge_name[e] << " ";
       cout << endl;
@@ -108 +108 @@
     while (!bfs.finished()) {
       //cout << "edge: ";
-      if (G.valid(bfs)) {
+      if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {
         cout << edge_name[bfs] << /*endl*/", " << 
-          node_name[G.aNode(bfs)] << 
-          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          node_name[G.bNode(bfs)] << 
+          node_name[G.tail(bfs)] << 
+          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          node_name[G.head(bfs)] << 
           (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
            ": is not newly reached.");
@@ -142 +142 @@
       ++dfs;
       //cout << "edge: ";
-      if (G.valid(dfs)) {
+      if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {
         cout << edge_name[dfs] << /*endl*/", " << 
-          node_name[G.aNode(dfs)] << 
-          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          node_name[G.bNode(dfs)] << 
+          node_name[G.tail(dfs)] << 
+          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          node_name[G.head(dfs)] << 
           (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
            ": is not newly reached.");
@@ -168 +168 @@
     
     cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
-    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 
+    for(GW::NodeIt n(gw); n!=INVALID; ++n) { 
       cout << node_name[GW::Node(n)] << ": ";
       cout << "out edges: ";
-      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) 
         cout << edge_name[e] << " ";
       cout << "in edges: ";
-      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) 
         cout << edge_name[e] << " ";
       cout << endl;
@@ -184 +184 @@
     while (!bfs.finished()) {
       //cout << "edge: ";
-      if (gw.valid(GW::OutEdgeIt(bfs))) {
+      if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {
         cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
-          node_name[gw.aNode(bfs)] << 
-          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          node_name[gw.bNode(bfs)] << 
+          node_name[gw.tail(bfs)] << 
+          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          node_name[gw.head(bfs)] << 
           (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
            ": is not newly reached.");
@@ -218 +218 @@
       ++dfs;
       //cout << "edge: ";
-      if (gw.valid(GW::OutEdgeIt(dfs))) {
+      if (GW::OutEdgeIt(dfs)!=INVALID) {
         cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
-          node_name[gw.aNode(dfs)] << 
-          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          node_name[gw.bNode(dfs)] << 
+          node_name[gw.tail(dfs)] << 
+          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          node_name[gw.head(dfs)] << 
           (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
            ": is not newly reached.");
@@ -236 +236 @@
   }
 
+//   {
+//     typedef UndirGraphWrapper<const Graph> GW;
+//     GW gw(G);
+    
+//     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
+    
+//     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
+//     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 
+//       cout << node_name[GW::Node(n)] << ": ";
+//       cout << "out edges: ";
+//       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+//      cout << edge_name[e] << " ";
+//       cout << "in edges: ";
+//       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+//      cout << edge_name[e] << " ";
+//       cout << endl;
+//     }
+// //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 
+// //       cout << edge_name.get(e) << " ";
+// //     }
+// //     cout << endl;
+
+//     cout << "bfs from t ..." << endl;
+//     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
+//     bfs.pushAndSetReached(t);
+//     while (!bfs.finished()) {
+//       //cout << "edge: ";
+//       if (gw.valid(GW::OutEdgeIt(bfs))) {
+//      cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
+//        node_name[gw.aNode(bfs)] << 
+//        (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+//        node_name[gw.bNode(bfs)] << 
+//        (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
+//         ": is not newly reached.");
+//       } else { 
+//      cout << "invalid" << /*endl*/", " << 
+//        node_name[bfs.aNode()] << 
+//        (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          
+//        "invalid.";
+//       }
+//       cout << endl;
+//       ++bfs;
+//     }
+
+//     cout << "    /-->    ------------->            "<< endl;
+//     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
+//     cout << "  / |          |    /  /->     \\     "<< endl;
+//     cout << " /  |          |   /  |    ^    \\  "<< endl;
+//     cout << "s   |          |  /   |    |     \\->  t "<< endl;
+//     cout << " \\  |          | /    |    |     /->  "<< endl;
+//     cout << "  \\ |       --/ /     |    |    /     "<< endl;
+//     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
+//     cout << "    \\-->    ------------->         "<< endl;
+    
+//     cout << "dfs from t ..." << endl;
+//     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
+//     dfs.pushAndSetReached(t);
+//     while (!dfs.finished()) {
+//       ++dfs;
+//       //cout << "edge: ";
+//       if (gw.valid(GW::OutEdgeIt(dfs))) {
+//      cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
+//        node_name[gw.aNode(dfs)] << 
+//        (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+//        node_name[gw.bNode(dfs)] << 
+//        (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
+//         ": is not newly reached.");
+//       } else { 
+//      cout << "invalid" << /*endl*/", " << 
+//        node_name[dfs.aNode()] << 
+//        (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          
+//        "invalid.";
+//       }
+//       cout << endl;
+//     }
+//   }
+
+
+
   {
-    typedef UndirGraphWrapper<const Graph> GW;
+    typedef BidirGraphWrapper<const Graph> GW;
     GW gw(G);
     
     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
     
-    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
-    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 
+    cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
+//     for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
+//       cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " ";
+//     } 
+    for(GW::NodeIt n(gw); n!=INVALID; ++n) { 
       cout << node_name[GW::Node(n)] << ": ";
       cout << "out edges: ";
-      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) 
         cout << edge_name[e] << " ";
       cout << "in edges: ";
-      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) 
         cout << edge_name[e] << " ";
       cout << endl;
@@ -263 +347 @@
     while (!bfs.finished()) {
       //cout << "edge: ";
-      if (gw.valid(GW::OutEdgeIt(bfs))) {
+      if (GW::OutEdgeIt(bfs)!=INVALID) {
         cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
-          node_name[gw.aNode(bfs)] << 
-          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          node_name[gw.bNode(bfs)] << 
+          node_name[gw.tail(bfs)] << 
+          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          node_name[gw.head(bfs)] << 
           (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
            ": is not newly reached.");
@@ -297 +381 @@
       ++dfs;
       //cout << "edge: ";
-      if (gw.valid(GW::OutEdgeIt(dfs))) {
+      if (GW::OutEdgeIt(dfs)!=INVALID) {
         cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
-          node_name[gw.aNode(dfs)] << 
-          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          node_name[gw.bNode(dfs)] << 
+          node_name[gw.tail(dfs)] << 
+          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          node_name[gw.head(dfs)] << 
           (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
            ": is not newly reached.");
@@ -314 +398 @@
     }
   }
-
-
-
-  {
-    typedef BidirGraphWrapper<const Graph> GW;
-    GW gw(G);
-    
-    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
-    
-    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
-    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 
-      cout << node_name[GW::Node(n)] << ": ";
-      cout << "out edges: ";
-      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
-        cout << edge_name[e] << " ";
-      cout << "in edges: ";
-      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
-        cout << edge_name[e] << " ";
-      cout << endl;
-    }
-//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 
-//       cout << edge_name.get(e) << " ";
-//     }
-//     cout << endl;
-
-    cout << "bfs from t ..." << endl;
-    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
-    bfs.pushAndSetReached(t);
-    while (!bfs.finished()) {
-      //cout << "edge: ";
-      if (gw.valid(GW::OutEdgeIt(bfs))) {
-        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
-          node_name[gw.aNode(bfs)] << 
-          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          node_name[gw.bNode(bfs)] << 
-          (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
-           ": is not newly reached.");
-      } else { 
-        cout << "invalid" << /*endl*/", " << 
-          node_name[bfs.aNode()] << 
-          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          
-          "invalid.";
-      }
-      cout << endl;
-      ++bfs;
-    }
-
-    cout << "    /-->    ------------->            "<< endl;
-    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
-    cout << "  / |          |    /  /->     \\     "<< endl;
-    cout << " /  |          |   /  |    ^    \\  "<< endl;
-    cout << "s   |          |  /   |    |     \\->  t "<< endl;
-    cout << " \\  |          | /    |    |     /->  "<< endl;
-    cout << "  \\ |       --/ /     |    |    /     "<< endl;
-    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
-    cout << "    \\-->    ------------->         "<< endl;
-    
-    cout << "dfs from t ..." << endl;
-    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
-    dfs.pushAndSetReached(t);
-    while (!dfs.finished()) {
-      ++dfs;
-      //cout << "edge: ";
-      if (gw.valid(GW::OutEdgeIt(dfs))) {
-        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
-          node_name[gw.aNode(dfs)] << 
-          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          node_name[gw.bNode(dfs)] << 
-          (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
-           ": is not newly reached.");
-      } else { 
-        cout << "invalid" << /*endl*/", " << 
-          node_name[dfs.aNode()] << 
-          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
-          
-          "invalid.";
-      }
-      cout << endl;
-    }
-  }
-
-
 
   return 0;

src/work/sage_graph.h

@@ -10 +10 @@
 namespace hugo {
 
-  template <typename It>
-  int count(It it) { 
-    int i=0;
-    for( ; it.valid(); ++it) { ++i; } 
-    return i;
-  }
+//   template <typename It>
+//   int count(It it) { 
+//     int i=0;
+//     for( ; it.valid(); ++it) { ++i; } 
+//     return i;
+//   }
 
   class SageGraph {
@@ -386 +386 @@
     public: //for everybody but marci
       NodeIt(const SageGraph& G) : Node(G._first_node) { }
+      NodeIt(const SageGraph& G, const Node& n) : Node(n) { } 
     public:
       NodeIt() : Node() { }
@@ -391 +392 @@
     protected:
       NodeIt(node_item* v) : Node(v) { }
+    public:
       NodeIt& operator++() { node=node->_next_node; return *this; }
       //FIXME::
@@ -426 +428 @@
     class EdgeIt : public Edge {
       friend class SageGraph;
-      //protected: 
-    public: //for alpar
+    public:
+      EdgeIt() : Edge() { }
+      EdgeIt(const Invalid& i) : Edge(i) { }
       EdgeIt(const SageGraph& G) {
         node_item* v=G._first_node;
@@ -433 +436 @@
         while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
       }
-    public:
-      EdgeIt() : Edge() { }
-      EdgeIt(const Invalid& i) : Edge(i) { }
-    protected:
-      EdgeIt(edge_item* _e) : Edge(_e) { }
+      EdgeIt(const SageGraph& G, const Edge& e) : Edge(e) { }
+//     protected:
+//       EdgeIt(edge_item* _e) : Edge(_e) { }
+    public:
       EdgeIt& operator++() { 
         node_item* v=edge->_tail;
@@ -448 +450 @@
     class OutEdgeIt : public Edge {
       friend class SageGraph;
-      //node_item* v;
-      //protected: 
-    protected: //for alpar
-      OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
-    public:
-      OutEdgeIt() : Edge()/*, v(0)*/ { }
+    public:
+      OutEdgeIt() : Edge() { }
       OutEdgeIt(const Invalid& i) : Edge(i) { }
-      OutEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
-    protected:
+      OutEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_out_edge) { }
+      OutEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { }
       OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
     protected:
@@ -465 +463 @@
     class InEdgeIt : public Edge {
       friend class SageGraph;
-      //node_item* v;
-      //protected:
-    protected: //for alpar
-      InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
-    public:
-      InEdgeIt() : Edge()/*, v(0)*/ { }
-      InEdgeIt(const Invalid& i) : Edge(i) { }
-      InEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
-    protected:
+    public:
+      InEdgeIt() : Edge() { }
+      InEdgeIt(Invalid i) : Edge(i) { }
+      InEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_in_edge) { }
+      InEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { }
       InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
     protected: