dyval.DAG.dag

class promptbench.dyval.DAG.dag.BaseDAG(add_cycles=0)

Bases: object

Base class for Directed Acyclic Graph (DAG) structures.

This class provides foundational functionality for DAG operations, including node management, topological sorting, and cycle detection.

Attributes:

symbols_setstr

A string of alphabets used in generating unique node names.

forbidden_namesset of str

A set of names that are not allowed for nodes.

name_generatorgenerator

A generator for producing unique node names.

nodeslist of Node

The list of nodes in the DAG.

add_cyclesint

The number of cycles to add to the DAG.

Methods:

get_node_by_name(name)

Retrieves a node by its name.

topological_sort()

Performs topological sorting on the DAG nodes.

check_link_constraint(father_node, child_node)

Checks if a link between two nodes is valid.

generate_cycles()

Introduces cycles in the DAG.

_form_cycle(start, end)

Checks if adding a link forms a cycle.

_generate_name()

Generates a unique name for a node.

_get_reachable_nodes(start)

Finds all nodes reachable from a given starting node.

generate_cycles()

Introduce cycles in the DAG.

get_node_by_name(name)
topological_sort()
class promptbench.dyval.DAG.dag.GeneralDAG(num_nodes, min_links_per_node=1, max_links_per_node=3, add_cycles=0)

Bases: BaseDAG

Represents a general Directed Acyclic Graph with customizable parameters.

Inherits from BaseDAG and allows for specifying the number of nodes and the range of links per node.

Parameters:

num_nodesint

The number of nodes in the DAG.

min_links_per_nodeint

The minimum number of links each node can have.

max_links_per_nodeint

The maximum number of links each node can have.

add_cyclesint, optional

The number of cycles to be added to the DAG (default is 0).

Methods:

generate_dag(num_nodes)

Generates the DAG with the specified number of nodes.

generate_dag(num_nodes)
class promptbench.dyval.DAG.dag.Node(value=None, op=None, name=None, children=None)

Bases: object

Represents a node in a graph or a tree structure.

Attributes:

valueAny

The value stored in the node.

opAny, optional

The operation or function associated with the node.

namestr, optional

The unique identifier of the node.

childrenlist of Node, optional

The children nodes of this node.

class promptbench.dyval.DAG.dag.TreeDAG(depth, num_children_per_node=2, extra_links_per_node=1, add_cycles=0)

Bases: BaseDAG

Represents a Directed Acyclic Graph built from a tree structure.

This class extends BaseDAG and allows for the creation of a DAG from a tree, with additional properties like depth, number of children per node, and extra links per node.

Parameters:

depthint

The depth of the tree to generate.

num_children_per_nodeint

The number of children each node can have.

extra_links_per_nodeint

The number of extra links per node.

add_cyclesint, optional

The number of cycles to be added to the DAG (default is 0).

Methods:

generate_tree(depth)

Generates the tree structure.

update_values()

Updates the value of each node after adding links.

check_link_constraint(father_node, child_node)

Defines constraints for link addition between nodes.

check_uni_ops()

Checks if all nodes’ operations are unary.

generate_dag()

Generates the DAG based on the tree.

collect_nodes(node)

Collects all nodes from a given starting node.

check_uni_ops()
collect_nodes(node)
generate_dag()
generate_tree(depth)
update_values()