python - Chu-Liu Edmond 算法(用于有向图)

Question

我喜欢在有向图中(有时可能有环)找到最小生成树(甚至森林)。一个解释here有一些错误。这个算法在 Python 中是否有任何实际有效的包/代码？

Answer 1

虽然我没用过，here是来自 GitHub 的实现。我在下面附上了它的本质。由于它是 GitHub 存储库，它可能会更改，因此最好使用那里的代码。如果您使用这个，请注明作者:Martin-Louis Bright .

    import sys


def _input(filename):
    prices = {}
    names = {}

    for line in file(filename).readlines():
        (name, src, dst, price) = line.rstrip().split()
        name = int(name.replace('M',''))
        src = int(src.replace('C',''))
        dst = int(dst.replace('C',''))
        price = int(price)
        t = (src,dst)
        if t in prices and prices[t] <= price:
            continue
        prices[t] = price
        names[t] = name

    return prices,names

def _load(arcs,weights):
    g = {}
    for (src,dst) in arcs:
        if src in g:
            g[src][dst] = weights[(src,dst)]
        else:
            g[src] = { dst : weights[(src,dst)] }
    return g

def _reverse(graph):
    r = {}
    for src in graph:
        for (dst,c) in graph[src].items():
            if dst in r:
                r[dst][src] = c
            else:
                r[dst] = { src : c }
    return r

def _getCycle(n,g,visited=set(),cycle=[]):
    visited.add(n)
    cycle += [n]
    if n not in g:
        return cycle
    for e in g[n]:
        if e not in visited:
            cycle = _getCycle(e,g,visited,cycle)
    return cycle

def _mergeCycles(cycle,G,RG,g,rg):
    allInEdges = []
    minInternal = None
    minInternalWeight = sys.maxint

    # find minimal internal edge weight
    for n in cycle:
        for e in RG[n]:
            if e in cycle:
                if minInternal is None or RG[n][e] < minInternalWeight:
                    minInternal = (n,e)
                    minInternalWeight = RG[n][e]
                    continue
            else:
                allInEdges.append((n,e))        

    # find the incoming edge with minimum modified cost
    minExternal = None
    minModifiedWeight = 0
    for s,t in allInEdges:
        u,v = rg[s].popitem()
        rg[s][u] = v
        w = RG[s][t] - (v - minInternalWeight)
        if minExternal is None or minModifiedWeight > w:
            minExternal = (s,t)
            minModifiedWeight = w

    u,w = rg[minExternal[0]].popitem()
    rem = (minExternal[0],u)
    rg[minExternal[0]].clear()
    if minExternal[1] in rg:
        rg[minExternal[1]][minExternal[0]] = w
    else:
        rg[minExternal[1]] = { minExternal[0] : w }
    if rem[1] in g:
        if rem[0] in g[rem[1]]:
            del g[rem[1]][rem[0]]
    if minExternal[1] in g:
        g[minExternal[1]][minExternal[0]] = w
    else:
        g[minExternal[1]] = { minExternal[0] : w }


def mst(root,G):


    RG = _reverse(G)
    if root in RG:
        RG[root] = {}
    g = {}
    for n in RG:
        if len(RG[n]) == 0:
            continue
        minimum = sys.maxint
        s,d = None,None
        for e in RG[n]:
            if RG[n][e] < minimum:
                minimum = RG[n][e]
                s,d = n,e
        if d in g:
            g[d][s] = RG[s][d]
        else:
            g[d] = { s : RG[s][d] }

    cycles = []
    visited = set()
    for n in g:
        if n not in visited:
            cycle = _getCycle(n,g,visited)
            cycles.append(cycle)

    rg = _reverse(g)
    for cycle in cycles:
        if root in cycle:
            continue
        _mergeCycles(cycle, G, RG, g, rg)

    return g


if __name__ == "__main__":
    try:
        filename = sys.argv[1]
        root = sys.argv[2]
    except IndexError:
        sys.stderr.write('no input and/or root node specified\n')
        sys.stderr.write('usage: python edmonds.py <file> <root>\n')
        sys.exit(1)

    prices,names = _input(filename)
    g = _load(prices,prices)
    h = mst(int(root),g)
    for s in h:
        for t in h[s]:
            print "%d-%d" % (s,t)