1 :mod:`altgraph.Graph` --- Basic directional graphs 2 ================================================== 3 4 .. module:: altgraph.Graph 5 :synopsis: Basic directional graphs. 6 7 The module :mod:`altgraph.Graph` provides a class :class:`Graph` that 8 represents a directed graph with *N* nodes and *E* edges. 9 10 .. class:: Graph([edges]) 11 12 Constructs a new empty :class:`Graph` object. If the optional 13 *edges* parameter is supplied, updates the graph by adding the 14 specified edges. 15 16 All of the elements in *edges* should be tuples with two or three 17 elements. The first two elements of the tuple are the source and 18 destination node of the edge, the optional third element is the 19 edge data. The source and destination nodes are added to the graph 20 when the aren't already present. 21 22 23 Node related methods 24 -------------------- 25 26 .. method:: Graph.add_node(node[, node_data]) 27 28 Adds a new node to the graph if it is not already present. The new 29 node must be a hashable object. 30 31 Arbitrary data can be attached to the node via the optional *node_data* 32 argument. 33 34 .. note:: the node also won't be added to the graph when it is 35 present but currently hidden. 36 37 38 .. method:: Graph.hide_node(node) 39 40 Hides a *node* from the graph. The incoming and outgoing edges of 41 the node will also be hidden. 42 43 Raises :class:`altgraph.GraphError` when the node is not (visible) 44 node of the graph. 45 46 47 .. method:: Graph.restore_node(node) 48 49 Restores a previously hidden *node*. The incoming and outgoing 50 edges of the node are also restored. 51 52 Raises :class:`altgraph.GraphError` when the node is not a hidden 53 node of the graph. 54 55 .. method:: Graph.restore_all_nodes() 56 57 Restores all hidden nodes. 58 59 .. method:: Graph.number_of_nodes() 60 61 Return the number of visible nodes in the graph. 62 63 .. method:: Graph.number_of_hidden_nodes() 64 65 Return the number of hidden nodes in the graph. 66 67 .. method:: Graph.node_list() 68 69 Return a list with all visible nodes in the graph. 70 71 .. method:: Graph.hidden_node_list() 72 73 Return a list with all hidden nodes in the graph. 74 75 .. method:: node_data(node) 76 77 Return the data associated with the *node* when it was 78 added. 79 80 .. method:: Graph.describe_node(node) 81 82 Returns *node*, the node's data and the lists of outgoing 83 and incoming edges for the node. 84 85 .. note:: 86 87 the edge lists should not be modified, doing so 88 can result in unpredicatable behavior. 89 90 .. method:: Graph.__contains__(node) 91 92 Returns True iff *node* is a node in the graph. This 93 method is accessed through the *in* operator. 94 95 .. method:: Graph.__iter__() 96 97 Yield all nodes in the graph. 98 99 .. method:: Graph.out_edges(node) 100 101 Return the list of outgoing edges for *node* 102 103 .. method:: Graph.inc_edges(node) 104 105 Return the list of incoming edges for *node* 106 107 .. method:: Graph.all_edges(node) 108 109 Return the list of incoming and outgoing edges for *node* 110 111 .. method:: Graph.out_degree(node) 112 113 Return the number of outgoing edges for *node*. 114 115 .. method:: Graph.inc_degree(node) 116 117 Return the number of incoming edges for *node*. 118 119 .. method:: Graph.all_degree(node) 120 121 Return the number of edges (incoming or outgoing) for *node*. 122 123 Edge related methods 124 -------------------- 125 126 .. method:: Graph.add_edge(head_id, tail_id [, edge data [, create_nodes]]) 127 128 Adds a directed edge from *head_id* to *tail_id*. Arbitrary data can 129 be added via *edge_data*. When *create_nodes* is *True* (the default), 130 *head_id* and *tail_id* will be added to the graph when the aren't 131 already present. 132 133 .. method:: Graph.hide_edge(edge) 134 135 Hides an edge from the graph. The edge may be unhidden at some later 136 time. 137 138 .. method:: Graph.restore_edge(edge) 139 140 Restores a previously hidden *edge*. 141 142 .. method:: Graph.restore_all_edges() 143 144 Restore all edges that were hidden before, except for edges 145 referring to hidden nodes. 146 147 .. method:: Graph.edge_by_node(head, tail) 148 149 Return the edge ID for an edge from *head* to *tail*, 150 or :data:`None` when no such edge exists. 151 152 .. method:: Graph.edge_by_id(edge) 153 154 Return the head and tail of the *edge* 155 156 .. method:: Graph.edge_data(edge) 157 158 Return the data associated with the *edge*. 159 160 .. method:: Graph.update_edge_data(edge, data) 161 162 Replace the edge data for *edge* by *data*. Raises 163 :exc:`KeyError` when the edge does not exist. 164 165 .. versionadded:: 0.12 166 167 .. method:: Graph.head(edge) 168 169 Return the head of an *edge* 170 171 .. method:: Graph.tail(edge) 172 173 Return the tail of an *edge* 174 175 .. method:: Graph.describe_edge(edge) 176 177 Return the *edge*, the associated data, its head and tail. 178 179 .. method:: Graph.number_of_edges() 180 181 Return the number of visible edges. 182 183 .. method:: Graph.number_of_hidden_edges() 184 185 Return the number of hidden edges. 186 187 .. method:: Graph.edge_list() 188 189 Returns a list with all visible edges in the graph. 190 191 .. method:: Graph.hidden_edge_list() 192 193 Returns a list with all hidden edges in the graph. 194 195 Graph traversal 196 --------------- 197 198 .. method:: Graph.out_nbrs(node) 199 200 Return a list of all nodes connected by outgoing edges. 201 202 .. method:: Graph.inc_nbrs(node) 203 204 Return a list of all nodes connected by incoming edges. 205 206 .. method:: Graph.all_nbrs(node) 207 208 Returns a list of nodes connected by an incoming or outgoing edge. 209 210 .. method:: Graph.forw_topo_sort() 211 212 Return a list of nodes where the successors (based on outgoing 213 edges) of any given node apear in the sequence after that node. 214 215 .. method:: Graph.back_topo_sort() 216 217 Return a list of nodes where the successors (based on incoming 218 edges) of any given node apear in the sequence after that node. 219 220 .. method:: Graph.forw_bfs_subgraph(start_id) 221 222 Return a subgraph consisting of the breadth first 223 reachable nodes from *start_id* based on their outgoing edges. 224 225 226 .. method:: Graph.back_bfs_subgraph(start_id) 227 228 Return a subgraph consisting of the breadth first 229 reachable nodes from *start_id* based on their incoming edges. 230 231 .. method:: Graph.iterdfs(start[, end[, forward]]) 232 233 Yield nodes in a depth first traversal starting at the *start* 234 node. 235 236 If *end* is specified traversal stops when reaching that node. 237 238 If forward is True (the default) edges are traversed in forward 239 direction, otherwise they are traversed in reverse direction. 240 241 .. method:: Graph.iterdata(start[, end[, forward[, condition]]]) 242 243 Yield the associated data for nodes in a depth first traversal 244 starting at the *start* node. This method will not yield values for nodes 245 without associated data. 246 247 If *end* is specified traversal stops when reaching that node. 248 249 If *condition* is specified and the condition callable returns 250 False for the associated data this method will not yield the 251 associated data and will not follow the edges for the node. 252 253 If forward is True (the default) edges are traversed in forward 254 direction, otherwise they are traversed in reverse direction. 255 256 .. method:: Graph.forw_bfs(start[, end]) 257 258 Returns a list of nodes starting at *start* in some bread first 259 search order (following outgoing edges). 260 261 When *end* is specified iteration stops at that node. 262 263 .. method:: Graph.back_bfs(start[, end]) 264 265 Returns a list of nodes starting at *start* in some bread first 266 search order (following incoming edges). 267 268 When *end* is specified iteration stops at that node. 269 270 .. method:: Graph.get_hops(start[, end[, forward]]) 271 272 Computes the hop distance to all nodes centered around a specified node. 273 274 First order neighbours are at hop 1, their neigbours are at hop 2 etc. 275 Uses :py:meth:`forw_bfs` or :py:meth:`back_bfs` depending on the value of 276 the forward parameter. 277 278 If the distance between all neighbouring nodes is 1 the hop number 279 corresponds to the shortest distance between the nodes. 280 281 Typical usage:: 282 283 >>> print graph.get_hops(1, 8) 284 >>> [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)] 285 # node 1 is at 0 hops 286 # node 2 is at 1 hop 287 # ... 288 # node 8 is at 5 hops 289 290 291 Graph statistics 292 ---------------- 293 294 .. method:: Graph.connected() 295 296 Returns True iff every node in the graph can be reached from 297 every other node. 298 299 .. method:: Graph.clust_coef(node) 300 301 Returns the local clustering coefficient of node. 302 303 The local cluster coefficient is the proportion of the actual number 304 of edges between neighbours of node and the maximum number of 305 edges between those nodes. 306
