/usr/lib/python2.7/dist-packages/dipy/core/graph.py is in python-dipy 0.10.1-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | """ A simple graph class """
from __future__ import division, print_function, absolute_import
class Graph(object):
''' A simple graph class
'''
def __init__(self):
''' A graph class with nodes and edges :-)
This class allows us to:
1. find the shortest path
2. find all paths
3. add/delete nodes and edges
4. get parent & children nodes
Examples
--------
>>> from dipy.core.graph import Graph
>>> g=Graph()
>>> g.add_node('a',5)
>>> g.add_node('b',6)
>>> g.add_node('c',10)
>>> g.add_node('d',11)
>>> g.add_edge('a','b')
>>> g.add_edge('b','c')
>>> g.add_edge('c','d')
>>> g.add_edge('b','d')
>>> g.up_short('d')
['d', 'b', 'a']
'''
self.node={}
self.pred={}
self.succ={}
def add_node(self,n,attr=None):
self.succ[n]={}
self.pred[n]={}
self.node[n]=attr
def add_edge(self,n,m,ws=True,wp=True):
self.succ[n][m]=ws
self.pred[m][n]=wp
def parents(self,n):
return self.pred[n].keys()
def children(self,n):
return self.succ[n].keys()
def up(self, n):
return self.all_paths(self.pred,n)
def down(self, n):
return self.all_paths(self.succ,n)
def up_short(self,n):
return self.shortest_path(self.pred,n)
def down_short(self,n):
return self.shortest_path(self.succ,n)
def all_paths(self,graph, start, end=None, path=[]):
path = path + [start]
if start==end or graph[start]=={}:
return [path]
if not start in graph:
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = self.all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
def shortest_path(self,graph, start, end=None, path=[]):
path = path + [start]
if graph[start]=={} or start == end:
return path
if not start in graph:
return []
shortest = None
for node in graph[start]:
if node not in path:
newpath = self.shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
def del_node_and_edges(self,n):
try:
del self.node[n]
except KeyError:
raise KeyError('node not in the graph')
for s in self.succ[n]:
del self.pred[s][n]
del self.succ[n]
for p in self.pred[n]:
del self.succ[p][n]
del self.pred[n]
def del_node(self,n):
try:
del self.node[n]
except KeyError:
raise KeyError('node not in the graph')
for s in self.succ[n]:
for p in self.pred[n]:
self.succ[p][s]=self.succ[n][s]
self.pred[s][p]=self.pred[s][n]
for s in self.succ.keys():
try:
del self.succ[s][n]
except KeyError:
pass
for p in self.pred.keys():
try:
del self.pred[p][n]
except KeyError:
pass
del self.succ[n]
del self.pred[n]
|