区分同名节点的正确图数据结构是什么？

Question

我正在学习图（感觉它们超级有用），想请教一下如何结构化我的图的一些建议。

简单来说，假设我每天都会收到采购订单，有些天的订单和前一天一样，有些天则不同。比如说，昨天我收到了一份铅笔和橡皮的订单，我就创建了两个节点来表示它们。然后今天我又收到了一份橡皮和马克笔的订单，依此类推。每天结束后，我的程序还会查看是谁买了什么，如果Bob昨天买了铅笔，今天又买了橡皮，我就会创建一条有向边。这样做的逻辑是，我可以看到每一天谁买了什么，还可以追踪Bob的购买行为（也许还能用来推测他或其他用户的购买模式）。

我遇到的问题是，我在使用networkx（python）时，昨天创建的'铅笔'节点和今天创建的'铅笔'节点是一样的，我无法区分它们。

我曾考虑过（并且一直在这样做）把它命名为day2-pencil，然后扫描整个图，把'day2-'去掉来追踪铅笔的订单。但我觉得这样不太对（更别提对处理器的负担了）。我认为关键在于能否将每一天标记为一个子图，这样当我想研究某一天或几天时，就不需要扫描整个图了。

随着我的测试数据越来越大，情况变得越来越混乱，所以我在想最佳实践是什么？任何通用的建议都很好（因为networkx功能很全，可能有解决办法）。

提前谢谢你们！

更新：仍然没有找到解决办法，但这可能有帮助：

import networkx as nx
G=nx.Graph()
G.add_node('pencil', day='1/1/12', colour='blue')
G.add_node('eraser', day='1/1/12', colour='rubberish colour. I know thats not a real colour')
G.add_node('pencil', day='1/2/12', colour='blue')

我输入以下命令 G.node 得到的结果是：

{'pencil': {'colour': 'blue', 'day': '1/2/12'}, 'eraser': {'colour': 'rubberish colour. I know thats not a real colour', 'day': '1/1/12'}}

显然，它把1/1/12的铅笔覆盖成了1/2/12的铅笔，不确定我是否能创建一个不同的。

Answer 1

试试这个：

给每个节点一个独特的整数ID。然后，创建一个字典，叫做nodes，内容如下：

nodes['pencil'] = [1,4,...] <- 这里面的所有数字都对应一个有“铅笔”属性的节点。你可以把“铅笔”换成你感兴趣的其他属性。

只要确保当你添加一个有“铅笔”属性的节点时，记得更新这个字典：

node['pencil'].append(new_node_id）。删除节点时也是一样。

Answer 2

用图形来处理这个问题并不是最好的办法。像MySQL这样的关系型数据库才是存储这些数据和执行查询（比如谁在什么时候买了什么）的合适工具。

Answer 3

这主要取决于你的目标。你想分析什么，决定了你图表的设计。不过，从你的结构来看，一个一般的结构可以是Customers（顾客）和Products（产品）这两个节点，它们通过Days（日期）连接起来（我不知道这对你有没有帮助，但实际上这是一个二分图）。

所以你的结构大概是这样的：

node(Person) --- edge(Day) ---> node(Product)

假设，Bob在2012年1月1日买了一支铅笔：

node(Bob) --- 1/1/12 ---> node(Pencil)

好吧，现在Bob在2012年1月2日又买了一支铅笔：

          -- 1/1/12 --
         /            \
node(Bob)              > node(Pencil)
         \            /
          -- 1/2/12 --

依此类推……

这实际上可以通过networkx来实现。因为你在节点之间有多个连接，所以你需要根据连接的方向选择MultiGraph或MultiDiGraph。

In : g = networkx.MultiDiGraph()

In : g.add_node("Bob")
In : g.add_node("Alice")

In : g.add_node("Pencil")

In : g.add_edge("Bob","Pencil",key="1/1/12")
In : g.add_edge("Bob","Pencil",key="1/2/12")

In : g.add_edge("Alice","Pencil",key="1/3/12")
In : g.add_edge("Alice","Pencil",key="1/2/12")

In : g.edges(keys=True)
Out:
[('Bob', 'Pencil', '1/2/12'),
 ('Bob', 'Pencil', '1/1/12'),
 ('Alice', 'Pencil', '1/3/12'),
 ('Alice', 'Pencil', '1/2/12')]

到目前为止，情况还不错。你实际上可以查询类似“Alice在2012年1月1日买了铅笔吗？”这样的问题。

In : g.has_edge("Alice","Pencil","1/1/12")
Out: False

In : g.has_edge("Alice","Pencil","1/2/12")
Out: True

如果你想要特定日期的所有订单，事情可能会变得复杂。这里的复杂不是指代码上的，而是计算上的。代码上其实挺简单的：

In : [(from_node, to_node) for from_node, to_node, key in g.edges(keys=True) if key=="1/2/12"]
Out: [('Bob', 'Pencil'), ('Alice', 'Pencil')]

但是这会扫描网络中的所有连接，并过滤出你想要的部分。我觉得networkx没有更好的方法。