Alper Akcan : ~/documents/erdos question

News

Projects

Documents

Contact

RSS Feed

Donations (SF)

 
The erdos question
2006-04-11 17:41

#!/bin/bash

#
# sh ./erdos.sh
#

echo inflating input.txt
cat > input.txt << EOF

K = [[makale1 yazar1 yazar2] [makale2 yazar3 yazar4] [makale3 yazar3 yazar5] [makale4 erdos yazar1] [makale5 erdoz yazar5] [makale6 erdos yazar3]]

EOF

echo inflating list.c
cat > list.c << EOF

#include <stdlib.h>
#include "main.h"

int list_init (list_t **li)
{
        (*li) = (list_t *) malloc(sizeof(list_t));
        if ((*li) == NULL) {
                return -1;
        }
        (*li)->nb_elt = 0;
        return 0;
}

int list_uninit (list_t *li)
{
        free(li);
        return 0;
}

int list_eol (list_t *li, int i)
{
        if (li == NULL) {
                return 1;
        }

        if ((i >= 0) && (i < li->nb_elt)) {
                return 0;
        }

        /* end of list */
        return 1;
}

void * list_get (list_t *li, int pos)
{
        int i = 0;
        list_node_t *ntmp;

        if ((li == NULL) || (pos < 0) || (pos >= li->nb_elt)) {
                /* element does not exist */
                return NULL;
        }

        /* exist because nb_elt > 0 */
        ntmp = li->node;

        while (pos > i) {
                i++;
                ntmp = (list_node_t *) ntmp->next;
        }

        return ntmp->element;
}

int list_add (list_t *li, void *el, int pos)
{
        int i = 0;
        list_node_t *ntmp;
        
        if (li == NULL) {
                return -1;
        }

        if ((pos == -1) || (pos >= li->nb_elt)) {
                /* insert at the end  */
                pos = li->nb_elt;
        }

        if (li->nb_elt == 0) {
                li->node = (list_node_t *) malloc(sizeof(list_node_t));
                li->node->element = el;
                li->nb_elt++;
                return li->nb_elt;
        }

        /* exist because nb_elt > 0  */
        ntmp = li->node;

        if (pos == 0) {
                li->node = (list_node_t *) malloc(sizeof(list_node_t));
                li->node->element = el;
                li->node->next = ntmp;
                li->nb_elt++;
                return li->nb_elt;
        }

        /* pos = 0 insert before first elt  */
        while (pos > (i + 1)) {
                i++;
                /* when pos > i next node exist  */
                ntmp = (list_node_t *) ntmp->next;
        }

        /* if pos == nb_elt next node does not exist  */
        if (pos == li->nb_elt) {
                ntmp->next = (list_node_t *) malloc(sizeof(list_node_t));
                ntmp = (list_node_t *) ntmp->next;
                ntmp->element = el;
                li->nb_elt++;
                return li->nb_elt;
        }

        /* here pos == i so next node is where we want to insert new node */
        {
                list_node_t *nextnode = (list_node_t *) ntmp->next;
                ntmp->next = (list_node_t *) malloc(sizeof(list_node_t));
                ntmp = (list_node_t *) ntmp->next;
                ntmp->element = el;
                ntmp->next = nextnode;
                li->nb_elt++;
        }

        return li->nb_elt;
}

EOF

echo inflating main.c
cat > main.c << EOF


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

#include "main.h"

typedef struct yazar_s {
        char *name;
        int erdos;
        list_t *makal;
        list_t *kanka;
} yazar_t;

typedef struct makale_s {
        char *name;
        list_t *yazar;
} makale_t;

makale_t * makale_new (char *buf)
{
        char *tmp;
        char *ptr;
        char *name;
        makale_t *makale;
        makale = (makale_t *) malloc(sizeof(makale_t));
        if (makale == NULL) {
                printf("(%d) malloc failed", __LINE__);
                return NULL;
        }
        if (list_init(&(makale->yazar))) {
                printf("(%d) list_init failed", __LINE__);
                free(makale);
                return NULL;
        }
        while (*buf == ' ')
                buf++;
        name = strchr(buf, ' ');
        if (name == NULL) {
                return NULL;
        }
        *name = '\0';
        makale->name = strdup(buf);
        *name = ' ';
        tmp = name;
        while (((tmp = strchr(tmp, ' ')) != NULL) &&
               (*++tmp)) {
                while (*tmp == ' ')
                        tmp++;
                ptr = strchr(tmp, ' ');
                if (ptr == NULL) {
                        list_add(makale->yazar, strdup(tmp), -1);
                        break;
                } else {
                        *ptr = '\0';
                        list_add(makale->yazar, strdup(tmp), -1);
                }
                *ptr = ' ';
                tmp = ptr;
        }
        return makale;
}

