ElementaryCycles

用于查找有向图中所有环路的算法的 Swift 移植

这是 Donald B. Johnson 算法的一个实现，用于查找有向图中的所有基本环路（Donald B. Johnson: Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing. Volumne 4, Nr. 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

输入: 邻接矩阵

	A	B	C	D
A	`false`	`true`	`false`	`false`
B	`true`	`false`	`false`	`false`
C	`true`	`false`	`false`	`true`
D	`false`	`false`	`true`	`false`

输出: 基本回路

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

许可证

(BSD-2 许可证)

原始工作版权 (c) 2012, Frank Meyer

保留所有权利。

Swift 移植版权 (c) 2018, Hèctor Marquès

如果满足以下条件，则允许以源和二进制形式重新发布和使用，无论是否经过修改：

源代码的重新分发必须保留上述版权声明、此条件列表和以下免责声明。二进制形式的重新分发必须在随发行版提供的文档和/或其他材料中复制上述版权声明、此条件列表和以下免责声明。

本软件由版权所有者和贡献者“按原样”提供，并且不承担任何明示或暗示的保证，包括但不限于对适销性和特定用途适用性的暗示保证。在任何情况下，版权所有者或贡献者均不对任何直接、间接、偶然、特殊、惩戒性或后果性损害（包括但不限于采购替代商品或服务；使用、数据或利润损失；或业务中断）负责，无论因何种原因导致以及基于任何责任理论，无论是合同、严格责任还是侵权行为（包括疏忽或其他原因）因使用本软件而以任何方式引起，即使已被告知存在此类损害的可能性。