Changeset 3:272a5677bd6d in lemon0.x for src/work/graphdemo.cc
 Timestamp:
 12/13/03 16:44:50 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@15
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/graphdemo.cc
r2 r3 27 27 typedef Graph<NodeData,EdgeData> TestGraph; 28 28 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() 29 int main() 124 30 { 125 31 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; 129 35 130 36 … … 170 76 171 77 ; 172 for(n=G.First();n.isValid();++n) 78 for(n=G.First();n.isValid();++n) //Demo 173 79 { 174 80 e=G.First(n); 175 81 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 ++ 177 83 else ++e; 178 84 } … … 193 99 } 194 100 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 203 102 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 } 217 137 }
Note: See TracChangeset
for help on using the changeset viewer.