← Back to branch summary

~ubuntu-branches/ubuntu/trusty/python-networkx/trusty

« back to all changes in this revision

Viewing changes to networkx/algorithms/shortest_paths/unweighted.py

  • Committer: Bazaar Package Importer
  • Author(s): Sandro Tosi
  • Date: 2011-03-19 12:19:16 UTC
  • mfrom: (1.2.5 upstream)
  • Revision ID: james.westby@ubuntu.com-20110319121916-xrhlpiwc9sa5e028
Tags: 1.4-1
http://bugs.debian.org/617677
http://bugs.debian.org/608780
* New upstream release; thanks to Yaroslav Halchenko for the report;
  Closes: #617677
* debian/rules
  - don't compress objects.inv; thanks to Michael Fladischer for the report;
    Closes: #608780
* debian/watch
  - updated to point to PyPi
* debian/control
  - bump python-sphinx versioned b-d-i to 1.0.1 minimum
  - added python-pygraphviz to b-d-i, needed for doc building
* debian/copyright
  - bump upstream and packaging copyright years
* debian/patches/{40_add_networkxcss, 50_boundary-test-fix.patch
                  60_remove_svn_refs.diff 70_set_matplotlib_ps_backend.patch}
  - removed since merged upstream
* debian/patches/{10_doc_relocation, 20_example_dirs_remove,
                  30_use_local_objects.inv}
  - refreshed/adapted to new upstream code

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/shortest_paths/unweighted.py
15
15
           'single_source_shortest_path_length',
16
16
           'all_pairs_shortest_path', 
17
17
           'all_pairs_shortest_path_length',
18
 
           'predecessor', 
19
 
           'floyd_warshall']
 
18
           'predecessor'] 
 
19
 
20
20
 
21
21
import networkx as nx
22
22
 
121
121
    path: list
122
122
       List of nodes in a path from source to target.
123
123
 
 
124
    Raises
 
125
    ------
 
126
    NetworkXNoPath
 
127
       If no path exists between source and target.
 
128
 
124
129
    See Also
125
130
    --------
126
131
    shortest_path
131
136
    """
132
137
    # call helper to do the real work
133
138
    results=_bidirectional_pred_succ(G,source,target)
134
 
    if results is False:
135
 
        return False  # no path from source to target
136
139
    pred,succ,w=results
137
140
 
138
141
    # build path from pred+w+succ
199
202
                        reverse_fringe.append(w)
200
203
                    if w in pred:  return pred,succ,w # found path
201
204
 
202
 
 
203
 
 
204
 
    return False  # no path found
 
205
    raise nx.NetworkXNoPath("No path between %s and %s." % (source, target))
205
206
 
206
207
 
207
208
def single_source_shortest_path(G,source,cutoff=None):
232
233
 
233
234
    Notes
234
235
    -----
235
 
    There may be more than one shortest path between the
236
 
    source and target nodes. This function returns only one
237
 
    of them.
 
236
    The shortest path is not necessarily unique. So there can be multiple 
 
237
    paths between the source and each target node, all of which have the 
 
238
    same 'shortest' length. For each target node, this function returns 
 
239
    only one of those paths.
238
240
 
239
241
    See Also
240
242
    --------
291
293
    return paths        
292
294
 
293
295
 
294
 
def floyd_warshall_array(G):
295
 
    """The Floyd-Warshall algorithm for all pairs shortest paths.
296
 
 
297
 
 
298
 
    Parameters
299
 
    ----------
300
 
    G : NetworkX graph
301
 
 
302
 
    Returns
303
 
    -------
304
 
    distance,pred : dictionaries
305
 
       A dictionary, keyed by source and target, of shortest path
306
 
       distance and predecessors in the shortest path.
307
 
 
308
 
    Notes
309
 
    ------
310
 
    This differs from floyd_warshall only in the types of the return
311
 
    values.  Thus, path[i,j] gives the predecessor at j on a path from
312
 
    i to j.  A value of None indicates that no path exists.  A
313
 
    predecessor of i indicates the beginning of the path.  The
314
 
    advantage of this implementation is that, while running time is
315
 
    O(n^3), running space is O(n^2).
316
 
 
317
 
    This algorithm handles negative weights.
