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 │
 └───┘     └───┘

许可证

(BSD-2许可证)

原始作品版权所有 © 2012, Frank Meyer

版权所有。

Swift版本版权所有 © 2018, Hèctor Marquès

以下条件满足的前提下，允许重新分发和使用源代码和二进制形式，无论是修改还是有修改

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

本软件由版权所有者和贡献者按“原样”提供，并且对任何明示或暗示的保证，包括但不限于适销性和针对特定目的的使用保证，均不予承认。在任何情况下，版权所有者或贡献者都不应对因使用本软件而产生的任何直接、间接、偶然、特殊、示范性或后果性损害（包括但不限于替代商品或服务的获取；使用、数据或利润的损失；或业务中断）承担责任，即使被告知本软件可能造成此类损害，也不承担责任。