Graphs

Context

Data structure than links a node to the rest of the graph.

Fields

• graph: Dynamic graph that contains the node.
• node: Node inside the graph.

Details

A Context object wraps references to a node and its associated graph. The purpose of this structure is to be able to test relationships among nodes within a graph (from with a query or rule), as well as access the data stored in a node (with data()) or the graph (with graph_data()).

Users do not build Context objects directly but they are provided by VPL as inputs to the user-defined functions inside rules and queries.

Graph(;axiom, rules = nothing, data = nothing)

Create a dynamic graph from an axiom, one or more rules and, optionally, graph-level variables.

Arguments

• axiom: A single object inheriting from Node or a subgraph generated with the graph construction DSL. It should represent the initial state of the dynamic graph.

Keywords

• rules: A single Rule object or a tuple of Rule objects (optional). It should include all graph-rewriting rules of the graph.
• data: A single object of any user-defined type (optional). This will be the graph-level variable accessible from any rule or query applied to the graph.
• FT: Floating-point precision to be used when generating the 3D geometry associated to a graph.

Details

All arguments are assigned by keyword. The axiom and rules are deep-copied when creating the graph but the graph-level variables (if a copy is needed due to mutability, the user needs to care of that).

Returns

An object of type Graph representing a dynamic graph. Printing this object results in a human-readable description of the type of data stored in the graph.

Examples

julia> struct A0 <: Node end;

julia> struct B0 <: Node end;

julia> axiom = A0() + B0();

julia> no_rules_graph = Graph(axiom = axiom);

julia> rule = Rule(A0, rhs = x -> A0() + B0());

julia> rules_graph = Graph(axiom = axiom, rules = rule);

Node

Abstract type from which every node in a graph should inherit. This allows using the graph construction DSL.

This type is mutable.

Example

julia> struct bar <: Node
           x::Int
       end;

julia> b1 = bar(1);

julia> b2 = bar(2);

julia> b1 + b2;

Query(N::DataType; condition = x -> true)

Create a query that matches nodes of type nodetype and a condition.

Arguments

• N::DataType: Type of node to be matched.

Keywords

• condition: Function or function-like object that checks if a node should be selected.

Details

If the nodetype should refer to a concrete type and match one of the types stored inside the graph. Abstract types or types that are not contained in the graph are allowed but the query will never return anything.

The condition must be a function or function-like object that takes a Context as input and returns true or false. The default condition always return true such that the query will

Returns

It returns an object of type Query. Use apply() to execute the query on a dynamic graph.

Examples

julia> struct A <: Node end;

julia> struct B <: Node end;

julia> axiom = A() + B();

julia> g = Graph(axiom = axiom);

julia> query = Query(A);

julia> apply(g, query);

Rule(nodetype; lhs = x -> true, rhs = x -> nothing, captures = false)

Create a replacement rule for nodes of type nodetype.

Arguments

• nodetype: Type of node to be matched.

Keywords

• lhs: Function or function-like object that takes a Context object and returns whether the node should be replaced or not (with true or false).
• rhs: Function or function-like object that takes one or more Context objects and returns a replacement graph or nothing. If it takes several inputs, the first one will correspond to the node being replaced.
• captures: Either false or true to indicate whether the left-hand side of the rule is capturing nodes in the context of the replacement node to be used for the construction of the replace graph.

Details

See VPL documentation for details on rule-based graph rewriting.

Return

An object of type Rule.

Examples

julia> struct A <: Node end;

julia> struct B <: Node end;

julia> axiom = A() + B();

julia> rule = Rule(A, rhs = x -> A() + B());

julia> rules_graph = Graph(axiom = axiom, rules = rule);

julia> rewrite!(rules_graph);

children(c::Context)

Returns all the children of a node as Context objects.

children(n::GraphNode, g::StaticGraph)

Return an iterator over the children nodes of a given graph node in a static graph.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node for which to retrieve the children.
• g::StaticGraph: The static graph containing the node.

Returns

An iterator over the GraphNode objects that are children of n in the static graph.

ancestor(node::GraphNode, g::Graph, condition, maxlevel::Int; level::Int=1)

Retrieve the ancestor of a graph node that satisfies a given condition, with optional recursive search up to a maximum depth.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• node::GraphNode: The node from which to start the ancestor search.
• g::Graph: The graph containing the node.
• condition: A function that takes a Context and returns true if the ancestor matches the condition.
• maxlevel::Int: The maximum depth to search for ancestors.
• level::Int=1: (Optional) The current recursion level (default is 1).

Returns

The ancestor node that matches the condition, or missing if none is found or the node is a root node.

ancestor(c::Context; condition = x -> true, max_level::Int = typemax(Int))

