CODEWITHSUNDEEP
javaalgorithmrecursiongraphopenstreetmap
C. Merabi Shmulik
C. Merabi Shmulik

Reputation: 282

Finding a cycle in a graph-like object

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<Arc>(), null);

I will be glad to get any help.

Upvotes: 1

Views: 120

Answers (2)

someone_somewhere
someone_somewhere

Reputation: 811

If I understood the algorithm correctly you are actually using depth-first-search but what you want to use is breadth-first search. Example of bfs: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Graph/bfs.html

Upvotes: 0

Kostas Kryptos
Kostas Kryptos

Reputation: 4111

You can use a LinkedHashSet and store nodes as you visit them. When you find the first duplicate you have a Ring.

LinkedHashSet keeps the order in which elements were inserted into the set, so you can easily export the Ring path.

Upvotes: 1

Related Questions