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

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

数值算法/人工智能

开发平台：

MultiPlatform

node_set.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  node_set.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_SET_H
  14. #define LEDA_NODE_SET_H
  16. //------------------------------------------------------------------------------
  17. // node_set  
  18. //------------------------------------------------------------------------------
  20. #include <LEDA/graph.h>
  22. /*{Manpage {node_set} {} {Sets of Nodes} }*/
  24. class node_set 
  25. {
  26. /*{Mdefinition
  27. An instance $S$ of the data type $node_set$ is a subset of
  28. the nodes of a graph $G$. $S$ is said to be valid for the nodes
  29. of $G$.}*/
  31.   graph* g;
  32.   list<node> L;
  33.   node_array<list_item> A;
  35. public:
  38. /*{Mcreation S }*/
  40. node_set(const graph& G) : A(G,nil) { g = (graph*)&G; }
  41. /*{Mcreate creates an instance $S$ of type $node_set$ valid for all 
  42.             nodes currently contained in graph $G$ and initializes it 
  43.             to the empty set.}*/
  45. ~node_set() {}
  48. /*{Moperations 1.3 4 }*/
  50. void insert(node x)  { if (A[x] == nil) A[x] = L.append(x); }
  51. /*{Mop       adds node $x$ to $S$. }*/
  53. void del(node x)     { if (A[x] != nil) { L.del(A[x]); A[x] = nil;} }
  54. /*{Mop       removes node $x$ from $S$. }*/
  56. bool member(node x)  { return (A[x] != nil); }
  57. /*{Mop      returns true if $x$ in $S$, false otherwise. }*/
  59. node choose()  const { return L.head(); }
  60. /*{Mop      returns a node of $S$. }*/
  62. int  size()    const { return L.length(); }
  63. /*{Mop      returns the size of $S$. }*/
  65. bool empty()   const { return L.empty(); }
  66. /*{Mop      returns true iff $S$ is the empty set. }*/
  68. void clear()         { L.clear(); A.init(*g,nil); }
  69. /*{Mop      makes $S$ the empty set. }*/
  71. };
  73. /*{Mimplementation
  74. A node set $S$ for a graph $G$ is implemented by a combination of a 
  75. list  $L$ of nodes and a node array of list_items 
  76. associating with each node its position in $L$. All operations 
  77. take constant time, except for clear which takes time $O(|S|)$. The space 
  78. requirement is $O(n)$, where $n$ is the number of nodes of $G$.}*/
  80. #endif