Returns the first ancestor of a node that matches the condition. Intended to be used within a rule or query.

Arguments

• c::Context: Context associated to a node in a dynamic graph.

Keywords

• condition: An user-defined function that takes a Context object as input and returns true or false.
• max_level::Int: Maximum number of steps that the algorithm may take when traversing the graph.

Details

If has_ancestor() returns false for the same node and condition, ancestor() will return missing, otherwise it returns the Context associated to the matching node

Returns

Return a Context object or missing.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(1) + (B1(1) + A1(3), B1(4));

julia> g = Graph(axiom = axiom);

julia> function qfun(n)
           na = ancestor(n, condition = x -> (data(x).val == 1))
           if !ismissing(na)
               data(na) isa B1
           else
               false
           end
       end;

julia> Q1 = Query(A1, condition = qfun);

julia> R1 = apply(g, Q1);

julia> Q2 = Query(B1, condition = qfun);

julia> R2 = apply(g, Q2);

apply!(output, g::Graph, query::Query)

Fill an array output with all the nodes in the graph that match the query supplied by the user.

Examples

julia> struct A <: Node end;

julia> struct B <: Node end;

julia> axiom = A() + B();

julia> g = Graph(axiom = axiom);

julia> output = A[];

julia> query = Query(A);

julia> apply!(output, g, query);

apply(g::Graph, query::Query)

Return an array with all the nodes in the graph that match the query supplied by the user.

Examples

julia> struct A <: Node end;

julia> struct B <: Node end;

julia> axiom = A() + B();

julia> g = Graph(axiom = axiom);

julia> query = Query(A);

julia> apply(g, query);

calculate_resolution(;width = 1024/300*2.54, height = 768/300*2.54,
                      format = "raster", dpi = 300)

Calculate the resolution required to achieve a specific width and height (in cm) of the exported image, with a particular dpi (for raster formats).

data(c::Context)

Returns the data stored in a node. Intended to be used within a rule or query.

data(n::GraphNode)

Returns the data stored in a graphnode. Users will generally not use this method as they will normally deal with Context objects.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

data(g::Graph)

Returns the graph-level variables.

Example

julia> struct A <: Node end;

julia> axiom = A();

julia> g = Graph(axiom = axiom, data = 2);

julia> data(g);

draw(g::Graph; resolution = (1920, 1080), nlabels_textsize = 15, arrow_size = 15,
     node_size = 5)

Visualize a graph as network diagram.

Arguments

• g::Graph: The graph to be visualized.

Keywords

• resolution = (1920, 1080): The resolution of the image to be rendered, in pixels (online relevant for native and web backends). Default resolution is HD.
• nlabels_textsize = 15: Customize the size of the labels in the diagram.
• arrow_size = 15: Customize the size of the arrows representing edges in the diagram.
• node_size = 5: Customize the size of the nodes in the diagram.

Details

By default, nodes are labelled with the type of data stored and their unique ID. See function node_label() to customize the label for different types of data.

See save from FileIO to export the network diagram as a raster or vector image (depending on the backend). The function calculate_resolution() can be useful to ensure a particular dpi of the exported image (assuming some physical size).

The graphics backend will interact with the environment where the Julia code is being executed (i.e., terminal, IDE such as VS Code, interactive notebook such as Jupyter or Pluto). These interactions are all controlled by the graphics package Makie that VPL relies on. Some details on the expected behavior specific to draw() can be found in the general VPL documentation.

Returns

This function returns a Makie Figure object, while producing the visualization as a side effect.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(1) + (B1(1) + A1(3), B1(4));

julia> g = Graph(axiom = axiom);

julia> import CairoMakie; # or GLMakie, WGLMakie, etc.

julia> draw(g);

draw(g::StaticGraph; resolution = (1920, 1080), nlabels_textsize = 15, arrow_size = 15,
     node_size = 5)

Equivalent to the method draw(g::Graph; kwargs...) but to visualize static graphs (e.g., the axiom of a graph).

generate_id()

Generate a new unique ID for a node in a graph and update the ID counter.

Returns

The new unique ID (an atomic Int).

get_descendant(c::Context; condition = x -> true, max_level::Int = typemax(Int))

Returns the first descendant of a node that matches the condition. Intended to be used within a rule or query.

getdescendant is an alias for get_descendant for compatibility with AbstractTrees.jl

Arguments

• c::Context: Context associated to a node in a dynamic graph.

Keywords

• condition: An user-defined function that takes a Context object as input and returns true or false.
• max_level::Int: Maximum number of steps that the algorithm may take when traversing the graph.

Details

If has_descendant() returns false for the same node and condition, get_descendant() will return missing, otherwise it returns the Context associated to the matching node.

Return

