[알고리즘/C++] Euler Cycle

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;
}