objective-c - 卡恩算法和可达性

Question

出于学习目的，我正在开发一个在现实生活中基本上可以像Quartz Composer 一样工作的应用程序或最近的 Vuo .我在核心数据框架的基础上构建节点图。

基本上我有一个 Node 实体，它与 Input 和 Output 实体有一对多的关系(一个节点可以有多个输入和多个输出)。 Input 与 Connection 实体具有一对一关系，而 Output 与后者具有一对多关系(输入只能有一个连接，而一个输出可以有多个)。

为了阅读图表，我使用拓扑排序算法(Kahn 的算法)，描述了 here .代码如下:

/**
 * 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];
            }
        }
    }
}

我试图理解我必须如何(以及在​​此代码中的何处)计算每个节点(因此每个输入)实体的可达性的逻辑，如果可能的话。

我的问题是:

• 是否可以计算 Kahn 算法中节点的可达性？
• 如果合适，在哪里以及如何做，这样我就能理解它为什么有效？

谢谢。

Answer 1

快速浏览一下您的代码，我建议首先创建您创建的 NSManagedObjects(节点等)的子类，以便您可以编写简单的代码来访问您创建的关系。这将使代码更易于维护。

一般来说，我不确定我是否理解了这个问题。您可以按照这些关系来测试任何托管对象/节点的可达性。不过，这实际上与核心数据无关。