3 - ManimGraphLibrary

When dealing with data structures, graphs are for sure among the ones that we encounter more frequently. When we are presented with an algorithm on a graph, visualization plays an essential role in its understanding. But, if on one hand visualization is key in the context of graphs, on the other dealing with such visualization is not straightforward.

This consideration led to the idea of developing a library for Manim that could make the visualization of graphs simple and quick. The functions presented in this chapter aim at the creation of elegant looking graphs, which can be obtained by writing a few lines of simple code. In addition, the user is given a set of functions, which are presented in Section Path utilities, that makes it possible to animate the creation of paths on graphs, which can be of great use when studying the behaviour of an algorithm.

The way in which the library has been built makes it possible for users to customize the way they intend to use the functions. As an example of this, the function that highlights a path on a graph mentioned previously calls two separate functions, one for nodes and one for edges, which are made available to the user separately. We have tried to apply this way of thinking to each component of the library.

Figure 3.1 allows us to get an idea about the structure of the library. The components have been divided into three sections: the first deals with the creation of graphs (see Section Graph creation), the second with the animation of paths (see Section Path utilities) and the third with the creation of backward edges on flow networks (see Section Flow network utilities).

Architecture
Figure 3.1 - ManimGraphLibrary architecture: arrows represent the interactions between the components and blocks highlight the three main sections of the library.

Graph Creation

This section contains an in-depth presentation about how graphs are implemented and visualized using ManimGraphLibrary. The main idea behind the way the architecture has been developed is the coexistence of the logical part of the graph and its visual representation.

This was done by creating multiple dictionaries when the function make_graph() gets called, one that represents the data structure, the others that contain the information about how nodes and edges appear on the screen. We will see that the model has been built as a dictionary of GraphNode objects, while the other dictionaries only contain visual objects.

GraphNode

Let us start with the description of the class GraphNode. The main use expected for this class is the one described in Section make_graph(). Despite this, the user can choose to manually create GraphNode objects and to connect them using the given methods.
A GraphNode contains information about multiple aspects of the node. First it takes as parameters the name through which the node will be referenced and the name_label that will be displayed on the node. If the user does not specify a value for the label, the name will be used also as label. It is also possible to set the label_color and the font_size.
In addition, we can set and store information about the position, the radius of the circle and its background and outline color (node_color and stroke_color).
In this section we also go through the methods of the class, which deal with the connection of two GraphNode objects.

class GraphNode(name, name_label=None, font_size=1, label_color='#FFFFFF', position=array([0., 0., 0.]), radius=0.5, node_color='#BBBBBB', stroke_color='#FFFFFF')[source]

Bases: object

Creates an object which is a node of a graph.

Parameters

  • name – Key of the node used to recall it. It becomes also the label if ‘node_label’ is not specified.

  • name_label – Label contained inside the circle. Can be omitted.

  • font_size – Scaling of the label inside the circle.

  • label_color – Color of the label inside the circle.

  • position – Position of the circle and the label.

  • radius – Radius of the circle.

  • node_color – Color of the inside of the circle. The opacity is set to be 0.5.

  • stroke_color – Color of the outline of the circle.

Now we discuss the details of the implementation of the class. First we create the name and the label attributes as described earlier. Note that name_label gets converted into a string in order to make it a Text object [15]. Next we scale, move and set the desired color to the label.
We create three more attributes: center, radius and circle. The circle that represents the node is a Circle object, of which we set a color for the inside (we lower the opacity to make it aesthetically pleasing) and one for the outline [8].
As mentioned earlier, we want each GraphNode to also have logical properties. We create the attribute neighbours, which is a list that will store the GraphNode objects connected to the current one.
The user is expected to extend the class GraphNode or to add new attributes dynamically in order to add the desired logical properties, as for example a visited attribute. An example of this use can be found in Example 8 (Section highlight_path()).

connect()

Let us now look into the first method of this class, which allows us to connect two nodes, both logically and visually. This method takes two GraphNode objects as input parameters and returns a Line that connects them. In addition, the second node gets added to the list of neighbours of the first node, which as anticipated makes a dictionary of GraphNode objects work as an implementation of the graph as a data structure.
The other possible input parameters are about the visual aspect of the line that connects the nodes. In particular, we can choose to add an arrow tip on the end to highlight the direction of the edge (this is expected to be used for directed graphs) and to change the color and width of the line.

connect(other, arrow=False, edge_color='#BBBBBB', width=7)[source]

Creates a line between node ‘self’ and node ‘other’. Adds ‘other’ to the list of neighbours of the first node.

Parameters

  • self – First node.

  • other – Second node.

  • arrow – If True adds an arrow tip at the end of the line.

  • edge_color – Color of the line.

  • width – Width of the line.

Returns

Line between node ‘self’ and ‘other’.

Return type

Line

Notes

When we connect two nodes, the line connects the centers of the circles. To solve this we get the direction of the line and move ‘start’ and ‘end’ by the value of the radius along this direction.

Examples

Let us create a simple scene that shows how to manually use the method connect(). First we create two GraphNode objects, giving as input parameters name and position. We group the objects we want to display in a VGroup; we get them by accessing the circle and label attributes of each GraphNode object.
We call connect() on node_a, which is our first GraphNode object. It is mandatory to specify the GraphNode that we want to connect to the first one. In our case this second GraphNode is node_b.
In addition, we require the presence of an arrow tip at the end of the edge and we also specify the desired color for the arrow we are creating.
Let us remark that connect() creates both a visual and logical connection between the given nodes. Indeed, it returns a Line object that represents the edge and also adds node_b to the list of neighbours of node_a.
We set the nodes visible by adding them to the scene. Then we animate the creation of the edge by calling Create() on edges_view, which is the Line object mentioned above.

Example 1: Connect 

