Summary

Add a class for handling topological sorts for dependency graphs.

Review Request #7722 — Created Oct. 21, 2015 and submitted Nov. 3, 2015, 5:12 p.m.

Information

Owner

chipx86

Repository

rbpkg

Branch

master

Bugs

Depends On

Reviewers

Groups

rbpkg

People

Description

DependencyGraph manages a graph of items and their dependencies, and can
generate a list of items in dependency order. This will be used for
determining the correct order in which to install packages.

Testing Done

Unit tests pass.

Issues

Description	From	Last Updated
"Vertice" isn't a word. "Vertex" is.	david	Oct. 21, 2015, 11:39 p.m.
Hrm. It bugs me that we're manipulating state on the vertices themselves to do this. Can we have a visited …	david	Oct. 21, 2015, 11:39 p.m.
Why do we maintain both this list and this dictionary? Can't we just use the dictionary? The only time a …	AD adriano	Oct. 25, 2015, 2:43 a.m.
Consider replacing "and dependencies" with "and its dependencies".	AD adriano	Oct. 25, 2015, 2:44 a.m.
This is usally called toposort	brennie	Oct. 23, 2015, 4:33 p.m.
I think "yielding" should be "yield". As in: "This will recursively...yield all results."	AD adriano	Oct. 25, 2015, 2:44 a.m.
This sounds a bit funny to me. We don't really sort a single vertex; we sort all the vertices in …	AD adriano	Oct. 25, 2015, 2:44 a.m.

Tool: PEP8 Style Checker
Processed Files:
    rbpkg/package_manager/dep_graph.py
    rbpkg/package_manager/tests/test_dep_graph.py



Tool: Pyflakes
Processed Files:
    rbpkg/package_manager/dep_graph.py
    rbpkg/package_manager/tests/test_dep_graph.py

rbpkg/package_manager/dep_graph.py (Diff revision 1)
The issue has been resolved. Show all issues
```
"Vertice" isn't a word. "Vertex" is.
```

rbpkg/package_manager/dep_graph.py (Diff revision 1)

The issue has been resolved. Show all issues

Hrm. It bugs me that we're manipulating state on the vertices themselves to do this. Can we have a visited cache that we pass along through the recursion?

chipx86 Oct. 21, 2015, 2:52 p.m.

I suppose. This is entirely for internal use, and is a short-lived throw-away object, but sure.

Change Summary:


Stopped inventing words.
Removed the visited flag on Vertex, switching to a local cache used during sort.

Diff:

Revision 2 (+164)

Show changes

	rbpkg/package_manager/__init__.py
	rbpkg/package_manager/dep_graph.py
	rbpkg/package_manager/tests/test_dep_graph.py

Tool: Pyflakes
Processed Files:
    rbpkg/package_manager/dep_graph.py
    rbpkg/package_manager/tests/test_dep_graph.py

Ignored Files:
    rbpkg/package_manager/__init__.py



Tool: PEP8 Style Checker
Processed Files:
    rbpkg/package_manager/dep_graph.py
    rbpkg/package_manager/tests/test_dep_graph.py

Ignored Files:
    rbpkg/package_manager/__init__.py

rbpkg/package_manager/dep_graph.py (Diff revision 2)
The issue has been resolved. Show all issues
```
This is usally called toposort
```

Ship it!

There's a typo in the summary: "toplogical" -> "topological".

rbpkg/package_manager/dep_graph.py (Diff revision 2)

It seems that edges is a list of vertices, as opposed to a list of directed edges in the usual graph theory sense (which to me would be ordered pairs of vertices). So perhaps a better name would be neighbours, since it's the list of all neighbouring vertices?

chipx86 Oct. 25, 2015, 2:59 a.m.

I'm not well schooled in graph theory, so forgive any ignorance here.
I would expect neighbors to be any vertices pointing to or from this particular vertex, which isn't the case here. For instance:


A
^
|
B -> C
^
|
D