int buf_parse (char *buf, list_t *list)
{
        char *tmp;
        char *ptr;
        makale_t *mkl;
        
        tmp = strchr(buf, '[');
        if (tmp == NULL) {
                printf("(%d) format error\n", __LINE__);
                return -1;
        }
        tmp++;
        while (((tmp = strchr(tmp, '[')) != NULL) &&
               (*++tmp)) {
                ptr = strchr(tmp, ']');
                if (ptr == NULL) {
                        continue;
                }
                *ptr = '\0';
                mkl = makale_new(tmp);
                if (mkl != NULL) {
                        list_add(list, mkl, -1);
                }
                tmp = ptr + 1;
        }
        
        return 0;
}

int calculate_erdos (yazar_t *yzr)
{
        int i;
        int e;
        yazar_t *tzr;
        e = yzr->erdos;
        if (e < 0) {
                return -1;
        }
        e++;
        for (i = 0; !list_eol(yzr->kanka, i); i++) {
                tzr = (yazar_t *) list_get(yzr->kanka, i);
                if (e < tzr->erdos ||
                    tzr->erdos == -1) {
                        tzr->erdos = e;
                        calculate_erdos(tzr);
                }
        }
        return 0;
}

int mkls_parse (list_t *mkls, list_t *yzrs, char *erdos)
{
        int i;
        int j;
        int k;
        int l;
        yazar_t *erd;
        yazar_t *yzr;
        makale_t *mkl;
        
        printf("Makale;\n"
               "\tYazarlari;\n");
        for (i = 0; !list_eol(mkls, i); i++) {
                mkl = (makale_t *) list_get(mkls, i);
                printf("%s;\n", mkl->name);
                for (j = 0; !list_eol(mkl->yazar, j); j++) {
                        printf("\t%s\n", (char *) list_get(mkl->yazar, j));
                        for (k = 0; !list_eol(yzrs, k); k++) {
                                yzr = (yazar_t *) list_get(yzrs, k);
                                if (strcmp(yzr->name, (char *) list_get(mkl->yazar, j)) == 0) {
                                        goto found_yazar;
                                }
                        }
                        yzr = (yazar_t *) malloc(sizeof(yazar_t));
                        if (yzr == NULL) {
                                printf("(%d) malloc failed\n", __LINE__);
                        }
                        yzr->name = strdup((char *) list_get(mkl->yazar, j));
                        yzr->erdos = -1;
                        list_init(&(yzr->kanka));
                        list_init(&(yzr->makal));
                        list_add(yzrs, yzr, -1);
found_yazar:            list_add(yzr->makal, mkl, -1);
                }
        }
        
        for (i = 0; !list_eol(yzrs, i); i++) {
                yzr = (yazar_t *) list_get(yzrs, i);
                for (j = 0; !list_eol(yzr->makal, j); j++) {
                        mkl = (makale_t *) list_get(yzr->makal, j);
                        for (k = 0; !list_eol(mkl->yazar, k); k++) {
                                for (l = 0; !list_eol(yzr->kanka, l); l++) {
                                        if (strcmp((char *) list_get(mkl->yazar, k), (char *) ((yazar_t *) list_get(yzr->kanka, l))->name) == 0) {
                                                goto found_kanka;
                                        }
                                }
                                for (l = 0; !list_eol(yzrs, l); l++) {
                                        if (strcmp((char *) ((yazar_t *) list_get(yzrs, l))->name, (char *) list_get(mkl->yazar, k)) == 0) {
                                                if (yzr != list_get(yzrs, l)) {
                                                        list_add(yzr->kanka, list_get(yzrs, l), -1);
                                                }
                                        }
                                }
found_kanka:                    ;
                        }
                }
        }
        
        erd = list_get(yzrs, 0);
        for (i = 0; !list_eol(yzrs, i); i++) {
                if (strcmp(erdos, (char *) ((yazar_t *) list_get(yzrs, i))->name) == 0) {
                        erd = list_get(yzrs, i);
                }
        }
        erd->erdos = 0;
        calculate_erdos(erd);
        
        printf("\n");
        printf("Yazarlar;\n");
        for (i = 0; !list_eol(yzrs, i); i++) {
                yzr = (yazar_t *) list_get(yzrs, i);
                printf("%s\n"
                       "\terdos: %d\n"
                       "\tmakales;\n", yzr->name, yzr->erdos);
                for (j = 0; !list_eol(yzr->makal, j); j++) {
                        mkl = (makale_t *) list_get(yzr->makal, j);
                        printf("\t\t%s\n", mkl->name);
                }
                printf("\tkankas;\n");
                for (j = 0; !list_eol(yzr->kanka, j); j++) {
                        printf("\t\t%s\n", (char *) ((yazar_t *) list_get(yzr->kanka, j))->name);
                }
        }
        
        printf("\nYazar erdoslari;\n");
        for (i = 0; !list_eol(yzrs, i); i++) {
                yzr = (yazar_t *) list_get(yzrs, i);
                printf("%s\t%d\n", yzr->name, yzr->erdos);
        }
        
        return 0;
}

