Changeset 2:37117ebbabe2 in lemon0.x for src
 Timestamp:
 12/11/03 08:24:53 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@13
 Location:
 src
 Files:

 1 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

src/include/graph.h
r1 r2 73 73 bool operator!=(const NodeIterator &i) const {return n!=i.n;} 74 74 75 int Index() { return n; } //If the nodes are indexable 75 76 friend class Graph; 76 77 friend class EdgeIterator; … … 115 116 bool operator==(const EdgeIterator &i) const {return e==i.e;} 116 117 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 118 122 friend class Graph; 119 123 friend class InEdgeIterator; 
src/work/graphdemo.cc
r1 r2 1 1 #include <iostream> 2 2 #include <graph.h> 3 #include <bfs.h> 3 4 4 5 using namespace NEGRO; … … 15 16 int id; 16 17 bool isVis; 18 bfs_node_data<TestGraph> bfs; 17 19 }; 18 20 … … 23 25 }; 24 26 25 26 27 typedef Graph<NodeData,EdgeData> TestGraph; 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 }; 27 122 28 123 void main() … … 83 178 } 84 179 180 // cout << "Number of edges: " << i << "\n\n"; 181 85 182 for(a=G.First();a.isValid();++a) 86 183 cout << a>id << ": " << a.From()>id << ">" << a.To()>id << " "; … … 96 193 } 97 194 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 98 217 } 
src/work/makefile
r1 r2 1 graphdemo: graphdemo.cc ../include/graph.h \1 graphdemo: graphdemo.cc ../include/graph.h ../include/bfs.h \ 2 2 ../include/oldgraph.h makefile 3 3 g++ g I../include o graphdemo graphdemo.cc
Note: See TracChangeset
for help on using the changeset viewer.