-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.h
153 lines (125 loc) · 4.75 KB
/
graph.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#ifndef GRAPH_H
#define GRAPH_H
/******** Graph data structures ******************************/
/**
The vertices of a graph can store certain information
*/
struct Vertex{
char* label;
struct VertexList* neighborhood;
struct Vertex* next;
int number;
int visited;
int lowPoint;
int isStringMaster;
int d;
};
/**
This is used to model edges
*/
struct VertexList{
char* label;
struct VertexList* next;
struct Vertex* startPoint;
struct Vertex* endPoint;
int used;
/* not used atm */
int flag;
int isStringMaster;
};
/**
A graph has n vertices and m edges and a !constant! number of vertices.
*/
struct Graph{
int n;
int m;
int number;
int activity;
struct Vertex** vertices;
struct Graph* next;
};
/**
A ShallowGraph is a container for a list of edges representing a subgraph of some Graph
*/
struct ShallowGraph{
struct VertexList* edges;
struct VertexList* lastEdge;
int m;
struct ShallowGraph* next;
struct ShallowGraph* prev;
int data;
};
/******** Object pools *****************************************/
struct ShallowGraphPool{
struct ShallowGraph* unused;
struct ShallowGraph* tmp;
struct ListPool* listPool;
unsigned int initNumberOfElements;
struct ShallowGraph* poolPointer; /* store pointer to the alloc'd pool space */
};
struct GraphPool{
struct Graph* unused;
struct Graph* tmp;
struct VertexPool* vertexPool;
struct ListPool* listPool;
unsigned int initNumberOfElements;
struct Graph* poolPointer; /* store pointer to the alloc'd pool space */
};
struct ListPool{
struct VertexList* unused;
struct VertexList* tmp;
unsigned int initNumberOfElements;
struct VertexList* poolPointer; /* store pointer to the alloc'd pool space */
};
struct VertexPool{
struct Vertex* unused;
struct Vertex* tmp;
unsigned int initNumberOfElements;
struct Vertex* poolPointer; /* store pointer to the alloc'd pool space */
};
/******* VertexList ******************************************/
struct VertexList* push(struct VertexList* list, struct VertexList* e);
struct VertexList* shallowCopyEdge(struct VertexList* e, struct ListPool* p);
struct VertexList* inverseEdge(struct VertexList* e, struct ListPool* p);
/******* Vertex ***********************************************/
struct Vertex* shallowCopyVertex(struct Vertex *v, struct VertexPool *p);
void removeEdge(struct Vertex* v, struct Vertex* w, struct ListPool* p);
struct VertexList* snatchEdge(struct Vertex* v, struct Vertex* w);
void addEdge(struct Vertex* v, struct VertexList* e);
int degree(struct Vertex* v);
char isLeaf(struct Vertex* v);
int commonNeighborCount(struct Vertex* v, struct Vertex* w);
char isIncident(struct Vertex* v, struct Vertex* w);
char isDegreeTwoVertex(struct Vertex* v);
/******* ShallowGraph ******************************************/
struct ShallowGraph* cloneShallowGraph(struct ShallowGraph* g, struct ShallowGraphPool* sgp);
void rebaseShallowGraphs(struct ShallowGraph* list, struct Graph* newBase);
void rebaseShallowGraphsOnLowPoints(struct ShallowGraph* list, struct Graph* newBase);
void pushEdge(struct ShallowGraph *g, struct VertexList *e);
void appendEdge(struct ShallowGraph *g, struct VertexList *e);
struct VertexList* popEdge(struct ShallowGraph* g);
struct VertexList* assertLastPointer(struct ShallowGraph* g);
struct ShallowGraph* inverseCycle(struct ShallowGraph* cycle, struct ShallowGraphPool *sgp);
struct ShallowGraph* addComponent(struct ShallowGraph* g, struct ShallowGraph* h);
/******* Graph *************************************************/
struct Graph* cloneGraph(struct Graph* g, struct GraphPool* gp);
struct Graph* cloneInducedGraph(struct Graph* g, struct GraphPool* gp);
struct Graph* mergeGraphs(struct Graph* g, struct GraphPool* gp);
struct Vertex** setVertexNumber(struct Graph* g, int n);
struct Graph* emptyGraph(struct Graph* g, struct GraphPool* gp);
struct Graph* createGraph(int n, struct GraphPool* gp);
void addEdgeBetweenVertices(int v, int w, char* label, struct Graph* g, struct GraphPool* gp);
void addEdges(struct Graph* g, struct ShallowGraph* list, struct GraphPool* gp);
struct VertexList* deleteEdge(struct Graph* g, int v, int w);
void deleteEdges(struct Graph* g, struct ShallowGraph* list, struct GraphPool* gp);
void deleteEdgeBetweenVertices(struct Graph* g, struct VertexList* idx, struct GraphPool* gp);
char isNeighbor(struct Graph* g, int v, int w);
int getMaxDegree(struct Graph* g);
int getMinDegree(struct Graph* g);
void canonicalizeShallowGraphCached(struct ShallowGraph* g, struct VertexList** edgePointers);
void canonicalizeShallowGraph(struct ShallowGraph* g);
struct Graph* popGraph(struct Graph** list);
struct ShallowGraph* getGraphEdges(struct Graph *g, struct ShallowGraphPool* sgp);
struct Graph* shallowGraphToGraph(struct ShallowGraph* edgeList, struct GraphPool* gp);
#include "memoryManagement.h"
#endif /* GRAPH_H */