Return a Context object or missing.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(1) + (B1(1) + A1(3), B1(4));

julia> g = Graph(axiom = axiom);

julia> function qfun(n)
           na = get_descendant(n, condition = x -> (data(x).val == 1))
           if !ismissing(na)
               data(na) isa B1
           else
               false
           end
       end;

julia> Q1 = Query(A1, condition = qfun);

julia> R1 = apply(g, Q1);

julia> Q2 = Query(B1, condition = qfun);

julia> R2 = apply(g, Q2);

get_id!()

Get the current value of the ID counter for generating unique IDs for nodes in graphs.

Returns

The current value of the ID counter (an atomic Int).

get_root(g::Graph)
get_root(g::StaticGraph)

Extract the root node of a Graph or StaticGraph object.

You may also use getroot (for compatibility with AbstractTrees.jl).

Returns

The GraphNode object that is the root of the graph.

graph(c::Context)

Returns the dynamic graph stored inside a Context object. Intended to be used within a rule or query.

Arguments

• c::Context: The context associated to a node in a dynamic graph.

Returns

The Graph object contained in the context.

graph_data(c::Context)

Returns the graph-level variables. Intended to be used within a rule or query.

has_ancestor(node::GraphNode, g::Graph, condition, maxlevel::Int; level::Int=1)

Check if a graph node has an ancestor that satisfies a given condition, with optional recursive search up to a maximum depth.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• node::GraphNode: The node from which to start the ancestor search.
• g::Graph: The graph containing the node.
• condition: A function that takes a Context and returns true if the ancestor matches

the condition.

• maxlevel::Int: The maximum depth to search for ancestors.
• level::Int=1: (Optional) The current recursion level (default is 1).

Returns

A tuple (found::Bool, steps::Int) where found is true if an ancestor matching the condition is found, and steps is the number of steps taken in the search.

has_ancestor(c::Context; condition = x -> true, max_level::Int = typemax(Int))

Check if a node has an ancestor that matches the condition. Intended to be used within a rule or query.

Arguments

• c::Context: Context associated to a node in a dynamic graph.

Keywords

• condition: An user-defined function that takes a Context object as input and returns true or false.
• max_level::Int: Maximum number of steps that the algorithm may take when traversing the graph.

Details

This function traverses the graph from the node associated to c towards the root of the graph until a node is found for which condition returns true. If no node meets the condition, then it will return false. The defaults values for this function are such that the algorithm always returns true after one step (unless it is applied to the root node) in which case it is equivalent to calling has_parent on the node.

The number of levels that the algorithm is allowed to traverse is capped by max_level (mostly to avoid excessive computation, though the user may want to specify a meaningful limit based on the topology of the graphs being used).

The function condition should take an object of type Context as input and return true or false.

Returns

Return a tuple with two values a Bool and an Int, the boolean indicating whether the node has an ancestor meeting the condition, the integer indicating the number of levels in the graph separating the node an its ancestor.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(2) + (B1(1) + A1(3), B1(4));

julia> g = Graph(axiom = axiom);

julia> function qfun(n)
            has_ancestor(n, condition = x -> data(x).val == 1)[1]
       end;

julia> Q1 = Query(A1, condition = qfun);

julia> R1 = apply(g, Q1);

julia> Q2 = Query(B1, condition = qfun);

julia> R2 = apply(g, Q2);

has_children(c::Context)

Check if a node has at least one child and return true or false. Intended to be used within a rule or query.

has_children(n::GraphNode)

Check if a graph node has any children.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node to check for children.

Returns

true if the node has one or more children, otherwise false.

has_descendant(node::GraphNode, g::Graph, condition, maxlevel::Int; level::Int=1)

Check if a graph node has a descendant that satisfies a given condition, with optional recursive search up to a maximum depth.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• node::GraphNode: The node from which to start the descendant search.
• g::Graph: The graph containing the node.
• condition: A function that takes a Context and returns true if the descendant

matches the condition.

• maxlevel::Int: The maximum depth to search for descendants.
• level::Int=1: (Optional) The current recursion level (default is 1).

Returns

A tuple (found::Bool, steps::Int) where found is true if a descendant matching the condition is found, and steps is the number of steps taken in the search.

has_descendant(c::Context; condition = x -> true, max_level::Int = typemax(Int))

Check if a node has a descendant that matches the optional condition. Intended to be used within a rule or query.

Arguments

• c::Context: Context associated to a node in a dynamic graph.

Keywords

• condition: An user-defined function that takes a Context object as input and returns true or false.
• max_level::Int: Maximum number of steps that the algorithm may take when traversing the graph.

Details

