Return-Path: X-Original-To: apmail-commons-dev-archive@www.apache.org Delivered-To: apmail-commons-dev-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 649059C9F for ; Sat, 3 Mar 2012 16:02:45 +0000 (UTC) Received: (qmail 95832 invoked by uid 500); 3 Mar 2012 16:02:44 -0000 Delivered-To: apmail-commons-dev-archive@commons.apache.org Received: (qmail 95757 invoked by uid 500); 3 Mar 2012 16:02:44 -0000 Mailing-List: contact dev-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: "Commons Developers List" Delivered-To: mailing list dev@commons.apache.org Received: (qmail 95749 invoked by uid 99); 3 Mar 2012 16:02:44 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 03 Mar 2012 16:02:44 +0000 X-ASF-Spam-Status: No, hits=-0.7 required=5.0 tests=RCVD_IN_DNSWL_LOW,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (athena.apache.org: domain of simone.tripodi@gmail.com designates 209.85.216.43 as permitted sender) Received: from [209.85.216.43] (HELO mail-qw0-f43.google.com) (209.85.216.43) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 03 Mar 2012 16:02:40 +0000 Received: by qadb15 with SMTP id b15so224660qad.9 for ; Sat, 03 Mar 2012 08:02:19 -0800 (PST) Received-SPF: pass (google.com: domain of simone.tripodi@gmail.com designates 10.229.77.134 as permitted sender) client-ip=10.229.77.134; Authentication-Results: mr.google.com; spf=pass (google.com: domain of simone.tripodi@gmail.com designates 10.229.77.134 as permitted sender) smtp.mail=simone.tripodi@gmail.com; dkim=pass header.i=simone.tripodi@gmail.com Received: from mr.google.com ([10.229.77.134]) by 10.229.77.134 with SMTP id g6mr2037723qck.33.1330790539963 (num_hops = 1); Sat, 03 Mar 2012 08:02:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:content-type :content-transfer-encoding; bh=VoRTaDNbLbrUlvA6zYO2w0v/X4yXig4d5Q+6wA6wEcA=; b=0YQ3v1Qeli9LpSekhduzl8RrqXAf0w+cWs14Hc5LJ8uV+OiuGpBhWiGvKE2HRSS1Eu Io1mo/ZgL1IkJ47lRNCmxL5Lcwv1W01NduKFoDIQsW52xWQS20ks9UCp9ZwINTRdYYUu ubNRKdtJJEEXJ5qAAvCqZPm8A/i3SLijPA09DrqdpgUpkVNrtbro10mzd6yYmxD9lvQg Af6GVskberoKenyq4cCd7OmQ/wWD+WL8uMTvaBOTXbvk8+//hoEI8pkenJvuSqXHnjoH /QyuRQTbJ+U0tij7TtMEl+IJ2+d9NS30cnKzUdUOn67QCh0FXYVQqYDKvSwKBd2+6jvx b4/Q== MIME-Version: 1.0 Received: by 10.229.77.134 with SMTP id g6mr1728540qck.33.1330790539870; Sat, 03 Mar 2012 08:02:19 -0800 (PST) Sender: simone.tripodi@gmail.com Received: by 10.224.195.73 with HTTP; Sat, 3 Mar 2012 08:02:19 -0800 (PST) In-Reply-To: References: <4F508774.7080905@dia.uniroma3.it> <4F513A1F.1030103@dia.uniroma3.it> <4F5167CB.4060306@dia.uniroma3.it> <4F521202.7010207@dia.uniroma3.it> <4F52236C.9000708@dia.uniroma3.it> Date: Sat, 3 Mar 2012 17:02:19 +0100 X-Google-Sender-Auth: cdZFq0AHM8EUicZT5RfKiekl_ug Message-ID: Subject: Re: [graph] Why the Vertex and Edge interfaces? From: Simone Tripodi To: Commons Developers List Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Virus-Checked: Checked by ClamAV on apache.org +1 for branches! -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Sat, Mar 3, 2012 at 5:01 PM, James Carman wrote: > Yes code will speak volumes. =C2=A0Perhaps a couple proposal branches if = we have > incompatible ideas? > On Mar 3, 2012 10:47 AM, "Simone Tripodi" wrot= e: > >> Cloud.io, >> >> > back to James' first email: any type could be immediately used as >> > edge/vertex without wrappers, while specific data related to the domai= n >> of >> > graphs (weights, labels) would be handled separately. I actually think >> this >> > is useful: back to my days of "DIY Java graphs" I implemented somethin= g >> > similar to what we have now, just to think every time: "why should I >> wrap my >> > objects with these markers? I already know my Router is a Vertex in th= e >> > graph..." >> >> I already showed be open on dropping elements, do I have to copy my >> first reply as well so we start again? :) >> OK, I started collecting various thoughts and trying to converge them >> to a common path: Vertex is something we can safety drop because we >> know its nature at priori, markers are unnecessary.This is fine. >> >> > >> > Here's the way I see it. A Graph implementing HasWeightedEdges wo= uld >> > have something like this inside: >> > >> > Map edgeWeights =3D new HashMap(); >> > >> > [... populate map, other methods, etc ...] >> > >> > // implementing HasWeightedEdges#getEdgeWeight >> > public W getEdgeWeight(E edge) >> > { >> > =C2=A0 =C2=A0[... check null etc...] >> > =C2=A0 =C2=A0return edgeWeights.get(edge); >> > >> > } >> > >> >> what is the sense, at that point, on keeping the Edge?!! It would be >> more than enough to know which is the Head and which is the Tail in >> the Edge to get the W! >> >> > then let's find a better name, but why *OrderedMonoid? >> >> maybe because they implement OrderedMonoid? :) >> >> > Assume we replace the >> > whole set of current interfaces (see my comment to the next paragraph >> below) >> > with just Addition and Comparable (the latter already exists of course= ). >> > There is no need to create another interface to merge the two >> > (ComparableAddition? OrderedAddition?). Then we have: >> > >> >> how much would Addition and Multiplication interface differ each other? >> >> > public class DoubleWeightOperations >> > =C2=A0 =C2=A0implements Addition, Comparator >> > { >> > =C2=A0 =C2=A0[...] >> > } >> > >> > I would not rename the class to DoubleWeightAddition or even >> > DoubleWeightComparableAddition. What if later we need to e.g. add a >> function >> > that normalizes weights by some factor, or returns the reciprocal of a >> > weight, etc? With the above code it would suffice to add new interface= s: >> > >> > public class DoubleWeightOperations >> > =C2=A0 =C2=A0implements Addition, Comparator, Normalization, Reciproca= l >> > { >> > =C2=A0 =C2=A0[...] >> > >> > } >> > >> > >> >> that would be fine, what is not clear is that Monoids expose the same >> interface, so *Operations class implementation canot declare same >> method multiple times >> >> > >> > That is fine for me. I simply followed pure theory while implementing >> that >> > and used all possible granularity. >> >> questionable, that is why we are still speaking about it >> >> > Now looking at our implementations I >> > think it is save enough to even merge Zero, Semigroup and Monoid (so >> that's >> > one step further than your example below) and call the result Addition= so >> > that its role is clear to everybody. Does that sound good? :) >> >> Sounds more than good, it is what I already proposed messages ago: >> >> > Zero, name of an element, contains `zero` method to get the zero (it >> > is still confusing to me), Monoid =C2=A0extends Zero and Semigroup - g= iven >> > the use inside graph math, Zero#zero and Semigroup#append can be moved >> > directly to Monoid and rename it as WeightOperation >> >> despite the rename, I still like the Monoid :P >> >> enough talk IMHO, time to code and make concrete proposals >> >> 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 2:58 PM, Claudio Squarcella >> wrote: >> > Hi, >> > >> > >> >> Apologize but I still don't understand what the benefit is on storing >> >> nodes/arcs data in the Graph data structure >> > >> > >> > back to James' first email: any type could be immediately used as >> > edge/vertex without wrappers, while specific data related to the domai= n >> of >> > graphs (weights, labels) would be handled separately. I actually think >> this >> > is useful: back to my days of "DIY Java graphs" I implemented somethin= g >> > similar to what we have now, just to think every time: "why should I >> wrap my >> > objects with these markers? I already know my Router is a Vertex in th= e >> > graph..." >> > >> > >> >> - sounds to me like a >> >> Collection =C2=A0where, to know the int value of its element= s, have >> >> to query the data structure, i.e. >> >> >> >> Collection =C2=A0integerCollection =3D ...; >> >> for ( Integer ptr : integerCollection ) >> >> { >> >> =C2=A0 =C2=A0 int value =3D 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 =C2=A0type inference issue fixed. >> > >> > >> > Here's the way I see it. A Graph implementing HasWeightedEdges wo= uld >> > have something like this inside: >> > >> > Map edgeWeights =3D new HashMap(); >> > >> > [... populate map, other methods, etc ...] >> > >> > // implementing HasWeightedEdges#getEdgeWeight >> > public W getEdgeWeight(E edge) >> > { >> > =C2=A0 =C2=A0[... check null etc...] >> > =C2=A0 =C2=A0return edgeWeights.get(edge); >> > >> > } >> > >> >>> 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. >> > >> > >> > then let's find a better name, but why *OrderedMonoid? Assume we repla= ce >> the >> > whole set of current interfaces (see my comment to the next paragraph >> below) >> > with just Addition and Comparable (the latter already exists of course= ). >> > There is no need to create another interface to merge the two >> > (ComparableAddition? OrderedAddition?). Then we have: >> > >> > public class DoubleWeightOperations >> > =C2=A0 =C2=A0implements Addition, Comparator >> > { >> > =C2=A0 =C2=A0[...] >> > } >> > >> > I would not rename the class to DoubleWeightAddition or even >> > DoubleWeightComparableAddition. What if later we need to e.g. add a >> function >> > that normalizes weights by some factor, or returns the reciprocal of a >> > weight, etc? With the above code it would suffice to add new interface= s: >> > >> > public class DoubleWeightOperations >> > =C2=A0 =C2=A0implements Addition, Comparator, Normalization, Reciproca= l >> > { >> > =C2=A0 =C2=A0[...] >> > >> > } >> > >> > >> >> >> >> 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: >> > >> > >> > That is fine for me. I simply followed pure theory while implementing >> that >> > and used all possible granularity. Now looking at our implementations = I >> > think it is save enough to even merge Zero, Semigroup and Monoid (so >> that's >> > one step further than your example below) and call the result Addition= so >> > that its role is clear to everybody. Does that sound good? :) >> > >> > Claudio >> > >> > >> >> >> >> /** >> >> =C2=A0* semigroup is an algebraic structure consisting of a set toget= her >> >> with an associative binary operation. >> >> =C2=A0*/ >> >> interface Semigroup >> >> { >> >> >> >> =C2=A0 =C2=A0 E append( E s1, E s2 ); >> >> >> >> } >> >> >> >> /** >> >> =C2=A0* A {@link Monoid} is a {@link Semigroup} with an identity valu= e. >> >> =C2=A0*/ >> >> public interface Monoid >> >> =C2=A0 =C2=A0 extends Semigroup >> >> { >> >> >> >> =C2=A0 =C2=A0E identity(); >> >> >> >> =C2=A0 =C2=A0E 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 >> >> =C2=A0wrote: >> >>> >> >>> 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 t= he >> >>>>> 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 result= s. >> >>>> >> >>>> sounds it would be better if you implement that stuff in a branch t= o >> >>>> keep both implementations, IMHO >> >>> >> >>> >> >>> sure :) >> >>> >> >>> >> >>>>> =C2=A0* with the current approach: one interface for edge-weighted= graphs >> >>>>> =C2=A0 (EdgeWeightedGraph, renaming the current WeightedGraph?), o= ne for >> >>>>> =C2=A0 vertex-weighted graphs (VertexWeightedGraph) and maybe even= one for >> >>>>> =C2=A0 weights on both edges and vertices (EdgeAndVertexWeightedGr= aph?) -- >> >>>>> =C2=A0 not to talk about their counterparts with labels, etc; >> >>>>> =C2=A0* with the proposed approach: a Graph would implement >> >>>>> =C2=A0 HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe = also >> >>>>> =C2=A0 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 dr= op >> >>> "WeightedEdge" and so on: one interface in, one out. >> >>> >> >>> Or we could even save both approaches as alternative implementations= . >> >>> That >> >>> is: >> >>> >> >>> =C2=A0* a set of interfaces: e.g. HasWeightedEdges#getWeight(edge), >> >>> =C2=A0 HasWeightedVertices#getWeight(vertex), etc. >> >>> =C2=A0* #1 implementation with external properties: the graph keeps = the >> >>> =C2=A0 mapping between edge/vertex and weight, so that any type can = be used >> >>> =C2=A0 for edges/vertices >> >>> =C2=A0* #2 classical implementation: we keep markers like WeightedEd= ge and >> >>> =C2=A0 WeightedVertex but only the graph knows about them. algorithm= s keep >> >>> =C2=A0 asking the graph for weights of edges/vertices, and the graph= in >> >>> =C2=A0 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 >> >>>> =C2=A0 =C2=A0wrote: >> >>>>> >> >>>>> Hi, >> >>>>> >> >>>>> >> >>>>>>> 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? >> >>>>>> >> >>>>>> that would imply that Graph implementations have to implement >> vertices >> >>>>>> and/or edges metadata indexing, that would be anyway less perform= ant >> >>>>>> than accessing directly on metadata contained in current node/arc= - >> >>>>>> just count the number of time you should have to touch the adapte= d >> >>>>>> 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 result= s. >> >>>>> >> >>>>> >> >>>>>>> We could externalize all different graph properties to appropria= te >> >>>>>>> interfaces (HasWeightsOnEdges, HasLabelsOnVertices, etc) and the= n >> >>>>>>> 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 wou= ld >> >>>>>> proliferate like pollen during Spring, users - and devs - would g= et >> >>>>>> 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: >> >>>>> >> >>>>> =C2=A0* with the current approach: one interface for edge-weighted= graphs >> >>>>> =C2=A0 (EdgeWeightedGraph, renaming the current WeightedGraph?), o= ne for >> >>>>> =C2=A0 vertex-weighted graphs (VertexWeightedGraph) and maybe even= one for >> >>>>> =C2=A0 weights on both edges and vertices (EdgeAndVertexWeightedGr= aph?) -- >> >>>>> =C2=A0 not to talk about their counterparts with labels, etc; >> >>>>> =C2=A0* with the proposed approach: a Graph would implement >> >>>>> =C2=A0 HasWeightsOnEdges and/or HasWeightsOnVertices -- and maybe = also >> >>>>> =C2=A0 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 =C2=A0extends Zero and Semigrou= p - >> given >> >>>>>> the use inside graph math, Zero#zero and Semigroup#append can be >> moved >> >>>>>> directly to Monoid and rename it as WeightOperation - does it rem= ind >> >>>>>> 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 i= s, >> a >> >>>>> Monoid representing the sum operation. "WeightOperation" sounds mo= re >> >>>>> like >> >>>>> a >> >>>>> general "container" which can include Addition, Comparator, and ma= ybe >> >>>>> in >> >>>>> the >> >>>>> near future Multiplication or who knows what -- which again is pre= tty >> >>>>> 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 >> >>>>>> =C2=A0 =C2=A0 =C2=A0wrote: >> >>>>>>> >> >>>>>>> Hi, >> >>>>>>> >> >>>>>>> >> >>>>>>>> The weights can be external, too. =C2=A0It's only a function fr= om edge >> to >> >>>>>>>> weight. =C2=A0Your algorithm can take a function for its weight= s. =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 >> >>>>>>> edges >> >>>>>>> is >> >>>>>>> moved to the containing graph? >> >>>>>>> >> >>>>>>> We could externalize all different graph properties to appropria= te >> >>>>>>> interfaces (HasWeightsOnEdges, HasLabelsOnVertices, etc) and the= n >> >>>>>>> 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" >> >>>>>>>> =C2=A0wrote: >> >>>>>>>> >> >>>>>>>>> Having weights on vertices is quite common. =C2=A0Consider any >> >>>>>>>>> probability >> >>>>>>>>> transition network. =C2=A0The weight on each node is the proba= bility >> 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> =C2=A0 =C2=A0 =C2=A0 =C2=A0wrote: >> >>>>>>>>> >> >>>>>>>>>> Hi all, >> >>>>>>>>>> >> >>>>>>>>>> =C2=A0Claudio is aware also about algorithms where weights ar= e >> >>>>>>>>>> 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 m= ore >> >>>>>>>>> >> >>>>>>>>> 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: >> >>>>>>>>>> >> >>>>>>>>>> =C2=A0* the graph itself is extremely simple and naked: no >> >>>>>>>>>> weights/labels >> >>>>>>>>>> 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, etc >> >>>>>>>>>> etc). >> >>>>>>>>>> >> >>>>>>>>>> He motivated the idea with a "personal use case": often graph= s >> 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 >> >>>>>> >> >>>>> -- >> >>>>> 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 >> >>>> >> >>> -- >> >>> 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 >> >> >> > >> > -- >> > 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