src/work/iterator_bfs_demo.cc
author jacint
Tue, 17 Feb 2004 11:16:39 +0000
changeset 85 15362fafaf1a
child 99 f26897fb91fd
permissions -rw-r--r--
*** empty log message ***
marci@75
     1
#include <iostream>
marci@75
     2
#include <vector>
marci@75
     3
#include <string>
marci@75
     4
marci@75
     5
#include <list_graph.hh>
marci@75
     6
#include <bfs_iterator.hh>
marci@75
     7
#include <graph_wrapper.h>
marci@75
     8
marci@75
     9
using namespace marci;
marci@75
    10
marci@75
    11
int main (int, char*[])
marci@75
    12
{
marci@75
    13
  typedef ListGraph::NodeIt NodeIt;
marci@75
    14
  typedef ListGraph::EdgeIt EdgeIt;
marci@75
    15
  typedef ListGraph::EachNodeIt EachNodeIt;
marci@75
    16
  typedef ListGraph::EachEdgeIt EachEdgeIt;
marci@75
    17
  typedef ListGraph::OutEdgeIt OutEdgeIt;
marci@75
    18
  typedef ListGraph::InEdgeIt InEdgeIt;
marci@75
    19
  typedef ListGraph::SymEdgeIt SymEdgeIt;
marci@75
    20
 
marci@75
    21
  ListGraph G;
marci@75
    22
marci@75
    23
  NodeIt s=G.addNode();
marci@75
    24
  NodeIt v1=G.addNode();
marci@75
    25
  NodeIt v2=G.addNode();
marci@75
    26
  NodeIt v3=G.addNode();
marci@75
    27
  NodeIt v4=G.addNode();
marci@75
    28
  NodeIt t=G.addNode();
marci@75
    29
  
marci@75
    30
  G.addEdge(s, v1);
marci@75
    31
  G.addEdge(s, v2);
marci@75
    32
  G.addEdge(v1, v2);
marci@75
    33
  G.addEdge(v2, v1);
marci@75
    34
  G.addEdge(v1, v3);
marci@75
    35
  G.addEdge(v3, v2);
marci@75
    36
  G.addEdge(v2, v4);
marci@75
    37
  G.addEdge(v4, v3);
marci@75
    38
  G.addEdge(v3, t);
marci@75
    39
  G.addEdge(v4, t);
marci@75
    40
marci@75
    41
  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
marci@75
    42
  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 
marci@75
    43
    std::cout << i << ": ";
marci@75
    44
    std::cout << "out edges: ";
marci@75
    45
    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) 
marci@75
    46
      std::cout << j << " ";
marci@75
    47
    std::cout << "in edges: ";
marci@75
    48
    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) 
marci@75
    49
      std::cout << j << " ";
marci@75
    50
    std::cout << std::endl;
marci@75
    51
  }
marci@75
    52
  
marci@75
    53
  {
marci@75
    54
    std::cout << "iterator bfs demo 4 ..." << std::endl;
marci@75
    55
    BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
marci@75
    56
    bfs.pushAndSetReached(s);
marci@75
    57
    while (!bfs.finished()) {
marci@75
    58
      if (OutEdgeIt(bfs).valid()) {
marci@75
    59
	std::cout << "OutEdgeIt: " << bfs; 
marci@75
    60
	std::cout << " aNode: " << G.aNode(bfs); 
marci@75
    61
	std::cout << " bNode: " << G.bNode(bfs) << " ";
marci@75
    62
      } else { 
marci@75
    63
	std::cout << "OutEdgeIt: " << "invalid"; 
marci@75
    64
	std::cout << " aNode: " << bfs.aNode(); 
marci@75
    65
	std::cout << " bNode: " << "invalid" << " ";
marci@75
    66
      }
marci@75
    67
      if (bfs.isBNodeNewlyReached()) { 
marci@75
    68
	std::cout << "bNodeIsNewlyReached ";
marci@75
    69
      } else { 
marci@75
    70
	std::cout << "bNodeIsNotNewlyReached ";
marci@75
    71
      } 
marci@75
    72
      if (bfs.isANodeExamined()) { 
marci@75
    73
	std::cout << "aNodeIsExamined ";
marci@75
    74
      } else { 
marci@75
    75
	std::cout << "aNodeIsNotExamined ";
marci@75
    76
      } 
marci@75
    77
      std::cout<<std::endl;
marci@75
    78
      ++bfs;
marci@75
    79
    }
marci@75
    80
  }
marci@75
    81
marci@75
    82
  typedef ConstTrivGraphWrapper<ListGraph> CTGW;
marci@75
    83
  CTGW wG(G);
marci@75
    84
marci@75
    85
  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
marci@75
    86
  for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) { 
marci@75
    87
    std::cout << i << ": ";
marci@75
    88
    std::cout << "out edges: ";
marci@75
    89
    for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j) 
marci@75
    90
      std::cout << j << " ";
marci@75
    91
    std::cout << "in edges: ";
marci@75
    92
    for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j) 
marci@75
    93
      std::cout << j << " ";
marci@75
    94
    std::cout << std::endl;
marci@75
    95
  }
marci@75
    96
marci@75
    97
marci@75
    98
  {
marci@75
    99
    std::cout << "iterator bfs demo 5 ..." << std::endl;
marci@75
   100
    BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
marci@75
   101
    bfs.pushAndSetReached(s);
marci@75
   102
    while (!bfs.finished()) {
marci@75
   103
      if (OutEdgeIt(bfs).valid()) {
marci@75
   104
	std::cout << "OutEdgeIt: " << bfs; 
marci@75
   105
	std::cout << " aNode: " << wG.aNode(bfs); 
marci@75
   106
	std::cout << " bNode: " << wG.bNode(bfs) << " ";
marci@75
   107
      } else { 
marci@75
   108
	std::cout << "OutEdgeIt: " << "invalid"; 
marci@75
   109
	std::cout << " aNode: " << bfs.aNode(); 
marci@75
   110
	std::cout << " bNode: " << "invalid" << " ";
marci@75
   111
      }
marci@75
   112
      if (bfs.isBNodeNewlyReached()) { 
marci@75
   113
	std::cout << "bNodeIsNewlyReached ";
marci@75
   114
      } else { 
marci@75
   115
	std::cout << "bNodeIsNotNewlyReached ";
marci@75
   116
      } 
marci@75
   117
      if (bfs.isANodeExamined()) { 
marci@75
   118
	std::cout << "aNodeIsExamined ";
marci@75
   119
      } else { 
marci@75
   120
	std::cout << "aNodeIsNotExamined ";
marci@75
   121
      } 
marci@75
   122
      std::cout<<std::endl;
marci@75
   123
      ++bfs;
marci@75
   124
    }
marci@75
   125
  }
marci@75
   126
marci@75
   127
marci@75
   128
  return 0;
marci@75
   129
}