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

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

数值算法/人工智能

开发平台：

MultiPlatform

node_partition.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  node_partition.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_PARTITION_H
  14. #define LEDA_NODE_PARTITION_H
  17. //------------------------------------------------------------------------------
  18. // node partitions 
  19. //------------------------------------------------------------------------------
  21. #include <LEDA/graph.h>
  23. /*{Manpage {node_partition} {} {Node Partitions}}*/
  25. #include <LEDA/partition.h>
  27. class node_partition : private partition
  28. {
  29. /*{Mdefinition
  30. An instance $P$ of the data type $node_partition$ is a partition of the nodes
  31. of a graph $G$.}*/
  33. public:
  35. void init(const graph& G);
  37. /*{Mcreation P }*/
  39.  node_partition(const graph& G) { init(G); }
  40. /*{Mcreate creates a name var containing for every node $v$ in $G$ a 
  41.             block ${v}$.}*/
  43. ~node_partition()               {}   
  45. /*{Moperations 1.2 4.5}*/
  47. int  same_block(node v, node w)   
  48. { return partition::same_block(partition_item(v->data[2]),
  49.                                partition_item(w->data[2])); }
  51. /*{Mopl      returns true if $v$ and $w$ belong to the
  52.               same block of var, false otherwise.}*/
  55. void union_blocks(node v, node w) 
  56. { partition::union_blocks(partition_item(v->data[2]), 
  57.                           partition_item(w->data[2])); }
  58. /*{Mopl      unites the blocks of var containing nodes
  59.       $v$ and $w$.}*/
  62. void make_rep(node v) 
  63. { partition::set_inf(partition_item(v->data[2]),v); }
  65. node find(node v) 
  66. { return node(partition::inf(partition::find(partition_item(v->data[2])))); }
  67. /*{Mop       returns a canonical representative node of 
  68.       the block that contains node $v$.}*/
  70. node operator()(node v) { return find(v); }
  71. /*{Mfunop    returns var.find($v$). }*/
  74. };
  76. /*{Mimplementation
  77. A node partition for a graph $G$ is implemented by a combination of a 
  78. partition $P$ and a node array of $partition_item$ associating with 
  79. each node in $G$ a partition item in $P$. Initialization takes linear time,
  80. union_blocks takes time $O(1)$ (worst-case), and same_block and find take 
  81. time $O(alpha(n))$ (amortized).  The space requirement is $O(n)$, where $n$ 
  82. is the number of nodes of $G$.}*/
  84. #endif