B.edges would consist of [A, C], not [A, C, D].
Regarding vertices, if I had stored each relation on the graph, rather than on this helper object, pairs of vertices would make sense. For instance, [(B, A), (B, C), (D, B)]. That's really just another form of what I have here, though. The X in (X, Y) is the entry in DependencyGraph._vertices, and each Y is an entry in Vertex.edges.
Am I totally wrong here?

adriano Oct. 25, 2015, 10:35 a.m.

You're right. Sorry, I meant to say out_neighbours instead.

rbpkg/package_manager/dep_graph.py (Diff revision 2)

The issue has been dropped. Show all issues

Why do we maintain both this list and this dictionary? Can't we just use the dictionary? The only time a call to self._vertices is made is when we iterate through all the vertices in Line 74. It doesn't seem like the order matters. So we could get rid of self._vertices and replace Line 74 with:

for vertex in six.itervalues(self._vertex_cache)

If it turns out that the order in which the vertices are added to the graph does matter, then we could always use an OrderedDict.

chipx86 Oct. 25, 2015, 2:59 a.m.

The order does matter, for predictability. If I add 4, 5, and 9 as dependencies for MyKey, and nothing else changes that order, I'd like those to come out as 4, 5, and 9. If we use a hash, it could be 9, 4, 5, etc. In fact, it breaks tests, because we can't test any sane orders.

OrderedDict isn't an option for us, as it's not available for Python 2.6 (which we must continue to support).

rbpkg/package_manager/dep_graph.py (Diff revision 2)
The issue has been resolved. Show all issues
```
Consider replacing "and dependencies" with "and its dependencies".
```

rbpkg/package_manager/dep_graph.py (Diff revision 2)

The issue has been resolved. Show all issues

I think "yielding" should be "yield". As in: "This will recursively...yield all results."

rbpkg/package_manager/dep_graph.py (Diff revision 2)

The issue has been resolved. Show all issues

This sounds a bit funny to me. We don't really sort a single vertex; we sort all the vertices in the graph. Perhaps replace it with something like "The starting vertex of the topological sort."

rbpkg/package_manager/dep_graph.py (Diff revision 2)

I'm curious: instead of the try/except, why not do something like:
if item in self._vertex_cache:
    return self._vertex_cache[item]
else:
    # ... append it to the vertices and return it ...

chipx86 Oct. 25, 2015, 2:59 a.m.

The try/except is faster in the case where the key already exists. In that case, we don't have to do two lookups.

In the case where it's not present, it performs the same (we do the lookup, and then add).

Change Summary:


Added __contains__, for checking if an item is in the graph.
Renamed _tsort to _toposort.
Changed some docstrings, based on feedback.

Summary:

Add a class for handling toplogical sorts for dependency graphs.

Add a class for handling topological sorts for dependency graphs.

Diff:

Revision 3 (+167)

Show changes

	rbpkg/package_manager/__init__.py
	rbpkg/package_manager/dep_graph.py
	rbpkg/package_manager/tests/test_dep_graph.py

Tool: PEP8 Style Checker
Processed Files:
    rbpkg/package_manager/dep_graph.py
    rbpkg/package_manager/tests/test_dep_graph.py

Ignored Files:
    rbpkg/package_manager/__init__.py



Tool: Pyflakes
Processed Files:
    rbpkg/package_manager/dep_graph.py
    rbpkg/package_manager/tests/test_dep_graph.py

Ignored Files:
    rbpkg/package_manager/__init__.py

Change Summary:

Renamed edges to out_neighbors.

Diff:

Revision 4 (+167)

Show changes

	rbpkg/package_manager/__init__.py
	rbpkg/package_manager/dep_graph.py
	rbpkg/package_manager/tests/test_dep_graph.py

Tool: PEP8 Style Checker
Processed Files:
    rbpkg/package_manager/dep_graph.py
    rbpkg/package_manager/tests/test_dep_graph.py

Ignored Files:
    rbpkg/package_manager/__init__.py



Tool: Pyflakes
Processed Files:
    rbpkg/package_manager/dep_graph.py
    rbpkg/package_manager/tests/test_dep_graph.py

Ignored Files:
    rbpkg/package_manager/__init__.py

Status:: Completed
Change Summary:: Pushed to master (196f85d)