2

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

在此处输入图像描述

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

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

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

4

7 回答 7

3

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

于 2012-07-25T19:03:54.180 回答
3

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

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

http://www.jgraph.com

于 2012-07-27T13:07:33.347 回答
2

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

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

于 2012-07-23T12:53:53.263 回答
1

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

// 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);
    }

}

于 2012-07-26T03:11:18.157 回答
0

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

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

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

于 2012-07-23T10:47:09.743 回答
0

是否有任何自定义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,从而避免过于频繁地复制图形结构(很像字符串缓冲区)。

于 2012-07-23T17:55:19.033 回答
0

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

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

于 2012-07-30T09:54:53.410 回答