graph.py

属性sosuo算法

"""
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 compat import *

class Graph(object):
    """
    The Graph class represents a directed graph with C{N} nodes and C{E} edges.

    Naming conventions:
        - the prefixes such asC{out}, C{inc} and C{all} will refer to methods
        that operate on the outgoing, incoming or all edges of that node.
        For example: L{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 C{forw} and C{back} will refer to the
        orientation of the edges used in the method with respect to the node.
        For example: L{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 = {}, {}

        try:
            # instantiate graph from iterable data
            if edges:
                cols = len(edges[0])
                if cols == 2:
                    for head, tail in edges:
                        self.add_edge(head, tail)
                elif cols == 3:
                    for head, tail, data in edges:
                        self.add_edge(head, tail, data)
        except Exception, exc:
            raise GraphError('%s -> Cannot create graph from edges=%s' %
                (exc, edges))

    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):
        """
        Creates a new node with a node.  Arbitrary data can be attached to the
        node via the node_data parameter.  Adding the same node twice will be
        silently ignored.
        """
        #
        # the nodes will contain tuples that will store incoming edges,
        # outgoing edges and data
        #
        # index 0 -> incoming edges
        # index 1 -> outgoing edges
        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)

        # store edge information
        self.edges[edge] = (head_id, tail_id, edge_data)

        # 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))

        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:
            self.edges[edge] = head_id, tail_id, data = self.hidden_edges[edge]
            self.nodes[tail_id][0].append(edge)
            self.nodes[head_id][1].append(edge)
            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 self.hidden_edges.keys():
            self.restore_edge(edge)

    def restore_all_nodes(self):
        """
        Restores all hidden nodes.
        """
        for node in 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 self.nodes.keys()

    def edge_list(self):
        """
        Returns an iterator for all visible nodes in the graph.
        """
        return 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 self.hidden_nodes.keys()

    def hidden_edge_list(self):
        """
        Returns a list with the hidden edges
        """
        return 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 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
        """
        return map(self.tail, self.out_edges(node))

    def inc_nbrs(self, node):
        """
        List of nodes connected by incoming edges
        """
        return map(self.head, self.inc_edges(node))

    def all_nbrs(self, node):
        """
        List of nodes connected by incoming and outgoing edges
        """
        return self.inc_nbrs(node) + self.out_nbrs(node)

    def out_edges(self, node):
        """