Paul Ngugi

Posted on

# Case Study: The Connected Circles Problem

The connected circles problem is to determine whether all circles in a two-dimensional plane are connected. This problem can be solved using a depth-first traversal. The DFS algorithm has many applications. This section applies the DFS algorithm to solve the connected circles problem.

In the connected circles problem, you determine whether all the circles in a two-dimensional plane are connected. If all the circles are connected, they are painted as filled circles, as shown in Figure below (a). Otherwise, they are not filled, as shown in Figure below (b).

We will write a program that lets the user create a circle by clicking a mouse in a blank area that is not currently covered by a circle. As the circles are added, the circles are repainted filled if they are connected or unfilled otherwise.

We will create a graph to model the problem. Each circle is a vertex in the graph. Two circles are connected if they overlap. We apply the DFS in the graph, and if all vertices are found in the depth-first search, the graph is connected.

The program is given in the code below.

``````import javafx.application.Application;
import javafx.geometry.Point2D;
import javafx.scene.Node;
import javafx.scene.Scene;
import javafx.scene.layout.Pane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Circle;
import javafx.stage.Stage;

public class ConnectedCircles extends Application {
@Override // Override the start method in the Application class
public void start(Stage primaryStage) {
// Create a scene and place it in the stage
Scene scene = new Scene(new CirclePane(), 450, 350);
primaryStage.setTitle("ConnectedCircles"); // Set the stage title
primaryStage.setScene(scene); // Place the scene in the stage
primaryStage.show(); // Display the stage
}

public static void main(String[] args) {
Application.launch(args);
}

/** Pane for displaying circles */
class CirclePane extends Pane {
public CirclePane() {
this.setOnMouseClicked(e -> {
if (!isInsideACircle(new Point2D(e.getX(), e.getY()))) {
colorIfConnected();
}
});
}

/** Returns true if the point is inside an existing circle */
private boolean isInsideACircle(Point2D p) {
for (Node circle: this.getChildren())
if (circle.contains(p))
return true;

return false;
}

/** Color all circles if they are connected */
private void colorIfConnected() {
if (getChildren().size() == 0)
return; // No circles in the pane

// Build the edges
java.util.List<AbstractGraph.Edge> edges = new java.util.ArrayList<>();
for (int i = 0; i < getChildren().size(); i++)
for (int j = i + 1; j < getChildren().size(); j++)
if (overlaps((Circle)(getChildren().get(i)), (Circle)(getChildren().get(j)))) {
}

// Create a graph with circles as vertices
Graph<Node> graph = new UnweightedGraph<>((java.util.List<Node>)getChildren(), edges);
AbstractGraph<Node>.Tree tree = graph.dfs(0); // a DFS tree
boolean isAllCirclesConnected = getChildren().size() == tree.getNumberOfVerticesFound();

for (Node circle: getChildren()) {
if (isAllCirclesConnected) { // All circles are connected
((Circle)circle).setFill(Color.RED);
}
else {
((Circle)circle).setStroke(Color.BLACK);
((Circle)circle).setFill(Color.WHITE);
}
}
}
}

public static boolean overlaps(Circle circle1, Circle circle2) {