commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From James Carman <jcar...@carmanconsulting.com>
Subject Re: [graph] Why the Vertex and Edge interfaces?
Date Sat, 03 Mar 2012 00:12:57 GMT
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
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message