/*******************************************************************************
+
+  LEDA 3.5
+
+  node_partition.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#ifndef LEDA_NODE_PARTITION_H
#define LEDA_NODE_PARTITION_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350083
#include <LEDA/REDEFINE_NAMES.h>
#endif



//------------------------------------------------------------------------------
// node partitions 
//------------------------------------------------------------------------------

#include <LEDA/graph.h>

/*{\Manpage {node_partition} {} {Node Partitions}}*/

#include <LEDA/partition.h>

class node_partition : private partition
{
/*{\Mdefinition
An instance $P$ of the data type $node\_partition$ is a partition of the nodes
of a graph $G$.}*/

node_array<partition_item> ITEM;

public:

void init(const graph& G);

/*{\Mcreation P }*/

 node_partition(const graph& G) : ITEM(G,nil) { init(G); }
/*{\Mcreate creates a |\Mname| |\Mvar| containing for every node $v$ in $G$ a 
            block $\{v\}$.}*/

~node_partition()               {}   

/*{\Moperations 1.2 4.5}*/

int  same_block(node v, node w)   
{ return partition::same_block(ITEM[v],ITEM[w]); }
/*{\Mopl      returns true if $v$ and $w$ belong to the
              same block of |\Mvar|, false otherwise.}*/


void union_blocks(node v, node w) 
{ partition::union_blocks(ITEM[v],ITEM[w]); } 
/*{\Mopl      unites the blocks of |\Mvar| containing nodes
	      $v$ and $w$.}*/


void make_rep(node v) { partition::inf(ITEM[v]) = v; }

node find(node v) 
{ return node(partition::inf(partition::find(ITEM[v]))); }
/*{\Mop       returns a canonical representative node of 
	      the block that contains node $v$.}*/

node operator()(node v) { return find(v); }
/*{\Mfunop    returns |\Mvar|.find($v$). }*/


};

/*{\Mimplementation
A node partition for a graph $G$ is implemented by a combination of a 
partition $P$ and a node array of $partition\_item$ associating with 
each node in $G$ a partition item in $P$. Initialization takes linear time,
union\_blocks takes time $O(1)$ (worst-case), and same\_block and find take 
time $O(\alpha(n))$ (amortized).  The space requirement is $O(n)$, where $n$ 
is the number of nodes of $G$.}*/


#if LEDA_ROOT_INCL_ID == 350083
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif

#endif
