Re: [jgrapht-users] hashCode and equals methods for graphs

[Vladimir K. <vla...@gm...>]

It's just a duplicate of GitHub discussion:

Here is my Graph equals vision:

Ok. Regarding my implementation we can say that two graphs are equals if:

a) they are implements the same Graph interface (for example Weighted
graph). In this case there are no difference in implementation. I mean two
graphs WeightedMultigraph and WeightedPseudograph could be equals if
following conditions are true.

b) they has identical edge sets and vertex sets. If uses instance of
IntrusiveEdge as edge its hashCode/equals features doesn't matter. It's
just a dynamically-created fake-edge which shows that two vertices are
connected.

c) they has the same weight for identical edges


On Tue, May 22, 2012 at 11:23 PM, Vladimir Kostyukov <
vla...@gm...> wrote:

> Hi John,
>
> First of all, thank you for fast reply!
>
> Regarding equals() and hashCode(). I've already implemented something and
> sent pull-request in GitHub (see GitHub project page). I hope you'll find
> my implementation useful :)
>
> BTW, I've also added two unit tests and it passes.
>
>
> On Tue, May 22, 2012 at 11:06 PM, John Sichi <js...@gm...> wrote:
>
>> CC'ing jgrapht-users list.
>>
>> Hi Vladimir,
>>
>> I'm not clear on the intent of your equals method.  Comparing hash
>> codes is not meaningful; two graphs could have the same hash code and
>> yet be totally unrelated; in this case equals should return false, not
>> true.
>>
>> There are three meaningful possibilities:
>>
>> 1) Java object identity (in this case the default equals/hashCode are
>> good enough)
>> 2) identical edge sets and vertex sets (I'm not sure whether this
>> makes sense, but it's easy to implement in terms of the corresponding
>> Collections methods)
>> 3) isomorphism (waaaaay too expensive even if some day it turns out to
>> be non-exponential)
>>
>> JVS
>>
>> On Tue, May 22, 2012 at 12:58 AM, Vladimir Kostyukov
>> <vla...@gm...> wrote:
>> > Oops. I've sent old hashCode implementation. Here is new one:
>> >
>> > public int hashCode()
>> > {
>> >         int result = 17;
>> >         for (E e: edgeSet())
>> >         {
>> >         int code = 27;
>> >             int source = getEdgeSource(e).hashCode();
>> >             int target = getEdgeTarget(e).hashCode();
>> >
>> >  // This is a paring function (see details here:
>> > http://en.wikipedia.org/wiki/Pairing_function) (VK)
>> >             int paring = ((source + target) * (source + target + 1) /
>> 2) +
>> > target;
>> >             long weight = (long) getEdgeWeight(e);
>> >
>> >             code = 37 * code + e.hashCode();
>> >             code = 37 * code + paring;
>> >             code = 37 * code + (int) (weight ^ (weight >>> 32));
>> >
>> >             result += code;
>> >         }
>> >
>> >         return result;
>> >     }
>> >
>> >
>> > On Tue, May 22, 2012 at 2:41 PM, Vladimir Kostyukov
>> > <vla...@gm...> wrote:
>> >>
>> >> Hi all,
>> >>
>> >> I've just forked JGraphT library in GitHub and started work on
>> >> implementation better serialization mechanism - I am planning to use
>> >> Externalizable instead of Serializable. It should works more faster (I
>> >> guess, we can get something about 2x-4x speed up). Now it takes about
>> 10
>> >> seconds on my laptop in demo (I've added serialization/deserialization
>> >> sections in PerformanceDemo).
>> >>
>> >> First of all, I've decided to implement hashCode() and equals()
>> methods in
>> >> AbstractGraph class. Iilve also created simple Unit tests for my
>> >> implementation. But in first run I got two tests failed. Here is:
>> >>
>> >> Failed tests:
>> testLinearGraph(org.jgrapht.alg.BlockCutpointGraphTest):
>> >> expecte d:<4> but was:<2>
>> >>   testNotBiconnected(org.jgrapht.alg.BlockCutpointGraphTest):
>> expected:<3>
>> >> but was:<2>
>> >>
>> >> I've tried to look into this, but I didn't find any Graph::equals usage
>> >> there. Could you guys, help me in this issue? Why it happens?
>> >>
>> >> Here is my implementation in AbstractGraph class:
>> >>
>> >> public int hashCode()
>> >>     {
>> >>         int result = 17;
>> >>         for (E e: edgeSet())
>> >>         {
>> >>             long source = getEdgeSource(e).hashCode();
>> >>             long target = getEdgeTarget(e).hashCode();
>> >>
>> >>             // This is a paring function (see details here:
>> >> http://en.wikipedia.org/wiki/Pairing_function) (VK)
>> >>             long paring = ((source + target) * (source + target + 1) /
>> 2)
>> >> + target;
>> >>             long weight = (long) getEdgeWeight(e);
>> >>
>> >>             result += 27 * (int) (paring ^ (paring >>> 32));
>> >>             result += 37 * (int) (e.hashCode() ^ (e.hashCode() >>>
>> 32));
>> >>             result += 47 * (int) (weight ^ (weight >>> 32));
>> >>         }
>> >>
>> >>         return result;
>> >>     }
>> >>
>> >> public boolean equals(Object object)
>> >> {
>> >>         if (this == object) return true;
>> >>         if (object == null) return false;
>> >>         if (!(object instanceof Graph)) return false;
>> >>
>> >>    // TODO: maybe we should add class checking here:
>> >>    // for example: Undirected and Directed are different graphs, but
>> could
>> >> looks the same (have same hashCodes()) (VK)
>> >>
>> >>         Graph<?, ?> g = (Graph<?, ?>) object;
>> >>
>> >>         if (vertexSet().size() != g.vertexSet().size()
>> >>             || edgeSet().size() != g.edgeSet().size()) return false;
>> >>
>> >>         // TODO: maybe we should add vertices and edges factory
>> checking
>> >> here (VK)
>> >>
>> >>         //return super.equals(object);
>> >>         return (hashCode() == g.hashCode());
>> >>     }
>> >>
>> >> BTW, my unit tests pass with my implementation.
>> >>
>> >>
>> >> I am going to send you my pull-request when I finish. It should
>> contains:
>> >> unit tests, new PerfromanceDemo, new serialization mechanism,
>> >> equals/hashCode implementations.
>> >>
>> >> --
>> >> Thanks,
>> >> Vladimir Kostyukov
>> >>
>> >
>> >
>> >
>> > --
>> > Thanks,
>> > Vladimir Kostyukov
>> >
>>
>
>
>
> --
> Thanks,
> Vladimir Kostyukov
>
>


-- 
Thanks,
Vladimir Kostyukov