commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Squarcella <squar...@dia.uniroma3.it>
Subject Re: [Graph] On graph weight type(s)
Date Thu, 15 Dec 2011 13:28:53 GMT
Hi,

On 15/12/2011 14:20, James Carman wrote:
> We may be modeling the domain properly with all of this terminology, but is
> this going to be understandable to the common user?

I highly appreciated the last contributions (thanks guys!) but I also 
agree on this point, so let's start from the end.
I think that, no matter what underlying structure we come up with, the 
user should be able to specify e.g. a weighted edge with something like

public class MyEdge implements Edge, Weighted<Double> { ... }

and be able to immediately use it as an input for all the algorithms, 
without extra steps required. So the average user is happy, while "graph 
geeks" can dig into advanced capabilities and forge their personalized 
weights :)
I hope we all agree on this as a first step. Complexity comes after.

I'll take my time as well to re-think.
Claudio


> On Dec 15, 2011 7:38 AM, "Matthew Pocock"<turingatemyhamster@gmail.com>
> wrote:
>
>> Hi,
>>
>> On 15 December 2011 11:35, James Carman<james@carmanconsulting.com>
>> wrote:
>>
>>
>>> public interface BinaryOperation<T>
>>> {
>>>   public T execute(T operand1, T operand2);
>>> }
>>>
>>> Perhaps we can come up with an interface that combines the two
>>> aspects.  I'm trying to think of mathematically what that would be
>>> called.  By the way, what do you need to know "HasZero"?  A sum
>>> operation has to have a "zero", doesn't it?
>>
>> The mathematical hierarchy goes: semigroup ->  monoid.
>>
>> http://en.wikipedia.org/wiki/Semigroup
>> http://en.wikipedia.org/wiki/Monoid
>>
>> You don't need a full group here as you are only interested in a single
>> operation, not a pair of interacting operations. There are several
>> JVM-hosted libraries that model this hierarchy to a greater or lesser
>> degree. scalaz uses:
>>
>> trait Semigroup[S] {
>>   def append(s1: S
>> <
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357
>>> ,
>> s2: =>  S): S<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#22357
>> }
>>
>> trait Zero[Z] {
>>   val zero: Z<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#22160
>> }
>>
>> trait Monoid[M] extends Zero
>> <
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945
>>> [M]
>> with Semigroup<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476
>>> [M]
>>
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html
>>
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html
>>
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Monoid.scala.html
>>
>> If you're not used to reading scala, here's the essentially equivalent
>> definitions in Java:
>>
>> public interface Semigroup<S>  {
>>   public S append(S s1, S s2);
>> }
>>
>> public interface Zero<Z>  {
>>
>>   public Z zero();
>> }
>>
>> public interface Monoid<M>  extends
>> Zero<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Zero.scala.html#17945
>>> <M>,
>> Semigroup<
>> http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/Semigroup.scala.html#15476
>> <M>
>>
>>
>> So, given that you have Ordering<O>  already (or is that Comparator<C>?),
>> I'd say that Weight is defined as:
>>
>> // insert comments here about the consistency of append and compare
>> public interface Weight<W>  extends Monoid<W>, Ordered<W>
>>
>> Of course, a sensible default implementation of Weight would delegate to
>> Monoid and Ordered instances and you can then pray to the gods of hotspot
>> to inline this all away.
>>
>> public<W>  Weight<W>  weight(Monoid<W>  m, Ordered<W>  o)
{
>>   new Weight<W>() {
>>     public W zero() { return m.zero(); }
>>     ...
>>   }
>> }
>>
>> Matthew
>>
>> --
>> Dr Matthew Pocock
>> Integrative Bioinformatics Group, School of Computing Science, Newcastle
>> University
>> mailto: turingatemyhamster@gmail.com
>> gchat: turingatemyhamster@gmail.com
>> msn: matthew_pocock@yahoo.co.uk
>> irc.freenode.net: drdozer
>> skype: matthew.pocock
>> tel: (0191) 2566550
>> mob: +447535664143
>>

-- 
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squarcel@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message