Untitled

// MCC HW07 Grouping Friends
// 薯妮亞patata

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <sys/time.h>
#define NAMELENGTH 50

// Graph Node
typedef struct sNode {
    int vertex;
    struct sNode* next;
} GNode;

// Graph sophisticated version
typedef struct sGraph {
    GNode **adjLists;       // adjacency lists
    GNode **rev_adjLists;   // reverse adjacency lists
    int *visited;           // 0: not been visited, 1: being visited, 2: visited

    // p, d, f are part of DFS_d in algorithm 4.2.6,
    // but will not be used is this homework
    int *p;                 // predecessor
    int *d;                 // discover time
    int *f;                 // finish time
} Graph;

// Graph operation
Graph* CreateGraph(int vertices);
    // constructor
void DeleteGraph(Graph* graph);
    // destructor
void AddEdge(Graph* graph, int src, int dest);
    // add a directed edge

// Stack
typedef struct sStack {
    int* array;
    int top;
    int capacity;
} Stack;

Stack* CreateStack(int capacity);
    // constrcutor
void DeleteStack(Stack* stack);
	// destrcutor, not automatically triggered like c++
bool IsEmpty(Stack* stack);
    // return true if stack is empty
void Push(Stack* stack, int item);
    // add an element at the top
void Pop(Stack* stack);
    // delete top element
int Top(Stack* stack);
    // return top element of stack
int Size(Stack* stack);
    // return size of stack
void ChangeSize1D(Stack* stack);
    // double the stack size

// DFS algorithms
typedef enum {CALL1, CALL2} DFS_mode;
void DFS_d(Graph* graph, int currentvertex, DFS_mode mode);
    // DFS sophisticated
void DFS_call1(Graph* graph);
    // Reapeatedly call DFS_d to form a forest, push to stack when finished
void DFS_call2(Graph* graph);
    // Use stack from DFS_call1 to call DFS_d, print all SCC
void SCC(Graph* graph);
    // Find SCC
void Swap(Graph* graph);
    // Swap adjacency list(graph transpose)

void ReadInput(Graph* graph);               // read input
int LinearSearch(char* word, char** list);  // search namelist

// Get CPU time(sec)
double GetTime(void);

// Global variable
int times;
int N;
int M;
int v_count = 0;
int subgroupCount = 0;
char **namelist;
Stack *S1, *S2, *S3;     // S1 for record finish order, S2, S3 for print output

int main(void)
{
    int i;
    double t0, t1, t;           // start time, end time, time interval

	scanf("%d %d", &N, &M);

    Graph* graph = CreateGraph(N);

    ReadInput(graph);

    S1 = CreateStack(N);
    S2 = CreateStack(2 * N);
    S3 = CreateStack(2 * N);

    t0 = GetTime();     // get system time

    SCC(graph);

    t1 = GetTime();     // get system time
    t = (t1 - t0);      // calculate time interval

    printf("N = %d M = %d Subgroup = %d CPU time = %g\n",
        N, M, subgroupCount, t);
    printf("Number of subgroups: %d\n", subgroupCount);

    // print subgroup
    subgroupCount = 0;
    while (!IsEmpty(S2)) {
        Push(S3, Top(S2)); Pop(S2);
            // reverse S2 because output requirement will reverse stack order
    }
    while (!IsEmpty(S3)) {
        printf("  Subgroup %d: ", ++subgroupCount);
        while (Top(S3) != -1) {
            printf("%s ", namelist[Top(S3)]); Pop(S3); // print S3 in namelist
        }
        Pop(S3);
        puts("");
    }

    // free memory
    DeleteGraph(graph);
    DeleteStack(S1); DeleteStack(S2); DeleteStack(S3);
    for (i = 0; i < N; i++) free(namelist[i]);
    free(namelist);

    return 0;
}

// Create graph
Graph* CreateGraph(int vertices)
{
    Graph* graph = (Graph*)malloc(sizeof(Graph));

    graph->adjLists = (GNode**)calloc(vertices, sizeof(GNode*));
    graph->rev_adjLists = (GNode**)calloc(vertices, sizeof(GNode*));
    graph->visited = (int*)calloc(vertices, sizeof(int));
    graph->p = (int*)calloc(vertices, sizeof(int));
    graph->d = (int*)calloc(vertices, sizeof(int));
    graph->f = (int*)calloc(vertices, sizeof(int));

    return graph;
}

// destructor
void DeleteGraph(Graph* graph)
{
    GNode *current, *next;
    int i;

    // free adjLists
    for (i = 0; i < N; i++) {
        current = graph->adjLists[i];
        while (current != NULL) {
            next = current->next;
            free(current);
            current = next;
        }
    }
    free(graph->adjLists);

    // free reverse adjLists
    for (i = 0; i < N; i++) {
        current = graph->rev_adjLists[i];
        while (current != NULL) {
            next = current->next;
            free(current);
            current = next;
        }
    }
    free(graph->rev_adjLists);

    free(graph->p);
    free(graph->d);
    free(graph->f);
    free(graph->visited);
    free(graph);
}

