A simple functional graph library. Keys used to identify nodes can be any comparable and nodes can have any kind of metadata associated with them.
All operations that look at a single node are at most O(log n).
Operations that look at all elements in the graph are at most O(n log n).
Create an empty graph.
Insert a node. Does not overwrite metadata if node already exists.
Update metadata for a node. Creates the node if it does not already exist.
Insert an edge between two nodes. Creates any nodes that do not already exist.
Remove a node by its key. No-op if node doesn't exist.
Remove an edge identified by its source and target keys. No-op if source, target or edge doesn't exist.
Get the data associated with a specific node.
Determine if a node identified by a key is in the graph.
Determine if an edge identified by a pair of keys is in the graph.
Get the set of incoming edges to a node.
Get the set of outgoing edges from a node.
Determine the number of nodes in the graph.
Get the keys for all nodes in the graph.
Get the (key, data) pair for each node in the graph.
Get the (from, to) pair for each edge in the graph.
Determine if a graph contains any loops or cycles.
Get the set of reachable nodes from a key, following outgoing edges any number of steps.
Returns the relative ordering of two keys in a directed acyclic graph. If there is a path from a to b over outgoing edges, a is Before b. If there is no path between them, they compare Concurrent.
Apply a function to the data associated with each node in a graph.
Fold over the node keys and data in a graph, in order from lowest key to highest key.
Fold over the node keys and data in a graph, in order from highest key to lowest key.
Partition a graph into two parts, one with the nodes where the predicate function returned True, and one where it returned False.
Join two graphs together. If an edge appears between two nodes in either of the graphs, it will be in the resulting graph. If a node identified by a specific key appears in any of the graphs, it will be in the resulting graph. If both graphs have metadata for the same key, the metadata in the left graph will be used.
Create a graph based on the intersection of two graphs. If both graphs have the same node, edge or associated metadata, it will be in the resulting graph. If one graph has metadata and the other only has the node, the node will be in the resulting graph, but the metadata will not.
Get a list of all keys according to a postorder traversal of a spanning tree of the graph.
Get a topological sorting of the graph, if the graph doesn't contain any loops or cycles.
Enable the dynamic reachability optimization for directed acyclic graphs. This allows O(log n) queries for the relative ordering of two elements in a partially ordered set, and O(log n) queries for the set of nodes that are reachable from a specific node.
The downside is that modifying the graph now takes O(log n * (nodes before this node)) time on average. Modifying the beginning of the graph is thus quite fast, but inserting an edge at the end takes O(n log n) time. The other downside is that this optimization only works on directed acyclic graphs.
Disable the dynamic reachability optimization for directed acyclic graphs.
A directed graph.
Graph Int Stringis a graph that usesInts for identifying its nodes, and lets you store aStringon each node.