偏序集可折叠子集CollapsibleSubset的Python现有实现查询

我正在寻找偏序全集的一类特殊子集的Python实现，这类子集我称之为CollapsibleSubset，其可包含的全集元素有特殊限制，需要同时满足1）“可折叠性（Collapsibility）”和2）“无可比元素（Absence of comparable elements）”两个要求，且CollapsibleSubset之间的运算定义也与普通集合不同，我将结合文件系统路径的示例说明其正式定义。

示例 - 文件系统路径集合 #

考虑如下文件系统树：

/root/
├── dir1/
│   ├── file11.txt
│   └── file12.txt
├── dir2/
│   ├── file21.txt
│   └── file22.txt
└── file0.txt

本例中的全集是所有合法路径的集合 { /root, /root/dir1, /root/dir1/file11.txt …… /root/file0.txt}。偏序关系lt由目录结构定义，即lt(a,b)表示b是a的祖先目录，例如lt(/root/dir1, /root)返回True。

使用CollapsibleSubset的核心目的是用尽可能少的元素最简表示一组路径，例如CollapsibleSubset({/root/dir1, /root/dir2})可以表示dir1、dir2下的所有文件和目录。

定义 #

偏序集U的CollapibleSubset A是取自U的元素集合，满足以下两个要求：

1. 可折叠性
   &space;%5Cimplies&space;%5Cexists&space;z&space;%5Cnotin&space;A&space;:dp(z,x))
   其中dp是直接前驱关系：&space;%5Cwedge&space;!&space;%5Cexists&space;z:&space;(a&space;%5Cprec&space;z&space;%5Cwedge&space;z&space;%5Cprec&space;b)
   换而言之，若某元素的所有前驱都属于该子集，则该元素本身也必须属于该子集。
   示例： {root/dir1/file11.txt, /root/dir1/file12.txt}不是合法的CollapibleSubset，而{/root/dir1}是合法实例。
2. 无可比元素
   
   换而言之，若某元素属于该子集，则其所有前驱都不能属于该子集。
   示例： {/root/dir1, /root/dir1/file12.txt}不是合法的CollapibleSubset，而{/root/dir1}是合法实例。

以上两个要求可以保证子集包含的元素数量尽可能少。

运算规则 #

并集

A、B均为CollapsibleSubset，若C是合法CollapsibleSubset且满足如下条件则C=Union(A,B)：

示例：

CollapsibleSubset({'/root/dir1', '/root/dir2/file21.txt'}).union(
    CollapsibleSubset({'/root/dir2/file22.txt', '/root/file0.txt'}
) = CollapsibleSubset({'/root'})

补集

A为CollapsibleSubset，若B是合法CollapsibleSubset且满足如下条件则B=Complement(A)：

示例：

CollapsibleSubset({'/root/dir2/file21.txt'}).complement()=
CollapsibleSubset({'/root/dir1', '/root/dir2/file22.txt', '/root/file0.txt'}))

CollapsibleSubset可选创建API #

实际场景中可以通过上确界和返回直接前驱的函数来定义偏序关系，以路径集合为例：

>>> colsub = CollapsibleSubset(sup='/root', pred_func=lambda p: os.listdir(p), elements={'/root/dir1', '/root/file0'})

其他使用场景：任意层级结构子集 #

文件系统示例不是我需要CollapsibleSubset类的唯一场景，另一个适用场景是快速定义任意层级结构的子集。
示例： 现有如下层级结构：

Commit
             /     |    \
           /      Fix     \
         /       /   \      \
  Feature   CodeFix  DocFix  Refactoring
   /          /        \           \
 ....       ....       ....        ...

用字典定义为：

>>> hierarchy = {'Commit': ['Feature', 'Fix', 'Refactoring'], 'Fix': ['CodeFix', 'DocFix'], ...}

我需要用最简方式定义该结构的子集，例如要定义所有属于修复类或重构类的提交类型，用CollapsibleSubset可以写为：

>>> CollapsibleSubset('Commit', lambda p: hierarchy[p], {'Fix', 'Refatoring'})

最终问询 #

请问是否有现有Python库已经实现了上述CollapsibleSubset抽象能力？

内容的提问来源于stack exchange，提问作者Hlib Babii