Mailing-List: contact dev-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Commons Developers List" <dev@commons.apache.org>
Received-SPF: pass (nike.apache.org: domain of simone.tripodi@gmail.com
 designates 209.85.216.50 as permitted sender)
Received-SPF: pass (google.com: domain of simone.tripodi@gmail.com designates
 10.224.187.129 as permitted sender) client-ip=10.224.187.129;
MIME-Version: 1.0
Sender: simone.tripodi@gmail.com
In-Reply-To: 
 <CAAqLGLM2zHKDJYd3_mL=e=6zv24pQVy-XDJvZzqzC89PD6-+HQ@mail.gmail.com>
References: 
 <CALznzY5WzQ99Rce44fuN=Zh4=Ze6+-0EJLSdS2bBhf7qxFQVYw@mail.gmail.com>
	<CAAqLGLMJuJ+fk5MnmpU0OeVfw6=b0Y4BfsFK4KtRobMXpQNW4w@mail.gmail.com>
	<4F508774.7080905@dia.uniroma3.it>
	<CAJwFCa3euPA4xORr_7Cz96M2SRg0KyFWeePXiB_GNB37Nwy3xQ@mail.gmail.com>
	<CALznzY48XKjzMEPAkSt+zz-M6x_EVx0vavfvTYG3z-j0rmivEA@mail.gmail.com>
	<4F513A1F.1030103@dia.uniroma3.it>
	<CAAqLGLM2zHKDJYd3_mL=e=6zv24pQVy-XDJvZzqzC89PD6-+HQ@mail.gmail.com>
Date: Fri, 2 Mar 2012 23:50:15 +0100
Message-ID: 
 <CAAqLGLPvUREik0WC=p-GUAryQ=+dBz2xOdt-T3TH7zCdF9yizQ@mail.gmail.com>
Subject: Re: [graph] Why the Vertex and Edge interfaces?
From: Simone Tripodi <simonetripodi@apache.org>
To: Commons Developers List <dev@commons.apache.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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 =C2=A0extends Zero and Semigroup - give=
n
> 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. =C2=A0It's only a function from edge =
to
>>> weight. =C2=A0Your algorithm can take a function for its weights. =C2=
=A0The 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 edge=
s 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> =C2=A0wrot=
e:
>>>
>>>> Having weights on vertices is quite common. =C2=A0Consider any probabi=
lity
>>>> transition network. =C2=A0The weight on each node is the probability o=
f 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> =C2=A0wrote:
>>>>
>>>>> Hi all,
>>>>>
>>>>> =C2=A0Claudio is aware also about algorithms where weights are associ=
ated 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 wi=
th
>>>>> 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 go=
od
>>>>
>>>> to
>>>>>
>>>>> keep them distinct from the standard "toString" method (you might wan=
t
>>>>> to
>>>>> represent only a subset of info in the label, etc).
>>>>>
>>>>> Matthew Pocock suggested an alternative approach back in the days of
>>>>> weight abstraction:
>>>>>
>>>>> =C2=A0* the graph itself is extremely simple and naked: no weights/la=
bels on
>>>>> =C2=A0 vertices/edges;
>>>>> =C2=A0* all properties are stored in some external structure, which I
>>>>> =C2=A0 imagine composed of associative maps (Map<Edge, Weight>, etc e=
tc).
>>>>>
>>>>> He motivated the idea with a "personal use case": often graphs are us=
ed
>>>>> and reused with the same structure but different weights (and/or labe=
ls,
>>>>> etc). Now if James' question becomes a second use case, maybe it's th=
e
>>>>> 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