graph_boyer.h File Reference

#include <stdio.h>
#include <stdlib.h>
#include "appconst.h"
#include "listcoll.h"
#include "stack.h"

Include dependency graph for graph_boyer.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	graphNode
struct	vertexRec
struct	extFaceLinkRec
struct	isolatorContext
struct	BM_graph
Defines
#define	EDGE_LIMIT   6
#define	MIN(x, y)   ((x) < (y) ? (x) : (y))
#define	MAX(x, y)   ((x) > (y) ? (x) : (y))
#define	MIN3(x, y, z)   MIN(MIN((x), (y)), MIN((y), (z)))
#define	MAX3(x, y, z)   MAX(MAX((x), (y)), MAX((y), (z)))
#define	VAS_INACTIVE   0
#define	VAS_INTERNAL   1
#define	VAS_EXTERNAL   2
#define	TYPE_UNKNOWN   0
#define	EDGE_DFSCHILD   1
#define	EDGE_FORWARD   2
#define	EDGE_BACK   3
#define	EDGE_DFSPARENT   4
#define	VERTEX_HIGH_RXW   6
#define	VERTEX_LOW_RXW   7
#define	VERTEX_HIGH_RYW   8
#define	VERTEX_LOW_RYW   9
#define	FLAGS_DFSNUMBERED   1
#define	FLAGS_SORTEDBYDFI   2
#define	FLAGS_MINOR_A   1
#define	FLAGS_MINOR_B   2
#define	FLAGS_MINOR_C   4
#define	FLAGS_MINOR_D   8
#define	FLAGS_MINOR_E   16
#define	FLAGS_MINOR_E1   32
#define	FLAGS_MINOR_E2   64
#define	FLAGS_MINOR_E3   128
#define	FLAGS_MINOR_E4   256
#define	FLAGS_MINOR_E5   512
#define	FLAGS_MINOR_E6   1024
#define	FLAGS_MINOR_E7   2048
#define	gp_GetTwinArc(theGraph, Arc)   ((Arc) & 1) ? Arc-1 : Arc+1
#define	WRITE_ADJLIST   1
#define	WRITE_ADJMATRIX   2
#define	WRITE_DEBUGINFO   3
#define	EMBEDFLAGS_PLANAR   1
#define	_VertexActiveStatus(theGraph, theVertex, I)   (EXTERNALLYACTIVE (theGraph, theVertex, I) ? VAS_EXTERNAL : PERTINENT (theGraph, theVertex, I) ? VAS_INTERNAL : VAS_INACTIVE)
#define	PERTINENT(theGraph, theVertex, I)   (theGraph->V[theVertex].adjacentTo != NIL || theGraph->V[theVertex].pertinentBicompList != NIL ? 1 : 0)
#define	EXTERNALLYACTIVE(theGraph, theVertex, I)   (theGraph->V[theVertex].leastAncestor < I ? 1 : theGraph->V[theVertex].separatedDFSChildList != NIL && theGraph->V[theGraph->V[theVertex].separatedDFSChildList].Lowpoint < I ? 1 : 0)
Typedefs
typedef graphNode *	graphNodeP
typedef vertexRec *	vertexRecP
typedef extFaceLinkRec *	extFaceLinkRecP
typedef isolatorContext *	isolatorContextP
typedef BM_graph *	graphP
Functions
graphP	gp_New (void)
int	gp_InitGraph (graphP theGraph, int N)
void	gp_ReinitializeGraph (graphP theGraph)
int	gp_CopyGraph (graphP dstGraph, graphP srcGraph)
graphP	gp_DupGraph (graphP theGraph)
int	gp_CreateRandomGraph (graphP theGraph)
int	gp_CreateRandomGraphEx (graphP theGraph, int numEdges)
void	gp_Free (graphP *pGraph)
int	gp_Read (graphP theGraph, char *FileName)
int	gp_Write (graphP theGraph, char *FileName, int Mode)
int	gp_IsNeighbor (graphP theGraph, int u, int v)
int	gp_GetVertexDegree (graphP theGraph, int v)
int	gp_AddEdge (graphP theGraph, int u, int ulink, int v, int vlink)
void	gp_HideEdge (graphP theGraph, int arcPos)
void	gp_RestoreEdge (graphP theGraph, int arcPos)
int	gp_DeleteEdge (graphP theGraph, int J, int nextLink)
int	gp_CreateDFSTree (graphP theGraph)
int	gp_SortVertices (graphP theGraph)
void	gp_LowpointAndLeastAncestor (graphP theGraph)
int	gp_Embed (graphP theGraph, int embedFlags)
int	gp_CheckEmbeddingIntegrity (graphP theGraph)
int	gp_CheckKuratowskiSubgraphIntegrity (graphP theGraph)

