graph.h

Go to the documentation of this file.

#ifndef MTMETIS_GRAPH_H
#define MTMETIS_GRAPH_H




#include "base.h"
#include "ctrl.h"




/******************************************************************************
* TYPES ***********************************************************************
******************************************************************************/


typedef struct graphdist_type {
  tid_type nthreads;
  vtx_type mask;
  int shift;
  vtx_type offset;
} graphdist_type;


typedef struct graph_type {
  /* global counts */
  vtx_type nvtxs; 
  vtx_type gnvtxs;
  adj_type nedges;
  /* distribution information */
  dlthread_comm_t comm;
  graphdist_type dist;
  /* pre partitioning info */
  pid_type ** group;
  pid_type ngroup;
  /* distributed graph structure */
  vtx_type * mynvtxs;
  adj_type * mynedges;
  adj_type ** xadj;
  wgt_type ** vwgt;
  vtx_type ** adjncy;
  wgt_type ** adjwgt;
  /* graph info */
  int uniformvwgt;
  int uniformadjwgt;
  vtx_type * nislands;
  /* coarsening info */
  size_t level;
  vtx_type ** cmap;
  /* partition information */
  wgt_type * pwgts;
  pid_type ** where;
  struct kwinfo_type * kwinfo;
  struct esinfo_type * esinfo;
  struct vsinfo_type * vsinfo;
  /* total weight */
  twgt_type tvwgt, tadjwgt;
  real_type invtvwgt;
  /* aliasing */
  vtx_type ** rename;
  vtx_type ** label;
  /* metrics */
  wgt_type mincut, minsep;
  vtx_type minvol;
  /* "To free, or not free" */
  int free_xadj, free_vwgt, free_vsize, free_adjncy, free_adjwgt;
  /* graphs in the heirarchy */
  struct graph_type *coarser, *finer;
} graph_type;




/******************************************************************************
* SERIAL FUNCTION PROTOTYPES **************************************************
******************************************************************************/


#define graph_create MTMETIS_graph_create

graph_type * graph_create(
    tid_type nthreads);


#define graph_setup MTMETIS_graph_setup

graph_type * graph_setup(
    vtx_type * nvtxs, 
    adj_type ** xadj, 
    vtx_type ** adjncy, 
    wgt_type ** adjwgt, 
    wgt_type ** vwgt,
    tid_type nthreads);


#define graph_distribute MTMETIS_graph_distribute

graph_type * graph_distribute(
    int dist,
    vtx_type nvtxs, 
    adj_type const * xadj, 
    vtx_type const * adjncy, 
    wgt_type const * vwgt,
    wgt_type const * adjwgt, 
    tid_type nthreads);


#define graph_gather MTMETIS_graph_gather

void graph_gather(
  graph_type const * graph,
  adj_type ** r_xadj,
  vtx_type ** r_adjncy,
  wgt_type ** r_vwgt,
  wgt_type ** r_adjwgt,
  vtx_type ** r_voff);


#define graph_setup_coarse MTMETIS_graph_setup_coarse

graph_type * graph_setup_coarse(
    graph_type * graph, 
    vtx_type * cnvtxs);


#define graph_setup_twgts MTMETIS_graph_setup_twgts

void graph_setup_twgts(
    graph_type * graph);


#define graph_alloc_partmemory MTMETIS_graph_alloc_partmemory

void graph_alloc_partmemory(
    ctrl_type * ctrl,
    graph_type * graph);

#define graph_free MTMETIS_graph_free

void graph_free(
    graph_type * graph);


#define graph_free_rdata MTMETIS_graph_free_rdata

void graph_free_rdata(
    graph_type * graph);


#define graph_imbalance MTMETIS_graph_imbalance

double graph_imbalance(
    graph_type const * graph,
    pid_type nparts,
    real_type const * pijbm);


#define graph_imbalance_diff MTMETIS_graph_imbalance_diff

double graph_imbalance_diff(
    graph_type const * const graph,
    pid_type const nparts,
    real_type const * const pijbm,
    real_type const ubfactor);


#define graph_cut MTMETIS_graph_cut

wgt_type graph_cut(
    graph_type const * graph,
    pid_type const * const * where);


#define graph_isbalanced MTMETIS_graph_isbalanced

int graph_isbalanced(
    ctrl_type const * ctrl, 
    graph_type const * graph, 
    real_type ffactor);


#define graph_readjust_memory MTMETIS_graph_readjust_memory

void graph_readjust_memory(
    graph_type * const graph,
    adj_type adjsize);


#define graph_extract_halves MTMETIS_graph_extract_halves

void graph_extract_halves(
    graph_type * graph,
    pid_type const * const * where,
    graph_type ** halves);


#define graph_size MTMETIS_graph_size

size_t graph_size(
    graph_type const * graph);


