luogu-dev / cyaron

CYaRon: Yet Another Random Olympic-iNformatics test data generator
GNU Lesser General Public License v3.0
1.35k stars 168 forks source link

Bug:生成有向有环图有生成了无环图 #96

Closed li1553770945 closed 1 year ago

li1553770945 commented 2 years ago

使用 graph = Graph.DAG(n,m,loop = True, self_loop=False, repeated_edges=False),想要生成一个有向有环图,但是生成的图是: n=5 m=5 1 2 1 3 1 5 3 5 4 2 如果是无向图,这个图是有环的,但是如果是有向图,应该是认为无环的。

li1553770945 commented 2 years ago

DAG确实应该是无环的意思,但是文档里面却说可以生成有环图,有点不太懂 image

YanWQ-monad commented 1 year ago

虽然不知道现在回复是不是有点太晚了。因为上面的 Graph.graph 是不保证连通的,之前有 issue 反映过,所以弄了一些玩意来生成连通图,本意是想 DAG() 生成有向无环连通图,DAG(loop=True) 来生成一个允许有环的有向连通图,UDAG 就是无向连通图。见识多了之后,发现 DAG 就是“有向无环图”的意思,这样方法的字面意就有点怪了,但是木已成舟,就有点懒得再改了……抱歉

对于 DAG(loop=True) 没有生成环的行为,我觉得和其它 API 的行为是比较一致的,毕竟 self_looprepeated_edges 也不保证一定就有重边和自环对吧。

yudshj commented 1 year ago

感觉这个issue可以close了。