prog-0219

// graph_demo_c.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
typedef struct vertex VERTEX;
typedef struct vertex_node VERTEX_NODE;
typedef struct vertex_list VERTEX_LIST;

typedef struct edge EDGE;
typedef struct edge_node EDGE_NODE;
typedef struct edge_list EDGE_LIST;
typedef struct graph GRAPH;

struct vertex {
    char *vertex_name;  //назва
    bool visited;       //індикатор відвідування
    VERTEX_LIST *neighbours; //список сусідів
};

struct vertex_node {
    VERTEX *value;   // дані
    VERTEX_NODE *prev;   // поле зв'зку
    VERTEX_NODE *next;   // поле зв'зку
};

struct vertex_list {
    struct vertex_node *head;   // поле зв'зку
    struct vertex_node *tail;   // поле зв'зку
};

struct edge {
    VERTEX* vertFrom;
    VERTEX* vertTo;
};

struct edge_node {
    EDGE value;   // дані
    EDGE_NODE *prev;   // поле зв'зку
    EDGE_NODE *next;   // поле зв'зку
};

struct edge_list {
    EDGE_NODE *head;
    EDGE_NODE *tail;
};


struct graph {
    VERTEX_LIST vertex_list;
    EDGE_LIST edge_list;
    unsigned count;
};

VERTEX_NODE *makeVertexNode(VERTEX *v);
EDGE_NODE* makeEdgeNode(EDGE *e);
void initGraph(GRAPH *g);

void addVertex(GRAPH *g, VERTEX *v);
void removeVertex(GRAPH *g, VERTEX *v);

bool addEdge(GRAPH *g, EDGE *e);
void removeEdge(GRAPH *g, EDGE *e);
void removeEdgeV(GRAPH *g, VERTEX *from, VERTEX *to);

void addNeighbour(VERTEX *v, VERTEX *n);
void removeNeibour(VERTEX_NODE *node, VERTEX *key);

bool isConnected(VERTEX *v, VERTEX *n);
VERTEX_NODE *findVertex(VERTEX_LIST *vl, VERTEX *key);
void printGraph(GRAPH *g);
bool BFS_traversal(GRAPH *g, VERTEX *start, VERTEX *goal);
bool DFS_traversal(GRAPH *g, VERTEX *start, VERTEX *goal);
void q_push(VERTEX_LIST *q, VERTEX_NODE *value);

int _tmain(int argc, _TCHAR* argv[])
{
    GRAPH g;
    VERTEX v[] = { { "0", NULL }, { "1", NULL }, { "2", NULL }, { "3", NULL },
                   { "4", NULL }, { "5", NULL }, { "6", NULL }, { "7", NULL } };
    EDGE edge[] = { { &v[0], &v[2] },
                    { &v[0], &v[5] },
                    { &v[0], &v[7] },
                    { &v[1], &v[7] },
                    { &v[2], &v[6] },
                    { &v[3], &v[4] },
                    { &v[3], &v[5] },
                    { &v[4], &v[6] },
                    { &v[4], &v[7] }};

    initGraph(&g);
    for (size_t i = 0; i < 8; i++) addVertex(&g, &v[i]);
    for (size_t i = 0; i < 9; i++) addEdge(&g, &edge[i]);

    //printGraph(&g);
    //removeEdge(&g, &edge);

    puts("----------");
    printGraph(&g);
    if (BFS_traversal(&g, &v[0], &v[3]))
        puts("Yes!");
    else
        puts("No!");

    if (DFS_traversal(&g, &v[0], &v[3]))
        puts("Yes!");
    else
        puts("No!");
    return 0;
}


VERTEX_NODE *makeVertexNode(VERTEX *v)
{
    VERTEX_NODE *tmp = (VERTEX_NODE *)calloc(1, sizeof(VERTEX_NODE));
    tmp->value = v;
    return tmp;
}

EDGE_NODE* makeEdgeNode(EDGE *e)
{
    EDGE_NODE *tmp = (EDGE_NODE *)calloc(1, sizeof(EDGE_NODE));
    tmp->value = *e;
    return tmp;
}

void initGraph(GRAPH *g)
{
    g->vertex_list.head = g->vertex_list.tail = NULL;
    g->edge_list.head = g->edge_list.tail = NULL;
    g->count = 0;
}

void addVertex(GRAPH *g, VERTEX *v)
{
    VERTEX_NODE *vn = makeVertexNode(v);
    if (g->vertex_list.head == NULL){
        g->vertex_list.head = g->vertex_list.tail = vn;
    }
    else
    {
        g->vertex_list.tail->next = vn;
        vn->prev = g->vertex_list.tail;
        g->vertex_list.tail = vn;
    }
    g->count++;
}

bool addEdge(GRAPH *g, EDGE *e)
{
    VERTEX_NODE *vFrom, *vTo;
    if ((vFrom = findVertex(&g->vertex_list, e->vertFrom)) == NULL)
        return false;
    if ((vTo = findVertex(&g->vertex_list, e->vertTo)) == NULL)
        return false;

    if (isConnected(e->vertFrom, e->vertTo))
        return false;

    EDGE_NODE *en = makeEdgeNode(e);
    if (g->edge_list.head == NULL){
        g->edge_list.head = g->edge_list.tail = en;
    }
    else
    {
        g->edge_list.tail->next = en;
        en->prev = g->edge_list.tail;
        g->edge_list.tail = en;
    }

    addNeighbour(e->vertFrom, e->vertTo);
    addNeighbour(e->vertTo, e->vertFrom);
    return true;
}

VERTEX_NODE *findVertex(VERTEX_LIST *vl, VERTEX *key)
{
    VERTEX_NODE *temp;
    for (temp = vl->head; temp != NULL; temp = temp->next)
        if (strcmp(temp->value->vertex_name, key->vertex_name) == 0)
            break;
    return temp;
}

void addNeighbour(VERTEX *v, VERTEX *n)
{
    VERTEX_LIST *vl = v->neighbours;
    VERTEX_NODE *vn = makeVertexNode(n);
    if (vl == NULL){
        v->neighbours = (VERTEX_LIST*)calloc(1, sizeof(VERTEX_LIST));
        v->neighbours->head = v->neighbours->tail = vn;
    }
    else {
        vl->tail->next = vn;
        vn->prev = vl->tail;
        vl->tail = vn;
    }
}

void printGraph(GRAPH *g)
{
    puts("----------");
    for (VERTEX_NODE* temp = g->vertex_list.head; temp != NULL; temp = temp->next)
    {
        if ((temp->value->neighbours!=NULL) && (temp->value->neighbours->head!=NULL))
        {
            printf("%s connected", temp->value->vertex_name);
            for (VERTEX_NODE* temp1 = temp->value->neighbours->head; temp1 != NULL; temp1 = temp1->next)
                printf("\t%s", temp1->value->vertex_name);
            putchar('\n');
        }
        else
            printf("%s not connected\n", temp->value->vertex_name);

    }
}

bool isConnected(VERTEX *v, VERTEX *n)
{
    VERTEX_LIST *vl = v->neighbours;
    if (vl == NULL) return false;
    for (VERTEX_NODE *temp = vl->head; temp != NULL; temp = temp->next)
    {
        if (temp->value == n) return true;
    }
    return false;
}

bool BFS_traversal(GRAPH *g, VERTEX *start, VERTEX *goal){
    for (VERTEX_NODE *temp = g->vertex_list.head; temp != NULL;
        temp = temp->next)
        temp->value->visited = false;
    VERTEX_LIST queue = { NULL, NULL };

    VERTEX_NODE *start_node = findVertex(&g->vertex_list, start);
    q_push(&queue, start_node);
    start_node->value->visited = true; // начиная с узла-источника
    while (queue.head != NULL) {            // пока очередь не пуста
        VERTEX_NODE *node = queue.head;                 // извлечь первый элемент в очереди
        printf("Visit in %s\n", node->value->vertex_name);
        queue.head = queue.head->next;
        if (strcmp(node->value->vertex_name, goal->vertex_name) == 0) {
            return true;                       // проверить, не является ли текущий узел целевым
        }
        for (VERTEX_NODE *child = node->value->neighbours->head;
            child != NULL; child = child->next) // все преемники текущего узла, ...
            if (child->value->visited == false) {      // ... которые ещё не были посещены ...
            q_push(&queue, child);                  // ... добавить в конец очереди...
            child->value->visited = true;           // ... и пометить как посещённые
            }
        free(node);
    }
    return false;                        // Целевой узел недостижим
}
void q_push(VERTEX_LIST *q, VERTEX_NODE *nd)
{
    VERTEX_NODE *node = makeVertexNode(nd->value);
    if (q->head == NULL)
        q->head = q->tail = node;
    else
    {
        q->tail->next = node;
        node->prev = q->tail;
        q->tail = node;
    }
}

