Graph colouring algorithm: typical scheduling problem

Question

I'm training code problems like UvA and I have this one in which I have to, given a set of n exams and k students enrolled in the exams, find whether it is possible to schedule all exams in two time slots.

Input Several test cases. Each one starts with a line containing 1 < n < 200 of different examinations to be scheduled. The 2nd line has the number of cases k in which there exist at least 1 student enrolled in 2 examinations. Then, k lines will follow, each containing 2 numbers that specify the pair of examinations for each case above. (An input with n = 0 will means end of the input and is not to be processed).

Output: You have to decide whether the examination plan is possible or not for 2 time slots.

Example:

Input:

3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0

Ouput:

NOT POSSIBLE.
POSSIBLE.

I think the general approach is graph colouring, but I'm really a newb and I may confess that I had some trouble understanding the problem. Anyway, I'm trying to do it and then submit it. Could someone please help me doing some code for this problem? I will have to handle and understand this algo now in order to use it later, over and over.

I prefer C or C++, but if you want, Java is fine to me ;)

Thanks in advance

Answer 1

You are correct that this is a graph coloring problem. Specifically, you need to determine if the graph is 2-colorable. This is trivial: do a DFS on the graph, coloring alternating black and white nodes. If you find a conflict, then the graph is not 2-colorable, and the scheduling is impossible.

possible = true

for all vertex V
  color[V] = UNKNOWN

for all vertex V
  if color[V] == UNKNOWN
    colorify(V, BLACK, WHITE)

procedure colorify(V, C1, C2)
  color[V] = C1
  for all edge (V, V2)
    if color[V2] == C1
      possible = false
    if color[V2] == UNKNOWN
      colorify(V2, C2, C1)

This runs in O(|V| + |E|) with adjacency list.

Answer 2

in practice the question is if you can partition the n examinations into two subsets A and B (two timeslots) such that for every pair in the list of k examination pairs, either a belongs to A and b belongs to B, or a belongs to B and b belongs to A.

You are right that it is a 2-coloring problem; it's a graph with n vertices and there's an undirected arc between vertices a and b iff the pair or appears in the list. Then the question is about the graph's 2-colorability, the two colors denoting the partition to timeslots A and B.

A 2-colorable graph is a "bipartite graph". You can test for bipartiteness easily, see http://en.wikipedia.org/wiki/Bipartite_graph.

Answer 3

I've translated the polygenelubricant's pseudocode to JAVA code, in order to provide a solution for my problem. We have a submission platform (like uva/ACM contests), so I know it passed even in the problem with more and hardest cases.

Here it is:

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Scanner;

/**
 *
 * @author newba
 */
public class GraphProblem {

    class Edge {
        int v1;
        int v2;

        public Edge(int v1, int v2) {
            this.v1 = v1;
            this.v2 = v2;
        }
    }

    public GraphProblem () {
        Scanner cin = new Scanner(System.in);

        while (cin.hasNext()) {

            int num_exams = cin.nextInt();
            if (num_exams == 0)
                break;
            int k = cin.nextInt();
            Hashtable<Integer,String> exams = new Hashtable<Integer, String>();
            ArrayList<Edge> edges = new ArrayList<Edge>();
            for (int i = 0; i < k; i++) {
                int v1 = cin.nextInt();
                int v2 = cin.nextInt();
                exams.put(v1,"UNKNOWN");
                exams.put(v2,"UNKNOWN");
                //add the edge from A->B and B->A
                edges.add(new Edge(v1, v2));
                edges.add(new Edge(v2, v1));
            }

            boolean possible = true;
            for (Integer key: exams.keySet()){
                if (exams.get(key).equals("UNKNOWN")){
                    if (!colorify(edges, exams,key, "BLACK", "WHITE")){
                        possible = false;
                        break;
                    }
                }
            }

            if (possible)
                System.out.println("POSSIBLE.");
            else
                System.out.println("NOT POSSIBLE.");

        }
    }

    public boolean colorify (ArrayList<Edge> edges,Hashtable<Integer,String> verticesHash,Integer node, String color1, String color2){

        verticesHash.put(node,color1);
        for (Edge edge : edges){
            if (edge.v1 == (int) node) {
                if (verticesHash.get(edge.v2).equals(color1)){
                    return false;
                }
                if (verticesHash.get(edge.v2).equals("UNKNOWN")){
                    colorify(edges, verticesHash, edge.v2, color2, color1);
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        new GraphProblem();
    }
}

I didn't optimized yet, I don't have the time right new, but if you want, you/we can discuss it here.

Hope you enjoy it! ;)