from manim import *

from ManimGraphLibrary import *

class Connect(Scene):
    def construct(self):
        node_a = GraphNode(name='a', position=LEFT*2)
        node_b = GraphNode(name='b', position=RIGHT*2)
        nodes_view = VGroup(node_a.circle, node_a.label, node_b.circle, node_b.label)
        edges_view = node_a.connect(node_b, arrow=True, edge_color=WHITE)
        self.add(nodes_view)
        self.play(Create(edges_view))
        self.wait()

Let us take a look at the implementation of connect(). The first step is creating a Line between the nodes. At first, we choose as start and end points the centers of the two nodes, that we access through the attribute center of each GraphNode. We created this line in order to call get_unit_vector() on it to get its direction, expressed as a normalized vector. This allows us to know in which direction to shift the current start and end points. We do this in order to place them on the outline of the circle, avoiding the overlapping between edge and node labels.
We move start by the value of the radius, which is saved as an attribute of the GraphNode, along the direction of the line. We do the same with end, but in this case we make the shift in the opposite verse (-direction).
We create the Line object with the new start and end points and we set its width and color.
If the parameter arrow, which by default is set to False, gets changed to True, we use add_tip() to add an arrow tip to the line. We also edit the width of the tip to make it aesthetically pleasing.
We add the second GraphNode, which is represented by the variable other, to the list of neighbours of the node we called the method connect() on.
The function returns the visual representation of the edge, which is the line just described.

connect_weight()

Now we go through connect_weight(), the second method of the class GraphNode, which is expected to be used for weighted graphs. It recalls the method connect(), adds to the line that gets returned a label with the weight of the edge and returns the line-label pair.
In addition to the parameters required by connect(), connect_weight() takes the value of the weight of the current edge and the color and size of the label that will display it.

connect_weight(other, arrow=False, edge_color='#BBBBBB', width=7, weight=None, label_color='#FFFFFF', label_font_size=0.8, label_distance=0.3)[source]

Recalls the function ‘connect’ to create a line between node ‘self’ and node ‘other’ and to add ‘other’ to the list of neighbours of the first node. Adds also a label with the weight of the edge.

Parameters

  • self – First node.

  • other – Second node.

  • arrow – If True adds an arrow tip at the end of the line.

  • edge_color – Color of the line.

  • width – Width of the line.

  • weight – Weight of the edge from node ‘self’ to ‘other’. If None the weight label will be empty.

  • label_color – Color of the weight label.

  • label_font_size – Scaling of the label.

  • label_distance – Distance between the line and the weight label.

Returns

  • Line – Line between node ‘self’ and ‘other’.

  • Text – Label with the weight of the edge.

Notes

To compute the position for the label we get the direction of the line between the nodes and compute the orthogonal direction anticlockwise: (x, y) -> (y, -x) Then we move the label along this orthogonal direction.

Examples

As an example for connect_weight(), let us go back to Example 1. This time, we also want to display the weight label on the side of the line representing the edge, so we call the method connect_weight() on the first node, specifying the weight parameter.
Let us remark a difference between Examples 1 and 2. We call Create() on VGroup(*edges_view), while earlier we had just Create(edges_view).
This happens because connect() returns a Line ready to be displayed, while connect_weight() returns a line-label pair. For this reason we need to group them together in order to pass them to Create(). This can be done explicitly by writing VGroup(edges_view[0], edges_view[1]) or by using the * operator, which will unpack the values from any iterable object. In our case this operator passes the two values in edges_view as two separate arguments [27].

Example 2: ConnectWeight 

from manim import *

from ManimGraphLibrary import *

class ConnectWeight(Scene):
    def construct(self):
        node_a = GraphNode(name='a', position=LEFT*2)
        node_b = GraphNode(name='b', position=RIGHT*2)
        nodes_view = VGroup(node_a.circle, node_a.label, node_b.circle, node_b.label)
        edges_view = node_a.connect_weight(node_b, arrow=True, weight=3)
        self.add(nodes_view)
        self.play(Create(VGroup(*edges_view)))
        self.wait()

Let us go through the implementation of connect_weight(). First we call connect() to create the visual edge and to add other to the list of neighbours of the GraphNode we called the method on.
We want to compute the right place for the weight label, therefore we start by getting the direction of line, which is the return value of the method connect(). At this point we compute the center of the line and the orthogonal direction anticlockwise with respect to the direction of the line.
We create the weight label. If no weight value gets passed, we create an empty Text object anyway for consistency. Otherwise we convert the given weight to a string in order to make it a Text object.
We want to move the label near the edge, so we compute the placement by starting in the center of the line and moving along the orthogonal direction by the desired value.
Lastly, we set the chosen color and font size of the label.

make_graph()

The function make_graph() is one of the key components of ManimGraphLibrary. We call it to create a graph automatically, both from a logical and visual points of view.
The mandatory inputs of the function are nodes_pos_input and edges_input. The first one is a dictionary with node names as keys and positions as values.
The second mandatory input, edges_input, can be a list or a dictionary depending on the graph we want to create. If the graph does not have weighted edges, we should provide a list of tuples of two elements that represent the node pairs that we want to be connected. Otherwise the input should be a dictionary, with node pairs as keys and the corresponding weights as values.
In addition, it is possible to specify one more parameter. We can set undirected to True if we want each pair of edges to be connected in both directions. We know that if we have ('a','b') in edge_list, 'b' will be added to the list of neighbours of 'a'. When undirected is set to True, the edge ('b','a') gets automatically created, therefore 'a' will be added to the list of neighbours of 'b'.
The function creates GraphNode objects and connects them using the methods of the class. Therefore make_graph() takes as parameters also the ones discussed in Section GraphNode, such as the radius, stroke and background color of the node circle, the color and size of the node label, the color and width of the edge line, the color and size of the weight label and the preference about the presence of the arrow tip at the end of the edge.

