python – 序列化有向加权图

概述我有一个有向加权图.图的每个节点表示为2元组,其第一个元素是节点的名称,其第二个元素是包含源自此节点的所有顶点的元组,按其权重排序.基本上每个顶点的权重是它在该元组内的索引. 免责声明： a = ('A', () ) a是名称为A的节点,其中没有顶点. b = ('B', () )a = ('A', (b,) ) a是名为A的节点,其中一个顶点指向名为B的节点,权重为0. b = ('B', ( 我有一个有向加权图.图的每个节点表示为2元组,其第一个元素是节点的名称,其第二个元素是包含源自此节点的所有顶点的元组,按其权重排序.基本上每个顶点的权重是它在该元组内的索引.

免责声明：

a = ('A',() )

a是名称为A的节点,其中没有顶点.

b = ('B',() )a = ('A',(b,) )

a是名为A的节点,其中一个顶点指向名为B的节点,权重为0.

b = ('B',() )c = ('C',c) )

a是名为A的节点,其中两个顶点指向名为B和C的节点,第一个是权重0,第二个是权重1.

很明显(‘A’,c))不等于(‘A’,(c,b)).

现在我需要根据这些规则序列化这个图：

>结果的第一个元素是起始节点.
>然后按照权重递增的顺序跟随从起始节点直接可访问的所有节点.如果节点已经在结果中,请不要再次附加它.
>现在递归地将规则一和二应用于刚刚添加的所有元素.

基本上,从低到高(重量)第一,深度第二.

这里有一个示例输入和输出：

f = ('F',() )e = ('E',() )d = ('D',(e,) )c = ('C',(f,d,e) )b = ('B',(d,) )a = ('A',c) )

结果是：

['A','B','C','D','F','E']

现在我的第一个天真的方法是：

def serialize (node):    acc = []    def serializeRec (node,level):        tbd = [] #acc items to be deleted        tbi = False #insertion index        for IDx,item in enumerate (acc):            if item [1] > level and tbi == False:                tbi = IDx            if item [0] == node [0]:                if item [1] > level: tbd.append (item)                else: break        else:            if tbi == False: acc.append ( (node [0],level) )            else: acc.insert (tbi,(node [0],level) )        for item in tbd:            acc.remove (item)        for vertex in node [1]:            serializeRec (vertex,level + 1)    serializeRec (node,0)    #remove levels    return [node for node,level in acc]

这显然是一个非常糟糕的主意,因为在每次递归中我都会迭代各种列表.这就是我切换到字典的原因：

def serializeDict (node):    levels = defaultdict (List) #nodes on each level    nodes = {} #on which level is which node    def serializeRec (node,level):        try:            curLevel = nodes [node [0] ]            if curLevel > level:                nodes [node [0] ] = level                levels [curLevel].remove (node [0] )                levels [level].append (node [0] )        except:            nodes [node [0] ] = level            levels [level].append (node [0] )        for vertex in node [1]:            serializeRec (vertex,0)    #flatten dict items    return [node for level in (v for _,v in sorted (levels.items (),key = lambda x: x [0] ) ) for node in level]

除非常小的图表,其运行速度要快得多.

我现在的问题是：

如何以最小化运行时的目标优化此序列化？

内存使用无关紧要(是的,宝贝),KLOC无关紧要,只有运行时间.除输入数据的格式外,一切都可以更改.但如果最后节省时间,我很乐意在序列化功能中重新组织这些数据.

我非常感谢你阅读这篇TL; DR墙的文字.

鬼混的示例图：

z = ('Z',() ); y = ('Y',(z,) ); x = ('X',y) ); w = ('W',(x,y,z) ); v = ('V',(w,x) ); u = ('U',v) ); t = ('T',(u,w) ); s = ('S',v,u) ); r = ('R',(t,u,z) ); q = ('Q',(r,z) ); p = ('P',u) ); o = ('O',(v,r,q) ); n = ('N',z) ); m = ('M',) ); l = ('L',) ); k = ('K',v) ); j = ('J',) ); i = ('I',(n,k) ); h = ('H',(k,x) ); g = ('G',(l,) ); f = ('F',m) ); e = ('E',) ); d = ('D',e,v) ); c = ('C',(m,) ); b = ('B',) ); a = ('A',(g,m,v) )

解决方法 这可以在没有递归的情况下工作,并使用双端队列来提高效率：

from collections import dequedef serialize_plain(n):    name,children = n    output = [name]    candIDates = deque(children)    while candIDates:        cname,cchildren = candIDates.popleft()        if cname not in output:            output.append(cname)            candIDates.extend(cchildren)    return output

根据图表的大小,保留已经处理的一组节点以避免昂贵的列表查询可能是有意义的：

from collections import dequedef serialize_with_set(n):    name,children = n    output = [name]    done = {name}    candIDates = deque(children)    while candIDates:        cname,cchildren = candIDates.popleft()        if cname not in done:            output.append(cname)            done.add(cname)            candIDates.extend(cchildren)    return output

总结

以上是内存溢出为你收集整理的python – 序列化有向加权图全部内容，希望文章能够帮你解决python – 序列化有向加权图所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。