Consider a system with a finite number of users and a finite number of groups.
To each group it corresponds a set of users. (We say that users "directly belong" to a group.)
Groups of users form a directed graph without cycles. If A→B for groups A and B, then I say that B is a direct subgroup of A.
The following operations are defined:
- add a user to a group
- remove a user from a group
- add a direct subgroup to a group
- remove a direct subgroup from a group
Note that attempt to make a cycle in the directed graph should throw an exception.
Also new users and groups may be created and existing users and groups may be deleted.
I need to efficiently cache this information, so that checking whether a user (directly or indirectly) belongs to a group (or any of its direct or indirect subgroups) should be a fast operation. Caching is done by a caching engine like memcached.
Please refer me to an efficient caching algorithm. I think I am not the first person to solve this problem and there is a known algorithm.
Note that we write in Python programming language.