Comments

s.Daniel’s picture

If I read the issues correctly the current functionality in includes/graph.inc lacks some desired features and your patch to add these features didn't recieve much love. What are your current thoughts on this as to future development plans / Have you had time to research the alternatives?

I've done a quick search but didn't find much interesting stuff.
https://github.com/clue/graph
http://www.symfony-project.org/plugins/sfDoctrineGraphvizPlugin

s.Daniel’s picture

Summarize Graphs?
graphviz_filter uses http://pear.php.net/package/Image_GraphViz/download

There are other libaries available via pear that might be interesting:
http://pear.php.net/package/Image_Graph/redirected
http://pear.php.net/package/Structures_Graph/redirected (blog post)

I'm not sure how to evaluate those but in general I think improving existing code is a good idea where possible.

More recources:
https://github.com/networkx/networkx Python but seems quite advanced

clemens.tolboom’s picture

Thanks for the links.

I should study http://pear.php.net/package/Structures_Graph/redirected in depth.

http://pear.php.net/package/Image_Graph/ seems to generate images which I'm not interested in for this project. The same goes for http://pear.php.net/package/Image_GraphViz/download

The classes (which are in the source tree afaik) are just data structures.

clemens.tolboom’s picture

Assigned: Unassigned » clemens.tolboom
Category: feature » bug
Status: Active » Needs work

Triggered by (core) #1762204: Introduce Assetic compatibility layer for core's internal handling of assets I grabbed the patch from #310898: Making module_enable and module_disable API functions and pushed an initial version for this module.

It needs some work especially #1209426: Multiple links from A to B are not supported which is needed for i.e. module version dependency graphs (core) #1247476: ModuleHandler::parseDependency fails on major version ops (>27.x) and (<=28.x)

Another core issue could benefit from these classes #896698: Circular dependency references between field and field_sql_storage maybe ?

sdboyer’s picture

a DX request - it'd be great if, rather than having to inject an array fully representing the graph, the graph class provided methods for incrementally declaring the vertexes and edges. so, instead of:

$graph = a_function_that_return_the_kinda_weird_multidimensional_graph_array();
new \Drupal\Component\Graph\Graph($graph);
$result = $graph->searchAndSort();

the class would actually help with the process:

$graph = new \Drupal\Component\Graph\BetterGraph();
foreach ($list_of_vertices as $vertex) {
  $graph->addVertex($vertex, $vertex->getArrayOfEdges());
}

$result = $graph->resolve();

total pseudocode there, but hopefully that communicates the idea.

clemens.tolboom’s picture

@sdboyer : I hope you didn't read graphapi.API.php which is about this module as a whole.

This issue is about the classes lying around.

I'm now working on the Classes only!

That way I can write tests and upgrade the module to D8 to test for some core issues. (This way I'm not risking much 'waste of time' if Core does not allow for the code.)

To answer your question. This should work already with

$g = new \GraphAPI\Component\Graph\DirectedGraph();

foreach ($list_of_vertices as $vertex) {
  $graph->addLinks($vertex->getId(), $vertex->getArrayOfEdgeIds());
}

$tsl => $g->getTSL();

as DirectedGraph knows about Topological Sorted List. But it now throws an exception if you try to #896698: Circular dependency references between field and field_sql_storage

I need to write some tests for this first.

clemens.tolboom’s picture

It's not true about the exception and getTSL().

You should use (currently named AcyclicDirectedGraph)

$g = new \GraphAPI\Component\Graph\DirectedAcyclicGraph();

as only a DAG has a real TSL. Tomorrow this is effected correctly.

sdboyer’s picture

@clemens.tolboom - i didn't read that file; i'm basing that API note on what's in D8 right now in \Drupal\Component\Graph\Graph (so, core/lib/Drupal/Component/Graph/Graph.php).

my recommendation would be, given how tight we are on the deadline, that you shoot for making the additions as similar to that paradigm as possible. so, maybe a few classes in that namespace that handle the different graph use cases.

we can also extend the API after feb 18, i suspect, to add the convenience methods i describe above. so no need to rush on that. the only absolutely crucial thing i need for #1762204: Introduce Assetic compatibility layer for core's internal handling of assets is handling for objects as vertices.

clemens.tolboom’s picture

I have refactored the different Graph API classes.

There are now DrupalUnitTestCase. Is that enough or will this be a blocker when adding the classes to #1762204: Introduce Assetic compatibility layer for core's internal handling of assets? I'll try that the next few days.

sdboyer’s picture

i'll have to look at the refactored classes and see how they'll do for our purposes. aiming for tonight.

have you made a core issue to incorporate these new classes? this issue won't be much use for D8 core while in this queue...

clemens.tolboom’s picture

My plan was to push it in through #1762204: Introduce Assetic compatibility layer for core's internal handling of assets but I need some more tests :(

clemens.tolboom’s picture

Assigned: clemens.tolboom » Unassigned

Will working on #1762204: Introduce Assetic compatibility layer for core's internal handling of assets I ran onto https://github.com/clue/graph which as a much richer code base. Not sure whether we can use it as it has no data attached to it's graph members / nodes / vertices.

I decided to move the Graph classes out of this project to https://github.com/clemens-tolboom/graph but that will happen only for the Drupal 8 version of Graph API. That way I'll learn more about composer and dependency management and gives me the opportunity to try to make a good library out of it instead of a module only.

For now I un-assign.

clemens.tolboom’s picture

Assigned: Unassigned » clemens.tolboom
Category: bug » task

This will be removed in favor of https://github.com/clue/graph.

The tests should be ported over.

clemens.tolboom’s picture

Version: 7.x-1.x-dev » 7.x-2.x-dev

This is obsoleted by the use of https://github.com/clue/graph in 7.x-2.x

clemens.tolboom’s picture

Status: Needs work » Closed (won't fix)
clemens.tolboom’s picture

Issue summary: View changes

-