Programming, Graph Theory and a Request For Help.

Comments on a work in progress

I’m working at the Banff Centre right now – taking existing work that I have already done and generalizing it to build a bare bones locative application server and client. The idea is to let people use a mobile device to post photographs or text or audio or movies up to a shared web server and to then see those posts on a shared map. This is similar to work I have already done and it is in fact just a slight repurposing of existing work from a variety of open source resources. If it goes well then it will be a resource for locative media artists to use to share their locative media projects.

However today I seem to have run into a problem – a similar kind of problem that I see over and over. And I thought I would elaborate on this – and hopefully get some answers.

What I’m stuck on is finding an easy way to let the user interact with the data without having to re-invent the wheel. Of course the whole dataset can be incredibly complex – and can end up being something that is difficult to interact with – so many people have worked at finding ways to visualize data – such as for example SkyRails:

What data am I trying to represent?

I’ll back up a bit and just talk about programming first – a kind of mini-tutorial on programming. In computer programming there at least 3 ways to represent data.  Let’s consider an ordinary web mapping application purely as an example here – and what data it might contain:

1) In a user view or UX view the user is presented with an easy to understand visual representation of the data. For example a user might see a “map” object that contains “marker” objects. And the user can interact with this visual representation – to add or remove markers for example.

2) A data only view may represent the “maps” and “markers” as just tables in a database column. This is a very dry and mechanical view that does not make it as clear that the objects have a relationship to each other ( such as that the map may own the markers or that the markers are near each other ).

3) A graph based view. Often in my head when I am working with an application I tend to represent it as a graph of nodes floating in space. These nodes have connections to each other and it is those connections that are of primary importance. In my case I would represent a “map” as a parent node, and then draw the “markers” as children nodes.

In fact it is the third view that is the most accurate I feel. What computer programming really “is” is just a form of graph manipulation. Once you can put aside the visual representation and really see what is going on – what you see is that it largely consists of many many subtle and carefully defined relationships between things. This is why many programming tutorials are so confusing; because they focus on syntax and grammar rather than the intuitive understanding.

When we’re looking at a graph based view what becomes clear is that it is the relationships between things, not the things, that is most important. This maxim might be true of everything.

What kinds of relationships exist between data?

So what I really want to look at is the kinds of relationships that exist between objects and then look at ways to try to represent them.  There are at least three kinds of relationships that a programmer often is trying to define:

1) The relationships of links between “Instances”, such as the relationship between you and your facebook friends. These can be referred to as “Instance Relationships”. An “object” in this sense is something that exists as an instance, not just that it is a “Person” or a “Place” but that it is a specific person, a specific place – an instance of a kind.  For example :

2) The “structural” relationships of properties, attributes or qualities. For example in FaceBook a Person and a Group are both a kind of object with similar properties. Often it makes sense to say that they are both a kind of “friendable” object so that you can write a piece of software that can look at friendable objects and show which ones are friends with which one – instead of having to write similar but slightly separate code for objects that are friends of persons and for objects that are friends of groups. In a kind of Platonic model there is an idea of an abstract “kind” and then other kinds are variations of that kind. The relationships between “kinds” not “instances” is crucial to understand.

3) The event messaging relationships, such as in a video game where a collision event may be sent from one object to another so that the other object knows it should do something appropriate ( such as rebound or make an appropriate sound ).

The challenge I face here is the following:

1) I would like to let users be able to make maps and markers (and other instance objects)… this is easy obviously.

2) I would like to be able to let users say that the maps/markers they make are “private” so that nobody else can see them, or “protected” so that only friends can see them or “public” so than anybody can see them…. this is also not hard.

3) I would like to allow the user to delete maps or markers that they made or that are marked public for deletion – or that they have administrative privileges over…. obviously a requirement.

4) I would like to let the users add or remove markers from maps if those maps are open, or if those users have administrative permissions over those maps…. and obviously a requirement as well.

5) Where it starts to get challenging is that I would like to let the user decorate a map or marker with arbitrary attributes. For example I would like to be able to let you set the “barometric pressure” on a marker if you wished.

6) In a perfect world I would like the user to be able to say that a given marker is a “prototype” kind of marker and that other kinds of markers can be instanced with the special attributes inherited from the prototype. I’m uncertain if it makes sense to allow an entire prototype hierarchy. This would let me have a map where all markers added to the map automatically had a “barometric pressure” attribute that could then be filled in.

7) In an even more perfect world I would like to be able to say that certain attributes are mandatory, and that others are optional.

Are there any off the shelf solutions?

Now, the challenge is really that this kind of issue occurs over and over. We’ve seen systems like RDF and the FreeBase project as an attempt to address this. What I really want is a combination of two things:

1) A database model that can bind to Rails that represents this kind of data.

2) And a visual editing tool that lets an ordinary user easily drag and drop objects together, to create and break relationships between objects, and to edit the attributes of objects.  Something I can simplify or tailor the view of.

On the second point – why don’t tools like this exist? If most if not all programming problems are a variation of this then one would imagine that there would be many graph editing tools out there that let users wander a garden full of data, pruning and trimming it as they go. It seems like even lesser versions. I would like something that could be put into a browser that provided a succinct view of the tree of objects and allowed easy manipulation of that tree directly. Tools like activescaffold for Rails do provide a complete database view but I want a view that reflects the relationships between objects in a tree – emphasizing the parents and children and emphasizing easy editing of attributes.

Any tips?


  1. Skry
    Posted August 9, 2009 at 11:33 am | #

    #6, I guess no, at least at first. The explosive complexity rules it out. Controlled vocabulary has too many limitations on the other hand. Worst case it would be like choosing tags from a menu of all used tags. If you really want to, maybe suggestive search would be a successful UI model. Would it take Googltastic infrastructure to pull that off, though? Suggestions based on typing could be helpful in collapsing terms for similar prototype ideas. Suggested synonyms would be helpful there too. Get the users to help prune the name space during creation maybe.

    Solutions: #2: I once saw something like this in Smalltalk, ca. 1994. A visual relational OO db. It was really cool, as easy as editing in old-school hypertext systems such as Storyspace. Object-node-containers and named links.

  2. Posted August 11, 2009 at 8:30 am | #

    graphviz! … oh wait thats not it either.

  3. Posted November 24, 2009 at 1:26 pm | #

    Have you though about using something like Mongo DB, Cassandra, or Couch DB for the type of storage you want? All of those provide essentially a native AJAXian way of accessing data through a RESTful json interface.

    I was thinking about creating the drag and drop interface. At first I thought Java 3D has the capability to create clickable 3D objects. Then I thought one could use jQuery to manipulate html entities to create an interactive editor, even adding psudo-3d abilities. What you probably want, is a fully interactive 3d interface. That can be done via Javascript via O3D a la Google. It give one the ability to import 3D models and let the user interact with them.

    I hope that at least helps.

One Trackback

  1. [...] anselm 2009-08-08 02:39:30 Continued here: Programming, Graph Theory and a Request For Help. [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>