1
#ifndef NETWORK_H
2#define NETWORK_H
3
4#include "map"
5#include "list"
6#include "queue"
7#include "stack"
8#include "algorithm"
9
10using namespace std;
11
12template<typename vertex, typename Compare = less<vertex> >
13class network
14
{
15
public:
16 struct vertex_weight_pair
17
{
18 vertex to;
19 double weight;
20
21 vertex_weight_pair(const vertex& x, const double& y)
22 {
23 to = x;
24 weight = y;
25
}
26
27 bool operator>(const vertex_weight_pair& p)const
28 {
29 return weight>p.weight;
30 }
31 };
32
33 typedef typename std::list<vertex_weight_pair> vertex_list_class;
34 typedef typename vertex_list_class::iterator vertex_list_iterator;
35 typedef typename std::map<vertex,vertex_list_class,Compare> map_class; //
36 typedef typename map_class::iterator map_iterator;
37
38protected:
39
40 map_class adjacency_map; //邻接表
41
42public:
43
44 class iterator;
45 friend class iterator;
46
47 /**///////////////////////////////////////////////////////////////////////////
48 class iterator
49 {
50 friend class network;
51
52 protected:
53
54 map_iterator adj_iterator;
55
56 public:
57
58 bool operator==(const iterator& other)
59 {
60 return adj_iterator == other.adj_iterator;
61 }
62
63 bool operator!=(const iterator& other)
64 {
65 return !(*this == other);
66 }
67
68 pair<vertex, list<vertex_weight_pair> >operator*()
69 {
70 return *adj_iterator;
71 }
72
73 iterator operator++(int)
74 {
75 iterator temp_itr;
76 temp_itr.adj_iterator = adj_iterator++;
77 return temp_itr;
78 }
79 };/**///////////////////////////////////////////////////////////////////////////
80
81 struct edge_triple
82 {
83 vertex from;
84 vertex to;
85
86 double weight;
87
88 edge_triple(const vertex& from, const vertex& to, double weight)
89 {
90 this->from = from;
91 this->to = to;
92 this->weight = weight;
93 }
94
95 bool operator>(const edge_triple& other_edge_triple)const
96 {
97 return weight>other_edge_triple.weight;
98 }
99 };/**///////////////////////////////////////////////////////////////////////////
100
101
102 class breadth_first_iterator;
103 friend class breadth_first_iterator;
104
105 /**///////////////////////////////////////////////////////////////////////////
106 class breadth_first_iterator //广度优先
107 {
108 friend class network;
109
110 protected:
111
112 queue<vertex>* vertex_queue; //以队列存储 已访问节点
113 map<vertex, bool ,Compare>* reached; //reached 为 <vertex,bool>形式的对的映射
114 map_class* map_ptr; //指向邻接点的指针
115
116 breadth_first_iterator(const vertex& start, map_class* ptr)
117 {
118 map_ptr = ptr;
119 reached = new map<vertex, bool, Compare>();
120 vertex_queue = new queue<vertex>();
121
122 map_iterator itr;
123 /**/////////////////////////将每个顶点标记为不可达的
124 for(itr = (*map_ptr).begin(); itr != (*map_ptr).end(); itr++)
125 {
126 (*reached)[(*itr).first] = false;
127 }
128
129 (*reached)[start] = true;
130 (*vertex_queue).push(start);
131 }
132
133 public:
134
135 breadth_first_iterator(){}
136
137 bool operator==(const breadth_first_iterator& other)
138 {
139 return (vertex_queue == other.vertex_queue)&&
140 (reached == other.reached)&&
141 (map_ptr == other.map_ptr);
142 }
143
144 bool operator!=(const breadth_first_iterator& other)
145 {
146 return !(*this == other);
147 }
148
149 vertex operator*()
150 {
151 return (*vertex_queue).front();
152 }
153
154 breadth_first_iterator operator++(int)
155 {
156 breadth_first_iterator temp = *this;
157
158 vertex current = (*vertex_queue).front();
159 (*vertex_queue).pop();
160
161 map_iterator itr = (*map_ptr).find(current);
162 vertex_list_iterator list_itr;
163
164 for (list_itr = (*itr).second.begin();
165 list_itr != (*itr).second.end(); list_itr++)
166 {
167 vertex to = (*list_itr).to;
168
169 if ((*reached)[to] == false)
170 {
171 (*reached)[to] = true; //
172 (*vertex_queue).push(to);
173 }
174 }
175
176 if ((*vertex_queue).empty())
177 {
178 vertex_queue = NULL;
179 reached = NULL;
180 map_ptr = NULL;
181 }
182
183 return temp;
184 }
185 };/**///////////////////////////////////////////////////////////////////////////
186
187 class depth_first_iterator;
188 friend class depth_first_iterator;
189
190 class depth_first_iterator
191 {
192 friend class network;
193
194 stack<vertex>* vertex_stack;
195 map<vertex, bool, Compare>* reached;
196 map_class* map_ptr;
197
198 depth_first_iterator(const vertex& start, map_class* ptr)
199 {
200 map_ptr = ptr; //
201 reached = new map<vertex, bool, Compare>();
202 vertex_stack = new stack<vertex>();
203
204 map_iterator itr;
205
206 for (itr = (*map_ptr).begin();
207 itr != (*map_ptr).end(); itr++)
208 {
209 (*reached)[(*itr).first] = false;
210 }
211
212 (*reached)[start] = true;
213 (*vertex_stack).push(start);
214 }
215
216 public:
217 depth_first_iterator(){}
218
219 bool operator==(const depth_first_iterator& other)
220 {
221 return (vertex_stack == other.vertex_stack)&&
222 (reached == other.reached)&&
223 (map_ptr == other.map_ptr);
224 }
225
226 bool operator!=(const depth_first_iterator& other)
227 {
228 return !(*this == other);
229 }
230
231 vertex operator*()
232 {
233 return (*vertex_stack).top();
234 }
235
236 depth_first_iterator operator++(int)
237 {
238 depth_first_iterator temp = *this;
239
240 vertex current = (*vertex_stack).top();
241 (*vertex_stack).pop();
242
243 map_iterator itr = (*map_ptr).find(current);
244 vertex_list_iterator list_itr;
245
246 for (list_itr = (*itr).second.begin();
247 list_itr != (*itr).second.end(); list_itr++)
248 {
249 vertex to = (*list_itr).to;
250
251 if ((*reached)[to] == false)
252 {
253 (*reached)[to] = true;
254 (*vertex_stack).push(to);
255 }
256 }
257
258 if ((*vertex_stack).empty())
259 {
260 vertex_stack = NULL;
261 reached = NULL;
262 map_ptr = NULL;
263 }
264 return temp;
265 }
266 };
267
268 network(){}
269
270 network(const network& other)
271 {
272 adjacency_map = other.adjacency_map;
273 }
274
275 unsigned int size()
276 {
277 return adjacency_map.size();
278 }
279
280 bool empty()
281 {
282 return size() == 0;
283 }
284
285 iterator begin()
286 {
287 iterator temp;
288
289 temp.adj_iterator = adjacency_map.begin();
290
291 return temp;
292 }
293
294 iterator end()
295 {
296 iterator temp;
297
298 temp.adj_iterator = adjacency_map.end();
299
300 return temp;
301 }
302
303 //与边有关的实现
304
305 unsigned get_edge_count()
306 {
307 unsigned count = 0;
308
309 map_iterator itr;
310
311 for (itr = adjacency_map.begin();
312 itr != adjacency_map.end(); itr++)
313 {
314 count += (*itr).second.size();
315 }
316
317 return count;
318 }
319
320 double get_edge_weight(const vertex& v1, const vertex& v2)
321 {
322 map_iterator itr = adjacency_map.find(v1);
323
324 if (itr == adjacency_map.end() ||
325 adjacency_map.find(v2) == adjacency_map.end()) //v1 或 v2 不存在
326 {
327 return -1.0;
328 }
329
330 vertex_list_iterator list_itr;
331
332 for (list_itr = (*itr).second.begin();
333 list_itr != (*itr).second.end(); list_itr++)
334 {
335 if ((*list_itr).to == v2)
336 {
337 return (*list_itr).weight;
338 }
339 }
340
341 return -1.0;
342 }
343
344 bool contains_edge(const vertex& v1, const vertex& v2)
345 {
346 map_iterator itr = adjacency_map.find(v1);
347
348 if (itr == adjacency_map.end() ||
349 adjacency_map.find(v2) == adjacency_map.end()) //v1 或 v2 不存在
350 {
351 return false; //
352 }
353
354 vertex_list_iterator list_itr;
355
356 for (list_itr = (*itr).second.begin();
357 list_itr != (*itr).second.end(); list_itr++)
358 {
359 if ((*list_itr).to == v2)
360 {
361 return true;
362 }
363 }
364
365 return false;
366
367 }
368
369 bool insert_edge(const vertex& v1, const vertex& v2, const double& weight)
370 {
371 if (contains_edge(v1,v2))
372 {
373 return false;
374 }
375
376 insert_vertex(v1);
377 insert_vertex(v2);
378
379 (*(adjacency_map.find(v1))).second.push_back(vertex_weight_pair(v2,weight));
380
381 return true;
382 }
383
384 bool erase_edge(const vertex& v1, const vertex& v2)
385 {
386 map_iterator itr = adjacency_map.find(v1);
387 if (itr == adjacency_map.end() ||
388 adjacency_map.find(v2) == adjacency_map.end() )
389 {
390 return false;
391 }
392
393 vertex_list_iterator list_itr;
394
395 for (list_itr = (*itr).second.begin();
396 list_itr != (*itr).second.end(); list_itr++)
397 {
398 if ((*list_itr).to == v2)
399 {
400 (*itr).second.erase(list_itr);
401 return true;
402 }
403 }
404
405 return false;
406 }
407
408 //与点有关的实现
409
410 bool contains_vertex(vertex v)
411 {
412 return adjacency_map.find(v) != adjacency_map.end();
413 }
414
415 bool insert_vertex(const vertex& v)
416 {
417 return adjacency_map.insert(pair<vertex,list<vertex_weight_pair> >
418 (v,list<vertex_weight_pair>())).second;
419 }
420
421 bool erase_vertex(const vertex& v)
422 {
423 map_iterator itr = adjacency_map.find(v);
424
425 if (itr == adjacency_map.end())
426 {
427 return false;
428 }
429
430 adjacency_map.erase(itr); //删除该节点所在list
431
432 vertex_list_iterator list_itr;
433
434 //其他节点list中的包含该节点的节点
435 for (itr = adjacency_map.begin(); itr!= adjacency_map.end(); itr++)
436 {
437 for (list_itr = (*itr).second.begin();
438 list_itr != (*itr).second.end(); list_itr++)
439 {
440 if ((*list_itr).to == v)
441 {
442 (*itr).second.erase(list_itr);
443 break;
444 }
445 }
446 }
447 return true;
448 }
449
450 /**///////////////////////////////////////////////////////////////////////////遍历相关
451
452 breadth_first_iterator breadth_first_begin(const vertex& v)
453 {
454 breadth_first_iterator b_itr(v,&adjacency_map);
455 return b_itr;
456 }
457
458 breadth_first_iterator breadth_first_end()
459 {
460 breadth_first_iterator b_itr;
461
462 b_itr.vertex_queue = NULL;
463 b_itr.reached = NULL;
464 b_itr.map_ptr = NULL;
465
466 return b_itr;
467 }
468
469
470 depth_first_iterator depth_first_begin(const vertex& v)
471 {
472 depth_first_iterator d_itr(v,&adjacency_map);
473 return d_itr;
474 }
475
476 depth_first_iterator depth_first_end()
477 {
478 depth_first_iterator d_itr;
479
480 d_itr.vertex_stack = NULL;
481 d_itr.reached = NULL;
482 d_itr.map_ptr = NULL;
483
484 return d_itr;
485 }
486
487
488 /**///////////////////////////////////////////////////////////////////////////全局方法
489
490 bool is_connected() //连通
491 {
492 map_iterator itr;
493
494 for (itr = adjacency_map.begin(); itr != adjacency_map.end(); itr++)
495 {
496 vertex v = (*itr).first;
497
498 unsigned count = 0;
499 breadth_first_iterator b_itr;
500
501 for (b_itr = breadth_first_begin(v); b_itr != breadth_first_end(); b_itr++)
502 {
503 count++;
504 }
505
506 if (count < adjacency_map.size())
507 {
508 return false;
509 }
510 }
511 return true;
512 }
513
514 list<vertex> get_neighbor_list(const vertex& v) //得到v的所有邻接点
515 {
516 vertex_list_iterator list_itr;
517 list<vertex> vertex_list;
518
519 map_iterator itr = adjacency_map.find(v);
520
521 for (list_itr = (*itr).second.begin();
522 list_itr != (*itr).second.end(); list_itr++)
523 {
524 vertex_list.push_back((*list_itr).to);
525 }
526
527 return vertex_list;
528 }
529
530
531 network<vertex> get_minimum_spanning_tree() //最小生成树
532 {
533 network min_spanning_tree;
534
535 //优先队列 带权的边 利用向量存储 从小到大排列
536 priority_queue<edge_triple, vector<edge_triple>, greater<edge_triple> >pq; //从小到大排列
537
538 vertex root;
539 vertex x;
540 vertex y;
541 vertex z;
542
543 iterator itr;
544
545 list<vertex_weight_pair> adjacency_list; //邻接 表
546 vertex_list_iterator list_itr;
547
548 double weight;
549
550 if (empty())
551 {
552 return min_spanning_tree;
553 }
554
555 itr = begin();
556 root = (*itr).first;
557 min_spanning_tree.insert_vertex(root);
558
559 adjacency_list = adjacency_map[root];
560
561 //初始化
562 for (list_itr = adjacency_list.begin();
563 list_itr != adjacency_list.end(); list_itr++)
564 {
565 pq.push(edge_triple(root,list_itr->to,list_itr->weight));
566 }
567
568 while (min_spanning_tree.size()<size())
569 {
570 x = pq.top().from;
571 y = pq.top().to;
572 weight = pq.top().weight;
573 pq.pop();
574
575 if (!min_spanning_tree.contains_vertex(y)) //
576 {
577 min_spanning_tree.insert_vertex(y);
578 min_spanning_tree.insert_edge(x,y,weight);
579
580 adjacency_list = adjacency_map[y];
581
582 for (list_itr = adjacency_list.begin();
583 list_itr != adjacency_list.end(); list_itr++)
584 {
585 z = list_itr->to;
586 if (!min_spanning_tree.contains_vertex(z)) //
587 {
588 weight = list_itr->weight;
589 pq.push(edge_triple(y,z,weight));
590 }
591 }
592 }
593 }
594 return min_spanning_tree;
595 }
596
597
598 //单源最短路径
599 pair<list<vertex>, double> get_shortest_path(const vertex& v1,const vertex& v2)
600 {
601 const double MAX_PATH_WEIGHT = 1000000.0;
602
603 map<vertex,vertex,Compare> predecessor;
604 map<vertex,double,Compare> weight_sum;
605
606 priority_queue<vertex_weight_pair,vector<vertex_weight_pair>,
607 greater<vertex_weight_pair> >pq; //从小到大排列
608
609 //存储 从v1 到 该点的最短路径，只有当v1可达该点时才压入
610
611 list<vertex_weight_pair> adjacency_list;
612 vertex_list_iterator list_itr;
613
614 breadth_first_iterator b_itr;
615
616 vertex to;
617 vertex from;
618
619 double weight;
620
621 if (adjacency_map.find(v1) == adjacency_map.end() ||
622 adjacency_map.find(v2) == adjacency_map.end()) //不存在->不可达到
623 {
624 return pair<list<vertex>, double> (list<vertex>(),-1.0);
625 }
626
627 bool found_v2 = false;
628
629 //利用广度优先遍历，确定v1是否可以达到v2
630 for (b_itr = breadth_first_begin(v1); b_itr != breadth_first_end(); b_itr++)
631 {
632 if (*b_itr == v2)
633 {
634 found_v2 = true;
635 break;
636 }
637 }
638
639 if (!found_v2)
640 {
641 return pair<list<vertex>, double> (list<vertex>(),-1.0);
642 }
643
644 /**//*weight_sum[v1] = 0.0;
645 predecessor[v1] = v1;*/
646
647 //初始化
648 for (b_itr = breadth_first_begin(v1);b_itr != breadth_first_end(); b_itr++)
649 {
650 weight_sum[*b_itr] = MAX_PATH_WEIGHT;
651 predecessor[*b_itr] = vertex();
652 }
653
654 weight_sum[v1] = 0.0;
655 predecessor[v1] = v1;
656
657 //根节点 的邻接点 的初始化
658 adjacency_list = adjacency_map[v1];
659 for (list_itr = adjacency_list.begin(); list_itr != adjacency_list.end(); list_itr++)
660 {
661 weight_sum[list_itr->to] = list_itr->weight;
662 predecessor[list_itr->to] = v1;
663 pq.push(vertex_weight_pair(*list_itr));
664 }
665
666 bool path_found = false;
667
668 while (!path_found)
669 {
670 from = pq.top().to; //
671 pq.pop();
672
673 if (from == v2)
674 {
675 path_found = true;
676 }
677 else
678 {
679 adjacency_list = adjacency_map[from];
680 for (list_itr = adjacency_list.begin();
681 list_itr != adjacency_list.end(); list_itr++)
682 {
683 to = list_itr->to; //
684 weight = list_itr->weight;
685
686 if (weight_sum[from] + weight < weight_sum[to])
687 {
688 weight_sum[to] = weight_sum[from] + weight;
689 predecessor[to] = from;
690
691 pq.push(vertex_weight_pair(to,weight_sum[to]));
692 }
693 }
694 }
695 }
696
697 list<vertex> path;
698 vertex current = v2;
699 while(current != v1)
700 {
701 path.push_front(current);
702 current = predecessor[current];
703 }
704 path.push_front(v1);
705
706 return pair<list<vertex>, double> (path,weight_sum[v2]);
707 }
708
709 // 连通
710 pair<list<vertex>, double> get_cycle() //环
711 {
712 pair<list<vertex>, double> cycle;
713
714 list<vertex> cycle_list;
715
716 double weight;
717 double cycle_weight = 0.0;
718
719 list<vertex_weight_pair> adjacency_list;
720 vertex_list_iterator list_itr;
721
722 iterator itr = begin();
723
724 vertex v;
725 vertex start = (*itr).first;
726
727 cycle_list.push_back(start);
728 v = start;
729
730 while (cycle_list.size() < size())
731 {
732 adjacency_list = adjacency_map[v];
733 list_itr = adjacency_list.begin();
734 do
735 {
736 v = list_itr->to;
737 weight = list_itr->weight;
738 list_itr++;
739 } while(find(cycle_list.begin(),cycle_list.end(),v)!=cycle_list.end()
740 &&list_itr != adjacency_list.end()); //v已经存在cycle_list中
741
742 if (find(cycle_list.begin(),cycle_list.end(),v) == cycle_list.end())
743 {
744 cycle_list.push_back(v);
745 cycle_weight += weight;
746 }
747 }
748
749 cycle_list.push_back(start);
750 cycle_weight += get_edge_weight(v,start);
751 cycle.first = cycle_list;
752 cycle.second = cycle_weight;
753 return cycle;
754 }
755
};
756#endif
757
758
759
760
posted on 2009-12-27 15:50
HenDanTou 阅读(555)
评论(0) 编辑 收藏 引用 所属分类:
数据结构