void s_push(VERTEX_LIST *st, VERTEX_NODE *nd)
{
    VERTEX_NODE *temp = makeVertexNode(nd->value);
    if (st->head != NULL)
    {
        temp->next = st->head;
        temp->prev = NULL; //unused
    }
    st->head = temp;
}

bool DFS_traversal(GRAPH *g, VERTEX *start, VERTEX *goal){
    VERTEX_LIST st = { NULL, NULL };
    for (VERTEX_NODE *temp = g->vertex_list.head; temp != NULL; temp = temp->next)
        temp->value->visited = false;
    VERTEX_NODE *start_node = findVertex(&g->vertex_list, start);
    s_push(&st, start_node);
    while (st.head != NULL)
    {
        VERTEX_NODE *node = st.head;
        printf("Visit in %s\n", node->value->vertex_name);
        if (strcmp(node->value->vertex_name, goal->vertex_name) == 0) {
            return true;                       // проверить, не является ли текущий узел целевым
        }
        st.head = st.head->next;
        if (!node->value->visited)
        {
            node->value->visited = true;
            for (VERTEX_NODE *child = node->value->neighbours->head;
                child != NULL; child = child->next)
                // все содседи текущего узла, ...
            {
                s_push(&st, child);
            }
        }
        free(node);
    }
    return false;
}

void removeVertex(GRAPH *g, VERTEX *v)
{
    VERTEX_NODE *node = findVertex(&g->vertex_list, v);
    for (VERTEX_NODE *child = node->value->neighbours->head; child != NULL; child = child->next) // все преемники текущего узла, ...
    {
        removeNeibour(child, node->value);
        removeEdgeV(g, node->value, child->value);
        removeEdgeV(g, child->value, node->value);
    }
    if (node->next != NULL)
        node->next->prev = node->prev;
    node->prev->next = node->next;
    free(node);

}

void removeNeibour(VERTEX_NODE *node, VERTEX *key)
{
    VERTEX_NODE *temp = node->value->neighbours->head;
    if (strcmp(node->value->neighbours->head->value->vertex_name, key->vertex_name) == 0)
    {
        node->value->neighbours->head = temp->next;
        if (node->value->neighbours->head!=NULL)
            node->value->neighbours->head->prev = NULL;
    }
    else
    {
        for (temp = node->value->neighbours->head->next; temp != NULL; temp = temp->next)
            if (strcmp(temp->value->vertex_name, key->vertex_name) == 0)
            {
                if (temp->next != NULL)
                    temp->next->prev = temp->prev;
                temp->prev->next = temp->next;
                free(temp);
                return;
            }
    }
    free(temp);
    return;
}
void removeEdge(GRAPH *g, EDGE *e)
{
    removeEdgeV(g, e->vertFrom, e->vertTo);
    removeEdgeV(g, e->vertTo, e->vertFrom);
    VERTEX_NODE *temp = findVertex(&g->vertex_list, e->vertFrom);
    removeNeibour(temp, e->vertTo);
    temp = findVertex(&g->vertex_list, e->vertTo);
    removeNeibour(temp, e->vertFrom);

}

void removeEdgeV(GRAPH *g, VERTEX *from, VERTEX *to)
{
    EDGE_NODE *temp = g->edge_list.head;
    if ((strcmp(temp->value.vertFrom->vertex_name, from->vertex_name) == 0) &&
        (strcmp(temp->value.vertTo->vertex_name, to->vertex_name) == 0))
    {
        g->edge_list.head = g->edge_list.head->next;
        g->edge_list.head->prev = NULL;
    }
    for (temp = temp->next; temp != NULL; temp = temp->next)
        if ((strcmp(temp->value.vertFrom->vertex_name, from->vertex_name) == 0) &&
            (strcmp(temp->value.vertTo->vertex_name, to->vertex_name) == 0))
        {
            if (temp->next != NULL)
                temp->next->prev = temp->prev;
            temp->prev->next = temp->next;
        }
    free(temp);
}