This function traverses the graph from the node associated to c towards the leaves of the graph until a node is found for which condition returns true. If no node meets the condition, then it will return false. The defaults values for this function are such that the algorithm always returns true after one step (unless it is applied to a leaf node) in which case it is equivalent to calling has_children on the node.

The number of levels that the algorithm is allowed to traverse is capped by max_level (mostly to avoid excessive computation, though the user may want to specify a meaningful limit based on the topology of the graphs being used).

The function condition should take an object of type Context as input and return true or false.

Returns

Return a tuple with two values a Bool and an Int, the boolean indicating whether the node has an ancestor meeting the condition, the integer indicating the number of levels in the graph separating the node an its ancestor.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(2) + (B1(1) + A1(3), B1(4));

julia> g = Graph(axiom = axiom);

julia> function qfun(n)
           has_descendant(n, condition = x -> data(x).val == 1)[1]
       end;

julia> Q1 = Query(A1, condition = qfun);

julia> R1 = apply(g, Q1);

julia> Q2 = Query(B1, condition = qfun);

julia> R2 = apply(g, Q2);

has_parent(c::Context)

Check if a node has a parent and return true or false. Intended to be used within a rule or query.

has_parent(n::GraphNode)

Check if a graph node has a parent.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node to check for a parent.

Returns

true if the node has a parent (i.e., its parent ID is not missing), otherwise false.

is_leaf(c::Context)

Check if a node is a leaf in the graph (i.e., has no children) and return true or false. Intended to be used within a rule or query.

is_leaf(n::GraphNode)

Check if a graph node is a leaf node (i.e., has no children).

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node to check.

Returns

true if the node is a leaf node (has no children), otherwise false.

is_root(c::Context)

Check if a node is the root of the graph (i.e., has no parent) and return true or false. Intended to be used within a rule or query.

isroot is an alias for is_root for compatibility with AbstractTrees.jl

node_label(n::Node, id)

Function to construct a label for a node to be used by draw() when visualizing. The user can specialize this method for user-defined data types to customize the labels. By default, the type of data stored in the node and the unique ID of the node are used as labels.

reset_id!()

Reset the ID counter for generating unique IDs for nodes in graphs to zero.

Returns

The new value of the ID counter (an atomic Int).

rewrite!(g::Graph)

Apply the graph-rewriting rules stored in the graph.

Arguments

• g::Graph: The graph to be rewritten. It will be modified in-place.

Details

This function will match the left-hand sides of all the rules in a graph. If any node is matched by more than one rule this will result in an error. The rules are then applied in order to replaced the matched nodes with the result of executing the right hand side of the rules. The rules are applied in the order in which they are stored in the graph but the order in which the nodes are processed is not defined. Since graph rewriting is semantically a parallel process, the rules should not be rely on any particular order for their functioning.

Returns

This function returns nothing, but the graph passed as input will be modified by the execution of the rules.

Examples

julia> struct A <: Node end;

julia> struct B <: Node end;

julia> axiom = A() + B();

julia> rule = Rule(A, rhs = x -> A() + B());

julia> g = Graph(axiom = axiom, rules = rule);

julia> rewrite!(g);

rules(g::Graph)

Returns a tuple with all the graph-rewriting rules stored in a dynamic graph

Examples

julia> struct A <: Node end;

julia> struct B <: Node end;

julia> axiom = A() + B();

julia> rule = Rule(A, rhs = x -> A() + B());

julia> rules_graph = Graph(axiom = axiom, rules = rule);

julia> rules(rules_graph);

set_id!(id)

Set the ID counter for generating unique IDs for nodes in graphs to any integer value id.

Returns

The new value of the ID counter (an atomic Int).

static_graph(g::Graph)

Return the internal StaticGraph stored inside a dynamic Graph object.

Arguments

• g::Graph: The dynamic graph from which to retrieve the internal static graph.

Returns

The StaticGraph object contained within the dynamic graph.

traverse(g::Graph; fun = () -> nothing, order = "any", ID = root_id(g))
traverse(g::StaticGraph; fun = () -> nothing, order = "any", ID = root_id(g))

Iterates over all the nodes in the graph and execute for the function fun on each node

Arguments

• g::Graph or g::StaticGraph: The graph object that will be traversed.

Keywords

• fun: A function or function-like object defined by the user that will be applied to each node.
• order: Order in which the nodes in the graph will be visited. It can be "any" (default), "dfs" (depth-first search) or "bfs" (breadth-first search).
• ID: The ID of the node where the traveral should start. By default, traversal starts at the root of the graph.

Details

When order = "any traveral happens in the order in which the nodes are stored in the graph. This order is arbitrary (it does not correspond to the order in which nodes are created) but it should be reproducible (i.e., the same code will store the nodes in the same order). For algorithms that require use any = "dfs" or any = "bfs".

