Summary

Add Dijkstra's algorithm and graphutils module

Review Request #7327 — Created May 21, 2015 and submitted May 22, 2015, 9:53 p.m.

Information

Owner

brennie

Repository

Review Board

Branch

dvcs

Bugs

Depends On

Blocks

7328

Commit

f65ae49...

Reviewers

Groups

reviewboard

People

Description

This patch adds the diffviewer.graphutils module which will contain
general purpose graph algorithms, the first of which being Dijkstra's
shortest path algorithm.

Testing Done

Ran unit tests.

Issues

Description	From	Last Updated
Col: 1 W391 blank line at end of file	reviewbot	May 21, 2015, 9:56 p.m.
Can you clarify in here exactly what the input and output formats are supposed to be? I can figure it …	david	May 22, 2015, 5:56 p.m.
Col: 1 E302 expected 2 blank lines, found 1	reviewbot	May 22, 2015, 5:59 p.m.
We should avoid using _ as a variable in any code, since by convention, we're using _ for gettext or …	chipx86	May 22, 2015, 6:30 p.m.
It might be nicer to have one big assert statement (compare distances against a dict that you create).	david	May 22, 2015, 6:30 p.m.
Same here.	david	May 22, 2015, 6:30 p.m.

Tool: Pyflakes
Processed Files:
    reviewboard/diffviewer/graphutils.py



Tool: PEP8 Style Checker
Processed Files:
    reviewboard/diffviewer/graphutils.py

reviewboard/diffviewer/graphutils.py (Diff revision 1)
The issue has been resolved. Show all issues
```
Col: 1
 W391 blank line at end of file
```

Change Summary:

PEP8

Commit:

71a83e0c173c1caabb02d4511db3e3cc98866402

4eafb28253e5db8e37c0a9dd723c9b9182503ec3

Diff:

Revision 2 (+42)

Show changes

reviewboard/diffviewer/graphutils.py

Tool: PEP8 Style Checker
Processed Files:
    reviewboard/diffviewer/graphutils.py



Tool: Pyflakes
Processed Files:
    reviewboard/diffviewer/graphutils.py

```
Unit tests/testing done?
```

reviewboard/diffviewer/graphutils.py (Diff revision 2)

The issue has been resolved. Show all issues

Can you clarify in here exactly what the input and output formats are supposed to be? I can figure it out from the code, but it would be nice to just read it in the comment.

Commit:

4eafb28253e5db8e37c0a9dd723c9b9182503ec3

0811177e0a4cbd75edb4b6cc9b61ce146e7cf486

Diff:

Revision 3 (+99)

Show changes

	reviewboard/diffviewer/graphutils.py
	reviewboard/diffviewer/tests.py

Tool: Pyflakes
Processed Files:
    reviewboard/diffviewer/tests.py
    reviewboard/diffviewer/graphutils.py



Tool: PEP8 Style Checker
Processed Files:
    reviewboard/diffviewer/tests.py
    reviewboard/diffviewer/graphutils.py

reviewboard/diffviewer/tests.py (Diff revision 3)
The issue has been resolved. Show all issues
```
Col: 1
 E302 expected 2 blank lines, found 1
```

Testing Done:: +
Ran unit tests.

Commit:

0811177e0a4cbd75edb4b6cc9b61ce146e7cf486

f4361fdf4f09bf8f367f15c5db436b8343c7398f

Diff:

Revision 4 (+100)

Show changes

	reviewboard/diffviewer/graphutils.py
	reviewboard/diffviewer/tests.py

Tool: Pyflakes
Processed Files:
    reviewboard/diffviewer/tests.py
    reviewboard/diffviewer/graphutils.py



Tool: PEP8 Style Checker
Processed Files:
    reviewboard/diffviewer/tests.py
    reviewboard/diffviewer/graphutils.py

Ship it!

reviewboard/diffviewer/tests.py (Diff revision 4)

The issue has been resolved. Show all issues

It might be nicer to have one big assert statement (compare distances against a dict that you create).

reviewboard/diffviewer/tests.py (Diff revision 4)

The issue has been resolved. Show all issues

Same here.

reviewboard/diffviewer/graphutils.py (Diff revision 4)

The issue has been resolved. Show all issues

We should avoid using _ as a variable in any code, since by convention, we're using _ for gettext or gettext_lazy. Maybe unused?

Change Summary:

Address Christian's and David's issues.

Commit:

f4361fdf4f09bf8f367f15c5db436b8343c7398f

f65ae49002401cddf41fb6a175572f6cc2a95979

Diff:

Revision 5 (+104)

Show changes

	reviewboard/diffviewer/graphutils.py
	reviewboard/diffviewer/tests.py

Tool: Pyflakes
Processed Files:
    reviewboard/diffviewer/tests.py
    reviewboard/diffviewer/graphutils.py



Tool: PEP8 Style Checker
Processed Files:
    reviewboard/diffviewer/tests.py
    reviewboard/diffviewer/graphutils.py

Status:: Completed
Change Summary:: Pushed to dvcs (e736879)