divide_friends

App.java

import java.util.HashSet;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;

public class App {

  static class Person {

    private final String name;
    private Set<Person> friends;

    Person(String name) {
      this.name = name;
    }

    public void setFriends(Set<Person> friends) {
      this.friends = friends;
    }

    public Set<Person> getFriends() {
      return this.friends;
    }

    public boolean isFriend(Person person) {
      return friends != null && !friends.isEmpty() && (friends.contains(person)
          || person.friends.contains(this));
    }

    public String getName() {
      return name;
    }

    @Override
    public boolean equals(Object o) {
      if (o == this) {
        return true;
      }
      if (!(o instanceof Person)) {
        return false;
      }
      Person other = (Person) o;
      return this.name.equals(other.name);
    }

    @Override
    public final int hashCode() {
      return 31 + name.hashCode();
    }
  }

  /**
   * Compute the disjoint two sets of people who are not friends if possible, otherwise it fails
   */
  public static List<Set<Person>> computeDisjointSets(Set<Person> people) {
// construct the output two sets
    Set<Person> outputSetA = new HashSet<>();
    Set<Person> outputSetB = new HashSet<>();

    // running queue of the friends of people to divide in the right set
    Queue<Person> queue = new LinkedList<>();

    // Add first person to the Queue
    queue.add(people.iterator().next());

    // Iterate on all friends in the queue
    while (!queue.isEmpty()) {
      final Person topPerson = queue.poll();
      final Set<Person> topPersonFriends = topPerson.getFriends();
      // Already placed to one of the output sets
      if (outputSetA.contains(topPerson) || outputSetB.contains(topPerson)) {
        continue;
      }
      // check if the top person can be place in output set A, by checking it has no freinds in set A
      final boolean hasAnyFriendInSetA = topPersonFriends.stream()
          .anyMatch(friend -> outputSetA.contains(friend));
      if (!hasAnyFriendInSetA) {
        outputSetA.add(topPerson);
      } else {
         // check if the top person can be place in output set B, by checking it has no freinds in set B
        final boolean hasAnyFriendInSetB = topPersonFriends.stream()
            .anyMatch(friend -> outputSetB.contains(friend));
        if (!hasAnyFriendInSetB) {
          outputSetB.add(topPerson);
        } else {
          // No solution case where the person can not be placed in any of output sets
          throw new IllegalArgumentException(" People can not be divided");
        }
      }
      // add friends of top person to Queue
      queue.addAll(topPersonFriends);
    }
    return List.of(outputSetA, outputSetB);
  }

  /**
   * The problem is to divide group of people into two set such that no two people in the same set
   * friends with each other
   */
  public static void main(String[] args) {

    // case 1 solvable
    case1();

    // case 2 unsolvable
    case2();

  }

  /**
   * Can be solved 1 --2,3 -- 4,5 -- 6
   */
  private static void case1() {
    Person person1 = new Person("1");
    Person person2 = new Person("2");
    Person person3 = new Person("3");
    Person person4 = new Person("4");
    Person person5 = new Person("5");
    Person person6 = new Person("6");

    person1.setFriends(Set.of(person2, person3));

    person2.setFriends(Set.of(person1, person4));
    person3.setFriends(Set.of(person1, person5));

    person4.setFriends(Set.of(person2, person6));
    person5.setFriends(Set.of(person3, person6));

    person6.setFriends(Set.of(person4, person5));

    List<Set<Person>> result = computeDisjointSets(
        Set.of(person1, person2, person3, person4, person5, person6));
    // Print the results sets
    System.out.println(" Case 1: output sets");
    for (Set<Person> peopleSet : result) {
      System.out.println(peopleSet.stream().map(Person::getName).collect(Collectors.joining(",")));
    }
  }


  /**
   * Can be solved (square & diagonal edge) ( 2 & 3 are also friends) -- 1 --- 3 -- --  2 -- 4
   */
  private static void case2() {

    Person person1 = new Person("1");
    Person person2 = new Person("2");
    Person person3 = new Person("3");
    Person person4 = new Person("4");

    person1.setFriends(Set.of(person2, person3));

    person2.setFriends(Set.of(person1, person3, person4));// conflict case between 2 & 3
    person3.setFriends(Set.of(person1, person4, person2));

    person4.setFriends(Set.of(person2, person3));

    System.out.println(" Case 2: output");
    List<Set<Person>> result = computeDisjointSets(Set.of(person1, person2, person3, person4));
    // Print the results sets
    for (Set<Person> peopleSet : result) {
      System.out.println(peopleSet.stream().map(Person::getName).collect(Collectors.joining(",")));
    }
  }
}