← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Aaron Bentley
  • Date: 2007-06-21 01:12:19 UTC
  • mto: This revision was merged to the branch mainline in revision 2542.
  • Revision ID: aaron.bentley@utoronto.ca-20070621011219-a967wm19vxxc8dx5
Add functionality for tsorting graphs

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
 
from bzrlib import errors
 
17
from bzrlib import (
 
18
    errors,
 
19
    tsort,
 
20
    )
18
21
from bzrlib.deprecated_graph import (node_distances, select_farthest)
19
22
from bzrlib.revision import NULL_REVISION
20
23
 
275
278
                return lca.pop()
276
279
            revisions = lca
277
280
 
 
281
    def iter_topo(self, revisions):
 
282
        """Iterate through the input revisions in topological order.
 
283
 
 
284
        This sorting only ensures that parents come before their children.
 
285
        An ancestor may sort after a descendant if the relationship is not
 
286
        visible in the supplied list of revisions.
 
287
        """
 
288
        subgraph = zip(revisions, self.get_parents(revisions))
 
289
        subgraph = [(r, [p for p in ps if p in revisions])
 
290
                    for r, ps in subgraph]
 
291
        return tsort.topo_sort(subgraph)
 
292
 
278
293
 
279
294
class _BreadthFirstSearcher(object):
280
295
    """Parallel search the breadth-first the ancestry of revisions.