We need some graph transformers

[clemens-tolboom]

We do have algorithms but we should have some transformers which test for an algorithm then apply a solution to validate that algorithm.

For example http://thejit.org has a space tree so we must supply it a tree. But what if our structure is only a DAG or worse a Cyclic Graph?

It's not hard to transform a DAG into a tree as I did http://drupalcode.org/project/thejit.git/blob/refs/heads/7.x-1.x:/modules/thejit_spacetree/thejit_spacetree.module#l368

• Are there more use cases?
• Is this different from exporters?

[clue]

Adding support for thejit would indeed be nice 👍

Is this different from exporters?

I think perhaps not. But perhaps yes, it might even be closer to our GraphViz "exporter" (despite the fact that we currently don't call it "exporter").

I have yet to work with thejit, but afaikt its documentation suggests it loads a simple JSON data object. So exporting the proper structure as an PHP array and providing an additional helper method which returns the JSON string should be fairly easy. If you're requesting (fictional method) TheJit::getJsonTreeForGraph($graph) and the given Graph can not be represented by a tree-like structure, then it should throw an Exception.

In my opinion, the main issue here is that we don't have a clear distinction of what an Exporter actually represents and whether GraphViz should actually be handled in a similar fashion and whether things like #23 actually fit the mold.

Any thoughts on this?

[clemens-tolboom]

The transformer just transforms the current graph into a graph representing a tree. So that could be kept internally.

The fact that thejit spacetree require a tree is more exporter related.

Another example is is ie Chord Diagram for http://d3js.org/ where we must transform the edge.weight into a table structure aka matrix. http://bl.ocks.org/mbostock/4062006

So I expect a directory layout aka package structure like

exporter/thejit/spacetree
transform/tree
trasnform/matrix/weight
importer/dot

Regarding the Drupal code the php tree structure is off coarse transformed into a space tree json. See http://skillcompass.org/ (which is Drupal + Graph API + thejit)

[clue]

The transformer just transforms the current graph into a graph representing a tree

So in that case, I think it's probably better to add it as an algorithm, perhaps somewhat similar to Algorithm\MinimumSpanningTree. The main issue here is that one can't just magically transform any given graph into a tree, because (obviously) some edges will violate the tree-constraints. So it's likely we'll need other/additional algorithms to base that decision on other parameters rather than the MST one (minimum sum of edges' weights).

However we're going to implement this, I'm all for returning a new Graph instance (which is a superset of a limited Tree class) that represents a Tree-like structure. Passing this Graph instance to the exporter should transform it into the appropriate data structure (JSON tree object, CSV matrix structure, whatever). If you're passing in a Graph instance that can not be represented as (for example) a JSON tree object, it should throw an Exception, so perhaps a new Algorithm\Tree::isTree() will be helpful here.

[clue]

New tree algorithms are going to be added with PR #44.

So what else has to be sorted out? :)

[clue]

Ping @clemens-tolboom. What's your status on this ticket?

Imho this can be closed now that PR #44 has been merged into master. Besides, I've set up a demo project as clue/graph-thejit, so I don't think it'll benefit the core of this library.

[clue]

According to the above comments, I think this is resolved. Otherwise, feel free to re-open or comment.

[clemens-tolboom]

I'm working to hard on other stuff ... sorry not to keep up the pace :-/