subject:"\[Graph\] Weighted as an interface"

Re: [Graph] Weighted as an interface

2011-12-06 Thread Simone Tripodi

Hola Claudio!

for all algorithms implemented in the `shortestpath` package (A*,
Dijkstra, Bellmann-Ford, ...), I didn't have the need to add new
specific methods for {{WeightedGraph}}es since that interface was used
more as a marker - a direct graph, which edges are weighted (granted
by generics), satisfies the algos input as well.

As domain expert you maybe know advanced algorithms that require more
assumptions on the input graph, so any suggestion is welcome!

Simo

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/



On Tue, Dec 6, 2011 at 10:11 AM, Claudio Squarcella
 wrote:
> Hi,
>
>
 Moreover, I start having the feeling the {{WeightedGraph}} is a
 useless interface: it is enough marking the vertices/edges as weighted
 depending on the problem... or not? At the end of the day,
 {{WeightedGraph}} does nothing than having the the edges marked as
 weighted, so Dijkstra signature changed as:

 >>> WE>>    WeightedPath    findShortestPath( G graph,  V source, V
 target )

 still define well the input type, a graph wich relations are directed
 edges and edges are weighted... WDYT?
>>>
>>>
>>> I agree, as long as there are no specific features of the graph that are
>>> independent on its vertices and edges.
>
>
> quoting myself here: actually I think {{WeightedGraph}} should *not* go away
> if it makes sense to add methods to it later (e.g. to get the total weight).
> But changing the signature of the methods is still a valid idea, as it
> allows for a more fine-grained expressiveness on the input. Right?
>
> Claudio
>
>
>>> Another advantage: I won't bother
>>> later to add more speficic interfaces like {{EdgeWeightedGraph}} or
>>> {{VertexWeightedGraph}} ;-)
>>>
>> +1, please include that in a separate issue!
>> All the best, have a nice day!
>> Simo
>>
>>> Ciao,
>>> Claudio
>>
>> http://people.apache.org/~simonetripodi/
>> http://simonetripodi.livejournal.com/
>> http://twitter.com/simonetripodi
>> http://www.99soft.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
> E-mail address: squar...@dia.uniroma3.it
> Phone: +39-06-57333215
> Fax: +39-06-57333612
> http://www.dia.uniroma3.it/~squarcel
>
>
> -
> 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

Re: [Graph] Weighted as an interface

2011-12-06 Thread Claudio Squarcella


Hi,


Moreover, I start having the feeling the {{WeightedGraph}} is a
useless interface: it is enough marking the vertices/edges as weighted
depending on the problem... or not? At the end of the day,
{{WeightedGraph}} does nothing than having the the edges marked as
weighted, so Dijkstra signature changed as:

>WeightedPathfindShortestPath( G graph,  V source, V
target )

still define well the input type, a graph wich relations are directed
edges and edges are weighted... WDYT?


I agree, as long as there are no specific features of the graph that are
independent on its vertices and edges.


quoting myself here: actually I think {{WeightedGraph}} should *not* go 
away if it makes sense to add methods to it later (e.g. to get the total 
weight). But changing the signature of the methods is still a valid 
idea, as it allows for a more fine-grained expressiveness on the input. 
Right?


Claudio



Another advantage: I won't bother
later to add more speficic interfaces like {{EdgeWeightedGraph}} or
{{VertexWeightedGraph}} ;-)


+1, please include that in a separate issue!
All the best, have a nice day!
Simo


Ciao,
Claudio

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.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
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel


-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

Re: [Graph] Weighted as an interface

2011-12-05 Thread Simone Tripodi

Hi Claudio,
so nice to see you are already deep in the spirit of the project! :)

> As for my suggestion on types, should I go for {{Weighted Number>}}?
> Note that I am also concerned about domain-specific requirements (e.g. all
> weights must be positive) that I would like to see implemented as
> "statically" as possible in the code. {{Number}} should give us quite enough
> freedom in that direction (e.g. one could later extend it with something
> like {{PositiveInteger}}).
>
> A more platonic alternative would be to have an abstract type of weight
> which 1. is comparable and 2. can be aggregated in some way (e.g. the weight
> of a path is the sum of weights of its edges). But I am probably going too
> far...
>
>

I think that is a valid idea, please don't stop and explore more! ;)

>>
>> Moreover, I start having the feeling the {{WeightedGraph}} is a
>> useless interface: it is enough marking the vertices/edges as weighted
>> depending on the problem... or not? At the end of the day,
>> {{WeightedGraph}} does nothing than having the the edges marked as
>> weighted, so Dijkstra signature changed as:
>>
>> > WE>>  WeightedPath  findShortestPath( G graph,  V source, V
>> target )
>>
>> still define well the input type, a graph wich relations are directed
>> edges and edges are weighted... WDYT?
>
>
> I agree, as long as there are no specific features of the graph that are
> independent on its vertices and edges. Another advantage: I won't bother
> later to add more speficic interfaces like {{EdgeWeightedGraph}} or
> {{VertexWeightedGraph}} ;-)
>

+1, please include that in a separate issue!
All the best, have a nice day!
Simo

