1. Ronald Oussoren
  2. pyobjc

Commits

Ronald Oussoren  committed 0845ced

Altgraph is not needed here, this was a copy of the trunk of altgraph.

  • Participants
  • Parent commits 44357b0
  • Branches pyobjc-ancient

Comments (0)

Files changed (13)

File altgraph/altgraph/Dot.py

  • Ignore whitespace
-'''
-Interface to the dot language
-=============================
-
-The B{Dot} module provides a simple interface to the
-file format used in the U{graphviz<http://www.research.att.com/sw/tools/graphviz/>}
-program. The module is intended to offload the most tedious part of the process
-(the B{dot} file generation) while transparently exposing most of its features.
-
-To display the graphs or to generate image files the U{graphviz<http://www.research.att.com/sw/tools/graphviz/>}
-package needs to be installed on the system, moreover the C{dot} and C{dotty} programs must
-be accesible in the program path so that they can be ran from processes spawned
-within the module. See the L{Dot} documentation for further information on the setup.
-
-Example usage
--------------
-
-Here is a typical usage::
-
-    from altgraph import Graph, Dot
-
-    # create a graph
-    edges = [ (1,2), (1,3), (3,4), (3,5), (4,5), (5,4) ]
-    graph = Graph.Graph(edges)
-
-    # create a dot representation of the graph
-    dot = Dot.Dot(graph)
-
-    # display the graph
-    dot.display()
-
-    # save the dot representation into the mydot.dot file
-    dot.save_dot(file_name='mydot.dot')
-
-    # save dot file as gif image into the graph.gif file
-    dot.save_img(file_name='graph', file_type='gif')
-
-Customizing the output
-----------------------
-
-The graph drawing process may be customized by passing
-valid B{dot} parameters for the nodes and edges. For a list of all
-parameters see the U{graphviz<http://www.research.att.com/sw/tools/graphviz/>}
-documentation.
-
-Example::
-    # customizing the way the overall graph is drawn
-    dot.style(size='10,10', rankdir='RL', page='5, 5' , ranksep=0.75)
-
-    # customizing node drawing
-    dot.node_style(1, label='BASE_NODE',shape='box', color='blue' )
-    dot.node_style(2, style='filled', fillcolor='red')
-
-    # customizing edge drawing
-    dot.edge_style(1, 2, style='dotted')
-    dot.edge_style(3, 5, arrowhead='dot', label='binds', labelangle='90')
-    dot.edge_style(4, 5, arrowsize=2, style='bold')
-
-B{Observation}: dotty (invoked via L{Dot.display}) may not be able to
-display all graphics styles. To verify the output save it to an image file
-and look at it that way.
-
-Valid attributes
-----------------
-
-    - dot styles, passed via the L{Dot.style} method::
-        rankdir = 'LR'   (draws the graph horizontally, left to right)
-        ranksep = number (rank separation in inches)
-
-    - node attributes, passed via the L{Dot.node_style} method::
-        style = 'filled' | 'invisible' | 'diagonals' | 'rounded'
-        shape = 'box' | 'ellipse' | 'circle' | 'point' | 'triangle'
-
-    - edge attributes, passed via the L{Dot.edge_style} method::
-        style     = 'dashed' | 'dotted' | 'solid' | 'invis' | 'bold'
-        arrowhead = 'box' | 'crow' | 'diamond' | 'dot' | 'inv' | 'none' | 'tee' | 'vee'
-        weight    = number (the larger the number the closer the nodes will be)
-
-    - valid U{graphviz colors<http://www.research.att.com/~erg/graphviz/info/colors.html>}
-
-    - for more details on how to control the graph drawing process see the
-    U{graphviz reference <http://www.research.att.com/sw/tools/graphviz/refs.html>}.
-
-'''
-import os
-
-from altgraph import GraphError
-from altgraph.compat import *
-
-class Dot(object):
-    '''
-    A  class providing a B{graphviz} (dot language) representation
-    allowing a fine grained control over how the graph is being
-    displayed.
-
-    If the C{dot} and C{dotty} programs are not in the current system path
-    their location needs to be specified in the L{constructor<__init__>}.
-
-    For detailed example usage see the L{Dot} module documentation.
-    '''
-
-    def __init__(self, graph=None, nodes=None, edgefn=None, nodevisitor=None, edgevisitor=None, name="G", dot='dot', dotty='dotty', neato='neato'):
-        '''
-        Initialization.
-        '''
-        self.name, self.attr = name, {}
-
-        self.temp_dot = "tmp_dot.dot"
-        self.temp_neo = "tmp_neo.dot"
-
-        self.dot, self.dotty, self.neato = dot, dotty, neato
-        self.nodes, self.edges = {}, {}
-
-        if graph is not None and nodes is None:
-            nodes = graph
-        if graph is not None and edgefn is None:
-            def edgefn(node, graph=graph):
-                return imap(graph.tail, graph.out_edges(node))
-        if nodes is None:
-            nodes = ()
-
-        seen = set()
-        for node in nodes:
-            if nodevisitor is None:
-                style = {}
-            else:
-                style = nodevisitor(node)
-            if style is not None:
-                self.node_style(node, **style)
-                seen.add(node)
-        if edgefn is not None:
-            for head in seen:
-                for tail in ifilter(seen.__contains__, edgefn(head)):
-                    if edgevisitor is None:
-                        edgestyle = {}
-                    else:
-                        edgestyle = edgevisitor(head, tail)
-                    if edgestyle is not None:
-                        self.edge_style(head, tail, **edgestyle)
-
-    def style(self, **attr):
-        '''
-        Changes the overall style
-        '''
-        self.attr = attr
-
-    def display(self, mode='dot'):
-        '''
-        Displays the current graph via dotty
-        '''
-
-        if  mode == 'neato':
-            self.save_dot(self.temp_neo)
-            neato_cmd = "%s -o %s %s" % (self.neato, self.temp_dot, self.temp_neo)
-            os.system(neato_cmd)
-        else:
-            self.save_dot(self.temp_dot)
-
-        plot_cmd = "%s %s" % (self.dotty, self.temp_dot)
-        os.system(plot_cmd)
-
-    def node_style(self, node, **kwargs):
-        '''
-        Modifies a node style to the dot representation.
-        '''
-        if node not in self.edges:
-            self.edges[node] = {}
-        self.nodes[node] = kwargs
-
-    def all_node_style(self, **kwargs):
-        '''
-        Modifies all node styles
-        '''
-        for node in self.nodes:
-            self.node_style(node, **kwargs)
-
-    def edge_style(self, head, tail, **kwargs):
-        '''
-        Modifies an edge style to the dot representation.
-        '''
-        try:
-            if tail not in self.edges[head]:
-                self.edges[head][tail]= {}
-            self.edges[head][tail] = kwargs
-        except KeyError:
-            raise GraphError("invalid edge  %s -> %s " % (head, tail) )
-
-    def iterdot(self):
-        # write graph title
-        yield 'digraph %s {\n' % (self.name,)
-
-        # write overall graph attributes
-        for attr_name, attr_value in self.attr.iteritems():
-            yield '%s="%s";' % (attr_name, attr_value)
-        yield '\n'
-
-        # some reusable patterns
-        cpatt  = '%s="%s",'      # to separate attributes
-        epatt  = '];\n'          # to end attributes
-
-        # write node attributes
-        for node_name, node_attr in self.nodes.iteritems():
-            yield '\t"%s" [' % (node_name,)
-            for attr_name, attr_value in node_attr.iteritems():
-                yield cpatt % (attr_name, attr_value)
-            yield epatt
-
-        # write edge attributes
-        for head in self.edges:
-            for tail in self.edges[head]:
-                yield '\t"%s" -> "%s" [' % (head, tail)
-                for attr_name, attr_value in self.edges[head][tail].iteritems():
-                    yield cpatt % (attr_name, attr_value)
-                yield epatt
-
-        # finish file
-        yield '}\n'
-
-    def __iter__(self):
-        return self.iterdot()
-
-    def save_dot(self, file_name=None):
-        '''
-        Saves the current graph representation into a file
-        '''
-
-        if not file_name:
-            file_name = self.temp_dot
-
-        fp   = open(file_name, "w")
-        write = fp.write
-        for chunk in self.iterdot():
-            write(chunk)
-        fp.close()
-
-    def save_img(self, file_name="out", file_type="gif", mode='dot'):
-        '''
-        Saves the dot file as an image file
-        '''
-
-        if  mode == 'neato':
-            self.save_dot(self.temp_neo)
-            neato_cmd = "%s -o %s %s" % (self.neato, self.temp_dot, self.temp_neo)
-            os.system(neato_cmd)
-            plot_cmd = self.neato
-        else:
-            self.save_dot(self.temp_dot)
-            plot_cmd = self.dot
-
-        file_name  = "%s.%s" % (file_name, file_type)
-        create_cmd = "%s -T%s %s -o %s" % (plot_cmd, file_type, self.temp_dot, file_name)
-        os.system(create_cmd)

