package com.google.mu.util.graph;

import static com.google.common.truth.Truth.assertThat;
import static com.google.common.truth.Truth8.assertThat;
import static com.google.mu.util.graph.ShortestPath.unweightedShortestCyclesFrom;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

import com.google.common.collect.ImmutableListMultimap;
import com.google.common.collect.Multimap;
import com.google.common.graph.GraphBuilder;
import com.google.common.graph.MutableGraph;
import com.google.common.truth.MultimapSubject;
import com.google.mu.util.stream.BiStream;

@RunWith(JUnit4.class)
public class ShortestCyclesTest {
  private final MutableGraph<String> graph = GraphBuilder.directed().<String>build();

  @Test public void unnweighted_oneNode() {
    graph.addNode("root");
    assertThat(unweightedShortestCyclesFrom("root", n -> graph.successors(n).stream()))
        .isEmpty();
  }

  @Test public void unweighted_twoNodes() {
    graph.putEdge("foo", "bar");
    assertThat(unweightedShortestCyclesFrom("foo", n -> graph.successors(n).stream()))
        .isEmpty();
  }

  @Test public void unweighted_threeNodesList() {
    graph.putEdge("foo", "bar");
    graph.putEdge("bar", "baz");
    assertThat(unweightedShortestCyclesFrom("foo", n -> graph.successors(n).stream()))
        .isEmpty();
  }

  @Test public void unweighted_threeNodesCycle() {
    graph.putEdge("foo", "bar");
    graph.putEdge("bar", "baz");
    graph.putEdge("baz", "foo");
    assertThat(unweightedShortestCyclesFrom(
            "foo", n -> graph.successors(n).stream()).map(Object::toString))
        .containsExactly("foo->bar->baz->foo");
  }

  static<K,V> MultimapSubject assertKeyValues(BiStream<K, V> stream) {
    Multimap<?, ?> multimap = stream.collect(ImmutableListMultimap::toImmutableListMultimap);
    return assertThat(multimap);
  }
}

@@ -696,16 +696,22 @@
  graph =
+%0A     
  GraphBu
@@ -727,16 +727,38 @@
 ected().
+allowsSelfLoops(true).
 %3CString%3E
@@ -1693,16 +1693,497 @@
 );%0A  %7D%0A%0A
+  @Test public void unweighted_multipleCycles() %7B%0A    graph.putEdge(%22foo%22, %22foo%22);%0A    graph.putEdge(%22foo%22, %22bar%22);%0A    graph.putEdge(%22bar%22, %22baz%22);%0A    graph.putEdge(%22baz%22, %22foo%22);%0A    graph.putEdge(%22baz%22, %22zoo%22);%0A    graph.putEdge(%22zoo%22, %22foo%22);%0A    assertThat(unweightedShortestCyclesFrom(%0A            %22foo%22, n -%3E graph.successors(n).stream()).map(Object::toString))%0A        .containsExactly(%22foo-%3Efoo%22, %22foo-%3Ebar-%3Ebaz-%3Efoo%22, %22foo-%3Ebar-%3Ebaz-%3Ezoo-%3Efoo%22)%0A        .inOrder();%0A  %7D%0A%0A
   static

test multiple cycles in order