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 Sat, 03 Mar 2012 00:32:02 GMT
and I am glad you feel comfortable in [graph] James! we have only to
learn from an experienced guy like you!!
best,
-Simo

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



On Sat, Mar 3, 2012 at 1:12 AM, James Carman
<jcarman@carmanconsulting.com> wrote:
> This is what the asf is all about, man.  I like it when we have projects
> like this getting a lot of traffic.  It's great to see so many folks
> getting involved.  Thanks, guys!  This is what keeps me coming back!
>
> Sent from tablet device.  Please excuse typos and brevity.
> On Mar 2, 2012 5:50 PM, "Simone Tripodi" <simonetripodi@apache.org> wrote:
>
>> Anyway, nothing has to prevent you to make a prototype and propose a patch
>> ;)
>> -Simo
>>
>> http://people.apache.org/~simonetripodi/
>> http://simonetripodi.livejournal.com/
>> http://twitter.com/simonetripodi
>> http://www.99soft.org/
>>
>>
>>
>> On Fri, Mar 2, 2012 at 11:02 PM, Simone Tripodi
>> <simonetripodi@apache.org> wrote:
>> > Hola,
>> >
>> >> what if that mapping function becomes a responsibility of WeightedGraph
>> >> itself?
>> >> And more generally, what if any property of vertices and/or edges is
>> >> moved to the containing graph?
>> >>
>> >
>> > that would imply that Graph implementations have to implement vertices
>> > and/or edges metadata indexing, that would be anyway less performant
>> > than accessing directly on metadata contained in current node/arc -
>> > just count the number of time you should have to touch the adapted
>> > data structures, of course will be at least one more than the actual.
>> >
>> >> We could externalize all different graph properties to appropriate
>> >> interfaces (HasWeightsOnEdges, HasLabelsOnVertices, etc) and then each
>> >> algorithm specifies the needed input graph including the subset of
>> >> interfaces it needs to implement. We do something like that with weight
>> >> operations already.
>> >
>> > I am worried that with that approach the number of interfaces would
>> > proliferate like pollen during Spring, users - and devs - would get
>> > easily lost
>> >
>> > weights are something already complicated for being a simple concept,
>> > please apologize for the little offtopic:
>> >
>> > Zero, name of an element, contains `zero` method to get the zero (it
>> > is still confusing to me), Monoid  extends Zero and Semigroup - given
>> > the use inside graph math, Zero#zero and Semigroup#append can be moved
>> > directly to Monoid and rename it as WeightOperation - does it remind
>> > you something? :P
>> >
>> > 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:22 PM, Claudio Squarcella
>> > <squarcel@dia.uniroma3.it> wrote:
>> >> Hi,
>> >>
>> >>
>> >>> 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.
>> >>
>> >>
>> >> what if that mapping function becomes a responsibility of WeightedGraph
>> >> itself? And more generally, what if any property of vertices and/or
>> edges is
>> >> moved to the containing graph?
>> >>
>> >> We could externalize all different graph properties to appropriate
>> >> interfaces (HasWeightsOnEdges, HasLabelsOnVertices, etc) and then each
>> >> algorithm specifies the needed input graph including the subset of
>> >> interfaces it needs to implement. We do something like that with weight
>> >> operations already.
>> >>
>> >> Claudio
>> >>
>> >>
>> >>
>> >>> 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
>> >>>>>
>> >>>>>
>> >>
>> >> --
>> >> Claudio Squarcella
>> >> PhD student at Roma Tre University
>> >> http://www.dia.uniroma3.it/~squarcel
>> >> http://squarcella.com/
>> >>
>> >>
>> >> ---------------------------------------------------------------------
>> >> To unsubscribe, e-mail: 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
>>
>>

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


Mime
View raw message