Let us now discuss the shape of the output. The first value is a dictionary that contains each GraphNode of the graph, which is accessible through the name key. This dictionary acts as a data structure since it stores the logical properties of the graph.
Next we have two more dictionaries that we use to interact with only the visual components of nodes and edges, which we usually refer to as nodes_view and edges_view.
The values in the nodes_view dictionary are circle-label pairs, that we can access using the node name as the key, while in the edges_view dictionary we have line-label pairs as values and pair of node names as keys.
Lastly, we have a VGroup, which we usually rename graph, in which we group together the values contained in the previous two dictionaries (circles, node labels, lines, weight labels). We decided to add this group to the output of the function make_graph() because the user is likely to be interested in moving/scaling/animating together all the objects of the graph.

make_graph(nodes_pos_input, edges_input, undirected=False, radius=0.5, font_size=1, node_color='#BBBBBB', stroke_color='#FFFFFF', node_label_color='#FFFFFF', edge_color='#BBBBBB', width=7, edge_label_color='#FFFFFF', label_font_size=0.8, label_distance=0.3, arrow=False)[source]

Defines logical relations between ‘GraphNode’s and creates visual objects. See section ‘Returns’ to better understand the shape of the output.

Parameters

  • nodes_pos_input – Dictionary with node names as keys and positions as values. Example: {‘a’: LEFT, ‘b’: np.array([-1.6, 0.1, 0. ]), ‘c’: UP + RIGHT*2}

  • edges_input – For not weighted graphs: list of edges. Example: [(‘a’,’b’), (‘b’,’c’)]. For weighted graphs: dictionary of edges-weights. Example: {(‘a’,’b’): 2, (‘b’,’c’): 3}.

  • undirected – If True, when the user adds the edge (‘a’,’b’), (‘b’,’a’) gets automatically added. The weight label gets added only for the first edge.

  • radius – Radius of the circle.

  • font_size – Scaling of the label inside the circle.

  • node_color – Color of the inside of the circle. The opacity is set to be 0.5.

  • stroke_color – Color of the outline of the circle.

  • node_label_color – Color of the label inside the circle.

  • edge_color – Color of the line.

  • width – Width of the line.

  • edge_label_color – Color of the weight label.

  • label_font_size – Scaling of the label.

  • label_distance – Distance between the line and the weight label.

  • arrow – If True adds am arrow tip at the end of the edge.

Returns

  • dict – Dictionary of node keys and ‘GraphNode’ values, which contain logical properties of the graph (for example list of neighbours)

  • dict – Dictionary of node keys and visual objects values (circle and node label)

  • dict – Dictionary of edge keys and visual objects values (line and weight label)

  • VGroup – Group that contains all the visual objects of the graph (circles, node labels, lines, weight labels). Useful to move/scale/animate them together.

Examples

Let us now look at a simple scene that shows how to use the function make_graph(). We define a dictionary with node names as keys and their positions as values. In Section node_layout() we discuss how to avoid doing this step manually by calling the function node_layout().
For this example we want to create an unweighted graph, therefore we will pass the desired edges in the shape of a list.
We call the function make_graph(), which gives four output values. We save the first, which is the dictionary of GraphNode objects, in the variable graph_nodes, the next two dictionaries, which contain the visual objects, in the variables nodes_view and edges_view and the VGroup of all the visual objects in the variable graph.
In this particular example we just want to display the graph on the screen, so we simply call Create() on graph.

Example 3: MakeGraph 

from manim import *
  
  from ManimGraphLibrary import *
  
  class MakeGraph(Scene):
      def construct(self):
          nodes_and_positions = { 'a': LEFT * 4,
                                  'b': LEFT * 2 + UP * 2, 'c': LEFT * 2 + DOWN * 2,
                                  'd': RIGHT * 2 + UP * 2, 'e': RIGHT * 2 + DOWN * 2,
                                  'f': RIGHT * 4 }
          edges_input = [('a','b') , ('a','c'), ('b','c'), ('b','d'), ('b','e'), ('c','e'), ('d','e'), ('d','f'), ('e','f')]
  
          graph_nodes, nodes_view, edges_view, graph = make_graph(nodes_and_positions, edges_input)
  
          self.play(Create(graph), run_time=2)
          self.wait()

Now we go through the implementation of the function make_graph. We start with the creation of three dictionaries and a VGroup, which will serve us in the way described previously.
We take the keys from the nodes_pos_input dictionary, which represent the names of the nodes of the graph. For each node we get its position from the dictionary and we create a GraphNode object, specifying all the desired parameters, such as the name, position, radius etc. We add this new GraphNode to the graph_nodes dictionary, using the name of the node as the key.
In the same way we add just the visual components of the node, which we find in the attributes circle and label, to the nodes_view dictionary. Lastly, we add them also to the VGroup called graph.
We are presented with two if conditions. The first one checks if edges_input is a list. If this is true, we go through each element of the list, that is expected to be a tuple of two elements, which are the names of the two nodes that the edge connects.
We recall the GraphNode that represents the first node of the pair by using edge[0] as key. Then we call the method connect() on it, passing as the second GraphNode the one with key edge[1], hence the second node of the pair described by the edge we are considering.
As we have seen before, connect() acts both in the logical and visual context, adding the second GraphNode to the list of neighbours of the first one and returning a line with all the desired properties.
We add that line to the edges_view dictionary, using edge, which is the pair of node names, as the key. As before, we also add it to the VGroup called graph.
We have another if condition inside the previous one, which checks if the variable undirected is set to True. If this is the case, the user wants the pair of nodes to be connected in both directions and therefore, to achieve this, we repeat the previous steps switching the two node names. As before, we add the line created by connect() to the dictionary edges_view, using (edge[1], edge[0]) as the key, and to the VGroup called graph.
The second if condition has the same structure of the previous one, but checks instead if edges_input is a dictionary.
If this is true, we are dealing with a weighted graph. For each edge we get its weight from the dictionary, then as before we connect the pair of GraphNodes. This time we connect them by calling the method connect_weight(), passing all the desired parameters, including the weight.
Again we check the parameter undirected and, if true, we connect the nodes also in the opposite direction calling connect_weight.
As we have already discussed, the function returns three dictionaries and a VGroup.

