python – 子图同构

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 子图同构，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含981字，纯文字阅读大概需要2分钟。

内容图文

在igraph或networkx中,在稀疏有向图中找到长度为4的所有简单路径的最快方法是什么？一种方法是制作长度为4的简单路径的图形并使用子图同构vf2函数.这是最好/最快的方式吗？

我没有源节点,我想在整个图中存在长度为4的所有简单路径.

在我的数据中,可能很少有这样的路径,我希望能够有效地迭代它们.

解决方法:

使用这样的函数：

def simple_paths(start, length, visited=[]):
    if length==0:
        yield(visited + [start])
    else:
        for child in children(start):
            if child not in visited:
                for path in simple_paths(child, length-1, visited + [start]):
                    yield(path)

您可以通过调用列出长度为4的所有简单路径

for start in nodes():
    for path in simple_paths(start, 4):
        print path

上面假设nodes()返回图中所有节点的可迭代,并且children(x)返回节点x的子节点的可迭代.

将simple_paths()函数正确应用于上图可以得到：

['5', '9', '3', '1', '0']
['6', '5', '9', '3', '1']
['6', '5', '3', '1', '0']
['9', '5', '3', '1', '0']

这证明了这个功能：

>尊重有向边(例如,它不选择[‘6′,’5′,’1′,’3′,’9’])
>只选择简单路径(例如,它不选择[‘6′,’5′,’3′,’1′,’5’])

内容总结

以上是互联网集市为您收集整理的python – 子图同构全部内容，希望文章能够帮你解决python – 子图同构所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端