commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: [graph] Why the Vertex and Edge interfaces?
Date Fri, 02 Mar 2012 21:14:46 GMT
of course, in that situation Vertex/Weight are just useless marker :P

-Simo

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/



On Fri, Mar 2, 2012 at 10:14 PM, Simone Tripodi
<simonetripodi@apache.org> wrote:
> Hi James,
>
> looking at the the code I think we can safety keep the Weighted*
> version AND use external functions you described. It is the same
> Comparable/Comparator pattern, WDYT?
>
> best,
> -Simo
>
> http://people.apache.org/~simonetripodi/
> http://simonetripodi.livejournal.com/
> http://twitter.com/simonetripodi
> http://www.99soft.org/
>
>
>
> On Fri, Mar 2, 2012 at 10:09 PM, James Carman
> <jcarman@carmanconsulting.com> wrote:
>> My point isn't that we would not need weights ever but we're putting a
>> needless restriction on the users (implementing a marker interface).  The
>> Edge and Vertex interfaces add no value.
>>
>> The weights can be external, too.  It's only a function from edge to
>> weight.  Your algorithm can take a function for its weights.  The files
>> library does it similar to this.
>> On Mar 2, 2012 3:08 PM, "Ted Dunning" <ted.dunning@gmail.com> wrote:
>>
>>> Having weights on vertices is quite common.  Consider any probability
>>> transition network.  The weight on each node is the probability of being in
>>> that state and the weights on the edges are conditional probabilties.
>>>
>>> Page rank is a related example of having weights on nodes.
>>>
>>> On Fri, Mar 2, 2012 at 12:40 AM, Claudio Squarcella <
>>> squarcel@dia.uniroma3.it> wrote:
>>>
>>> > Hi all,
>>> >
>>> >  Claudio is aware also about algorithms where weights are associated to
>>> >> Vertex - he's preparing his PhD research on graphes - maybe he can
>>> >> show us a more long-vision roadmap and evaluate benefits on
>>> >> simplifying the design.
>>> >>
>>> >
>>> > yes there are algorithms with weights on vertices. Of course those with
>>> > weighted edges (like the ones already implemented) are much more
>>> widespread
>>> > and frequently used, but still we cannot forget about that. Also,
>>> although
>>> > on a secondary level, labels on vertices/edges are kind of important in
>>> > many situations (including testing, debugging) where I think it is good
>>> to
>>> > keep them distinct from the standard "toString" method (you might want to
>>> > represent only a subset of info in the label, etc).
>>> >
>>> > Matthew Pocock suggested an alternative approach back in the days of
>>> > weight abstraction:
>>> >
>>> >  * the graph itself is extremely simple and naked: no weights/labels on
>>> >   vertices/edges;
>>> >  * all properties are stored in some external structure, which I
>>> >   imagine composed of associative maps (Map<Edge, Weight>, etc etc).
>>> >
>>> > He motivated the idea with a "personal use case": often graphs are used
>>> > and reused with the same structure but different weights (and/or labels,
>>> > etc). Now if James' question becomes a second use case, maybe it's the
>>> > right time to exhume that idea ;)
>>> >
>>> > Ciao,
>>> > Claudio
>>> >
>>> > --
>>> > Claudio Squarcella
>>> > PhD student at Roma Tre University
>>> > http://www.dia.uniroma3.it/~**squarcel<
>>> http://www.dia.uniroma3.it/~squarcel>
>>> > http://squarcella.com/
>>> >
>>> >
>>> > ------------------------------**------------------------------**---------
>>> > To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
>>> dev-unsubscribe@commons.apache.org>
>>> > For additional commands, e-mail: dev-help@commons.apache.org
>>> >
>>> >
>>>

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


Mime
View raw message