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.

Files: 
CommentFileSizeAuthor
#38 1915308_38.patch12.47 KBchx
PASSED: [[SimpleTest]]: [MySQL] 53,128 pass(es).
[ View ]
#38 interdiff.txt1.4 KBchx
#37 core-graph-1915308-34-37-diff.txt2.36 KBclemens.tolboom
#37 core-graph-1915308-37.patch11.2 KBclemens.tolboom
PASSED: [[SimpleTest]]: [MySQL] 51,331 pass(es).
[ View ]
#34 1915308_34.patch9.04 KBchx
FAILED: [[SimpleTest]]: [MySQL] 51,241 pass(es), 2 fail(s), and 0 exception(s).
[ View ]
#32 1915308_32.patch9.03 KBchx
FAILED: [[SimpleTest]]: [MySQL] 50,796 pass(es), 3 fail(s), and 30 exception(s).
[ View ]
#30 1915308_30.patch9.02 KBchx
FAILED: [[SimpleTest]]: [MySQL] Drupal installation failed.
[ View ]
#29 1915308_29.patch6.78 KBchx
FAILED: [[SimpleTest]]: [MySQL] Failed to run tests: failed to enable simpletest module.
[ View ]
#28 1915308_28.patch6.78 KBchx
FAILED: [[SimpleTest]]: [MySQL] Failed to run tests: failed to enable simpletest module.
[ View ]
#25 1915308_25.patch3.59 KBchx
FAILED: [[SimpleTest]]: [MySQL] Failed to run tests: failed to enable simpletest module.
[ View ]
#22 core-graph-1915308-22.patch6.39 KBclemens.tolboom
FAILED: [[SimpleTest]]: [MySQL] 50,754 pass(es), 0 fail(s), and 129 exception(s).
[ View ]
#13 1915308_13.patch3.35 KBchx
FAILED: [[SimpleTest]]: [MySQL] 50,351 pass(es), 14 fail(s), and 35 exception(s).
[ View ]
#11 1915308_11.patch3.25 KBchx
FAILED: [[SimpleTest]]: [MySQL] Drupal installation failed.
[ View ]
#9 core-graph-1915308-9.patch5.63 KBclemens.tolboom
PASSED: [[SimpleTest]]: [MySQL] 50,402 pass(es).
[ View ]
#6 core-graph.png7.75 KBclemens.tolboom
#4 core-graph-1915308-4.patch5.94 KBclemens.tolboom
FAILED: [[SimpleTest]]: [MySQL] 50,392 pass(es), 4 fail(s), and 0 exception(s).
[ View ]
#4 core-graph.png7.52 KBclemens.tolboom
#5 core-graph.png7.94 KBclemens.tolboom
#2 core-graph-1915308-3.patch3.74 KBclemens.tolboom
FAILED: [[SimpleTest]]: [MySQL] 49,742 pass(es), 8 fail(s), and 15,045 exception(s).
[ View ]

Comments

Status:Needs review» Active

[edit: removed useless code example /]

Status:Active» Needs review
StatusFileSize
new3.74 KB
FAILED: [[SimpleTest]]: [MySQL] 49,742 pass(es), 8 fail(s), and 15,045 exception(s).
[ View ]

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.

Issue summary:View changes

Fixed link

StatusFileSize
new7.52 KB
new5.94 KB
FAILED: [[SimpleTest]]: [MySQL] 50,392 pass(es), 4 fail(s), and 0 exception(s).
[ View ]

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/]

StatusFileSize
new7.94 KB

Issue summary:View changes

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

Issue summary:View changes

Updated issue summary.

Status:Needs work» Needs review
StatusFileSize
new7.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.

Issue summary:View changes

Updated image + text.

Issue summary:View changes

Updated issue summary.

Status:Active» Needs work

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

(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

<?php
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

Status:Needs work» Needs review
StatusFileSize
new5.63 KB
PASSED: [[SimpleTest]]: [MySQL] 50,402 pass(es).
[ View ]

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

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

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

(I will update summary tomorrow)

Title:Graph.inc is not TSL completeInclude all vertices in Graph::searchAndSort
Category:bug» task

Issue summary:View changes

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

Issue summary:View changes

updated list summary

Title:Include all vertices in Graph::searchAndSortDrains are not included in Graph::searchAndSort
StatusFileSize
new3.25 KB
FAILED: [[SimpleTest]]: [MySQL] Drupal installation failed.
[ View ]

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.

Status:Needs work» Needs review
StatusFileSize
new3.35 KB
FAILED: [[SimpleTest]]: [MySQL] 50,351 pass(es), 14 fail(s), and 35 exception(s).
[ View ]

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

Issue summary:View changes

Updated issue summary.

Title:Drains are not included in Graph::searchAndSortAdd a topological sort facility

Even better title :)

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.

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.

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.

Title:Add a topological sort facilityAdd topological sort and graph normalization

Status:Needs review» Needs work

Status:Needs work» Needs review
StatusFileSize
new6.39 KB
FAILED: [[SimpleTest]]: [MySQL] 50,754 pass(es), 0 fail(s), and 129 exception(s).
[ View ]

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.

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.

Status:Needs work» Needs review
StatusFileSize
new3.59 KB
FAILED: [[SimpleTest]]: [MySQL] Failed to run tests: failed to enable simpletest module.
[ View ]

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.

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

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.)

Title:Add topological sort and graph normalizationMake the graph component input an edge list and add various graph helpers
StatusFileSize
new6.78 KB
FAILED: [[SimpleTest]]: [MySQL] Failed to run tests: failed to enable simpletest module.
[ View ]

Here is more. Needs doxygen and tests.

StatusFileSize
new6.78 KB
FAILED: [[SimpleTest]]: [MySQL] Failed to run tests: failed to enable simpletest module.
[ View ]

Forgot the drains in the module code.

Title:Make the graph component input an edge list and add various graph helpersMake the graph component input an edge list and add topological sort
StatusFileSize
new9.02 KB
FAILED: [[SimpleTest]]: [MySQL] Drupal installation failed.
[ View ]

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.

Status:Needs work» Needs review
StatusFileSize
new9.03 KB
FAILED: [[SimpleTest]]: [MySQL] 50,796 pass(es), 3 fail(s), and 30 exception(s).
[ View ]

Status:Needs review» Needs work

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

Status:Needs work» Needs review
StatusFileSize
new9.04 KB
FAILED: [[SimpleTest]]: [MySQL] 51,241 pass(es), 2 fail(s), and 0 exception(s).
[ View ]

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.

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.

Status:Needs work» Needs review
StatusFileSize
new11.2 KB
PASSED: [[SimpleTest]]: [MySQL] 51,331 pass(es).
[ View ]
new2.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.

StatusFileSize
new1.4 KB
new12.47 KB
PASSED: [[SimpleTest]]: [MySQL] 53,128 pass(es).
[ View ]

> 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.

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.

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

Status:Needs review» Needs work

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

Issue summary:View changes

Updated issue summary.

Issue summary:View changes

rewrote the issue summary

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

Status:Needs work» Closed (duplicate)

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

Issue summary:View changes

Updated issue summary.