graphdual.h

Go to the documentation of this file.

/* this file define structure to make graph duals */
#ifndef __GRAPHDUAL_H__
#define __GRAPHDUAL_H__
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "cookInterface.h"
#include "eg_mempool.h"
#include "eg_list.h"
#include "eg_dgraph.h"
#include "eg_ugraph.h"
#include "eg_equiset.h"
#include "eg_bit.h"
#include "eg_dijkstra.h"
#include "eg_menger.h"
#include "eg_menger_app.h"
#include "bc_spanning.h"
#include "eg_util.h"
#include "dp_config.h"
#include "graph_boyer.h"

#define GD_LEVEL 9

/* check planarity of a graph in cook's format */
int isPlanarBoyer (int nnodes,
                   int nedges,
                   int *edges);
/* check planarity of a graph in cook's format, return minor if not */
int isPlanarOrMinorBoyer (int nnodes,
                          int nedges,
                          int *edges,
                          int *nmedges,
                          int *medges);

/* generate the dual graph */
EGdGraph_t *getDualBoyer (graphP G,
                          int nnodes,
                          int nedges,
                          double *weigh,
                          EGlist_t *** dembed,
                          EGmemPool_t * localmem,
                          EGlist_t***lembed);

/* this function chooses an edge among the k lightest edges (by weight) of a
   kuratowski minor. If no such minor exists, values -1 are set for the ends. */

int DPfindBadEdge (int nnodes,
                   int nedges,
                   int *edges,
                   double *weight);

/* this function chooses an edge among the k lightest edges (by weight) of a
   kuratowski minor. If no such minor exists, values -1 are set for the ends. */

int DPfindBadEdgeK (int nnodes,
                    int nedges,
                    int *edges,
                    double *weight,
                    int k);

/* generate a planar subgraph from a graph by building a maximum weight spanning
 * tree and then eliminating edges that make it non planar */
int DPedgeEliminationHeuristic (int nnodes,
                                int nedges,
                                int *edges,
                                double *weight,
                                int *nplanar_edges,
                                int *planar_edges,
                                double *planar_weight,
                                int *nelim_indices,
                                int *elim_indices);

/* This function works with two graphs G1 and G2 spanning a common set of
   vertices. It assumes that G2 is a planar graph, and that its edge set 
   is strictly contained in that of G1. It finds a graph G3 in between
   G1 and G2 that is planar by means of binary search and edge additions.
  
   nnodes: number of nodes in G1 and G2.
   nedges1: number of edges of G1.
   nedges2: number of edges of G2.
   edges: array of edges in G1. It is assumed that the first nedges2 edges
          of the array are the edges of G2. In Cook format.
   nedges3: number of edges in G3 (output).
   edges3: array with edges in G3 in Cook format (output).
   elim_indices: array with the indices of those edges eliminated from edges. */
int DPbinPlanarizeBoyer (int nnodes,
                         int nedges1,
                         int nedges2,
                         int *edges,
                         double *weigh,
                         int *nedges3,
                         int *edges3,
                         double *weigh3,
                         int *elim_indices);

/* This function finds a minor in the graph described by
 * nnodes and nedges and then identifies two nodes,
 * node_1 and node_2, which upon contraction ensure that
 * the graph no longer has the minor. If there is no such
 * minor, then the values of node_1 and node_2 are set to
 * -1. If there is no such
 * minor, then the values of node_1 and node_2 are set to
 * -1.*/

int DPgetMinorNodesToContract (int nnodes,
                               int nedges,
                               int *edges,
                               int *node_1,
                               int *node_2);

/* same as above, but preserves the minor */

int DPgetNonMinorNodesToContract (int nnodes,
                                  int nedges,
                                  int *edges,
                                  double *weight,
                                  int *node_1,
                                  int *node_2);

int DPgetTrivialNodesToContract (int nnodes,
                                 int nedges,
                                 int *edges,
                                 double *weight,
                                 int *node_1,
                                 int *node_2);

/* This function works with a graph G1. It finds a graph G2 contained in G1
   which is planar by eliminating edges in Kuratowski minors.
  
   nnodes: number of nodes in G1.
   nedges1: number of edges of G1.
   edges: array of edges in G1. (Cook format).
   nedges3: number of edges in G3 (output).
   edges3: array with edges in G3 in Cook format (output).
   elim_indices: array with the indices of those edges eliminated from edges. */

int DPfastEdgeEliminationHeuristic (int nnodes,
                                    int nedges1,
                                    int *edges,
                                    double *weight,
                                    int *nedges2,
                                    int *edges2,
                                    double *weight2,
                                    int *nelim,
                                    int *elim_indices,
                                    int k_param);

int DPfindBadBinEdge (int nnodes,
                      int nedges,
                      int *edges);

int DPfindBadBinEdgeK (int nnodes,
                       int nedges,
                       int *edges,
                       double *weight,
                       int k);

int DPgetBinMinor (int nnodes,
                   int nedges,
                   int *edges,
                   int *nmedges,
                   int *medges,
                   int k);
#endif

---