import org.jgrapht.*;
import org.jgrapht.alg.flow.PushRelabelMFImpl;
import org.jgrapht.graph.*;
import org.jgrapht.alg.*;

import java.util.*;

public class SauerSignage {

    /*
     * Design an algorithm that outputs whether or not a phrase can be shown using the given displays
     *
     * Input: A list of displays, each display is a list of Strings each containing one capital letter
     * i.e. { {"A", "B"}, {"C, "D"}, {"A", "C", "E"}}
     * A phrase which given as a list of Strings each containing one capital letter (no spaces)
     * i.e. {"B", "E", "D"}
     *
     * Output: A boolean true/false if there exists a selection of displays and their letters which match
     * the letters of the phrase.
     */

    public static boolean isSignagePossible(String[][] displays, String[] phrase){
        //Basic graph operations
        Graph<String, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);

        //Creates two test vertices, an edge between the two, and sets that edge weight to 1.
        graph.addVertex("test1");
        graph.addVertex("test2");
        graph.addEdge("test1", "test2");
        graph.setEdgeWeight("test1", "test2", 1.0);


        //The graph network flow algorithm you're suggested to use.
        PushRelabelMFImpl<String,DefaultWeightedEdge> maxFlow = new PushRelabelMFImpl<>(graph);
        double flowAmt = maxFlow.calculateMaximumFlow("test1", "test2");

        //This outputs the flow configuration of the graph, useful for debugging.
        //System.out.println(maxFlow.getFlowMap())

        //TODO

        return false;
    }

    public static void main(String[] args){
        String[][] displays = {{"A", "B", "C"}, {"C", "D", "E"}, {"E", "F", "G"}, {"S", "E", "F"}};
        String[] phrase = {"S", "E", "D", "C"};

        //System.out.println(isSignagePossible(displays, phrase));
    }
}