COIN-OR::LEMON - Graph Library

Changeset 2:37117ebbabe2 in lemon-0.x


Ignore:
Timestamp:
12/11/03 08:24:53 (16 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@13
Message:

bfs

Location:
src
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/include/graph.h

    r1 r2  
    7373      bool operator!=(const NodeIterator &i) const {return n!=i.n;}
    7474     
     75      int Index() { return n; } //If the nodes are indexable
    7576      friend class Graph;
    7677      friend class EdgeIterator;
     
    115116      bool operator==(const EdgeIterator &i) const {return e==i.e;}
    116117      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
    117      
     118       
     119      int Index() { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
     120      //If the edges are indexable
     121
    118122      friend class Graph;
    119123      friend class InEdgeIterator;
  • src/work/graphdemo.cc

    r1 r2  
    11#include <iostream>
    22#include <graph.h>
     3#include <bfs.h>
    34
    45using namespace NEGRO;
     
    1516  int id;
    1617  bool isVis;
     18  bfs_node_data<TestGraph> bfs;
    1719};
    1820
     
    2325};
    2426
    25 
    2627typedef Graph<NodeData,EdgeData> TestGraph;
     28
     29/*
     30struct isVis_map {};
     31bool Get(isVis_map p,TestGraph::NodeIterator i) { return i->isVis;}
     32void Set(isVis_map p,TestGraph::NodeIterator i,bool b) {  i->isVis=b;}
     33*/
     34
     35class my_bfs_maps
     36{
     37public:
     38  //isVis_map visited;  //node->bool (RW)
     39  class_element_map<TestGraph::NodeIterator,
     40                    TestGraph::NodeType,
     41                    bool,
     42                    &NodeData::isVis> visited;
     43  struct _tree_map_t {
     44    typedef TestGraph::EdgeIterator value_type;
     45    void Set(const TestGraph::NodeIterator &n,const value_type &t)
     46    {
     47      cout << t.From()->id << "->" << t.To()->id << '\n';
     48    }
     49  } tree;
     50  do_nothing_map dist;   //node->int (W)
     51  do_nothing_map priority; //node->int (W)
     52  //priority_map priority; //node->int (W)
     53};
     54
     55
     56
     57
     58class IGraph
     59{
     60public:
     61
     62  //  struct NodeType {bfs_node_data<TestGraph> bfs;};
     63  struct NodeType {bool isVis;};
     64
     65  vector<NodeType> nodes;
     66 
     67  class NodeIterator
     68  {
     69  public:
     70    IGraph *G;
     71    int n;
     72    NodeIterator &operator ++() { n++; return *this;}
     73    NodeType &operator *() const { return G->nodes[n];}
     74    NodeType *operator ->() const { return &(G->nodes[n]);}
     75    bool isValid() const {return n<=5000;}
     76    int Index() {return n;} //csak a kiirashoz kell
     77  };
     78
     79  void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
     80
     81  class OutEdgeIterator
     82  {   
     83  public:
     84    IGraph *G;
     85    int f,t;
     86    int gcd() { int a=f;int b=t;int c;while(c=a%b) {a=b;b=c;} ; return b;}
     87    OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
     88    bool isValid() const {return t<=5000;}
     89    NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
     90    NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
     91    NodeIterator Anode() const {return From();}
     92    NodeIterator Bnode() const {return To();}
     93  };
     94
     95  typedef OutEdgeIterator EdgeIterator;
     96  void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
     97  {i.G=this;i.f=n.n;i.t=0;++i;}
     98
     99  IGraph() : nodes(5000) {}
     100};
     101
     102class IMaps_t
     103{
     104public:
     105//     class_element_map<IGraph::NodeIterator,
     106//                  IGraph::NodeType,
     107//                  bool,
     108//                  &IGraph::NodeType::isVis> visited;
     109  struct _visited_map_t {
     110    typedef bool value_type;
     111    void Set(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
     112    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
     113  } visited;
     114  struct _tree_map_t {
     115    typedef IGraph::EdgeIterator value_type;
     116    void Set(const IGraph::NodeIterator &n,const value_type &t)
     117    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
     118  } tree;
     119  do_nothing_map dist;   //node->int (W)
     120  do_nothing_map priority; //node->int (W)
     121};
    27122
    28123void main()
     
    83178    }
    84179 
     180  // cout << "Number of edges: " << i << "\n\n";
     181
    85182  for(a=G.First();a.isValid();++a)
    86183    cout << a->id << ": " << a.From()->id << "->" << a.To()->id << "   ";
     
    96193    }
    97194 
     195  n=G.First();
     196
     197
     198  //G.Clean();
     199
     200  cout << "\n\n\n BFS \n\n\n";
     201  //my_bfs_maps Maps;
     202  //  bfs_static_maps<TestGraph> Maps(&NodeData::bfs);
     203 
     204  /// bfs(G,n,Maps);
     205
     206  cout << '\n';
     207
     208  IGraph IG;
     209  IMaps_t IMaps;
     210
     211  IGraph::NodeIterator in;
     212  IG.GetFirst(in);
     213  ++in;
     214  bfs(IG,in,IMaps);
     215 
     216 
    98217}
  • src/work/makefile

    r1 r2  
    1 graphdemo: graphdemo.cc ../include/graph.h \
     1graphdemo: graphdemo.cc ../include/graph.h ../include/bfs.h \
    22        ../include/oldgraph.h makefile
    33        g++ -g -I../include -o graphdemo graphdemo.cc
Note: See TracChangeset for help on using the changeset viewer.