1.1 --- a/src/work/graphdemo.cc Thu Dec 11 07:24:53 2003 +0000
1.2 +++ b/src/work/graphdemo.cc Sat Dec 13 15:44:50 2003 +0000
1.3 @@ -26,106 +26,12 @@
1.4
1.5 typedef Graph<NodeData,EdgeData> TestGraph;
1.6
1.7 -/*
1.8 -struct isVis_map {};
1.9 -bool Get(isVis_map p,TestGraph::NodeIterator i) { return i->isVis;}
1.10 -void Set(isVis_map p,TestGraph::NodeIterator i,bool b) { i->isVis=b;}
1.11 -*/
1.12 -
1.13 -class my_bfs_maps
1.14 -{
1.15 -public:
1.16 - //isVis_map visited; //node->bool (RW)
1.17 - class_element_map<TestGraph::NodeIterator,
1.18 - TestGraph::NodeType,
1.19 - bool,
1.20 - &NodeData::isVis> visited;
1.21 - struct _tree_map_t {
1.22 - typedef TestGraph::EdgeIterator value_type;
1.23 - void Set(const TestGraph::NodeIterator &n,const value_type &t)
1.24 - {
1.25 - cout << t.From()->id << "->" << t.To()->id << '\n';
1.26 - }
1.27 - } tree;
1.28 - do_nothing_map dist; //node->int (W)
1.29 - do_nothing_map priority; //node->int (W)
1.30 - //priority_map priority; //node->int (W)
1.31 -};
1.32 -
1.33 -
1.34 -
1.35 -
1.36 -class IGraph
1.37 -{
1.38 -public:
1.39 -
1.40 - // struct NodeType {bfs_node_data<TestGraph> bfs;};
1.41 - struct NodeType {bool isVis;};
1.42 -
1.43 - vector<NodeType> nodes;
1.44 -
1.45 - class NodeIterator
1.46 - {
1.47 - public:
1.48 - IGraph *G;
1.49 - int n;
1.50 - NodeIterator &operator ++() { n++; return *this;}
1.51 - NodeType &operator *() const { return G->nodes[n];}
1.52 - NodeType *operator ->() const { return &(G->nodes[n]);}
1.53 - bool isValid() const {return n<=5000;}
1.54 - int Index() {return n;} //csak a kiirashoz kell
1.55 - };
1.56 -
1.57 - void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
1.58 -
1.59 - class OutEdgeIterator
1.60 - {
1.61 - public:
1.62 - IGraph *G;
1.63 - int f,t;
1.64 - int gcd() { int a=f;int b=t;int c;while(c=a%b) {a=b;b=c;} ; return b;}
1.65 - OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
1.66 - bool isValid() const {return t<=5000;}
1.67 - NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
1.68 - NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
1.69 - NodeIterator Anode() const {return From();}
1.70 - NodeIterator Bnode() const {return To();}
1.71 - };
1.72 -
1.73 - typedef OutEdgeIterator EdgeIterator;
1.74 - void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
1.75 - {i.G=this;i.f=n.n;i.t=0;++i;}
1.76 -
1.77 - IGraph() : nodes(5000) {}
1.78 -};
1.79 -
1.80 -class IMaps_t
1.81 -{
1.82 -public:
1.83 -// class_element_map<IGraph::NodeIterator,
1.84 -// IGraph::NodeType,
1.85 -// bool,
1.86 -// &IGraph::NodeType::isVis> visited;
1.87 - struct _visited_map_t {
1.88 - typedef bool value_type;
1.89 - void Set(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
1.90 - value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
1.91 - } visited;
1.92 - struct _tree_map_t {
1.93 - typedef IGraph::EdgeIterator value_type;
1.94 - void Set(const IGraph::NodeIterator &n,const value_type &t)
1.95 - { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
1.96 - } tree;
1.97 - do_nothing_map dist; //node->int (W)
1.98 - do_nothing_map priority; //node->int (W)
1.99 -};
1.100 -
1.101 -void main()
1.102 +int main()
1.103 {
1.104 TestGraph G;
1.105 - TestGraph::NodeIterator n,m,o,p,q;
1.106 - TestGraph::OutEdgeIterator e,f,g,h;
1.107 - int i,j,k;
1.108 + TestGraph::NodeIterator n,m;
1.109 + TestGraph::OutEdgeIterator e;
1.110 + int i;
1.111
1.112
1.113 //for(i=1;i<=10;i++) G.AddNode().n=i; //Ez nagyon rossz!!!!!!!!
1.114 @@ -169,11 +75,11 @@
1.115 if(n!=m) G.AddEdge(n,m)->id=++i;
1.116
1.117 ;
1.118 - for(n=G.First();n.isValid();++n)
1.119 + for(n=G.First();n.isValid();++n) //Demo
1.120 {
1.121 e=G.First(n);
1.122 while(e.isValid())
1.123 - if((e->id)%2) G.Delete(e++);
1.124 + if((e->id)%2) G.Delete(e++); //it may be nice to have a postfix ++
1.125 else ++e;
1.126 }
1.127
1.128 @@ -192,26 +98,40 @@
1.129 cout << '\n';
1.130 }
1.131
1.132 - n=G.First();
1.133 -
1.134 -
1.135 - //G.Clean();
1.136 -
1.137 - cout << "\n\n\n BFS \n\n\n";
1.138 - //my_bfs_maps Maps;
1.139 - // bfs_static_maps<TestGraph> Maps(&NodeData::bfs);
1.140 + // For Marci's sake
1.141
1.142 - /// bfs(G,n,Maps);
1.143 -
1.144 - cout << '\n';
1.145 -
1.146 - IGraph IG;
1.147 - IMaps_t IMaps;
1.148 -
1.149 - IGraph::NodeIterator in;
1.150 - IG.GetFirst(in);
1.151 - ++in;
1.152 - bfs(IG,in,IMaps);
1.153 -
1.154 -
1.155 + {
1.156 + G.Clean();
1.157 +
1.158 + for(int i=1;i<=10;i++) G.AddNode()->id=i;
1.159 +
1.160 +
1.161 + { //I would'n say I'm really happy with this.
1.162 + int i;
1.163 + for(TestGraph::NodeIterator n(G);n.isValid();n++)
1.164 + for(TestGraph::NodeIterator m(G);m.isValid();++m)
1.165 + if(n!=m) G.AddEdge(n,m)->id=++i;
1.166 + }
1.167 +
1.168 + for(TestGraph::NodeIterator n(G);n.isValid();++n) //Demo
1.169 + {
1.170 + TestGraph::OutEdgeIterator e(G,n);
1.171 + while(e.isValid())
1.172 + if((e->id)%2) G.Delete(e++); //it may be nice to have a postfix ++
1.173 + else ++e;
1.174 + }
1.175 +
1.176 + for(TestGraph::AllEdgeIterator a(G);a.isValid();++a)
1.177 + cout << a->id << ": " << a.From()->id << "->" << a.To()->id << " ";
1.178 +
1.179 + cout << "\n\n\n";
1.180 +
1.181 + for(TestGraph::NodeIterator n(G);n.isValid();++n)
1.182 + {
1.183 + cout << n->id << "->";
1.184 + for(TestGraph::OutEdgeIterator e(G,n);e.isValid();++e)
1.185 + cout << e->id << ":" << e.To()->id << ' ';
1.186 + cout << '\n';
1.187 + }
1.188 + }
1.189 }