开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
node_pq.h
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：4k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

node_pq.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  node_pq.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_NODE_PQ_H
  14. #define LEDA_NODE_PQ_H
  16. //------------------------------------------------------------------------------
  17. // node priority queues
  18. //------------------------------------------------------------------------------
  20. #include <LEDA/graph.h>
  21. #include <LEDA/impl/bin_heap.h>
  23. #define PRIO_IMPL bin_heap
  24. #define PRIO_ITEM bin_heap_item
  27. /*{Manpage {node_pq} {P} {Node Priority Queues}}*/
  29. template <class P>
  31. class node_pq : private PRIO_IMPL
  32. {
  33. /*{Mdefinition
  34. An instance $Q$ of the parameterized data type name is a partial
  35. function from the nodes of a graph $G$ to a linearly ordered type $P$
  36. of priorities. The priority of a node is sometimes called the information
  37. of the node. For every graph $G$ only one name may be used and every node
  38. of $G$ may be contained in the queue at most once (cf. section 
  39. ref{Priority Queues} for general priority queues). }*/
  41. int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(P,x,y); }
  42. int  int_type()              const { return LEDA_INT_TYPE(P); }
  43. void print_key(GenPtr x)     const { LEDA_PRINT(P,x,cout); }
  44. void print_inf(GenPtr x)     const { cout << index(node(x));  }
  45. void clear_key(GenPtr& x)    const { LEDA_CLEAR(P,x); }
  46. void copy_key(GenPtr& x)     const { LEDA_COPY(P,x);  }
  48. public:
  50. /*{Mcreation Q }*/
  51.  
  52. node_pq(const graph& G) { init_node_data(G,1,nil); }
  53. /*{Mcreate creates an instance $Q$ ot type name for the nodes of graph $G$
  54.     with $dom(Q)=emptyset$.}*/
  56. ~node_pq()             { clear(); }
  59. /*{Moperations 1.3 4.7}*/
  61. void insert(node v, P x)
  62. { v->data[1] = PRIO_IMPL::insert(Convert(x),v);}
  63. /*{Mop          adds the node $v$ with priority $x$ to
  64.             var.\ precond $vnotin dom(Q)$.}*/
  66. P prio(node v) const
  67. { return LEDA_ACCESS(P,PRIO_IMPL::key((PRIO_ITEM)v->data[1])); }
  68. /*{Mop         returns the priority of node $v$.}*/
  72. bool member(node v) const {return v->data[1] != nil;};
  73. /*{Mop         returns true if $v$ in var, false otherwise.}*/
  75. void decrease_p(node v, P x)
  76. { PRIO_IMPL::decrease_key(PRIO_ITEM(v->data[1]),Convert(x)); }
  77. /*{Mop          makes $x$ the new priority of node $v$.\
  78.           precond $x le Q$.prio$(v)$.}*/
  80. node find_min() const
  81. { return (node)PRIO_IMPL::inf(PRIO_IMPL::find_min());   }
  82. /*{Mop          returns a node with minimal priority 
  83.                  (nil if var is empty).}*/
  85. void del(node v) 
  86. { PRIO_IMPL::del_item(PRIO_ITEM(v->data[1])); v->data[1] = 0; }
  87. /*{Mop          removes the node $v$ from var. }*/
  89. node del_min()   
  90. { node v = find_min(); PRIO_IMPL::del_min(); v->data[1] = 0;  return v; }
  91. /*{Mop          removes a node with minimal priority from var 
  92.                  and returns it (nil if var is empty).}*/
  94. void clear()     { PRIO_IMPL::clear(); }
  95. /*{Mop          makes $Q$ the empty node priority queue.}*/
  97. int size()   const { return PRIO_IMPL::size(); }
  98. /*{Mop          returns $|dom(Q)|$. }*/
  100. int empty()  const { return PRIO_IMPL::empty(); }
  101. /*{Mop          returns true if var is the empty node
  102.  priority queue, false otherwise.}*/
  104. P inf(node v) const
  105. { return LEDA_ACCESS(P,PRIO_IMPL::key((PRIO_ITEM)v->data[1])); }
  106. /*{Mop         returns the priority of node $v$.}*/
  108. void decrease_inf(node v, P x)
  109. { PRIO_IMPL::decrease_key(PRIO_ITEM(v->data[1]),Convert(x)); }
  110. /*{Xop (for backward compatibility) makes $x$ the new priority of node $v$.\
  111.           precond $p le Q$.prio$(v)$.}*/
  114. };
  116. /*{Mimplementation
  117. Node priority queues are implemented by fibonacci heaps and node arrays.
  118. Operations insert, del_node, del_min take time $O(log n)$, find_min, 
  119. decrease_inf, empty take time $O(1)$ and clear takes time $O(m)$, where 
  120. $m$ is the size of $Q$. The space requirement is $O(n)$, where $n$ is the 
  121. number of nodes of $G$.}*/
  123. #endif