ElementaryCycles

Swift版本的用于在有向图中找到所有循环的算法

这是Donald B. Johnson算法在有向图中找到所有基本循环的实现 (Donald B. Johnson: Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing. Volume 4, Number 1 (1975), pp. 77-84).

原始Java实现: http://normalisiert.de

使用方法

ElementaryCycles

import ElementaryCycles

// dictionary pairs represent node connections from the keys to their values
let graph = ["A": ["B", "C"], "B": ["A"], "C": ["D"], "D": ["C"]]

let cycles = ElementaryCycles.find(graph: graph, sort: { $0 < $1 })

// nodes order is determined by sort parameter 
print(cycles) // [["A", "B"], ["C", "D"]]

• 输入: 有向图

                ┌─────────┐
                ∨         │
    ┌───┐     ┌───┐     ┌───┐
 ┌> │ A │ ──> │ C │ ──> │ D │
 │  └───┘     └───┘     └───┘
 │    │
 │    │
 │    ∨
 │  ┌───┐
 └─ │ B │
    └───┘

• 输出: 基本回路

 ┌───┐     ┌───┐
 │ A │ ──> │ B │
 └───┘     └───┘
 ┌───┐     ┌───┐
 │ C │ ──> │ D │
 └───┘     └───┘

ElementaryCyclesSearch

您还可以直接使用ElementaryCyclesSearch库，它包含实际的算法实现

实现相当通用，它只需要您的图的邻接矩阵和节点的对象。然后您将得到形成循环的节点对象的集合。

原始Java实现: http://normalisiert.de

import ElementaryCyclesSearch

let nodes = Vector(["A", "B", "C", "D"])
let matrix = AdjacencyMatrix(4, 4) { matrix in
    matrix[0][1] = true
    matrix[0][2] = true
    matrix[1][0] = true
    matrix[2][3] = true
    matrix[3][2] = true
}
let cycles = getElementaryCycles(adjacencyMatrix: matrix, graphNodes: nodes)

• 输入: 节点对象

• 输入: 邻接矩阵

• 输出: 基本回路

 ┌───┐     ┌───┐
 │ A │ ──> │ B │
 └───┘     └───┘
 ┌───┐     ┌───┐
 │ C │ ──> │ D │
 └───┘     └───┘

许可

(BSD-2许可证)

原始作品版权所有(c) 2012，Frank Meyer

版权所有。

Swift端口版权所有(c) 2018，Hèctor Marquès

在不修改的情况下重新分发源代码和二进制形式，只要符合以下条件

源代码的分发必须保留上述版权声明、本许可条款和以下免责声明。二进制形式的分发必须重复上述版权声明、本许可条款和以下免责声明在提供的文档或其它材料中。

本软件由版权所有者和贡献者提供“按现状”并且明示或默示的任何保证（包括但不限于适销性和特定用途适用性）均被排除；在不对任何直接、间接、偶然、特殊、示范性或后果性损害（包括但不限于替代商品或服务的采购；使用的丧失；数据的丧失或利润的丧失；业务的中断）承担责任，无论何种原因说成是导致的，也不论是根据合同、侵权法或其他法律理论来追究责任，即使被告知了软件可能造成此类损害。