DBL 사용
헤더
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define NONE -1
extern void Error_Exit(const char *s);
//
// Functions for Doubly Linked List for Graph Adjacent List
//
typedef struct _DBL { // Adjacent list element structure
int d;
struct _DBL *twin; // the other DBL pointer
struct _DBL *lp, *rp;
} DBL;
class DBList {
private:
DBL *DBL_pool;
public:
unsigned long DBL_cnt;
unsigned long UsedMemoryForDBLs;
DBList(void) {
DBL_pool = NULL;
DBL_cnt = 0;
UsedMemoryForDBLs = 0;
}
~DBList(void) {
}
DBL *allocDBL(void);
void freeDBL(DBL *p);
void freeDBL_pool(void);
};
class dblStack {
private:
DBL *ST;
public:
dblStack(void) {
ST = NULL;
}
~dblStack(void) {
}
void push(DBL *p);
DBL *pop(void);
void remove(DBL *p);
DBL *top(void);
bool empty(void); // true if the stack is empty
};
소스코드
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#include <time.h>
#include <stack>
#include "DBL.h"
void Error_Exit(const char *s);
typedef struct _Vertex {
dblStack S; // adj list contains edge index
int degree;
} Vertex;
typedef struct _Edge {
int v1, v2;
} Edge;
void graphGeneration(Vertex **V, Edge **E, int *VN, int *EN);
void adjListGenerate(Vertex *V, Edge *E, int VN, int EN);
void deallocGraph(Vertex *V, Edge *E, int VN);
int *Find_Euler(Vertex *V, Edge *E, int VN, int EN, int *flag, int *pathN);
DBList pool; // DBL storage pool
int main() {
int T, VN, EN;
Vertex *V;
Edge *E;
int *path; // Euler cycle or path
int pathN; // path length
int flag; // 0: cycle, 1: path, 2: none
clock_t start_time, finish_time;
scanf("%d", &T); // read # of tests
for (int t = 1; t <= T; t++) { // for each test
graphGeneration(&V, &E, &VN, &EN);
start_time = clock(); // set the start time
path = Find_Euler(V, E, VN, EN, &flag, &pathN); // find an Euler path or cycle
finish_time = clock(); // set finish time
double cmpt = (((double)(finish_time - start_time)) / CLK_TCK)*1000; // compute the time passed
printf("Test= %d flag= %d VnumInCycle/Path)= %d ", t, flag, pathN);
if (flag == 0)
printf("Euler_cycle(exec_time= %.2f msec)\n",cmpt);
else if (flag == 1)
printf("Euler_path(exec_time= %.2f msec)\n", cmpt);
else
printf("not_Eulerian(exec_time= %.2f msec)\n", cmpt);
#ifndef NO_PATH_OUT
if (flag != 2) {
for (int i = 0; i < EN + 1; i++) {
printf("%d\n", path[i]);
}
}
#endif
if (flag != 2) delete[] path;
deallocGraph(V, E, VN);
}
pool.freeDBL_pool(); // clear all the DBL elements
return 0;
}
int *Find_Euler(Vertex *V, Edge *E, int VN, int EN, int *flag, int *pathN) {
// input V, VN, E, EN
// output through paramters
// *flag = 0 (Euler cycle), 1 (Euler path), 2 (not Eulerian)
// *pathN = size of path[] array
// output by return
// *path = list of vertex ids found(Euler cycle or path)
stack<int> ST; // STL 스택을 사용한다
int *path = NULL;
int checkOdd = 0; // 0개면 Euler Cycle, 2개면 Euler Path, 그 외는 존재X
int start;
for (int v = 0; v < VN; v++) {
if (V[v].degree % 2 == 1) {
checkOdd++;
start = v; // Euler Path의 경우 홀수 degree vertex에서 시작해야 하므로
}
}
if (checkOdd == 0) {
*flag = 0;
start = 0; // Euler Cycle은 아무데서나 시작해도 괜찮다.
}
else if (checkOdd == 2) *flag = 1; // 위에서 start가 지정되었다
else {
*flag = 2;
*pathN = 0;
return path; // NULL상태
}
path = new int[EN + 1];
ST.push(start);
int v;
*pathN = 0;
while (!ST.empty()) {
v = ST.top();
if (V[v].degree == 0) {
// v를 path에 추가하고 ST에서 제거(pop)한다
(*pathN)++;
path[(*pathN)-1] = v;
ST.pop();
}
else {
// v에 인접한 임의의 에지를 선택하고, 그 에지를 그래프에서 제거하고, 스택에 w를 푸시한다
DBL *edgeS = V[v].S.top();
int e = (*edgeS).d;
int w; // e는 (v,w)
if (v == E[e].v1) w = E[e].v2;
else w = E[e].v1;
DBL *pw = edgeS->twin;
V[w].S.remove(pw);
pool.freeDBL(pw);
V[v].S.pop();
pool.freeDBL(edgeS);
V[v].degree--;
V[w].degree--;
ST.push(w);
}
}
return path;
}
void deallocGraph(Vertex *V, Edge *E, int VN) {
DBL *p;
// adj list를 삭제하는 routine
// adj list의 원소 제거
for (int k = 0; k < VN; k++) {
while (!V[k].S.empty()) {
p = V[k].S.pop();
pool.freeDBL(p);
}
}
// V,E배열 삭제
delete[] V;
delete[] E;
}
void graphGeneration(Vertex **V, Edge **E, int *VN, int *EN) {
scanf("%d %d", VN, EN); // read # of vertices and edges
//allocVandEarray(V, E, *VN, *EN); // vertex and edge array allocation
*V = new Vertex[*VN];
*E = new Edge[*EN];
if (*V == NULL || *E == NULL) Error_Exit("Memory Allocation Error!");
for (int v = 0; v < *VN; v++) {
(*V)[v].degree = 0;
}
for (int e = 0; e < *EN; e++) {
scanf("%d %d", &((*E)[e].v1), &((*E)[e].v2)); // read edge information
++((*V)[(*E)[e].v1].degree);
++((*V)[(*E)[e].v2].degree);
}
adjListGenerate(*V, *E, *VN, *EN); // create adj lust in G=(V,E)
}
void adjListGenerate(Vertex *V, Edge *E, int VN, int EN) {
// Construct adjacent list in V array
int v1, v2;
DBL *adjE1, *adjE2;
for (int e = 0; e < EN; e++) {
// Edge 안의 v1과 v2에 대해서..
// DBL에다가 twin으로 v1,v2 정보 연결시키고
// 각 v 리스트에 push하기
v1 = E[e].v1; v2 = E[e].v2;
adjE1 = pool.allocDBL(); adjE2 = pool.allocDBL();
adjE1->d = e; adjE2->d = e; // 에지 인덱스
adjE1->twin = adjE2; adjE2->twin = adjE1; // twin 포인터
V[v1].S.push(adjE1); V[v2].S.push(adjE2);
}
}
void Error_Exit(const char *s) {
printf("%s", s);
exit(-1);
}
DBL *DBList::allocDBL(void) { // allocate a DBL element
DBL *p;
if (DBL_pool == NULL) { // pool=empty, call malloc
p = new DBL;
if (p == NULL) {
Error_Exit("Memory alloc error(Alloc_DBL)");
}
UsedMemoryForDBLs += sizeof(DBL);
p->d = NONE;
}
else { // get an slm from the DBL_pool
p = DBL_pool;
DBL_pool = p->rp; // rp를 사용하여 pool 연결
}
p->rp = p->lp = p->twin = NULL; // clear pointers
++DBL_cnt;
return(p);
}
void DBList::freeDBL(DBL *p) {
// move p to pool
if (p->d == NONE) {
Error_Exit("This element is already freed(Free_DBL).");
}
p->d = NONE;
p->rp = DBL_pool; // p->rp points to DBL_pool
DBL_pool = p; // p becomes the 1st element
--DBL_cnt; // reduce # of active DBL elements by one
}
void DBList::freeDBL_pool(void) {
DBL *p = DBL_pool;
while (p != NULL) {
DBL_pool = p->rp; // get next pointer
delete p;
p = DBL_pool;
UsedMemoryForDBLs -= sizeof(DBL);
}
if (DBL_cnt != 0) {
Error_Exit("Non-zero DBL_cnt after cleanup.");
}
}
void dblStack::push(DBL *p) {
if (ST != NULL) {
ST->lp = p; // link left pointer if Q != NULL
}
p->rp = ST;
p->lp = NULL;
ST = p; // p becomes the 1st element of Q
}
DBL *dblStack::pop(void) { // remove and return p in front of Q
DBL *p;
p = ST;
if (ST->rp == NULL) ST = NULL;
else {
ST = ST->rp;
ST->lp = NULL;
}
return p;
}
void dblStack::remove(DBL *p) { // delete p from ST
if (ST == p) { // p is the 1st element of ST
ST = p->rp; // assign p->rp to Q (may be NULL)
if (p->rp != NULL) { // p is not the only elm
(p->rp)->lp = NULL; // p 우의 좌를 NULL
}
}
else { // p is not the 1st element
(p->lp)->rp = p->rp; // p의 좌의 우를 p의 우로
if (p->rp != NULL) { // p is not last
(p->rp)->lp = p->lp; // p의 우의 좌를 p의 좌로
}
}
}
DBL *dblStack::top(void) {
return ST;
}
bool dblStack::empty(void) {
if (ST == NULL) return true;
else return false;
}