int main (int argc, char *argv[])
{
        int i;
        int c;
        FILE *fp;
        char *buf;
        list_t *mkls;
        list_t *yzrs;
        char *erdos = NULL;
        char *input = NULL;
        struct stat sbuf;
        
        if (argc < 5) {
usage:          printf("usage:\n"
                       "\t%s -i input.txt -e erdos\n", argv[0]);
                return -1;
        }
        
        while ((c = getopt(argc, argv, "i:e:h?")) != -1) {
                switch (c) {
                        case 'e':
                                erdos = strdup(optarg);
                                break;
                        case 'i':
                                input = strdup(optarg);
                                break;
                        case 'h':
                        case '?':
                                goto usage;
                }
        }
        
        if (stat(input, &sbuf)) {
                printf("(%d) stat failed\n", __LINE__);
                goto err0;
        }
        
        buf = (char *) malloc(sizeof(char) * (sbuf.st_size + 1));
        if (buf == NULL) {
                printf("(%d) malloc failed\n", __LINE__);
                goto err1;
        }
        
        fp = fopen(input, "r");
        if (fp == NULL) {
                printf("(%d) fopen failed\n", __LINE__);
                goto err2;
        }
        
        i = fread(buf, sizeof(char), sbuf.st_size, fp);
        if (i != sbuf.st_size) {
                printf("(%d) fread failed\n", __LINE__);
                goto err3;
        }
        buf[i] = '\0';
        
        if (list_init(&mkls)) {
                printf("(%d) list_init failed\n", __LINE__);
                goto err4;
        }

        if (list_init(&yzrs)) {
                printf("(%d) list_init failed\n", __LINE__);
                goto err5;
        }
        
        buf_parse(buf, mkls);
        mkls_parse(mkls, yzrs, erdos);
        
        list_uninit(mkls);
        list_uninit(yzrs);
        fclose(fp);
        free(buf);
        
        return 0;
err5:   list_uninit(mkls);
err4:
err3:   fclose(fp);
err2:   free(buf);
err1:
err0:   return -1;
}


EOF

echo inflating main.h
cat > main.h << EOF


typedef struct list_node_s {
        void *next;
        void *element;
} list_node_t;

typedef struct list_s {
        int nb_elt;
        list_node_t *node;
} list_t;

int list_init (list_t **li);
int list_uninit (list_t *li);
int list_eol (list_t *li, int i);
void * list_get (list_t *li, int pos);
int list_add (list_t *li, void *el, int pos);


EOF

echo "usage;"
echo "gcc -o main main.c list.c"
echo "./main -i input.txt -e erdos"
echo "alper akcan -=[ anhanguera ]=-"


(CL) alper akcan
http://www.valgrind.org   hacker emblem   Valid HTML 4.01!   Viewable With Any Browser   [Valid Rss]   Open Source