Home » forums » LtU Forum

A graph puzzle

Before I get going, as this is my first post here, I would just like to say hello and thank you all for your contributions to an always-interesting forum. :o) I will also point out that my background is in Mathematics, not computer science.

Graphs are extremely useful structures, and they are pretty much everywhere you look in computing whether explicitly or implicitly. Yet I have never met a mainstream language which included graph processing as an in-built facility. I am wondering - why not?

A quick Google search turned up a few research languages which make heavy use of graph rewriting rules (GP, Spider), and some interesting systems like NESL and SARTEX. The last of these sounds the most like what I am thinking of - a mainstream language (for the time) with built-in support for graphs. But the paper is from 1985, so it appears that the idea did not catch on. Was there a good reason for this?

By Brett Gibson at 2008-09-22 14:00 | LtU Forum | previous forum topic | next forum topic | other blogs | 4816 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Maybe related...

This paper discusses "a new style of writing graph algorithms in functional languages which is based on an alternative view of graphs as inductively defined data types."

By Matt M at Mon, 2008-09-22 15:01 | login or register to post comments

Guessing

I guess it is just easy enough to implement a small graph library in a GPL, and there are too many different kind of graphs/graph representations to actually develop a language which would fulfill the exact needs of potential users.

(Those who want a fast SKI rewrite system have different requirements than those who want to implement Edmonds Blossoming Algorithm for some application than those who want to study heuristics for optimal routing of messages. I don't see all those different requirements met in one language.)

By marco at Mon, 2008-09-22 18:25 | login or register to post comments

algorithmic complexity

Programming language designers like the basis sets of their languages to contain mostly O(1) operations. They like to not overly constrain the representation of types for which more than one representation is plausible. When they vary from these, they tend to still want to leave wiggle room for programmers to alter the representations or the algorithms needed for core operations. However, the simplest way to leave that wiggle room is to push the problematic functionality into libraries, rather than build it in.

If you had a "perfect or at least excellent choice for many, many choices" graph library then you might want a high-level notation that treats graph operations as primitive.

No such library exists except within narrowed problem domains.

I think that explains the phenomenon you've observed.

-t

By Thomas Lord at Mon, 2008-09-22 19:30 | login or register to post comments

You can have a look at

You can have a look at Boost.Graph, a very good C++ graph library using generic programming.

By hoang vu at Tue, 2008-09-23 01:23 | login or register to post comments