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 <squar...@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: squar...@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-unsubscr...@commons.apache.org>
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>
--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle
University
mailto: turingatemyhams...@gmail.com
gchat: turingatemyhams...@gmail.com
msn: matthew_poc...@yahoo.co.uk
irc.freenode.net: drdozer
skype: matthew.pocock
tel: (0191) 2566550
mob: +447535664143
