fca-algorithms-cpp

FCA algorithms C++ Implementation

This projects is the version of the fca_algorithms PyPi module implemented in C++.

Purpose

The goal of this project is to eventually replace totally the implementation of the Python library with backend C++, and just leave the Python interface.

So far, the only ported algorithm is inclose.

Performance

Unsurprisingly, this implementation runs much faster than the one done totally in python. In the following, we can see an example of the difference in runtimes using get_concepts method from the Context class of both fca_algorithms<=0.2.x and fca_algorithms_cpp.

After running these tests, I decided to use this library in the Python one so that at least the code can take advantage of the faster implementation of inclose.

Future Work

As said before, the ideal would be to fully implement the CPU-intensive algorithms in C++ and maintain the Python interface. Considering this, the goal would be to eventually replace the python code with full C++ one.

Usage

There are one function and two classes that are exported to Python

from fca_algorithms_cpp import ContextCpp, ConceptCpp, inclose


# inclose: (List[str] -> List[str] -> List[List[int]]) -> List[ConceptCpp]
inclose(['g1', 'g2'], ['m1', 'm2', 'm3'], [[1, 1, 0], [0, 1, 0]])

# ContextCpp: (List[str] -> List[str] -> List[List[int]]) -> List[ConctextCpp]
c = ContextCpp(['g1', 'g2'], ['m1', 'm2', 'm3'], [[1, 1, 0], [0, 1, 0]])
c.G  # ['g1', 'g2']
c.M  # ['m1', 'm2', 'm3']
C.I  # [[1, 1, 0], [0, 1, 0]]

# ConceptCpp: (ContextCpp, List[int], List[int]) -> ConceptCpp
concept = ConceptCpp(c, [0, 1], [1, 2])  # ({g1, g2}, {m2, m3})
concept.X  # [0, 1]
concept.Y  # [1, 2]

Incremental Lattice

By intent

This implementation follows the article: AddIntent

k = ContextCpp([], ['a', 'b'], [])
L = LatticeCpp(k)  # Lattice: { ({ }, { a, b })}
L.add_intent('o1', [1])
# Lattice: { ({ }, { a, b }), ({ o1 }, { b })}
L.add_intent('o2', [1])
# Lattice: { ({ }, { a, b }), ({ o1, o2 }, { b })}
L.add_intent('o3', [0])
# Lattice: { ({ }, { a, b }), ({ o1, o2 }, { b }), ({ o1, o2, o3 }, { }), ({ o3 }, { a })}

By pair

k = ContextCpp([], [], [])
L = LatticeCpp(k)  # Lattice: {  }
L.add_pair('o1', 'a2')
# Lattice: Lattice: { ({ o1 }, { a2 })}
L.add_pair('o2', 'a3')
# Lattice: { ({ o1 }, { a2 }), ({ }, { a2, a3 }), ({ o1, o2 }, { }), ({ o2 }, { a3 })}
L.add_pair('o3', 'a1')
# Lattice: { ({ o1 }, { a2 }), ({ }, { a2, a3, a1 }), ({ o1, o2, o3 }, { }), ({ o2 }, { a3 }), ({ o3 }, { a1 })}
L.add_pair('o3', 'a2')
# Lattice: { ({ o1, o3 }, { a2 }), ({ }, { a2, a3, a1 }), ({ o1, o2, o3 }, { }), ({ o2 }, { a3 }), ({ o3 }, { a1, a2 })}

Delete instance

This implementation follows the article: DeleteInstance

k = ContextCpp(['o1', 'o2', 'o3'], ['a1', 'a2', 'a3'], [[0, 1, 0], [0, 0 , 1], [1, 1, 0]])
L = LatticeCpp(k)
# Lattice: { ({ }, { a1, a2, a3 }), ({ o1, o3 }, { a2 }), ({ o1, o2, o3 }, { }), ({ o2 }, { a3 }), ({ o3 }, { a1, a2 })}
L.delete_instance('o3')
# Lattice: { ({ }, { a1, a2, a3 }), ({ o1 }, { a2 }), ({ o1, o2 }, { }), ({ o2 }, { a3 })}