Enhancements to `graphlib`

Ideas
#1

Hello,

I have some thought about the standard library’s graphlib module.

The primary innovation that I’m proposing is a new format for representing graph-like structures.

  • Nodes can be any hashable python object,
  • Edges are specified by a function which takes the form: edges(node) -> iterable-of-nodes.
    When edges are directed: the argument is the source and the return values are the destinations.

This API can be used on arbitrary data-structures, without ever needing to modify your data-structures to accommodate these algorithms!

This new API solves the following usability issues which all other graph libraries suffer from:

  1. Users don’t store their data in explicit graph structures.

    • Instead, they store their data in custom OOP class structures which are opaque to the std-lib.
    • Therefore the user must construct the libraries “Graph” structure.
      • Necessitating that they duplicate a lot of data.
      • And if the underlying data structure ever changes, then they must either update or rebuild the Graph structure.

  2. Other graph algorithms (not topological sorting) accept potentially infinite graphs, e.g. IDDFS, Dykstra’s shortest path, A* pathfinding.

Review of the state of the art:

The standard library’s graphlib.TopologicalSorter uses a dictionary to specify the nodes and edges.

These 3rd party libraries provide a “Graph” class which users are required to use:
These “Graph” classes typically are not compatible between different 3rd party library implementations.

The following libraries use compressed sparse matrices. Sparse matrices are a very efficient format. Numpy/scipy make it easy to convert to/from them and so provides good interoperability with the rest of the software ecosystem.

Algorithms:

I’ve ranked them by how useful I think they are:

  • Preorder depth first traversal
  • Postorder depth first traversal
  • Topological sort
  • A-Star pathfinding
  • Strongly connected components
  • Depth first search (returning the final stack / search path)
  • Iterative Deepening depth first search (shortest path on infinite graphs)
  • min-cut/max-flow
  • Dykstra’s shortest path (technically a subset of A* but should have its own public API entry point for ppl who don’t know how to do A*)

Example:

I have a prototype of this on pypi: graph-algorithms · PyPI

import graph_algorithms

# Make a data structure to represent a person and their familial relations.
class Person:
    def __init__(self, name, mom=None, dad=None):
        self.name = name
        self.mom = mom
        self.dad = dad
        self.children = []
        if self.mom is not None: self.mom.children.append(self)
        if self.dad is not None: self.dad.children.append(self)

    def __repr__(self):
        return self.name

# Make a family of people.
# Grandparents
James       = Person("James")
Patricia    = Person("Patricia")
Joseph      = Person("Joseph")
Margaret    = Person("Margaret")
# Parents
Michael     = Person("Michael", mom=Patricia, dad=James)
Susan       = Person("Susan",   mom=Patricia, dad=James)
Richard     = Person("Richard", mom=Margaret, dad=Joseph)
David       = Person("David",   mom=Margaret, dad=Joseph)
# Grandchildren
Sandra      = Person("Sandra",  mom=Susan, dad=Richard)
Ashley      = Person("Ashley",  mom=Susan, dad=Richard)

# Now let's traverse Susan's family tree:
print("")
print("Ancestors of Susan:")
known_parents = lambda person: filter(None, [person.mom, person.dad])
for person in graph_algorithms.depth_first_traversal(Susan, known_parents):
    print(person)
print("")
print("Descendants of Susan:")
for person in graph_algorithms.depth_first_traversal(Susan, lambda p: p.children):
    print(person)
print("")

Program Output:


Ancestors of Susan:
Susan
Patricia
James

Descendants of Susan:
Susan
Sandra
Ashley

The important thing to notice about this example is that the Person class and the graph library’s depth_first_traversal are totally decoupled.

  • The Person class does not care about the graph library.
  • The depth first traversal does not care about the Person class.
  • They only interaction between the traversal-code and the Person-class is through the adjacency function (the lambda’s in the example).

As a result, the depth-first-traversal can be applied to different sets of edges by simply swapping out the adjacency function. In this example: one set of edges describes the parents, and the other set of edges describes the children.

#2

My first instinct is to think that there are too many variations to standardize this into the stdlib, but on the other hand, I can think of a time or two I would have used some of these. I appreciate the passing-a-function API that makes your idea data-structure-invariant.

For concreteness, even something as simple as this could be nice occasionally:

from collections import deque

def depth_first_traversal(root, neighbors_func):
    seen = set()
    stack = [iter((root,))]
    while stack:
        try:
            node = next(stack[-1])
        except StopIteration:
            stack.pop()
        else:
            if node not in seen:
                seen.add(node)
                yield node
                stack.append(iter(neighbors_func(node)))

