Problem/Motivation

The current Graph class is not generic. It is tightly coupled with the needs of the module system.

The used storage structure currently stores matrix edges in an array with the following (strange) format $graph[$start]['edges'][$end] = 1;. If $graph[$end] is not set, it is a missing dependency.

Proposed resolution

The graph should be a classed object. You need the following operations:

  1. Constructor: build a matrix from an edge list. The current input format will do.
  2. What other vertices can I reach from this vertex. This is your module dependency list.
  3. Was this vertex part of the initial edge list? It is a missing dependency if not.
  4. Topological sort. #1762204: Introduce Assetic compatibility layer for core's internal handling of assets needs a complete TSL to dump css /js

Remaining tasks

Code this API.

API changes

the Graph class changes completely.

Support from Acquia helps fund testing for Drupal Acquia logo

Comments

clemens.tolboom’s picture

Status: Needs review » Active

[edit: removed useless code example /]

clemens.tolboom’s picture

Status: Active » Needs review
FileSize
3.74 KB

Attached patch will fail as the current tests do not assume the existence of end points having a reversed_path.

Status: Needs review » Needs work

The last submitted patch, core-graph-1915308-3.patch, failed testing.

clemens.tolboom’s picture

Issue summary: View changes

Fixed link

clemens.tolboom’s picture

I removed the overall fix and added some new methods:

- reset() : we need to be able to recalculate stuff for getTSL()
- addHead() : needed for calculating on TSL
- addTail() : needed to proof searchAndSort operates correctly
- getTSL() : returns the complete TSL

Test will still fail as I haven't fixed the bug in Graph.inc. I only added tests + methods.

[edit: removed image/]

clemens.tolboom’s picture

FileSize
7.94 KB
clemens.tolboom’s picture

Issue summary: View changes

Added image + more text ... I definitely needs some time for the issue summary template :(

clemens.tolboom’s picture

Issue summary: View changes

Updated issue summary.

clemens.tolboom’s picture

Status: Needs work » Needs review
FileSize
7.75 KB

(sigh: needs review + better image)

Test will fail as the results of #2 needs some analysis.

I need to fix the BUG at least.

clemens.tolboom’s picture

Issue summary: View changes

Updated image + text.

clemens.tolboom’s picture

Issue summary: View changes

Updated issue summary.

Status: Active » Needs work

The last submitted patch, core-graph-1915308-4.patch, failed testing.

clemens.tolboom’s picture

(mea culpa) Rereading the Graph.inc documentation it does not do a TSL but a depth first search. Checking my D7 graph_api_devel.module I use the weights returned from drupal_depth_first_search($graph);

So there is no TSL right now. I'll create one shortly from the algorithm on http://en.wikipedia.org/wiki/Topological_sorting

clemens.tolboom’s picture

Status: Needs work » Needs review
FileSize
5.63 KB

Ok I found the 'BUG' thanks to the algorithm on http://en.wikipedia.org/wiki/Topological_sorting

The Depth first Search should deliver a TSL too but that was not added to $state.

We can now create a Graph and ask for the TSL like

    $graph = new Graph($g);
    $tsl = $graph->getTSL();

I guess @chx could shine a light on this 'BUG'.

(I will update summary tomorrow)

chx’s picture

Title: Graph.inc is not TSL complete » Include all vertices in Graph::searchAndSort
Category: bug » task
chx’s picture

Issue summary: View changes

Added the issue summary template.
Rewrote some text
Added new methods
Added code example

chx’s picture

Issue summary: View changes

updated list summary

chx’s picture

Title: Include all vertices in Graph::searchAndSort » Drains are not included in Graph::searchAndSort
FileSize
3.25 KB

Even better title. I also rewrote the patch from ground up -- I think the previous ones are needlessly complex and not particularly clean. While Graph can not add any new vertices to the graph, a class extending it surely can.

Please add doxygen and test. The test needs to assert relative order -- you can't simply assert any given order; the only thing you can assert is that it's not in a wrong order, that is if A->B exists then A must come before B. This already is visible in GraphUnitTest::assertWeights. So a new test class is needed which asserts the relative order.

Status: Needs review » Needs work

The last submitted patch, 1915308_11.patch, failed testing.

chx’s picture

Status: Needs work » Needs review
FileSize
3.35 KB
chx’s picture

Perhaps rename traverse to step? It'd be better I think.

chx’s picture

Issue summary: View changes

Updated issue summary.

chx’s picture

Title: Drains are not included in Graph::searchAndSort » Add a topological sort facility

Even better title :)

msonnabaum’s picture

The approach in #13 seems sane to me. Just needs unit tests.

Status: Needs review » Needs work

The last submitted patch, 1915308_13.patch, failed testing.

clemens.tolboom’s picture

Category: task » bug
Status: Needs work » Needs review

Regarding patch from #9