> Ciao,
> Claudio

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

Re: [Graph] Weighted as an interface

2011-12-05 Thread Claudio Squarcella


Hi,

thanks to both for your words! Please find comments below.

On 05/12/2011 10:01, Simone Tripodi wrote:

Hi Claudio,
what a pleasant surprise! :) I was hoping commons-graph would have
caught the interest of researchers on that field, I'm really happy you
would like to contribute!

I agree with your observations, please fill new issues on JIRA[1] and
feel free to provide patches, I'll process them ASAP :)


Alright, I'll find time later this week.

As for my suggestion on types, should I go for {{WeightedNumber>}}?
Note that I am also concerned about domain-specific requirements (e.g. 
all weights must be positive) that I would like to see implemented as 
"statically" as possible in the code. {{Number}} should give us quite 
enough freedom in that direction (e.g. one could later extend it with 
something like {{PositiveInteger}}).


A more platonic alternative would be to have an abstract type of weight 
which 1. is comparable and 2. can be aggregated in some way (e.g. the 
weight of a path is the sum of weights of its edges). But I am probably 
going too far...




Moreover, I start having the feeling the {{WeightedGraph}} is a
useless interface: it is enough marking the vertices/edges as weighted
depending on the problem... or not? At the end of the day,
{{WeightedGraph}} does nothing than having the the edges marked as
weighted, so Dijkstra signature changed as:

>  WeightedPath  findShortestPath( G graph,  V source, V
target )

still define well the input type, a graph wich relations are directed
edges and edges are weighted... WDYT?


I agree, as long as there are no specific features of the graph that are 
independent on its vertices and edges. Another advantage: I won't bother 
later to add more speficic interfaces like {{EdgeWeightedGraph}} or 
{{VertexWeightedGraph}} ;-)


Ciao,
Claudio



Looking forward for your contributions, can't wait for them! :)
Simo

[1] https://issues.apache.org/jira/browse/SANDBOX

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/



On Mon, Dec 5, 2011 at 2:00 AM, James Carman  wrote:

Welcome!  Contributions (and the contributor) are always welcome.  In my
past life, I did quite a bit of graph programming to solve "business"
problems.  We used yfiles, though.  I hope to get around to playing with
[graph] someday too.  Please do submit a patch!
On Dec 4, 2011 6:43 PM, "Claudio Squarcella"
wrote:


Hello,

I have been reading the source in the past days and I found that the
concept of "weight" (e.g. weighted edge, graph, etc) could benefit from a
bit of abstraction.

The basic idea would be to have an interface called Weighted with an
obvious method getWeight(). Changes in the code would easily derive from
that. As a side effect it would be easy to implement new stuff like
weighted vertices: not as glorious as weighted edges, but still needed in
some problems (e.g. all-pairs bottleneck paths) and therefore desirable for
a general purpose graph API.

One step further. A weight is not necessarily a double: in some cases not
even a number, but rather a "comparable" of some sort. So I would suggest
to make use of generics in some way, possibly the smartest. Suggestions are
welcome :-)

If my thoughts meet some interest I will work on a patch.

Ciao,
Claudio


P.S.
I am a first-timer here, so what follows is a short introduction.
I am doing a PhD in Graph Drawing and Information Visualization. I always
looked for a standard, unified way to represent and handle graphs when
developing prototypes. So my interest in this project is quite natural, and
I am willing to help and see it become a robust project.

--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~**squarcel


--**--**-
To unsubscribe, e-mail: 
dev-unsubscribe@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
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel


-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

Re: [Graph] Weighted as an interface

2011-12-05 Thread Simone Tripodi

Hi Claudio,
what a pleasant surprise! :) I was hoping commons-graph would have
caught the interest of researchers on that field, I'm really happy you
would like to contribute!

I agree with your observations, please fill new issues on JIRA[1] and
feel free to provide patches, I'll process them ASAP :)

Moreover, I start having the feeling the {{WeightedGraph}} is a
useless interface: it is enough marking the vertices/edges as weighted
depending on the problem... or not? At the end of the day,
{{WeightedGraph}} does nothing than having the the edges marked as
weighted, so Dijkstra signature changed as:

> WeightedPath findShortestPath( G graph,  V source, V
target )

still define well the input type, a graph wich relations are directed
edges and edges are weighted... WDYT?

Looking forward for your contributions, can't wait for them! :)
Simo

[1] https://issues.apache.org/jira/browse/SANDBOX

http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/



