commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: [Graph] On graph weight type(s)
Date Fri, 23 Dec 2011 08:47:54 GMT
Hi Matthew!

at a first looks it is really interesting, just give me the time to
digest because at the same time I had the feeling of a little
over-engineering activity, I am worried that "5 minutes to run" users
would find it not so immediate.

Thanks for providing stuff to learn from!
All the best,
-Simo

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



On Thu, Dec 22, 2011 at 6:25 PM, Matthew Pocock
<turingatemyhamster@gmail.com> wrote:
> Hi,
>
> Just thought I'd throw something out here. My experience is that I often
> take the same graph (as in the exact same data, same objects) but at
> different times want to use different weights. So, rather than having Edge
> extend Weighted<W>, I'd factor weights out into their own interface:
>
> /**
>  * An edge weight function.
>  *
>  * note: perhaps this should more generally just be a Function1<A, B>, if
> we have such a thing handy.
>  *
>  * @tparam E  edge type
>  * @tparam W weight type
>  */
> public interface EdgeWeight<E, W> {
>  public W getWeight(E: Edge);
> }
>
> /**
>  * A combination of a monoid and comparator that satisfy monotinicity of
> the addition operation with respect to the comparator.
>  *
>  * ∀a: m.compare(m.zero, a) <= 0
>  * ∀a,b: m.compare(a, m.append(a, b)) <= 0
>  */
> public interface Monotonic<W> extends Monoid<W>, Comparator<W>
>
> Also, some algorithms calculate all shortest paths at once, while others
> calculate them individually and independently. It's probably even possible
> to calculate some lazily. So, the interfaces for shortest paths should
> decouple setting up a strategy for all shortest paths from an object that
> can be used to fetch a specific shortest path.
>
> /**
>  * An algorithm for finding shortest paths between vertices of a graph,
> given some edge weighting function and
>  * a well-behaved combinator for edges between connected vertices.
>  */
> public interface ShortestPathFunction<V extends Vertex, E extends Edge<E>,
> G extends DirectedGraph<V, E>, W> {
>  public ShortestPathResult<V, E, W> makeResult(G graph, EdgeWeight<E, W>
> weighting, Monotonic<W> combineWith);
> }
>
> /**
>  * The shortest paths between vertices in a graph.
>  */
> public interface ShortestPathResult<V extends Vertex, E extends Edge<E>, W>
> {
>  public WeightedPath<V, E, W> findShortestPath(V source, V target);
> }
>
> How does that look? You can then have standard implementations of these
> things in some static utility class or a spring-friendly resource. The
> brute-force algorithms that compute all paths at once would do all the work
> in makeResult() and simply store this in some state within the returned
> ShortestPathResult. Those that calculate individual pairs on the fly (or
> all shortest paths from some vertex) would capture state in makeResult()
> and perform the actual computation in findShortestPath().
>
> Matthew
>
> On 22 December 2011 16:39, Claudio Squarcella <squarcel@dia.uniroma3.it>wrote:
>
>> Hi,
>>
>>
>>  I highly appreciated the last contributions (thanks guys!) but I also
>>> agree on this point, so let's start from the end.
>>> I think that, no matter what underlying structure we come up with, the
>>> user should be able to specify e.g. a weighted edge with something like
>>>
>>> public class MyEdge implements Edge, Weighted<Double> { ... }
>>>
>>> and be able to immediately use it as an input for all the algorithms,
>>> without extra steps required. So the average user is happy, while "graph
>>> geeks" can dig into advanced capabilities and forge their personalized
>>> weights :)
>>> I hope we all agree on this as a first step. Complexity comes after.
>>>
>>> I'll take my time as well to re-think.
>>>
>>
>> I did think and code a bit more. First of all please take a look at the
>> updated code: Weighted<W> is an interface (weight W can be any type) and
>> all the algorithms require edges to implement Weighted<Double> for now --
>> we did not break it that much ;)
>>
>> About the "HasProperty-vs-Property" question (as in Comparable vs
>> Comparator, MonoidElement vs Monoid, etc) I would go for the second one
>> only. That is, external classes handle all operations on weights. Downside:
>> the # of method parameters would increase linearly with the number of
>> properties, but I can live with that (how many properties would weights
>> have anyway?). On the other hand we have a neat interface for each
>> property/class (Zero, Semigroup, Monoid, Ordering or Comparator, etc) and
>> one clean, generic implementation for each algorithm. Dijkstra's signature
>> becomes something like:
>>
>> public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends
>> DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G graph,
V
>> source, V target, Monoid<W> weightMonoid, Comparator<W> weightComparator
)
>>
>> Scary uh? But wait, default implementations for Double, Integer, etc. are
>> way easier. E.g. Dijkstra's shortcut for Double:
>>
>> public static <V extends Vertex, WE extends WeightedEdge<Double>, G
>> extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> findShortestPath(
>> G graph, V source, V target )
>> {
>>    return findShortestPath(graph, source, target, new DoubleMonoid(), new
>> DoubleComparator());
>> }
>>
>> where DoubleMonoid and DoubleComparator are part of the library.
>>
>>
>> If you guys are fine with this, I'm ready to try and patch [graph] with a
>> Christmas gift :)
>> Claudio
>>
>>
>> --
>> Claudio Squarcella
>> PhD student at Roma Tre University
>> E-mail address: squarcel@dia.uniroma3.it
>> Phone: +39-06-57333215
>> Fax: +39-06-57333612
>> http://www.dia.uniroma3.it/~**squarcel<http://www.dia.uniroma3.it/~squarcel>
>>
>>
>> ------------------------------**------------------------------**---------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<dev-unsubscribe@commons.apache.org>
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> --
> Dr Matthew Pocock
> Integrative Bioinformatics Group, School of Computing Science, Newcastle
> University
> mailto: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143

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


Mime
View raw message