+++ b/core/lib/Drupal/Component/Graph/Graph.php
@@ -85,11 +87,103 @@ class Graph {
+   */
+  public function reset() {

We need a reset IMHO as we may need both the TSL and paths in one go.
========
Regarding #11

While Graph can not add any new vertices to the graph, a class extending it surely can.

Shouldn't we add this to Graph so ie ModuleHandler::buildModuleDependencies can run a foreach on the Graph object?
========
Regarding patch from #13

+++ b/core/lib/Drupal/Component/Graph/Graph.php
@@ -157,6 +155,32 @@ protected function depthFirstSearch(&$state, $start, &$component = NULL) {
+  protected function traverse($state, $start, $end, $component) {

Nice addition as it makes code clearer. Traverse is good to me as it does not do 'just one step'.

+++ b/core/lib/Drupal/Component/Graph/TopologicalSort.php
@@ -0,0 +1,24 @@
+
+class TopologicalSort extends Graph {

This class should better be named DirectedAcyclicGraph if we want to give it a name.

Trouble I have is class Graph is in a way Directed Graph and is used as a DAG but not cycle aware as it just ignores cycles.

chx’s picture

One, you need to take this patch forward, I do not plan to. It fails because traverse($state, needs to be traverse(&$state. Please reroll my patch with more doxygen and add tests as explained above.

> We need a reset IMHO as we may need both the TSL and paths in one go.
> Shouldn't we add this to Graph so ie ModuleHandler::buildModuleDependencies can run a foreach on the Graph object?

Absolutely not! That's the very reason Graph must not add a vertex. What happens if module A depends on module B and B is missing? Currently, the graph will miss the B vertex and the module code can appropriately flip out. It's hardly the task of a DFS to add new vertexes. Arguably it's not the case for topsort either... Here's a better one: add getTopologicalSortedList to Graph and rename the new class to something else (GraphNormalized?) and explain that it does the normalization for you. Yes, that's what's happening really. See how the Graph Unit test does the normalization for you currently? Rename the current test to GraphNormalizedUnitTest, make it use the new GraphNormalized class and then remove the normalization method from test. Then copy this test to GraphUnitTest, make it use Graph and adjust test so that it passes. Then add getTopologicalSortedList to both tests. Hope this makes sense.

chx’s picture

Title: Add a topological sort facility » Add topological sort and graph normalization
chx’s picture

Status: Needs review » Needs work
clemens.tolboom’s picture

Status: Needs work » Needs review
FileSize
6.39 KB

Fixed the ByRef as mentioned in #19

Absolutely not! That's the very reason Graph must not add a vertex. What happens if module A depends on module B and B is missing?

Trouble with our implementation is there is no theory about it. So this code is hard to maintain. See ie http://en.wikipedia.org/wiki/Dependency_graph where all vertices are 'real'. It's current purpose is to support module_build_dependencies cum suis and will not help contrib.

I've renamed the class into GraphNormalized. It's name covers the current implementation.

I've added a test for GraphNormalized.

Let's see what testbot does.

Status: Needs review » Needs work

The last submitted patch, core-graph-1915308-22.patch, failed testing.

sdboyer’s picture

Trouble with our implementation is there is no theory about it...It's current purpose is to support module_build_dependencies cum suis and will not help contrib.

so, without having looked at code...

agreed, but it's not just contrib that suffers - other core utilities do, too. a basic graph implementation should not be responsible for handling "real" vs. "non-real" vertices; doing so would probably require typing of edges, which adds a whole new layer of complexity. a basic DAG is good at describing a dependency tree, and can provide all the information necessary for the calling code to iterate over the graph and determine whether or not we're able to satisfy the tree with the resources we actually have available.

chx’s picture

Status: Needs work » Needs review
FileSize
3.59 KB

Adding disparaging comments to the code is not helping for you are linking to the wrong Wikipedia article. And there is no theory about it? Puh-lease. You need to look at data structures instead. We have a data structure where the first dimension is the list of the vertices and then they store information including a list of vertices they point to. Now what should happen if the endpoint is not in the already defined list of vertices? That's where you can throw your pretty theory questions out the window because this is not covered in any theory. For the sake of convenience, I have chosen to ignore such data. This has extremely little to do with graph theory itself, this is a data representation and error handling question.

If you want to change the behavior and the meaning of the data structure, that is fine, we can certainly do that, say that it's an edge list and so all vertices must actually exist. However, it's worth noting that getting a list of vertices from the input now is much more expensive than it was previously -- previously it was O(V) now it's O(V+E), just to show I know some theory as well. Theory! In a web application. Let me laugh.

This probably will fail as I have not touched the test -- the real status is CNW because you need to fix the tests for the changed semantics of the class.

chx’s picture

Also, a note to return about drains is necessary. See? Drains! I know graph theory.

chx’s picture

Oh and rename drain to sink, apparently that's the appropriate English word. (My last graph theory exam was 17 years ago and in Hungarian, pardon me remembering wrong the translation.)

chx’s picture

Title: Add topological sort and graph normalization » Make the graph component input an edge list and add various graph helpers
FileSize
6.78 KB

Here is more. Needs doxygen and tests.

chx’s picture

FileSize
6.78 KB

Forgot the drains in the module code.

chx’s picture

Title: Make the graph component input an edge list and add various graph helpers » Make the graph component input an edge list and add topological sort
FileSize
9.02 KB

Meh, let's not add those methods it's off topic. I was incorrect naming there, anyways. Better names than unlisted_sink is welcome. And the module code needed a lot of love.

Status: Needs review » Needs work

The last submitted patch, 1915308_30.patch, failed testing.

chx’s picture

Status: Needs work » Needs review
FileSize
9.03 KB

Status: Needs review » Needs work

The last submitted patch, 1915308_32.patch, failed testing.

chx’s picture

Status: Needs work » Needs review
FileSize
9.04 KB

This won't quite pass but hopefully will fix the update tests. The Graph tests I leave to @clemens.tolboom.

Status: Needs review » Needs work

The last submitted patch, 1915308_34.patch, failed testing.

clemens.tolboom’s picture

I'm sorry this is now derailing and moving out of my coding comfort zone. I can fix the unit test but will that help :(

My only intend was to help with #1762204: Introduce Assetic compatibility layer for core's internal handling of assets. This now is getting a weird non-collaborating patch battle.

The root cause is Graph.inc does not provide for a real graph. Should we care yes but not in this issue. I'll post a new issue for that. So we can now focus on the issue at hand.

+++ b/core/lib/Drupal/Component/Graph/Graph.php
@@ -40,6 +45,9 @@ class Graph {
+   *     $graph[4]['reverse_paths'][1] = 1;
+   *     $graph[4]['unlisted_sink'] = TRUE;
    *   @endcode

This is not helping me as a sink is a Vertice: http://mathworld.wolfram.com/DigraphSink.html
I cannot fix for that as I don't get it.

+++ b/core/lib/Drupal/Component/Graph/Graph.php
@@ -129,34 +129,50 @@ protected function depthFirstSearch(&$state, $start, &$component = NULL) {
+    return array_reverse($this->lastVisited);

This should not be reversed as we must enable the deepest module first. (I maybe wrong)

I'll fix the two tests and add my TSL tests later today.

clemens.tolboom’s picture

Status: Needs work » Needs review
FileSize
11.2 KB
2.36 KB

Fixed failing test for vertice 6 as that now is an entry in the first column with a reveresed_paths, unlisted_sink and a component.

I added new test for TSL.

chx’s picture

FileSize
1.4 KB
12.47 KB

> This now is getting a weird non-collaborating patch battle.

Really. I changed what the graph means to better accomodate need and fixed the failures arising from that while you were throwing disparaging comments in the Graph code.

> This is not helping me as a sink is a Vertice: http://mathworld.wolfram.com/DigraphSink.html

It's just additional data on the vertex that it was not in the original list of vertices which is quite necessary for the module list. As said, better name are welcome. If it's not helping you, then I need to know what your problem is.

Also, only because your claim that this code contradicts graph theory, I need to point out that Vertex (graph theory):

In graph theory, a vertex (plural vertices)

so "a Vertice" is incorrect. It's "a vertex" or "a set of vertices". In general, I very strongly recommend not trying to get into a maths theory war with me. It really brings out the nasty of me. Nonetheless, I am still here to help.

This patch removes the now unnecessary normalize graph method from the test.

clemens.tolboom’s picture

I like the interdiff as it is now an example too.

Regarding the sink ... we really should document it. But that's probably another issue as Graph.inc does not have proper Class documentation yet. So let's skip that now.

clemens.tolboom’s picture

The issue summary really needs some update before this can be RTBCed. I myself have lost the current goal of this issue :-/

chx’s picture

Status: Needs review » Needs work

And the current patch also needs serious work. Stay tuned.

chx’s picture

Issue summary: View changes

Updated issue summary.

chx’s picture

Issue summary: View changes

rewrote the issue summary

Mile23’s picture

Patch in #38 doesn't apply cleanly against cd62f0bc02cc26b887c211e757e6268784f9db08.

It gives me this:

$ git apply 1915308_38.patch 
error: core/modules/system/lib/Drupal/system/Tests/Graph/GraphUnitTest.php: No such file or directory
error: patch failed: core/modules/system/system.admin.inc:856
error: core/modules/system/system.admin.inc: patch does not apply
sdboyer’s picture

Status: Needs work » Closed (duplicate)

marking this a duplicate in favor of #2098375: Add gliph to composer.

sdboyer’s picture

Issue summary: View changes

Updated issue summary.