How can Go solve a problem that is well served by multiple inheritance?
Mark Summerfield
Here is a link to a simple but effective implementation of Dijkstra's
algorithm:
http://rosettacode.org/wiki/Maze_solving#Python
My understanding is that this implemenation is O(n * n), so only really
good up to 10K nodes. The reason for the slowness is that it searches
for everything over and over again (for the min node, for its
neighbors). Clearly it would be v. easy to convert this to Go, but that
would still have the quadratic time complexity.
At the end of this email is an Eiffel implementation from Jeff
Kingston's Algorithms and data structures book that is O(n log n + m)
(if used with the right graph and priority queue implementations),
preceded by some notes, including a negative claim about Go indicated by
*s.
In the Eiffel implementation a key aspect to its efficiency is multiple
inheritance: this allows objects to access things in a way that Go's
embedding doesn't seem to support.
So is there a nice Go-ish way to do this? Does the claim hold up?
------------------------------------------------------------
Here are some notes from Jeff Kingston plus his Eiffel Dijkstra
implementation.
DIGRAPH_ALGS_VERTEX is simultaneously a vertex of a graph and an element
of a priority queue; it inherits these two classes:
DIGRAPH_LISTS_VERTEX
PRIQUEUE_EXTENDED_FIBHEAP_ENTRY
The other types are
vertex_type: DIGRAPH_ALGS_VERTEX;
edge_type: DIGRAPH_ALGS_EDGE;
priqueue_extended_type: DIGRAPH_ALGS_PRIQUEUE_EXTENDED;
The whole point is in variables v and w. The line
v := q.delete_min
extracts a smallest element from priority queue q, but q has been
generically instantiated so that the type of its entries is
DIGRAPH_ALGS_VERTEX, not merely type PRIQUEUE_EXTENDED_FIBHEAP_ENTRY
(this requires constrained genericity) so it can be passed to
g.first_edge(v) and the other graph operations. Conversely, even
though w is obtained from
w := g.end_point(e);
(the endpoint of edge e in graph g), g has also been generically
instantiated so that its vertices have type DIGRAPH_ALGS_VERTEX,
and so you can put w into the priority queue:
q.insert(w) or q.decrease_key(w, v.distance + e.cost)
depending on whether it is already in the priority queue or not.
So v and w are simultaneously graph vertices and priority queue
elements. No casts, and static type safety throughout.
* Of course, I am not claiming that you can't implement Dijkstra's
* algorithm in Go. The claim is that you can't take two types, one for
* directed graphs and one for priority queues, and use them, without
* rewriting their methods, to produce a version of Dijkstra's algorithm
* which is free of casts or other extraneous rubbish, as this version
* is:
dijkstra(g: like digraph_type; a: like vertex_type) is
local
q: like priqueue_extended_type;
v, w: like vertex_type;
e: like edge_type;
do
from v := g.first_vertex until g.nil_vertex(v) loop
v.put_visited(false);
v := g.next_vertex(v);
end;
a.put_visited(true);
a.put_parent(v); -- a nil vertex
a.put_distance(0);
from !!q.make; q.insert(a) until q.empty loop
v := q.delete_min;
from e := g.first_edge(v) until g.nil_edge(e) loop
w := g.end_point(e);
if not w.visited then
w.put_visited(true);
w.put_distance(v.distance + e.cost);
w.put_parent(v);
q.insert(w)
elseif v.distance + e.cost < w.distance then
w.put_parent(v);
q.decrease_key(w, v.distance + e.cost)
end
e := g.next_edge(v, e)
end
end;
end;
------------------------------------------------------------
Thanks!
--
Mark Summerfield, Qtrac Ltd, www.qtrac.eu
C++, Python, Qt, PyQt - training and consultancy
"Programming in Python 3" - ISBN 0321680561
http://www.qtrac.eu/py3book.html
Andreas Krennmair
> In the Eiffel implementation a key aspect to its efficiency is multiple
> inheritance: this allows objects to access things in a way that Go's
> embedding doesn't seem to support.
You can embed multiple types in a struct. Unless these multiple types
conflict on the interfaces they implement, I see no problem with that.
Have you even attempted a Go implementation?
Regards,
Andreas
Mark Summerfield
Unfortunately, that completely misses the point.
I know that you can do this:
type A struct { data int }
func (a A) MethodA() int { return a.data * 2 }
type B struct { data float64 }
func (b B) MethodB() float64 { return b.data / 3 }
type AB struct { A B }
var ab AB
ab.MethodA()
ab.MethodB()
However, the Eiffel Dijkstra implementation needs to do something subtly
different (which is why it uses multiple inheritance).
The issue is explained in the notes at the end of my original email.
--
Mark Summerfield, Qtrac Ltd, www.qtrac.eu
C++, Python, Qt, PyQt - training and consultancy
"Advanced Qt Programming" - ISBN 0321635906
http://www.qtrac.eu/aqpbook.html
Jan Mercl
However, the Eiffel Dijkstra implementation needs to do something subtly
different (which is why it uses multiple inheritance).
The issue is explained in the notes at the end of my original email.
* directed graphs and one for priority queues, and use them, without
* rewriting their methods, to produce a version of Dijkstra's algorithm
* which is free of casts or other extraneous rubbish, as this version
* is:
John Arbash Meinel
Hash: SHA1
...
> Unfortunately, that completely misses the point.
>
> I know that you can do this:
>
> type A struct { data int } func (a A) MethodA() int { return a.data
> * 2 } type B struct { data float64 } func (b B) MethodB() float64 {
> return b.data / 3 } type AB struct { A B }
>
> var ab AB ab.MethodA() ab.MethodB()
>
> However, the Eiffel Dijkstra implementation needs to do something
> subtly different (which is why it uses multiple inheritance).
>
> The issue is explained in the notes at the end of my original
> email.
>
Go does not have generics, so you can't implement a generic "priority
queue" that uses an abstract type for its storage structure.
You could do it with interfaces, which would provide abstraction, but
is approximately at the level of virtual functions.
type PriorityQueueItem interface {
Value() int
}
type PriorityQueue interface {
AddItem(PriorityQueueItem i)
PopHighest() PriorityQueueItem
}
and then
type DijkstrasItem interface {
Distance(DijkstrasItem other) int
}
Then your concrete type can implement both interfaces, and you'll have
one memory region per node that is both in a PriorityQueue and in a
DijkstrasSearch.
John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iEYEARECAAYFAk5zLwEACgkQJdeBCYSNAAPd5gCggxJELg8EiZBhQITvEHIL9Q+4
poUAn3gekD0R8Sl2yaAd7Pg74/oGcO17
=cuYF
-----END PGP SIGNATURE-----
roger peppe
get exactly what you want with Go.
for reference purposes, here's an implementation of Dijkstra's in Go,
(derived from http://code.google.com/p/gowire/source/browse/wire/convert.go#86
which does slightly more).
it isn't generic, but it could be made so, by making node an interface
with an Arcs method, which probably would not be as efficient
as your Eiffel code above.
one difference is that this version is thread-safe - paths can
be computed concurrently - which the Eiffel version is not.
func shortestPath(n0, n1 *node) *mark {
q := markHeap{&mark{node: n0, dist: 0}}
marks := map[*node]*mark{n0: q[0]}
for len(q) > 0 {
u := q[0]
if u.node == n1 {
return u
}
heap.Remove(&q, 0)
for _, a := range u.node.arc {
if v := marks[a.dst]; v != nil {
if u.dist+1 < v.dist {
heap.Remove(&q, v.index)
v.dist = u.dist + 1
v.arc = a
v.previous = u
heap.Push(&q, v)
}
} else {
v := &mark{node: a.dst, dist: u.dist + 1, previous: u, arc: a}
heap.Push(&q, v)
marks[a.dst] = v
}
}
}
return nil
⚛
> However, the Eiffel Dijkstra implementation needs to do something subtly
> different (which is why it uses multiple inheritance).
As far as I understand, the key distinction (in context of your
example) between Eiffel and Go is in the so-called generic types.
Eiffel has them, Go doesn't.
In other words, what I am trying to say here is that the issue in your
example is being wrongly attributed to the absence of multiple
inheritance in Go. I think it should be attributed to the absence of
generic types in Go.
The absence of generic types in Go means that it is impossible to
express the concept "Priority queue of DIGRAPH_ALGS_VERTEX". In Go, it
is only possible to express "Priority queue of QueueItem", where
QueueItem is a Go type. Because of this, after extracting an item from
the queue, there would need to be an explicit conversion from a
QueueItem to a DIGRAPH_ALGS_VERTEX. This has nothing to do with
multiple inheritance - because adding multiple inheritance to Go would
*not* erase this explicit from the Go code.
The "code free of casts" you are requesting seems to be a consequence
of Eiffel's ability to perform simple type computations at compile-
time.
⚛
> This has nothing to do with
> multiple inheritance - because adding multiple inheritance to Go would
> *not* erase this explicit from the Go code.
Mark Summerfield
Jan Mercl <jan....@nic.cz> wrote:
> On Friday, September 16, 2011 12:51:37 PM UTC+2, Mark wrote:
> >
> > However, the Eiffel Dijkstra implementation needs to do something
> > subtly different (which is why it uses multiple inheritance).
> >
> Please try to explain the subtly different thing, I didn't get it.
> See bellow.
It is hard to explain! Hopefully this will help:
In the Dijkstra algorithm, the library functions for node-of-graph
are pretty trivial, but the library functions for
element-of-priority-queue are far from trivial. We don't want to
have to copy them, or even look at them. We want them to remain
permanently buried in the library.
In Eiffel (and C++), which have multiple inheritance, this is doable.
In Go, which does not have inheritance, it can be done if you use
delegation. But delegation will not work on the Dijkstra example,
because, in general, when you call a TypeA function from TypeABC
implemented using delegation, what it receives is not the original
variable of type TypeABC, but rather a TypeA, and there is no way
back from there to the original variable. And you need this in the
Dijkstra example. (Personally, I really like this feature, but it is
disadvantageous in this one case.)
In summary, you can express the required type structure in Go, but
you cannot build an implementation that re-uses the library
functions. (Well, actually you can, but you need two objects for
each node, one holding its node state, and one holding its priority
queue state; each has to point to the other. This is the usual
simulation of multiple inheritance in languages that don't have it.
[snip]
> * The claim is that you can't take two types, one for
> * directed graphs and one for priority queues, and use them, without
> * rewriting their methods, to produce a version of Dijkstra's
> algorithm
> * which is free of casts or other extraneous rubbish, as this version
> * is:
>
> I don't know Eiffel, unfortunately, I don't understand the claim.
> Maybe it could be useful to write a Go version and show where it runs
> in a problem. Then someone might want to try and bring an
> improvement/solution, if it exists.
Roger Peppe has shown us a v. interesting Go version.
--
Mark Summerfield, Qtrac Ltd, www.qtrac.eu
C++, Python, Qt, PyQt - training and consultancy
Jan Mercl
It is hard to explain! Hopefully this will help:
In the Dijkstra algorithm, the library functions for node-of-graph
are pretty trivial, but the library functions for
element-of-priority-queue are far from trivial. We don't want to
have to copy them, or even look at them. We want them to remain
permanently buried in the library.In Eiffel (and C++), which have multiple inheritance, this is doable.
In Go, which does not have inheritance, it can be done if you use
delegation. But delegation will not work on the Dijkstra example,
because, in general, when you call a TypeA function from TypeABC
implemented using delegation, what it receives is not the original
variable of type TypeABC, but rather a TypeA, and there is no way
back from there to the original variable.
And you need this in the
Dijkstra example. (Personally, I really like this feature, but it is
disadvantageous in this one case.)In summary, you can express the required type structure in Go, but
you cannot build an implementation that re-uses the library
functions.
(Well, actually you can, but you need two objects for
each node, one holding its node state, and one holding its priority
queue state; each has to point to the other. This is the usual
simulation of multiple inheritance in languages that don't have it.
⚛
> On Fri, 16 Sep 2011 04:04:20 -0700 (PDT)
> you cannot build an implementation that re-uses the library
> functions. (Well, actually you can, but you need two objects for
> each node, one holding its node state, and one holding its priority
> queue state; each has to point to the other. This is the usual
> simulation of multiple inheritance in languages that don't have it.
algorithm which is free of casts or other extraneous rubbish". The
only (as in: the only one) issue with Go is that you cannot put the
PriorityQueue and Graph types into separate reusable packages and
expect Go codes using those packages to be free from explicit
conversions (casts).
If you allow explicit conversions (or some other run-time type checks)
in Go code which is pulling elements from the PriorityQueue and from
the Graph, then of course there is no problem to be solved here.
Without the so-called generic types, explicit conversions in the Go
code are inevitable. Neither delegation, nor multiple inheritance, nor
anything else dissimilar to actual generic types (i.e: type
computation at compile-time), can erase those conversions from the Go
code.
Mark Summerfield
⚛ <0xe2.0x...@gmail.com> wrote:
> On Sep 16, 2:31 pm, Mark Summerfield <l...@qtrac.plus.com> wrote:
> > On Fri, 16 Sep 2011 04:04:20 -0700 (PDT)
> > [cut]
> > In summary, you can express the required type structure in Go,
> > but you cannot build an implementation that re-uses the library
> > functions. (Well, actually you can, but you need two objects
> > for each node, one holding its node state, and one holding its
> > priority queue state; each has to point to the other. This is the
> > usual simulation of multiple inheritance in languages that don't
> > have it.
>
> I thought your primary goal was to have "a version of Dijkstra's
> algorithm which is free of casts or other extraneous rubbish". The
> only (as in: the only one) issue with Go is that you cannot put the
> PriorityQueue and Graph types into separate reusable packages and
> expect Go codes using those packages to be free from explicit
> conversions (casts).
No, the primary goal was to be able to take two completely independent
types (in this case priority queue element and vector element) and use
them together without needing to tinker with them.
> If you allow explicit conversions (or some other run-time type checks)
> in Go code which is pulling elements from the PriorityQueue and from
> the Graph, then of course there is no problem to be solved here.
>
> Without the so-called generic types, explicit conversions in the Go
> code are inevitable. Neither delegation, nor multiple inheritance, nor
> anything else dissimilar to actual generic types (i.e: type
> computation at compile-time), can erase those conversions from the Go
> code.
OK!
--
Mark Summerfield, Qtrac Ltd, www.qtrac.eu
C++, Python, Qt, PyQt - training and consultancy
"Programming in Go" - ISBN 0321774639
http://www.qtrac.eu/gobook.html
Kyle Lemons
Russ Cox
> inheritance: this allows objects to access things in a way that Go's
> embedding doesn't seem to support.
I don't think this is a key aspect to its efficiency, nor to
its brevity. It is, however, a key aspect to its multiple
inheritance.
> * Of course, I am not claiming that you can't implement Dijkstra's
> * algorithm in Go. The claim is that you can't take two types, one for
> * directed graphs and one for priority queues, and use them, without
> * rewriting their methods, to produce a version of Dijkstra's algorithm
This question betrays an inheritance-oriented bias: it
assumes that to reuse an algorithm, you have to do it by
inheriting from a type that implements that algorithm. Go
doesn't buy into that. Algorithms are code, not types.
They obviously operate on values that have types, and each
algorithm has requirements it places on the types of values
it can operate on, but in the end, an algorithm is not a
type, nor is it embodied by a type. Algorithms are code, so
it is idiomatic to express them in Go as functions.
Sort is a good example. There are many kinds of sorting
algorithms, but a very common kind is comparison-based,
meaning that the operations it expects to be able to apply
to the data are to compare two elements at arbitrary indices
and perhaps also swap them. The Go sort package defines an
interface, sort.Interface, that must be implemented by any
data that wants to submit itself to this kind of sorting
algorithm:
package sort
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less returns whether the element with index i should sort
// before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
If your type implements sort.Interface, you can sort what it
represents, by passing it to the sort.Sort function - the
actual algorithm. We changed the algorithm recently,
actually, and no one noticed, because the details are hidden
behind this simple signature:
func Sort(data Interface)
So far this doesn't look too different than many languages,
because there is no actual state that Sort must maintain
other than the values themselves. Maybe another language
would choose different methods, but it's about the same.
Heaps are another good example, and where things start to
diverge from inheritance-oriented languages. Instead of
requiring each element that will be stored in a heap to
inherit from some heap-element type, Go's heap package
defines the interface required of a container in order to
apply the heap algorithms to it:
package heap
type Interface interface {
sort.Interface
Push(x interface{})
Pop() interface{}
}
The container needs to be able to do the comparison
operations that sort requires, and it also needs to be able
to push an element onto the end of the underlying array and
to pop an element from the end.
If your container implements those operations, you can call
the heap algorithm operations:
func Pop(h Interface) interface{}
func Push(h Interface, x interface{})
func Remove(h Interface, i int) interface{}
Remove is the interesting operation here: it requires that
you give it the heap index of the element you want to
remove, not the element itself.
In an inheritance-oriented language, you can pass the
element itself because the element type inherits from a
master heap element type that the heap algorithm updates
with its current index every time it moves within the heap.
That has an implication: you can only put your element into
one heap at a time. Since you only need this info during
Remove, we decided in Go to let the caller do the tracking
when necessary (and skip it if not). The most obvious
implementation is to stick an index into the struct being
moved around, like in this code from package time:
func (timerHeap) Swap(i, j int) {
timers[i], timers[j] = timers[j], timers[i]
timers[i].i = i
timers[j].i = j
}
but it's also possible to leave it out (if not calling
Remove) or to do something more general (if you want one
object to be storable in multiple heaps). In Go there is no
PRIQUEUE_EXTENDED_FIBHEAP_ENTRY to inherit. This is
especially important if you are building a heap of objects
of a type you don't control, which comes up when writing
Dijkstra's algorithm. (You could even implement an on-disk
heap using Go's heap package; trying doing that when a disk
block has to inherit from PRIQUEUE_EXTENDED_FIBHEAP_ENTRY!)
Speaking of Dijkstra's algorithm, there's no implementation
in the standard library, so I wrote one. It expects an
input that satisfies the Graph interface:
package graph
type Graph interface {
// NumVertex returns the number of vertices in the graph.
NumVertex() int
// VertexID returns a vertex ID, 0 <= ID < NumVertex(), for v.
VertexID(v Vertex) int
// Neighbors returns a slice of vertices that are adjacent
// to v in the graph.
Neighbors(v Vertex) []Vertex
}
type Vertex interface {
String() string
}
func ShortestPath(g Graph, start, end Vertex) []Vertex
Here I've decided that a Graph should be able to give each
vertex a dense numeric ID, which the various graph
algorithms can use to identify the vertex. Note that I am
not requiring a Vertex to be a
PRIQUEUE_EXTENDED_FIBHEAP_ENTRY. Why should internal
details of the implementation of ShortestPath leak into the
interface required of its callers?
ShortestPath is straightforward:
// ShortestPath uses Dijkstra's algorithm to find the shortest
// path from start to end in g. It returns the path as a slice of
// vertices, with start first and end last. If there is no path,
// ShortestPath returns nil.
func ShortestPath(g Graph, start, end Vertex) []Vertex {
d := newDijkstra(g)
// Run Dijkstra's traversal.
d.visit(start, 1, nil)
for !d.empty() {
p := d.next()
if g.VertexID(p.v) == g.VertexID(end) {
break
}
for _, v := range g.Neighbors(p.v) {
d.visit(v, p.depth+1, p)
}
}
// Reconstruct path.
p := d.pos(end)
if p.depth == 0 {
// unvisited - no path
return nil
}
path := make([]Vertex, p.depth)
for ; p != nil; p=p.parent {
path[p.depth-1] = p.v
}
return path
}
The visit and next methods contain calls to container/heap's
heap algorithm functions, but that fact does not leak into
the Graph interface. The ShortestPath code manages separate
state on the side (the value d of type dijkstra) instead of
requiring that state to be mixed into the Graph that is
passed in.
A maze, of course, is a very specialized kind of graph, in
which each vertex has at most four neighbors drawn from a
fixed set. It is easy to implement a custom Maze type and
then add the methods to implement graph.Graph.
The maze "solver" is then just a call to ShortestPath:
m := NewMaze(w, h)
path := graph.ShortestPath(m, m.Vertex(0, 0), m.Vertex(w-1, h-1))
fmt.Println(m.PathString(path))
The full code is at:
http://code.google.com/p/rsc/source/browse/rosetta/graph/graph.go
http://code.google.com/p/rsc/source/browse/rosetta/maze/maze.go
You can play with the code by running
goinstall rsc.googlecode.com/hg/rosetta/maze
maze
maze
maze
If you look through the code, the only time there are
conversions is to turn a Vertex into a maze.pos or an
interface{} into a *graph.dpos. Those are fundamental to
the way you write type-agnostic algorithms in Go: they have
to operate on interface values, and then the implementations
that accept those interfaces need to write a converson
occasionally. There are two in package graph and three in
maze. I don't believe that rises to the level of
"extraneous rubbish".
It is easy to get caught in the trap of seeing a piece of
nice code in another language, like this
multiple-inheritance Eiffel shortest path, and then trying
to translate the concepts into Go instead of stepping back
to think about how you'd approach the problem and the
solution from a Go point of view. Taking an Eiffel point of
view when trying to write a Go program will not produce
nice, idiomatic Go code. Quite the opposite. But if you
can avoid the trap, and you come at it thinking about Go
concepts instead of concepts from some other language, I
think you can arrive at an elegant solution.
This makes Go different from many languages: because so many
of today's languages are inheritance-oriented languages, it
is easy to move between them and transliterate code, because
the underlying model is the same. Go is built on a
different model, so trying to move code from Eiffel or
Python or Java or C# or C++ to Go usually works poorly. You
have to start over, thinking in Go.
Go's interfaces force you to separate code from data. You
don't get to mix them like you do in inheritance-oriented
languages. This is certainly limiting - at the least, it
makes code in inheritance-oriented languages harder to
convert to Go - but it has benefits too. For example,
because the ShortestPath state is not mixed into the Maze's
Vertex implementation, it is possible for multiple
goroutines to run graph.ShortestPath on the same maze
simultaneously (presumably with different start, end pairs).
It's unfortunate that every time someone asks for
inheritance the answer is "well, there's embedding."
Embedding is useful and a kind of inheritance, but when
people come looking for inheritance, embedding is not the
answer. The answer is: you're thinking in C++, or in Python
or Java or Eiffel or whatever. Don't do that. Think in Go.
Russ
Jeremy Shute
Daniel Jo
+1
I think that should be a Go blog post.
-Daniel
Charles Thompson
and probably many other readers, about Go.
This is definitely blog post worthy and should be linked to from
golang.org. Language newcomers would benefit very much. Thank you.
Dave Cheney
roger peppe
> implementation is to stick an index into the struct being
> moved around, like in this code from package time:
>
> func (timerHeap) Swap(i, j int) {
> timers[i], timers[j] = timers[j], timers[i]
> timers[i].i = i
> timers[j].i = j
> }
i was happy when i thought of that (though i'm sure i wasn't the first).
> func ShortestPath(g Graph, start, end Vertex) []Vertex {
this is really nice - use of indexes to save slow map accesses;
pity it needs an allocation on every call to Neighbours.
great expository text. definite +1 on putting it on the Go blog.
Mark Summerfield
Thank you very much for this outsanding reply, code, and comments!
I think that Roger's comment that this would be a good basis for a Go
blog is spot on.
When I was challenged with this question my first response was "use
delegation". But when it was pointed out that that wouldn't work, I was
stuck. Like many people I have had years and years of conventional OOP
using inheritance, so I still don't always see things the Go way
straight off. I think a slight reworking of your reply to illustrate
good Go _thinking_ would be really interesting and useful.
[snip]
Thanks:-D
PS Kyle: _I_ wasn't criticizing Go, I was in a discussion about it and
could not figure out the refutation---but thanks to Russ et al., I now
have an excellent answer:-)
⚛
> [a long post about implementation of generic algorithms in Go]
Well, maybe some people at golang-nuts are now expecting that I will
try to somehow refute your post with some "However ..." argument.
Because interaction of conjectures and refutations is a good thing.
I agree that the generic implementations of Graph, ShortestPath(),
Sort and Heap mentioned in your post are well suited to the task.
However ... there seems to be a common aspect to all of them: they
require/imply an "apriory view" of data they are working with (or we
can call it a "static view"). Thanks to this requirement, it was
possible to simply use an "int" in various places in the Go code. In
particular, "Graph.VertexID(v Vertex)" returns an "int". There is also
"Heap.Swap(i, j int)". This allows Graph, Heap and ShortestPath() to
simply use ints when talking to each other.
The Graph and ShortestPath() imply that the program must have apriori
knowledge of all the vertices in the graph. This is natural, it
follows from the fact that for the algorithm to work correctly, it
needs to keep track of whether it already visited a vertex.
The apriori knowledge requirement enables to put all the vertices in a
single list. We need to know about all the vertices before the
algorithm starts, so it is easy to line them up in a list and
associate an index with a particular vertex. The "int" values that the
modules use to talk to each other are simply list indexes. The "int"
type plays the role of a generic type.
The argument I would like to present here is that in a lot of problem
domains we do *not* have such an apriori knowledge. Since we do have
it, we are unable to beforehand/apriori create a static list of all
objects, and therefore we cannot use an "int" as an index and as a
generic type for communication between algorithms. In other words, the
general method that Russ used in his post cannot be extended all
problem domains (that is kind-of obvious, but I just wanted to
explicitly point out this fact).
It is a *very common* coding pattern to create objects on-the-fly in a
program, especially if the program is running for a longer period of
time or if it is a program which is interacting with its surrounding
environment a lot. It is also very common to deallocate (forget about)
objects during the execution of a program. What this basically means
is that there is no such thing as "a global list of all objects",
because the working set is constantly changing.
It is therefore common to use memory allocation (and memory
deallocation (either automatic or manual)). Essentially, the "list of
all objects" concept is now equivalent to the whole address space
available to the program, and it is being managed by a memory
allocator.
In an assembly language, the programmer is responsible for handling
the address space - an object pointer is simply an integer here.
Unfortunately, this is highly error prone. Indeed, assembly is generic
and highly flexible (otherwise it wouldn't be possible to translate
higher-level languages down to assembler instructions). But the error
rate and productivity of programming in assembly are not good.
In order to keep the error rate down, we have higher-level languages
(such as Go) which are trying to categorize the integer mess into
something comprehensible.
... in short, while it is possible to use ints in Graph, Heap and
ShortestPath(), it does *not* imply that it is a generally good method
of programming to follow the example of Graph, Heap and
ShortestPath(). The method used may be closer to an assembly-language
than to a higher-level language style of programming and thinking.
What I am basically trying to say is that the method Russ used is
useful, but not all-powerful. (Maybe I am just stating the obvious and
there is nothing new to learn here.)
warmfuzzykitten
Mark Summerfield
Here's Jeff's unedited response to your Dijkstra implementation (and to
Roger Peppe's).
------------------------------------------------------------
From: Jeff Kingston <je...@it.usyd.edu.au>
To: Mark Summerfield <ma...@qtrac.eu>
Subject: Re: Go: A Go Dijkstra in good Go style
Date: Sun, 18 Sep 2011 12:55:48 +1000
Mark,
Feel free to copy this mail to the Go list, if you think they
will be interested. I've written it for redistribution.
First of all, I'm impressed by the speed and quality of the
responses you got to your email to the Go list. I'm also
impressed by the fact that Go's library includes a heap.
When time complexity matters, Heap should offer a DecreaseKey
operation which combines removing an element, decreasing its
key, and re-inserting it. This is because both remove and
insert usually cost O(log n), but some heap implementations
have a DecreaseKey which costs an amazing O(1). But only
algorithms people know or care about this.
The use of an integer index in the Remove operation is a worry.
From the Swap operation I saw down Russ's link, I conclude that
this is the element's index in a Floyd-Williams heap. This index
has no place in the interface: it is part of the internal state
of one particular implementation of the heap interface, and it
changes unpredictably as the heap changes, leading to the need
for that Swap operation. But this is just a case of poor
interface design, arising from the fact that Heap's authors
had only one heap implementation in mind and wanted to make
it efficient. It could be fixed; it's not a reflection on Go.
Roger Peppe's implementation is basically the two-object
version I've mentioned several times (he has a mark object
for every node object). To get back from the priority queue
entry (i.e the mark) to the node, he has a node field in his
mark type. To get from the node to the priority queue entry,
he has an integer index in his mark type.
Although Roger's code is very concise, I do think it can
fairly be said to contain "extraneous rubbish" when compared
with the Eiffel version: the mark type with its mysterious set
of attributes, and the array of marks. But this is mitigated
by the fact that the mark type can be conceived as a genuine
abstraction of its own - basically the endpoint of a path to
a node, not just the raw node. In my solution these two
ideas are conflated.
I have doubts about the concurrency, a quick look suggested
that his marks[] array is subject to contention; or if it
is not shared, then different threads do duplicate work.
Perhaps he means that completely separate traversals can
run in parallel; that's true, but why do it? But this is
not a big issue for me, everyone knows you have to think
again when concurrency is required. In graphs there is a
fundamental concurrency issue whenever two threads reach the
same vertex via different paths.
My response to Russ Cox's posting is as follows.
When Russ says that multiple inheritance is not a key aspect to
the efficiency of the Eiffel implementation of Dijkstra, he is
correct in the sense that you can simulate multiple inheritance
using the two-object simulation I have mentioned so often. But
in order to get the efficiency you do need to do something
equivalent to what multiple inheritance does so elegantly: you
need an O(1) route from the node to the priority queue element,
and you need an O(1) route from the priority queue element to
the node. (This is what the Python solution lacked.) In the
multiple inheritance solution this route is provided by pointers
or deltas behind the scenes; in the two object simulation it is
provided by the pointers (or heap indexes, etc.) that point in
each direction between the two objects.
> > Of course, I am not claiming that you can't implement Dijkstra's
> > algorithm in Go. The claim is that you can't take two types, one for
> > directed graphs and one for priority queues, and use them, without
> > rewriting their methods, to produce a version of Dijkstra's
> > algorithm
>
> This question betrays an inheritance-oriented bias: it
> assumes that to reuse an algorithm, you have to do it by
> inheriting from a type that implements that algorithm...
Rubbish. The question merely assumes that people want to use
library code without having to rewrite it. Surely that's true!
This sounds like a reflex reaction, or perhaps the confusion is
owing to the fact that someone has misquoted me here by cutting
me off in the middle. What I actually wrote was
"Of course, I am not claiming that you can't implement Dijkstra's
algorithm in Go. The claim is that you can't take two libraries,
one for directed graphs and one for priority queues, and use
them without rewriting their methods to produce a version of
Dijkstra's algorithm which is free of casts or other extraneous
rubbish, as this version is: ... " followed by my Eiffel Dijkstra.
The stuff about not rewriting is a non-issue because no-one in the
Go camp has even considered rewriting the library routines for Heap
- naturally enough. So it's the "free of casts or other extraneous
rubbish" bit, left out of the truncated quotation, that is significant
in my claim. Perhaps Russ would not dispute this claim, I don't know.
Russ then goes on to explain why algorithms are not classes and
what interfaces are about, which I have no problems with.
> That has an implication: you can only put your element into
> one heap at a time.
This is a problem with the inherit-an-element approach, I agree.
It's also a problem for the Go implementation in cases where
Remove is needed: you can only have one Swap operation, but
it has to change different indexes depending on which heap is
involved. In both cases you can get around it by having
separate wrapper objects for the element in each heap.
But I don't want to make an issue of this, because one heap at
a time is adequate for Dijkstra and for most problems. I am
the author of an algorithms and data structures textbook; I
coded every algorithm in the book, and this problem never came up.
> This is especially important if you are building a heap of objects
> of a type you don't control, which comes up when writing Dijkstra's
> algorithm. (You could even implement an on-disk heap using Go's heap
> package; trying doing that when a disk block has to inherit
> from PRIQUEUE_EXTENDED_FIBHEAP_ENTRY!)
The issue here is heapifying objects whose type you don't control,
which for shorthand we are calling disk blocks.
With the interface approach, you define the operations needed
by the Heap interface, effectively adding them to the disk
block type, and away you go. If you are using Remove and need
to store an index, or if you are unlucky and the disk block
type already has an operation with the same name as a Heap
operation, you will need wrapper objects for the disk blocks.
With the inheritance approach, you always define a wrapper
type, and it always inherits element-of-priority-queue. You
define the operations that priority queue elements need on
that type, the same as needed for Heap, and away you go again.
The inheritance approach is clumsier in the simple usual
case, and virtually the same in the harder case. Either
way, behind the scenes the interface objects in the heap
look a lot like element-of-priority-queue objects.
However, whatever we think of the merits of these approaches,
we won't prove that Go can implement Dijkstra as elegantly as
Eiffel can by proving that Go can heapify disk blocks more
elegantly than Eiffel can. Let's keep to the original point.
We are not trying to prove that Eiffel is better than Go, or
vice versa. (If you thought we were, see the quote above
beginning with "Of course".)
> Note that I am not requiring a Vertex to be a
> PRIQUEUE_EXTENDED_FIBHEAP_ENTRY. Why should internal
> details of the implementation of ShortestPath leak into the
> interface required of its callers?
Let me say first, to avoid confusion, that in my type structure,
type Vertex in the library knows nothing about priority queues.
The two aspects get combined using multiple inheritance only in
the application, adjacent to the code for Dijsktra's algorithm.
Other than that, there is a fair point here. If you want to start
with a graph object whose type knows nothing about Dijkstra and
run Dijkstra's algorithm on it, with inheritance you will need
wrapper objects and your solution will become messier and closer
to the Go solutions. Many applications (public transport trip
planner web sites, for example) would naturally assume from the
start that the graphs they build are going to be Dijkstra'd at
some point. In such applications there would be no problem with
defining a vertex type which inherited the library vertext type and
the library priority queue element type from the start, and building
the graph out of vertices of this type.
Russ does not show the full implementation of Dijkstra in his
posting (procedure visit is omitted), but he gives a link:
http://code.google.com/p/rsc/source/browse/rosetta/graph/graph.go
I think it's fair to say that his implementation is significantly
less elegant than mine: it has little statements like
p := d.pos(v)
which don't do anything useful in terms of the abstract algorithm.
My Eiffel code has none of this extraneous rubbish. It contains
statements derived from the abstract algorithm and nothing else.
I think that proves my point. If you've forgotten what my point
was, look at the quote beginning "Of course" above.
Two quick comments before I close. First, although it is not his
fault, Russ's implementation has the dreadful
func (d *dijkstra) Swap(i, j int) {
d.q[i], d.q[j] = d.q[j], d.q[i]
d.q[i].heapIndex = i
d.q[j].heapIndex = j
}
in which part of the implementation of Heap is outsourced to
the application.
Second, Russ has implemented breadth-first search, not general
shortest paths. That is, all his edges have length 1. He could
have used an ordinary queue for that, but the issues we are
discussing here are not affected.
Jeff Kingston
------------------------------------------------------------
--
Mark Summerfield, Qtrac Ltd, www.qtrac.eu
C++, Python, Qt, PyQt - training and consultancy
⚛
> ------------------------------------------------------------
> From: Jeff Kingston <j...@it.usyd.edu.au>
> To: Mark Summerfield <m...@qtrac.eu>
> Date: Sun, 18 Sep 2011 12:55:48 +1000
>
>
> When Russ says that multiple inheritance is not a key aspect to
> the efficiency of the Eiffel implementation of Dijkstra, he is
> correct in the sense that you can simulate multiple inheritance
> using the two-object simulation I have mentioned so often. But
> in order to get the efficiency you do need to do something
> equivalent to what multiple inheritance does so elegantly: you
> need an O(1) route from the node to the priority queue element,
element".
That is false. The truth is that you don't need that route.
You think you need that route because multiple inheritance in Eiffel
has fooled you.
> and you need an O(1) route from the priority queue element to
> the node. (This is what the Python solution lacked.) In the
> multiple inheritance solution this route is provided by pointers
> or deltas behind the scenes; in the two object simulation it is
> provided by the pointers (or heap indexes, etc.) that point in
> each direction between the two objects.
The reality is that the average size of heap in Dijkstra is usually
*much smaller* than the number of nodes in the graph. Multiple
inheritance means that *all* the instances are both heap elements and
graph nodes at the same time. In consequence of this, multiple
inheritance causes the Eiffel implementation to consume more memory
than is actually required. Russ'es implementation does not suffer from
this issue.
I think it is a poor idea to use multiple inheritance in problem
domains where it causes unnecessary memory consumption. From this
perspective, multiple inheritance is a poor match for implementing
Dijkstra's algorithm. The algorithm has: list of all nodes (i.e: the
graph), the working set (i.e: the heap). The working set is usually
much smaller than the graph. It appears that by choosing multiple
inheritance, you chose to ignore this property of the algorithm.
I will go even farther than this and will say that multiple
inheritance is in fact a poor match for any kind of algorithm (not
just Dijkstra) which exhibits the pattern I mentioned in previous
paragraphs.
roger peppe
> Although Roger's code is very concise, I do think it can
> fairly be said to contain "extraneous rubbish" when compared
> with the Eiffel version: the mark type with its mysterious set
> of attributes, and the array of marks. But this is mitigated
> by the fact that the mark type can be conceived as a genuine
> abstraction of its own - basically the endpoint of a path to
> a node, not just the raw node. In my solution these two
> ideas are conflated.
>
> I have doubts about the concurrency, a quick look suggested
> that his marks[] array is subject to contention; or if it
> is not shared, then different threads do duplicate work.
> Perhaps he means that completely separate traversals can
> run in parallel; that's true, but why do it? But this is
> not a big issue for me, everyone knows you have to think
> again when concurrency is required. In graphs there is a
> fundamental concurrency issue whenever two threads reach the
> same vertex via different paths.
i was indeed thinking that completely separate traversals
can run in parallel. this means that, for instance, several
threads can run shortest path calculations in parallel without needing
an interlock on the main graph.
this kind of approach also makes more interesting things possible.
for instance in a previous agent based modelling application [1] i
used a similar
structure to enable different agents to find routes over slightly different
versions of the same (large) graph without needing to use
an edited copy - each agent had its own information about
which arcs are blocked.
this would be easy to implement in Russ's version, but harder
(i think) in the Eiffel version.
roger peppe
> The reality is that the average size of heap in Dijkstra is usually
> *much smaller* than the number of nodes in the graph. Multiple
> inheritance means that *all* the instances are both heap elements and
> graph nodes at the same time. In consequence of this, multiple
> inheritance causes the Eiffel implementation to consume more memory
> than is actually required. Russ'es implementation does not suffer from
> this issue.
i'm not convinced. all it takes to be a member of this kind of heap is the
array storage, which is used in both cases, and some way
of mapping from the member to the heap index, which is again
used in both cases.
if the A* algorithm was being used, you could make a better
case around the extra Dijkstra information (parent and distance),
because it's possible that many nodes in the graph will not
be visited.
and if path calculations are infrequent, then Russ's approach uses
the extra memory only during the path calculation, which might
also be a consideration.
⚛
>
> > The reality is that the average size of heap in Dijkstra is usually
> > *much smaller* than the number of nodes in the graph. Multiple
> > inheritance means that *all* the instances are both heap elements and
> > graph nodes at the same time. In consequence of this, multiple
> > inheritance causes the Eiffel implementation to consume more memory
> > than is actually required. Russ'es implementation does not suffer from
> > this issue.
>
> i'm not convinced. all it takes to be a member of this kind of heap is the
> array storage, which is used in both cases, and some way
> of mapping from the member to the heap index, which is again
> used in both cases.
implementation. My apologies.
It is possible to simply delete the field "heapIndex" from struct
"dpos", because the field is never being read from.
My critique was primarily targeted against the idea of multiple
inheritance being a good match for the graph algorithm.
roger peppe
> It is possible to simply delete the field "heapIndex" from struct
> "dpos", because the field is never being read from.
that's true, but only because of a bug in the code.
russ's code doesn't actually implement "shortest path", but only
"some path". the visit method should move the item
in the heap if the new depth is less than the old depth,
but it doesn't. that's when heapIndex would come in handy.
⚛
>
> > It is possible to simply delete the field "heapIndex" from struct
> > "dpos", because the field is never being read from.
>
> that's true, but only because of a bug in the code.
> russ's code doesn't actually implement "shortest path", but only
> "some path".
between connected vertices equals to 1.
> the visit method should move the item
> in the heap if the new depth is less than the old depth,
> but it doesn't. that's when heapIndex would come in handy.
currently in the heap.
roger peppe
> On Sep 19, 1:17 pm, roger peppe <rogpe...@gmail.com> wrote:
>> On 19 September 2011 12:08, ⚛ <0xe2.0x9a.0...@gmail.com> wrote:
>>
>> > It is possible to simply delete the field "heapIndex" from struct
>> > "dpos", because the field is never being read from.
>>
>> that's true, but only because of a bug in the code.
>> russ's code doesn't actually implement "shortest path", but only
>> "some path".
>
> It implements "shortest path", but under the assumption that distance
> between connected vertices equals to 1.
yes you're right of course.
heapIndex could go. or the graph code could be updated
to support different path lengths, which would probably
be a better demonstration.
my code should be similarly updated.
Russ Cox
> Here's Jeff's unedited response to your Dijkstra implementation
Jeff's response is mainly arguing that the Eiffel version is nicer.
Whether that is true is irrelevant, at least to my post.
The discussion is about how to implement X in
idiomatic Go, not whether X is prettier in Eiffel or Go.
If I were writing in Eiffel, I would definitely use
Jeff's code, since it *is* nice, and it is apparently
idiomatic Eiffel. But getting into a debate about
which one is nicer misses the fundamental point:
because languages provide different tools,
you sometimes need to approach a problem from
different directions in different languages.
Russ
Jeremy Shute
Tarmigan
> Lets assume that we wanted to modify the Dijkstra code to account for non
> unitary weights. Presumably that would mean we need to modify the graph
> interface to enable calling of the edge weight (something like Weight(e
> Edge) ). There may be some graph classes which have all of the bells and
> whistles, and allow things like edge weights. There may be other graph
> classes which are designed for efficiency on simple graphs, and so don't
> have a weight assigned to their edge. Is there any way to write a single
> Dijkstra's code that can run on both of those kinds of graphs? I think this
> would be equivalent to having a statement like "If the type has an edge
> weight method, then use it, otherwise the edge weight is 1".
You can test whether a type implements an interface. So you could
make a new interface that includes a Weight() method, and test against
that.
http://play.golang.org/p/Hkt0qQaD3L
-Tarmigan