Topological sort 알고리즘

/*
 * 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