1 year ago

#365602

test-img

Klayser

Problem with DFS graph algorithm, wrong loops found

I want to create an algorithm to understand how many closed areas there are in a graph with the relative points, at the moment the problem is that it finds almost all the loops, using a DFS algorithm. However, a problem arises

This is my actual code,momentarily done on processing for instant video feedback:

import java.util.Iterator;
import java.util.LinkedList;
class Graph {
        int white = 0, gray = 1, black = 2;
        ArrayList<ArrayList<Integer>> path = new ArrayList<ArrayList<Integer>>();
        int V;
        LinkedList<Integer>[] adj;
        LinkedList<Integer>[] cycles;
        LinkedList<PVector> points = new LinkedList<PVector>();
         int num_cycles = 0;

        Graph(int v) {
            V = v;
            adj = new LinkedList[V];
            cycles = new LinkedList[V];
            for (int i = 0; i < V; i++) {
                adj[i] = new LinkedList();
                cycles[i] = new LinkedList(); 
            }

        }
        void DFSCycleUtil(int source, int parent, int[] colors, int[] parents) {
            if (colors[source] == gray) {
                System.out.println("Cycle");
                path.add(new ArrayList<Integer>());
                int curr_parent = parent;
                cycles[num_cycles].add(source);
                System.out.println(source);
                path.get(num_cycles).add(source);

                while (curr_parent != source) {
                    cycles[num_cycles].add(curr_parent);
                    path.get(num_cycles).add(curr_parent);
                    System.out.println(curr_parent);
                    curr_parent = parents[curr_parent];
                }
                num_cycles++;
                return;
            } else if (colors[source] == black) {
                return;
            }
            parents[source] = parent;
            colors[source] = gray;
            Iterator<Integer> i = adj[source].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (n != parent) {

                    DFSCycleUtil(n, source, colors, parents);
                }

            }
            colors[source] = black;
        }
        void DFSCycle() {
            int colors[] = new int[V];
            int parents[] = new int[V];
            for (int i = 0; i < V; i++) {
                colors[i] = white;
            }
            for (int i = 0; i < V; i++) {

                if (colors[i] == white) {

                    DFSCycleUtil(i, -1, colors, parents);
                }
            }
        }

        void addEdge(int u, int v) {
            adj[u].add(v);
            adj[v].add(u);
        }
        void addPoint(int x, int y){
          points.add(new PVector(x,y));
        }
        void drawGraph(){
          for(int i = 0; i<points.size();i++){
            circle(points.get(i).x,points.get(i).y,10);
            text(i+1,points.get(i).x,points.get(i).y-5);
            Iterator<Integer> in = adj[i+1].listIterator();
            
            print(i + ": \n");
            while (in.hasNext()) {
                int t = in.next();
                line(points.get(i).x,points.get(i).y,points.get(t-1).x,points.get(t-1).y);
            }
          }
          for(int i = 0; i<path.size();i++){
            fill(10,10,random(255));
            beginShape();
            for(int j = 0; j<path.get(i).size(); j++){
              vertex(points.get(path.get(i).get(j)-1).x, points.get(path.get(i).get(j)-1).y);   
            }
            endShape(CLOSE);
          }
        }
    }
void setup(){
  size(500,500);
  Graph g = new Graph(9);
  g.addEdge(1,2);
  g.addEdge(1,3);
  g.addEdge(3,2);
  g.addEdge(3,4);
  g.addEdge(5,2);
  g.addEdge(5,6);
  g.addEdge(4,2);
  g.addEdge(4,6);
  g.addEdge(4,5);
  g.addPoint(100,50);
  g.addPoint(150,50);
  g.addPoint(100,100);
  g.addPoint(150,100);
  g.addPoint(200,50);
  g.addPoint(200,100);
  g.DFSCycle();
  g.drawGraph();
}

The problem is that it also finds areas that cover other previously found areas, and I don't know how to avoid it. I would like to know first if there is a better method than the one I am using, and then how I can solve my need. Thanks in advance Example images:

This is my actual result:

enter image description here

And this would be my final result:

enter image description here

algorithm

processing

graph-theory

depth-first-search

0 Answers

Your Answer

Accepted video resources