node_layout()

The function node_layout() is useful when we want to automatically generate a dictionary containing the positions of the nodes of the graph to pass to the function make_graph().
The function takes as parameters a list of edges and the name of the layout desired, which can be chosen from the ones made available by the library NetworkX [20].

node_layout(edges_input, layout='kamada_kawai_layout')[source]

Generates positions for the nodes taking a list of edges as the input.

Parameters

  • edges_input – List of edges. Example: [(‘a’,’b’), (‘b’,’c’)]

  • layout – Name of the NETWORKX layout desired.

Returns

Dictionary with node names as keys and positions as values. Example: {‘a’: LEFT, ‘b’: np.array([-1.6, 0.1, 0. ])}

Return type

dict

Notes

We use the library NETWORKX, we create a graph and add the edges. https://networkx.org/documentation/stable/reference/drawing.html?highlight=layout#module-networkx.drawing.layout

In the variable ‘pos’ we save each node label with (x,y) coordinates. We want to give as output something in the form {‘0’: np.array([-1.6, 0.1, 0. ]), ‘1’: np.array([ 0.4, -1.8 , 0. ])} We use (x,y) coordinates from ‘pos’ and edit them in order to fit the space properly: we compute the ratio between the available space and the space taken by the graph in order to scale it.

Examples

Let us now show how the function node_layout() can be used. We start by creating a list of edges. We call node_layout() passing as parameters the list of edges and the name of the NetworkX layout desired, which in this case is spring_layout.
The function returns a dictionary of nodes and positions, that we can use as the input of make_graph(), together with the list of edges.
Now we create two more graphs, to show how different NetworkX layouts behave. As we have seen before, we can display a graph on the screen just by calling Create() on the VGroup that contains its visual components.
We start by adding the first graph on the scene without any animation. Then we call ReplacementTransform(), which as suggested by the name, replaces and transforms in a smooth way an object into a target object [24].
We repeat this step and transform the second graph into the third. Then we close the loop by transforming the third graph into the first one. To make this last transformation work, we need to use a copy of the first graph as the target object, because the variable graph no longer contains the VGroup representing the first graph, since we called ReplacementTransform() on it.
This code produces a scene that can be watched as a loop between three different layouts of the same graph.

Example 4: NodeLayout 

from manim import *
      
      from ManimGraphLibrary import *
      
      class NodeLayout(Scene):
          def construct(self):
              edges_input = [('a','b'), ('b','c'), ('a','c'), ('c', 'd'), ('a', 'd')]
      
              nodes_and_positions = node_layout(edges_input, layout = 'spring_layout')
              graph_nodes, nodes_view, edges_view, graph = make_graph(nodes_and_positions, edges_input)
      
              nodes_and_positions = node_layout(edges_input, layout = 'kamada_kawai_layout')
              graph_nodes_2, nodes_view_2, edges_view_2, graph_2 = make_graph(nodes_and_positions, edges_input)
      
              nodes_and_positions = node_layout(edges_input, layout = 'planar_layout')
              graph_nodes_3, nodes_view_3, edges_view_3, graph_3 = make_graph(nodes_and_positions, edges_input)
      
              self.add(graph)
              self.wait()
              graph_copy = graph.copy()
              self.play(ReplacementTransform(graph, graph_2))
              self.wait()
              self.play(ReplacementTransform(graph_2, graph_3))
              self.wait()
              self.play(ReplacementTransform(graph_3, graph_copy))

Let us go through the code of the function node_layout(). First we create an empty graph structure with no nodes and no edges by using the class DiGraph provided by NetworkX [19]. Then we add edges to it by passing our list of edges as the input for add_edges_from().
We take the string input layout that we expect to be the name of the chosen NetworkX algorithm, and we transform it into a Python expression using the function eval() [22].
If the chosen layout is an actual NetworkX algorithm, we call it passing the graph structure as the input. We get a dictionary with nodes as keys and positions as values that we save in the variable pos.
If the layout is not available, we print an error message and, in order not to stop the algorithm, we call another algorithm that we set as a default choice.
Now we want to edit the given coordinates in order to fit the space properly. We compute the ratio between the available space and the space currently taken by the graph in order to scale it of the correct amount. We do this computation for the x and y axes separately.
We apply this scaling to the position of each node in the dictionary pos and save the results in a new list called positions.
We create a new dictionary by merging, using the function zip() [23], the list of the node labels and the list positions. Then we return this dictionary.

Path utilities

In this section, we look into three functions which can be useful when dealing with paths on graphs. As seen in Chapter 1, this library has been developed aiming at two main use cases: we want the library to be useful for both someone who wants to create an explanatory animation and for someone who wishes for a better understanding of the execution of an algorithm. In both cases, visualizing a path on a graph can be of great interest. Let us now look in detail at how these functions should be used and how they work.

highlight_node()

The function highlight_node() animates the creation of a colored circle, placed over the circle passed as a parameter by the user. It is possible to set the color and the width of the new stroke, which otherwise are set to default values.
This function deals also with the animation of the creation of the new circle and for this reason Manim requires that scene gets passed as a parameter of the function.

highlight_node(scene, node_circle, color='#FC6255', width=8, run_time=1)[source]

Creates a copy of a given circle, modifies its color and stroke width and animates its creation.