318
 
    """
319
 
 
320
 
    # A weight that's more than any path weight
321
 
    HUGE_VAL = 1
322
 
    for u,v,d in G.edges(data=True):
323
 
        HUGE_VAL += abs(d)
324
 
 
325
 
    dist = {}
326
 
    dist_prev = {}
327
 
    pred = {}
328
 
    pred_prev = {}
329
 
    for i in G:
330
 
        dist[i] = {}
331
 
        dist_prev[i] = {}
332
 
        pred[i] = {}
333
 
        pred_prev[i] = {}
334
 
        inbrs=G[i]
335
 
        for j in G:
336
 
            dist[i][j] = 0              # arbitrary, just create slot
337
 
            pred[i][j] = 0              # arbitrary, just create slot
338
 
            if i == j:
339
 
                dist_prev[i][j] = 0
340
 
                pred_prev[i][j] = -1
341
 
            elif j in inbrs:
342
 
                val = inbrs[j]
343
 
                dist_prev[i][j] = val
344
 
                pred_prev[i][j] = i
345
 
            else:
346
 
                # no edge, distinct vertices
347
 
                dist_prev[i][j] = HUGE_VAL
348
 
                pred_prev[i][j] = -1    # None, but has to be numerically comparable
349
 
    for k in G:
350
 
        for i in G:
351
 
            for j in G:
352
 
                dist[i][j] = min(dist_prev[i][j], dist_prev[i][k] + dist_prev[k][j])
353
 
                if dist_prev[i][j] <= dist_prev[i][k] + dist[k][j]:
354
 
                    pred[i][j] = pred_prev[i][j]
355
 
                else:
356
 
                    pred[i][j] = pred_prev[k][j]
357
 
        tmp = dist_prev
358
 
        dist_prev = dist
359
 
        dist = tmp
360
 
 
361
 
        tmp = pred_prev
362
 
        pred_prev = pred
363
 
        pred = tmp
364
 
    # The last time through the loop, we exchanged for nothing, so
365
 
    # return the prev versions, since they're really the current
366
 
    # versions.
367
 
    return dist_prev, pred_prev
368
 
######################################################################
369
 
 
370
 
def floyd_warshall(G):
371
 
    """The Floyd-Warshall algorithm for all pairs shortest paths.
372
 
    
373
 
    Parameters
374
 
    ----------
375
 
    G : NetworkX graph
376
 
 
377
 
    Returns
378
 
    -------
379
 
    distance,pred : dictionaries
380
 
       A dictionary, keyed by source and target, of shortest path
381
 
       distance and predecessors in the shortest path.
382
 
 
383
 
    Notes
384
 
    -----
385
 
    This algorithm is most appropriate for dense graphs.
386
 
    The running time is O(n^3), and running space is O(n^2)
387
 
    where n is the number of nodes in G.  
388
 
 
389
 
    See Also
390
 
    --------
391
 
    all_pairs_shortest_path()
392
 
    all_pairs_shortest_path_length()
393
 
 
394
 
    """
395
 
    huge=1e30000 # sentinal value
396
 
    # dictionary-of-dictionaries representation for dist and pred
397
 
    dist={} 
398
 
    # initialize path distance dictionary to be the adjacency matrix
399
 
    # but with sentinal value "huge" where there is no edge
400
 
    # also set the distance to self to 0 (zero diagonal)
401
 
    pred={}
402
 
    # initialize predecessor dictionary 
403
 
    for u in G:
404
 
        dist[u]={}
405
 
        pred[u]={}
406
 
        unbrs=G[u]
407
 
        for v in G:
408
 
            if v in unbrs:
409
 
                dist[u][v]=unbrs[v].get('weight',1)
410
 
                pred[u][v]=u
411
 
            else:
412
 
                dist[u][v]=huge
413
 
                pred[u][v]=None 
414
 
        dist[u][u]=0  # set 0 distance to self
415
 
 
416
 
    for w in G.nodes():
417
 
        for u in G.nodes():
418
 
            for v in G.nodes():
419
 
                if dist[u][v] > dist[u][w] + dist[w][v]:
420
 
                    dist[u][v] = dist[u][w] + dist[w][v]
421
 
                    pred[u][v] = pred[w][v]
422
 
    return dist,pred
423
296
 
424
297
 
425
298
def predecessor(G,source,target=None,cutoff=None,return_seen=None):