source: lemon-0.x/src/work/graphdemo.cc @ 2:37117ebbabe2

#include <iostream>
#include <graph.h>
#include <bfs.h>

using namespace NEGRO;
using namespace std;

class NodeData;
class EdgeData;

typedef Graph<NodeData,EdgeData> TestGraph;

class NodeData
{
public:
  int id;
  bool isVis;
  bfs_node_data<TestGraph> bfs;
};

class EdgeData
{
public:
  int id;
};

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()
{
  TestGraph G;
  TestGraph::NodeIterator n,m,o,p,q;
  TestGraph::OutEdgeIterator e,f,g,h;
  int i,j,k;

  
  //for(i=1;i<=10;i++) G.AddNode().n=i; //Ez nagyon rossz!!!!!!!!
  for(i=1;i<=10;i++) G.AddNode()->id=i; //Ez a jo!!!!!!!!

  //n=G.AddNode();
  
   //for(i=1;i<=10;i++) cout << (G.AddNode()->n=i) << ' ';
   //cout << '\n';
 
  i=0;
  for(G.GetFirst(n);n.isValid();n++)
    for(G.GetFirst(m);m.isValid();++m)
      if(n!=m) G.AddEdge(n,m)->id=++i;
   
  cout << "Number of edges: " << i << "\n\n";

  TestGraph::AllEdgeIterator a;
  for(G.GetFirst(a);a.isValid();++a)
    cout << a->id << ":" << a.From()->id << "->" << a.To()->id << "   ";

  cout << "\n\n\n";
  
  for(G.GetFirst(n);n.isValid();++n)
    {
      cout << n->id << "->";
      for(G.GetFirst(e,n);e.isValid();++e)
        cout << e->id << ":" << e.To()->id << ' ';
      cout << '\n';
    }
  
  cout << "\n\n\n\nB-verzio:\n\n\n";
  
  G.Clean();

  for(i=1;i<=10;i++) G.AddNode()->id=i;
  
  i=0;
  for(n=G.First();n.isValid();n++)
    for(m=G.First();m.isValid();++m)
      if(n!=m) G.AddEdge(n,m)->id=++i;
   
  ;
  for(n=G.First();n.isValid();++n)
    {
      e=G.First(n);
      while(e.isValid())
        if((e->id)%2) G.Delete(e++);
        else ++e;
    }
  
  // cout << "Number of edges: " << i << "\n\n";

  for(a=G.First();a.isValid();++a)
    cout << a->id << ": " << a.From()->id << "->" << a.To()->id << "   ";
  
  cout << "\n\n\n";
  
  for(n=G.First();n.isValid();++n)
    {
      cout << n->id << "->";
      for(e=G.First(n);e.isValid();++e)
        cout << e->id << ":" << e.To()->id << ' ';
      cout << '\n';
    }
  
  n=G.First();


  //G.Clean();

  cout << "\n\n\n BFS \n\n\n";
  //my_bfs_maps Maps;
  //  bfs_static_maps<TestGraph> Maps(&NodeData::bfs);
  
  /// bfs(G,n,Maps);

  cout << '\n';

  IGraph IG;
  IMaps_t IMaps;

  IGraph::NodeIterator in;
  IG.GetFirst(in);
  ++in;
  bfs(IG,in,IMaps);
  
  
}