[jgrapht-users] Bizarre issue with TopologicalOrderIterator

[<org...@io...>]

Hi.

I've been using jgrapht for over a year now to handle various tasks in
the implementation of a compiler. Today, I've started having an issue that's
causing me to question my own sanity.

I use jgrapht to handle the graph of dependencies between terms, types,
and modules in a shading language I've developed:

  http://mvn.io7m.com/io7m-jparasol

When attempting to run the test suite today (despite the code not having
been changed since the last commit on 2014-11-15), I suddenly find that
there's a test failing.

Specifically, I use jgrapht to handle module dependencies. The language
allows the programmer to define modules/terms/types in any order, but
the target language (GLSL) requires things to be declared in the order
of their dependencies (like C/C++). So, using a directed acyclic graph
to detect circular imports, I then sort modules topologically in
preparation for emitting GLSL declarations. I actually use the reverse
of the topological order for declarations, but that makes no difference
here.

So, for example:

--8<--

module N is
  import x.y.M;
end;

module M is

end;

module Q is
  import x.y.P;
end;

module P is
  import x.y.M;
end;

--8<--

The expected topological order for the above is something like:

  [Q, N, P, M]

  M has no dependencies, so it should probably be declared first.
  Because Q depends on P, it must be declared after P. 
  Because P depends on M, it must be declared after M.
  Because N depends on M, it must be declared after M.
  P and N could be declared in either order, obviously.

Reversing this gives me the order that I'd need to use for declarations
in the target language.

However, I'm suddenly getting the order [N, Q, P, M] from the
test suite, which doesn't really make sense whatever way I try to look
at it. The code that handles imports is pretty simple, and I've
extracted it (and the test case) to this easy example:

--8<--
package com.io7m.graphtbug;

import java.util.ArrayList;
import java.util.List;

import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph.CycleFoundException;
import org.jgrapht.traverse.TopologicalOrderIterator;
import org.junit.Assert;
import org.junit.Test;

public final class JGraphTBugTest
{
  static final class Import
  {
    private final ModulePath importer;
    private final ModulePath target;

    public Import(
      final ModulePath in_importer,
      final ModulePath in_target)
    {
      this.importer = in_importer;
      this.target = in_target;
    }

    @Override public int hashCode()
    {
      final int prime = 31;
      int result = 1;
      result = (prime * result) + this.importer.hashCode();
      result = (prime * result) + this.target.hashCode();
      return result;
    }

    @Override public boolean equals(
      final Object obj)
    {
      if (this == obj) {
        return true;
      }
      if (obj == null) {
        return false;
      }
      if (this.getClass() != obj.getClass()) {
        return false;
      }
      final Import other = (Import) obj;
      if (!this.importer.equals(other.importer)) {
        return false;
      }
      if (!this.target.equals(other.target)) {
        return false;
      }
      return true;
    }

    @Override public String toString()
    {
      final StringBuilder builder = new StringBuilder();
      builder.append("[Import ");
      builder.append(this.importer);
      builder.append(" → ");
      builder.append(this.target);
      builder.append("]");
      return builder.toString();
    }

  }

  static final class ModulePath
  {
    private final String name;

    ModulePath(
      final String in_name)
    {
      this.name = in_name;
    }

    @Override public String toString()
    {
      final StringBuilder builder = new StringBuilder();
      builder.append("[");
      builder.append(this.name);
      builder.append("]");
      return builder.toString();
    }

    @Override public int hashCode()
    {
      return this.name.hashCode();
    }

    @Override public boolean equals(
      final Object obj)
    {
      if (this == obj) {
        return true;
      }
      if (obj == null) {
        return false;
      }
      if (this.getClass() != obj.getClass()) {
        return false;
      }
      final ModulePath other = (ModulePath) obj;
      return this.name.equals(other.name);
    }
  }

  @Test public void testTopology()
    throws CycleFoundException
  {
    final DirectedAcyclicGraph<ModulePath, Import> g =
      new DirectedAcyclicGraph<ModulePath, Import>(Import.class);

    final ModulePath mm = new ModulePath("x.y.M");
    final ModulePath mn = new ModulePath("x.y.N");
    final ModulePath mp = new ModulePath("x.y.P");
    final ModulePath mq = new ModulePath("x.y.Q");

    g.addVertex(mn);
    g.addVertex(mm);
    g.addVertex(mp);
    g.addVertex(mq);

    g.addDagEdge(mn, mm, new Import(mn, mm));
    g.addDagEdge(mp, mm, new Import(mp, mm));
    g.addDagEdge(mq, mp, new Import(mq, mp));

    final TopologicalOrderIterator<ModulePath, Import> iter =
      new TopologicalOrderIterator<ModulePath, Import>(g);

    final List<ModulePath> ordered = new ArrayList<ModulePath>();

    while (iter.hasNext()) {
      final ModulePath p = iter.next();
      ordered.add(p);
    }

    System.out.println(ordered);
    Assert.assertEquals(mq, ordered.get(0));
    Assert.assertEquals(mn, ordered.get(1));
    Assert.assertEquals(mp, ordered.get(2));
    Assert.assertEquals(mm, ordered.get(3));
  }
}
--8<--

The output is:

  [[x.y.N], [x.y.Q], [x.y.P], [x.y.M]]
  
Followed by an assertion error (expected Q but got N).

What's utterly bizarre about this whole situation is that nothing has
changed in the environment from two weeks ago. Same Java version, no significant OS
updates, same jgrapht version, no changes to the code. I even have log
files showing the test output from unit tests executed on 2014-11-15
that show the output as:

  [[ModulePathFlat x.y.Q], [ModulePathFlat x.y.N], [ModulePathFlat x.y.P], [ModulePathFlat x.y.M]]

I'm using Java 8, but have tested on Java 7 too. I'm using jgrapht-core 0.9.0 from Maven Central.

Any ideas would be appreciated.

M