Hola Claud.io,
> * a set of interfaces: e.g. HasWeightedEdges#getWeight(edge),
> HasWeightedVertices#getWeight(vertex), etc.
> * #1 implementation with external properties: the graph keeps the
> mapping between edge/vertex and weight, so that any type can be used
> for edges/vertices
> * #2 classical implementation: we keep markers like WeightedEdge and
> WeightedVertex but only the graph knows about them. algorithms keep
> asking the graph for weights of edges/vertices, and the graph in
> turn asks the edge/vertex itself (passed as parameter).
>
> WDYT?
Apologize but I still don't understand what the benefit is on storing
nodes/arcs data in the Graph data structure - sounds to me like a
Collection<Integer> where, to know the int value of its elements, have
to query the data structure, i.e.
Collection<Integer> integerCollection = ...;
for ( Integer ptr : integerCollection )
{
int value = integerCollection.getInt( ptr );
}
It is weird to me even reading it.
When I started modeling Graph, I had collections in mind - above all
to simplify its adoption - I would be more than pleased to drop
Weighted* version of graphs and come back to the previous situation,
but with the annoying type inference issue fixed.
> no, trying to be clearer: you propose to rename Monoid into WeightOperation,
> which is like renaming Addition into Operation. Or alternatively to call the
> current *WeightBaseOperations something like *WeightMonoid. In both cases I
> disagree because I would prefer to keep a clear distinction between single
> well-defined properties/operations (like Addition or Comparator) and the
> comprehensive implementation (e.g. DoubleWeightBaseOperations) that
> implements all the operations it can implement with Doubles.
OK, concept is clear, I still don't agree on the nomenclature, anyway.
Actually *WeightBaseOperations describe
*WeightAdditionalOrderedMonoid, so *BaseOperations doesn't sound self
explaining.
Moreover, The Zero interface is the *additional* monoid identity
element, if someone has to implement the Multiplication Monoid I
wouldn't expect he implements the One interface wich declares O one()
method.
This is why IMHO in the current algebra model, Zero has to be dropped
and has to be modified in:
/**
* semigroup is an algebraic structure consisting of a set together
with an associative binary operation.
*/
interface Semigroup<E>
{
E append( E s1, E s2 );
}
/**
* A {@link Monoid} is a {@link Semigroup} with an identity value.
*/
public interface Monoid<E>
extends Semigroup<M>
{
E identity();
E inverse( E element );
}
that would continue working for every Monoid specialization. Or not? thoughts?
Thanks and 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:43 PM, Claudio Squarcella
<squar...@dia.uniroma3.it> wrote:
> Hi,
>
>
> On 03/03/2012 02:21, Simone Tripodi wrote:
>>>
>>> first of all: yes, I will play with this stuff as soon as I find the time
>>> :)
>>
>> this is scaring... go Orb.io, go! :)
>>
>>> constant), but still there is one more step of indirection. So we would
>>> need
>>> to test and compare performances, hopefully with acceptable results.
>>
>> sounds it would be better if you implement that stuff in a branch to
>> keep both implementations, IMHO
>
>
> sure :)
>
>
>>> * with the current approach: one interface for edge-weighted graphs
>>> (EdgeWeightedGraph, renaming the current WeightedGraph?), one for
>>> vertex-weighted graphs (VertexWeightedGraph) and maybe even one for
>>> weights on both edges and vertices (EdgeAndVertexWeightedGraph?) --
>>> not to talk about their counterparts with labels, etc;
>>> * with the proposed approach: a Graph would implement
>>> HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe also
>>> HasLabelsOnEdges if needed.
>>
>> do you remember that we reintroduced the WeightedGraph just for the
>> type inference issue on fluent APIs in Eclipse, do you? ;) It would
>> have been worked otherwise as well dropping the WeightedGraph and
>> expressing types only on Vertex/Edges
>
>
> that is right. On the other hand with "HasWeightedEdges" we could drop
> "WeightedEdge" and so on: one interface in, one out.
>
> Or we could even save both approaches as alternative implementations. That
> is:
>
> * a set of interfaces: e.g. HasWeightedEdges#getWeight(edge),
> HasWeightedVertices#getWeight(vertex), etc.
> * #1 implementation with external properties: the graph keeps the
> mapping between edge/vertex and weight, so that any type can be used
> for edges/vertices
> * #2 classical implementation: we keep markers like WeightedEdge and
> WeightedVertex but only the graph knows about them. algorithms keep
> asking the graph for weights of edges/vertices, and the graph in
> turn asks the edge/vertex itself (passed as parameter).
>
> WDYT?
>
>
>>> I know that this kind of "mismatch" is not your favourite ;) but would
>>> you
>>> really call "Operations" something which is just an "Addition" -- or
>>> viceversa "DoubleWeightAddition" something that might later be expanded
>>> with
>>> other operations?
>>
>> I am confused now: this is what you did in the concrete implementation!
>
>
> no, trying to be clearer: you propose to rename Monoid into WeightOperation,
> which is like renaming Addition into Operation. Or alternatively to call the
> current *WeightBaseOperations something like *WeightMonoid. In both cases I
> disagree because I would prefer to keep a clear distinction between single
> well-defined properties/operations (like Addition or Comparator) and the
> comprehensive implementation (e.g. DoubleWeightBaseOperations) that
> implements all the operations it can implement with Doubles.
>
> Hoping we'll converge somewhere, maybe asymptotically ;)
> Claudio
>
>
>>
>> time to sleep, cannot reply anymore, read tomorrow
>>
>> -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:37 AM, Claudio Squarcella
>> <squar...@dia.uniroma3.it> wrote:
>>>
>>> Hi,
>>>
>>>
>>>>> 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.
>>>
>>>
>>> that is absolutely right. Not asymptotically if the implementation is
>>> good
>>> (hashmaps are already good enough with their read time which is basically
>>> constant), but still there is one more step of indirection. So we would
>>> need
>>> to test and compare performances, hopefully with acceptable results.
>>>
>>>
>>>>> 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
>>>
>>>
>>> but that would happen anyway as soon as we implement an algorithm with
>>> weights on vertices, right? Here are the options I see:
>>>
>>> * with the current approach: one interface for edge-weighted graphs
>>> (EdgeWeightedGraph, renaming the current WeightedGraph?), one for
>>> vertex-weighted graphs (VertexWeightedGraph) and maybe even one for
>>> weights on both edges and vertices (EdgeAndVertexWeightedGraph?) --
>>> not to talk about their counterparts with labels, etc;
>>> * with the proposed approach: a Graph would implement
>>> HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe also
>>> HasLabelsOnEdges if needed.
>>>
>>>
>>>
>>>> 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
>>>
>>>
>>> I can agree with most of what you say but I would still call the result
>>> Monoid, or maybe even better Addition -- because that is what it is, a
>>> Monoid representing the sum operation. "WeightOperation" sounds more like
>>> a
>>> general "container" which can include Addition, Comparator, and maybe in
>>> the
>>> near future Multiplication or who knows what -- which again is pretty
>>> much
>>> what happens now with the wrappers for Double, Integer, etc.
>>>
>>> I know that this kind of "mismatch" is not your favourite ;) but would
>>> you
>>> really call "Operations" something which is just an "Addition" -- or
>>> viceversa "DoubleWeightAddition" something that might later be expanded
>>> with
>>> other operations?
>>>
>>> Ciao and thanks for your feedback!
>>> Claudio
>>>
>>>
>>>> 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
>>>> <squar...@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.dunn...@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<
>>>>>>> squar...@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-unsubscr...@commons.apache.org>
>>>>>>>>
>>>>>>>> For additional commands, e-mail: dev-h...@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-unsubscr...@commons.apache.org
>>>>>
>>>>> For additional commands, e-mail: dev-h...@commons.apache.org
>>>>>
>>>> ---------------------------------------------------------------------
>>>> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
>>>> For additional commands, e-mail: dev-h...@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-unsubscr...@commons.apache.org
>>> For additional commands, e-mail: dev-h...@commons.apache.org
>>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
>> For additional commands, e-mail: dev-h...@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-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
