我需要一个key ==>> value
如下图的图形结构:
圆圈中的数字是其节点的键。
我想访问 key 中的存储值,2-7-6-5
并且我想通过2-7
key 检索一个子图,其中包含2
, 6-5
, 6-11
keys-values 的集合,所以我通过嵌套映射编写了我的实现,它工作得很好,但我的问题是:
是否有任何自定义Map
实现或第三方库可以解决我的情况,以便从手动操作(例如String.split
循环和条件语句)中清理我的代码?
我需要一个key ==>> value
如下图的图形结构:
圆圈中的数字是其节点的键。
我想访问 key 中的存储值,2-7-6-5
并且我想通过2-7
key 检索一个子图,其中包含2
, 6-5
, 6-11
keys-values 的集合,所以我通过嵌套映射编写了我的实现,它工作得很好,但我的问题是:
是否有任何自定义Map
实现或第三方库可以解决我的情况,以便从手动操作(例如String.split
循环和条件语句)中清理我的代码?
如果您真的只是在寻找一个 3rd-Party Java 库来处理图表,请查看JUNG,它有很多用于图表操作的功能。但是,对于您想要实现的目标来说,这可能是矫枉过正。
拿这个 - 非常适合图形操作,也适合在摇摆中显示图形结构
<dependency>
<groupId>jgraph</groupId>
<artifactId>jgraph</artifactId>
<version>5.13.0.0</version>
</dependency>
这是一个相当简单的图构造和遍历问题。您不需要任何库。你可以在一个简单的java类中做到这一点。例如
http://it-essence.xs4all.nl/roller/technology/entry/three_tree_traversals_in_java
听起来您希望将节点实现为类实例并将链接实现为引用。使用地图来实现图形边缘将非常复杂且效率低下。难怪你想清理你的代码。我不确定我是否完全理解您的问题,但这应该很接近:
// 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);
}
}
我发现的最好的图形库不是用 Java 编写的,而是用 Scala 编写的,它利用了 Java 中没有的一些强大的 scala 特性,例如抽象类型。
它被称为 Scala 的 Graph,它非常全面,但我必须警告您,虽然 Scala 和 Java 是相互兼容的(您可以在同一个项目中构建它们并从 Scala 类调用 Java 类,反之亦然),当涉及到 Java 中不可用的某些功能时,从 Java 调用 Scala 时可能会出现一些问题。
是否有任何自定义
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
,从而避免过于频繁地复制图形结构(很像字符串缓冲区)。
如果您正在寻找 Java 中的图形数据库和操作,Neo4j可能会帮助您。如果您正在寻找一个完美的 Graph DB 和操作 API,这可能超出您的讨价还价。
它为您提供了非常高级的选项来遍历图形节点、关系、审计。Neo4j 被跨组织用于存储非常复杂的分层数据,Neo4j 的性能远远优于基于 oracle 的 R-DB 用于复杂的分层数据库。