BFS-DFS-DEMO/BFS.java at master · LuisRobaina/BFS-DFS-DEMO · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.awt.Color;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

import com.sun.javafx.collections.MappingChange.Map;

// BFS
class BFS {
    ArrayList<Node> nodes;
    // Visiting Queue
    Queue<Node> visit;
    // Map set to backtrace
    HashMap<Node, Node> backtrace;

    // Set of visited
    ArrayList<Node> visited;

    BFS(ArrayList<Node> nodes) {
        visit = new LinkedList<>();
        visited = new ArrayList<>();
        this.nodes = nodes;
        traverse(nodes.get(0), false, null, null);
    }

    BFS(ArrayList<Node> nodes, Node source, Node sink) {
        backtrace = new HashMap<Node, Node>();
        visit = new LinkedList<>();
        visited = new ArrayList<>();
        this.nodes = nodes;
        traverse(source, true, source, sink);
    }

    private void traverse(Node n, boolean path, Node source, Node sink) {
        visit.add(n);
        visited.add(n);
        StdDraw.filledCircle(n.x, n.y, 0.005);

        while (!visit.isEmpty()) {
            n = visit.remove();
            if (path)
                explore(n, source, sink);
            else
                explore(n);
        }
        System.out.println("DONE");
    }

    int color = 0;

    private void explore(Node n, Node source, Node sink) {

        for (Node a : n.bag) {
            StdDraw.setPenColor(Color.RED);
            System.out.println(a);

            if (a == sink) {
                switch (color) {
                case 0:
                    StdDraw.setPenColor(Color.BLUE);
                    break;
                case 1:
                    StdDraw.setPenColor(Color.ORANGE);
                    break;
                case 2:
                    StdDraw.setPenColor(Color.darkGray);
                    break;
                case 3:
                    StdDraw.setPenColor(Color.green);
                    break;
                default:
                    StdDraw.setPenColor(Color.magenta);
                }
                StdDraw.line(n.x, n.y, a.x, a.y);
                visited.add(sink);
                Node current = n;

                while (current != source) {
                    Node priv = backtrace.get(current);
                    StdDraw.line(current.x, current.y, priv.x, priv.y);
                    current = priv;
                }
                // found path
                color++;
            }

            if (!visited.contains(a)) {
                StdDraw.line(n.x, n.y, a.x, a.y);
                visit.add(a);
                backtrace.put(a, n);
                // Map
                visited.add(a);
                // StdDraw.pause(1500);
                StdDraw.setPenColor(Color.BLACK);
                StdDraw.line(n.x, n.y, a.x, a.y);

            }
        }
    }

    private void explore(Node n) {
        for (Node a : n.bag) {
            StdDraw.setPenColor(Color.RED);
            System.out.println(a);
            if (!visited.contains(a)) {
                StdDraw.line(n.x, n.y, a.x, a.y);
                visit.add(a);
                // Map
                visited.add(a);
                // StdDraw.pause(1500);
                StdDraw.setPenColor(Color.BLACK);
                StdDraw.line(n.x, n.y, a.x, a.y);

            }
        }
    }

}