Parameters

  • scene – Canvas of animations, which are played by calling scene.play().

  • node_circle – Circle that gets copied into the object ‘highlighted_node’.

  • color – Color of the outline of the new object.

  • width – Width of the outline.

  • run_time – Duration of the animation.

Returns

Copy of ‘node_circle’ with different color and width of the outline. The inside of the circle has opacity 0.

Return type

Circle

Examples

Let us now produce a simple scene to show how the function highlight_node() can be used. We start by defining a dictionary with nodes as keys and their position as values and a list of edges expressed as tuples of two indices.
At this point we can use the function make_graph() to create a graph with both logic and visual properties. In this example, we just add the whole graph to the scene.
We call highlight_node() passing self and the circle of the node that we want to highlight, which can be recalled through the dictionary nodes_view, using 'a' as the key. Since the function takes just the circle and not the whole node view as the input, we pass the circle by specifying [0].

Example 5: HighlightNode 

from manim import *
  
  from ManimGraphLibrary import *
  
  class HighlightNode(Scene):
      def construct(self):
          nodes_and_positions = { 'a': LEFT * 2, 'b': RIGHT * 2 }
          edges_input = [('a','b')]
          graph_nodes, nodes_view, edges_view, graph = make_graph(nodes_and_positions, edges_input, arrow=True)
          self.add(graph)
  
          highlight_node(self, nodes_view['a'][0])
          self.wait()

Let us now look at how this function works. First we create a copy of the circle we want to highlight using the function copy(). We set the stroke color and width to the values chosen by the user, or to the default ones if there are no custom values. We also set the opacity of the fill of the circle to 0 in order only have the outline of the circle, making the node label underneath visible.
We call play() and Create() to animate the creation of the new circle. This is possible because scene has been passed as a parameter. When we call the function play() we also set the run_time of the animation, whose default value is 1.
The function returns the highlighted node, which is an object of type Circle.

highlight_edge()

The function highlight_edge() animates the creation of a new object, placed over the one passed as a parameter by the user. We expect this function to be used on objects of type Line or ArcBetweenPoints, both with or without an arrow tip. For this reason in the description of the function we will refer to the object this function returns as a line. It is possible to set the color and the width of the new line, which otherwise are set to default values.
As the function highlight_node() seen in Section highlight_node(), this function deals with the animation of the creation of the new line and for this reason it is mandatory to pass scene a parameter of the function.

highlight_edge(scene, edge, color='#FC6255', width=7, run_time=1)[source]

Creates a copy of a given edge (expected Line or ArcBetweenPoints), modifies its color and stroke width and animates its creation.

Parameters

  • scene – Canvas of animations, which are played by calling scene.play().

  • edge – Object that gets copied into the object ‘highlighted_edge’.

  • color – Color of the new object.

  • width – Width of the new object.

  • run_time – Duration of the animation.

Returns

Copy of ‘edge’ with different color and width.

Return type

Mobject

Notes

If the edge has an arrow tip, modifying the width of the tip can cause problems with the alignment of the new object with the existing one. To solve this, we set the width of the arrow to its original width.

Examples

As an example for this function, let us go back to Example 5. This time, instead of highlighting the node, we are willing to highlight the edge ('a','b'). We call the function highlight_edge() passing as parameters self and the line/arrow we want to highlight. To recall it we use the pair ('a','b') as the key for the dictionary edges_view. Since the corresponding value is a pair of line and weight label, we specify the index [0] to pass just the line.

Example 6: HighlightEdge 

from manim import *
      
      from ManimGraphLibrary import *
      
      class HighlightEdge(Scene):
          def construct(self):
              nodes_and_positions = { 'a': LEFT * 2, 'b': RIGHT * 2 }
              edges_input = [('a','b')]
              graph_nodes, nodes_view, edges_view, graph = make_graph(nodes_and_positions, edges_input, arrow=True)
              self.add(graph)
      
              highlight_edge(self, edges_view[('a','b')][0])
              self.wait()

Now we discuss how this function works.
As for the function highlight_node(), we create a copy of the object passed as an input and set the desired color and width.
If the edge has an arrow tip, modifying the width of the tip can cause problems with the alignment of the new object to the existing one. To solve this, we check if the object has a tip using the function hasattr(obj, name). If it does, we get the width of the original arrow tip and set the new one to this value.
We can call play() and Create() to animate the creation of the new line. We set the duration of the animation to the value of the parameter run_time.
The function returns the highlighted edge, which is an object of the same type as the object edge, with different color and width.

highlight_path()

The function highlight_path() highlights nodes and edges of a selected path by calling the functions highlight_node() and highlight_edge(), which have been described in Sections highlight_node() and highlight_edge().
This function takes as inputs, in addition to the parameters required by the functions highlight_node() and highlight_edge(), two dictionaries and a list. The shape of the dictionaries is the one described when discussing the output of the function make_graph() (Section make_graph()); we call the first dictionary nodes_view and the second edges_view.
The other parameter required is a list of edges, which are expected to be part of a connected path.

highlight_path(scene, nodes_view, edges_view, path_list, node_color='#FC6255', node_width=8, node_run_time=0.5, edge_color='#FC6255', edge_width=7, edge_run_time=0.5)[source]

Creates and animates a path given a list of edges. Uses functions ‘highlight_node’ and ‘highlight_edge’.

Parameters

  • scene – Canvas of animations, which are played by calling scene.play().

  • nodes_view – Dictionary of node keys and visual objects values (circle and node label)

  • edges_view – Dictionary of edge keys and visual objects values (line and weight label)

  • path_list – List of edge keys of the path.

  • node_color – Color of the outline of the node of the highlighted path.

  • node_width – Width of the outline of the node of the highlighted path.

  • node_run_time – Duration of the animation.

  • edge_color – Color of the edge of the highlighted path.

  • edge_width – Width of the edge of the highlighted path.

  • edge_run_time – Duration of the animation.