When order = "dfs" the traveral happens in a depth-first order. That is, all nodes in a branch of the graph are visited until reach a leaf node, then moving to the next branch. Hence, this algorithm should always generate the same result when applied to the same graph (assuming the user-defined function is not stochastic)

When order = "bfs" the traveral happens in a breadth-first order. That is, all nodes at a given depth of the the graph are visited first, then moving on to the next level. Hence, this algorithm should always generate the same result when applied to the same graph (assuming the user-defined function is not stochastic). For a version of this function that us depth-first order see traverse_dfs.

This function does not store any results generated by fun. Hence, if the user wants to keep track of such results, they should be stored indirectly (e.g., via a global variable or internally by creating a functor).

The function or function-like object provided by the user should take only one argument that corresponds to applying data() to each node in the graph. Several methods of such function may be defined for different types of nodes in the graph. Since the function will use the data stored in the nodes, relations among nodes may not be used as input. For algorithms where relations among nodes are important, the user should be using queries instead (see Query and general VPL documentation).

Returns

This function returns nothing but fun may have side-effects.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> struct Foo
         vals::Vector{Int}
       end;

julia> function (f::Foo)(x)
         push!(f.vals, x.val)
       end;

julia> f = Foo(Int[]);

julia> axiom = A1(2) + (B1(1) + A1(3), B1(4));

julia> g = Graph(axiom = axiom);

julia> traverse(g, fun = f);

julia> traverse(g, fun = f, order = "dfs");

julia> traverse(g, fun = f, order = "bfs");

traverse_bfs(g::Graph; fun = () -> nothing, ID = root_id(g))
traverse_bfs(g::StaticGraph, fun, ID)

Iterates over all the nodes in the graph in breadth-first order and executes the function fun on each node.

Arguments

• g::Graph or g::StaticGraph: The graph object to be traversed.

Keywords

• fun: A function or function-like object defined by the user that will be applied to each node.
• ID: The ID of the node where the traversal should start. By default, traversal starts at

the root of the graph.

Details

Traversal happens in breadth-first order: all nodes at a given depth are visited first, then the algorithm moves to the next level. The function provided by the user should take only one argument corresponding to the data stored in each node. Results generated by fun are not stored by this function; side effects should be managed by the user.

Returns

This function returns nothing but fun may have side-effects.

traverse_dfs(g::Graph; fun = () -> nothing, ID = root_id(g))
traverse_dfs(g::StaticGraph, fun, ID)

Iterates over all the nodes in the graph in depth-first order and executes the function fun on each node.

Arguments

• g::Graph or g::StaticGraph: The graph object to be traversed.

Keywords

• fun: A function or function-like object defined by the user that will be applied to each node.
• ID: The ID of the node where the traversal should start. By default, traversal starts at the root of the graph.

Details

Traversal happens in depth-first order: all nodes in a branch are visited until a leaf node is reached, then the algorithm moves to the next branch. The function provided by the user should take only one argument corresponding to the data stored in each node. Results generated by fun are not stored by this function; side effects should be managed by the user.

Returns

This function returns nothing but fun may have side-effects.

GR.DiGraph(g::Graph)

Translate a dynamic Graph object into a directed graph (DiGraph) structure for visualization with GraphMakie. This method forwards the translation to the underlying static graph contained in the Graph object.

Arguments

• g::Graph: The dynamic graph to be translated into a DiGraph.

Returns

A tuple (dg, labels, n) where:

• dg: The constructed DiGraph object.
• labels: An array of labels for each node.
• n: The number of nodes in the graph.

GR.DiGraph(g::StaticGraph)

Translate a static graph into a directed graph (DiGraph) structure for visualization with GraphMakie. Nodes are labelled using node_label, and edges represent parent-child relationships.

Arguments

• g::StaticGraph: The static graph to be translated into a DiGraph.

Returns

A tuple (dg, labels, n) where:

• dg: The constructed DiGraph object.
• labels: An array of labels for each node.
• n: The number of nodes in the graph.

GraphNode

Data structure that wraps the contents of a node and includes references to the ids of the parent and children node and the node itself. Users do not build GraphNode objects directly, this is always handled by VPL when creating or modifying a graph.

This type is mutable. All fields can be accessed through methods with the same name as the field.

Fields

• data: Data stored in the node, which should inherit from Node (i.e., the object the user creates).
• children_id::OrderedSet{Int}: Ids of the children nodes.
• parent_id::Union{Int, Missing}: Id of the parent node. If the node is a root node, this is missing.
• self_id::Int: Id of this node.

StaticGraph(n::GraphNode)

Create a StaticGraph from a single GraphNode. This is useful for initializing a graph with a root node.

Users will generally not use this method as they will normally deal with Graph objects rather than StaticGraph directly.

