친구관계정리 - Dijkstra / Graph / List

 
//
//  main.c
//  HomeWork2
//
//  Created by Skia on 2015. 7. 9..
//  Copyright (c) 2015년 Skia. All rights reserved.
//

#include "Graph.h"

void ReadData(FILE* input, Graph* fr); // read data from the input file and add edge info
void WriteData(FILE* output, Graph* fr); // Write data to a output file that contains shortpath info
void PrintPath(FILE* output, Graph* fr, int fromIdx, char path[]);

int main(int argc, const char * argv[]) {
    Graph fr;
    FILE* input;
    FILE* output;
    
    
    if (  (input = fopen("test_input","rt")) == NULL){
        printf("Error! There is No input File. Please check out FILE NAME!");
        exit(EXIT_SUCCESS);
    }
    else {
        printf("Success! Readin rg input File is complete\n");
    }

    if ( (output = fopen("test_output","wt")) == NULL){
        printf("Error! There is No Output File. Please check out FILE NAME!\n");
        exit(EXIT_SUCCESS);
    }
    else {
        printf("Success! Reading output File is complete\n");
    }
    
    GraphInit(&fr);
    ReadData(input, &fr);
    WriteData(output, &fr);
    return 0;
}

void ReadData(FILE* input, Graph* fr){
    char str[10]; // string from the input file
    char fromV[10]; // first string
    char toV[10]; // second string
    int flag = 0; // the flag to save seperated string
    
    while ( !(fscanf(input,"%s", str) == EOF)){
        if (flag == 0){
            sscanf(str, "%[^.,\"\'!?]", fromV);
            flag++;
        }
        else{
            sscanf(str,"%s", toV);
            AddEdge(fr, fromV, toV);
            flag = 0;
        }
    }
    
    fclose(input);
    
    
}

void WriteData(FILE* output, Graph* fr){
    char path[MAX_LIST];
    int i;
    for (i = 0; i < MAX_LIST; i++){
        if(fr->adjList[i].head != NULL){
            memset(path,-1,26);
            ShortPath(fr, i, path);
            fprintf(output,"%s",fr->adjList[i].head->data); fprintf(output,"\n");
            PrintPath(output,fr,i,path);
        }
    }
}


void PrintPath(FILE* output, Graph* fr, int fromIdx, char path[]){
    int i;
    int previous,j;
    
    for (i = 0; i < MAX_LIST; i++){
        if( i != fromIdx && fr->adjList[i].head != NULL){
            j = i;
            fprintf(output,"\t");
            fprintf(output,"%s ", fr->adjList[i].head->data);
            
            if( path[i] == -1){ // 경로가 없는 경우
                fprintf(output,"( - )");
            }
            else{
                fprintf(output,"(");
                while( path[j] != fromIdx){
                    previous = path[j];
                    fprintf(output,"%s ", fr->adjList[previous].head->data);
                    j = previous;
                }
                fprintf(output,")");
            }
            fprintf(output,"\n");
        }
    }
}

//
//  Graph.c
//  HomeWork2
//
//  Created by Skia on 2015. 7. 9..
//  Copyright (c) 2015년 Skia. All rights reserved.
//

#include "Graph.h"
#define NOEDGE 999

void InsertWeight(Graph* fr, int weight, int fromIdx, char* toV);
int SearchWeight(Graph* fr, int fromIdx, int toIdx);
int find(int distance[], int found[]);

void GraphInit(Graph* fr){
    int i;
    
    fr->numE = 0;
    
    for(i = 0; i < MAX_LIST; i++){
        ListInit(&(fr->adjList[i]));
    }
    
}

void AddEdge(Graph* fr, char* fromV, char* toV){
    int fromIdx = fromV[0] - 65;
    int toIdx = toV[0] - 65;
    
    int weight = 1;
    
    /*printf("Input weight (%c - %c) : ",fromV[0],toV[0]);
    scanf("%d", &weight);*/
    
    if ( fr->adjList[fromIdx].head == NULL){
        ListInsert(&(fr->adjList[fromIdx]), fromV);
        fr->numV++;
    }
    
    if ( fr->adjList[toIdx].head == NULL){
        ListInsert(&(fr->adjList[toIdx]), toV);
        fr->numV++;
    }
    
    ListInsert(&(fr->adjList[fromIdx]), toV);
    ListInsert(&(fr->adjList[toIdx]), fromV);
    InsertWeight(fr, weight, fromIdx, toV);
    InsertWeight(fr, weight, toIdx, fromV);
}

void DisplayGraph(Graph* fr){
    int i;
    
    for ( i = 0; i < MAX_LIST ; i++){
        if(fr->adjList[i].head != NULL){
            ListRef(&(fr->adjList[i]));
            printf("\n");
        }
        
    }
}

void InsertWeight(Graph* fr, int weight, int fromIdx, char* toV){
    Node* temp;
    
    temp = fr->adjList[fromIdx].head;
    
    while( temp != NULL ){
        if ( strcmp(toV, temp->data) == 0 ){
            temp->weight = weight;
            break;
        }
        temp = temp->link;
    }
    
}

int SearchWeight(Graph* fr, int fromIdx, int toIdx){
    Node* temp = fr->adjList[fromIdx].head;
    
    while( temp != NULL){
        if( temp->data[0] == (toIdx + 65)){
            return temp->weight;
        }
        temp = temp->link;
    }
    
    return NOEDGE;
}