def breadth_first_traversal(root, neighbors_func):
    seen = set()
    q = deque([root])
    while q:
        node = q.popleft()
        if node not in seen:
            yield node
            seen.add(node)
            for neighbor in neighbors_func(node):
                if neighbor not in seen:
                    q.append(neighbor)

graph = {
    0: [2, 1, 2, 3],
    1: [2, 4],
    2: [4, 5, 2],
    3: [],
    4: [4],
    5: [0],
}

dfs = list(depth_first_traversal(0, lambda x: graph.get(x, ())))
assert dfs == [0, 2, 4, 5, 1, 3], dfs

bfs = list(breadth_first_traversal(0, lambda x: graph.get(x, ())))
assert bfs == [0, 2, 1, 3, 4, 5], bfs

My biggest worry would be the ratio of users who need exactly the functionality of one of the algorithms you implement to users who need a slight variation of the functionalities might be too low. For instance, what if a user needs to add logging to each exploration? Or to access the “seen” set? Or what if the “seen” set gets too big to store in memory and would be better served by something on disk? Or what if the search can start at multiple roots? Or what if the user needs access to each node’s predecessor? Or the list of predecessors? Or just the count of predecessors to compute something about the numbers of cycles? These may all be solvable problems, but it also seems like the sort of thing that invites scope-creep and bloat.

I think I’m -1 for adding all of the functions you list, but if there is a nice small API that emerges as a consensus, I might become +1.

1 Like
#3

Are you aware of Guido’s ancient essay on graph structures here?

That uses possibly the simplest data structure that can work: a graph is
a dict of {node: list_of_nodes}. He uses a simple one character string
as the node, but any hashable object would work, and of course it would
be trivial to map short node names (A, B, C etc) to more complicated
data structures.

I’m not sure what benefit you gain from making edges into functions.
Taking Guido’s example that he writes as this:

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

you would write it as, what? A function like this?

def graph(node):
    if node == 'A':
        return ['B', 'C']
    elif node == 'B':
        return ['C', 'D']
    elif ...  # you get the picture

That would make it very difficult to add, delete or modify nodes, and
inefficient for all but the smallest graphs. And I think it’s harder to
read too. I think you need to justify why a function is better than a
dict.

In your example of the family tree, I presume that the graph would be
represented by edges like this:

     child
#4

I agree that dictionaries are the most natural for representing finite unweighted graphs eagerly (though maybe a defaultdict(dict) may be better for weighted graphs or defaultdict(set) when you need a quick test for the presence of an edge), but I think the functional API covers that use-case and more. If you had the graph

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

then you could use a functional API by saying

for node in breadth_first_search(start='A', neighbors_function=graph.get):
    process(node)

That’ll have the same time complexity as whatever you would implement in a dictionary-specific way, but the functional API also lets you do things lazily like

# Solve The Wiki Game

def links_on_wikipedia_page(title):
    """
    >>> list(links_on_wikipedia_page("Python (Programming Language)"))
    ['Interpreter (computing)', 'High-level programming language', 'General-purpose programming language', ...]
    """
    # Fetch from the web

for page_title in breadth_first_search("Python (Programming Language)", links_on_wikipedia_page):
    if page_title == "Holy Grail":
        print("'Holy Grail' is accessible from Python")
        break

But presumably one would actually want access to the complete path of links:

["Python (Programming Language)", "Monty Python", "Monty Python and the Holy Grail", "Holy Grail"]

and so I don’t know if there’s a general-enough-yet-simple-enough API for what graph traversal functions should return. Maybe there could be one breadth_first_search_path_to_destination(start, neighbors_func, destination) function that returns a list like the above and another breadth_first_search(start, neighbors_func) that just lazily iterates.

#5

If I saw something like this:

for node in breadth_first_search(start='A', neighbors_function=graph.get):

in the wild, I wouldn’t even know how to interpret it. What is a
“neighbors function” when it is home? To me, that reads like:

mydict = {}
mydict.update(keyvalue_function=another_dict.get)

or:

book = [page1, page2, page3, page4]
number_of_pages = len(item_function=lambda i: book[i])

I’m sure I could work it out by hitting the reference documentation, but
passing a getter method to a data structure instead of the data
structure itself is hardly a natural, clear or readable API.

It smacks of “architecture”, or at least, excessive abstraction.

