用属性实现“类别”系统

Question

我有大约1000‘类别’，包括我的边缘。我使用属性对这些类别进行了专门化：

g.es[0]["$cat1"]=True

一个边缘可以属于多个类别。

问题是，这会导致我的所有其他边缘，即使它们与类别1无关，以获得属性$cat1=None。

因此，基本上，即使我的edge是单个类别的一部分，它也将具有999个其他属性，如$catN=None。

我需要将每个类别(包括它的所有成员节点和边)提取到一个单独的子图中的能力。现在，我只需遍历所有的边缘，查看$catN = True的位置，并将这些边和节点放到一个新的图中。

1. 这个方法作为一个整体看起来可伸缩吗？这似乎有点混乱，因为可能有一百万个节点和一万种类别。这意味着每个边缘将存储2-3 $catN = True，但存储数千个冗余$catN = None。
2. 如果没有，你有什么建议来更好地实施这个“类别”系统吗？
3. 如果这是最好的做法，有什么建议来检索一个特定的类别吗？穿越所有的边缘似乎是一种浪费。我想我可以维护一个单独的数据结构，与每个类别对应的边编号。不过，维持下去是件痛苦的事。

Answer 1

是否需要将每个边缘的类别存储为边缘属性？如果您的图不会发生变异(也就是说，您不会从图中删除边缘)，您可以简单地使用外部Python dict将类别ID映射到边缘IDs -然后您可以使用单个字典查找来获取每个类别的成员。如果您还需要快速判断边缘属于哪个类别，则还需要反向映射，所以最好创建一个单独的“双向映射”类，并分别维护映射的两边：

from collections import defaultdict

class CategoryMapping(object):
    def __init__(self):
        self.category_to_members = defaultdict(set)
        self.member_to_categories = defaultdict(set)

    def add(self, category, member):
        self.category_to_members[category].add(member)
        self.member_to_categories[member].add(category)

    def remove(self, category, member):
        self.category_to_members[category].discard(member)
        self.member_to_categories[member].discard(category)

    def categories_of(self, member):
        return self.member_to_categories[member]

    def members_of(self, category):
        return self.category_to_member[category]

编辑：如果有时从图形中删除边缘，则可以为其id edge属性中的每个边缘分配一个唯一ID，然后在CategoryMapping中使用这些ID。唯一的问题是，由属性进行的边查找是一个O(n)操作，其中n是边的数目。为了缓解这种情况，您还可以创建一个从ID到索引的边缘映射类。这个类可以有一个edges_removed()方法，每当您从图中删除边缘时，必须用删除的边的旧ID调用该方法，并且它应该相应地更新内部ID到索引映射。(遗憾的是，iGraph对于边缘没有一个特殊的id类属性，尽管它以这种方式处理顶点对象的name属性，这样就可以通过名称实现对顶点的O(1)查找)。你可以利用这样一个事实，边i的索引在移除后会变成i当且仅当有k个被移除的边，其索引比原始图中的我小。