java - java中图形操作的实用程序

Question

我需要一个key ==>> value如下图的图形结构：

圆圈中的数字是其节点的键。

我想访问 key 中的存储值，2-7-6-5并且我想通过2-7key 检索一个子图，其中包含2, 6-5, 6-11keys-values 的集合，所以我通过嵌套映射编写了我的实现，它工作得很好，但我的问题是：

是否有任何自定义Map实现或第三方库可以解决我的情况，以便从手动操作（例如String.split循环和条件语句）中清理我的代码？

Answer 1

如果您真的只是在寻找一个 3rd-Party Java 库来处理图表，请查看JUNG，它有很多用于图表操作的功能。但是，对于您想要实现的目标来说，这可能是矫枉过正。

Answer 2

拿这个 - 非常适合图形操作，也适合在摇摆中显示图形结构

<dependency>
    <groupId>jgraph</groupId>
    <artifactId>jgraph</artifactId>
    <version>5.13.0.0</version>
</dependency>

http://www.jgraph.com

Answer 3

这是一个相当简单的图构造和遍历问题。您不需要任何库。你可以在一个简单的java类中做到这一点。例如

http://it-essence.xs4all.nl/roller/technology/entry/three_tree_traversals_in_java

Answer 4

听起来您希望将节点实现为类实例并将链接实现为引用。使用地图来实现图形边缘将非常复杂且效率低下。难怪你想清理你的代码。我不确定我是否完全理解您的问题，但这应该很接近：

// Null nodes are the simplest type. They represent missing children.
class NullNode {

    // Get the values of all leaves descended from this node as a set.
    Set<Integer> getValues() { return new HashSet(0); }

    // Get the values descended from the node at the end of the given
    // key path as a set.  For a null node, this should not be called.
    Set<Integer> getValues(int [] path, int i) { raise new IllegalOperationException(); }

    // Initiate the search for values.  The only way that's okay
    // for null nodes is when the path is empty.
    Set<Integer> getValues(int [] path) {
        if (path.length == 0)
            return new HashSet(0);
        else
            raise new IllegalOperationException();
    }
}

// A regular node is a null node with a key. It should
// never be instantiated. Use Interior or Leaf nodes for that.
abstract class Node extends NullNode {

    int key;

    // Initiate the search for values.  Only descend if the key matches.
    Set<Integer> getValues(int [] path) {
        return (path.length > 0 && path[0] == key) ? getValues(path, 1) : new HashSet(0);
    }
}

// Interior nodes have two children, which may be Null, Interior, or Leaf.
class InteriorNode extends Node {

    Node left, right;

    Set<Integer> getValues() {
        Set<Integer> v = left.getValues();
        v.addAll(right.getValues());
        return v;
    }

    Set<Integer> getValues(int [] path, int i) {
        if (i + 1 < path.length) {
            // Again we only descend if the key matches.
            if (path[i + 1] == left.key)  return getValues(left, i + 1);
            if (path[i + 1] == right.key) return getValues(right, i + 1);
            return new HashSet(0);
        }
        return getValues(); // Get values from both children.
    }
}

// A leaf node has no children and a value.
class LeafNode extends Node {

    int value;

    Set<Integer> getValues() {
        HashSet<Integer> v = new HashSet(1);
        v.add(value);
        return v;
    }

    Set<Integer> getValues(int [] path, int i) {
        return (i + 1 >= path.length) ? getValues() : new HashSet(0);
    }

}

Answer 5

我发现的最好的图形库不是用 Java 编写的，而是用 Scala 编写的，它利用了 Java 中没有的一些强大的 scala 特性，例如抽象类型。

它被称为 Scala 的 Graph，它非常全面，但我必须警告您，虽然 Scala 和 Java 是相互兼容的（您可以在同一个项目中构建它们并从 Scala 类调用 Java 类，反之亦然），当涉及到 Java 中不可用的某些功能时，从 Java 调用 Scala 时可能会出现一些问题。

http://www.assembla.com/spaces/scala-graph/wiki

Answer 6

是否有任何自定义Map实现或第三方库可以解决我的情况，以便从手动操作（例如String.split循环和条件语句）中清理我的代码？

如果您想消除编写操作代码的自由，那么您可以创建自己的库。您可以通过将类导出到 Jar 文件中轻松地在 Eclipse 中创建库，我认为这在 NetBeans 中是一项微不足道的任务。

如果您想防止在构建后对图形进行更改，那么您需要创建一个不可变的数据结构。使用不可变的图结构，您必须将 Graph 视为一个 Universe，并且每个操作都是一个 GraphOperation。您永远不能修改 Graph，只能创建一个新的 Graph，它是通过 Graph 与您的 GraphOperations 列表交叉产生的。假设您的 Graph 结构包含唯一的节点值，这不会造成太大问题，因为您可以愉快地使用值来描述关系。您的代码将如下所示：

Graph graph2 = graph1.process(graph1.GetTopNode().RemoveLeft());
graph2 = graph2.process(graph2.GetNode(7).AddRight(8));

GetTopNode()返回一个仅提供节点视图的对象。RemoveLeft()返回一个GraphOperation对象，该对象Graph.process()用于从操作中创建一个新图。如果您愿意，它可以只返回一个Graph内部存储链接的实现graph1，以及已传递给它的实例列表GraphOperation，从而避免过于频繁地复制图形结构（很像字符串缓冲区）。

Answer 7

如果您正在寻找 Java 中的图形数据库和操作，Neo4j可能会帮助您。如果您正在寻找一个完美的 Graph DB 和操作 API，这可能超出您的讨价还价。

它为您提供了非常高级的选项来遍历图形节点、关系、审计。Neo4j 被跨组织用于存储非常复杂的分层数据，Neo4j 的性能远远优于基于 oracle 的 R-DB 用于复杂的分层数据库。