如何将带权有向知识图谱表示为唯一确定性序列？

我正在使用NetworkX处理带权有向的知识图谱（KG），需要将这类图谱表示为唯一且确定的序列（列表），且需保留边的权重与方向。当前处理的图谱较为简单（2-5个节点，每个节点通常有1条边，最多2条），可通过以下代码复现示例：

import networkx as nx

sample_graphs = [{'directed': True,
  'multigraph': False,
  'graph': {},
  'nodes': [{'type': 'INTERNAL',
    'name_': 'Q211930',
    'id': 0,
    'label': 'Marxism–Leninism'},
   {'type': 'ANSWER_CANDIDATE_ENTITY',
    'name_': 'Q7264',
    'id': 1,
    'label': 'Marxism'},
   {'type': 'QUESTIONS_ENTITY',
    'name_': 'Q1120576',
    'id': 2,
    'label': 'Communist Party of Britain'}],
  'links': [{'name_': 'P279',
    'source': 0,
    'target': 1,
    'label': 'subclass of'},
   {'name_': 'P1142',
    'source': 2,
    'target': 0,
    'label': 'political ideology'}]},
 {'directed': True,
  'multigraph': False,
  'graph': {},
  'nodes': [{'type': 'ANSWER_CANDIDATE_ENTITY',
    'name_': 'Q5968650',
    'id': 0,
    'label': 'labourism'},
   {'type': 'QUESTIONS_ENTITY',
    'name_': 'Q1120576',
    'id': 1,
    'label': 'Communist Party of Britain'}],
  'links': [{'name_': 'P1142',
    'source': 1,
    'target': 0,
    'label': 'political ideology'}]}]

graph_objs = [nx.readwrite.json_graph.node_link_graph(graph) for graph in sample_graphs]

请问是否存在方法，可将带权有向图表示为唯一且确定的序列？即对同一图多次执行算法，输出的序列始终一致。我了解Prufer序列，但它仅适用于树结构，无法保留边的权重与方向，或许存在能对任意图进行确定性遍历的算法，恳请提供相关思路或帮助。

针对你处理的小规模带权有向图，以下几种确定性序列化方法完全适用，且能保留所有关键信息：

1. 基于有序节点+有序边的结构化序列 #

核心思路是通过固定排序规则让节点和边的顺序完全确定，避免遍历随机性：

• 节点排序：选择节点的全局唯一标识（比如name_字段，示例中是Q开头的唯一ID）作为排序键，按字典序升序排列所有节点，提取固定顺序的节点属性（如id、name_、label、type）组成节点子序列。
• 边排序：以边的源节点唯一标识、目标节点唯一标识、边的唯一标识（如name_）为排序键，对所有边升序排列，提取包含方向（源在前、目标在后）、边属性的边子序列。
• 最终序列可将节点子序列与边子序列拼接，或按"节点+其出边"的结构组合。

示例代码：

def graph_to_deterministic_sequence(G):
    # 按节点name_升序排序，提取固定字段组成节点序列
    sorted_nodes = sorted(G.nodes(data=True), key=lambda x: x[1]['name_'])
    node_seq = [(node_data['id'], node_data['name_'], node_data['label'], node_data['type']) 
                for _, node_data in sorted_nodes]
    
    # 按源节点name_、目标节点name_、边name_升序排序，提取边信息
    def edge_sort_key(edge):
        u, v, edge_data = edge
        u_name = G.nodes[u]['name_']
        v_name = G.nodes[v]['name_']
        return (u_name, v_name, edge_data['name_'])
    
    sorted_edges = sorted(G.edges(data=True), key=edge_sort_key)
    edge_seq = [(G.nodes[u]['name_'], edge_data['name_'], G.nodes[v]['name_'], edge_data['label']) 
                for u, v, edge_data in sorted_edges]
    
    # 组合节点序列与边序列，得到最终确定性序列
    return node_seq + edge_seq

# 测试示例图谱
for idx, graph in enumerate(graph_objs):
    print(f"图谱{idx+1}的序列化结果：")
    print(graph_to_deterministic_sequence(graph))

2. 固定规则的确定性遍历序列 #

如果需要更贴近图结构的遍历序列，可以用DFS或BFS，但必须严格指定起始节点和遍历顺序规则：

• 固定起始节点：选择图中type为QUESTIONS_ENTITY的节点（示例中的问题实体），或name_字典序最小的节点作为起始点。
• 固定遍历顺序：每次访问节点时，对其出边的目标节点按name_字典序升序排序，确保每次遍历的节点顺序一致。
• 记录信息：遍历过程中依次记录节点属性、边的方向与属性，生成线性序列。

示例代码（DFS版本）：

def deterministic_dfs_sequence(G):
    # 选择name_字典序最小的节点作为起始点
    start_node = min(G.nodes, key=lambda x: G.nodes[x]['name_'])
    visited = set()
    sequence = []
    
    def dfs(node):
        if node in visited:
            return
        # 记录当前节点信息
        node_data = G.nodes[node]
        sequence.append(('node', node_data['id'], node_data['name_'], node_data['label'], node_data['type']))
        visited.add(node)
        # 按目标节点name_升序排序出边
        out_edges = sorted(G.out_edges(node, data=True), key=lambda x: G.nodes[x[1]]['name_'])
        for u, v, edge_data in out_edges:
            # 记录边信息（源、边属性、目标）
            sequence.append(('edge', G.nodes[u]['name_'], edge_data['name_'], G.nodes[v]['name_'], edge_data['label']))
            dfs(v)
    
    dfs(start_node)
    # 处理未被遍历到的孤立节点（如果有）
    for node in sorted(G.nodes, key=lambda x: G.nodes[x]['name_']):
        if node not in visited:
            node_data = G.nodes[node]
            sequence.append(('node', node_data['id'], node_data['name_'], node_data['label'], node_data['type']))
    return sequence

# 测试
for idx, graph in enumerate(graph_objs):
    print(f"图谱{idx+1}的DFS序列化结果：")
    print(deterministic_dfs_sequence(graph))

3. 哈希式元组序列 #

如果需要可哈希的唯一标识序列，可以将排序后的节点和边转成不可变元组：

• 把每个节点的属性按固定顺序转成元组，所有节点元组排序后组成节点元组列表；
• 把每条边的（源节点标识、边属性、目标节点标识）转成元组，所有边元组排序后组成边元组列表；
• 最终将两个元组列表组合成一个大元组，确保每次生成的结果完全一致且可哈希。

内容的提问来源于stack exchange，提问作者Hai Le