graph.py

属性sosuo算法

        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
        else:
            get_edges = self.inc_edges
            get_degree = self.out_degree

        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 = self.tail(edge)
                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 (hop_num, node) in bfs_list:
            g.add_node(node)

        for (hop_num, 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=True)

    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
        else:
            get_edges = self.inc_edges

        while stack:
            curr_node = stack.pop()
            yield curr_node
            if curr_node == end:
                break
            for edge in get_edges(curr_node):
                tail = self.tail(edge)
                if tail not in visited:
                    visited.add(tail)
                    stack.append(tail)

    def iterdata(self, start, end=None, forward=True, condition=None):
        visited, stack = set([start]), deque([start])

        if forward:
            get_edges = self.out_edges
        else:
            get_edges = self.inc_edges

        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 = self.tail(edge)
                if tail not in visited:
                    visited.add(tail)
                    stack.append(tail)

    def _dfs(self, start, end=None, forward=True):
        return list(self.iterdfs(start, end=end, forward=forward))

    def _iterbfs(self, start, end=None, forward=True):
        """
        Private method, collecting nodes in some breadth first traversal.
        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
        else:
            get_edges = self.inc_edges

        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 = self.tail(edge)
                if tail not in visited:
                    visited.add(tail)
                    queue.append((tail, curr_step + 1))

    def _bfs(self, start, end=None, forward=True):
        return list(self._iterbfs(start, end=end, forward=forward))

    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._bfs(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._bfs(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 self._dfs(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 self._dfs(start, end, forward=False)

    def connected(self):
        """
        Returns C{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 clustering coefficient of node. The clustering
        coeffcient is defined as ...
        """
        num = 0
        nbr_set = set(self.out_nbrs(node))
        nbr_set.remove(node) # loop defense

        for nbr in nbr_set:
            sec_set = set(self.out_nbrs(nbr))
            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 L{forw_bfs} or L{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 self._bfs(start=start, end=end, forward=True)
        else:
            return self._bfs(start=start, end=end, forward=False)