type_partitions.h

Go to the documentation of this file.

 
#ifndef PARTITIONS_H
#define PARTITIONS_H
 
 /*  ____            _   _ _   _                  */
 /* |  _ \ __ _ _ __| |_(_) |_(_) ___  _ __  ___  */
 /* | |_) / _` | '__| __| | __| |/ _ \| '_ \/ __| */
 /* |  __/ (_| | |  | |_| | |_| | (_) | | | \__ \ */
 /* |_|   \__,_|_|   \__|_|\__|_|\___/|_| |_|___/ */
 
#include "alloc.h"
#include "stdbool.h"
#include "stdlib.h"
#include "type_basic.h"
#include "type_dequeue.h"
 
/**************/
/* First Type */
/**************/

typedef struct {
    uint size_set; 
    uint size_par; 
    uint* numcl; 
    uint* storage; 
    uint** cl_elems; 
    uint* cl_size; 
 
 
    //dequeue** cl; //!< Array indexed by the classes. Each class is mapped to the list
} parti;

parti* create_parti(uint size_set, 
    uint size_par, 
    uint* numcl 
);
 

void delete_parti(parti* 
);

bool istrivial_parti(parti* 
);

parti* restrict_parti(
    parti*, 
    uint,    
    bool*, 
    uint*  
);

parti* restrict_parti_subset(
    parti*, 
    uint,    
    bool*, 
    uint*, 
    uint*  // Mapping from the original subset to the full set.
);

uint* parti_compute_inv(parti* P 
);
 
/**************/
/* Union-Find */
/**************/

typedef struct {
    uint size_tab; 
    uint size_set; 
    uint size_par; 
    uint* parent;  
    uint* rank;    
    uint* sizec;   
} ufind;

ufind* create_ufind(uint 
);

void delete_ufind(ufind* 
);

uint sizeset_ufind(ufind* 
);

uint sizepar_ufind(ufind* 
);

void makeset_ufind(ufind* 
);

uint find_ufind(uint,   
    ufind* 
);

uint sizeclass_ufind(uint,   
    ufind* 
);

void union_ufind(uint,   
    uint,   
    ufind* 
);

void print_ufind(ufind* 
);

ufind* parti_to_ufind(parti* 
);

parti* ufind_to_parti(ufind* 
);

parti* ufind_to_parti_refined(
    ufind*, 
    parti*  
);
 
#endif