Arguments

• n::GraphNode: The GraphNode to be used as the root of the graph.

Returns

A StaticGraph object containing the node.

StaticGraph(n::Node)

Create a StaticGraph from a single object that inherits from Node.

Users will generally not use this method as they will normally deal with Graph objects rather than StaticGraph directly.

Arguments

• n::Node: The object that inherits from Node to be used as the root of the graph.

Returns

A StaticGraph object containing the node.

StaticGraph()

Generate an empty StaticGraph object.

Users will generally not use this method as they will normally deal with Graph objects rather than StaticGraph directly.

Returns

An empty StaticGraph object with no nodes, nodetypes, and both root and insertion IDs set to -1.

getdescendant(node::GraphNode, g::Graph, condition, maxlevel::Int; level::Int=1)

Retrieve the descendant of a graph node that satisfies a given condition, with optional recursive search up to a maximum depth.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• node::GraphNode: The node from which to start the descendant search.
• g::Graph: The graph containing the node.
• condition: A function that takes a Context and returns true if the descendant

matches the condition.

• maxlevel::Int: The maximum depth to search for descendants.
• level::Int=1: (Optional) The current recursion level (default is 1).

Returns

The descendant node that matches the condition, or missing if none is found or the node is a leaf node.

getdescendant(c::Context; condition = x -> true, max_level::Int = typemax(Int))

Returns the first descendant of a node that matches the condition. Intended to be used within a rule or query.

Arguments

• c::Context: Context associated to a node in a dynamic graph.

Keywords

• condition: An user-defined function that takes a Context object as input and returns true or false.
• max_level::Int: Maximum number of steps that the algorithm may take when traversing the graph.

Details

This function traverses the graph from the node associated to c towards the leaves of the graph until a node is found for which condition returns true. If no node meets the condition, then it will return missing.

Returns

Return a Context object or missing.

getroot(g::StaticGraph)
getroot(g::Graph)

Returns the root node of a Graph or StaticGraph object.

Returns

The GraphNode object that is the root of the graph.

isroot(c::Context)

Check if a node is the root of the graph (i.e., has no parent) and return true or false. Intended to be used within a rule or query.

Arguments

• c::Context: The context associated to a node in a dynamic graph.

Returns

true if the node is the root of the graph, otherwise false.

isroot(n::GraphNode)

Check if a graph node is a root node (i.e., has no parent).

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node to check.

Returns

true if the node is a root node (has no parent), otherwise false.

+(n1::GraphNode, n2::GraphNode)

Create a static graph with two nodes, where n1 is the root and n2 is appended as a child at the insertion point.

Arguments

• n1::GraphNode: The node to use as the root of the graph.
• n2::GraphNode: The node to append to the root node.

Returns

A StaticGraph object with n1 as the root and n2 as the insertion point.

+(n::GraphNode, T::Tuple)

Creates a static graph as the result of appending a tuple of graphs or nodes T to the insertion point of the graph rooted at n. Each element in the tuple becomes a branch.

Arguments

• n::GraphNode: The node to use as the root of the graph.
• T::Tuple: A tuple of graphs or nodes to append as branches.

Returns

A StaticGraph with n as the root and all elements of the tuple appended as branches.

+(n1::Node, n2::Node)

Creates a graph with two nodes where n1 is the root and n2 is the insertion point.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(1) + B1(1);

julia> import CairoMakie; # or GLMakie, WGLMakie, etc.

julia> draw(axiom);

+(n::Node, g::StaticGraph)

Creates a graph as the result of appending the static graph g to the node n.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(1) + B1(1);

julia> axiom = A1(2) + axiom;

julia> import CairoMakie; # or GLMakie, WGLMakie, etc.

julia> draw(axiom);

+(g::StaticGraph, T::Tuple)
+(n::Node, T::Tuple)

Creates a graph as the result of appending a tuple of graphs/nodes T to the insertion point of the graph g or node n. Each graph/node in L becomes a branch.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(1) + (B1(1) + A1(3), B1(4));

julia> import CairoMakie; # or GLMakie, WGLMakie, etc.

julia> draw(axiom);

+(g::StaticGraph, n::Node)

Creates a graph as the result of appending the node n to the insertion point of graph g.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(1) + B1(1);

julia> axiom = axiom + A1(2);

julia> import CairoMakie; # or GLMakie, WGLMakie, etc.

julia> draw(axiom);

+(g1::StaticGraph, g2::StaticGraph)

Creates a graph as the result of appending g2 to the insertion point of g1. The insertion point of the final graph corresponds to the insertion point of g2.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom1 = A1(1) + B1(1);

julia> axiom2 = A1(2) + B1(2);

julia> axiom = axiom1 + axiom2;

