Support for Drupal 7 is ending on 5 January 2025—it’s time to migrate to Drupal 10! Learn about the many benefits of Drupal 10 and find migration tools in our resource center.
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:
- Constructor: build a matrix from an edge list. The current input format will do.
- What other vertices can I reach from this vertex. This is your module dependency list.
- Was this vertex part of the initial edge list? It is a missing dependency if not.
- 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.
Comment | File | Size | Author |
---|---|---|---|
#38 | 1915308_38.patch | 12.47 KB | chx |
#38 | interdiff.txt | 1.4 KB | chx |
#37 | core-graph-1915308-34-37-diff.txt | 2.36 KB | clemens.tolboom |
#37 | core-graph-1915308-37.patch | 11.2 KB | clemens.tolboom |
#34 | 1915308_34.patch | 9.04 KB | chx |
Comments
Comment #1
clemens.tolboom[edit: removed useless code example /]
Comment #2
clemens.tolboomAttached patch will fail as the current tests do not assume the existence of end points having a reversed_path.
Comment #3.0
clemens.tolboomFixed link
Comment #4
clemens.tolboomI 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/]
Comment #5
clemens.tolboomComment #5.0
clemens.tolboomAdded image + more text ... I definitely needs some time for the issue summary template :(
Comment #5.1
clemens.tolboomUpdated issue summary.
Comment #6
clemens.tolboom(sigh: needs review + better image)
Test will fail as the results of #2 needs some analysis.
I need to fix the BUG at least.
Comment #6.0
clemens.tolboomUpdated image + text.
Comment #6.1
clemens.tolboomUpdated issue summary.
Comment #8
clemens.tolboom(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
Comment #9
clemens.tolboomOk 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
I guess @chx could shine a light on this 'BUG'.
(I will update summary tomorrow)
Comment #10
chx CreditAttribution: chx commentedComment #10.0
chx CreditAttribution: chx commentedAdded the issue summary template.
Rewrote some text
Added new methods
Added code example
Comment #10.1
chx CreditAttribution: chx commentedupdated list summary
Comment #11
chx CreditAttribution: chx commentedEven 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.
Comment #13
chx CreditAttribution: chx commentedComment #14
chx CreditAttribution: chx commentedPerhaps rename traverse to step? It'd be better I think.
Comment #14.0
chx CreditAttribution: chx commentedUpdated issue summary.
Comment #15
chx CreditAttribution: chx commentedEven better title :)
Comment #16
msonnabaum CreditAttribution: msonnabaum commentedThe approach in #13 seems sane to me. Just needs unit tests.
Comment #18
clemens.tolboomRegarding patch from #9
We need a reset IMHO as we may need both the TSL and paths in one go.
========
Regarding #11
Shouldn't we add this to Graph so ie ModuleHandler::buildModuleDependencies can run a foreach on the Graph object?
========
Regarding patch from #13
Nice addition as it makes code clearer. Traverse is good to me as it does not do 'just one step'.
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.
Comment #19
chx CreditAttribution: chx commentedOne, 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.
Comment #20
chx CreditAttribution: chx commentedComment #21
chx CreditAttribution: chx commentedComment #22
clemens.tolboomFixed the ByRef as mentioned in #19
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.
Comment #24
sdboyer CreditAttribution: sdboyer commentedso, 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.
Comment #25
chx CreditAttribution: chx commentedAdding 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.
Comment #26
chx CreditAttribution: chx commentedAlso, a note to return about drains is necessary. See? Drains! I know graph theory.
Comment #27
chx CreditAttribution: chx commentedOh 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.)
Comment #28
chx CreditAttribution: chx commentedHere is more. Needs doxygen and tests.
Comment #29
chx CreditAttribution: chx commentedForgot the drains in the module code.
Comment #30
chx CreditAttribution: chx commentedMeh, 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.
Comment #32
chx CreditAttribution: chx commentedComment #34
chx CreditAttribution: chx commentedThis won't quite pass but hopefully will fix the update tests. The Graph tests I leave to @clemens.tolboom.
Comment #36
clemens.tolboomI'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.
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.
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.
Comment #37
clemens.tolboomFixed 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.
Comment #38
chx CreditAttribution: chx commented> 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):
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.
Comment #39
clemens.tolboomI 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.
Comment #40
clemens.tolboomThe issue summary really needs some update before this can be RTBCed. I myself have lost the current goal of this issue :-/
Comment #41
chx CreditAttribution: chx commentedAnd the current patch also needs serious work. Stay tuned.
Comment #41.0
chx CreditAttribution: chx commentedUpdated issue summary.
Comment #41.1
chx CreditAttribution: chx commentedrewrote the issue summary
Comment #42
Mile23Patch in #38 doesn't apply cleanly against cd62f0bc02cc26b887c211e757e6268784f9db08.
It gives me this:
Comment #43
sdboyer CreditAttribution: sdboyer commentedmarking this a duplicate in favor of #2098375: Add gliph to composer.
Comment #43.0
sdboyer CreditAttribution: sdboyer commentedUpdated issue summary.