/*
* http://sosal.tistory.com/
* made by so_Sal
*/
GCC ++ 환경입니다.
인하대학교 유원희 교수님 이산수학 이산수학 기말 프로젝트였는데
근원노드를 찾아가는 부분에서 코드가 좀 지져분해졌네요.
알고리즘 책이나 인터넷에서 좀 찾아보면 좋은 코드들이 많은데..
첨부터 뚝심으로 혼자 짜겠다고 한 결과가 -.- 참;;
좀 더럽습니다 ㅠㅠ.
input파일로부터 노드와 간선을 읽어옵니다.
input ex)
a b
b c
c d
d f
e f
f g
결과값을 output이란 파일로 저장합니다.
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<fcntl.h>
using namespace std;
class TP_sort{
private:
int **matrix; //행렬, 동적으로 생성
char table[200][3];
char node_table[100];
char temp[50];
int row,line;
int sequence;
public:
int len_line;
int fd_input;
int fd_output;
int node;
int flag;
TP_sort(){ //생성자 함수. 변수들 초기화와 파일 디스크립터 추가
len_line=0;
node=0;
sequence=1;
fd_input = open("./input",O_CREAT | O_RDWR);
fd_output = open("./output",O_CREAT | O_TRUNC | O_WRONLY);
}
~TP_sort(){
delete* matrix; //동적배열 삭제
}
void get_from_file(){
while( read(fd_input,temp,4) > 1){
table[len_line][0]=temp[0];
table[len_line][1]=temp[2];
len_line++;
} //파일로부터 읽어들여서 저장한다.
get_node(); //노드들의 갯수를 알아낸 후
matrix = new int* [node]; //2차원 동적 배열 생성
for(int k=0;k<node;k++)
matrix[k]=new int[node];
}
void print_matrix(){
cout<<"간단한 행렬"<<endl;
printf(": : ");
for(int i=0;i<node;i++)
printf(":%c:",node_table[i]);
cout<<endl;
for(int i=0;i<node;i++){
printf(":%c: ",node_table[i]);
for(int j=0;j<node;j++){
if(matrix[i][j]==0)
printf(": :");
else
printf(":■:");
}
cout<<endl;
}
}
void get_node(){ //노드 종류의 갯수 가져온다.
for(int i=0;i<len_line;i++){
for(int j=0;j<2;j++){
if(check_node(table[i][j])){
node_table[node]=table[i][j];
node++;
}
}
}
}
bool check_node(char one){ //get_node()의 서브루틴
for(int i=0;i<node;i++){
if(one == node_table[i])
return false;
}
return true;
}
int where_node(char one){ //make_matrix()의 서브루틴
for(int i=0;i<node;i++)
if(one == node_table[i])
return i;
}
void make_matrix(){
for(int i=0;i<len_line;i++){
line = where_node(table[i][0]); //행
row = where_node(table[i][1]); //열
matrix[line][row]=-1;
}
}
int find_sequence(){ //선행노드가 없는 노드를 찾기 위한 합수
bool ret=false;
for(int i=0;i<node;i++){
for(int j=0;j<node;j++){
if(matrix[j][i]!=0)
ret=true;
}
if(ret==false){
return i; // 행을리턴하여 flag로 가져온다.
} // flag는 mark_sequence()와 mark_zero()를 보자.
ret=false;
}
return -1;
}
void mark_sequence() //선행노드가 없는 노드에 번호를 붙임
{
for(int i=0;i<node;i++)
matrix[i][flag]=1; //메인의 While문 조건에 따라 무한루프가 생기지 않도록 값을 변경
sprintf(temp,"[%c -> %d]",node_table[flag],sequence++);
cout<<"temp :: "<<temp<<endl;
write(fd_output,temp,strlen(temp));
}
void mark_zero() //마크된 노드에 해당되는 선행노드를 모두 F로 바꿔준다
{
for(int i=0; i<node; i++) //해당행을 0으로 만들고 1로 된 부분만 0으로 바꾼다
if(matrix[flag][i]==-1)
matrix[flag][i]=0;
}
bool cycle() //사이클의 유무를 확인하여 있으면 true, 없으면 false리턴
{
for(int i=0; i<node; i++){ //행렬의 값이 a같으면 사이클 존재한다.
for(int j=0; j<node; j++)
if(matrix[i][j]==-1 || matrix[i][j]==0)
return true;
}
return false;
}
void prin(){
for(int i=0;i<node;i++){
for(int j=0;j<node;j++)
cout<<matrix[i][j];
cout<<endl;
}
}
};
int main(){
TP_sort Topological; //객체 생성과 생성자 함수
Topological.get_from_file(); //파일에서 노드를 읽어옴
Topological.make_matrix(); //행렬 생성
Topological.print_matrix(); //행렬 출력
while((Topological.flag=Topological.find_sequence())!=-1){
Topological.mark_sequence();
Topological.mark_zero();
} //노드 순서 결정 및 출력
cout<<endl<<endl<<endl;
if(Topological.cycle()){
cout<<"Cycle exists"<<endl;
write(Topological.fd_output,"\n\ncycle exists\n\n",20);
}
else{
cout<<"No cycle. ^-^"<<endl; //사이클 유무 확인
write(Topological.fd_output,"\n\nNo cycle.\n\n",20);
}
Topological.prin();
cout<<endl;
return 0;
}
좌측 실행의 input (no Cycle)
a b
b c
c d
d f
e f
f g
우측 실행의 input (Cycle..)
a b
b c
c d
d f
e f
f g
g c
'Programing > C- programing' 카테고리의 다른 글
C++ - inline function 인라인 함수 (0) | 2010.09.14 |
---|---|
C++ - 복사생성자 (얕은복사와 깊은복사) (2) | 2010.09.02 |
Default Parameter를 이용한 피보나치 수열 (0) | 2010.09.01 |
Hash function - 나눗셈법 (0) | 2010.09.01 |
이진 탐색트리 삭제 포함 소스 (0) | 2010.08.23 |