Returns

Dictionary with node names and edge names as keys and objects as values.

Return type

dict

Examples

Now we produce a scene to show how to use the function highlight_path().
We create a graph by using the function make_graph(), which takes as mandatory inputs a list of edges (or a dictionary with weights for weighted graphs) and a dictionary with the desired position of each node. Hence we write a list of edges and generate the dictionary nodes_and_positions by calling the function node_layout(), specifying the desired layout for the graph.
We generate the graph and add it to the scene. For this specific example we want the graph to be undirected, so we specify undirected=True when calling the function.
We call the function highlight_path(). We pass self, which is necessary to make the animations possible, the two dictionaries nodes_view and edges_view and finally the list of edges of the path that we want to highlight.

Example 7: HighlightPath 

from manim import *
      
      from ManimGraphLibrary import *
      
      class HighlightPath(Scene):
          def construct(self):
              edges_input = [('a','b'), ('b','c'), ('a','c'), ('c', 'd'), ('a', 'd')]
              nodes_and_positions = node_layout(edges_input, layout = 'planar_layout')
              graph_nodes, nodes_view, edges_view, graph = make_graph(nodes_and_positions, edges_input, undirected=True)
              self.add(graph)
      
              highlight_path(self, nodes_view, edges_view, [('d','c'), ('c','a'), ('a','b')])
              self.wait()

Let us look at how the function highlight_path() can be used to better understand the execution of an algorithm, which in this example is the breadth-first search.
The BFS is an algorithm for searching a tree or a graph starting from a node and exploring all nodes at the current depth level before proceeding with nodes at the next depth level [3]. To keep track of the child nodes that have been encountered but not yet visited more memory, generally a queue, is required.
We implemented the BFS in a way that gives a list of edges as the return value. The parameters required are a dictionary of GraphNode objects, like the one returned by the function make_graph() described in Section make_graph(), and the key of the name from which we want to start.
We add two attributes, visited and previous, to each GraphNode contained in the graph_nodes dictionary. In this way we are adapting the dictionary, which acts as a data structure, to this specific algorithm.
We pop the first element in the queue and, if we have not yet encountered it, mark it as visited. Then we go through its neighbours and add them to the queue to be visited in the next iterations.
When we get to a new node, we need to keep track of which node has led to it in order to highlight the correct edge on the graph. For this reason we save this information in the field previous.

Code 3.15 - Implementation of the breadth-first search.

Now we want to visualize the execution of this algorithm.
We recall Example 3 in which we created and visualized a graph by using the function make_graph(). We pass the dictionary graph_nodes to the function bfs() as seen in Code 3.15, then we use the output as the input parameter for highlight_path().
Visualizing the execution of the breadth-first search with the scene generated in Example 8 is surely an effective way to understand how the algorithm works.

Example 8: BreadthFirstSearch 

from manim import *
      
      from ManimGraphLibrary import *
      from graph_algorithms import bfs
      
      class BreadthFirstSearch(Scene):
          def construct(self):
              edges_input = [('a','b') , ('a','c'), ('b','c'), ('b','d'), ('b','e'), ('c','e'), ('d','e'), ('d','f'), ('e','f')]
              nodes_and_positions = { 'a': LEFT * 4,
                                      'b': LEFT * 2 + UP * 2, 'c': LEFT * 2 + DOWN * 2,
                                      'd': RIGHT * 2 + UP * 2, 'e': RIGHT * 2 + DOWN * 2,
                                      'f': RIGHT * 4 }
              graph_nodes, nodes_view, edges_view, graph = make_graph(nodes_and_positions, edges_input, undirected=True)
              self.add(graph)
      
              bfs_edges = bfs(graph_nodes, 'a')
      
              highlight_path(self, nodes_view, edges_view, bfs_edges)
      
              self.wait()

Let us go through how the function works. We start by creating a dictionary in which we will add highlighted nodes and edges as values, using node names and edges names as keys. We assign the name of the first node of the path to the variable start to make the code easier to read.
We want to highlight this node by using highlight_node(). This function takes the inputs described in Section highlight_node(), which are scene, the circle of the node that we want to highlight, the color and the width of the highlighted node and the duration of the animation. To get the circle, we use the node name as key for the dictionary nodes_view, which returns the pair circle-label. Then we specify that we want only the circle by adding [0]. We add the highlighted node to the path dictionary, using the node name as key.
We create a loop over the edge names in path_list. We call the function highlight_edge(), which as described in Section highlight_edge() takes as parameters scene, the edge to highlight, color and width of the new edge and the duration of the animation.
The edge object, which is expected to be a Line or an ArcBetweenPoints (with or without an arrow tip), is saved in the dictionary edges_view. Using the name of the edge as the key, we get the pair edge-label. We specify that we want only the edge by adding [0].
We add the highlighted edge to the path dictionary, using the edge name as key. We assign the name of the second node of the current_edge_key pair to the variable second_node to make the code less cumbersome.
We highlight second_node and we add it to the path dictionary using the node name as key, as seen for node start.
The function returns the dictionary with all the highlighted nodes and edges.

Flow network utilities

When dealing with weighted graphs, we often need to display two different weights near the line that connects two nodes, referring to the two different directions we can go through that edge.
This may cause the visualization of the graph to become cumbersome, hence it can be useful to represent the edges using arcs instead of lines, in order for the two directions not to overlap.
In the context of flow networks, which are directed graphs with capacities associated to the edges, we often face this need when dealing with backward edges and for this reason we decided to add to ManimGraphLibrary the function show_backward_edge() (Section show_backward_edge()), which automatically creates two curved edges with the desired weights between the given nodes.
To make this possible we implemented also the function create_curved_edge() (Section create_curved_edge()), that deals with the creation of the arc and computes the position for the label.
Finally, this function calls compute_arc_start_end() (Section compute_arc_start_end()), which computes start and end points for the new arc.
Let us remark that, as for the previous components of the library, we decided to divide these steps into multiple functions in order to make it possible for users to customize the way they intend to use them.