---

Define Documentation

#define _VertexActiveStatus (  theGraph, theVertex, I   )     (EXTERNALLYACTIVE (theGraph, theVertex, I) ? VAS_EXTERNAL : PERTINENT (theGraph, theVertex, I) ? VAS_INTERNAL : VAS_INACTIVE)

Definition at line 352 of file graph_boyer.h.

#define EDGE_BACK   3

Definition at line 69 of file graph_boyer.h.

#define EDGE_DFSCHILD   1

Definition at line 67 of file graph_boyer.h.

#define EDGE_DFSPARENT   4

Definition at line 70 of file graph_boyer.h.

#define EDGE_FORWARD   2

Definition at line 68 of file graph_boyer.h.

#define EDGE_LIMIT   6

Definition at line 26 of file graph_boyer.h.

#define EMBEDFLAGS_PLANAR   1

Definition at line 342 of file graph_boyer.h.

#define EXTERNALLYACTIVE (  theGraph, theVertex, I   )     (theGraph->V[theVertex].leastAncestor < I ? 1 : theGraph->V[theVertex].separatedDFSChildList != NIL && theGraph->V[theGraph->V[theVertex].separatedDFSChildList].Lowpoint < I ? 1 : 0)

Definition at line 367 of file graph_boyer.h.

#define FLAGS_DFSNUMBERED   1

Definition at line 183 of file graph_boyer.h.

#define FLAGS_MINOR_A   1

Definition at line 225 of file graph_boyer.h.

#define FLAGS_MINOR_B   2

Definition at line 226 of file graph_boyer.h.

#define FLAGS_MINOR_C   4

Definition at line 227 of file graph_boyer.h.

#define FLAGS_MINOR_D   8

Definition at line 228 of file graph_boyer.h.

#define FLAGS_MINOR_E   16

Definition at line 229 of file graph_boyer.h.

#define FLAGS_MINOR_E1   32

Definition at line 230 of file graph_boyer.h.

#define FLAGS_MINOR_E2   64

Definition at line 231 of file graph_boyer.h.

#define FLAGS_MINOR_E3   128

Definition at line 232 of file graph_boyer.h.

#define FLAGS_MINOR_E4   256

Definition at line 233 of file graph_boyer.h.

#define FLAGS_MINOR_E5   512

Definition at line 235 of file graph_boyer.h.

#define FLAGS_MINOR_E6   1024

Definition at line 236 of file graph_boyer.h.

#define FLAGS_MINOR_E7   2048

Definition at line 237 of file graph_boyer.h.

#define FLAGS_SORTEDBYDFI   2

Definition at line 184 of file graph_boyer.h.

#define gp_GetTwinArc (  theGraph, Arc   )     ((Arc) & 1) ? Arc-1 : Arc+1

Definition at line 331 of file graph_boyer.h.

#define MAX (  x, y   )     ((x) > (y) ? (x) : (y))

Definition at line 31 of file graph_boyer.h.

#define MAX3 (  x, y, z   )     MAX(MAX((x), (y)), MAX((y), (z)))

Definition at line 34 of file graph_boyer.h.

#define MIN (  x, y   )     ((x) < (y) ? (x) : (y))

Definition at line 30 of file graph_boyer.h.

#define MIN3 (  x, y, z   )     MIN(MIN((x), (y)), MIN((y), (z)))

Definition at line 33 of file graph_boyer.h.

#define PERTINENT (  theGraph, theVertex, I   )     (theGraph->V[theVertex].adjacentTo != NIL || theGraph->V[theVertex].pertinentBicompList != NIL ? 1 : 0)

Definition at line 360 of file graph_boyer.h.

