1.1 --- a/src/include/bfs.h Thu Dec 11 07:24:53 2003 +0000
1.2 +++ b/src/include/bfs.h Sat Dec 13 15:44:50 2003 +0000
1.3 @@ -38,14 +38,14 @@
1.4 // };
1.5
1.6
1.7 -// Nem jo! Osszeakad a masik Set-tel
1.8 +// Nem jo! Osszeakad a masik Put-tel
1.9 // class do_nothing_map {};
1.10 // template <typename V,typename T>
1.11 -// void Set(const do_nothing_map &p,const V &v,const T &t) {}
1.12 +// void Put(const do_nothing_map &p,const V &v,const T &t) {}
1.13
1.14 struct do_nothing_map {
1.15 template <typename V,typename T>
1.16 - static void Set(V v,T t) {}
1.17 + static void Put(V v,T t) {}
1.18 };
1.19
1.20
1.21 @@ -53,23 +53,23 @@
1.22 class class_element_map {
1.23 public:
1.24 typedef T value_type;
1.25 - static void Set(const I &i, const T &t) {(*i).*M=t;}
1.26 + static void Put(const I &i, const T &t) {(*i).*M=t;}
1.27 static T Get(const I i) {return (*i).*M;}
1.28 T &operator[](I i) {return (*i).*M;}
1.29 };
1.30
1.31 /*
1.32 template <typename C,typename I,typename T, T C::*M>
1.33 - void Set(class_element_map<C,T,M> p,I i, T t)
1.34 + void Put(class_element_map<C,T,M> p,I i, T t)
1.35 {
1.36 i->*M=t;
1.37 };
1.38 */
1.39
1.40 template <typename P,typename I,typename T>
1.41 - inline void Set(P &p,const I &i, const T &t)
1.42 + inline void Put(P &p,const I &i, const T &t)
1.43 {
1.44 - p.Set(i,t);
1.45 + p.Put(i,t);
1.46 };
1.47 template <typename P,typename I>
1.48 inline typename P::value_type Get(const P &p,const I &i)
1.49 @@ -125,7 +125,7 @@
1.50 public:
1.51 bfs_node_data<G> NodeType::*d;
1.52 typedef bool value_type;
1.53 - void Set(typename G::NodeIterator &i, const value_type &t)
1.54 + void Put(typename G::NodeIterator &i, const value_type &t)
1.55 {((*i).*d).visited=t;}
1.56 value_type Get(const typename G::NodeIterator &i) const
1.57 {return ((*i).*d).visited;}
1.58 @@ -136,7 +136,7 @@
1.59 public:
1.60 bfs_node_data<G> NodeType::*d;
1.61 typedef typename G::EdgeIterator value_type;
1.62 - void Set(typename G::NodeIterator &i, const value_type &t)
1.63 + void Put(typename G::NodeIterator &i, const value_type &t)
1.64 {((*i).*d).tree=t;}
1.65 value_type Get(const typename G::NodeIterator &i) const
1.66 {return ((*i).*d).tree;}
1.67 @@ -147,7 +147,7 @@
1.68 public:
1.69 bfs_node_data<G> NodeType::*d;
1.70 typedef int value_type;
1.71 - void Set(typename G::NodeIterator &i, const value_type &t)
1.72 + void Put(typename G::NodeIterator &i, const value_type &t)
1.73 {((*i).*d).dist=t;}
1.74 value_type Get(const typename G::NodeIterator &i) const
1.75 {return ((*i).*d).dist;}
1.76 @@ -158,7 +158,7 @@
1.77 public:
1.78 bfs_node_data<G> NodeType::*d;
1.79 typedef int value_type;
1.80 - void Set(typename G::NodeIterator &i, const value_type &t)
1.81 + void Put(typename G::NodeIterator &i, const value_type &t)
1.82 {((*i).*d).priority=t;}
1.83 value_type Get(const typename G::NodeIterator &i) const
1.84 {return ((*i).*d).priority;}
1.85 @@ -175,7 +175,7 @@
1.86
1.87 bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
1.88 {
1.89 - SetDataField(dd);
1.90 + PutDataField(dd);
1.91 }
1.92
1.93 bfs_static_maps(const bfs_static_maps<G> &B)
1.94 @@ -210,17 +210,17 @@
1.95 int d;
1.96
1.97 for(Gr.GetFirst(n);n.isValid();++n)
1.98 - Set(maps.visited,n,false);
1.99 + Put(maps.visited,n,false);
1.100
1.101 queue<Q_T> Q;
1.102
1.103 q.n=start_node;
1.104 q.dist=0;
1.105 Q.push(q);
1.106 - Set(maps.visited,start_node,true);
1.107 - // Set(maps::tree,start_node,?????);
1.108 - Set(maps.dist,start_node,0);
1.109 - Set(maps.priority,start_node,pr++);
1.110 + Put(maps.visited,start_node,true);
1.111 + // Put(maps::tree,start_node,?????);
1.112 + Put(maps.dist,start_node,0);
1.113 + Put(maps.priority,start_node,pr++);
1.114
1.115 do {
1.116 n=Q.front().n;d=Q.front().dist+1;
1.117 @@ -230,10 +230,10 @@
1.118 q.n=m;
1.119 q.dist=d;
1.120 Q.push(q);
1.121 - Set(maps.visited,m,true);
1.122 - Set(maps.tree,m,e);
1.123 - Set(maps.dist,m,d);
1.124 - Set(maps.priority,m,pr++);
1.125 + Put(maps.visited,m,true);
1.126 + Put(maps.tree,m,e);
1.127 + Put(maps.dist,m,d);
1.128 + Put(maps.priority,m,pr++);
1.129 }
1.130 } while(!Q.empty());
1.131 };
2.1 --- a/src/include/graph.h Thu Dec 11 07:24:53 2003 +0000
2.2 +++ b/src/include/graph.h Sat Dec 13 15:44:50 2003 +0000
2.3 @@ -57,6 +57,8 @@
2.4 public:
2.5
2.6 NodeIterator() {;}
2.7 + NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
2.8 + {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
2.9 NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
2.10
2.11 NodeIterator &GoNext() { n=G->NextNode(n); return *this;}
2.12 @@ -148,6 +150,10 @@
2.13 //Ne a BiEdgeIterator-bol szarmazzon?
2.14 {
2.15 public:
2.16 + InEdgeIterator() {}
2.17 + InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)
2.18 + { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
2.19 +
2.20 InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
2.21 InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
2.22 InEdgeIterator &operator++() { return GoNext();}
2.23 @@ -169,6 +175,10 @@
2.24 class OutEdgeIterator : public EdgeIterator
2.25 {
2.26 public:
2.27 + OutEdgeIterator() {}
2.28 + OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
2.29 + { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
2.30 +
2.31 OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
2.32 OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
2.33 OutEdgeIterator &operator++() { return GoNext();}
2.34 @@ -192,6 +202,10 @@
2.35 NodeIterator n; // Itt ketszer van a G
2.36
2.37 public:
2.38 + SymEdgeIterator() {}
2.39 + SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)
2.40 + { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }
2.41 +
2.42 SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
2.43 SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
2.44 SymEdgeIterator &operator++() { return GoNext();}
2.45 @@ -216,6 +230,12 @@
2.46 NodeIterator n; // Itt ketszer van a G
2.47
2.48 public:
2.49 + AllEdgeIterator() {}
2.50 + AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)
2.51 + {
2.52 + e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
2.53 + }
2.54 +
2.55 AllEdgeIterator &GoNext()
2.56 {
2.57 e=e->NextOut();
2.58 @@ -248,7 +268,7 @@
2.59 typedef InEdgeIterator DeletingInEdgeIterator;
2.60 typedef SymEdgeIterator DeletingSymEdgeIterator;
2.61
2.62 - const NodeIterator &FirstNode()
2.63 + const NodeIterator FirstNode()
2.64 {
2.65 NodeIterator i;
2.66 i.G=this;i.n=OldGraph<N,E>::FirstNode();
2.67 @@ -284,19 +304,19 @@
2.68
2.69
2.70 //Vagy beginnode()?
2.71 - const DeletingEdgeIterator &FirstOut(const NodeIterator &n)
2.72 + const DeletingEdgeIterator FirstOut(const NodeIterator &n)
2.73 {
2.74 EdgeIterator i;
2.75 i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
2.76 return i;
2.77 }
2.78 - const DeletingEdgeIterator &FirstIn(const NodeIterator &n)
2.79 + const DeletingEdgeIterator FirstIn(const NodeIterator &n)
2.80 {
2.81 EdgeIterator i;
2.82 i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
2.83 return i;
2.84 }
2.85 - const DeletingSymEdgeIterator &FirstSym(const NodeIterator &n)
2.86 + const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)
2.87 {
2.88 EdgeIterator i;
2.89 i.G=n.G;i.n=n.n;
2.90 @@ -368,7 +388,7 @@
2.91 void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
2.92
2.93 int NodeNum() { OldGraph<N,E>::NodeNum(); }
2.94 - int Clean() { OldGraph<N,E>::Clean(); }
2.95 + void Clean() { OldGraph<N,E>::Clean(); }
2.96
2.97 Graph() : _FST(this) {}
2.98 };
3.1 --- a/src/include/oldgraph.h Thu Dec 11 07:24:53 2003 +0000
3.2 +++ b/src/include/oldgraph.h Sat Dec 13 15:44:50 2003 +0000
3.3 @@ -111,51 +111,52 @@
3.4 public:
3.5 int NodeNum() {return nodenum;};
3.6 int EdgeNum();
3.7 - int MaxNode() {return nodes_size;};
3.8 - int FirstNode() {return firstnode;};
3.9 - int NextNode(int n) {return nodes[n].next;};
3.10 - int PrevNode(int n) {return nodes[n].prev;};
3.11 - N& operator()(int n) {return *(N*)(nodes[n].data);};
3.12 - N& Data (int n) {return *(N*)(nodes[n].data);};
3.13 + int MaxNode() const {return nodes_size;};
3.14 + int FirstNode() const {return firstnode;};
3.15 + int NextNode(int n) const {return nodes[n].next;};
3.16 + int PrevNode(int n) const {return nodes[n].prev;};
3.17 + N& operator()(int n) const {return *(N*)(nodes[n].data);};
3.18 + N& Data (int n) const {return *(N*)(nodes[n].data);};
3.19 int AddNode();
3.20 - void AddNodeBlock(int n) {for(int i=0;i<n;i++) AddNode();}
3.21 + void AddNodeBlock(int n) const {for(int i=0;i<n;i++) AddNode();}
3.22 int AddNode(int n);
3.23 void Delete(int n);
3.24 - int isaNode(int n) {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
3.25 + int isaNode(int n) const
3.26 + {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
3.27
3.28 - int InDeg(int n) {return nodes[n].indeg;};
3.29 - int OutDeg(int n) {return nodes[n].outdeg;};
3.30 - EdgePoint FirstIn(int n) {return nodes[n].firstin;};
3.31 - EdgePoint FirstOut(int n) {return nodes[n].firstout;};
3.32 + int InDeg(int n) const {return nodes[n].indeg;};
3.33 + int OutDeg(int n) const {return nodes[n].outdeg;};
3.34 + EdgePoint FirstIn(int n) const {return nodes[n].firstin;};
3.35 + EdgePoint FirstOut(int n) const {return nodes[n].firstout;};
3.36
3.37 - E& operator()(EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
3.38 - E& Data (EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
3.39 - int From(EdgePoint e) {return e->from;};
3.40 - int To(EdgePoint e) {return e->to;};
3.41 - EdgePoint NextIn(EdgePoint e)
3.42 + E& operator()(EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
3.43 + E& Data (EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
3.44 + int From(EdgePoint e) const {return e->from;};
3.45 + int To(EdgePoint e) const {return e->to;};
3.46 + EdgePoint NextIn(EdgePoint e) const
3.47 {return e->nextin;};
3.48 - EdgePoint NextOut(EdgePoint e)
3.49 + EdgePoint NextOut(EdgePoint e)const
3.50 {return e->nextout;};
3.51 EdgePoint AddEdge(int f, int t);
3.52 void Delete(EdgePoint e);
3.53 EdgePoint Edge(int f,int t);
3.54 // EdgePoint Edge(E &d)
3.55 // {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};
3.56 - E& operator()(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
3.57 - E& Data(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
3.58 + E& operator()(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
3.59 + E& Data(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
3.60 void Delete(int f, int t) {Delete(Edge(f,t));};
3.61 void Reverse(EdgePoint e);
3.62
3.63 // Functions for EdgeIndex
3.64
3.65 - EdgePoint Edge(EdgeIndex i)
3.66 + EdgePoint Edge(EdgeIndex i) const
3.67 { return (EdgePoint)(edges[i.block]->fields+i.index);};
3.68 - EdgeIndex Index(EdgePoint e) { return e->index;};
3.69 - EdgeIndex Index(int f, int t) { EdgePoint e; return Edge(f,t)->index; }
3.70 + EdgeIndex Index(EdgePoint e) const { return e->index;};
3.71 + EdgeIndex Index(int f, int t) const { EdgePoint e; return Edge(f,t)->index; }
3.72 void Delete(EdgeIndex i) { Delete(Edge(i));};
3.73 - E& operator()(EdgeIndex i)
3.74 + E& operator()(EdgeIndex i) const
3.75 {return *(E*)(edges[i.block]->fields[i.index].data);};
3.76 - E& Data(EdgeIndex i)
3.77 + E& Data(EdgeIndex i) const
3.78 {return *(E*)(edges[i.block]->fields[i.index].data);};
3.79 EdgePoint AddEdge(int f, int t,EdgeIndex in);
3.80
3.81 @@ -163,11 +164,11 @@
3.82
3.83 // Operators for symmetric graphs:
3.84
3.85 - EdgePoint FirstEdge(int n)
3.86 + EdgePoint FirstEdge(int n) const
3.87 { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};
3.88 - EdgePoint NextEdge(int n,EdgePoint e)
3.89 + EdgePoint NextEdge(int n,EdgePoint e) const
3.90 { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };
3.91 - int Opposite(EdgePoint e,int n)
3.92 + int Opposite(EdgePoint e,int n) const
3.93 { return From(e)+To(e)-n; };
3.94
3.95 // Initializers, destructors
3.96 @@ -222,7 +223,6 @@
3.97
3.98 template<class N, class E> void OldGraph<N,E>::destroy()
3.99 {
3.100 - edge_block *oe;
3.101 int i;
3.102
3.103 while(firstnode!=INVALID) Delete(firstnode);
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/bfsdemo.cc Sat Dec 13 15:44:50 2003 +0000
4.3 @@ -0,0 +1,83 @@
4.4 +#include <iostream>
4.5 +#include <graph.h>
4.6 +#include <bfs.h>
4.7 +
4.8 +using namespace NEGRO;
4.9 +using namespace std;
4.10 +
4.11 +class IGraph
4.12 +{
4.13 +public:
4.14 +
4.15 + // struct NodeType {bfs_node_data<TestGraph> bfs;};
4.16 + struct NodeType {bool isVis;};
4.17 +
4.18 + vector<NodeType> nodes;
4.19 +
4.20 + class NodeIterator
4.21 + {
4.22 + public:
4.23 + IGraph *G;
4.24 + int n;
4.25 + NodeIterator &operator ++() { n++; return *this;}
4.26 + NodeType &operator *() const { return G->nodes[n];}
4.27 + NodeType *operator ->() const { return &(G->nodes[n]);}
4.28 + bool isValid() const {return n<=5000;}
4.29 + int Index() {return n;} //csak a kiirashoz kell
4.30 + };
4.31 +
4.32 + void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
4.33 +
4.34 + class OutEdgeIterator
4.35 + {
4.36 + public:
4.37 + IGraph *G;
4.38 + int f,t;
4.39 + int gcd() { int a=f;int b=t;int c;while((c=a%b)) {a=b;b=c;} ; return b;}
4.40 + OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
4.41 + bool isValid() const {return t<=5000;}
4.42 + NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
4.43 + NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
4.44 + NodeIterator Anode() const {return From();}
4.45 + NodeIterator Bnode() const {return To();}
4.46 + };
4.47 +
4.48 + typedef OutEdgeIterator EdgeIterator;
4.49 + void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
4.50 + {i.G=this;i.f=n.n;i.t=0;++i;}
4.51 +
4.52 + IGraph() : nodes(5001) {}
4.53 +};
4.54 +
4.55 +class IMaps_t
4.56 +{
4.57 +public:
4.58 +// class_element_map<IGraph::NodeIterator,
4.59 +// IGraph::NodeType,
4.60 +// bool,
4.61 +// &IGraph::NodeType::isVis> visited;
4.62 + struct _visited_map_t {
4.63 + typedef bool value_type;
4.64 + void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
4.65 + value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
4.66 + } visited;
4.67 + struct _tree_map_t {
4.68 + typedef IGraph::EdgeIterator value_type;
4.69 + void Put(const IGraph::NodeIterator &n,const value_type &t)
4.70 + { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
4.71 + } tree;
4.72 + do_nothing_map dist; //node->int (W)
4.73 + do_nothing_map priority; //node->int (W)
4.74 +};
4.75 +
4.76 +
4.77 +int main()
4.78 +{
4.79 + IGraph IG;
4.80 + IMaps_t IMaps;
4.81 +
4.82 + IGraph::NodeIterator in;
4.83 + IG.GetFirst(in);
4.84 + ++in;
4.85 + bfs(IG,in,IMaps);
4.86 +}
5.1 --- a/src/work/graphdemo.cc Thu Dec 11 07:24:53 2003 +0000
5.2 +++ b/src/work/graphdemo.cc Sat Dec 13 15:44:50 2003 +0000
5.3 @@ -26,106 +26,12 @@
5.4
5.5 typedef Graph<NodeData,EdgeData> TestGraph;
5.6
5.7 -/*
5.8 -struct isVis_map {};
5.9 -bool Get(isVis_map p,TestGraph::NodeIterator i) { return i->isVis;}
5.10 -void Set(isVis_map p,TestGraph::NodeIterator i,bool b) { i->isVis=b;}
5.11 -*/
5.12 -
5.13 -class my_bfs_maps
5.14 -{
5.15 -public:
5.16 - //isVis_map visited; //node->bool (RW)
5.17 - class_element_map<TestGraph::NodeIterator,
5.18 - TestGraph::NodeType,
5.19 - bool,
5.20 - &NodeData::isVis> visited;
5.21 - struct _tree_map_t {
5.22 - typedef TestGraph::EdgeIterator value_type;
5.23 - void Set(const TestGraph::NodeIterator &n,const value_type &t)
5.24 - {
5.25 - cout << t.From()->id << "->" << t.To()->id << '\n';
5.26 - }
5.27 - } tree;
5.28 - do_nothing_map dist; //node->int (W)
5.29 - do_nothing_map priority; //node->int (W)
5.30 - //priority_map priority; //node->int (W)
5.31 -};
5.32 -
5.33 -
5.34 -
5.35 -
5.36 -class IGraph
5.37 -{
5.38 -public:
5.39 -
5.40 - // struct NodeType {bfs_node_data<TestGraph> bfs;};
5.41 - struct NodeType {bool isVis;};
5.42 -
5.43 - vector<NodeType> nodes;
5.44 -
5.45 - class NodeIterator
5.46 - {
5.47 - public:
5.48 - IGraph *G;
5.49 - int n;
5.50 - NodeIterator &operator ++() { n++; return *this;}
5.51 - NodeType &operator *() const { return G->nodes[n];}
5.52 - NodeType *operator ->() const { return &(G->nodes[n]);}
5.53 - bool isValid() const {return n<=5000;}
5.54 - int Index() {return n;} //csak a kiirashoz kell
5.55 - };
5.56 -
5.57 - void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
5.58 -
5.59 - class OutEdgeIterator
5.60 - {
5.61 - public:
5.62 - IGraph *G;
5.63 - int f,t;
5.64 - int gcd() { int a=f;int b=t;int c;while(c=a%b) {a=b;b=c;} ; return b;}
5.65 - OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
5.66 - bool isValid() const {return t<=5000;}
5.67 - NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
5.68 - NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
5.69 - NodeIterator Anode() const {return From();}
5.70 - NodeIterator Bnode() const {return To();}
5.71 - };
5.72 -
5.73 - typedef OutEdgeIterator EdgeIterator;
5.74 - void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
5.75 - {i.G=this;i.f=n.n;i.t=0;++i;}
5.76 -
5.77 - IGraph() : nodes(5000) {}
5.78 -};
5.79 -
5.80 -class IMaps_t
5.81 -{
5.82 -public:
5.83 -// class_element_map<IGraph::NodeIterator,
5.84 -// IGraph::NodeType,
5.85 -// bool,
5.86 -// &IGraph::NodeType::isVis> visited;
5.87 - struct _visited_map_t {
5.88 - typedef bool value_type;
5.89 - void Set(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
5.90 - value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
5.91 - } visited;
5.92 - struct _tree_map_t {
5.93 - typedef IGraph::EdgeIterator value_type;
5.94 - void Set(const IGraph::NodeIterator &n,const value_type &t)
5.95 - { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
5.96 - } tree;
5.97 - do_nothing_map dist; //node->int (W)
5.98 - do_nothing_map priority; //node->int (W)
5.99 -};
5.100 -
5.101 -void main()
5.102 +int main()
5.103 {
5.104 TestGraph G;
5.105 - TestGraph::NodeIterator n,m,o,p,q;
5.106 - TestGraph::OutEdgeIterator e,f,g,h;
5.107 - int i,j,k;
5.108 + TestGraph::NodeIterator n,m;
5.109 + TestGraph::OutEdgeIterator e;
5.110 + int i;
5.111
5.112
5.113 //for(i=1;i<=10;i++) G.AddNode().n=i; //Ez nagyon rossz!!!!!!!!
5.114 @@ -169,11 +75,11 @@
5.115 if(n!=m) G.AddEdge(n,m)->id=++i;
5.116
5.117 ;
5.118 - for(n=G.First();n.isValid();++n)
5.119 + for(n=G.First();n.isValid();++n) //Demo
5.120 {
5.121 e=G.First(n);
5.122 while(e.isValid())
5.123 - if((e->id)%2) G.Delete(e++);
5.124 + if((e->id)%2) G.Delete(e++); //it may be nice to have a postfix ++
5.125 else ++e;
5.126 }
5.127
5.128 @@ -192,26 +98,40 @@
5.129 cout << '\n';
5.130 }
5.131
5.132 - n=G.First();
5.133 -
5.134 -
5.135 - //G.Clean();
5.136 -
5.137 - cout << "\n\n\n BFS \n\n\n";
5.138 - //my_bfs_maps Maps;
5.139 - // bfs_static_maps<TestGraph> Maps(&NodeData::bfs);
5.140 + // For Marci's sake
5.141
5.142 - /// bfs(G,n,Maps);
5.143 -
5.144 - cout << '\n';
5.145 -
5.146 - IGraph IG;
5.147 - IMaps_t IMaps;
5.148 -
5.149 - IGraph::NodeIterator in;
5.150 - IG.GetFirst(in);
5.151 - ++in;
5.152 - bfs(IG,in,IMaps);
5.153 -
5.154 -
5.155 + {
5.156 + G.Clean();
5.157 +
5.158 + for(int i=1;i<=10;i++) G.AddNode()->id=i;
5.159 +
5.160 +
5.161 + { //I would'n say I'm really happy with this.
5.162 + int i;
5.163 + for(TestGraph::NodeIterator n(G);n.isValid();n++)
5.164 + for(TestGraph::NodeIterator m(G);m.isValid();++m)
5.165 + if(n!=m) G.AddEdge(n,m)->id=++i;
5.166 + }
5.167 +
5.168 + for(TestGraph::NodeIterator n(G);n.isValid();++n) //Demo
5.169 + {
5.170 + TestGraph::OutEdgeIterator e(G,n);
5.171 + while(e.isValid())
5.172 + if((e->id)%2) G.Delete(e++); //it may be nice to have a postfix ++
5.173 + else ++e;
5.174 + }
5.175 +
5.176 + for(TestGraph::AllEdgeIterator a(G);a.isValid();++a)
5.177 + cout << a->id << ": " << a.From()->id << "->" << a.To()->id << " ";
5.178 +
5.179 + cout << "\n\n\n";
5.180 +
5.181 + for(TestGraph::NodeIterator n(G);n.isValid();++n)
5.182 + {
5.183 + cout << n->id << "->";
5.184 + for(TestGraph::OutEdgeIterator e(G,n);e.isValid();++e)
5.185 + cout << e->id << ":" << e.To()->id << ' ';
5.186 + cout << '\n';
5.187 + }
5.188 + }
5.189 }
6.1 --- a/src/work/makefile Thu Dec 11 07:24:53 2003 +0000
6.2 +++ b/src/work/makefile Sat Dec 13 15:44:50 2003 +0000
6.3 @@ -1,3 +1,20 @@
6.4 -graphdemo: graphdemo.cc ../include/graph.h ../include/bfs.h \
6.5 +CXXFLAGS=-g -Wall -I../include
6.6 +
6.7 +none:
6.8 + @echo 'Please use one of these forms:'
6.9 + @echo ' make all'
6.10 + @echo ' make clean'
6.11 + @echo ' make graphdemo'
6.12 + @echo ' make bfsdemo'
6.13 +
6.14 +all: graphdemo bfsdemo
6.15 +
6.16 +clean:
6.17 + rm graphdemo bfsdemo
6.18 +graphdemo: graphdemo.cc ../include/graph.h \
6.19 ../include/oldgraph.h makefile
6.20 - g++ -g -I../include -o graphdemo graphdemo.cc
6.21 + g++ $(CXXFLAGS) -o graphdemo graphdemo.cc
6.22 +
6.23 +bfsdemo: bfsdemo.cc ../include/graph.h ../include/bfs.h \
6.24 + ../include/oldgraph.h makefile
6.25 + g++ $(CXXFLAGS) -o bfsdemo bfsdemo.cc