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 Fri, 02 Mar 2012 21:09:05 GMT
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
> >
> >
>

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