COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
12/13/03 16:44:50 (18 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:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/graphdemo.cc

    r2 r3  
    2727typedef Graph<NodeData,EdgeData> TestGraph;
    2828
    29 /*
    30 struct isVis_map {};
    31 bool Get(isVis_map p,TestGraph::NodeIterator i) { return i->isVis;}
    32 void Set(isVis_map p,TestGraph::NodeIterator i,bool b) {  i->isVis=b;}
    33 */
    34 
    35 class my_bfs_maps
    36 {
    37 public:
    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 
    58 class IGraph
    59 {
    60 public:
    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 
    102 class IMaps_t
    103 {
    104 public:
    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 };
    122 
    123 void main()
     29int main()
    12430{
    12531  TestGraph G;
    126   TestGraph::NodeIterator n,m,o,p,q;
    127   TestGraph::OutEdgeIterator e,f,g,h;
    128   int i,j,k;
     32  TestGraph::NodeIterator n,m;
     33  TestGraph::OutEdgeIterator e;
     34  int i;
    12935
    13036 
     
    17076   
    17177  ;
    172   for(n=G.First();n.isValid();++n)
     78  for(n=G.First();n.isValid();++n) //Demo
    17379    {
    17480      e=G.First(n);
    17581      while(e.isValid())
    176         if((e->id)%2) G.Delete(e++);
     82        if((e->id)%2) G.Delete(e++);  //it may be nice to have a postfix ++
    17783        else ++e;
    17884    }
     
    19399    }
    194100 
    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);
     101  // For Marci's sake
    203102 
    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  
     103  {
     104    G.Clean();
     105   
     106    for(int i=1;i<=10;i++) G.AddNode()->id=i;
     107   
     108   
     109    {  //I would'n say I'm really happy with this.
     110      int i;
     111      for(TestGraph::NodeIterator n(G);n.isValid();n++)
     112        for(TestGraph::NodeIterator m(G);m.isValid();++m)
     113          if(n!=m) G.AddEdge(n,m)->id=++i;
     114    }
     115   
     116    for(TestGraph::NodeIterator n(G);n.isValid();++n) //Demo
     117      {
     118        TestGraph::OutEdgeIterator e(G,n);
     119        while(e.isValid())
     120          if((e->id)%2) G.Delete(e++);  //it may be nice to have a postfix ++
     121          else ++e;
     122      }
     123   
     124    for(TestGraph::AllEdgeIterator a(G);a.isValid();++a)
     125      cout << a->id << ": " << a.From()->id << "->" << a.To()->id << "   ";
     126   
     127    cout << "\n\n\n";
     128   
     129    for(TestGraph::NodeIterator n(G);n.isValid();++n)
     130      {
     131        cout << n->id << "->";
     132        for(TestGraph::OutEdgeIterator e(G,n);e.isValid();++e)
     133          cout << e->id << ":" << e.To()->id << ' ';
     134        cout << '\n';
     135      }
     136  }
    217137}
  • src/work/makefile

    r2 r3  
    1 graphdemo: graphdemo.cc ../include/graph.h ../include/bfs.h \
     1CXXFLAGS=-g -Wall -I../include
     2
     3none:
     4        @echo 'Please use one of these forms:'
     5        @echo '   make all'
     6        @echo '   make clean'
     7        @echo '   make graphdemo'
     8        @echo '   make bfsdemo'
     9
     10all: graphdemo bfsdemo
     11
     12clean:
     13        rm graphdemo bfsdemo
     14graphdemo: graphdemo.cc ../include/graph.h \
    215        ../include/oldgraph.h makefile
    3         g++ -g -I../include -o graphdemo graphdemo.cc
     16        g++ $(CXXFLAGS) -o graphdemo graphdemo.cc
     17
     18bfsdemo: bfsdemo.cc ../include/graph.h ../include/bfs.h \
     19        ../include/oldgraph.h makefile
     20        g++ $(CXXFLAGS) -o bfsdemo bfsdemo.cc
Note: See TracChangeset for help on using the changeset viewer.