Data Structure and Algorithm for Circular Graph

Question

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.

Data:

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

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.

Questions:

1. What will be the best Data Structure for this requirement? For example Tree like or any other?
2. Should I write my own logic to read the data and set in Tree or are there any standard algorithms out there?
3. What’s the best way of avoiding the recursion?

Any working example will really help here :)

Please also see my working solution below.

Answer 1

My own solution:

public class MyTree 
{
    static Set<String> fileDataList = new HashSet<String>();
    static
    {
        fileDataList.add("A,B");
        fileDataList.add("A,B");
        fileDataList.add("A,H");
        fileDataList.add("B,C");
        fileDataList.add("B,D");
        fileDataList.add("D,E");
        fileDataList.add("E,F");
        fileDataList.add("F,G");
        fileDataList.add("G,C");
        fileDataList.add("H,I");
        fileDataList.add("H,J");
        fileDataList.add("J,K");
        fileDataList.add("K,L");
        fileDataList.add("L,M");
        fileDataList.add("M,K");
        fileDataList.add("L,N");
        fileDataList.add("N,O");
        fileDataList.add("N,Q");
        fileDataList.add("O,P");
        fileDataList.add("P,A");
    }

    static Map<String, Set<String>> dataMap =new HashMap<String, Set<String>>();
    static Map<String, Set<Node>> nodeMap =new HashMap<String, Set<Node>>();

    public static void main(String args[]) throws IOException
    {
        //String fileName= "data.csv";
        //fileDataList = JSSTest.getFileData(fileName);        
        //String lineageFor="100";
        String lineageFor="A";

        //Build map
        for(String kv : fileDataList)
        {
            String arr[] = kv.split(",");
            String p = arr[0];
            String c = arr[1];
            if(dataMap.containsKey(p))
            {
                dataMap.get(p).add(c);
            }
            else
            {
                Set<String> list = new HashSet<String>();
                list.add(c);
                dataMap.put(p, list);
            }
        }

        //Get the lineage for Application
        Node lineage = getLineage(lineageFor);
        print(lineage, "");
    }

    private static void print(Node node, String space) 
    {
        System.out.println(space + node.getName());

        if(node.getInNode() != null && node.getInNode().size() > 0)
        {
            for(Node child:node.getInNode())
            {
                if(child.getRecursive() == null)
                {
                    print(child, space+".");
                }
                else
                {
                    System.out.println(space + child.getName());
                    System.out.println(space  + "."+ child.getRecursive().getName());
                }
            }
        }
    }

    /**
     * Get Lineage
     * @param appName
     * @return
     */
    private static Node getLineage(String appName) 
    {
        Node node = new Node(appName);
        Set<String> allInNodes = new HashSet<String>();
        setInnerNodes(node, dataMap.get(appName), allInNodes);
        return node;
    }

    private static void setInnerNodes(Node node, Set<String> childrenList, Set<String> allInNodes) 
    {
        if(childrenList == null) return;

        for(String child:childrenList)
        {
            Node containedNode = nodeContains(node, child);
            if(containedNode != null)
            {
                node.setRecursive(new Node(child));
                continue;
            }

            Node childNode = new Node(child);            
            node.addNode(childNode);
            if(dataMap.containsKey(child))
            {
                setInnerNodes(childNode, dataMap.get(child), allInNodes);
            }
        }
    }

    static int nodeCounter=1;
    private static Node nodeContains(Node node, String child) 
    {
        if(node.getName().equals(child)) return node;

        if(node.getParent() != null)
        {
            if(node.getParent().getName().equals(child)) return node.getParent();

            if(node.getParent().getParent() != null && nodeContains(node.getParent().getParent(), child) != null)
            {
                return node.getParent();
            }
        }

        return null;
    }
}
class Node
{
    private String name;
    private Node parent;
    private Node recursive;

    public Node getParent() 
    {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    private Set<Node> inNode = new LinkedHashSet<Node>();

    public Node(String name) 
    {
        this.name=name;
    }

    public void addNode(Node child)
    {
        child.parent=this;
        this.inNode.add(child);
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Set<Node> getInNode() {
        return inNode;
    }

    public void setInNode(Set<Node> inNode) {
        this.inNode = inNode;
    }

    public Node getRecursive() {
        return recursive;
    }

    public void setRecursive(Node recursive) {
        this.recursive = recursive;
    }
}

Answer 2

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.

1. 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.

2. 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.

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).

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

}

Answer 3

Use recursion and provide a depth parameter which tells how many spaces there are in front of each output element.

Something along the lines of:

private final int INDENTSIZE = 4;

public void printNodes() {
    for (Node n : roots) {
        System.out.print("- " + n.getName());
        printNode(n, 1);
    }
}

private void printNode(Node n, int depth) {
    List<Node> children = n.getChildren();

    for (Node child : children) {
        printIndent(depth);
        System.out.print("- " + child.getName());
        printNode(child, depth + 1);
    }
}

private void printIndent(int depth) {
    System.out.println();
    for (int i = 0; i < depth * INDENTSIZE; i++) {
        System.out.print(" ");
    }
}

Of course, the getChildren() you have to implement by your own. Shouldn't be that hard if you have a Map or a Tree.

This example however, does not adress cyclic references and will then loop forever.

Answer 4

Storing your example in memory? Since what you describe is a Graph, take a look at this: Three ways to store a graph in memory, advantages and disadvantages