好的Java图算法库？

Question

有没有人对Graph算法的任何Java库有很好的经验.我试过JGraph并发现它没关系,谷歌中有很多不同的.是否有人实际在生产代码中成功使用或推荐？

为了澄清,我不是在寻找一个产生图形/图表的库,我正在寻找一个有助于Graph算法的库,例如最小生成树,Kruskal的算法节点,边缘等.理想情况下,它有一些好的算法/数据一个不错的Java OO API中的结构.

Answer 1

如果您使用的是JGraph,那么您应该尝试使用专为算法设计的JGraphT.它的一个功能是使用JGraph库进行可视化.它仍然开发,但非常稳定.我前段时间分析了JGraphT算法的复杂性.其中一些并不是最快的,但如果你要自己实现它们并需要显示图形,那么它可能是最好的选择.我真的很喜欢使用它的API,当我快速编写一个正在使用图形并稍后显示它的应用程序时.

Answer 2

摘要:

• JGraphT如果您对数据结构和算法更感兴趣.
• JGraph如果您的主要关注点是可视化.
• Jung,yWorks和BFG是人们尝试使用的其他东西.
• Prefuse是不是没有,因为必须重写大部分.
• Google Guava如果您只需要良好的数据结构.
• Apache Commons Graph.目前处于休眠状态,但提供了许多算法的实现.有关已实现算法的列表,请参阅https://issues.apache.org/jira/browse/SANDBOX-458,并与Jung,GraphT,Prefuse,jBPT进行比较

Answer 3

查看JGraphT是一个非常简单而强大的Java图形库,它做得非常好,为了减轻任何混淆,与JGraph不同.一些示例代码:

UndirectedGraph<String, DefaultEdge> g =
        new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

    String v1 = "v1";
    String v2 = "v2";
    String v3 = "v3";
    String v4 = "v4";

    // add the vertices
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);

    // add edges to create a circuit
    g.addEdge(v1, v2);
    g.addEdge(v2, v3);
    g.addEdge(v3, v4);
    g.addEdge(v4, v1);

Answer 4

JUNG是可视化的一个很好的选择,并且还有一套相当好的可用图形算法,包括用于随机图形创建,重新布线等的几种不同机制.我还发现它通常很容易扩展并在必要时进行调整.

Answer 5

Apache Commons提供commons-graph.在http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/下, 可以检查来源.示例API使用也在SVN中.有关已实现算法的列表,请参阅https://issues.apache.org/jira/browse/SANDBOX-458,并与Jung,GraphT,Prefuse,jBPT进行比较

Google Guava如果您只需要良好的数据结构.

JGraphT是一个图形库,其中实现了许多算法并且(在我的观点中)具有良好的图形模型.Helloworld示例.许可证:LGPL + EPL.

JUNG2也是一个BSD许可的库,其数据结构类似于JGraphT.它提供了JGraphT目前缺少的布局算法.最近的提交是从2010年开始的,包hep.aida.*是LGPL(通过colt库,由JUNG导入).这可以防止JUNG被用于ASF和ESF旗下的项目中.也许应该使用github fork并删除该依赖项.提交f4ca0cd正在镜像最后一次CVS提交.当前提交似乎删除了可视化功能.提交d0fb491c添加了一个.gitignore.

Prefuse使用矩阵结构存储图形,这对于稀疏图形而言不是内存有效的.许可证:BSD

Eclipse Zest内置了图形布局算法,可以独立于SWT使用.请参阅org.eclipse.zest.layouts.algorithms.使用的图形结构是Eclipse Draw2d之一,其中节点是显式对象,而不是通过泛型注入(在Apache Commons Graph,JGraphT和JUNG2中发生).

Answer 6

http://neo4j.org/是一个图形数据库,它包含许多图形算法,并且比大多数内存库更好地扩展.

Answer 7

在一个大学项目中,我通过yWorks玩弄了yFiles,发现它有相当不错的API.

Answer 8

查看蓝图:

蓝图是属性图数据模型的接口,实现,ouplement和测试套件的集合.蓝图类似于JDBC,但对于图形数据库.在TinkerPop开源软件堆栈中,Blueprints作为以下基础技术:

管道:一个懒惰的数据流框架

Gremlin:图形遍历语言

框架:对象到图形的映射器

熔炉:图算法包

Rexster:图形服务器

Answer 9

如果您使用图形算法,JDSL(Java中的数据结构库)应该足够好 - http://www.cs.brown.edu/cgc/jdsl/

Answer 10

http://incubator.apache.org/hama/是Hadoop上用于海量矩阵和图形数据的分布式科学软件包.

Answer 11

对于可视化我们的团队取得了一些成功prefuse.我们将它扩展到处理建筑地板和气泡图,并没有抱怨太多.他们有一个新的Flex工具包,也称为Flare,它使用非常相似的API.

更新:我必须同意评论,我们最终写了很多自定义功能/解决prefuse限制.我不能说从头开始本来会更好,因为我们能够通过使用prefuse来证明从第1天开始的进展.另一方面,如果我们对相同的东西进行第二次实现,我可能会跳过prefuse,因为我们已经更好地理解了这些要求.

Answer 12

试试Annas它的开源图形包,很容易掌握

http://annas.googlecode.com

Answer 13

确信Graph可以简单地表示为:

class Node {
   int value;
   List<Node> adj;
}

并实现大多数你自己感兴趣的算法.如果您在图表上的某些练习/学习会话中遇到这个问题,那么这是最好的库.;)

对于大多数常见算法,您也可以更喜欢邻接矩阵:

class SparseGraph {
  int[] nodeValues;
  List<Integer>[] edges;     
}

或某些操作的矩阵:

class DenseGraph {
  int[] nodeValues;
  int[][] edges;     
}