I think that, in practical terms, you’re dreaming if you think that in
general you can just write a function to handle this, especially for
something like internet networks. Far more likely you will need a
collection of functions, probably a large collection of functions, to
handle caching, retries, error recovery, redirects, scraping of pages or
calling the site’s API, rate limiting, etc.

So in other words, a class. And if you’re going to do that, I think a
much better idea is to write a class which duck-types as a dict, and
pass the CachedInternetLazyDict instance, not some getter function.

If probably won’t need the full dict API either, probably just
subscripting and/or the get method, maybe iteration.

#6

I was not aware of this.

I did work through the whole example. The solution is:
>>> lambda person: person.children

A second solution to find the parents (instead of the children) is also shown:
>>> lambda person: filter(None, [person.mom, person.dad])

Ease of use:
A function is easier to specify than a dictionary, because with the function you only need to specify how to access the neighbors, but with a dict you also need to specify what all of the nodes and their neighbors are.

Its the difference between:
>>> lambda node: node.my_neighbors_list
versus
>>> graph = {node: node.my_neighbors_list for node in all_my_nodes}
And building the dict required all_my_nodes whereas the functional API is able to discover all of the nodes given a sufficient subset of them.
And now I’ve copied a lot of data, which is likely going to be used once and then discarded.
And if I don’t discard it, the dict is not the original/authoritative copy so it needs to be updated if/when the underlying data changes.

Two problems:

  1. Everything is a graph and graphs are everywhere. Every data structure with a pointer to another data structure is -technically- a graph. Every two pieces of data with a relationship between them is -technically- a graph. Should every data structure implement an API for doing graph traversals? Of course not and this is why I’ve designed the API to not relying on any particular graph or node type.

  2. Every different type of relationship between nodes could constituent its own graph. The user might want to specify different graphs using the same underlying data. You can only implement a class-based API once per class.

    • For example my first posted showed how you can have one data structure with multiple types of relationships in it. It was a family tree with relationships for “mom”, “dad”, and “children”. First I traversed through the ancestors of a person, and then I did a different traversal through the descendants of a person. This would not have been possible with a class-based API.
#7

For depth first traversals, I was thinking we could organize it like:

  1. graphlib.depth_first_traversal()
  2. graphlib.depth_first_traversal.preorder()
  3. graphlib.depth_first_traversal.inorder()
  4. graphlib.depth_first_traversal.postorder()

All forms require two positional arguments:

  1. iterable_of_starting_nodes
  2. edges_function

Forms #2, #3, and #4 are the simpler versions:
They simply yield the nodes in their specified order (as lazy iterators).

  • Note: Form #3 (inorder traversal) is probably useless. It’s in the textbooks but I don’t think I’ve ever encountered it in the wild.

