karger.c File Reference

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#include "karger.h"
#include "bc_zeit.h"
#include "eg_macros.h"

Include dependency graph for karger.c:

Go to the source code of this file.

Defines
#define	MAXCKEYS   32768
#define	MAXALPHA   4
#define	MAXPSNODES   64
#define	RFACTOR   1000
Functions
static int	get_numiter (int nnode, int nedges, int alpha, double bound)
static int	create_cutset (int nnodes, int nps, int *psnodes, int *pssubset, int nremain, int *edge, double *length, int *treeinf, unsigned int *nkey, char *ckeys, int *cutset, int *cutsize, double *cutweight, int *foundset)
static int	get_alphacut (int nnodes, int nedges, int *edge, double *length, int *treeinf, unsigned int *nkey, char *ckeys, int alpha, double bound, setlist **sets, int(*choose_edge)(int, int *, double *, double, void *, int *), void *process_info, int(*process_set)(int *, int, double, void *, setlist **))
static void	merge_components (int comp1, int comp2, int *treeinf, int *newnode)
int	karger (int nnodes, int nedges, int *elist, double *elen, int alpha, double bound, double maxtime, int seed, setlist **sets, int(*choose_edge)(int, int *, double *, double, void *, int *), void *process_info, int(*process_set)(int *, int, double, void *, setlist **))
int	choose_edge1 (int nremain, int *edge, double *length, double tweight, void *process_info, int *e)
int	add_cut (int *cutset, int cutsize, double cutweight, void *process_info, setlist **sets)
int	karg_getprob (char *fname, int *nnodes, int *nedges, int **elist, double **elen)
int	process_cut (int *cutset, int cutsize, double cutweight, void *process_info, setlist **sets)
Variables
int	max_numiter = 0

---

Define Documentation

#define MAXALPHA   4

Definition at line 13 of file karger.c.

#define MAXCKEYS   32768

Definition at line 12 of file karger.c.

#define MAXPSNODES   64

Definition at line 14 of file karger.c.

#define RFACTOR   1000

Definition at line 15 of file karger.c.

---

Function Documentation

int add_cut (  int *  cutset, int  cutsize, double  cutweight, void *  process_info, setlist **  sets )

Definition at line 179 of file karger.c.

int choose_edge1 (  int  nremain, int *  edge, double *  length, double  tweight, void *  process_info, int *  e )

Definition at line 157 of file karger.c.

static int create_cutset (  int  nnodes, int  nps, int *  psnodes, int *  pssubset, int  nremain, int *  edge, double *  length, int *  treeinf, unsigned int *  nkey, char *  ckeys, int *  cutset, int *  cutsize, double *  cutweight, int *  foundset )

Definition at line 541 of file karger.c.

static int get_alphacut (  int  nnodes, int  nedges, int *  edge, double *  length, int *  treeinf, unsigned int *  nkey, char *  ckeys, int  alpha, double  bound, setlist **  sets, int(*)(int, int *, double *, double, void *, int *)  choose_edge, void *  process_info, int(*)(int *, int, double, void *, setlist **)  process_set )

Definition at line 318 of file karger.c.

static int get_numiter (  int  nnode, int  nedges, int  alpha, double  bound )  [static]

Definition at line 309 of file karger.c.

int karg_getprob (  char *  fname, int *  nnodes, int *  nedges, int **  elist, double **  elen )

Definition at line 207 of file karger.c.

int karger (  int  nnodes, int  nedges, int *  elist, double *  elen, int  alpha, double  bound, double  maxtime, int  seed, setlist **  sets, int(*)(int, int *, double *, double, void *, int *)  choose_edge, void *  process_info, int(*)(int *, int, double, void *, setlist **)  process_set )

Definition at line 44 of file karger.c.

static void merge_components (  int  comp1, int  comp2, int *  treeinf, int *  newnode )  [static]

Definition at line 505 of file karger.c.

int process_cut (  int *  cutset, int  cutsize, double  cutweight, void *  process_info, setlist **  sets )

Definition at line 264 of file karger.c.

---

Variable Documentation

int max_numiter = 0

Definition at line 10 of file karger.c.

---