Changeset 986:e997802b855c in lemon-0.x for src/work/alpar
- Timestamp:
- 11/13/04 13:53:28 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1376
- Location:
- src/work/alpar
- Files:
-
- 10 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/alpar/bfs-named-param.cc
r945 r986 11 11 struct _BFS_CUSTOM_VIS {}; 12 12 13 template<class GT,class VT,class DVT,class PNT,class PET,class PT > 14 class _BFS 13 14 class _Bfs_Traits 15 { 16 typedef ListGraph Graph; 17 } 18 19 template<class T> 20 class _Bfs 15 21 { 16 22 public: 17 typedef GT Graph; 18 typedef VT Visited; 19 typedef PNT PredNode; 20 typedef PET PredEdge; 21 typedef PT Priority; 22 // typedef QDT QueueData; 23 typedef typename T::Graph Graph; 24 typedef typename T::Reached Reached; 25 typedef typename T::PredNode PredNode; 26 typedef typename T::PredEdge PredEdge; 27 typedef typename T::Priority Priority; 28 29 typedef typename T::DefaultReachedTag DefaultReachedTag; 23 30 24 31 typedef typename Graph::Node Node; 25 32 typedef typename Graph::OutEdgeIt OutEdgeIt; 26 33 27 typedef DVT DefaultVisitedTag;28 29 34 const Graph &_graph; 30 35 31 36 Node _source; 32 37 33 Visited *_visited;38 Reached *_visited; 34 39 PredNode _predNode; 35 40 PredEdge _predEdge; 36 41 Priority _priority; 37 42 38 _B FS(const Graph &g,43 _Bfs(const Graph &g, 39 44 Node s, 40 Visited *v,45 Reached *v, 41 46 PredNode &pn, 42 47 PredEdge &pe, … … 46 51 47 52 48 int run(const _B FS_CUSTOM_VIS &)53 int run(const _Bfs_CUSTOM_VIS &) 49 54 { 50 55 using namespace std; … … 64 69 Node n=Q[Qt++]; 65 70 for(OutEdgeIt e(_graph,n);e!=INVALID;++e) 66 if(!(*_visited)[m=_graph. head(e)]) {71 if(!(*_visited)[m=_graph.target(e)]) { 67 72 Q[Qh++]=m; 68 73 _visited->set(m,true); … … 76 81 int run(const _BFS_DEFAULT_VIS &) 77 82 { 78 _visited= new Visited(_graph);83 _visited= new Reached(_graph); 79 84 int r = run(_BFS_CUSTOM_VIS()); 80 85 delete _visited; 81 86 return r; 82 87 } 83 int run() { return run(Default VisitedTag());}84 85 template<class T> _B FS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>88 int run() { return run(DefaultReachedTag());} 89 90 template<class T> _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> 86 91 setVisitMap(T &t) 87 92 { 88 return _B FS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>93 return _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> 89 94 (_graph,_source,&t,_predNode,_predEdge,_priority); 90 95 } 91 96 92 97 template<class T> 93 _B FS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>98 _Bfs<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority> 94 99 setPredNodeMap(T &t) 95 100 { 96 return _BFS<Graph, Visited,DefaultVisitedTag,T,PredEdge,Priority>101 return _BFS<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority> 97 102 (_graph,_source, 98 103 _visited, … … 101 106 102 107 template<class T> 103 _BFS<Graph, Visited,DefaultVisitedTag,PredNode,T,Priority>108 _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority> 104 109 setPredEdgeMap(T &t) 105 110 { 106 return _BFS<Graph, Visited,DefaultVisitedTag,PredNode,T,Priority>111 return _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority> 107 112 (_graph,_source, 108 113 _visited, … … 110 115 } 111 116 112 _B FS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>117 _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> 113 118 setNothing() 114 119 { 115 return _B FS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>120 return _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> 116 121 (_graph,_source, 117 122 _visited, … … 122 127 123 128 template<class G> 124 _B FS<G,129 _Bfs<G, 125 130 typename G::template NodeMap<bool>, 126 131 _BFS_DEFAULT_VIS, … … 132 137 // typename G::template NodeMap<bool> v(g); 133 138 134 return _B FS< G,139 return _Bfs < G, 135 140 typename G::template NodeMap<bool>, 136 141 _BFS_DEFAULT_VIS, … … 147 152 148 153 149 class My VisitedMap : public SmartGraph::NodeMap<bool>154 class MyReachedMap : public SmartGraph::NodeMap<bool> 150 155 { 151 156 const SmartGraph &_G; 152 157 public: 153 My VisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}158 MyReachedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {} 154 159 void set(SmartGraph::Node n,bool b) 155 160 { … … 181 186 SmartGraph::NodeMap<SmartGraph::Edge> em(G); 182 187 183 My VisitedMap vm(G);188 MyReachedMap vm(G); 184 189 185 190 -
src/work/alpar/boolmap_iter.cc
r921 r986 120 120 121 121 for(EdgeIt e(G);G.valid(e);G.next(e)) 122 std::cout << G.id(G. tail(e)) << "->" << G.id(G.head(e))122 std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) 123 123 << ": " << map[e] << '\n'; 124 124 std::cout << "True Edges:\n"; 125 125 for(BoolIterEdgeMap<Graph>::TrueIterator i(map);i;++i) 126 std::cout << G.id(G. tail(i)) << "->" << G.id(G.head(i)) << '\n';126 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; 127 127 std::cout << "False Edges:\n"; 128 128 for(BoolIterEdgeMap<Graph>::FalseIterator i(map);i;++i) 129 std::cout << G.id(G. tail(i)) << "->" << G.id(G.head(i)) << '\n';129 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; 130 130 } 131 131 -
src/work/alpar/dijkstra.h
r967 r986 394 394 395 395 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { 396 Node w=G-> head(e);396 Node w=G->target(e); 397 397 switch(heap.state(w)) { 398 398 case Heap::PRE_HEAP: -
src/work/alpar/f_ed_ka.h
r921 r986 85 85 c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t)); 86 86 //FIXME: I would need 'G.opposite(e,n)' 87 gn = visited.get(t)==1 ? G. tail(tree.get(t)) : G.head(tree.get(t));87 gn = visited.get(t)==1 ? G.source(tree.get(t)) : G.target(tree.get(t)); 88 88 while(gn!=s) if(visited.get(gn)==1) 89 89 { 90 90 //FIXME: nonstandard gcc extension! 91 91 aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn)); 92 gn=G. tail(tree.get(gn));92 gn=G.source(tree.get(gn)); 93 93 } 94 94 else { 95 95 //FIXME: nonstandard gcc extension! 96 96 aug_val <?= f.get(tree.get(gn)); 97 gn=G. head(tree.get(gn));97 gn=G.target(tree.get(gn)); 98 98 } 99 99 … … 103 103 { 104 104 f.set(tree.get(gn),f.get(tree.get(gn))+aug_val); 105 gn=G. tail(tree.get(gn));105 gn=G.source(tree.get(gn)); 106 106 } 107 107 else { 108 108 f.set(tree.get(gn),f.get(tree.get(gn))-aug_val); 109 gn=G. head(tree.get(gn));109 gn=G.target(tree.get(gn)); 110 110 } 111 111 -
src/work/alpar/f_ed_ka_demo.cc
r921 r986 42 42 //std::cout << "maximum flow: "<< std::endl; 43 43 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 44 // std::cout<<"("<<G. tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";44 // std::cout<<"("<<G.source(e)<< "-"<<flow.get(e)<<"->"<<G.target(e)<<") "; 45 45 //} 46 46 //std::cout<<std::endl; -
src/work/alpar/graph.h
r253 r986 107 107 // Lehet, hogy ez a ketto nem kell!!! 108 108 109 NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}110 NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}109 NodeIterator source() const {NodeIterator i;i.G=G;i.n=e->From();return i;} 110 NodeIterator target() const {NodeIterator i;i.G=G;i.n=e->To();return i;} 111 111 NodeIterator opposite(const NodeIterator &n) const 112 {return n== tail()?head():tail();}112 {return n==source()?target():source();} 113 113 114 114 bool valid() {return e;} … … 191 191 {OutEdgeIterator tmp(*this); goNext(); return tmp;} 192 192 193 NodeIterator aNode() const {return tail();}194 NodeIterator bNode() const {return head();}193 NodeIterator aNode() const {return source();} 194 NodeIterator bNode() const {return target();} 195 195 196 196 operator const InEdgeIterator () … … 219 219 220 220 NodeIterator aNode() const {return n;} 221 NodeIterator bNode() const {return n.n== tail().n?head():tail();}221 NodeIterator bNode() const {return n.n==source().n?target():source();} 222 222 223 223 operator const InEdgeIterator () … … 255 255 256 256 NodeIterator aNode() const {return n;} 257 NodeIterator bNode() const {return n.n== tail().n?head():tail();}257 NodeIterator bNode() const {return n.n==source().n?target():source();} 258 258 259 259 operator const EdgeIterator () … … 464 464 { 465 465 return n? 466 reversed[n-1]?path[n-1]. tail():path[n-1].head():467 reversed[0]?path[0]. head():path[0].tail();466 reversed[n-1]?path[n-1].source():path[n-1].target(): 467 reversed[0]?path[0].target():path[0].source(); 468 468 } 469 469 void setRevert(int n,bool r=true) {reversed[n]=r;} … … 471 471 { 472 472 path[n]=i; 473 reversed[n] = i. head()==i.aNode();473 reversed[n] = i.target()==i.aNode(); 474 474 } 475 475 void setEdge(int n,EdgeIterator i,bool r) … … 479 479 } 480 480 481 NodeIterator tail() { return getNode(0); }482 NodeIterator head() { return getNode(getLength()); }481 NodeIterator source() { return getNode(0); } 482 NodeIterator target() { return getNode(getLength()); } 483 483 }; 484 484 -
src/work/alpar/gwrapper.h
r921 r986 28 28 template<typename I> I &goNext(I &i); { return graph->goNext(i); } 29 29 30 NodeIt head(const EdgeIt &e);31 { return graph-> head(e); }32 NodeIt tail(const EdgeIt &e);33 { return graph-> tail(e); }30 NodeIt target(const EdgeIt &e); 31 { return graph->target(e); } 32 NodeIt source(const EdgeIt &e); 33 { return graph->source(e); } 34 34 35 35 template<typename I> NodeIt aNode(const I e); … … 84 84 template<typename I> I &goNext(I &i); { return graph->goNext(i); } 85 85 86 NodeIt head(const EdgeIt &e);87 { return graph-> tail(e); }88 NodeIt tail(const EdgeIt &e);89 { return graph-> head(e); }86 NodeIt target(const EdgeIt &e); 87 { return graph->source(e); } 88 NodeIt source(const EdgeIt &e); 89 { return graph->target(e); } 90 90 91 91 template<typename I> NodeIt aNode(const I e); … … 138 138 // template<typename I> I &goNext(I &i); { return graph->goNext(i); } 139 139 140 NodeIt head(const EdgeIt &e);141 { return G:: tail(e); }142 NodeIt tail(const EdgeIt &e);143 { return G:: head(e); }140 NodeIt target(const EdgeIt &e); 141 { return G::source(e); } 142 NodeIt source(const EdgeIt &e); 143 { return G::target(e); } 144 144 145 145 // template<typename I> NodeIt aNode(const I e); … … 195 195 template<typename I> I &goNext(I &i); { return graph->goNext(i); } 196 196 197 NodeIt head(const EdgeIt &e);198 { return graph-> head(e); }199 NodeIt tail(const EdgeIt &e);200 { return graph-> tail(e); }197 NodeIt target(const EdgeIt &e); 198 { return graph->target(e); } 199 NodeIt source(const EdgeIt &e); 200 { return graph->source(e); } 201 201 202 202 template<typename I> NodeIt aNode(const I e); … … 344 344 template<typename I> I next(const I i); { return graph->goNext(i); } 345 345 346 NodeIt head(const EdgeIt &e);347 { return graph-> head(e); }348 NodeIt tail(const EdgeIt &e);349 { return graph-> tail(e); }346 NodeIt target(const EdgeIt &e); 347 { return graph->target(e); } 348 NodeIt source(const EdgeIt &e); 349 { return graph->source(e); } 350 350 351 351 template<typename I> NodeIt aNode(const I e); -
src/work/alpar/list_graph_demo.cc
r959 r986 112 112 for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e); 113 113 for(EdgeIt e(G);G.valid(e);G.next(e)) 114 if(G. tail(e)<G.head(e)) sm[e]=G.id(e);114 if(G.source(e)<G.target(e)) sm[e]=G.id(e); 115 115 116 116 for(EdgeIt e(G);G.valid(e);G.next(e)) 117 std::cout << G.id(G. tail(e)) << "->" << G.id(G.head(e))117 std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) 118 118 << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e)) 119 119 << " em=" << em[e] -
src/work/alpar/rw_nonref_map.cc
r921 r986 24 24 { 25 25 ValueType tmp; 26 std::cout << G.id(G. tail(e)) << "->"27 << G.id(G. head(e)) << ": ";26 std::cout << G.id(G.source(e)) << "->" 27 << G.id(G.target(e)) << ": "; 28 28 std::cin >> tmp; 29 29 return tmp; … … 31 31 ValueType operator = (ValueType v) const 32 32 { 33 std::cout << G.id(G. tail(e)) << "->"34 << G.id(G. head(e)) << ": " << v << '\n';33 std::cout << G.id(G.source(e)) << "->" 34 << G.id(G.target(e)) << ": " << v << '\n'; 35 35 return v; 36 36 } -
src/work/alpar/smart_graph_demo.cc
r921 r986 112 112 for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e); 113 113 for(EdgeIt e(G);G.valid(e);G.next(e)) 114 if(G. tail(e)<G.head(e)) sm[e]=G.id(e);114 if(G.source(e)<G.target(e)) sm[e]=G.id(e); 115 115 116 116 for(EdgeIt e(G);G.valid(e);G.next(e)) 117 std::cout << G.id(G. tail(e)) << "->" << G.id(G.head(e))117 std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) 118 118 << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e)) 119 119 << " em=" << em[e]
Note: See TracChangeset
for help on using the changeset viewer.