1:mod:`altgraph.Graph` --- Basic directional graphs
2==================================================
3
4.. module:: altgraph.Graph
5   :synopsis: Basic directional graphs.
6
7The module :mod:`altgraph.Graph` provides a class :class:`Graph` that
8represents 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
23Node 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
123Edge 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
195Graph 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
291Graph 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