File altgraph/altgraph/Graph.py

  • Ignore whitespace
-"""
-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):
-        """
-        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)

File altgraph/altgraph/GraphAlgo.py

  • Ignore whitespace
-'''
-Graph algorithms
-'''
-from altgraph import GraphError
-
-def dijkstra(graph, start, end=None):
-    """
-    Dijkstra's algorithm for shortest paths
-
-    David Eppstein, UC Irvine, 4 April 2002
-
-    U{http://www.ics.uci.edu/~eppstein/161/python/}
-
-    U{http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466}
-
-    Find shortest paths from the  start node to all nodes nearer than or equal to the end node.
-
-    Dijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive.
-    This code does not verify this property for all edges (only the edges examined until the end
-    vertex is reached), but will correctly compute shortest paths even for some graphs with negative
-    edges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake.
-
-    I{Adapted to altgraph by Istvan Albert, Pennsylvania State University - June, 9 2004}
-
-    """
-    D = {}    # dictionary of final distances
-    P = {}    # dictionary of predecessors
-    Q = _priorityDictionary()    # estimated distances of non-final vertices
-    Q[start] = 0
-
-    for v in Q:
-        D[v] = Q[v]
-        if v == end: break
-
-        for w in graph.out_nbrs(v):
-            edge_id  = graph.edge_by_node(v,w)
-            vwLength = D[v] + graph.edge_data(edge_id)
-            if w in D:
-                if vwLength < D[w]:
-                    raise GraphError("Dijkstra: found better path to already-final vertex")
-            elif w not in Q or vwLength < Q[w]:
-                Q[w] = vwLength
-                P[w] = v
-
-    return (D,P)
-
-def shortest_path(graph, start, end):
-    """
-    Find a single shortest path from the given start node to the given end node.
-    The input has the same conventions as dijkstra(). The output is a list of the nodes
-    in order along the shortest path.
-
-    B{Note that the distances must be stored in the edge data as numeric data}
-    """
-
-    D,P = dijkstra(graph, start, end)
-    Path = []
-    while 1:
-        Path.append(end)
-        if end == start: break
-        end = P[end]
-    Path.reverse()
-    return Path
-
-#
-# Utility classes and functions
-#
-class _priorityDictionary(dict):
-    '''
-    Priority dictionary using binary heaps (internal use only)
-
-    David Eppstein, UC Irvine, 8 Mar 2002
-
-    Implements a data structure that acts almost like a dictionary, with two modifications:
-        1. D.smallest() returns the value x minimizing D[x].  For this to work correctly,
-            all values D[x] stored in the dictionary must be comparable.
-        2. iterating "for x in D" finds and removes the items from D in sorted order.
-            Each item is not removed until the next item is requested, so D[x] will still
-            return a useful value until the next iteration of the for-loop.
-            Each operation takes logarithmic amortized time.
-    '''
-    def __init__(self):
-        '''
-        Initialize priorityDictionary by creating binary heap of pairs (value,key).
-        Note that changing or removing a dict entry will not remove the old pair from the heap
-        until it is found by smallest() or until the heap is rebuilt.
-        '''
-        self.__heap = []
-        dict.__init__(self)
-
-    def smallest(self):
-        '''
-        Find smallest item after removing deleted items from front of heap.
-        '''
-        if len(self) == 0:
-            raise IndexError, "smallest of empty priorityDictionary"
-        heap = self.__heap
-        while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]:
-            lastItem = heap.pop()
-            insertionPoint = 0
-            while 1:
-                smallChild = 2*insertionPoint+1
-                if smallChild+1 < len(heap) and heap[smallChild] > heap[smallChild+1] :
-                    smallChild += 1
-                if smallChild >= len(heap) or lastItem <= heap[smallChild]:
-                    heap[insertionPoint] = lastItem
-                    break
-                heap[insertionPoint] = heap[smallChild]
-                insertionPoint = smallChild
-        return heap[0][1]
-
-    def __iter__(self):
-        '''
-        Create destructive sorted iterator of priorityDictionary.
-        '''
-        def iterfn():
-            while len(self) > 0:
-                x = self.smallest()
-                yield x
-                del self[x]
-        return iterfn()
-
-    def __setitem__(self,key,val):
-        '''
-        Change value stored in dictionary and add corresponding pair to heap.
-        Rebuilds the heap if the number of deleted items gets large, to avoid memory leakage.
-        '''
-        dict.__setitem__(self,key,val)
-        heap = self.__heap
-        if len(heap) > 2 * len(self):
-            self.__heap = [(v,k) for k,v in self.iteritems()]
-            self.__heap.sort()  # builtin sort probably faster than O(n)-time heapify
-        else:
-            newPair = (val,key)
-            insertionPoint = len(heap)
-            heap.append(None)
-            while insertionPoint > 0 and newPair < heap[(insertionPoint-1)//2]:
-                heap[insertionPoint] = heap[(insertionPoint-1)//2]
-                insertionPoint = (insertionPoint-1)//2
-            heap[insertionPoint] = newPair
-
-    def setdefault(self,key,val):
-        '''
-        Reimplement setdefault to pass through our customized __setitem__.
-        '''
-        if key not in self:
-            self[key] = val
-        return self[key]

File altgraph/altgraph/GraphStat.py

  • Ignore whitespace
-'''
-Functions providing various graph statistics
-'''
-import sys
-
-def avg_hops(graph):
-    '''
-
-    '''
-    pass
-
-def degree_dist(graph, limits=(0,0), bin_num=10, mode='out'):
-    '''
-    Computes the degree distribution for a graph.
-    Returns a list of tuples where the first element of the tuple is the center of the bin
-    representing a range of degrees and the second element of the tuple are the number of nodes
-    with the degree falling in the range.
-
-    Example::
-        ....
-
-    '''
-
-    deg = []
-    if mode == 'inc':
-        get_deg = graph.inc_degree
-    else:
-        get_deg = graph.out_degree
-
-    for node in graph:
-        deg.append( graph.get_degree(node) )
-
-    results = _binning(values=deg, limits=limits, bin_num=bin_num)
-
-    return results
-
-def _binning(values, limits=(0,0), bin_num=10):
-    '''
-    Bins data that falls between certain limits.
-    Returns a list of tuples where the first element of the tuple is the center of the bin
-    and the second element of the tuple are the counts.
-    '''
-    if limits == (0, 0):
-        eps = 1.0/sys.maxint
-        min_val, max_val = min(values) - eps, max(values) + eps
-    else:
-        min_val, max_val = limits
-
-    # get bin size
-    bin_size = (max_val - min_val)/float(bin_num)
-    bins = [0] * (bin_num)
-
-    # will ignore these outliers for now
-    out_points = 0
-    for value in values:
-        try:
-            if (value - min_val) < 0:
-                out_points += 1
-            else:
-                index = int((value - min_val)/float(bin_size))
-                bins[index] += 1
-        except:
-            out_points += 1
-
-    # make it ready for an x,y plot
-    result = []
-    center = (bin_size/2) + min_val
-    for i, y in enumerate(bins):
-        x = center + bin_size * i
-        result.append( (x,y) )
-
-    return result
-
-
-if __name__ == '__main__':
-    a = range(100)
-    out = _binning(a, limits = (0, 0) )
-    print out

File altgraph/altgraph/GraphUtil.py

  • Ignore whitespace
-'''
-Utility classes and functions
-'''
-
-from altgraph.compat import *
-from altgraph import Graph
-import random
-
-def generate_random_graph(node_num, edge_num, self_loops=False, multi_edges=False):
-    '''
-    Generates and returns a L{Graph.Graph} instance with C{node_num} nodes
-    randomly connected by C{edge_num} edges.
-    '''
-    g = Graph.Graph()
-    nodes = range(node_num)
-
-    for node in nodes:
-        g.add_node(node)
-
-    while 1:
-        head = random.choice(nodes)
-        tail = random.choice(nodes)
-
-        # loop defense
-        if head == tail and not self_loops:
-            continue
-
-        # multiple edge defense
-        if g.edge_by_node(head,tail) and not multi_edges:
-            continue
-
-        # add the edge
-        g.add_edge(head, tail)
-        if g.number_of_edges() >= edge_num:
-            break
-
-    return g
-
-def generate_scale_free_graph(steps, growth_num, self_loops=False, multi_edges=False):
-    '''
-    Generates and returns a L{Graph.Graph} instance that will have C{steps*growth_num} nodes
-    and a scale free (powerlaw) connectivity. Starting with a fully connected graph with C{growth_num} nodes
-    at every step C{growth_num} nodes are added to the graph and are connected to existing nodes with
-    a probability proportional to the degree of these existing nodes.
-    '''
-    graph = Graph.Graph()
-
-    # initialize the graph
-    store = []
-    for i in range(growth_num):
-        store   += [ i ] * (growth_num - 1)
-        for j in range(i + 1, growth_num):
-            graph.add_edge(i,j)
-
-    # generate
-    for node in range(growth_num, (steps-1) * growth_num):
-        graph.add_node(node)
-        while ( graph.out_degree(node) < growth_num ):
-            nbr = random.choice(store)
-
-            # loop defense
-            if node == nbr and not self_loops:
-                continue
-
-            # multi edge defense
-            if graph.edge_by_node(node, nbr) and not multi_edges:
-                continue
-
-            graph.add_edge(node, nbr)
-
-
-        for nbr in graph.out_nbrs(node):
-            store.append(node)
-            store.append(nbr)
-
-    return graph
-
-def filter_stack(graph, head, filters):
-    visited, removes, orphans = set([head]), set(), set()
-    stack = deque([(head, head)])
-    get_data = graph.node_data
-    get_edges = graph.out_edges
-    get_tail = graph.tail
-
-    while stack:
-        last_good, node = stack.pop()
-        data = get_data(node)
-        if data is not None:
-            for filtfunc in filters:
-                if not filtfunc(data):
-                    removes.add(node)
-                    break
-            else:
-                last_good = node
-        for edge in get_edges(node):
-            tail = get_tail(edge)
-            if last_good is not node:
-                orphans.add((last_good, tail))
-            if tail not in visited:
-                visited.add(tail)
-                stack.append((last_good, tail))
-
-    orphans = [(last_good, tail) for (last_good, tail) in orphans if tail not in removes]
-
-    return visited, removes, orphans
-
-
-
-if __name__ == '__main__':
-
-    import Dot
-
-    g = generate_scale_free_graph(steps=10, growth_num=4)
-
-    d = Dot.Dot(g)
-
-    d.all_node_style(width=1, shape='circle', style='filled', fillcolor='white')
-
-    d.display()
-    d.save_img()
-
-    print g

File altgraph/altgraph/ObjectGraph.py

  • Ignore whitespace
-from itertools import imap
-
-from altgraph.compat import *
-from altgraph.Graph import Graph
-from altgraph.GraphUtil import filter_stack
-
-class ObjectGraph(object):
-    """
-    A graph of objects that have a "graphident" attribute.
-    graphident is the key for the object in the graph
-    """
-    def __init__(self, graph=None, debug=0):
-        if graph is None:
-            graph = Graph()
-        self.graphident = self
-        self.graph = graph
-        self.debug = debug
-        self.indent = 0
-        graph.add_node(self, None)
-
-    def __repr__(self):
-        return '<%s>' % (type(self).__name__,)
-
-    def flatten(self, condition=None, start=None):
-        """
-        Iterate over the subgraph that is entirely reachable by condition
-        starting from the given start node or the ObjectGraph root
-        """
-        if start is None:
-            start = self
-        start = self.getRawIdent(start)
-        return self.graph.iterdata(start=start, condition=condition)
-
-    def get_edges(self, node):
-        start = self.getRawIdent(node)
-        _, _, outraw, incraw = self.graph.describe_node(start)
-        def iter_edges(lst, n):
-            seen = set()
-            for tpl in imap(self.graph.describe_edge, lst):
-                ident = tpl[n]
-                if ident not in seen:
-                    yield self.findNode(ident)
-                    seen.add(ident)
-        return iter_edges(outraw, 3), iter_edges(incraw, 2)
-    
-    def filterStack(self, filters):
-        """
-        Filter the ObjectGraph in-place by removing all edges to nodes that
-        do not match every filter in the given filter list
-
-        Returns a tuple containing the number of:
-            (nodes_visited, nodes_removed, nodes_orphaned)
-        """
-        visited, removes, orphans = filter_stack(self.graph, self, filters)
-
-        for last_good, tail in orphans:
-            self.graph.add_edge(last_good, tail, edge_data='orphan')
-
-        for node in removes:
-            self.graph.hide_node(node)
-
-        return len(visited)-1, len(removes), len(orphans)
-
-    def removeNode(self, node):
-        """
-        Remove the given node from the graph if it exists
-        """
-        ident = self.getIdent(node)
-        if ident is not None:
-            self.graph.hide_node(ident)
-
-    def removeReference(self, fromnode, tonode):
-        """
-        Remove all edges from fromnode to tonode
-        """
-        if fromnode is None:
-            fromnode = self
-        fromident = self.getIdent(fromnode)
-        toident = self.getIdent(tonode)
-        if fromident is not None and toident is not None:
-            while True:
-                edge = self.graph.edge_by_node(fromident, toident)
-                if edge is None:
-                    break
-                self.graph.hide_edge(edge)
-
-    def getIdent(self, node):
-        """
-        Get the graph identifier for a node
-        """
-        ident = self.getRawIdent(node)
-        if ident is not None:
-            return ident
-        node = self.findNode(node)
-        if node is None:
-            return None
-        return node.graphident
-
-    def getRawIdent(self, node):
-        """
-        Get the identifier for a node object
-        """
-        if node is self:
-            return node
-        ident = getattr(node, 'graphident', None)
-        if ident is not None:
-            return ident
-        return ident
-
-    def findNode(self, node):
-        """
-        Find the node on the graph
-        """
-        ident = self.getRawIdent(node)
-        if ident is None:
-            ident = node
-        try:
-            return self.graph.node_data(ident)
-        except KeyError:
-            return None
-
-    def addNode(self, node):
-        """
-        Add a node to the graph referenced by the root
-        """
-        self.msg(4, "addNode", node)
-        self.graph.add_node(node.graphident, node)
-
-    def createReference(self, fromnode, tonode, edge_data=None):
-        """
-        Create a reference from fromnode to tonode
-        """
-        if fromnode is None:
-            fromnode = self
-        fromident, toident = self.getIdent(fromnode), self.getIdent(tonode)
-        if fromident is None or toident is None:
-            return
-        self.msg(4, "createReference", fromnode, tonode, edge_data)
-        self.graph.add_edge(fromident, toident, edge_data=edge_data)
-
-    def createNode(self, cls, name, *args, **kw):
-        """
-        Add a node of type cls to the graph if it does not already exist
-        by the given name
-        """
-        m = self.findNode(name)
-        if m is None:
-            m = cls(name, *args, **kw)
-            self.addNode(m)
-        return m
-
-    def msg(self, level, s, *args):
-        """
-        Print a debug message with the given level
-        """
-        if s and level <= self.debug:
-            print "%s%s %s" % ("    " * self.indent, s, ' '.join(map(repr, args)))
-
-    def msgin(self, level, s, *args):
-        """
-        Print a debug message and indent
-        """
-        if level <= self.debug:
-            self.msg(level, s, *args)
-            self.indent = self.indent + 1
-
-    def msgout(self, level, s, *args):
-        """
-        Dedent and print a debug message
-        """
-        if level <= self.debug:
-            self.indent = self.indent - 1
-            self.msg(level, s, *args)

File altgraph/altgraph/__init__.py

  • Ignore whitespace
-'''
-
-altgraph - a python graph library
-=================================
-
-altgraph is a fork of graphlib U{http://pygraphlib.sourceforge.net} tailored
-to use newer Python 2.3+ features, including additional support used by the
-py2app suite (modulegraph and macholib, specifically).
-
-altgraph is a python based graph (network) representation and manipulation package.
-It has started out as an extension to the C{graph_lib} module written by Nathan Denny
-U{http://www.ece.arizona.edu/~denny/python_nest/graph_lib_1.0.1.html} but over time
-it has been significantly optimized and expanded.
-
-The L{Graph} class is loosely modeled after the U{LEDA<http://www.algorithmic-solutions.com/enleda.htm>} (Library of Efficient Datatypes)  representation. The library
-includes methods for constructing graphs, BFS and DFS traversals,
-topological sort, finding connected components, shortest paths as well as a number
-graph statistics functions. The library can also visualize graphs
-via U{graphviz<http://www.research.att.com/sw/tools/graphviz/>}.
-
-The package contains the following modules:
-    -  the L{Graph} module contains the L{Graph.Graph} class that stores the graph data
-    -  the L{GraphAlgo} implements graph algorithms operating on graphs (L{Graph.Graph} instances)
-    -  the L{GraphStat} contains functions for computing statistical measures on graphs
-    -  the L{GraphUtil} contains functions for generating, reading and saving graphs
-    -  the L{Dot}  contains functions for displaying graphs via U{graphviz<http://www.research.att.com/sw/tools/graphviz/>}.
-
-Download
---------
-
-Download the  U{python source code<../dist>}.
-
-Installation
-------------
-
-Download and unpack the archive then type::
-
-    python setup.py install
-
-This will install the library in the default location. For instructions on
-how to customize the install procedure read the output of::
-
-    python setup.py --help install
-
-To verify the installation procedure switch to the test directory and run the
-test_graphib.py file that is located there::
-
-    python test_altgraph.py
-
-Example usage
--------------
-
-Lets assume that we want to analyze the graph below (links to the full picture) GRAPH_IMG.
-Our script then might look the following way::
-
-    from altgraph import Graph, GraphAlgo, Dot
-
-    # these are the edges
-    edges = [ (1,2), (2,4), (1,3), (2,4), (3,4), (4,5), (6,5),
-    (6,14), (14,15), (6, 15),  (5,7), (7, 8), (7,13), (12,8),
-    (8,13), (11,12), (11,9), (13,11), (9,13), (13,10) ]
-
-    # creates the graph
-    graph = Graph.Graph()
-    for head, tail in edges:
-        graph.add_edge(head, tail)
-
-    # do a forward bfs from 1 at most to 20
-    print graph.forw_bfs(1)
-
-This will print the nodes in some breadth first order::
-
-    [1, 2, 3, 4, 5, 7, 8, 13, 11, 10, 12, 9]
-
-If we wanted to get the hop-distance from node 1 to node 8
-we coud write::
-
-    print graph.get_hops(1, 8)
-
-This will print the following::
-
-    [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)]
-
-Node 1 is at 0 hops since it is the starting node, nodes 2,3 are 1 hop away ...
-node 8 is 5 hops away. To find the shortest distance between two nodes you
-can use::
-
-    print GraphAlgo.shortest_path(graph, 1, 12)
-
-It will print the nodes on one (if there are more) the shortest paths::
-
-    [1, 2, 4, 5, 7, 13, 11, 12]
-
-To display the graph we can use the GraphViz backend::
-
-    dot = Dot.Dot(graph)
-
-    # display the graph on the monitor
-    dot.display()
-
-    # save it in an image file
-    dot.save_img(file_name='graph', file_type='gif')
-
-
-@author: U{Istvan Albert<http://www.personal.psu.edu/staff/i/u/iua1/>}
-
-@license:  MIT License
-
-Copyright (c) 2004 Istvan Albert unless otherwise noted.
-
-Permission is hereby granted, free of charge, to any person obtaining a copy of this software
-and associated documentation files (the "Software"), to deal in the Software without restriction,
-including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
-and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do
-so.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
-INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
-PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
-FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
-ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
-THE SOFTWARE.
-@requires: Python 2.3 or higher
-
-@newfield contributor: Contributors:
-@contributor: U{Reka Albert <http://www.phys.psu.edu/~ralbert/>}
-
-'''
-
-__version__ = '0.6.8'
-
-class GraphError(ValueError):
-    pass

File altgraph/altgraph/compat.py

  • Ignore whitespace
-"""
-Python 2.4-like compatibility library for Python 2.3
-"""
-from itertools import *
-
-#
-# builtins from 2.4
-#
-
-try:
-    set, frozenset
-except NameError:
-    from sets import Set as set, ImmutableSet as frozenset
-
-try:
-    sorted
-except NameError:
-    def sorted(iterable, cmp=None, key=None, reverse=False):
-        if key is not None:
-            a, b = tee(iterable)
-            iterable = izip(imap(key, iterable), iterable)
-        if cmp is not None:
-            iterable = list(iterable)
-            iterable.sort(cmp)
-        else:
-            iterable = isorted(iterable)
-        if key is not None:
-            iterable = [v for (k,v) in iterable]
-        if type(iterable) is not list:
-            iterable = list(iterable)
-        if reverse:
-            iterable.reverse()
-        return iterable
-
-try:
-    reversed
-except NameError:
-    def reversed(iterable):
-        lst = list(iterable)
-        pop = lst.pop
-        while lst:
-            yield pop()
-
-
-#
-# itertools functions from 2.4
-#
-try:
-    tee
-except NameError:
-    def tee(iterable, n=2):
-        def gen(next, data={}, cnt=[0]):
-            for i in count():
-                if i == cnt[0]:
-                    item = data[i] = next()
-                    cnt[0] += 1
-                else:
-                    item = data.pop(i)
-                yield item
-        return tuple(imap(gen, repeat(iter(iterable), n)))
-
-try:
-    groupby
-except NameError:
-    class groupby(object):
-        def __init__(self, iterable, key=None):
-            if key is None:
-                key = lambda x: x
-            self.keyfunc = key
-            self.it = iter(iterable)
-            self.tgtkey = self.currkey = self.currvalue = xrange(0)
-        def __iter__(self):
-            return self
-        def next(self):
-            while self.currkey == self.tgtkey:
-                self.currvalue = self.it.next() # Exit on StopIteration
-                self.currkey = self.keyfunc(self.currvalue)
-            self.tgtkey = self.currkey
-            return (self.currkey, self._grouper(self.tgtkey))
-        def _grouper(self, tgtkey):
-            while self.currkey == tgtkey:
-                yield self.currvalue
-                self.currvalue = self.it.next() # Exit on StopIteration
-                self.currkey = self.keyfunc(self.currvalue)
-
-
-#
-# operators from 2.4
-#
-try:
-    from operator import attrgetter, itemgetter
-except ImportError:
-    def attrgetter(attr):
-        def attrgetter(obj):
-            return getattr(obj, attr)
-        return attrgetter
-
-    def itemgetter(item):
-        def itemgetter(obj):
-            return obj[item]
-        return itemgetter
-
-
-#
-# deque from 2.4's collections
-# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/259179/
-#
-try:
-    from collections import deque
-except ImportError:
-    class deque(object):
-
-        def __init__(self, iterable=()):
-            self.data = dict(enumerate(iterable))
-            self.left = 0
-            self.right = len(self.data)
-
-        def append(self, x):
-            self.data[self.right] = x
-            self.right += 1
-
-        def appendleft(self, x):
-            self.left -= 1
-            self.data[self.left] = x
-
-        def pop(self):
-            if self.left == self.right:
-                raise IndexError('cannot pop from empty deque')
-            self.right -= 1
-            return self.data[self.right]
-
-        def popleft(self):
-            if self.left == self.right:
-                raise IndexError('cannot pop from empty deque')
-            x = self.data[self.left]
-            self.left += 1
-            return x
-
-        def __len__(self):
-            return self.right - self.left
-
-        def __iter__(self):
-            return imap(self.data.__getitem__, xrange(self.left, self.right))
-
-        def __repr__(self):
-            return 'deque(%r)' % (list(self),)
-
-        def __getstate__(self):
-            return (tuple(self),)
-
-        def __setstate__(self, s):
-            self.__init__(s[0])
-
-        def __hash__(self):
-            raise TypeError
-
-        def __copy__(self):
-            return self.__class__(self)
-
-        def __deepcopy__(self, memo={}):
-            from copy import deepcopy
-            result = self.__class__()
-            memo[id(self)] = result
-            result.__init__(deepcopy(tuple(self), memo))
-            return result
-
-#
-# new functions
-#
-import heapq as _heapq
-def isorted(iterable):
-    lst = list(iterable)
-    _heapq.heapify(lst)
-    pop = _heapq.heappop
-    while lst:
-        yield pop(lst)
-
-def ireversed(iterable):
-    if isinstance(iterable, (list, tuple)):
-        for i in xrange(len(iterable)-1, -1, -1):
-            yield iterable[i]
-    else:
-        for obj in reversed(iterable):
-            yield obj

File altgraph/ez_setup/README.txt

  • Ignore whitespace
-This directory exists so that Subversion-based projects can share a single
-copy of the ``ez_setup`` bootstrap module for ``setuptools``, and have it
-automatically updated in their projects when ``setuptools`` is updated.
-
-For your convenience, you may use the following svn:externals definition::
-
-    ez_setup svn://svn.eby-sarna.com/svnroot/ez_setup
-
-You can set this by executing this command in your project directory::
-
-    svn propedit svn:externals .
-
-And then adding the line shown above to the file that comes up for editing.
-Then, whenever you update your project, ``ez_setup`` will be updated as well.
-

File altgraph/ez_setup/__init__.py

  • Ignore whitespace
-#!python
-"""Bootstrap setuptools installation
-
-If you want to use setuptools in your package's setup.py, just include this
-file in the same directory with it, and add this to the top of your setup.py::
-
-    from ez_setup import use_setuptools
-    use_setuptools()
-
-If you want to require a specific version of setuptools, set a download
-mirror, or use an alternate download directory, you can do so by supplying
-the appropriate options to ``use_setuptools()``.
-
-This file can also be run as a script to install or upgrade setuptools.
-"""
-import sys
-DEFAULT_VERSION = "0.6c7"
-DEFAULT_URL     = "http://pypi.python.org/packages/%s/s/setuptools/" % sys.version[:3]
-
-md5_data = {
-    'setuptools-0.6b1-py2.3.egg': '8822caf901250d848b996b7f25c6e6ca',
-    'setuptools-0.6b1-py2.4.egg': 'b79a8a403e4502fbb85ee3f1941735cb',
-    'setuptools-0.6b2-py2.3.egg': '5657759d8a6d8fc44070a9d07272d99b',
-    'setuptools-0.6b2-py2.4.egg': '4996a8d169d2be661fa32a6e52e4f82a',
-    'setuptools-0.6b3-py2.3.egg': 'bb31c0fc7399a63579975cad9f5a0618',
-    'setuptools-0.6b3-py2.4.egg': '38a8c6b3d6ecd22247f179f7da669fac',
-    'setuptools-0.6b4-py2.3.egg': '62045a24ed4e1ebc77fe039aa4e6f7e5',
-    'setuptools-0.6b4-py2.4.egg': '4cb2a185d228dacffb2d17f103b3b1c4',
-    'setuptools-0.6c1-py2.3.egg': 'b3f2b5539d65cb7f74ad79127f1a908c',
-    'setuptools-0.6c1-py2.4.egg': 'b45adeda0667d2d2ffe14009364f2a4b',
-    'setuptools-0.6c2-py2.3.egg': 'f0064bf6aa2b7d0f3ba0b43f20817c27',
-    'setuptools-0.6c2-py2.4.egg': '616192eec35f47e8ea16cd6a122b7277',
-    'setuptools-0.6c3-py2.3.egg': 'f181fa125dfe85a259c9cd6f1d7b78fa',
-    'setuptools-0.6c3-py2.4.egg': 'e0ed74682c998bfb73bf803a50e7b71e',
-    'setuptools-0.6c3-py2.5.egg': 'abef16fdd61955514841c7c6bd98965e',
-    'setuptools-0.6c4-py2.3.egg': 'b0b9131acab32022bfac7f44c5d7971f',
-    'setuptools-0.6c4-py2.4.egg': '2a1f9656d4fbf3c97bf946c0a124e6e2',
-    'setuptools-0.6c4-py2.5.egg': '8f5a052e32cdb9c72bcf4b5526f28afc',
-    'setuptools-0.6c5-py2.3.egg': 'ee9fd80965da04f2f3e6b3576e9d8167',
-    'setuptools-0.6c5-py2.4.egg': 'afe2adf1c01701ee841761f5bcd8aa64',
-    'setuptools-0.6c5-py2.5.egg': 'a8d3f61494ccaa8714dfed37bccd3d5d',
-    'setuptools-0.6c6-py2.3.egg': '35686b78116a668847237b69d549ec20',
-    'setuptools-0.6c6-py2.4.egg': '3c56af57be3225019260a644430065ab',
-    'setuptools-0.6c6-py2.5.egg': 'b2f8a7520709a5b34f80946de5f02f53',
-    'setuptools-0.6c7-py2.3.egg': '209fdf9adc3a615e5115b725658e13e2',
-    'setuptools-0.6c7-py2.4.egg': '5a8f954807d46a0fb67cf1f26c55a82e',
-    'setuptools-0.6c7-py2.5.egg': '45d2ad28f9750e7434111fde831e8372',
-}
-
-import sys, os
-
-def _validate_md5(egg_name, data):
-    if egg_name in md5_data:
-        from md5 import md5
-        digest = md5(data).hexdigest()
-        if digest != md5_data[egg_name]:
-            print >>sys.stderr, (
-                "md5 validation of %s failed!  (Possible download problem?)"
-                % egg_name
-            )
-            sys.exit(2)
-    return data
-
-
-def use_setuptools(
-    version=DEFAULT_VERSION, download_base=DEFAULT_URL, to_dir=os.curdir,
-    download_delay=15
-):
-    """Automatically find/download setuptools and make it available on sys.path
-
-    `version` should be a valid setuptools version number that is available
-    as an egg for download under the `download_base` URL (which should end with
-    a '/').  `to_dir` is the directory where setuptools will be downloaded, if
-    it is not already available.  If `download_delay` is specified, it should
-    be the number of seconds that will be paused before initiating a download,
-    should one be required.  If an older version of setuptools is installed,
-    this routine will print a message to ``sys.stderr`` and raise SystemExit in
-    an attempt to abort the calling script.
-    """
-    try:
-        import setuptools
-        if setuptools.__version__ == '0.0.1':
-            print >>sys.stderr, (
-            "You have an obsolete version of setuptools installed.  Please\n"
-            "remove it from your system entirely before rerunning this script."
-            )
-            sys.exit(2)
-    except ImportError:
-        egg = download_setuptools(version, download_base, to_dir, download_delay)
-        sys.path.insert(0, egg)
-        import setuptools; setuptools.bootstrap_install_from = egg
-
-    import pkg_resources
-    try:
-        pkg_resources.require("setuptools>="+version)
-
-    except pkg_resources.VersionConflict, e:
-        # XXX could we install in a subprocess here?
-        print >>sys.stderr, (
-            "The required version of setuptools (>=%s) is not available, and\n"
-            "can't be installed while this script is running. Please install\n"
-            " a more recent version first.\n\n(Currently using %r)"
-        ) % (version, e.args[0])
-        sys.exit(2)
-
-def download_setuptools(
-    version=DEFAULT_VERSION, download_base=DEFAULT_URL, to_dir=os.curdir,
-    delay = 15
-):
-    """Download setuptools from a specified location and return its filename
-
-    `version` should be a valid setuptools version number that is available
-    as an egg for download under the `download_base` URL (which should end
-    with a '/'). `to_dir` is the directory where the egg will be downloaded.
-    `delay` is the number of seconds to pause before an actual download attempt.
-    """
-    import urllib2, shutil
-    egg_name = "setuptools-%s-py%s.egg" % (version,sys.version[:3])
-    url = download_base + egg_name
-    saveto = os.path.join(to_dir, egg_name)
-    src = dst = None
-    if not os.path.exists(saveto):  # Avoid repeated downloads
-        try:
-            from distutils import log
-            if delay:
-                log.warn("""
----------------------------------------------------------------------------
-This script requires setuptools version %s to run (even to display
-help).  I will attempt to download it for you (from
-%s), but
-you may need to enable firewall access for this script first.
-I will start the download in %d seconds.
-
-(Note: if this machine does not have network access, please obtain the file
-
-   %s
-
-and place it in this directory before rerunning this script.)
----------------------------------------------------------------------------""",
-                    version, download_base, delay, url
-                ); from time import sleep; sleep(delay)
-            log.warn("Downloading %s", url)
-            src = urllib2.urlopen(url)
-            # Read/write all in one block, so we don't create a corrupt file
-            # if the download is interrupted.
-            data = _validate_md5(egg_name, src.read())
-            dst = open(saveto,"wb"); dst.write(data)
-        finally:
-            if src: src.close()
-            if dst: dst.close()
-    return os.path.realpath(saveto)
-
-def main(argv, version=DEFAULT_VERSION):
-    """Install or upgrade setuptools and EasyInstall"""
-
-    try:
-        import setuptools
-    except ImportError:
-        egg = None
-        try:
-            egg = download_setuptools(version, delay=0)
-            sys.path.insert(0,egg)
-            from setuptools.command.easy_install import main
-            return main(list(argv)+[egg])   # we're done here
-        finally:
-            if egg and os.path.exists(egg):
-                os.unlink(egg)
-    else:
-        if setuptools.__version__ == '0.0.1':
-            # tell the user to uninstall obsolete version
-            use_setuptools(version)
-
-    req = "setuptools>="+version
-    import pkg_resources
-    try:
-        pkg_resources.require(req)
-    except pkg_resources.VersionConflict:
-        try:
-            from setuptools.command.easy_install import main
-        except ImportError:
-            from easy_install import main
-        main(list(argv)+[download_setuptools(delay=0)])
-        sys.exit(0) # try to force an exit
-    else:
-        if argv:
-            from setuptools.command.easy_install import main
-            main(argv)
-        else:
-            print "Setuptools version",version,"or greater has been installed."
-            print '(Run "ez_setup.py -U setuptools" to reinstall or upgrade.)'
-
-
-
-def update_md5(filenames):
-    """Update our built-in md5 registry"""
-
-    import re
-    from md5 import md5
-
-    for name in filenames:
-        base = os.path.basename(name)
-        f = open(name,'rb')
-        md5_data[base] = md5(f.read()).hexdigest()
-        f.close()
-
-    data = ["    %r: %r,\n" % it for it in md5_data.items()]
-    data.sort()
-    repl = "".join(data)
-
-    import inspect
-    srcfile = inspect.getsourcefile(sys.modules[__name__])
-    f = open(srcfile, 'rb'); src = f.read(); f.close()
-
-    match = re.search("\nmd5_data = {\n([^}]+)}", src)
-    if not match:
-        print >>sys.stderr, "Internal error!"
-        sys.exit(2)
-
-    src = src[:match.start(1)] + repl + src[match.end(1):]
-    f = open(srcfile,'w')
-    f.write(src)
-    f.close()
-
-
-if __name__=='__main__':
-    if len(sys.argv)>2 and sys.argv[1]=='--md5update':
-        update_md5(sys.argv[2:])
-    else:
-        main(sys.argv[1:])
-
-
-
-
-

File altgraph/setup.cfg

  • Ignore whitespace
-[egg_info]
-tag_build = .dev
-tag_svn_revision = true

File altgraph/setup.py

  • Ignore whitespace
-#!/usr/bin/env python
-
-import ez_setup
-ez_setup.use_setuptools()
-
-from setuptools import setup, Extension
-
-VERSION = '0.6.8'
-DESCRIPTION = "Python graph (network) package"
-LONG_DESCRIPTION = """
-altgraph is a fork of graphlib: a graph (network) package for constructing
-graphs, BFS and DFS traversals, topological sort, shortest paths, etc. with
-graphviz output.
-
-altgraph includes some additional usage of Python 2.3+ features and
-enhancements related to modulegraph and macholib.
-"""
-
-CLASSIFIERS = filter(None, map(str.strip,
-"""                 
-Intended Audience :: Developers
-License :: OSI Approved :: MIT License
-Programming Language :: Python
-Topic :: Software Development :: Libraries :: Python Modules
-Topic :: Scientific/Engineering :: Mathematics
-Topic :: Scientific/Engineering :: Visualization
-""".splitlines()))
-
-setup(
-    name="altgraph",
-    version=VERSION,
-    description=DESCRIPTION,
-    long_description=LONG_DESCRIPTION,
-    classifiers=CLASSIFIERS,
-    author="Bob Ippolito",
-    author_email="bob@redivi.com",
-    url="http://undefined.org/python/#altgraph",
-    license="MIT License",
-    packages=['altgraph'],
-    platforms=['any'],
-    zip_safe=True,
-)

File altgraph/test/test_altgraph.py

  • Ignore whitespace
-#!/usr/bin/env py.test
-import os
-import sys
-
-from altgraph import Graph, GraphAlgo
-
-def test_altgraph():
-
-    # these are the edges
-    edges = [ (1,2), (2,4), (1,3), (2,4), (3,4), (4,5), (6,5), (6,14), (14,15), (6, 15),
-    (5,7), (7, 8), (7,13), (12,8), (8,13), (11,12), (11,9), (13,11), (9,13), (13,10) ]
-
-    store = {}
-    g = Graph.Graph()
-    for head, tail in edges:
-        store[head] = store[tail] = None
-        g.add_edge(head, tail)
-
-    # check the parameters
-    assert g.number_of_nodes() == len(store)
-    assert g.number_of_edges() == len(edges)
-
-
-    # do a forward bfs
-    assert g.forw_bfs(1) == [1, 2, 3, 4, 5, 7, 8, 13, 11, 10, 12, 9]
-
-
-    # diplay the hops and hop numbers between nodes