julia> import CairoMakie; # or GLMakie, WGLMakie, etc.

julia> draw(axiom);

append!(g::StaticGraph, ID, n::GraphNode)

Append a node to a specified node in a static graph.

Arguments

• g::StaticGraph: The static graph to which the node will be appended.
• ID: The ID of the node to which the new node will be appended as a child.
• n::GraphNode: The node to append to the graph.

Returns

The unique ID assigned to the newly appended node.

append!(g::StaticGraph, ID, gn::StaticGraph)

Append a static graph to a specified node in another static graph. The insertion point of the final graph is the insertion point of the appended graph.

Arguments

• g::StaticGraph: The static graph to which the other graph will be appended.
• ID: The ID of the node to which the root of the appended graph will be added as a child.
• gn::StaticGraph: The static graph to append.

Returns

The ID of the insertion point of the appended graph.

empty!(g::StaticGraph)

Remove all nodes and nodetypes from a static graph, making it empty.

Users will generally not use this method as they will normally deal with Graph objects rather than StaticGraph directly.

Arguments

• g::StaticGraph: The static graph to empty.

Returns

Nothing. The graph is modified in place and all nodes and nodetypes are removed.

length(g::StaticGraph)
length(g::Graph)

Returns the number of nodes stored in a StaticGraph or Graph object.

Arguments

• g::StaticGraph or g::Graph: The static graph for which to count the nodes.

Returns

An integer representing the number of nodes in the graph.

parent(n::GraphNode, g::Graph, nsteps::Int=1)

Retrieve the parent or ancestor of a graph node in a graph, with optional recursion depth.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node for which to retrieve the parent or ancestor.
• g::Graph: The graph containing the node.
• nsteps::Int=1: (Optional) The number of steps to go up the ancestor chain (default is

1 for direct parent).

Returns

The parent node if nsteps == 1, or the ancestor node nsteps away. Returns missing if the node is a root node.

parent(c::Context; nsteps::Int)

Returns the parent of a node that is nsteps away towards the root of the graph. Intended to be used within a rule or query.

Arguments

• c::Context: Context associated to a node in a dynamic graph.

Keywords

• nsteps: Number of steps to traverse the graph towards the root node.

Details

If has_parent() returns false for the same node or the algorithm has reached the root node but nsteps have not been reached, then parent() will return missing, otherwise it returns the Context associated to the matching node.

Return

Return a Context object or missing.

Examples

julia> struct A1 <: Node val::Int end;

julia> struct B1 <: Node val::Int end;

julia> axiom = A1(2) + (B1(1) + A1(3), B1(4));

julia> g = Graph(axiom = axiom);

julia> function qfun(n)
           np = parent(n, nsteps = 2)
           !ismissing(np) && data(np).val == 2
       end;

julia> Q1 = Query(A1, condition = qfun);

julia> R1 = apply(g, Q1);

julia> Q2 = Query(B1, condition = qfun);

julia> R2 = apply(g, Q2);

parent(n::GraphNode, g::StaticGraph)

Retrieve the parent node of a graph node from a static graph.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node for which to retrieve the parent.
• g::StaticGraph: The static graph containing the node.

Returns

The parent node of n in the static graph, or missing if the node is a root node.

+(g::StaticGraph, T::Tuple)

Creates a graph as the result of appending a tuple of graphs or nodes T to the insertion point of the static graph g. Each element in the tuple becomes a branch.

Arguments

• g::StaticGraph: The static graph to which the tuple will be appended.
• T::Tuple: A tuple of graphs or nodes to append as branches.

Returns

The modified StaticGraph with all elements of the tuple appended as branches.

add!(g::StaticGraph, N::GraphNode)

Add a new node to a static graph, automatically generating a unique ID for the node.

Arguments

• g::StaticGraph: The static graph to which the node will be added.
• N::GraphNode: The node to add to the graph.

Returns

The unique ID assigned to the newly added node.

add_child!(n::GraphNode, id)

Add a child ID to a graph node.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node to which to add the child.
• id: The ID of the child node to add.

Returns

Nothing. The node is modified in place.

change_id!(n::GraphNode, id)

Set the self ID of a graph node.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node for which to set the self ID.
• id::Int: The new ID to assign to the node.

Returns

Nothing. The node is modified in place.

children_id(n::GraphNode)

Returns the ids of the children nodes.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

has_node(g::StaticGraph, ID)

Check if a static graph contains a node with a given ID.

Users will generally not use this method as they will normally deal with Graph objects rather than StaticGraph directly.

Arguments

• g::StaticGraph: The static graph to check.
• ID: The node ID to check for.

Returns

true if the graph contains a node with the given ID, otherwise false.

has_nodetype(g::StaticGraph, T)