// Add edge
void AddEdge(Graph* graph, int src, int dest)
{
    GNode* newNode1 = (GNode*)malloc(sizeof(GNode));
    GNode* newNode2 = (GNode*)malloc(sizeof(GNode));

    // Add edge from src to dest
    newNode1->vertex = dest;
    newNode1->next = graph->adjLists[src];
    graph->adjLists[src] = newNode1;

    // Add reverse adjlist
    newNode2->vertex = src;
    newNode2->next = graph->rev_adjLists[dest];
    graph->rev_adjLists[dest] = newNode2;
}

// DFS sophisiticated version
// CALL1: push S1, CALL2: push S2
void DFS_d(Graph* graph, int currentvertex, DFS_mode mode)
{
    GNode* adjList = graph->adjLists[currentvertex];
    GNode* temp = adjList;
    int connectedVertex;

    graph->visited[currentvertex] = 1;  // visiting
    graph->d[currentvertex] = ++times;  // record discover time

    while (temp != NULL) {
        connectedVertex = temp->vertex;
        if (graph->visited[connectedVertex] == 0) {     // not being visited
            graph->p[connectedVertex] = currentvertex;  // mark predecessor
            DFS_d(graph, connectedVertex, mode);
        }
        temp = temp->next;  // search for next connexted vertex
    }

    graph->visited[currentvertex] = 2;  // visited
    graph->f[currentvertex] = ++times;  // record finish time

    if (mode == CALL1) {
        Push(S1, currentvertex);    // S1 for record finish order
    } else {        // mode == CALL2
        Push(S2, currentvertex);    // S2 for print output
    }
}

// Reapeatedly call DFS_d to form a forest, push to stack when finished
void DFS_call1(Graph* graph)
{
    int i;

    times = 0;  // set time = 0
    for (i = 0; i < N; i++) {
        if (graph->visited[i] == 0) {   // if not been visist, call DFS
            DFS_d(graph, i, CALL1);
            graph->p[i] = -1;           // first vertex, no predecessor
        }
    }
}

// Use stack from DFS_call1 to call DFS_d, print all SCC
void DFS_call2(Graph* graph)
{
    int v;
    int i;

    // initialize
    for (i = 0; i < N; i++) {
        graph->visited[i] = 0;
        graph->p[i] = 0;
        graph->d[i] = 0;
        graph->f[i] = 0;
    }

    while (!IsEmpty(S1)) {
        v = Top(S1); Pop(S1);   // recursively call DFS from S1
        if (graph->visited[v] == 0) {
            DFS_d(graph, v, CALL2);
            graph->p[v] = -1;
            subgroupCount++;
            Push(S2, -1);   // stop sign for printing
        }
    }
}

// Find SCC
void SCC(Graph* graph)
{
    DFS_call1(graph);   // find arbitrary resonable DFS order
    Swap(graph);        // graph transpose
    DFS_call2(graph);   // DFS_call1 order guaranteed to seperate SCC in GT
}

// swap adjacency list(graph transpose)
void Swap(Graph* graph)
{
    GNode **temp;

    temp = graph->adjLists;
    graph->adjLists = graph->rev_adjLists;
    graph->rev_adjLists = temp;
}

// read input
void ReadInput(Graph* graph)
{
    int i;
    char *name1, *name2;
    int v1, v2;

    namelist = (char**)malloc(N * sizeof(char*));
    name1 = (char*)malloc(NAMELENGTH * sizeof(char));
    name2 = (char*)malloc(NAMELENGTH * sizeof(char));

    // read all names
    for (i = 0; i < N; i++) {
        namelist[i] = (char*)malloc(NAMELENGTH * sizeof(char));
        scanf("%s", namelist[i]);
    }

    // read all connections
    for (i = 0; i < M; i++) {
        scanf("%s -> %s", name1, name2);
        v1 = LinearSearch(name1, namelist); // find name
        v2 = LinearSearch(name2, namelist);
        AddEdge(graph, v1, v2);
    }

    // free memory
    free(name1);
    free(name2);
}

// sear namelist
int LinearSearch(char* word, char** list)
{
    int i;

    for (i = 0; i < N; i++) {
        if (strcmp(word, list[i]) == 0) return i;
    }
    return -1;
}

// constructor
Stack* CreateStack(int capacity)
{
    Stack* stack = (Stack*)malloc(sizeof(Stack));

    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));

    return stack;
}

// destructor
void DeleteStack(Stack* stack)
{
    free(stack->array);
    free(stack);
}

// return true if stack is empty
bool IsEmpty(Stack* stack)
{
    return stack->top == -1;
}

// add an element at the top
void Push(Stack* stack, int item)
{
    if (stack->top == stack->capacity - 1) {
        ChangeSize1D(stack);
    }
    stack->array[++stack->top] = item;
}

// delete top element
void Pop(Stack* stack)
{
    if (!IsEmpty(stack)) {
        stack->top--;
    }
}

// return top element of stack
int Top(Stack* stack)
{
    return stack->array[stack->top];
}

// return size of stack
int Size(Stack* stack)
{
    return stack->top + 1;
}

// double the stack size
void ChangeSize1D(Stack* stack)
{
    stack->capacity *= 2;
    stack->array = (int*)realloc(stack->array, stack->capacity * sizeof(int));
}

// Get CPU time(sec)
double GetTime(void)
{
    struct timeval tv;

    gettimeofday(&tv, NULL);
    return tv.tv_sec + tv.tv_usec * 1e-6;
}