void ShortPath(Graph* fr, int fromIdx, char path[]){
    int distance[MAX_LIST];
    int found[MAX_LIST];
    Node* temp = fr->adjList[fromIdx].head->link;
    int tempIdx;
    int minIdx;
    int i;
    int destIdx;
    
    for (i = 0; i < MAX_LIST; i++){
        found[i] = FALSE;
        distance[i] = NOEDGE;
    }
    
    found[fromIdx] = TRUE;
    distance[fromIdx] = 0; // 자기자신에 해당하는 거리값은 0
    
    while(temp != NULL){ // 초기 Vertex와 adjacency Vertex에 해당하는 distance에 값 삽입.
        tempIdx = temp->data[0]-65;
        distance[tempIdx] = temp->weight;
        temp = temp->link;
    }
    
    for(i = 0; i < fr->numV - 1; i++){
        minIdx = find(distance,found);
        if(minIdx == NOEDGE){
            break;
        }
        found[minIdx] = TRUE;
        
        if(found[minIdx] == TRUE && SearchWeight(fr, fromIdx, minIdx) != NOEDGE){
            path[minIdx] = fromIdx; // fromVertex와 adjacency 일 경우 경로저장!
        }
        
        for(destIdx = 0; destIdx < MAX_LIST; destIdx++){
            if(distance[destIdx] > distance[minIdx] + SearchWeight(fr, minIdx, destIdx)){
                distance[destIdx] = distance[minIdx] + SearchWeight(fr, minIdx, destIdx);
                path[destIdx] = minIdx; // 새로운 경로를 찾고난 후 destination의 전 노드 를 경로에 저장
            }
        }
    }
    
    /*for(i = 0; i < MAX_LIST; i++){
        if(fr->adjList[i].head != NULL && i != fromIdx){ // 없는 노드와 자기자신을 제외하고 최단거리 출력
            printf("distance[%c]의 값 : %d", i+65,distance[i]);
            printf("\n");
        }
    }
    
    for(i = 0; i < MAX_LIST; i++){
        if(fr->adjList[i].head != NULL){ // 없는 노드와 자기자신을 제외하고 최단거리 출력
            printf("path[%c]의 값 : %c", i+65,path[i]+65);
            printf("\n");
        }
    }*/
    
    
}

int find(int distance[], int found[]){
    int min = INT16_MAX;
    int minIdx = -1; // arr index에 영향을 주지않기 위해 음수 설정
    int i;
    
    for(i = 0; i < MAX_LIST; i++){
        if(distance[i] < min && !found[i]){
            min = distance[i];
            minIdx = i;
        }
    }
    
    return minIdx;
}

 
//
//  Graph.h
//  HomeWork2
//
//  Created by Skia on 2015. 7. 9..
//  Copyright (c) 2015년 Skia. All rights reserved.
//

#ifndef __HomeWork2__Graph__
#define __HomeWork2__Graph__

#include "List.h"

#define TRUE 1
#define FALSE 0
#define MAX_LIST 26

typedef struct _graph{
    int numV;
    int numE; // Number of Edge
    List adjList[MAX_LIST];
    
}Graph;

void GraphInit(Graph* fr);// fr : Freinds Relatinship
void AddEdge(Graph* fr, char* fromV, char* toV);
void DisplayGraph(Graph* fr);
void ShortPath(Graph* fr, int fromIdx, char path[]);

#endif /* defined(__HomeWork2__Graph__) */

 
//
//  List.c
//  HomeWork2
//
//  Created by Skia on 2015. 7. 9..
//  Copyright (c) 2015년 Skia. All rights reserved.
//

#include "List.h"


void ListInit(List* plist){ // Initialization
    plist->head = NULL;
    plist->count = 0;
    
}

void ListInsert(List* plist, LData data){ // Data Insert
    Node* newNode = (Node*) malloc(sizeof(Node));
    
    newNode->data = (char*) malloc(strlen(data)+1);
    strcpy(newNode->data, data);
    newNode->link = NULL;
    
    if (plist->count == 0){
        plist->head = newNode; 
    }
    else{
        plist->tail->link = newNode;
    }
    
    plist->tail = newNode;
    plist->count++;
    
}
/*
LData ListRemove(List* plist){
    
}
*/
void ListRef(List* plist){ // refer list's contents
    Node* cur = plist->head;
    
    while(cur != NULL){
        printf("%s \n", cur->data);
        cur = cur->link;
    }
    
}

 
//
//  List.h
//  HomeWork2
//
//  Created by Skia on 2015. 7. 9..
//  Copyright (c) 2015년 Skia. All rights reserved.
//

#ifndef __HomeWork2__List__
#define __HomeWork2__List__

#include 
#include 
#include 

typedef char* LData;
typedef struct _node{
    LData data;
    int weight;
    struct _node* link;
}Node;

typedef struct _list{
    Node* head;
    Node* tail;
    int count;
}List;

void ListInit(List* plist);
void ListInsert(List* plist, LData data);
void ListRef(List* plist);


#endif /* defined(__HomeWork2__List__) */

자료구조 독학하고 나서 만들어보는 첫 구현. 다소 복잡하고 주석이 달려있지 않아 제 3가 보기에 어렵다는 단점(그 외에도 많지만..) 일단 구현완성에 의의를 둔다. 2학년때 과제였는데 그 때 왜 제출하지 못했을까 라는 후회감이 들정도로 그다지 어렵지 않았던 문제.