Найти простые циклы с рекурсией в ориентированном графе.С - PullRequest
Новая
       47

Найти простые циклы с рекурсией в ориентированном графе.С

0 голосов
/ 21 октября 2018

У меня есть ориентированный граф, и я пытаюсь найти в нем все простые круги узла графа.Мой график выглядит примерно так: directed graph

Каждый g_node, представляющий имя пользователя, имеет список t_nodes, который представляет транзакции для других имен пользователей.Каждый узел транзакции указывает на имя пользователя, с которым он совершает транзакцию, а также на саму транзакцию.Например, A имеет транзакцию с B a1-> b2 с весом 500. Поскольку A фактически дает деньги B, это направление также должно быть представлено.Когда имя пользователя дает деньги, направление равно 0, а когда оно получает деньги, направление равно 1. Если имя пользователя имеет транзакцию с самим собой, направление равно 2.

Вот мой код: 

void find_simple_circles(struct t *t_temp)
{
    int circles_t;
    struct s *s_temp;

    circles_t = 0;

    while (t_temp != NULL)      //Check all transaction nodes of current g_node.
    {
                                //If a transaction node has direction 0 or 2 and it is not yet visited "t_temp->to_user->state == WHITE".
        if ((t_temp->direction == 0 || t_temp->direction == 2) && (t_temp->to_user->state == WHITE))
        {
            weight_input(t_temp);   //Insert its weight to the stack.
            if (strcmp(s_head->username, t_temp->to_user->username) == 0)
            {                       //If a transaction node, transacts with the username (graph node) I am looking for, print whole stack.
                circles_t++;        
                circles++;         
                print_assist(s_head);
            }
            else                                                //If it transacts with someone else,
            {   
                t_temp->to_user->state = GRAY;                  //that someone else becomes proccessed and cannot be visited for the time being "GRAY".
                s_temp = new_s_node(t_temp->to_user);           //Create a new stack member with the above username.
                add_s_to_list(s_temp, t_temp);                  //Add it to the stack list.
                find_simple_circles(t_temp->to_user->gt_node);  //Recursively call find_simple_circles(), with the transactions list of that username.
                remove_last(s_head);                            //When recurse returns, remove the last member of the stack list.
                t_temp->to_user->state = WHITE;                 //And set the username to "WHITE"(can be visited again).
            }
        }
        if((circles_t == 0) && (t_temp->t_next == NULL))        //If no circles where found while proccessing a username
            t_temp->to_user_t->to_user->state = BLACK;          //Set it to "BLACK"(cannot be visited).
        t_temp = t_temp->t_next;                                //Step through all transactions of a username.
    }
    return;
}

Мой график имеет около 13000 имен пользователей с 7 * 13000 транзакций.И моя рекурсия по какой-то причине зависает и не печатает ни одного цикла, или печатает циклы навсегда.Для меньшего графика все работает нормально.Я не могу найти способ, чтобы представить проблему только с 3 или 4 именами пользователей.Можете ли вы обнаружить что-то принципиально неправильное в моем коде?

Заранее спасибо.

...