compute_arc_start_end()

The function compute_arc_start_end() computes and returns start and end point on the outline of the circles passed as the input.
It is possible to choose the desired placement of the points by changing the value of start_angle, which gives the direction along which we shift the points (see Figure 3.11).
If the nodes have been scaled, it is also possible to specify this scaling factor in order to compute the correct placement for the points on the outline of the circles.

compute_arc_start_end(start_node_circle, end_node_circle, start_angle=1.0471975511965976, scale_factor=1)[source]

Given two circles, computes start/end points for a curved edge on the radius of the circles.

Parameters

  • start_node_circle – First circle.

  • end_node_circle – Second circle.

  • start_angle – Gives the direction along which we shift the start/end points (relative to the straight line between the circles).

  • scale_factor – Scaling of each circle applied before the computation of start/end points for the curved edge.

Returns

  • new_start – First point shifted on the outline of the circle.

  • new_end – Second point shifted on the outline of the circle.

Notes

To compute the direction along which we shift the start/end points first we compute the ‘edge_angle’ of the straight line between the nodes. Then we add the desired ‘start_angle’ in anticlockwise direction (negative sign). For the end point we consider the PI-complementary angle.

Examples

Even if we do not expect the user to call this function directly, let us look at an example that allows us to understand how that call would work.
First we create a graph with two nodes by using the functions of the library seen in Section Graph creation. We remove the edge ('a','b') from the scene, in order to replace it with the new arcs.
We call compute_arc_start_end(), passing the circles of nodes 'a' and 'b' as input parameters.
To visualize the result of this call we create two Dot objects and place them over the points start and end, then we call Create() on them.
We call create_curved_edge() to create an arc between the nodes to make this example more complete, but the details of the use of this function are described in Example 10.

Example 9: ComputeArcStartEnd 

from manim import *

from ManimGraphLibrary import *

class ComputeArcStartEnd(Scene):
    def construct(self):
        nodes_and_positions = {'a': LEFT * 2, 'b': RIGHT * 2}
        edges_input = {('a','b'): 2}
        graph_nodes, nodes_view, edges_view, graph = make_graph(nodes_and_positions, edges_input, arrow=True)
        self.add(graph)
        self.remove(edges_view[('a','b')][0], edges_view[('a','b')][1])

        start, end = compute_arc_start_end(nodes_view['a'][0], nodes_view['b'][0])
        p_start = Dot(start, color=RED)
        p_end = Dot(end, color=RED)
        self.play(Create(VGroup(p_start, p_end)))
        self.wait()

        curved_edge = create_curved_edge(start, end, arrow=True, weight=edges_input[('a','b')], arc_color=DARK_GREY, label_color=DARK_GREY)
        self.play(FadeIn(VGroup(*curved_edge)))
        self.wait()

Let us look at the implementation of the function compute_arc_start_end(). We get the center of the circles and save them as the current start and end values. Then we get the radius of each circle and scale them by the scale_factor.
We create a Line between the node centers. We call get_unit_vector() on it to get the the direction of the straight line between the nodes, as seen for the function connect().
To get the direction along which to shift the start/end points, first we need to compute the edge_angle of the straight line between the nodes. We get it by computing the arccos of the first component of the edge_direction vector.

Angles
Figure 3.11 - Visualization of edge_angle and start_angle

In Figure 3.11 we can visualize this angle highlighted in red.
Now we want to add the start_angle (highlighted in blue) in anticlockwise direction.
For the first node we get the desired angle just by computing the difference between edge_angle and start_angle, while for the second node we compute the difference between edge_angle and the π-complementary of start_angle.
To get the desired direction we compute the cos and sin of the resulting angles (lines 19-21), then we normalize.
We finally shift the start/end points on the outline of the circles along the directions computed.

create_curved_edge()

The function create_curved_edge() takes two points as the input and returns an ArcBetweenPoints between them and a label that displays the weight of the edge.
It is possible to specify the curvature of the arc through the parameter arc_angle, which will be used by Manim when creating the ArcBetweenPoints object.
If arrow is set to True, an arrow tip will be added at the end of the arc.
The user can set multiple visual properties, such as width and color of the arc and font size, distance and color of the weight label.
Notice that there are also default values for the colors marked with the letter b. This allows the user to choose the default visual properties of backward edges just by setting the backward parameter to True.

create_curved_edge(start, end, arc_angle=1.0471975511965976, arrow=False, backward=False, stroke_width=4, arc_color='#FFFFFF', arc_b_color='#444444', weight=None, label_font_size=0.8, label_distance=0.3, label_color='#FFFFFF', label_b_color='#444444', scale_factor=1)[source]

Creates an arc between two points using ‘ArcBetweenPoints’ and adds a weight label.

Parameters

  • start – First point.

  • end – Second point.

  • arc_angle – Angle of the arc.

  • arrow – If True, adds an arrow tip.

  • backward – If True use visual properties of backward edges.

  • stroke_width – Width of the arc.

  • arc_color – Color of the edge.

  • arc_b_color – Color of the backward edge.

  • weight – Weight of the edge.

  • label_font_size – Size of the weight label.

  • label_distance – Distance between the line and the weight label.

  • label_color – Color of the label.

  • label_b_color – Color of the label of the backward edge.

  • scale_factor – Scaling of the edge, useful to create the arrow tip in the right scale.

