logo标签列表

支持子图同构问题的Java库是什么？

java
3
我正在尝试分析C文件中“#include”的使用（包括什么被首先包含，依赖关系等）。
为此，我从C文件中提取“#include”，然后构建一个图表。我想识别此图表中的常见模式……
到目前为止，我使用JGraphT作为图形引擎（不确定这是否是正确的表达方式），并使用JGraph进行渲染（但是使用jgraph有些问题，因为布局不再包含在免费版本中）。
我无法在jgrapht中找到任何同构支持。您是否知道任何提供此类支持的解决方案（类似于igraph，但适用于Java）？
我正在使用Java 1.5，所提出的解决方案必须是免费的...
5个回答
1

你看过Parsemis吗？

它是一个Java图形挖掘库，(子)图同构对这个过程至关重要，所以我猜他们肯定有解决这个问题的方法。

不过我不确定许可证是什么，但我相信它是开源的，因为它是为了学术目的而开发的。

1

我不确定它们中的哪一个可以做同构，但我在我的博客中收集了一些图形布局引擎的链接：http://blog.pdark.de/2009/02/11/graph-layout-in-java/

你可能也想看看graphviz。它不是Java，但有一个非常强大的布局引擎。

至于同构：您可能只需要检查级别0（即直接包含）的模式，因为在此之下的任何内容都必须根据定义是同构的（由一些包含文件包含的所有文件始终相同，除非某人在包含部分使用了很多#if魔法）。

0

最近我一直在思考这个问题（在我的情况下，是寻找可以从JSP中抽象出来的常见标记结构）。

一个库会很不错。我还没有找到一个。同时，以下是可能与您的问题相关的一些问题（等同？）

  • 我打算研究数学软件用于解析微积分问题中积分的技术。 在这种情况下，有许多已知的结构模式，而问题必须与其中一个已知的模式匹配。 最佳方法并不总是显然，因为它取决于分组在一起的术语等。

  • 生物学中用于在两种复杂分子中查找对应结构的算法也可以应用于此问题。

你关于生物学的事情是正确的... 你知道这个软件 http://www.cytoscape.org/ 吗？它有一个插件可以找到小分子的同构：drugviz。 - LB40
不，我还没有看到那个。谢谢你的指引！GINY这个名字有点不太好听... - erickson
0

我确实不知道有没有一个特定的图形库带有子图同构代码 - 因为它已知是NP完全问题，你除了搜索之外别无选择。它经常出现在图重写方案中，所以AGG可能会有所帮助。

0

看起来在几个月前的 JGraphT 的 "experimental" 包中有 同构 相关的内容，但似乎没有文档。

同构比较是化学信息学软件中的基本需求（技术上使用的是 单同态）。原子是“节点”，键是“边缘”。分子图是无向的，可以是循环的。有一些用 Java 编写的开源化学信息学库可供使用。您可能能够通过查看这些库来找到解决问题的线索。

例如，我编写了一个基于VF的单态算法的BSD许可的化学信息学库MX。我撰写了一个高级概述，介绍了该算法的实现方式，并且您可以在我的GitHub存储库中浏览映射包的源代码。大部分工作都是在DefaultState类中完成的。

MX还包括一个快速的全面环检测器和其他可能适用于您的问题的图形操作。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接