Adjacency-list-backed representations of graphs, with methods for performing graph analysis using dynamic programming.
An Adjacency List representation of a Directed Acyclical Graph An adjacency list contains a list of nodes, and for each node, a reference to other nodes. These references represent edges between the nodes. A directed acylic graph (DAG) is a graph that contains directed edges only, and contains zero cycles. - https://en.wikipedia.org/wiki/Adjacency_list - https://en.wikipedia.org/wiki/Directed_acyclic_graph
Construct a DAG from a list of node labels and weighted edges.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
nodes
|
list[str]
|
Unique string labels for each node. |
required |
edges
|
list[tuple[int, int, float]]
|
Tuples of (from_index, to_index, weight) defining directed edges. |
required |
Raises:
| Type | Description |
|---|---|
ValueError
|
If node labels are not unique, edges reference invalid nodes, weights are negative, duplicate edges exist, or the graph contains a cycle. |
Return True if the graph is weakly connected.
A DAG is weakly connected if every node is reachable from every other node when edge directions are ignored. Returns False for empty graphs.
Return True if outgoing edge weights from each node sum to 1 (or 0 for leaves).
True if the graph is unweighted, false otherwise.
A graph is unweighted if all stored edge weights are either 0 or 1.
Return the index of the node with the given label.
Raises:
| Type | Description |
|---|---|
ValueError
|
If no node with the given label exists in the graph. |
Return an iterator of (label, index) pairs for nodes with no outgoing edges.
Return an iterator of (label, index) pairs for all nodes in the graph.
normalised() -> DirectedAcyclicGraph
Return a new DAG with outgoing edge weights normalised to sum to 1 per node.
Leaf nodes (with zero total outgoing weight) are left unchanged.