Section 3.9 Networks
PreFigure enables authors to create diagrams of networks, such as that shown in Figure 3.9.1. Mathematicians sometimes refer to these as graphs, but we will use the term network to distinguish them from graphs of functions. There is quite a bit of flexibility as will be explained in the remainder of this section.
Subsection 3.9.1 Getting started
Let’s begin by discussing Figure 3.9.1. Notice that it is a directed network and that there are multiple edges between two of the vertices. The PreFigure source is in Listing 3.9.2.
<diagram dimensions="(300,300)" margins="5">
<definition>graph={1:[3,4,5,5],2:[4,5],3:[4,5],6:[2,4]}</definition>
<coordinates bbox="(-1,-1,1,1)">
<network directed="yes" graph="graph" arrows="end"
scale="0.8" node-fill="#fcf" node-stroke="black"
seed="1" labels="yes"
tactile-node-size="40">
</network>
</coordinates>
</diagram>
The network is defined by the dictionary in line 2 where each key in the dictionary defines a node in the network and the corresponding value lists the nodes connected by edges. Notice that node 1 is connected to node 5 by two edges, as seen in the diagram.
The
<network> element then constructs the graphical representation of the network. There are quite a few attributes for that element so let’s take a moment to consider them.- graph
- The
@graphattribute tells PreFigure about the dictionary that defines the structure of the network. - directed
- The attribute
@directed="yes"declares this to be a directed network, which means that the edges have a direction indicated by arrows. If this attribute is set to"no", which is the default, then no arrows are placed on the edges. - arrows
- For a directed graph, this attribute controls where the arrowheads appear. There are two values,
@arrows="end"and@arrows="middle"with “middle” being the default. - labels
- Use
@labels="yes"to include labels inside the nodes. - scale
- The nodes will fit just inside the bounding box defined by the current coordinate system so the value of
@scalecan be used to pull the nodes in toward the center. The default is@scale="0.8". - node-fill
-
The
@node-fillattribute defines the color to use when filling the nodes. This is part of a collection of attributes that control the visual appearance of the network. Each<node>will generate a<point>so other attributes include@node-stroke,@node-thickness,@node-size,@node-style.Similarly, an edge will generate a<path>so some path attributes can be applied, such as@edge-stroke,@edge-thickness, and@edge-dash. - loop-scale
- As described in more detail below, this attribute provides some control over how the shape of loops.
- label-dictionary
- If the value of this attribute is a dictionary
{0:'a', 1:'b'}, then the node whose handle is0will be given the label \(a\text{.}\) Similarly, the node whose handle is1will be given the label \(b\text{.}\) This is demonstrated in Figure 3.9.4. - seed
- Some algorithms that determine the positions of the nodes uses a random seed. To ensure consistent behavior while you are developing a diagram, set the value of the
@seedattribute so that the nodes will stay in the same position from one compilation to the next. If you are not satisfied with the appearance of the network, you could try using a different seed.
Subsection 3.9.2 A more verbose network
A second way of defining the same network is shown in Listing 3.9.3. In this case, we do not define the structure of the network using a dictionary. Instead, we include
<node> elements as children of <network>. The @edges attribute for each node defines the edges connecting that node to others.<diagram dimensions="(300,300)" margins="5">
<coordinates bbox="(-1,-1,1,1)">
<network directed="yes" scale="0.8"
node-fill="#fcf" node-stroke="black"
seed="1" labels="yes"
tactile-node-size="40">
<node at="1" edges="[3,4,5,5]"/>
<node at="2" edges="[4,5]"/>
<node at="3" edges="[4,5]"/>
<node at="4"/>
<node at="5"/>
<node at="6" edges="[2,4]"/>
</network>
</coordinates>
</diagram>
In fact, we can mix these two approaches to defining the network for more flexibility as demonstrated by the next example.
<diagram dimensions="(250,250)" margins="5"
xmlns="https://prefigure.org">
<coordinates bbox="(-1,-1,1,1)">
<definition>graph={0:[0,1], 1:[0]}</definition>
<definition>labels={0:'a', 1:'b'}</definition>
<network directed="yes" graph="graph" arrows="middle"
seed="1" node-size="15" scale="0.5" node-fill="white"
labels="yes" label-dictionary="labels">
<node at="2" style="double-circle"><m>S</m></node>
<edge vertices="(2,2)">1</edge>
<edge vertices="(2,1)"/>
<edge vertices="(2,0)"/>
<edge vertices="(0,0)" label-location="0.6">1</edge>
</network>
</coordinates>
</diagram>
First notice that a subgraph is defined by the
@graph attribute of the <network> element. Furthermore, a third node is defined using a <node>, which enables us to change some properties of this node, such as its style and its label. Some edges are added using <edge> elements, and one edge, which was added to the graph through the @graph attribute, is given a label and the location of the label specified by the @label-location attribute, which is a value between 0 and 1.There are some general principles at play:
- Nodes and edges can be defined through the network’s
@graphattribute. Network features defined in this way inherit the properties, such as node style, defined as an attribute of the<network>element. - A
<node>element should be defined with a handle given by its@atattribute. If the handle already exists in the graph as defined through the network’s@graphattribute, then this element will act as a replacement. If the handle is a new one, then this element is added to the graph structure. Edges defined through a node’s@edgesattribute are considered to be new edges and so are added to the graph and drawn with the default appearance. - An
<edge>element also obeys the previous principle. This provides a way to override the appearance of previously defined edges or to define new edges and their appearance.
A loop is just an edge that connects a node with itself. By default, a loop will be drawn approximately as a circle whose radius depends on the size of the node. As demonstrated in Figure 3.9.4, loops will be drawn centered in the largest gap between a node’s outgoing and incoming edges. However, the
@loop-orientation attribute of a node can be used to change this behavior. The value of this attribute is an angle, given in degrees.The dimensions of a loop can be controlled using the
@loop-scale attribute of the <edge> element. The value of this attribute is an ordered pair of scaling factors, with the first scaling radially and the second tranversally, that are applied to the loop. This attribute may be added to the <network> in which case the value is applied to every loop that does not have a @loop-scale attribute in its <edge> element.These last two attributes are demonstrated in Figure 3.9.6.
<diagram dimensions="(300,150)"
xmlns="https://prefigure.org">
<coordinates bbox="(-1,-1,1,2)">
<network directed="yes" arrows="end"
node-fill="lightskyblue" node-stroke="black"
node-size="25" tactile-node-size="60"
labels="yes">
<node at="0" p="(-0.5,0)" style="double-circle"
loop-orientation="90">
<m>S_0</m>
</node>
<node at="1" p="(0.5,0)" loop-orientation="90">
<m>S_1</m>
</node>
<edge vertices="(1,0)">0</edge>
<edge vertices="(0,1)">0</edge>
<edge vertices="(0,0)" loop-scale="(0.6,0.5)">1</edge>
<edge vertices="(1,1)" loop-scale="(0.6,0.5)">1</edge>
</network>
</coordinates>
</diagram>
Subsection 3.9.3 Positioning the nodes
PreFigure relies on the Python package
networkx to determine the positions of the nodes, a process referred to as layout. This subsection shows some examples that demonstrate the possibilities.First, we may explicitly declare where we would like the nodes to be by including a
@p attribute for each node.
<diagram dimensions="(300,300)" margins="5">
<coordinates bbox="(-1,-1,1,1)">
<definition>N=5</definition>
<definition>f(t)=(cos(2*pi*t/N), sin(2*pi*t/N))</definition>
<network scale="0.8" labels="yes"
node-fill="#ccf" node-stroke="black"
tactile-node-size="40">
<node at="0" p="f(0)" edges="[1,2,3,4]"/>
<node at="1" p="f(1)" edges="[2,3,4]"/>
<node at="2" p="f(2)" edges="[3,4]"/>
<node at="3" p="f(3)" edges="[4]"/>
<node at="4" p="f(4)"/>
</network>
</coordinates>
</diagram>
Alternatively, we can define the structure of the graph by including a
@graph attribute inside the <network> element and then using <node> elements to set the positions. This is seen in Listing 3.9.10.<diagram dimensions="(300,300)" margins="5">
<coordinates bbox="(-1,-1,1,1)">
<definition>graph={0:[1,2,3,4], 1:[2,3,4], 2:[3,4], 3:[4]}</definition>
<definition>N=5</definition>
<definition>f(t)=(cos(2*pi*t/N), sin(2*pi*t/N))</definition>
<network scale="0.8" labels="yes" graph="graph"
node-fill="#ccf" node-stroke="black"
tactile-node-size="40">
<node at="0" p="f(0)"/>
<node at="1" p="f(1)"/>
<node at="2" p="f(2)"/>
<node at="3" p="f(3)"/>
<node at="4" p="f(4)"/>
</network>
</coordinates>
</diagram>
Nodes are created when they are referenced in the dictionary defined by the
@graph attribute. When a <node> element is encountered inside the <network> element, PreFigure checks to see if the node has already been defined. If not, it will add it to the graph using the @edges attribute to append more structure to the network. While this is allowed, it is not necessary and could be confusing to author and maintain a network defined like this.In these last two examples, we have specified the position of the nodes as an attribute inside the
<node> element. If we would like networkx to position the nodes, we have some more options.We can prescribe a different layout method using the
@layout attribute of the <network> element. The diagram in Figure 3.9.11 illustrates how the @layout="bfs" can be used to illustrate a binary tree.
<diagram dimensions="(300,300)" margins="5">
<definition>
graph={0:[1,2],1:[3,4],2:[5,6],3:[7,8],4:[9,10],5:[11,12],6:[13,14]}
</definition>
<coordinates bbox="(-1,-1,1,1)">
<rectangle center="(0,0)" dimensions="(2,2)" stroke="black"/>
<network layout="bfs" start="0" graph="graph" node-fill="orange"
rotate="-90" scale="0.8">
<node at="0" fill="red"/>
<edge vertices="[0,1]" stroke="blue" thickness="4"/>
</network>
</coordinates>
</diagram>
There are a couple of features to notice here. If we use the
bfs algorithm for the layout, we need to specify a node at which to @start. This is an attribute of the <network> element.The
bfs algorithm produces a tree that moves from left to right. To depict the tree with the root at the top, we use @rotate="-90" to rotate the graph.Since we would like the root to be colored differently, we use a
<node> element to specify the color of that node.In the same way, we use an
<edge> element to modify the appearance of a particular edge that has already been added to the graph structure. If the edge has not been added previously, then it will be added to the structure of the graph.Here are the possible values of the
@layout attribute.- spring
- This is the default if
@layoutis not specifically defined. This algorithm begins by randomly positioning the nodes, and an optional@seedattribute declares the seed for the algorithm. - bfs
- This is the breadth-first search algorithm demonstrated above. The root of the tree needs to be declared with the
@startattribute. - circular
- The nodes are equally spaced around a circle.
- random
- Nodes are randomly positioned using the value of the
@seedattribute, which is 1 by default. - bipartite
- Used for bipartite graphs. The
@bipartite-setattribute, whose value is a list of handles describing the nodes in one of the two sets, is required. The@alignmentattribute can be set to “vertical” or “horizontal”, which is the default. - planar
- Lays out planar graphs so that edges do not cross.
- spectral
- See the
networkxdocumentation.
After the nodes are positioned by
networkx, PreFigure sets up a coordinate transformation so that the nodes will be positioned in the current bounding box. Because a <network> may have loops or nodes drawn with a large size, an author may wish to pull the nodes into the center of the bounding box so that, say, a loop does not leave the bounding box. The @scale attribute of the <network>, which is 0.8 by default, determines the degree to which nodes are pulled into the center.Subsection 3.9.4 Putting everything together
Networks have a lot of features so it may be worthwhile to show an example that illustrates how these features can be used in mathematical exposition. Suppose that we would like to explain the idea of a spanning tree as a subgraph of a graph \(G\text{.}\) On the left of Figure 3.9.13 is the graph \(G\) with a collection of dashed edges. If we remove those edges, we obtain a spanning tree as shown on the right. To make the point clear, we would like the nodes to be in the same positions in both diagrams.
<diagram dimensions="(250,250)" margins="5">
<definition>graph={1:[3,4,5],2:[4,5],3:[4,5],6:[2,4]}</definition>
<coordinates bbox="(-1,-1,1,1)">
<network graph="graph" scale="0.8"
node-fill="#fcf" node-stroke="black"
seed="1" labels="yes" node-style="box"
tactile-node-size="40">
<edge vertices="[3,5]" dash="9 9"/>
<edge vertices="[1,4]" dash="9 9"/>
<edge vertices="[4,6]" dash="9 9"/>
<edge vertices="[2,4]" dash="9 9"/>
</network>
</coordinates>
</diagram>
The PreFigure source for Figure 3.9.13 is shown in Listing 3.9.14. Notice how the structure of the graph is defined using a dictionary with instructions given to draw some edges as dashed lines.
The PreFigure source to create the diagram on the right is quite similar except that we replace
@dash="9 9" in the <edge> elements with @stroke="none".<diagram dimensions="(250,250)" margins="5">
<definition>graph={1:[3,4,5],2:[4,5],3:[4,5],6:[2,4]}</definition>
<coordinates bbox="(-1,-1,1,1)">
<network graph="graph" scale="0.8"
node-fill="#fcf" node-stroke="black"
seed="1" labels="yes" node-style="box"
tactile-node-size="40">
<edge vertices="[3,5]" stroke="none"/>
<edge vertices="[1,4]" stroke="none"/>
<edge vertices="[4,6]" stroke="none"/>
<edge vertices="[2,4]" stroke="none"/>
</network>
</coordinates>
</diagram>
Subsection 3.9.5 Annotating networks
Handles are automatically given to the nodes and edges in a
<network> so that the network can be annotated. For instance,- when a node is defined with the label “a”, its handle becomes “node-a”.
- an edge from node “a” to node “b” has the handle “edge-a-b”.
- a loop at node “a” has the handle “loop-a”.
- if there are multiple edges from node “a” to node “b”, they acquire the handles “edge-a-b-0”, “edge-a-b-1”, and so forth. The same is true for loops.
Figure 3.9.16 demonstrates an annotated network.
Diagram Exploration Keyboard Controls
<diagram dimensions="(300,300)" margins="5"
xmlns="https://prefigure.org">
<definition>graph={1:[3,4,5,5],2:[4,5],3:[4,5],6:[2,4]}</definition>
<network directed="yes" graph="graph" scale="0.7"
node-fill="#fcf" node-stroke="black"
node-style="circle" node-size="15"
arrows="end" seed="1" labels="yes"
tactile-node-size="45">
<edge vertices="(1,2)">4</edge>
<edge vertices="(2,2)" label-location="0.3"
loop-scale="(0.8,0.8)">
<m>\alpha</m>
</edge>
<node at="2" style="double-circle"/>
</network>
<annotations>
<annotation ref="figure" text="A directed network with nodes and edges">
<annotation ref="node-1" text="The node 1">
<annotation ref="edge-1-3" text="An edge from node 1 to node 3"/>
<annotation ref="edge-1-4" text="An edge from node 1 to node 4"/>
<annotation ref="edge-1-5-0" text="An edge from node 1 to node 5"/>
<annotation ref="edge-1-5-1" text="A second edge from node 1 to node 5"/>
</annotation>
<annotation ref="node-2" text="The node 2">
<annotation ref="edge-2-4" text="An edge from node 2 to node 4"/>
<annotation ref="edge-2-5" text="An edge from node 2 to node 5"/>
<annotation ref="loop-2" text="A loop from node 2 to itself"/>
</annotation>
<annotation ref="node-3" text="The node 2">
<annotation ref="edge-1-3" text="An incoming edge from node 1"/>
<annotation ref="edge-3-4" text="An edge from node 3 to node 4"/>
<annotation ref="edge-3-5" text="An edge from node 3 to node 5"/>
</annotation>
<annotation ref="node-5" text="The node 5 and four incoming edges">
<annotation ref="edge-1-5-0" text="An incoming edge from node 1"/>
<annotation ref="edge-1-5-1" text="A second incoming edge from node 1"/>
<annotation ref="edge-2-5" text="An incoming edge from node 2"/>
<annotation ref="edge-3-5" text="An incoming edge from node 3"/>
</annotation>
<annotation ref="node-6" text="The node 2">
<annotation ref="edge-6-2" text="An edge from node 6 to node 2"/>
<annotation ref="edge-6-4" text="An edge from node 6 to node 4"/>
</annotation>
</annotation>
</annotations>
</diagram>
