bc_spanning.h

Go to the documentation of this file.

#ifndef _DPSPANNINGTREE
#define _DPSPANNINGTREE

#include <stdio.h>
#include <malloc.h>
#include "eg_macros.h"
#include "eg_mempool.h"

#define SWAP(x,y,temp) {temp = x; x = y; y = temp;}

typedef struct DPspanningNode
{
  struct
  {
    struct DPspanningNode *parent;
    int rank;
  }
  setinfo;
}
DPspanningNode;

typedef struct DPspanningEdge
{
  double weight;
  int ends[2];
}
DPspanningEdge;

typedef struct DPedgeSet
{
  int nedges;
  int *edges;
}
DPedgeSet_t;

void makeset (DPspanningNode * v);
DPspanningNode *find (DPspanningNode * v);
DPspanningNode *slink (DPspanningNode * x,
                       DPspanningNode * y);
int getprob (char *fname,
             int *p_ncount,
             int *p_ecount,
             int **p_elist,
             double **p_wlist);
int kruskal_spanningtree (int ncount,
                          int ecount,
                          int *elist,
                          double *wlist,
                          int *tlist,
                          void *function_data);
int biased_spanningtree (int ncount,
                         int ecount,
                         int *elist,
                         double *wlist,
                         int *tlist,
                         void *function_data);
void printtree (int ncount,
                int *elist,
                int *tlist);
void qsort_DPspanningEdges (int *perm,
                            DPspanningEdge * elist,
                            int l,
                            int u);
int buildgraph (int ecount,
                int *elist,
                double *wlist,
                DPspanningEdge ** p_edglist);

#endif

---