Node abstraction and graph library.

[mason-bially]

Need a graph library. Specifically for building wrappers around existing objects. Should live in the pyext namespace pyext.graph. Basic design goals include power, performance, and simplicity (in that order). Following is a spec for the graph library:

Graph

There are a number of abstract base classes from which "graph" objects may inherit. A graph object is an instance of configuration data for a specific graph. Specifically each class which subclasses graph features is describing how to configure and interpret a class of graphs. Instances of graph classes do not store any information (although they may cache it), specifically, graph class are meant to allow for interpretation of data from other locations.

INodeCoerce

Provides functionality for coercing nodes in the graph to provide useful information.

• graph_coerce_node(self, node): Given a node, coerce it into an object usable by the graph. Must support equality, hashing, and ordering. All other graph functions will pass nodes after calling this function on them.
• graph_node_edges(self, node): Given a node compute the edges out of and into it, in the form of a tuple of two dictionaries, the first dictionary is for outgoing edges (where the given node is the source) and second dictionary is for incoming edges (where the given node is the destination). The keys of each dictionary is the other node (first dictionary keys are the destination node, second dictionary keys are the source node), the values are the associated edge data.
• graph_list_nodes(self): Returns an enumerable (list, set, generator, etc) of every node (pre coerce) in the graph. This function should only be called by operations which require it (like whole graph algorithms). Returning None implies that these algorithms should not work, and only allows a subclass of algorithms to run.

  GraphBase

Base class, which inherits the INodeCoerce class as an abstract, may provide other internal abstract interfaces, provides functionality for reading graphs from sources which do not change. Hence the arguments must be immutable, or locked and enumerated on construction. (It may be useful to, in the future, provide functionality for graphs which do read mutable sources).

IWeightedEdgeGraph

Some functions require weighted edges. Every edge is assumed to weight 1 unless this interface is provided.

• graph_edge_weight(self, src, dst, edge): Given the source node, destination node and edge data compute a comparable weight value. Weight values must support equality, hashing, ordering, and addition.
• graph_limits(self): A dictionary of limits on edges in this graph space in a dictionary, merges with other graph_limits functions.

{
    graph.EdgeWeightNegative: false, # Describes if edge weights can be "negative".
    graph.EdgeWeightZero: 0.0 # Starting edge weight.
    graph.EdgeWeightUnreachable: float("inf") # Maximum possible value, "unreachable"
}

IWeightedNodeGraph

Some functions require weighted edges. Every node is assumed to weight 0 unless this interface is provided.

• graph_node_weight(self, node): Given a node, compute a comparable weight value. Weight values must support equality, hashing, ordering, and addition.
• graph_limits(self): A dictionary of limits on nodes in this graph space in a dictionary, merges with other graph_limits functions.

{
    graph.NodeWeightNegative: false, # Describes if node weights can be "negative".
    graph.NodeWeightZero: 0.0 # Starting node weight, if none, use node weight of initial node.
    graph.NodeWeightUnreachable: float("inf") # Maximum possible value, "unreachable"
}

Functions

Graphs

These functions manipulate graphs, returning new graph(s).

• reverse(graph): Returns a new graph with all the edges inverted.
• connected_subgraphs(graph): [graph_list_nodes] Returns a list of graphs which are the connected subgraphs of the given graph (i.e. each subgraph returned will be completely connected) returned by count of nodes in each graph.

  Traversals

Traversals provide ways of visiting every node from a given node. Must be used as generators, as they return objects stateful to the traversal (i.e. each function returns a generator of traversal objects).

Traversal objects have the following functions and properties, mutating these without using a set function doesn't do anything:

• path(self): Return the list of edges to reach the current location.
• walk(self): Return the list of nodes to reach the current location (including current and root node).
• is_leaf(self): Computes if this node is a leaf (no outgoing edges).
• graph: The current graph.
• node: The current node.
• edge: The edge which arrived us at this node.
• weight: The accumulated weight after arriving at this node (includes this nodes weight).
• set_out_edges(self, edge_dict): Inform the traversal about the outgoing edges acceptable for traversing out of this node (effects the is_leaf function on this class). The edge dict is dictionary mapping destination objects (pre coerce) to edge data, using the current node as the source for each edge.

Here are some traversals:

• traverse_breadth(graph, node): Traverse the graph, breadth first, starting from the given node. Also, traverses in shortest distance from root node.
• traverse_depth(graph, node): Traverse the graph, depth first, starting from the given node. Also an in order traversal on a minimum spanning tree.

  Helpers

• search(traversal, node): Given a traversal generator, search it for a node, and return the traversal object at that node (can construct the path, return weight, etc.).

  Usage

Generally speaking the library will be used like:

## Create a graph class:
class SomeGraph(graph.Graph):
    def graph_node_coerce(self, node):
        return node.as_some_node() # In this implementation we assume every object in the graph is aware of the graph's existence.

    def graph_node_edges(self, node):
        return node.edges() # We assume the instances returned by coerce have this edges function.

# Shortest path search:
for traverse in graph.traverse_breadth(SomeGraph(), an_object):
    if traverse.node.object is target_object:
        nodes = traverse.walk()

# Equivalent to:
nodes = graph.search(graph.traverse_breadth(SomeGraph(), an_object), target_object).walk()

# In order traversal of the inverted graph
used_by = [t.node.object for t in graph.traverse_depth(graph.reverse(SomeGraph()), query_object)]

[mason-bially]

This will be sufficient to replace some very brittle code having to do with generating in order lists of modules required and depended on by a module.

In addition, it will provide a useful library for traversing the new dependency system, and entity systems with relations (as opposed to writing the code twice), as well as adding new features to these systems that might otherwise be too time consuming to bother adding.

Some near future additions:

• A graph base class capable of holding mutable graphs (requiring functions like graph_refresh_node(self, node).
• Adding thread awareness (monitors) on graphs so that calls to cache invalidation (like the above) can wait until traversals across the graph have finished. This may also be done outside of this library completely.
• Better tree/forests/dense forest functions.
• Coloring.
• Building interesting subgraphs (finding the larges subgraph(s) with similar properties).