Recently, in the company’s project, there was a problem of tree structure to graph structure. Originally, we represented the relationship between the entities in the project as a tree structure, that is, there is no reuse between the entities, and there is no loop. Now we need to turn it into a graph structure that can be reused between entities, but without rings. So how to solve this problem?

Let’s first define what a ring is:

Ring definition: Start with an edge and prove a ring if you can return to the current edge.

As you can see, by definition, the diagram above does not have a ring. Because you can’t come back from either side. A graph with a ring is given below.The 3, 4 and 5 of the red arrow form a loop. Because if you start at any point 3, 4, 5, you can go back to where you started. So how do we use code to tell if there’s a ring in the graph?

Code logic

The first thing you might think of is to determine whether a node has been reused. But this doesn’t work, and the first diagram shows a counter example of this idea. Instead, we need to make it clear that this is a structure described by a graph, which can be defined by referring to a graph data structure. For example, in the figure above, we can give all the edges of the figure (in the project, each edge is a ResRelation) :

1 -> 2 1 -> 3 1 -> 4 2 -> 4 3 -> 4 4 5 5 -> 3Copy the code

We need to maintain a set of colors to indicate whether an edge has been accessed, and a queue for iterative algorithms. When iterating through the graph, 1(which can be any starting point) is first enqueued, since the reachable path of 1 is [2,3,4]. So we queue the reachable path of 1. At the same time in color 1 -> 2,1 ->3,1 -> 4.

Continue iterating, the current node in queue is [2,3,4], pop up 2 first, find the reachable path of 2 as 4, and mark 2 -> 4 as accessed. Same thing for node 3.

The queue may be duplicate because [1,2, and 3] can be up to 4, and I’ve done a de-duplication in the code. So now we only have 4 in our queue. Looking for a reachable path to 4, we find 5 and mark 4 -> 5. Searching for reachable paths according to 5, we found 3 and marked 5 -> 3. Now there is only one node 3 in the queue, and we iterate again to find a reachable path for 3, and we find 3 -> 4, and then we realize that this edge has been accessed. So there are rings in this diagram. The code is shown below:

    private static boolean isCircle(String id, List<ResRelation> resRelationList) {
        boolean isCircle = false;
		/* 队列*/
        LinkedList<String> queue = Lists.newLinkedList(Lists.newArrayList(id));
		/* Tag collection */
        Set<ResRelation> color=new HashSet<>();
        while (queue.size() > 0) {
            String parentId = queue.poll();
            for (ResRelation i : resRelationList) {
				/* Find the relationship between the nodes, that is, the edge */
                if (parentId.equals(i.getStart_id())) {
					/* Check whether the edge is accessed */
                    if(! color.contains(i)){ color.add(i);if(! queue.contains(i.getEnd_id())){/* Join queue */queue.add(i.getEnd_id()); }}else{
						/* If repeated access, there is a loop */
                        isCircle=true;
                        queue.clear();
                        break; }}}}return isCircle;
    }
Copy the code