Riešenia testu č. 3

Úloha č. 1

package graphs;

public class RegularGraphs {

    public static int getDegree(UndirectedGraph g, int vertex) {
        int degree = 0;
        for (int neighbour : g.outgoingEdgesDestinations(vertex)) {
            degree++;
        }
        return degree + (g.hasEdge(vertex, vertex) ? 1 : 0);
    }

    public static boolean isRegular(UndirectedGraph g) {
        if (g.getVertexCount() == 0) {
            return true;
        }
        int k = getDegree(g, 0);
        for (int v = 0; v <= g.getVertexCount() - 1; v++) {
            if (g.hasEdge(v, v) || getDegree(g, v) != k) {
                return false;
            }
        }
        return true;
    }
}

Úloha č. 2

package graphs;

import java.util.*;

public class ShortestCycleThroughVertex {
    private int vertex;
    private List<Integer> distances;
    private List<Integer> predecessors;
    private int shortestCycleLength = -1;

    public ShortestCycleThroughVertex(DirectedGraph g, int vertex) {
        this.vertex = vertex;
        distances = new ArrayList<>();
        predecessors = new ArrayList<>();
        for (int i = 0; i <= g.getVertexCount() - 1; i++) {
            distances.add(-1);
            predecessors.add(-1);
        }

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

    public int getShortestCycleLength() {
        return shortestCycleLength;
    }

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

Úloha č. 3

package graphs;

import java.util.*;

public class LongestCycleThroughVertex {
    private DirectedGraph g;
    private int vertex;
    private LinkedList<Integer> walk;
    private ArrayList<Boolean> visited;
    private List<Integer> longestCycle;

    public LongestCycleThroughVertex(DirectedGraph g, int vertex) {
        this.g = g;
        this.vertex = vertex;

        visited = new ArrayList<>();
        for (int i = 0; i <= g.getVertexCount() - 1; i++) {
            visited.add(false);
        }
        walk = new LinkedList<>();
        walk.add(vertex);
        visited.set(vertex, true);
        search();
    }

    private void search() {
        if (g.hasEdge(walk.getLast(), vertex)) {
            LinkedList<Integer> cycle = new LinkedList<>(walk);
            cycle.add(vertex);
            if (longestCycle == null || cycle.size() > longestCycle.size()) {
                longestCycle = cycle;
            }
        }
        for (int successor : g.outgoingEdgesDestinations(walk.getLast())) {
            if (!visited.get(successor)) {
                visited.set(successor, true);
                walk.add(successor);
                search();
                walk.removeLast();
                visited.set(successor, false);
            }
        }
    }

    public int getLongestCycleLength() {
        if (longestCycle == null) {
            return -1;
        } else {
            return longestCycle.size() - 1;
        }
    }

    public List<Integer> getLongestCycle() {
        if (longestCycle != null) {
            return Collections.unmodifiableList(longestCycle);
        } else {
            return null;
        }
    }
}