Collapsible subset of partially ordered set

Problem

I am looking for python implementation of a special kind of subset of a partially ordered universal set. It is special because there are restrictions on which elements from the universal set this subset (which I would call CollapsibleSubset) can contain. CollapsibleSubset has to satisfy 1) "Collapsibility" and 2) "Absence of comparable elements" requirements. The operations on CollapsibleSubsets are also defined differently compared to normal sets. I will illustrate the formal definition with the example of file system paths.

Example - File system paths set

Consider a file system tree:

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

The universal set, in this case, are all valid paths { /root, /root/dir1, /root/dir1/file11.txt .. /root/file0.txt}. The partial order lt is defined by the directory structure, i.e. lt(a,b) means that b is an ancestor directory of a, e.g. lt(/root/dir1, /root) is True.

The idea of using CollapsibleSubset is to represent a set of paths in the briefest way, i.e. with a few elements as possible. E.g. CollapsibleSubset({/root/dir1, /root/dir2}) would represent all files and dirs in dir1, dir2.

Definition

CollapibleSubset A of a partially-ordered set U, is a set of elements from U that satisfies two requirements:

1. "Collapsibility".

   

   , where dp is a direct predecessor relation:

   In other words, if all predecessors of an element belong to the subset, then the element itself must belong to the subset.

   Example. {root/dir1/file11.txt, /root/dir1/file12.txt} is not a valid CollapibleSubset, but {/root/dir1} is.

2. No comparable elements

   

   In other words, if an element belongs to the subset, none of its predecessors can.

   Example. {/root/dir1, /root/dir1/file12.txt} is not a valid CollapibleSubset, but {/root/dir1} is.

Requirements 1 and 2 ensure that the subset contains as few elements as possible.

Operations

Union

A,B - CollapsibleSubsets, C=Union(A,B) if C is a valid CollapsibleSubset and:

Example.

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

Complement

A - CollapsibleSubset, B = Complement(A) if B is a valid CollapsibleSubset and:

Example.

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

Possible CollapsibleSubset creation API

Partial order in practice can be specified by supremum and a function that returns direct predecessors. For the paths set example:

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

Another use-case - arbitrary hierarchy subset

The file system example is not my only use-case for which having a CollapsibleSubset class would be useful. Another one is defining a subset of an arbitrary hierarchy in the fastest way.

Example. Having the following hierarchy:

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

defined as a dictionary:

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

I would like to define a subset of it in the briefest way. For example, a way to define all types of commits that are different kinds of fixes or refactorings with CollapsibleSubset would be:

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

Question

Is such CollapsibleSubset abstraction already implemented in any library?

from Collapsible subset of partially ordered set