Java Stream API : Find the maximum clique in a graph

Introduction

Finding the maximum clique in a graph is a classic problem in computer science and graph theory. A clique is a subset of vertices in an undirected graph such that every pair of vertices in the subset is connected by an edge. The maximum clique is the largest clique in the graph. In this blog post, we will explore how to find the maximum clique in a graph using Java Stream API.

Java Stream API : Find the maximum clique in a graph

Graph Representation

We will represent the graph as an adjacency matrix, where `graph[i][j]` is true if there is an edge between vertices `i` and `j`, and false otherwise. The graph will be represented as a two-dimensional array of booleans.

boolean[][] graph = {

    {false, true, true, false, false},

    {true, false, true, true, false},

    {true, true, false, true, true},

    {false, true, true, false, true},

    {false, false, true, true, false}

};

In this example, the graph has 5 vertices, and the adjacency matrix represents the following edges:

- Vertex 0 is connected to vertices 1 and 2.

- Vertex 1 is connected to vertices 0, 2, and 3.

- Vertex 2 is connected to vertices 0, 1, 3, and 4.

- Vertex 3 is connected to vertices 1, 2, and 4.

- Vertex 4 is connected to vertices 2 and 3.

Finding Cliques

To find all cliques in the graph, we will use a recursive algorithm that generates all possible subsets of vertices and checks if each subset is a clique. We will then filter out the maximum cliques from the list of all cliques.

import java.util.*;

import java.util.stream.*;

public class MaximumCliqueFinder {

    public static List<List<Integer>> findCliques(boolean[][] graph) {

        List<List<Integer>> cliques = new ArrayList<>();

        List<Integer> currentClique = new ArrayList<>();

        Set<Integer> candidates = IntStream.range(0, graph.length).boxed().collect(Collectors.toSet());

        findCliquesUtil(graph, cliques, currentClique, candidates);

        return cliques;

    }

    private static void findCliquesUtil(boolean[][] graph, List<List<Integer>> cliques,

                                        List<Integer> currentClique, Set<Integer> candidates) {

        if (candidates.isEmpty()) {

            cliques.add(new ArrayList<>(currentClique));

            return;

        }

        List<Integer> candidatesList = new ArrayList<>(candidates);

        for (Integer candidate : candidatesList) {

            Set<Integer> newCandidates = new HashSet<>(candidates);

            newCandidates.retainAll(getNeighbors(candidate, graph));

            currentClique.add(candidate);

            findCliquesUtil(graph, cliques, currentClique, newCandidates);

            currentClique.remove(candidate);

            candidates.remove(candidate);

        }

    }

    private static Set<Integer> getNeighbors(int vertex, boolean[][] graph) {

        Set<Integer> neighbors = new HashSet<>();

        for (int i = 0; i < graph[vertex].length; i++) {

            if (graph[vertex][i]) {

                neighbors.add(i);

            }

        }

        return neighbors;

    }

    public static List<List<Integer>> findMaximumCliques(boolean[][] graph) {

        List<List<Integer>> allCliques = findCliques(graph);

        int maxSize = allCliques.stream().mapToInt(List::size).max().orElse(0);

        return allCliques.stream().filter(clique -> clique.size() == maxSize).collect(Collectors.toList());

    }

    public static void main(String[] args) {

        boolean[][] graph = {

            {false, true, true, false, false},

            {true, false, true, true, false},

            {true, true, false, true, true},

            {false, true, true, false, true},

            {false, false, true, true, false}

        };

        List<List<Integer>> maximumCliques = findMaximumCliques(graph);

        System.out.println("Maximum Cliques:");

        for (List<Integer> clique : maximumCliques) {

            System.out.println(clique);

        }

    }

}

In this code, the `findCliques` method generates all cliques in the graph using a recursive approach. The `findMaximumCliques` method filters out the maximum cliques from the list of all cliques based on their size.

Conclusion

In this blog post, we explored how to find the maximum clique in a graph using Java Stream API. We represented the graph as an adjacency matrix and implemented an algorithm to find all cliques in the graph. Finally, we filtered out the maximum cliques from the list of all cliques. This approach demonstrates the power and flexibility of Java Stream API in solving graph-related problems.