Finding a cycle in a graph-like object

manpreet Best Answer 2 years ago

I'm implementing some kind of graph-like objects that I'll describe now.

I have the following objects:

Node - contains two doubles (lat, lon) and two arcs (edges). MeetingPointNode extends node - contains two doubles (lat, lon) and eight arcs. Arc - contains a list of nodes (some regular some meeting points). Ring - contains a list of arcs. (Basically it's going to look like polygon).

I have the following problem: I need to start from a random Meeting Point and iterate until I came back to the same Meeting Point or I came into a dead-end (I only iterate over meeting points and ignore regular nodes). Here is my implementation trying to achieve that goal:

public void findRing(Node ringHead, Node current, List<Arc> arcs, Ring foundRing) {
        if (current == ringHead) {
            foundRing = new Ring();
            foundRing.setArcs(arcs);
            return;
        }

        for (int i = 0; i < 8; i++) {
           Arc currentArc = current.getArcs()[i];
           if (currentArc == null) {
                return;
           }

           arcs.add(currentArc);
           currentArc.setIsUsed(true);
           for (Node n : currentArc.getListOfNodes()) {
               if (n.getClass() != MeetingPointNode.class)
                   continue;
               findRing(ringHead, n, arcs, foundRing);

           }
           if (foundRing == null) {
              currentArc.setIsUsed(false);
              arcs.remove(current);
           }
       }
       return;
}

I will call the method in the following format: findRing(head, headNext /* the next meetingPoint from head*/, new ArrayList(), null);

I will be glad to get any help.

manpreet 2 years ago