#define graph_calc_dist MTMETIS_graph_calc_dist

void graph_calc_dist(
    vtx_type maxnvtxs, 
    tid_type nthreads,
    graphdist_type * dist);




/******************************************************************************
* PARALLEL FUNCTION PROTOTYPES ************************************************
******************************************************************************/


#define par_graph_create MTMETIS_par_graph_create

graph_type * par_graph_create(
    dlthread_comm_t comm);


#define par_graph_setup MTMETIS_par_graph_setup

graph_type * par_graph_setup(
    vtx_type nvtxs, 
    adj_type * xadj, 
    vtx_type * adjncy, 
    wgt_type * adjwgt, 
    wgt_type * vwgt,
    dlthread_comm_t comm);


#define par_graph_gather MTMETIS_par_graph_gather

void par_graph_gather(
  graph_type const * graph,
  adj_type ** r_xadj,
  vtx_type ** r_adjncy,
  wgt_type ** r_vwgt,
  wgt_type ** r_adjwgt,
  vtx_type * r_voff);


#define par_graph_shuffle MTMETIS_par_graph_shuffle

void par_graph_shuffle(
    ctrl_type * ctrl,
    graph_type * graph,
    pid_type const * const * where,
    int wgts);


#define par_graph_setup_coarse MTMETIS_par_graph_setup_coarse

graph_type * par_graph_setup_coarse(
    graph_type * const graph, 
    vtx_type cnvtxs);


#define par_graph_setup_twgts MTMETIS_par_graph_setup_twgts

void par_graph_setup_twgts(
    graph_type * graph);


#define par_graph_alloc_partmemory MTMETIS_par_graph_alloc_partmemory

void par_graph_alloc_partmemory(
    ctrl_type * ctrl,
    graph_type * graph);


#define par_graph_free MTMETIS_par_graph_free

void par_graph_free(
    graph_type * graph);


#define par_graph_free_rdata MTMETIS_par_graph_free_rdata

void par_graph_free_rdata(
    graph_type * graph);


#define par_graph_readjust_memory MTMETIS_par_graph_readjust_memory

void par_graph_readjust_memory(
    graph_type * const graph,
    adj_type adjsize);


#define par_graph_extract_halves MTMETIS_par_graph_extract_halves

tid_type par_graph_extract_halves(
    graph_type * graph,
    pid_type const * const * where,
    graph_type ** halves);


#define par_graph_extract_boundary MTMETIS_par_graph_extract_boundary

graph_type * par_graph_extract_boundary(
    ctrl_type const * ctrl,
    graph_type const * graph,
    vtx_iset_t const * bnd);


#define par_graph_extract_separator MTMETIS_par_graph_extract_separator

graph_type * par_graph_extract_separator(
    ctrl_type const * ctrl,
    graph_type const * graph,
    vtx_iset_t const * bnd);


#define par_graph_extract_aseparator MTMETIS_par_graph_extract_aseparator

graph_type * par_graph_extract_aseparator(
    ctrl_type const * ctrl,
    graph_type const * graph,
    vtx_iset_t const * bnd);


#define par_graph_build_radj MTMETIS_par_graph_build_radj

adj_type * par_graph_build_radj(
    graph_type const * graph);


#define par_graph_contract MTMETIS_par_graph_contract

void par_graph_contract(
    ctrl_type * ctrl, 
    graph_type * graph, 
    vtx_type const cnvtxs, 
    vtx_type const * const * gmatch, 
    vtx_type const * fcmap);


#define par_graph_intext_vtx MTMETIS_par_graph_intext_vtx

void par_graph_intext_vtx(
    graph_type const * const graph,
    vtx_type * const r_nint,
    vtx_type * const r_next);


#define par_graph_cut MTMETIS_par_graph_cut

wgt_type par_graph_cut(
    graph_type const * graph,
    pid_type const * const * where);


#define par_graph_removeislands MTMETIS_par_graph_removeislands

void par_graph_removeislands(
    ctrl_type * ctrl,
    graph_type * graph);


#define par_graph_restoreislands MTMETIS_par_graph_restoreislands

void par_graph_restoreislands(
    ctrl_type * ctrl,
    graph_type * graph,
    pid_type * const * gwhere);


#define par_graph_extract_parts MTMETIS_par_graph_extract_parts

void par_graph_extract_parts(
    graph_type * const graph,
    pid_type const * const * const gwhere,
    pid_type const nparts,
    graph_type ** const parts);


#define par_graph_distribute MTMETIS_par_graph_distribute

graph_type * par_graph_distribute(
    int distribution,
    vtx_type nvtxs, 
    adj_type const * xadj, 
    vtx_type const * adjncy, 
    wgt_type const * vwgt,
    wgt_type const * adjwgt, 
    dlthread_comm_t comm);



#endif