数据结构与算法的圆形图 [英] Data Structure and Algorithm for Circular Graph
问题描述
我有一个要求来定义数据结构和算法为的通知数据图的Web客户端。
在服务器上，数据将在2列CSV格式（如发件人，收件人）提供。
最终输出将在 JSON 呈现格式，发送到Web请求。
我已经看到了一些树的例子可以在父子关系帮助。但对我来说，我有一个递归关系即一个家长盛大的孩子也可以用作父;这让生活有点困难，因为我跑的无限循环。
I’ve a requirement to define Data Structure and Algorithm for Circular Data Graph for web client.
At server, data will provided in a 2 column CSV format (e.g. Sender, Receiver).
Final output will be rendered in JSON format and sent to web request.
I have seen some Tree examples which can help in Parent Child relationships. But In my case, I have a recursive relationship i.e. A Parent's grand child can also be used as a Parent; which make life bit difficult as I run in to infinite loop.
数据：
Sender,Receiver
A,B
A,H
B,C
B,D
D,E
E,F
F,G
G,C
H,I
H,J
J,K
K,L
L,M
M,K
L,N
N,O
N,P
P,A
N,Q
客户端可能会导致这样的（我只在乎的Java结构）：
客户端可以请求任何节点，我必须生成整个树和发送响应，即A，K或N。
Client may render like this (I only care about Java Structure):
Client can request any Node and I have to generate the whole Tree and send the response i.e. A, K or N.
问题：
- 在什么将是最好的
数据结构这一要求？对于 例如树状或其他？ - 我应该写我自己的逻辑来阅读
数据和设置
树还是有什么标准算法出 那里？ - 什么是避免了递归的最好方法？
- What will be the best
Data Structurefor this requirement? For exampleTreelike or any other? - Should I write my own logic to read
the data and set in
Treeor are there any standard algorithms out there? - What’s the best way of avoiding the recursion?
所有工作的例子将真正帮助在这里：）
Any working example will really help here :)
请参见我下面的工作解决方案。
Please also see my working solution below.
推荐答案
我敢肯定，你已经找到了树的例子是关于如何实现树状结构正确。你的情况，你必须更加复杂，这是可能的递归循环存在某些孩子是准确的对象引用他们的祖先之一。 （是吗？）
I'm sure the tree examples you've found already are correct on how to implement a tree like structure. In your case you have the added complication that it is possible for recursive loops to exist as certain children will be exact object references to one of their ancestors. (right?)
这复杂的任何企图通过遍历每个节点的孩子穿越你的树过程中由于将围绕直到堆栈溢出这些递归连接环路发生。
Because of this complication any process that attempts to traverse your tree by iterating over the children of each node will loop around these recursive connections until stack overflow occurs.
在这种情况下，你不再真正处理的树。在数学上，一树被定义为一个格拉夫无环的。你的情况，你有周期的，因此不是一棵树，但一个的圆形图表。
In this case you are no longer really dealing with a tree. Mathematically, a tree is defined as a Graph without cycles. In your case you have cycles, and therefore not a tree but a circular graph.
我已经处理了在过去，这种情况下，我认为你可以，你可以用这个对付两种方式。
I have dealt with such situations in the past, and I think you can you can deal with this in two ways.
-
打破周期（对象级），回到树上。如果这些递归的连接情况发生，不要把真正的对象引用的祖先，而是一个存根，指示它连接到不被的在的对象引用该项目的哪些对象。
Break the cycles (at an object level), to return to a tree. Where one of these recursive connections happens, do not place the real object reference to the ancestor, but a stub that indicates which object it connects to without being the object reference to that item.
接受你有一个圆形的曲线图，并确保您的code能够应付这种遍历图的时候。确保所有客户端code与您的图形交互可以检测到它是在一个递归分支对付它恰如其分。
Accept you have a circular graph, and ensure your code can cope with this when traversing the graph. Ensure that any client code interacting with your graph can detect when it is in a recursive branch and deal with it appropriately.
恕我直言，方案2是不是非常有吸引力的，你可能会发现难以保障的约束，往往会导致错误。只要你能在树中分配给每个项目的唯一标识符，选项1效果很好，但客户仍然需要这种可能性发生的，使他们能够处理去耦合链接，并重新正确present它的意识（用于例如在树视图UI）。你还是想要一个圆形的图形模式，但将使用一棵树重新present它在一个对象级别简化了code（和presentation）。
IMHO Option 2 is not very attractive as you may find it hard to guarantee the constraint and it often leads to bugs. As long as you can allocate each item in the tree a unique identifier, option 1 works well, although clients will still need an awareness of this possibility occurring so they can process the de-coupled link and represent it correctly (for instance in a tree view UI). You are still wanting to model a circular graph, but are going to use a tree to represent it at an object level as it simplifies the code (and presentation).
完整的例子备选方案1：
Full Example of Option 1:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class CyclicGraphTest
{
public static void main(String[] args)
{
new CyclicGraphTest().test();
}
public void test()
{
NodeManager manager = new NodeManager();
Node root = manager.processNode("ZZZ");
root.add(manager.processNode("AAA"));
manager.get("AAA").add(manager.processNode("BBB"));
manager.get("AAA").add(manager.processNode("CCC"));
manager.get("AAA").add(manager.processNode("DDD"));
manager.get("DDD").add(manager.processNode("EEE"));
manager.get("EEE").add(manager.processNode("FFF"));
manager.get("FFF").add(manager.processNode("AAA"));
manager.get("AAA").add(manager.processNode("JJJ"));
root.add(manager.processNode("EEE"));
GraphWalker walker = new GraphWalker(manager, root, 1);
System.out.println(walker.printGraph());
}
/**
* Basic Node
*/
public class Node implements Iterable<Node>
{
private String id;
private List<Node> children = new ArrayList<Node>();
public Node(String id) {
this.id = id;
}
public boolean add(Node e) {
return children.add(e);
}
public String getId() {
return id;
}
@Override
public Iterator<Node> iterator() {
return children.iterator();
}
}
/**
* Cyclical Reference
*
*/
public class ReferenceNode extends Node
{
private String refId;
public ReferenceNode(String id, String refId) {
super(id);
this.refId = refId;
}
@Override
public boolean add(Node e) {
throw new UnsupportedOperationException("Cannot add children to a reference");
}
public String getRefId() {
return refId;
}
}
/**
* Keeps track of all our nodes. Handles creating reference nodes for existing
* nodes.
*/
public class NodeManager
{
private Map<String, Node> map = new HashMap<String, Node>();
public Node get(String key) {
return map.get(key);
}
public Node processNode(String id)
{
Node node = null;
if(map.containsKey(id))
{
node = new ReferenceNode(getRefId(id), id);
map.put(node.getId(), node);
}
else
{
node = new Node(id);
map.put(id, node);
}
return node;
}
private String getRefId(String id) {
int i = 0;
String refId = null;
while(map.containsKey(refId = id + "###" + i)) { i++; }
return refId;
}
public Node resolve(ReferenceNode node) {
return map.get(node.getRefId());
}
}
/**
* Walks a tree representing a cyclical graph down to a specified level of recursion
*/
public class GraphWalker
{
private NodeManager manager;
private Node root;
private int maxRecursiveLevel;
public GraphWalker(NodeManager manager, Node root, int recursiveLevel) {
super();
this.manager = manager;
this.root = root;
this.maxRecursiveLevel = recursiveLevel;
}
public String printGraph()
{
return printNode(root, 0, " ").toString();
}
private StringBuilder printNode(Node node, int recursionDepth, String prefix) {
Node resolvedNode = resolveNode(node, recursionDepth);
if(resolvedNode != node) {
recursionDepth ++;
node = resolvedNode;
}
StringBuilder sb = new StringBuilder(node.getId());
int i = 0;
for(Node child : node)
{
if(i != 0) sb.append("\n").append(prefix);
sb.append(" -> ").append(printNode(child, recursionDepth, prefix + " "));
i++;
}
return sb;
}
/**
* Returns a resolved reference to another node for reference nodes when the
* recursion depth is less than the maximum allowed
* @param node
* @param recursionDepth
* @return
*/
private Node resolveNode(Node node, int recursionDepth)
{
return (node instanceof ReferenceNode) && (recursionDepth < maxRecursiveLevel) ?
manager.resolve((ReferenceNode) node) : node;
}
}
}
这篇关于数据结构与算法的圆形图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
