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.

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.

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(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(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).

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_root(g::Graph)

Extract the root node of a graph.

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

graph_data(c::Context)

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

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_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.

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_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.

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);

traverse(g::Graph; 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: 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");

+(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);

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);

generate_id()

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

get_id!()

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

reset_id!()

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

set_id!(id)

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