Re: [jgrapht-users] Bizarre issue with TopologicalOrderIterator

[John S. <js...@gm...>]

I don't see any dependency between Q and N in your code, so why do you
think their relative order would be deterministic?
On Dec 3, 2014 2:10 PM, <org...@io...> wrote:

> 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
>
>
> ------------------------------------------------------------------------------
> Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and Dashboards
> with Interactivity, Sharing, Native Excel Exports, App Integration & more
> Get technology previously reserved for billion-dollar corporations, FREE
>
> http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>