Riešenia testu č. 6

Úloha č. 1

// ...

public class Circles extends Application {

    @Override
    public void start(Stage primaryStage) {
           
        // ...

        ArrayList<Circle> circles = new ArrayList<>();

        canvas.setOnMouseClicked(event -> {
            Circle circle = new Circle(event.getX(), event.getY(), 20);
            MouseButton mouseButton = event.getButton();
            if (mouseButton == MouseButton.PRIMARY) {
                circle.setFill(Color.BLUE);
            }
            if (mouseButton == MouseButton.SECONDARY) {
                circle.setFill(Color.RED);
            }
            circles.add(circle);
            canvas.getChildren().add(circle);
        });

        MenuBar menuBar = new MenuBar();
        borderPane.setTop(menuBar);
        Menu mView = new Menu("Zobrazenie");
        menuBar.getMenus().add(mView);
        MenuItem miClear = new MenuItem("Zmazať");
        MenuItem miSwapColours = new MenuItem("Vymeniť farby");
        MenuItem miClose = new MenuItem("Zavrieť");
        mView.getItems().addAll(miClear, miSwapColours, miClose);

        miClear.setOnAction(event -> {
            canvas.getChildren().removeAll(circles);
            circles.clear();
        });

        miSwapColours.setOnAction(event -> {
            for (Circle circle : circles) {
                if (circle.getFill() == Color.RED) {
                    circle.setFill(Color.BLUE);
                } else {
                    circle.setFill(Color.RED);
                }
            }
        });

        miClose.setOnAction(event -> {
            Platform.exit();
        });

        // ...
    }

    // ...

}

Úloha č. 2

package graphs;

import java.util.*;

public class ShortestRestrictedPaths {
    private List<Integer> distances;
    private List<Integer> predecessors;

    public ShortestRestrictedPaths(DirectedGraph g, int start, Set<Integer> forbiddenVertices) {
        distances = new ArrayList<>();
        predecessors = new ArrayList<>();
        for (int v = 0; v <= g.getVertexCount() - 1; v++) {
            distances.add(-1);
            predecessors.add(-1);
        }

        Queue<Integer> queue = new LinkedList<>();
        distances.set(start, 0);
        queue.add(start);
        while (!queue.isEmpty()) {
            int vertex = queue.remove();
            for (int successor : g.outgoingEdgesDestinations(vertex)) {
                if (distances.get(successor) == -1) {
                    distances.set(successor, distances.get(vertex) + 1);
                    predecessors.set(successor, vertex);
                    if (!forbiddenVertices.contains(successor)) {
                        queue.add(successor);
                    }
                }
            }
        }
    }

    public int shortestRestrictedPathLength(int vertex) {
        return distances.get(vertex);
    }

    public List<Integer> shortestRestrictedPath(int vertex) {
        if (distances.get(vertex) == -1) {
            return null;
        }
        LinkedList<Integer> path = new LinkedList<>();
        int v = vertex;
        while (v != -1) {
            path.addFirst(v);
            v = predecessors.get(v);
        }
        return path;
    }

}

Úloha č. 3

package graphs;

import java.util.*;

public class ChromaticNumber {
    private DirectedGraph g;
    private int n;
    private int chromaticNumber = Integer.MAX_VALUE;
    private LinkedList<Integer> colouring;

    public ChromaticNumber(UndirectedGraph g) {
        this.g = g;
        n = g.getVertexCount();
        colouring = new LinkedList<>();
        for (int k = 0; k <= n; k++) {
            search(k, 0);
            if (chromaticNumber == k) {
                break;
            }
        }
    }

    private void search(int colours, int vertex) {
        if (vertex == n) {
            chromaticNumber = colours;
        } else if (chromaticNumber > colours) {
            for (int colour = 0; colour <= colours - 1; colour++) {
                boolean isAdmissible = true;
                for (int neighbour : g.outgoingEdgesDestinations(vertex)) {
                    if (neighbour == vertex || (neighbour < vertex && colouring.get(neighbour) == colour)) {
                        isAdmissible = false;
                    }
                }
                if (isAdmissible) {
                    colouring.add(colour);
                    search(colours, vertex + 1);
                    colouring.removeLast();
                }
            }
        }
    }

    public int getChromaticNumber() {
        return chromaticNumber;
    }

}