如题,并未发现 cyaron 有类似功能。下文为一种可能的实现,原理为随机删除树边,同时因 Python del O(n),因此采取了看上去比较丑的写法,但复杂度是 O(n) 的。
@staticmethod
def forest(point_count, chain=0, flower=0, **kwargs):
"""forest(point_count, chain=0, flower=0, **kwargs) -> Graph
Factory method. Return a forest with point_count vertexes.
int point_count -> the count of vertexes
float chain = 0 -> 1 means the forest is a set of chains
float flower = 0 -> 1 means the forest is a set of flowers
NOTICE:only either chain or flower can be True
**kwargs(Keyword args):
bool directed = False -> whether the chain is directed(true:directed,false:not directed)
(int,int) weight_limit = (1,1) -> the limit of weight. index 0 is the min limit, and index 1 is the max limit(both included)
int weight_limit -> If you use a int for this arg, it means the max limit of the weight(included)
int/float weight_gen()
= lambda: random.randint(weight_limit[0], weight_limit[1])
-> the generator of the weights. It should return the weight. The default way is to use the random.randint()
tree_count: the count of tree in the forest generated.
"""
trees = kwargs.get("tree_count", random.randrange(1, int(point_count ** 0.6)))
graph = Graph.tree(point_count, chain, flower, directed = True, **kwargs)
graph.directed = kwargs.get("directed", False)
edges = []
for i in graph.edges:
edges.extend(i)
for i in range(point_count + 1):
graph.edges[i] = []
deletes = random.choices([i for i in range(len(edges))], k = trees - 1)
chkdel = [True for i in range(len(edges))]
for i in deletes:
chkdel[i] = False
for i, j in enumerate(edges):
if chkdel[i]:
graph.add_edge(j.start, j.end, weight = j.weight)
return graph
如题,并未发现 cyaron 有类似功能。下文为一种可能的实现,原理为随机删除树边,同时因 Python del O(n),因此采取了看上去比较丑的写法,但复杂度是 O(n) 的。