diff options
Diffstat (limited to 'catapult/telemetry/third_party/altgraph/altgraph/Graph.py')
| -rw-r--r-- | catapult/telemetry/third_party/altgraph/altgraph/Graph.py | 677 |
1 files changed, 677 insertions, 0 deletions
diff --git a/catapult/telemetry/third_party/altgraph/altgraph/Graph.py b/catapult/telemetry/third_party/altgraph/altgraph/Graph.py new file mode 100644 index 00000000..491e5c22 --- /dev/null +++ b/catapult/telemetry/third_party/altgraph/altgraph/Graph.py @@ -0,0 +1,677 @@ +""" +altgraph.Graph - Base Graph class +================================= + +.. + #--Version 2.1 + #--Bob Ippolito October, 2004 + + #--Version 2.0 + #--Istvan Albert June, 2004 + + #--Version 1.0 + #--Nathan Denny, May 27, 1999 +""" + +from altgraph import GraphError +from collections import deque + +class Graph(object): + """ + The Graph class represents a directed graph with *N* nodes and *E* edges. + + Naming conventions: + + - the prefixes such as *out*, *inc* and *all* will refer to methods + that operate on the outgoing, incoming or all edges of that node. + + For example: :py:meth:`inc_degree` will refer to the degree of the node + computed over the incoming edges (the number of neighbours linking to + the node). + + - the prefixes such as *forw* and *back* will refer to the + orientation of the edges used in the method with respect to the node. + + For example: :py:meth:`forw_bfs` will start at the node then use the outgoing + edges to traverse the graph (goes forward). + """ + + def __init__(self, edges=None): + """ + Initialization + """ + + self.next_edge = 0 + self.nodes, self.edges = {}, {} + self.hidden_edges, self.hidden_nodes = {}, {} + + if edges is not None: + for item in edges: + if len(item) == 2: + head, tail = item + self.add_edge(head, tail) + elif len(item) == 3: + head, tail, data = item + self.add_edge(head, tail, data) + else: + raise GraphError("Cannot create edge from %s"%(item,)) + + + def __repr__(self): + return '<Graph: %d nodes, %d edges>' % ( + self.number_of_nodes(), self.number_of_edges()) + + def add_node(self, node, node_data=None): + """ + Adds a new node to the graph. Arbitrary data can be attached to the + node via the node_data parameter. Adding the same node twice will be + silently ignored. + + The node must be a hashable value. + """ + # + # the nodes will contain tuples that will store incoming edges, + # outgoing edges and data + # + # index 0 -> incoming edges + # index 1 -> outgoing edges + + if node in self.hidden_nodes: + # Node is present, but hidden + return + + if node not in self.nodes: + self.nodes[node] = ([], [], node_data) + + def add_edge(self, head_id, tail_id, edge_data=1, create_nodes=True): + """ + Adds a directed edge going from head_id to tail_id. + Arbitrary data can be attached to the edge via edge_data. + It may create the nodes if adding edges between nonexisting ones. + + :param head_id: head node + :param tail_id: tail node + :param edge_data: (optional) data attached to the edge + :param create_nodes: (optional) creates the head_id or tail_id node in case they did not exist + """ + # shorcut + edge = self.next_edge + + # add nodes if on automatic node creation + if create_nodes: + self.add_node(head_id) + self.add_node(tail_id) + + # update the corresponding incoming and outgoing lists in the nodes + # index 0 -> incoming edges + # index 1 -> outgoing edges + + try: + self.nodes[tail_id][0].append(edge) + self.nodes[head_id][1].append(edge) + except KeyError: + raise GraphError('Invalid nodes %s -> %s' % (head_id, tail_id)) + + # store edge information + self.edges[edge] = (head_id, tail_id, edge_data) + + + self.next_edge += 1 + + def hide_edge(self, edge): + """ + Hides an edge from the graph. The edge may be unhidden at some later + time. + """ + try: + head_id, tail_id, edge_data = self.hidden_edges[edge] = self.edges[edge] + self.nodes[tail_id][0].remove(edge) + self.nodes[head_id][1].remove(edge) + del self.edges[edge] + except KeyError: + raise GraphError('Invalid edge %s' % edge) + + def hide_node(self, node): + """ + Hides a node from the graph. The incoming and outgoing edges of the + node will also be hidden. The node may be unhidden at some later time. + """ + try: + all_edges = self.all_edges(node) + self.hidden_nodes[node] = (self.nodes[node], all_edges) + for edge in all_edges: + self.hide_edge(edge) + del self.nodes[node] + except KeyError: + raise GraphError('Invalid node %s' % node) + + def restore_node(self, node): + """ + Restores a previously hidden node back into the graph and restores + all of its incoming and outgoing edges. + """ + try: + self.nodes[node], all_edges = self.hidden_nodes[node] + for edge in all_edges: + self.restore_edge(edge) + del self.hidden_nodes[node] + except KeyError: + raise GraphError('Invalid node %s' % node) + + def restore_edge(self, edge): + """ + Restores a previously hidden edge back into the graph. + """ + try: + head_id, tail_id, data = self.hidden_edges[edge] + self.nodes[tail_id][0].append(edge) + self.nodes[head_id][1].append(edge) + self.edges[edge] = head_id, tail_id, data + del self.hidden_edges[edge] + except KeyError: + raise GraphError('Invalid edge %s' % edge) + + def restore_all_edges(self): + """ + Restores all hidden edges. + """ + for edge in list(self.hidden_edges.keys()): + try: + self.restore_edge(edge) + except GraphError: + pass + + def restore_all_nodes(self): + """ + Restores all hidden nodes. + """ + for node in list(self.hidden_nodes.keys()): + self.restore_node(node) + + def __contains__(self, node): + """ + Test whether a node is in the graph + """ + return node in self.nodes + + def edge_by_id(self, edge): + """ + Returns the edge that connects the head_id and tail_id nodes + """ + try: + head, tail, data = self.edges[edge] + except KeyError: + head, tail = None, None + raise GraphError('Invalid edge %s' % edge) + + return (head, tail) + + def edge_by_node(self, head, tail): + """ + Returns the edge that connects the head_id and tail_id nodes + """ + for edge in self.out_edges(head): + if self.tail(edge) == tail: + return edge + return None + + def number_of_nodes(self): + """ + Returns the number of nodes + """ + return len(self.nodes) + + def number_of_edges(self): + """ + Returns the number of edges + """ + return len(self.edges) + + def __iter__(self): + """ + Iterates over all nodes in the graph + """ + return iter(self.nodes) + + def node_list(self): + """ + Return a list of the node ids for all visible nodes in the graph. + """ + return list(self.nodes.keys()) + + def edge_list(self): + """ + Returns an iterator for all visible nodes in the graph. + """ + return list(self.edges.keys()) + + def number_of_hidden_edges(self): + """ + Returns the number of hidden edges + """ + return len(self.hidden_edges) + + def number_of_hidden_nodes(self): + """ + Returns the number of hidden nodes + """ + return len(self.hidden_nodes) + + def hidden_node_list(self): + """ + Returns the list with the hidden nodes + """ + return list(self.hidden_nodes.keys()) + + def hidden_edge_list(self): + """ + Returns a list with the hidden edges + """ + return list(self.hidden_edges.keys()) + + def describe_node(self, node): + """ + return node, node data, outgoing edges, incoming edges for node + """ + incoming, outgoing, data = self.nodes[node] + return node, data, outgoing, incoming + + def describe_edge(self, edge): + """ + return edge, edge data, head, tail for edge + """ + head, tail, data = self.edges[edge] + return edge, data, head, tail + + def node_data(self, node): + """ + Returns the data associated with a node + """ + return self.nodes[node][2] + + def edge_data(self, edge): + """ + Returns the data associated with an edge + """ + return self.edges[edge][2] + + def update_edge_data(self, edge, edge_data): + """ + Replace the edge data for a specific edge + """ + self.edges[edge] = self.edges[edge][0:2] + (edge_data,) + + def head(self, edge): + """ + Returns the node of the head of the edge. + """ + return self.edges[edge][0] + + def tail(self, edge): + """ + Returns node of the tail of the edge. + """ + return self.edges[edge][1] + + def out_nbrs(self, node): + """ + List of nodes connected by outgoing edges + """ + l = [self.tail(n) for n in self.out_edges(node)] + return l + + def inc_nbrs(self, node): + """ + List of nodes connected by incoming edges + """ + l = [self.head(n) for n in self.inc_edges(node)] + return l + + def all_nbrs(self, node): + """ + List of nodes connected by incoming and outgoing edges + """ + l = dict.fromkeys( self.inc_nbrs(node) + self.out_nbrs(node) ) + return list(l) + + def out_edges(self, node): + """ + Returns a list of the outgoing edges + """ + try: + return list(self.nodes[node][1]) + except KeyError: + raise GraphError('Invalid node %s' % node) + + return None + + def inc_edges(self, node): + """ + Returns a list of the incoming edges + """ + try: + return list(self.nodes[node][0]) + except KeyError: + raise GraphError('Invalid node %s' % node) + + return None + + def all_edges(self, node): + """ + Returns a list of incoming and outging edges. + """ + return set(self.inc_edges(node) + self.out_edges(node)) + + def out_degree(self, node): + """ + Returns the number of outgoing edges + """ + return len(self.out_edges(node)) + + def inc_degree(self, node): + """ + Returns the number of incoming edges + """ + return len(self.inc_edges(node)) + + def all_degree(self, node): + """ + The total degree of a node + """ + return self.inc_degree(node) + self.out_degree(node) + + def _topo_sort(self, forward=True): + """ + Topological sort. + + Returns a list of nodes where the successors (based on outgoing and + incoming edges selected by the forward parameter) of any given node + appear in the sequence after that node. + """ + topo_list = [] + queue = deque() + indeg = {} + + # select the operation that will be performed + if forward: + get_edges = self.out_edges + get_degree = self.inc_degree + get_next = self.tail + else: + get_edges = self.inc_edges + get_degree = self.out_degree + get_next = self.head + + for node in self.node_list(): + degree = get_degree(node) + if degree: + indeg[node] = degree + else: + queue.append(node) + + while queue: + curr_node = queue.popleft() + topo_list.append(curr_node) + for edge in get_edges(curr_node): + tail_id = get_next(edge) + if tail_id in indeg: + indeg[tail_id] -= 1 + if indeg[tail_id] == 0: + queue.append(tail_id) + + if len(topo_list) == len(self.node_list()): + valid = True + else: + # the graph has cycles, invalid topological sort + valid = False + + return (valid, topo_list) + + def forw_topo_sort(self): + """ + Topological sort. + + Returns a list of nodes where the successors (based on outgoing edges) + of any given node appear in the sequence after that node. + """ + return self._topo_sort(forward=True) + + def back_topo_sort(self): + """ + Reverse topological sort. + + Returns a list of nodes where the successors (based on incoming edges) + of any given node appear in the sequence after that node. + """ + return self._topo_sort(forward=False) + + def _bfs_subgraph(self, start_id, forward=True): + """ + Private method creates a subgraph in a bfs order. + + The forward parameter specifies whether it is a forward or backward + traversal. + """ + if forward: + get_bfs = self.forw_bfs + get_nbrs = self.out_nbrs + else: + get_bfs = self.back_bfs + get_nbrs = self.inc_nbrs + + g = Graph() + bfs_list = get_bfs(start_id) + for node in bfs_list: + g.add_node(node) + + for node in bfs_list: + for nbr_id in get_nbrs(node): + g.add_edge(node, nbr_id) + + return g + + def forw_bfs_subgraph(self, start_id): + """ + Creates and returns a subgraph consisting of the breadth first + reachable nodes based on their outgoing edges. + """ + return self._bfs_subgraph(start_id, forward=True) + + def back_bfs_subgraph(self, start_id): + """ + Creates and returns a subgraph consisting of the breadth first + reachable nodes based on the incoming edges. + """ + return self._bfs_subgraph(start_id, forward=False) + + def iterdfs(self, start, end=None, forward=True): + """ + Collecting nodes in some depth first traversal. + + The forward parameter specifies whether it is a forward or backward + traversal. + """ + visited, stack = set([start]), deque([start]) + + if forward: + get_edges = self.out_edges + get_next = self.tail + else: + get_edges = self.inc_edges + get_next = self.head + + while stack: + curr_node = stack.pop() + yield curr_node + if curr_node == end: + break + for edge in sorted(get_edges(curr_node)): + tail = get_next(edge) + if tail not in visited: + visited.add(tail) + stack.append(tail) + + def iterdata(self, start, end=None, forward=True, condition=None): + """ + Perform a depth-first walk of the graph (as ``iterdfs``) + and yield the item data of every node where condition matches. The + condition callback is only called when node_data is not None. + """ + + visited, stack = set([start]), deque([start]) + + if forward: + get_edges = self.out_edges + get_next = self.tail + else: + get_edges = self.inc_edges + get_next = self.head + + get_data = self.node_data + + while stack: + curr_node = stack.pop() + curr_data = get_data(curr_node) + if curr_data is not None: + if condition is not None and not condition(curr_data): + continue + yield curr_data + if curr_node == end: + break + for edge in get_edges(curr_node): + tail = get_next(edge) + if tail not in visited: + visited.add(tail) + stack.append(tail) + + def _iterbfs(self, start, end=None, forward=True): + """ + The forward parameter specifies whether it is a forward or backward + traversal. Returns a list of tuples where the first value is the hop + value the second value is the node id. + """ + queue, visited = deque([(start, 0)]), set([start]) + + # the direction of the bfs depends on the edges that are sampled + if forward: + get_edges = self.out_edges + get_next = self.tail + else: + get_edges = self.inc_edges + get_next = self.head + + while queue: + curr_node, curr_step = queue.popleft() + yield (curr_node, curr_step) + if curr_node == end: + break + for edge in get_edges(curr_node): + tail = get_next(edge) + if tail not in visited: + visited.add(tail) + queue.append((tail, curr_step + 1)) + + + def forw_bfs(self, start, end=None): + """ + Returns a list of nodes in some forward BFS order. + + Starting from the start node the breadth first search proceeds along + outgoing edges. + """ + return [node for node, step in self._iterbfs(start, end, forward=True)] + + def back_bfs(self, start, end=None): + """ + Returns a list of nodes in some backward BFS order. + + Starting from the start node the breadth first search proceeds along + incoming edges. + """ + return [node for node, step in self._iterbfs(start, end, forward=False)] + + def forw_dfs(self, start, end=None): + """ + Returns a list of nodes in some forward DFS order. + + Starting with the start node the depth first search proceeds along + outgoing edges. + """ + return list(self.iterdfs(start, end, forward=True)) + + def back_dfs(self, start, end=None): + """ + Returns a list of nodes in some backward DFS order. + + Starting from the start node the depth first search proceeds along + incoming edges. + """ + return list(self.iterdfs(start, end, forward=False)) + + def connected(self): + """ + Returns :py:data:`True` if the graph's every node can be reached from every + other node. + """ + node_list = self.node_list() + for node in node_list: + bfs_list = self.forw_bfs(node) + if len(bfs_list) != len(node_list): + return False + return True + + def clust_coef(self, node): + """ + Computes and returns the local clustering coefficient of node. The + local cluster coefficient is proportion of the actual number of edges between + neighbours of node and the maximum number of edges between those neighbours. + + See <http://en.wikipedia.org/wiki/Clustering_coefficient#Local_clustering_coefficient> + for a formal definition. + """ + num = 0 + nbr_set = set(self.out_nbrs(node)) + + if node in nbr_set: + nbr_set.remove(node) # loop defense + + for nbr in nbr_set: + sec_set = set(self.out_nbrs(nbr)) + if nbr in sec_set: + sec_set.remove(nbr) # loop defense + num += len(nbr_set & sec_set) + + nbr_num = len(nbr_set) + if nbr_num: + clust_coef = float(num) / (nbr_num * (nbr_num - 1)) + else: + clust_coef = 0.0 + return clust_coef + + def get_hops(self, start, end=None, forward=True): + """ + 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. + + :param start: the starting node + :param end: ending node (optional). When not specified will search the whole graph. + :param forward: directionality parameter (optional). If C{True} (default) it uses L{forw_bfs} otherwise L{back_bfs}. + :return: returns a list of tuples where each tuple contains the node and the hop. + + 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 + """ + if forward: + return list(self._iterbfs(start=start, end=end, forward=True)) + else: + return list(self._iterbfs(start=start, end=end, forward=False)) |