函数API的调用,按照以下步骤来创建构建图:
1.networkx的加载
在python中调用networkx通常只需要将该库导入即可
import networkx as nx
2.图对象的创建
networkx提供了四种基本图对象:Graph,DiGraph,MultiGraph,MultiDiGraph。
使用如下调用方式,可以创建以上四种图对象的空图。
G=nx.Graph()
G=nx.DiGraph()
G=nx.MultiGraph()
G=nx.MultiDiGraph()
在 networkx中,图的各个节点允许以哈希表对象来表示,而对于图中边的各个参量,则可以通过与边相关联的方式来标识,一般而言,对于权重,用weight作为keyword,而对于其他的参数,使用者可以采用任何除weight以外的keyword来命名。
3.在2中,创建的只是一副空图,为了得到一个有节点、有边的图,一般采用下面这个函数:
1
2
G.add_edge(1,2) #default edge data=1
G.add_edge(1,2) #specify edge data=0.9
add_edge()函数,该函数在调用时需要传入两个参数u和v,以及多个可选参数
u和v即图中的两个节点,如果图中不存在节点,在调用时会自动将这两个节点添加入内,同时构建两个节点之间的连接关系,可选参数通常指这条边的权重等关系参量。需要注意的是,如果图中已经存在了这条边,重新进行添加时会对这条边进行跟新操作(也就是覆盖了原有的信息)。
对于该函数,除了上述的构建方式以外,还有以下几种方式来创建边:
1
2
3
G.add_edge(*e) # single edge as tuple of two nodes
G.add_edge(1, 3, weight=7, capacity=15, length=342.7) #using many arguements to create edge
G.add_edges_from( [(1, 2)] ) # add edges from iterable container
有时候,当采用默认方式创建边以后,我们可能还会往边里面添加边的相关参数,这时候,可以采用下面的方式来更新边的信息:
1
2
3
4
5
#For non-string attribute keys, use subscript notation.
G.add_edge(1, 2)
G[1][2].update({0: 5}) #更新边的信息
G.edges[1, 2].update({0: 5}) #更新边的信息
#上述两种更新方式,择一选取即可
细心的朋友可能注意到我在写创建图的内容的时候,提到了add_edges_from()函数,该函数也是用来创建边的,该方式与add_edges()略有不同,比之add_edges()采用一个一个节点的方式进行创建,它来的更为便利。这个函数在调用时,需要一个节点元组作为参数以及多个可选参数作为边的信息。你可以这么传递:
默认创建节点之间的边:
1
G.add_edges_from([(u,v)])
也可以这么写,在创建的同时添加信息:
1
G.add_edges_from([(3, 4), (1, 4)], label='WN2898')
通过上述方式,就构建了一个3-4-1的图的连接,并给每条边打上了标签。
由此你就可以创建出自己的图模型了。
我们平时比较多会遇到的一种情景是从一堆的数据中随机选择一个, 大多数我们使用random就够了, 但是假如我们要选取的这堆数据分别有自己的权重, 也就是他们被选择的概率是不一样的, 在这种情况下, 就需要使用加权随机来处理这些数据1. 简单线性方法
下面是一种简单的方案, 传入权重的列表(weights), 然后会返回随机结果的索引值(index), 比如我们传入[2, 3, 5], 那么就会随机的返回0(概率0.2), 1(概率0.3), 2(概率0.5)
简单的思路就是把所有的权重加和, 然后随机一个数, 看看落在哪个区间
import random
def weighted_choice(weights):
totals = []
running_total = 0
for w in weights:
running_total += w
totals.append(running_total)
rnd = random.random() * running_total
for i, total in enumerate(totals):
if rnd <total:
return i
2. 加速搜索
上面这个方法看起来非常简单, 已经可以完成我们所要的加权随机, 然是最后的这个for循环貌似有些啰嗦, Python有个内置方法bisect可以帮我们加速这一步
import random
import bisect
def weighted_choice(weights):
totals = []
running_total = 0
for w in weights:
running_total += w
totals.append(running_total)
rnd = random.random() * running_total
return bisect.bisect_right(totals, rnd)
bisect方法可以帮我们查找rnd在totals里面应该插入的位置, 两个方法看起来差不多, 但是第二个会更快一些, 取决于weights这个数组的长度, 如果长度大于1000, 大约会快30%左右
3. 去掉临时变量
其实在这个方法里面totals这个数组并不是必要的, 我们调整下策略, 就可以判断出weights中的位置
def weighted_choice(weights):
rnd = random.random() * sum(weights)
for i, w in enumerate(weights):
rnd -= w
if rnd <0:
return i
这个方法比第二种方法竟然快了一倍, 当然, 从算法角度角度, 复杂度是一样的, 只不过我们把赋值临时变量的功夫省下来了, 其实如果传进来的weights是已经按照从大到小排序好的话, 速度会更快, 因为rnd递减的速度最快(先减去最大的数)
4. 更多的随机数
如果我们使用同一个权重数组weights, 但是要多次得到随机结果, 多次的调用weighted_choice方法, totals变量还是有必要的, 提前计算好它, 每次获取随机数的消耗会变得小很多
class WeightedRandomGenerator(object):
def __init__(self, weights):
self.totals = []
running_total = 0
for w in weights:
running_total += w
self.totals.append(running_total)
def next(self):
rnd = random.random() * self.totals[-1]
return bisect.bisect_right(self.totals, rnd)
def __call__(self):
return self.next()
在调用次数超过1000次的时候, WeightedRandomGenerator的速度是weighted_choice的100倍
所以我们在对同一组权重列表进行多次计算的时候选择方法4, 如果少于100次, 则使用方法3
5. 使用accumulate
在python3.2之后, 提供了一个itertools.accumulate方法, 可以快速的给weights求累积和
>>>>from itertools import accumulate
>>>>data = [2, 3, 5, 10]
>>>>list(accumulate(data))
[2, 5, 10, 20]