Add a class for handling topological sorts for dependency graphs.

Review Request #7722 — Created Oct. 21, 2015 and submitted

Information

rbpkg
master

Reviewers

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.

Unit tests pass.

Description From Last Updated

"Vertice" isn't a word. "Vertex" is.

daviddavid

Hrm. It bugs me that we're manipulating state on the vertices themselves to do this. Can we have a visited …

daviddavid

Why do we maintain both this list and this dictionary? Can't we just use the dictionary? The only time a …

AD adriano

Consider replacing "and dependencies" with "and its dependencies".

AD adriano

This is usally called toposort

brenniebrennie

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

AD adriano

This sounds a bit funny to me. We don't really sort a single vertex; we sort all the vertices in …

AD adriano
reviewbot
  1. 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
    
    
  2. 
      
david
  1. 
      
  2. rbpkg/package_manager/dep_graph.py (Diff revision 1)
     
     
    Show all issues

    "Vertice" isn't a word. "Vertex" is.

  3. rbpkg/package_manager/dep_graph.py (Diff revision 1)
     
     
    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?

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

  4. 
      
chipx86
reviewbot
  1. 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
    
    
  2. 
      
brennie
  1. 
      
  2. rbpkg/package_manager/dep_graph.py (Diff revision 2)
     
     
    Show all issues

    This is usally called toposort

  3. 
      
david
  1. 
      
  2. 
      
AD
  1. There's a typo in the summary: "toplogical" -> "topological".

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

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

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

  3. rbpkg/package_manager/dep_graph.py (Diff revision 2)
     
     
     
    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.

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

  4. rbpkg/package_manager/dep_graph.py (Diff revision 2)
     
     
    Show all issues

    Consider replacing "and dependencies" with "and its dependencies".

  5. rbpkg/package_manager/dep_graph.py (Diff revision 2)
     
     
    Show all issues

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

  6. rbpkg/package_manager/dep_graph.py (Diff revision 2)
     
     
    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."

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

  8. 
      
chipx86
reviewbot
  1. 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
    
    
  2. 
      
chipx86
reviewbot
  1. 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
    
    
  2. 
      
chipx86
Review request changed
Status:
Completed
Change Summary:
Pushed to master (196f85d)