Returns

  • ArcBetweenPoints – Arc between ‘start’ and ‘end’.

  • Text – Weight label.

Examples

This code is similar to the one seen in Example 9, but this time we focus on the function create_curved_edge().
We use the start and end values computed earlier with the function compute_arc_start_end() as input parameters for create_curved_edge().
As the weight we use the value saved in the edges_input dictionary defined earlier, using the edge name as the key.
We call Create() to display the new arc and label. Since we have a pair ArcBetweenPoints-Text saved in the variable curved_edge, we group them together using the * operator, as seen in Example 2.

Example 10: CreateCurvedEdge 

from manim import *

from ManimGraphLibrary import *

class CreateCurvedEdge(Scene):
    def construct(self):
        nodes_and_positions = { 'a': LEFT * 2, 'b': RIGHT * 2 }
        edges_input = {('a','b'): 2}
        graph_nodes, nodes_view, edges_view, graph = make_graph(nodes_and_positions, edges_input, arrow=True)
        self.add(graph)
        self.remove(edges_view[('a','b')][0], edges_view[('a','b')][1])

        start, end = compute_arc_start_end(nodes_view['a'][0], nodes_view['b'][0])
        curved_edge = create_curved_edge(start, end, arrow=True, weight=edges_input[('a','b')])
        self.play(Create(VGroup(*curved_edge)))
        self.wait()

Now we go through the implementation of create_curved_edge().
We create an ArcBetweenPoints object, passing the start and end points and the desired angle of the arc. Then we set its visual properties, such as the width and the color, which depends on the parameter backward.
We compute the position of the weight label by creating a Line between start and end, getting its direction and computing the orthogonal direction anticlockwise with respect to the direction of the line. These steps are similar to the ones seen for the implementation of the function connect_weight().
We compute the final position by starting from the center of the arc (which we get by calling get_boundary_point and passing orthogonal_direction as the desired direction) and by shifting along the orthogonal direction by a value that is proportional to the distance between the nodes.
At lines 34-37 we create the weight label. If no weight value gets passed, we create an empty Text object anyway for consistency. Otherwise we convert the given weight to a string in order to make it a Text object. Then we set the position and the font size of the label.
If arrow is set to True we add an arrow tip at the end of the ArcBetweenPoints. We also edit the width of the tip to make it aesthetically pleasing.
We set the color of the label, which depends on the variable backward.

show_backward_edge()

The function show_backward_edge() takes as input two circles and returns forward and backward edges that connects them, also adding weight labels.
It recalls the functions compute_arc_start_end() and compute_curved_edge(), hence most of the input parameters are the ones required by the functions (see Sections compute_arc_start_end()/a> and compute_curved_edge).
Since this function returns two arc-label pairs, the two functions get called twice, one for the forward and one for the backward edge. Therefore we need to specify both forward_weight and backward_weight as input parameters.

show_backward_edge(start_node_circle, end_node_circle, arrow=True, start_angle=0.5235987755982988, arc_angle=0.5235987755982988, arc_color='#FFFFFF', arc_b_color='#444444', stroke_width=4, forward_weight=None, backward_weight=None, label_color='#FFFFFF', label_b_color='#444444', label_font_size=0.8, label_distance=0.3, scale_factor=1)[source]

Given two (node) circles as start/end returns forward/backward edges between them.

Parameters

  • start_node_circle – Circle of the first node.

  • end_node_circle – Circle of the second node.

  • arrow – If True, adds an arrow tip.

  • start_angle – Gives the direction along which we shift the start/end points (relative to the straight line between the circles).

  • arc_angle – Angle of the arc.

  • arc_color – Color of the arc stroke.

  • arc_b_color – Color of the backward edge.

  • stroke_width – Width of the arc stroke.

  • forward_weight – Weight of the forward edge.

  • backward_weight – Weight of the backward edge.

  • label_color – Color of the weight label.

  • label_b_color – Color of the label of the backward edge.

  • label_font_size – Scaling of the weight label.

  • label_distance – Distance between the line and the weight label.

  • scale_factor – Scaling of each circle applied before the computation of start/end points for the curved edge.

Returns

  • tuple – Forward edge (ArcBetweenPoints, Text)

  • tuple – Backward edge (ArcBetweenPoints, Text)

Examples

Let us go back to the code seen in Example 9 and 10, but this time we use the function show_backward_edge() instead of calling manually the two separate functions.
We pass the two node circles and the weights to the function. We save the two pairs that get returned in two separate variables, forward and backward.
We animate a smooth transformation between the straight edge and the new arcs by calling ReplacementTransform(). The starting object is a VGroup with the straight line and the original label, while the target object is VGroup with the two new arcs and labels.

Example 11: ShowBackwardEdge 

from manim import *

from ManimGraphLibrary import *

class ShowBackwardEdge(Scene):
    def construct(self):
        nodes_and_positions = {'a': LEFT * 2, 'b': RIGHT * 2}
        edges_input = {('a','b'): 2}
        graph_nodes, nodes_view, edges_view, graph = make_graph(nodes_and_positions, edges_input, arrow=True)
        self.add(graph)
        self.wait()
        forward, backward = show_backward_edge(nodes_view['a'][0], nodes_view['b'][0], forward_weight=2, backward_weight=0)
        self.play(ReplacementTransform(VGroup(edges_view[('a','b')][0], edges_view[('a','b')][1]), VGroup(*forward, *backward)))
        self.wait()

The code of the function show_backward_edge() is pretty straightforward.
We call compute_arc_start_end(), then we use the returned values as inputs for the function compute_curved_edge(), adding also all the parameters that deals with the visual aspect of the arc and the label.
We repeat this steps switching the two nodes. In this way we create a new arc which is symmetric with respect to the one just created. Also in this case we specify all the visual parameters, considering this time the colors chosen for the backward edge.