Hi Everyone,
remember my post titled "scala.collection.Graph – Call for Comments" about 10 days ago? Many thanks for reviewing my design thoughts! Some of you claimed executable code or at least technical documentation. Now I'd like to present you a preliminary of Graph coming along with all that. Just go to http://www.tip-top-tipp.info/scala-graph/Quick-Start.pdf http://www.tip-top-tipp.info/scala-graph/doc/ First you should have a look at collection.Graph and collection.GraphEdge - all others are less important. If you like, you may play around with it downloading http://www.tip-top-tipp.info/scala-graph/Graph.jar (see also REPL.txt and TGraph.scala) All that is, of-course, solely for evaluation purposes - personally for you. Certainly, I've got a long list of to-do's. But listening to your suggestions is even more valuable. So don't hesitate to further comment. Cheers Peter |
On Thursday November 25 2010, Peter Empen wrote:
> Hi Everyone, > > ... > > http://www.tip-top-tipp.info/scala-graph/Quick-Start.pdf > http://www.tip-top-tipp.info/scala-graph/doc/ From the ScalaDoc for trait EdgeLike: "Inheriting classes should not be case classes." Why not? > ... > > Cheers > Peter Randall Schulz |
In reply to this post by Peter Empen
Dear Peter,
i saw this post some time back and didn't get a chance to respond. i like that you're making this effort. i'm not sure what it buys a user over using JGraphT from Scala. Could you comment on a usage scenario that differentiates this package? Also, have you taken a look at the Haskell graph package? In particular, Martin Erwig's package [1] purports to be compositional. There are several other proposals for a compositional treatment of graphs. Consider Philippa Gardner (with Giogio Ghelli and Luca Cardelli)'s proposal. The logic is based on an underlying compositional encoding of graphs. Finally, i took a swipe at an algebra of graphs. You can see a simple presentation of the algebra here; and an implementation of a Lift-based app (the code is nearly two years old -- so bit rot may have set in) using the library here.
The key point in all of these proposals is that just as lists are made of lists (and their elements) graphs are made of graphs and their elements. Thus, if we think of a simple compositional presentation of lists as taken directly from monoid
m,n ::= 0 | g1 | ... | gN | m*n what would be an algebraic presentation for graphs following this model? Such a presentation will be markedly different from the standard G = ( V, E ).
Best wishes, --greg [1] Inductive Graphs and Functional Graph Algorithms
Martin Erwig. Journal of Functional Programming, Vol. 11, No. 5, 467-492, 2001. We propose a new style of writing graph algorithms in functional languages which is based on an alternative view of graphs as inductively defined data types. We show how this graph model can be implemented efficiently, and then we demonstrate how graph algorithms can be succinctly given by recursive function definitions based on the inductive graph view. We also regard this as a contribution to the teaching of algorithm and data structures in functional languages since we can use the functional-style graph algorithms instead of the imperative algorithms that are dominant today. Paper.ps.gz (125K), Paper.pdf (297K) On Thu, Nov 25, 2010 at 9:09 AM, Peter Empen <[hidden email]> wrote:
-- L.G. Meredith Managing Partner Biosimilarity LLC 7329 39th Ave SW |
In reply to this post by Randall R Schulz-2
Hello Randal:
good question. This is not necessary because I've prepared EdgeLike to deal with hashCode and equals in a more elegant way. So it's easy and safe to mix in AttributedEdge and then to define the abstract val attributes = … It's also better to have control defining apply and unapply in your custom companion object. There, you can call helper methods defined in object EdgeLike to transform your parameter list to a Product: def apply[N](node_1: N, node_2: N, nodes: N*): Product Another aspect is that we are generally discouraged to inherit from case classes. Though I’ve not yet examined whether a case class deriving from EdgeLike would really do harm. |
On Thursday November 25 2010, Peter Empen wrote:
> Hello Randal: > > ... > > Another aspect is that we are generally discouraged to inherit from > case classes. Though I’ve not yet examined whether a case class > deriving from EdgeLike would really do harm. Inheriting _from_ them is problematic. Making them inherit from a trait or an abstract class is not. Randall Schulz |
In reply to this post by Meredith Gregory
Dear Greg,
I was thinking about M. Erwig’s proposal a lot. It seems to me that the question whether to adhere to a pure functional style is mostly an implementation issue. If so, I could sustain the traditional G = (V, E) while optionally providing a pure functional implementation. Please correct me if this doesn’t hold in your opinion. I was also wondering about M. Erwig’s motivation. His aspects of teaching functional languages and being pure functional are clearly not valid for a Scala implementation. So far I couldn’t spot a real benefit from using the proposed algebra so may I ask you to give an example also to those lacking Haskell skills? I would especially be interested to see the benefit of having nodes being graphs itself. Looking at graphatrope I don’t have an immediate clue, either. Best regards Peter |
Dear Peter,
Thanks for your thoughtful reply! i've included some responses below. Best wishes, --greg
On Sun, Dec 5, 2010 at 6:29 AM, Peter Empen <[hidden email]> wrote:
If threading and concurrent access to the graph is largely an implementation issue, then i suppose you are correct. Sometimes it might be useful to have concurrent access to graph structure, in which case a purely functional approach might be useful. My main concern, however, is not purely functional design, but compositional one! That's what scales. The process calculi, my ever present example, represent computations that are highly stateful, but they are compositional. Moreover, the G = (V,E) is a view of an underlying structure. It may or may not be the most useful depending the aim of the representation. Likewise, for operations on G's, you might have some equations, e.g. G1+G2 = (V1+V2, E1+E2). The extent to which you can support this sort of compositional view preferentially will be the extent to which your library scales, imho.
i'm not sure i follow your logic, here; but, it doesn't matter. The point is that Erwig's design had compositionality as one of the desiderata. i mention it as a touchstone because in addition to having compositionality as a design goal, it was well enough executed that it became bundled with the Haskell release and so is worthy of consideration.
So far I couldn’t spot a real benefit from using the proposed algebra so may Please find below links several examples from Graphatrope that i took the time to illustrate (at the time i wrote down the algebra) just to convince myself that the representation had any legs. The fact that these are all essentially 1-liners in the algebra (read, compositional representation) is the point about scalability and compositionality. As the programmatic complexity of the graph that needs representation goes up, the compositional representation scales along with it nicely. This is rarely the case with non-compositional views.
The historical argument in favor of this position is the trend in Graph Theory, itself. Compare the development of graph theory towards algebraic graph theory. More importantly, compare the size of a standard text on graph theory to the size of standard text on algebraic graph theory. That alone might give pause for thought.
Now, i confess, most programmers are about 10x smarter than i am. So, they can handle a lot more complexity than i can. i need organizing principles that help me simplify what i have to think about and simplify the number of things i have to think about and the amount of code i have to keep in play on the screen and in my mind. i have noticed that for a lot of people, considerations of complexity scaling are simply not of interest. For me they are of paramount importance as they almost completely determine the actual, in practice maintainability of a codebase -- whether the codebase is a website or quantum physics or a body of law.
For example, if i can express a graph as an algebra that is tantamount to expressing it as a monad (or composition of monads). Excellent! i've now lowered the number of things i have to thing about. i don't have to design a fresh interface, i get to reuse one that has been given about 50 years worth of Q&A.
Best regards -- L.G. Meredith Managing Partner Biosimilarity LLC 7329 39th Ave SW |
P.S. A compositional view is not to be equated with a view that collapses the category of Graphs with the category of Nodes/Vertices. Those are entirely distinct propositions.
P.P.S. One thread that got lost was what examples would make your library be a better choice than using JGraphT from Scala. i would love to see those.
On Sun, Dec 5, 2010 at 12:56 PM, Meredith Gregory <[hidden email]> wrote: Dear Peter, -- L.G. Meredith Managing Partner Biosimilarity LLC 7329 39th Ave SW |
Slightly off-topic. Greg, what do you use to draw those beautiful graphs? On Mon, Dec 6, 2010 at 1:35 AM, Meredith Gregory <[hidden email]> wrote: P.S. A compositional view is not to be equated with a view that collapses the category of Graphs with the category of Nodes/Vertices. Those are entirely distinct propositions. |
Dear Vadim,
i dashed them off with OmniGraffle. Best wishes, --greg
On Mon, Dec 6, 2010 at 1:29 AM, Vadim <[hidden email]> wrote:
-- L.G. Meredith Managing Partner Biosimilarity LLC 7329 39th Ave SW |
In reply to this post by Meredith Gregory
P.P.P.S. i just noticed there's a typo in the complete graph spec in the examples i gave.
complete( n ) = (let x = v in discrete( 1 ), { x in v(complete( n-1 ) | true }) should read complete( n )
= (let x = v in discrete( 1 ), { x in complete( n-1 ) | true }) On Sun, Dec 5, 2010 at 3:35 PM, Meredith Gregory <[hidden email]> wrote: P.S. A compositional view is not to be equated with a view that collapses the category of Graphs with the category of Nodes/Vertices. Those are entirely distinct propositions. -- L.G. Meredith Managing Partner Biosimilarity LLC 7329 39th Ave SW |
This post has NOT been accepted by the mailing list yet.
In reply to this post by Peter Empen
Hey all,
I was just wondering if there was any more progress on this since the initial posts on this thread. I'm really interested in a pure Scala graph class, and, as you may know, the options out there right now are pretty slim. This implementation looks promising; is development still continuing? --Rob |
Free forum by Nabble | Edit this page |