diff options
Diffstat (limited to 'catapult/telemetry/third_party/altgraph/doc/graph.rst')
| -rw-r--r-- | catapult/telemetry/third_party/altgraph/doc/graph.rst | 305 |
1 files changed, 305 insertions, 0 deletions
diff --git a/catapult/telemetry/third_party/altgraph/doc/graph.rst b/catapult/telemetry/third_party/altgraph/doc/graph.rst new file mode 100644 index 00000000..502a2186 --- /dev/null +++ b/catapult/telemetry/third_party/altgraph/doc/graph.rst @@ -0,0 +1,305 @@ +:mod:`altgraph.Graph` --- Basic directional graphs +================================================== + +.. module:: altgraph.Graph + :synopsis: Basic directional graphs. + +The module :mod:`altgraph.Graph` provides a class :class:`Graph` that +represents a directed graph with *N* nodes and *E* edges. + +.. class:: Graph([edges]) + + Constructs a new empty :class:`Graph` object. If the optional + *edges* parameter is supplied, updates the graph by adding the + specified edges. + + All of the elements in *edges* should be tuples with two or three + elements. The first two elements of the tuple are the source and + destination node of the edge, the optional third element is the + edge data. The source and destination nodes are added to the graph + when the aren't already present. + + +Node related methods +-------------------- + +.. method:: Graph.add_node(node[, node_data]) + + Adds a new node to the graph if it is not already present. The new + node must be a hashable object. + + Arbitrary data can be attached to the node via the optional *node_data* + argument. + + .. note:: the node also won't be added to the graph when it is + present but currently hidden. + + +.. method:: Graph.hide_node(node) + + Hides a *node* from the graph. The incoming and outgoing edges of + the node will also be hidden. + + Raises :class:`altgraph.GraphError` when the node is not (visible) + node of the graph. + + +.. method:: Graph.restore_node(node) + + Restores a previously hidden *node*. The incoming and outgoing + edges of the node are also restored. + + Raises :class:`altgraph.GraphError` when the node is not a hidden + node of the graph. + +.. method:: Graph.restore_all_nodes() + + Restores all hidden nodes. + +.. method:: Graph.number_of_nodes() + + Return the number of visible nodes in the graph. + +.. method:: Graph.number_of_hidden_nodes() + + Return the number of hidden nodes in the graph. + +.. method:: Graph.node_list() + + Return a list with all visible nodes in the graph. + +.. method:: Graph.hidden_node_list() + + Return a list with all hidden nodes in the graph. + +.. method:: node_data(node) + + Return the data associated with the *node* when it was + added. + +.. method:: Graph.describe_node(node) + + Returns *node*, the node's data and the lists of outgoing + and incoming edges for the node. + + .. note:: + + the edge lists should not be modified, doing so + can result in unpredicatable behavior. + +.. method:: Graph.__contains__(node) + + Returns True iff *node* is a node in the graph. This + method is accessed through the *in* operator. + +.. method:: Graph.__iter__() + + Yield all nodes in the graph. + +.. method:: Graph.out_edges(node) + + Return the list of outgoing edges for *node* + +.. method:: Graph.inc_edges(node) + + Return the list of incoming edges for *node* + +.. method:: Graph.all_edges(node) + + Return the list of incoming and outgoing edges for *node* + +.. method:: Graph.out_degree(node) + + Return the number of outgoing edges for *node*. + +.. method:: Graph.inc_degree(node) + + Return the number of incoming edges for *node*. + +.. method:: Graph.all_degree(node) + + Return the number of edges (incoming or outgoing) for *node*. + +Edge related methods +-------------------- + +.. method:: Graph.add_edge(head_id, tail_id [, edge data [, create_nodes]]) + + Adds a directed edge from *head_id* to *tail_id*. Arbitrary data can + be added via *edge_data*. When *create_nodes* is *True* (the default), + *head_id* and *tail_id* will be added to the graph when the aren't + already present. + +.. method:: Graph.hide_edge(edge) + + Hides an edge from the graph. The edge may be unhidden at some later + time. + +.. method:: Graph.restore_edge(edge) + + Restores a previously hidden *edge*. + +.. method:: Graph.restore_all_edges() + + Restore all edges that were hidden before, except for edges + referring to hidden nodes. + +.. method:: Graph.edge_by_node(head, tail) + + Return the edge ID for an edge from *head* to *tail*, + or :data:`None` when no such edge exists. + +.. method:: Graph.edge_by_id(edge) + + Return the head and tail of the *edge* + +.. method:: Graph.edge_data(edge) + + Return the data associated with the *edge*. + +.. method:: Graph.update_edge_data(edge, data) + + Replace the edge data for *edge* by *data*. Raises + :exc:`KeyError` when the edge does not exist. + + .. versionadded:: 0.12 + +.. method:: Graph.head(edge) + + Return the head of an *edge* + +.. method:: Graph.tail(edge) + + Return the tail of an *edge* + +.. method:: Graph.describe_edge(edge) + + Return the *edge*, the associated data, its head and tail. + +.. method:: Graph.number_of_edges() + + Return the number of visible edges. + +.. method:: Graph.number_of_hidden_edges() + + Return the number of hidden edges. + +.. method:: Graph.edge_list() + + Returns a list with all visible edges in the graph. + +.. method:: Graph.hidden_edge_list() + + Returns a list with all hidden edges in the graph. + +Graph traversal +--------------- + +.. method:: Graph.out_nbrs(node) + + Return a list of all nodes connected by outgoing edges. + +.. method:: Graph.inc_nbrs(node) + + Return a list of all nodes connected by incoming edges. + +.. method:: Graph.all_nbrs(node) + + Returns a list of nodes connected by an incoming or outgoing edge. + +.. method:: Graph.forw_topo_sort() + + Return a list of nodes where the successors (based on outgoing + edges) of any given node apear in the sequence after that node. + +.. method:: Graph.back_topo_sort() + + Return a list of nodes where the successors (based on incoming + edges) of any given node apear in the sequence after that node. + +.. method:: Graph.forw_bfs_subgraph(start_id) + + Return a subgraph consisting of the breadth first + reachable nodes from *start_id* based on their outgoing edges. + + +.. method:: Graph.back_bfs_subgraph(start_id) + + Return a subgraph consisting of the breadth first + reachable nodes from *start_id* based on their incoming edges. + +.. method:: Graph.iterdfs(start[, end[, forward]]) + + Yield nodes in a depth first traversal starting at the *start* + node. + + If *end* is specified traversal stops when reaching that node. + + If forward is True (the default) edges are traversed in forward + direction, otherwise they are traversed in reverse direction. + +.. method:: Graph.iterdata(start[, end[, forward[, condition]]]) + + Yield the associated data for nodes in a depth first traversal + starting at the *start* node. This method will not yield values for nodes + without associated data. + + If *end* is specified traversal stops when reaching that node. + + If *condition* is specified and the condition callable returns + False for the associated data this method will not yield the + associated data and will not follow the edges for the node. + + If forward is True (the default) edges are traversed in forward + direction, otherwise they are traversed in reverse direction. + +.. method:: Graph.forw_bfs(start[, end]) + + Returns a list of nodes starting at *start* in some bread first + search order (following outgoing edges). + + When *end* is specified iteration stops at that node. + +.. method:: Graph.back_bfs(start[, end]) + + Returns a list of nodes starting at *start* in some bread first + search order (following incoming edges). + + When *end* is specified iteration stops at that node. + +.. method:: Graph.get_hops(start[, end[, forward]]) + + Computes the hop distance to all nodes centered around a specified node. + + First order neighbours are at hop 1, their neigbours are at hop 2 etc. + Uses :py:meth:`forw_bfs` or :py:meth:`back_bfs` depending on the value of + the forward parameter. + + If the distance between all neighbouring nodes is 1 the hop number + corresponds to the shortest distance between the nodes. + + Typical usage:: + + >>> print graph.get_hops(1, 8) + >>> [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)] + # node 1 is at 0 hops + # node 2 is at 1 hop + # ... + # node 8 is at 5 hops + + +Graph statistics +---------------- + +.. method:: Graph.connected() + + Returns True iff every node in the graph can be reached from + every other node. + +.. method:: Graph.clust_coef(node) + + Returns the local clustering coefficient of node. + + The local cluster coefficient is the proportion of the actual number + of edges between neighbours of node and the maximum number of + edges between those nodes. |