Check if a static graph contains nodes of a given type.

Users will generally not use this method as they will normally deal with Graph objects rather than StaticGraph directly.

Arguments

• g::StaticGraph: The static graph to check.
• T: The node type to check for (usually a DataType).

Returns

true if the graph contains nodes of type T, otherwise false.

id(c::Context)

Returns the unique identifier (ID) of the node stored in a Context object. Intended to be used within a rule or query.

Arguments

• c::Context: The context associated to a node in a dynamic graph.

Returns

The integer ID of the node contained in the context.

insertion(g::StaticGraph)
insertion(g::Graph)

Returns the most recently inserted node in a StaticGraph or Graph object.

Arguments

• g::StaticGraph or g::Graph: The static graph from which to retrieve the node.

Returns

The GraphNode object that is the most recently inserted node in the graph.

insertion_id(g::StaticGraph)
insertion_id(g::Graph)

Returns the ID of the most recently inserted node in a StaticGraph or Graph object.

Arguments

• g::StaticGraph or g::Graph: The static graph from which to retrieve the insertion ID.

Returns

The ID of the most recently inserted node in the graph.

nodes(g::StaticGraph)
nodes(g::Graph)

Returns the nodes stored in a StaticGraph or Graph object.

Arguments

• g::StaticGraph or g::Graph: The static graph from which to retrieve the nodes.

Returns

An OrderedDict{Int, GraphNode} containing all nodes in the graph, indexed by their IDs.

nodetypes(g::StaticGraph)
nodetypes(g::Graph)

Returns the nodetypes stored in a static graph. This is a dictionary mapping each type of node stored in a graph to the ids of the nodes with that type.

Arguments

• g::StaticGraph or g::Graph: The StaticGraph or Graph from which to retrieve the nodetypes.

Returns

An OrderedDict mapping types to OrderedSet{Int} containing the ids of the nodes of that type within the Graph or StaticGraph.

parent_id(n::GraphNode)

Returns the id of the parent node.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

prune!(g::StaticGraph, ID)

Remove a node and all its descendants from a static graph. Updates the root or insertion point if required, and always updates edges from other nodes. The algorithm starts from the leaf nodes and works its way back to the pruning node.

Arguments

• g::StaticGraph: The static graph from which to prune nodes.
• ID: The ID of the node to prune (and all its descendants).

Returns

Nothing. The graph is modified in place.

remove!(g::StaticGraph, ID)

Remove a node from a static graph by its ID. Updates the root and insertion points if necessary. If the graph only contains one node, the graph is emptied.

Arguments

• g::StaticGraph: The static graph from which to remove the node.
• ID: The ID of the node to remove.

Returns

Nothing. The graph is modified in place.

remove_child!(n::GraphNode, id)

Remove the id of a child from a graph node (this does not actually remove the child node from the graph).

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node from which to remove the child.
• id: The ID of the child node to remove.

Returns

Nothing. The node is modified in place.

remove_parent!(n::GraphNode)

Remove the parent ID from a graph node, setting it to missing.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node for which to remove the parent.

Returns

Nothing. The node is modified in place.

replace!(g::StaticGraph, ID, n::GraphNode)

Replace a node in a static graph by a new node. The new node inherits the parents and children of the old node. The old node is removed and the new node is added with the same ID.

Arguments

• g::StaticGraph: The static graph in which to perform the replacement.
• ID: The ID of the node to be replaced.
• n::GraphNode: The new node to insert in place of the old node.

Returns

Nothing. The graph is modified in place.

replace!(g::StaticGraph, ID::Int, gn::StaticGraph)

Replace a node in a static graph by a whole new subgraph. The root node of the subgraph inherits the ID and parents of the old node. The insertion node of the subgraph inherits the children of the old node. The insertion node of the subgraph will change if the replaced node was the insertion point.

Arguments

• g::StaticGraph: The static graph in which to perform the replacement.
• ID: The ID of the node to be replaced.
• gn::StaticGraph: The subgraph to insert in place of the old node.

Returns

Nothing. The graph is modified in place.

root_id(g::StaticGraph)
root_id(g::Graph)

Returns the ID of the root node in a StaticGraph or Graph object.

Arguments

• g::StaticGraph or g::Graph: The StaticGraph or Graph from which to retrieve the root ID.

Returns

The ID of the root node in the graph.

self_id(n::GraphNode)

Returns the id of this node.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

set_parent!(n::GraphNode, id)

Set the parent ID of a graph node.

Users will generally not use this method as they will normally deal with Context objects rather than GraphNode directly.

Arguments

• n::GraphNode: The node for which to set the parent.
• id: The ID of the parent node (or missing for root nodes).

Returns

Nothing. The node is modified in place.