Form #1 will accept four optional keyword only arguments: preorder, postorder, inorder, revisit.
These arguments are callback hooks which are called with the nodes.

  • Note: the revisit callback would be called when a node that’s already been visited is visited again. The revisited nodes are not traversed (that would cause infinite recursion) but they are presented to the users via this special callback.
  • I think that this form (#1) should be evaluated eagerly and return a preorder’ed list?
    The purpose of the callbacks is for user to write algorithms on top of this one, and I think eager evaluation is more in line with that use-case. However it would be inconsistent with the other forms which use lazy iterators.

I call that a “search” instead of a “traversal”.
They are very similar under the hood, but they have different API’s tailored for the different use-cases.

My prototype’s API is:
depth_first_search(start_vertex, adjacent, goal) -> list

  • Where goal is a predicate function: goal(node) -> bool
  • The returned list is the path from the start_vertex to the first goal found. It includes all intermediate nodes which are passed through on the way to the goal.
#8

To me, it’s absolutely clear that there’s a lot of room for debate and discussion over the API design. That’s fine, but the stdlib is not the place for working out the best design for something like this.

I suggest you write your proposed library and publish it on PyPI, and refine the design there based on real use cases. Once there’s good evidence that the design is solid and of use to people, that’s when it starts to be useful to discuss stdlib inclusion.

5 Likes
#9

The OP has already posted a link to a published prototype on PyPI. These algorithms are so common that I’m not sure we can expect “good evidence” on a particular design any time soon. Given the ubiquity of graph algorithms, how long should one wait to propose or even discuss additions into the stdlib?

#10

Oh dammit, the Discourse bug has struck again, eating half my message.

Discourse appears to have some sort of anti-feature, or bug, where it
deletes all the text below whatever looks like a row of dashes. Even if
the dashes are part of a code block, or if it isn’t a row of dashes.

So I forgot about it, and half of my message got eaten.

I’m a bit disturbed that apparently nobody commented that my post
appeared to end mid thought :frowning:

Before I waste time resending the missing half of my post, here’s an
experiment. I’m going to send two code blocks below, followed by a
regular paragraph, to see where Discourse cuts the message. Thank you
for your patience.

code block #1
This is to see if I can guard the text from deletion with an x
x
x        a
x        |
x    +---+---+
x    |       |
x    b       c

Following is a duplicate of code block #1 above, except it won’t have
the column of x guarding the ASCII tree diagram. Following the code
block will be another paragraph. If you don’t see a second tree diagram
and a paragraph, you will know that Discourse deleted my text, again.

code block #2
This block has no guard. If you see no tree diagram below,
Discourse has eaten my post.

    a
#11

You are correct that there are multiple libraries on PyPI. Are they
over-engineered? Under-engineered? Do people use them?

Do they share the same API? If they do, that suggests (not proves,
suggests) that this may be a good API, or at least an expected API. If
they don’t share the same API, then there is still doubt about what API
should be used.

What do other languages do?

Pretty much every programming language after Pascal in the 1970s has
provided some sort of standard string-handling facility. Can we say the
same about graphs? If we compare Python to other, newer, languages, does
our lack of graphs seem as poor as standard Pascal’s lack of strings?

Quote:

“Given the ubiquity of graph algorithms, how long should one wait to
propose or even discuss additions into the stdlib?”

Aren’t we proposing and discussing that right now?

#12

Does anyone know where I can report this as bug?

#13

I’m re-sending the second half of my post, which was deleted by
Discourse.

In your example of the family tree, I presume that the graph would be
represented by edges like this:

x        child
x          |
x     +----+----+
x     |         |
x   mother    father

(The edges are implied to be directional.)

So if I have this right, using a dict, we would represent the family
tree as:

# Edges show "is a child of" relationships.
graph = {'Ashley':   ['Susan', 'Richard'],
         'Sandra':   ['Susan', 'Richard'],
         'David':    ['Margaret', 'Joseph'],
         'Richard':  ['Margaret', 'Joseph'],
         'Susan':    ['Patricia', 'James'],
         'Michael':  ['Patricia', 'James'],
         'Margaret': [],
         'Joseph':   [],
         'Patricia': [],
         'James':    [],
         }

With a dict, we can easily manipulate the graph by adding, removing or
modifying nodes and edges, or to copy it, or manipulate it in any way,
e.g. to produce the graph showing the opposite relationship, “is a
parent of”. I think using functions would make that quite difficult.

Using your Person class instead of strings, it wouldn’t be difficult to
generate the equivalent dict programmatically.

graph = {person: [person.mom, person.pop] for person in persons}

But apart from my concerns about your use of functions to represent
edges, this does sound like a very interesting proposal.

#14

Hi David,

I’m a little concerned about the verbosity of the names.

graphlib.depth_first_traversal.postorder

would get a bit annoying to type and read after a while, I think. I
think that graph terminology is verbose enough and technical enough that
a small amount of abbreviation is justifiable.

Passing an iterable of starting nodes rather than just a single node
seems like an over-generalisation to me. If you want to re-run the same
traversal over the same graph multiple times with different starting
points, use a loop.

# I'm using "traverse" as a stand in for any traversal method
for start in nodes:
    traverse(start, graph)

This API:

traverse(nodes, graph)

assumes that you don’t care where one run ends and the next begins,
which I think is unlikely.

Your bare, undotted depth_first_traversal() function seems to be a bit
odd. Do I understand correctly that you have this:

depth_first_traversal(nodes, graph,
#15

Raymond Hettinger’s 2019 PyCon talk included a relevant graph-searching “Puzzle solver” here where the user inherits from Puzzle and overrides .__iter__() to return an iterator that yields the adjacent Puzzles. It also allows overriding .isgoal() to specify what the destination is and overriding .canonical() to count symmetric nodes as the same. It then has a solve(pos, depthFirst=False) method that returns a list of the steps.

I think I would prefer to pass in functions (or mappings I suppose) rather than subclassing, but this is certainly an interesting rendition of the sort of ideas discussed in this thread.

1 Like
#16

David replies:

But you still need to specify what all the nodes and their neighbours

are somewhere. You give the example of:

lambda node: node.my_neighbors_list

but that’s useless unless you actually have a graph of nodes somewhere,

and to get that, you have to do a ton of work:

  • you need a Node class with a my_neighbors_list attribute;

  • the instances have to be mutable, because each node needs to

    store a reference to its neighbours, and the neighbours may not

    exist yet;

  • you need to create the node instances;

  • then you need to go back and fill in the older nodes that are

    connected to the new node (hence why they have to be mutable)

  • which probably means tracking nodes as named variables;

  • because the nodes are mutable, and stores references to their

    neighbours, you can’t re-use nodes in two graphs at the same time;

  • and then once you have your implicit graph hidden inside this

    network of node instances, it’s not very easy to make a copy of

    the graph, or print it.

Until you have set up the actual graph structure itself, your callback

function does nothing.

The question is whether the graph structure should be implicit in a

bunch of relationships between nodes, or explicit in a dict.

If it is explicit in a dict, you can still use a Node class, you can

still make the nodes mutable, but you don’t have to. You can use strings

or ints or anything you like, so long as they are hashable.

As I see it, your function API does support the dict data structure.

(Just pass graph.get as your function.) But why overgeneralise the API

to support an overly complex, less usable, awkward, less comprehensible

interface? It just seems like YAGNI to me.

Great. But that’s more than can be said for the readers of the code, who

are not likely to be able to read or maintain the graph easily given

your function API, unless it is written as a dict, in which case your

function API is redundant.

It’s a dict with a bunch of pointers. If you’re worried about that,

you’re probably using the wrong language.

If you want two graphs with the function API using mutable nodes, you

have to duplicate the nodes. Using the dict API, you don’t have to

duplicate the nodes, just make a modified copy of the dict.

The bottom line here is that your function API assumes (not requires)

that the information about edges is buried inside mutable nodes. So you

need a callback function that takes a node and returns a list of new

nodes.

The dict API assumes (not requires) that the information about edges is

distinct from the nodes. We have a standard data structure for graphs,

the dict, but anything that duck-types as a dict is probably sufficient.

It is a cleaner design:

  • conceptually, the nodes and the relationship between nodes are

    separate;

  • the only data structure needed is the dict, which is probably as

    efficient and fast as anything in Python;

  • so long as the nodes are hashable, you can use anything;

  • dicts are easy to copy, modify and print; we get all that

    functionality for free;

  • and if I really, really want to write a Node class, I can still do

    that.

#17

Dammit, Discourse strikes again. Here is the rest of the text of my
previous message, fixed so that it (hopefully!) doesn’t delete my
content.

Your bare, undotted depth_first_traversal() function seems to be a bit
odd. Do I understand correctly that you have this:

depth_first_traversal(nodes, graph, *,
                      preorder=None,
                      postorder=None,
                      inorder=None,
                      revisit=None)

where the keyword parameters take a callback function.

What if the caller doesn’t provide any callbacks at all? Or more than
one? What is the use-case of the revisit callback?

I know that the Visitor pattern using callbacks is traditional for
traversal algorithms, but I’m not sure that this is a great fit for
Python idioms. If you just yield the nodes, the caller can iterate over
the nodes and do whatever they want, there in the loop directly, rather
than write a callback.

You suggest that inorder traversal is not very useful. Trees are a
subset of graphs, and inorder traversal of binary trees is quite useful.

#18

“Aren’t we proposing and discussing that right now?”

Yes. I was responding to post preceding mine.

#19

It seems to me that we’re discussing the design of the OP’s graph library. Which is fine, as a topic of conversation. But no-one’s discussing whether it’s suitable for inclusion in the stdlib, because (as I said in my post) it’s too under-developed at the moment to be ready for that.

1 Like
#20

On the one hand I agree that they’re inconveniently long. On the other hand, these names are easily searchable (they have wikipedia articles by those names) and if we abbreviated them then they would not be as understandable.

The purpose of those callbacks is for the user to implement programs which are based on a depth first traversal.
The callbacks allow users to do stuff at each step of the traversal.
It has 4 different callbacks for each of the different ways it can enter a node on the traversal.

  • The revisit callback is called when it visits a node that’s already been visited. The revisited nodes are not traversed (that would cause infinite recursion) but they are presented to the users via this special callback.

In my limited experience I haven’t every needed one.
That’s interesting to know, that other people have found uses for it.

  • To my knowledge, I’m the first and only to use a function to specify the edges of a graph.
  • The API of existing libraries fall into three categories:
    1. Define a Graph class for their library (and different libraries each define their own class).
    2. Use a sparse matrix. This is the best solution for crunching numbers.
    3. Use a dictionary.

Historically, graphs have never been included in standard libraries. But then python 3.9 added the graphlib module which I took as an invitation addressed to me.