Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

请求添加功能:生成森林 #108

Closed
xiaohanlin101407 opened this issue Sep 4, 2023 · 1 comment · Fixed by #146
Closed

请求添加功能:生成森林 #108

xiaohanlin101407 opened this issue Sep 4, 2023 · 1 comment · Fixed by #146
Assignees

Comments

@xiaohanlin101407
Copy link

如题,并未发现 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
@Thaumic-Executor
Copy link

其实可以PR的

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants