Алгоритм Кана и достижимость

Question

В целях обучения я разрабатываю приложение, которое в реальной жизни будет работать в основном как Quartz Composer или недавний Vuo. Я строю график узлов на основе Core Data Framework.

По сути, у меня есть сущность Node с отношением ко-многим с сущностями Input и Output (узел может иметь несколько входов и несколько выходов). Вход имеет отношение "один к одному" с объектом " Соединение", в то время как " Выход" имеет отношение ко многим с последним (вход может иметь только одно подключение, а выход может иметь много).

Для чтения графика я использую алгоритм топологической сортировки (Канна), описанный здесь. Код выглядит следующим образом:

/**
 * Get all nodes.
 */
NSFetchRequest *request = [NSFetchRequest fetchRequestWithEntityName:@"Node"];
NSMutableArray *nodes = [[[_document managedObjectContext] executeFetchRequest:request error:nil] mutableCopy];
/**
 * Reset the nodes 'visited' flag.
 */
[self reset:nodes];
/**
 * Get sources: predicate for nodes without input ports or with input ports without connections.
 */
[request setPredicate:[NSPredicate predicateWithFormat:@"inputs == nil OR ALL inputs.connection == nil"]];
NSMutableArray *sources = [[[_document managedObjectContext] executeFetchRequest:request error:nil] mutableCopy];
/**
 * Perform a topological sort.
 */
while ([sources count] > 0) {
    /**
     * While there are sources.
     */
    NSManagedObject *node = [sources lastObject];
    /**
     * Add the node to the tail of the final graph (NSMutableArray).
     */
    [_graph addObject:node];
    [node setValue:@([_graph count] - 1) forKey:@"kNodeExecutionIndex"];
    [sources removeLastObject];
    /**
     * Outputs.
     */
    NSMutableSet *outputs = [node valueForKey:@"outputs"];
    for (NSManagedObject *output in outputs) {
        /**
         * Get output connections.
         */
        NSMutableSet *connections = [output valueForKey:@"connections"];
        for (NSManagedObject *connection in connections) {
            /**
             * Set the connection as already visited.
             */
            [connection setValue:@(YES) forKey:@"kConnectionVisited"];
            NSManagedObject *n = [[connection valueForKey:@"destination"] valueForKey:@"node"];
            /**
             * Set the 'source' flag to YES by default.
             */
            BOOL isNewSource = YES;
            /**
             * Get connected inputs.
             */
            NSMutableSet *inputs = [n valueForKey:@"inputs"];
            for (NSManagedObject *input in inputs) {
                /**
                 * Check if one of the input connections was visited.
                 * If not, then we need to process this connection and
                 * don't add it to sources for next pass.
                 */
                if ([[[input valueForKey:@"connection"] valueForKey:@"kConnectionVisited"] isEqualTo:@(NO)]) {
                    isNewSource = NO;
                    break;
                }
            }

            if (isNewSource) {
                [sources addObject:n];
            }
        }
    }
}

Я пытаюсь понять логику того, как (и где в этом коде) я должен был бы вычислить достижимость для каждого объекта Node (следовательно, для каждого Input), если это возможно.

Мои вопросы:

• Можно ли рассчитать достижимость узлов внутри алгоритма Кана?
• Если уместно, где и как это сделать, чтобы я мог понять, почему это работает?

Спасибо.

Answer 1

Беглый взгляд на ваш код, я предлагаю сначала создать подкласс NSManagedObjects, который вы создаете (узел и т. Д.), Чтобы вы могли написать простой код для доступа к созданным вами отношениям. Это сделает код более понятным.

В общем, я не уверен, что понимаю вопрос. Вы можете следить за отношениями, чтобы проверить достижимость любого управляемого объекта / узла. Это действительно не имеет ничего общего с основными данными, хотя.