#define TYPE_UNKNOWN   0

Definition at line 65 of file graph_boyer.h.

#define VAS_EXTERNAL   2

Definition at line 40 of file graph_boyer.h.

#define VAS_INACTIVE   0

Definition at line 38 of file graph_boyer.h.

#define VAS_INTERNAL   1

Definition at line 39 of file graph_boyer.h.

#define VERTEX_HIGH_RXW   6

Definition at line 72 of file graph_boyer.h.

#define VERTEX_HIGH_RYW   8

Definition at line 74 of file graph_boyer.h.

#define VERTEX_LOW_RXW   7

Definition at line 73 of file graph_boyer.h.

#define VERTEX_LOW_RYW   9

Definition at line 75 of file graph_boyer.h.

#define WRITE_ADJLIST   1

Definition at line 336 of file graph_boyer.h.

#define WRITE_ADJMATRIX   2

Definition at line 337 of file graph_boyer.h.

#define WRITE_DEBUGINFO   3

Definition at line 338 of file graph_boyer.h.

---

Typedef Documentation

typedef extFaceLinkRec* extFaceLinkRecP

Definition at line 174 of file graph_boyer.h.

typedef graphNode* graphNodeP

Definition at line 117 of file graph_boyer.h.

typedef BM_graph* graphP

Definition at line 277 of file graph_boyer.h.

typedef isolatorContext* isolatorContextP

Definition at line 223 of file graph_boyer.h.

typedef vertexRec* vertexRecP

Definition at line 160 of file graph_boyer.h.

---

Function Documentation

int gp_AddEdge (  graphP  theGraph, int  u, int  ulink, int  v, int  vlink )

Definition at line 845 of file graphStructure.c.

int gp_CheckEmbeddingIntegrity (  graphP  theGraph  )

Definition at line 51 of file graphTests.c.

int gp_CheckKuratowskiSubgraphIntegrity (  graphP  theGraph  )

Definition at line 159 of file graphTests.c.

int gp_CopyGraph (  graphP  dstGraph, graphP  srcGraph )

Definition at line 367 of file graphStructure.c.

int gp_CreateDFSTree (  graphP  theGraph  )

Definition at line 22 of file graphPreprocess.c.

int gp_CreateRandomGraph (  graphP  theGraph  )

Definition at line 429 of file graphStructure.c.

int gp_CreateRandomGraphEx (  graphP  theGraph, int  numEdges )

Definition at line 599 of file graphStructure.c.

int gp_DeleteEdge (  graphP  theGraph, int  J, int  nextLink )

Definition at line 970 of file graphStructure.c.

graphP gp_DupGraph (  graphP  theGraph  )

Definition at line 403 of file graphStructure.c.

int gp_Embed (  graphP  theGraph, int  embedFlags )

Definition at line 920 of file graphEmbed.c.

void gp_Free (  graphP *  pGraph  )

Definition at line 347 of file graphStructure.c.

int gp_GetVertexDegree (  graphP  theGraph, int  v )

Definition at line 773 of file graphStructure.c.

void gp_HideEdge (  graphP  theGraph, int  arcPos )

Definition at line 929 of file graphStructure.c.

int gp_InitGraph (  graphP  theGraph, int  N )

Definition at line 85 of file graphStructure.c.

int gp_IsNeighbor (  graphP  theGraph, int  u, int  v )

Definition at line 747 of file graphStructure.c.

void gp_LowpointAndLeastAncestor (  graphP  theGraph  )

Definition at line 266 of file graphPreprocess.c.

graphP gp_New (  void   )

Definition at line 52 of file graphStructure.c.

int gp_Read (  graphP  theGraph, char *  FileName )

Definition at line 195 of file graphIO.c.

void gp_ReinitializeGraph (  graphP  theGraph  )

Definition at line 318 of file graphStructure.c.

void gp_RestoreEdge (  graphP  theGraph, int  arcPos )

Definition at line 952 of file graphStructure.c.

int gp_SortVertices (  graphP  theGraph  )

Definition at line 155 of file graphPreprocess.c.

int gp_Write (  graphP  theGraph, char *  FileName, int  Mode )

Definition at line 377 of file graphIO.c.

---