On Mon, Dec 5, 2011 at 2:00 AM, James Carman  wrote:
> Welcome!  Contributions (and the contributor) are always welcome.  In my
> past life, I did quite a bit of graph programming to solve "business"
> problems.  We used yfiles, though.  I hope to get around to playing with
> [graph] someday too.  Please do submit a patch!
> On Dec 4, 2011 6:43 PM, "Claudio Squarcella" 
> wrote:
>
>> Hello,
>>
>> I have been reading the source in the past days and I found that the
>> concept of "weight" (e.g. weighted edge, graph, etc) could benefit from a
>> bit of abstraction.
>>
>> The basic idea would be to have an interface called Weighted with an
>> obvious method getWeight(). Changes in the code would easily derive from
>> that. As a side effect it would be easy to implement new stuff like
>> weighted vertices: not as glorious as weighted edges, but still needed in
>> some problems (e.g. all-pairs bottleneck paths) and therefore desirable for
>> a general purpose graph API.
>>
>> One step further. A weight is not necessarily a double: in some cases not
>> even a number, but rather a "comparable" of some sort. So I would suggest
>> to make use of generics in some way, possibly the smartest. Suggestions are
>> welcome :-)
>>
>> If my thoughts meet some interest I will work on a patch.
>>
>> Ciao,
>> Claudio
>>
>>
>> P.S.
>> I am a first-timer here, so what follows is a short introduction.
>> I am doing a PhD in Graph Drawing and Information Visualization. I always
>> looked for a standard, unified way to represent and handle graphs when
>> developing prototypes. So my interest in this project is quite natural, and
>> I am willing to help and see it become a robust project.
>>
>> --
>> Claudio Squarcella
>> PhD student at Roma Tre University
>> E-mail address: squar...@dia.uniroma3.it
>> Phone: +39-06-57333215
>> Fax: +39-06-57333612
>> http://www.dia.uniroma3.it/~**squarcel
>>
>>
>> --**--**-
>> To unsubscribe, e-mail: 
>> dev-unsubscribe@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

Re: [Graph] Weighted as an interface

2011-12-04 Thread James Carman

Welcome!  Contributions (and the contributor) are always welcome.  In my
past life, I did quite a bit of graph programming to solve "business"
problems.  We used yfiles, though.  I hope to get around to playing with
[graph] someday too.  Please do submit a patch!
On Dec 4, 2011 6:43 PM, "Claudio Squarcella" 
wrote:

> Hello,
>
> I have been reading the source in the past days and I found that the
> concept of "weight" (e.g. weighted edge, graph, etc) could benefit from a
> bit of abstraction.
>
> The basic idea would be to have an interface called Weighted with an
> obvious method getWeight(). Changes in the code would easily derive from
> that. As a side effect it would be easy to implement new stuff like
> weighted vertices: not as glorious as weighted edges, but still needed in
> some problems (e.g. all-pairs bottleneck paths) and therefore desirable for
> a general purpose graph API.
>
> One step further. A weight is not necessarily a double: in some cases not
> even a number, but rather a "comparable" of some sort. So I would suggest
> to make use of generics in some way, possibly the smartest. Suggestions are
> welcome :-)
>
> If my thoughts meet some interest I will work on a patch.
>
> Ciao,
> Claudio
>
>
> P.S.
> I am a first-timer here, so what follows is a short introduction.
> I am doing a PhD in Graph Drawing and Information Visualization. I always
> looked for a standard, unified way to represent and handle graphs when
> developing prototypes. So my interest in this project is quite natural, and
> I am willing to help and see it become a robust project.
>
> --
> Claudio Squarcella
> PhD student at Roma Tre University
> E-mail address: squar...@dia.uniroma3.it
> Phone: +39-06-57333215
> Fax: +39-06-57333612
> http://www.dia.uniroma3.it/~**squarcel
>
>
> --**--**-
> To unsubscribe, e-mail: 
> dev-unsubscribe@commons.**apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>

[Graph] Weighted as an interface

2011-12-04 Thread Claudio Squarcella


Hello,

I have been reading the source in the past days and I found that the 
concept of "weight" (e.g. weighted edge, graph, etc) could benefit from 
a bit of abstraction.


The basic idea would be to have an interface called Weighted with an 
obvious method getWeight(). Changes in the code would easily derive from 
that. As a side effect it would be easy to implement new stuff like 
weighted vertices: not as glorious as weighted edges, but still needed 
in some problems (e.g. all-pairs bottleneck paths) and therefore 
desirable for a general purpose graph API.


One step further. A weight is not necessarily a double: in some cases 
not even a number, but rather a "comparable" of some sort. So I would 
suggest to make use of generics in some way, possibly the smartest. 
Suggestions are welcome :-)


If my thoughts meet some interest I will work on a patch.

Ciao,
Claudio


P.S.
I am a first-timer here, so what follows is a short introduction.
I am doing a PhD in Graph Drawing and Information Visualization. I 
always looked for a standard, unified way to represent and handle graphs 
when developing prototypes. So my interest in this project is quite 
natural, and I am willing to help and see it become a robust project.


--
Claudio Squarcella
PhD student at Roma Tre University
E-mail address: squar...@dia.uniroma3.it
Phone: +39-06-57333215
Fax: +39-06-57333612
http://www.dia.uniroma3.it/~squarcel


-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

Re: [Graph] Weighted as an interface

Re: [Graph] Weighted as an interface

Re: [Graph] Weighted as an interface

Re: [Graph] Weighted as an interface

Re: [Graph] Weighted as an interface

Re: [Graph] Weighted as an interface

[Graph] Weighted as an interface

7 matches

Site Navigation

Mail list logo

Footer information