0

你知道我没有增加什么吗？我正在尝试生成具有 n 个节点的加权图？

我是我的增量。

因此，如果我调用 genWeightGraph(10)，我想添加 10 个节点，将节点 k 添加到两个顶点（v1 和 v2）。我开始我的图表只有两个相互连接的节点，所以它们的边列表开始为 [[1],[0]]，索引为 list[index] = vertex. 我从一组 N 节点中随机生成 k ，并将 K 连接到 2 个随机顶点。

存在加权列表是因为，就像互联网一样，您拥有的连接/边缘越多，新节点连接到您的可能性就越大。所以加权列表只是帮助我解释这种概率偏差，因为我从这个加权列表中提取/抽样。

但它并没有结束。曾经。我想不通。

def genWeightGraph(n): #n nodes, davg number of links
    links = [[] for i in xrange(n-2)] # create n many nodes -2 to adjust for insert [1],[0]
    links.insert(0,[1])
    links.insert(1,[0]) # start with [[1],[0],...[]] of n length
    weighted = [nodes for v in links for nodes in v] #initialized weighted list of [1,0]
    i = 0 #initialized edges added
    while (i < n): #add this many nodes
        v1 = random.choice(weighted) #pick a friend/vertex from weighted list
        v2 = random.choice(weighted) #pick another friend/vertex from weighted list
        k = random.choice(xrange(2,n)) #pick a new friend to connect both v1 and v2 to
        print "v1", v1
        print "v2", v2 
        print "k", k
        print "nodes", i
        if k in links[v1] or links[v2]:
           continue
        elif v1 == v2: # if you pick the same vertex, just add k to one of them
            links[v1].append(k)
            links[k].append(v1)
            weighted += [k,v1] 
            i += 1
        else:
            links.insert(v1, k) # access v1's friend list, append k
            links.insert(k, v1) # find k's list, add v
            links.insert(v2, k) #add k to v2's list
            links.insert(k, v2) #find k's list, add v2 
            weighted += [k,v1,k,v2] #add to weighted
            i += 1
4

3 回答 3

2

这就是问题：

if k in links[v1] or links[v2]:

这不是您使用 or 运算符的方式......它应该是：

if (k in links[v1]) or (k in links[v2]):

在您的代码中，一旦链接 [v2] 被初始化，您总是会获得真正的价值。

考虑以下示例

>>> a = [1,2,3]
>>> b = [4,5,6]
>>> if 3 in a or b: print 'ok'
... 
ok
>>> if 13 in a or b: print 'bad'
... 
bad
>>> if 13 in a or 13 in b: print 'bad'
... 
>>>
于 2013-11-03T21:20:14.867 回答
0

您有以下行

if k in links[v1] or links[v2]:

which 测试是否k为空in links[v1]或是否links[v2]不为空。将其更改为

if (k in links[v1]) or (k in links[v2]):
于 2013-11-03T21:19:59.443 回答
-2

正因为如此：

if k in links[v1] or links[v2]:
    continue
于 2013-11-03T21:20:00.093 回答