Basic graphs

The methods defined here appear in sage.graphs.graph_generators.

sage.graphs.generators.basic.BullGraph()[source]

Return a bull graph with 5 nodes.

A bull graph is named for its shape. It’s a triangle with horns. See the Wikipedia article Bull_graph for more information.

PLOTTING:

Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the bull graph is drawn as a triangle with the first node (0) on the bottom. The second and third nodes (1 and 2) complete the triangle. Node 3 is the horn connected to 1 and node 4 is the horn connected to node 2.

EXAMPLES:

Construct and show a bull graph:

sage: g = graphs.BullGraph(); g
Bull graph: Graph on 5 vertices
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.BullGraph(); g
Bull graph: Graph on 5 vertices
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.BullGraph(); g
g.show()                          # long time                             # needs sage.plot

The bull graph has 5 vertices and 5 edges. Its radius is 2, its diameter 3, and its girth 3. The bull graph is planar with chromatic number 3 and chromatic index also 3:

sage: g.order(); g.size()
5
5
sage: g.radius(); g.diameter(); g.girth()
2
3
3
sage: g.chromatic_number()
3

>>> from sage.all import *
>>> g.order(); g.size()
5
5
>>> g.radius(); g.diameter(); g.girth()
2
3
3
>>> g.chromatic_number()
3

g.order(); g.size()
g.radius(); g.diameter(); g.girth()
g.chromatic_number()

The bull graph has chromatic polynomial \(x(x - 2)(x - 1)^3\) and Tutte polynomial \(x^4 + x^3 + x^2 y\). Its characteristic polynomial is \(x(x^2 - x - 3)(x^2 + x - 1)\), which follows from the definition of characteristic polynomials for graphs, i.e. \(\det(xI - A)\), where \(x\) is a variable, \(A\) the adjacency matrix of the graph, and \(I\) the identity matrix of the same dimensions as \(A\):

sage: # needs sage.libs.flint
sage: chrompoly = g.chromatic_polynomial()
sage: x = chrompoly.parent()('x')
sage: x * (x - 2) * (x - 1)^3 == chrompoly
True

sage: # needs sage.libs.flint sage.modules
sage: charpoly = g.characteristic_polynomial()
sage: M = g.adjacency_matrix(); M
[0 1 1 0 0]
[1 0 1 1 0]
[1 1 0 0 1]
[0 1 0 0 0]
[0 0 1 0 0]
sage: Id = identity_matrix(ZZ, M.nrows())
sage: D = x*Id - M
sage: D.determinant() == charpoly                                               # needs sage.symbolic
True
sage: x * (x^2 - x - 3) * (x^2 + x - 1) == charpoly
True

>>> from sage.all import *
>>> # needs sage.libs.flint
>>> chrompoly = g.chromatic_polynomial()
>>> x = chrompoly.parent()('x')
>>> x * (x - Integer(2)) * (x - Integer(1))**Integer(3) == chrompoly
True

>>> # needs sage.libs.flint sage.modules
>>> charpoly = g.characteristic_polynomial()
>>> M = g.adjacency_matrix(); M
[0 1 1 0 0]
[1 0 1 1 0]
[1 1 0 0 1]
[0 1 0 0 0]
[0 0 1 0 0]
>>> Id = identity_matrix(ZZ, M.nrows())
>>> D = x*Id - M
>>> D.determinant() == charpoly                                               # needs sage.symbolic
True
>>> x * (x**Integer(2) - x - Integer(3)) * (x**Integer(2) + x - Integer(1)) == charpoly
True

# needs sage.libs.flint
chrompoly = g.chromatic_polynomial()
x = chrompoly.parent()('x')
x * (x - 2) * (x - 1)^3 == chrompoly
# needs sage.libs.flint sage.modules
charpoly = g.characteristic_polynomial()
M = g.adjacency_matrix(); M
Id = identity_matrix(ZZ, M.nrows())
D = x*Id - M
D.determinant() == charpoly                                               # needs sage.symbolic
x * (x^2 - x - 3) * (x^2 + x - 1) == charpoly
sage.graphs.generators.basic.ButterflyGraph()[source]

Return the butterfly graph.

Let \(C_3\) be the cycle graph on 3 vertices. The butterfly or bowtie graph is obtained by joining two copies of \(C_3\) at a common vertex, resulting in a graph that is isomorphic to the friendship graph \(F_2\). See the Wikipedia article Butterfly_graph for more information.

See also

EXAMPLES:

The butterfly graph is a planar graph on 5 vertices and having 6 edges:

sage: G = graphs.ButterflyGraph(); G
Butterfly graph: Graph on 5 vertices
sage: G.show()                          # long time                             # needs sage.plot
sage: G.is_planar()
True
sage: G.order()
5
sage: G.size()
6

>>> from sage.all import *
>>> G = graphs.ButterflyGraph(); G
Butterfly graph: Graph on 5 vertices
>>> G.show()                          # long time                             # needs sage.plot
>>> G.is_planar()
True
>>> G.order()
5
>>> G.size()
6

G = graphs.ButterflyGraph(); G
G.show()                          # long time                             # needs sage.plot
G.is_planar()
G.order()
G.size()

It has diameter 2, girth 3, and radius 1:

sage: G.diameter()
2
sage: G.girth()
3
sage: G.radius()
1

>>> from sage.all import *
>>> G.diameter()
2
>>> G.girth()
3
>>> G.radius()
1

G.diameter()
G.girth()
G.radius()

The butterfly graph is Eulerian, with chromatic number 3:

sage: G.is_eulerian()
True
sage: G.chromatic_number()
3

>>> from sage.all import *
>>> G.is_eulerian()
True
>>> G.chromatic_number()
3

G.is_eulerian()
G.chromatic_number()
sage.graphs.generators.basic.CircularLadderGraph(n)[source]

Return a circular ladder graph with \(2 * n\) nodes.

A Circular ladder graph is a ladder graph that is connected at the ends, i.e.: a ladder bent around so that top meets bottom. Thus it can be described as two parallel cycle graphs connected at each corresponding node pair.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the circular ladder graph is displayed as an inner and outer cycle pair, with the first \(n\) nodes drawn on the inner circle. The first (0) node is drawn at the top of the inner-circle, moving clockwise after that. The outer circle is drawn with the \((n+1)\)-th node at the top, then counterclockwise as well. When \(n == 2\), we rotate the outer circle by an angle of \(\pi/8\) to ensure that all edges are visible (otherwise the 4 vertices of the graph would be placed on a single line).

EXAMPLES:

Construct and show a circular ladder graph with 26 nodes:

sage: g = graphs.CircularLadderGraph(13)
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.CircularLadderGraph(Integer(13))
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.CircularLadderGraph(13)
g.show()                          # long time                             # needs sage.plot

Create several circular ladder graphs in a Sage graphics array:

sage: g = []
sage: j = []
sage: for i in range(9):
....:    k = graphs.CircularLadderGraph(i+3)
....:    g.append(k)
sage: for i in range(3):                                                        # needs sage.plot
....:    n = []
....:    for m in range(3):
....:        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:    j.append(n)
sage: G = graphics_array(j)                                                     # needs sage.plot
sage: G.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...    k = graphs.CircularLadderGraph(i+Integer(3))
...    g.append(k)
>>> for i in range(Integer(3)):                                                        # needs sage.plot
...    n = []
...    for m in range(Integer(3)):
...        n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...    j.append(n)
>>> G = graphics_array(j)                                                     # needs sage.plot
>>> G.show()                          # long time                             # needs sage.plot

g = []
j = []
for i in range(9):
   k = graphs.CircularLadderGraph(i+3)
   g.append(k)
for i in range(3):                                                        # needs sage.plot
   n = []
   for m in range(3):
       n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
   j.append(n)
G = graphics_array(j)                                                     # needs sage.plot
G.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.ClawGraph()[source]

Return a claw graph.

A claw graph is named for its shape. It is actually a complete bipartite graph with (n1, n2) = (1, 3).

PLOTTING: See CompleteBipartiteGraph().

EXAMPLES:

Show a Claw graph:

sage: (graphs.ClawGraph()).show()       # long time                             # needs sage.plot

>>> from sage.all import *
>>> (graphs.ClawGraph()).show()       # long time                             # needs sage.plot

(graphs.ClawGraph()).show()       # long time                             # needs sage.plot

Inspect a Claw graph:

sage: G = graphs.ClawGraph()
sage: G
Claw graph: Graph on 4 vertices

>>> from sage.all import *
>>> G = graphs.ClawGraph()
>>> G
Claw graph: Graph on 4 vertices

G = graphs.ClawGraph()
G
sage.graphs.generators.basic.CompleteBipartiteGraph(p, q, set_position=True)[source]

Return a Complete Bipartite Graph on \(p + q\) vertices.

A Complete Bipartite Graph is a graph with its vertices partitioned into two groups, \(V_1 = \{0,...,p-1\}\) and \(V_2 = \{p,...,p+q-1\}\). Each \(u \in V_1\) is connected to every \(v \in V_2\).

INPUT:

  • p, q – number of vertices in each side

  • set_position – boolean (default: True); if set to True, we assign positions to the vertices so that the set of cardinality \(p\) is on the line \(y=1\) and the set of cardinality \(q\) is on the line \(y=0\).

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each complete bipartite graph will be displayed with the first \(p\) nodes on the top row (at \(y=1\)) from left to right. The remaining \(q\) nodes appear at \(y=0\), also from left to right. The shorter row (partition with fewer nodes) is stretched to the same length as the longer row, unless the shorter row has 1 node; in which case it is centered. The \(x\) values in the plot are in domain \([0, \max(p, q)]\).

In the Complete Bipartite graph, there is a visual difference in using the spring-layout algorithm vs. the position dictionary used in this constructor. The position dictionary flattens the graph and separates the partitioned nodes, making it clear which nodes an edge is connected to. The Complete Bipartite graph plotted with the spring-layout algorithm tends to center the nodes in \(p\) (see spring_med in examples below), thus overlapping its nodes and edges, making it typically hard to decipher.

Filling the position dictionary in advance adds \(O(n)\) to the constructor. Feel free to race the constructors below in the examples section. The much larger difference is the time added by the spring-layout algorithm when plotting. (Also shown in the example below). The spring model is typically described as \(O(n^3)\), as appears to be the case in the NetworkX source code.

EXAMPLES:

Two ways of constructing the complete bipartite graph, using different layout algorithms:

sage: # needs networkx
sage: import networkx
sage: n = networkx.complete_bipartite_graph(389, 157)   # long time
sage: spring_big = Graph(n)             # long time
sage: posdict_big = graphs.CompleteBipartiteGraph(389, 157)        # long time

>>> from sage.all import *
>>> # needs networkx
>>> import networkx
>>> n = networkx.complete_bipartite_graph(Integer(389), Integer(157))   # long time
>>> spring_big = Graph(n)             # long time
>>> posdict_big = graphs.CompleteBipartiteGraph(Integer(389), Integer(157))        # long time

# needs networkx
import networkx
n = networkx.complete_bipartite_graph(389, 157)   # long time
spring_big = Graph(n)             # long time
posdict_big = graphs.CompleteBipartiteGraph(389, 157)        # long time

Compare the plotting:

sage: n = networkx.complete_bipartite_graph(11, 17)                             # needs networkx
sage: spring_med = Graph(n)                                                     # needs networkx
sage: posdict_med = graphs.CompleteBipartiteGraph(11, 17)

>>> from sage.all import *
>>> n = networkx.complete_bipartite_graph(Integer(11), Integer(17))                             # needs networkx
>>> spring_med = Graph(n)                                                     # needs networkx
>>> posdict_med = graphs.CompleteBipartiteGraph(Integer(11), Integer(17))

n = networkx.complete_bipartite_graph(11, 17)                             # needs networkx
spring_med = Graph(n)                                                     # needs networkx
posdict_med = graphs.CompleteBipartiteGraph(11, 17)

Notice here how the spring-layout tends to center the nodes of \(n1\):

sage: spring_med.show()                 # long time                             # needs networkx
sage: posdict_med.show()                # long time                             # needs sage.plot

>>> from sage.all import *
>>> spring_med.show()                 # long time                             # needs networkx
>>> posdict_med.show()                # long time                             # needs sage.plot

spring_med.show()                 # long time                             # needs networkx
posdict_med.show()                # long time                             # needs sage.plot

View many complete bipartite graphs with a Sage Graphics Array, with this constructor (i.e., the position dictionary filled):

sage: g = []
sage: j = []
sage: for i in range(9):
....:     k = graphs.CompleteBipartiteGraph(i+1,4)
....:     g.append(k)
sage: for i in range(3):                                                        # needs sage.plot
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)                                                     # needs sage.plot
sage: G.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...     k = graphs.CompleteBipartiteGraph(i+Integer(1),Integer(4))
...     g.append(k)
>>> for i in range(Integer(3)):                                                        # needs sage.plot
...     n = []
...     for m in range(Integer(3)):
...         n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...     j.append(n)
>>> G = graphics_array(j)                                                     # needs sage.plot
>>> G.show()                          # long time                             # needs sage.plot

g = []
j = []
for i in range(9):
    k = graphs.CompleteBipartiteGraph(i+1,4)
    g.append(k)
for i in range(3):                                                        # needs sage.plot
    n = []
    for m in range(3):
        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
    j.append(n)
G = graphics_array(j)                                                     # needs sage.plot
G.show()                          # long time                             # needs sage.plot

We compare to plotting with the spring-layout algorithm:

sage: # needs networkx sage.plot
sage: g = []
sage: j = []
sage: for i in range(9):
....:     spr = networkx.complete_bipartite_graph(i+1,4)
....:     k = Graph(spr)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

>>> from sage.all import *
>>> # needs networkx sage.plot
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...     spr = networkx.complete_bipartite_graph(i+Integer(1),Integer(4))
...     k = Graph(spr)
...     g.append(k)
>>> for i in range(Integer(3)):
...     n = []
...     for m in range(Integer(3)):
...         n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...     j.append(n)
>>> G = graphics_array(j)
>>> G.show()                          # long time

# needs networkx sage.plot
g = []
j = []
for i in range(9):
    spr = networkx.complete_bipartite_graph(i+1,4)
    k = Graph(spr)
    g.append(k)
for i in range(3):
    n = []
    for m in range(3):
        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
    j.append(n)
G = graphics_array(j)
G.show()                          # long time

Issue #12155:

sage: graphs.CompleteBipartiteGraph(5,6).complement()
complement(Complete bipartite graph of order 5+6): Graph on 11 vertices

>>> from sage.all import *
>>> graphs.CompleteBipartiteGraph(Integer(5),Integer(6)).complement()
complement(Complete bipartite graph of order 5+6): Graph on 11 vertices

graphs.CompleteBipartiteGraph(5,6).complement()
sage.graphs.generators.basic.CompleteGraph(n)[source]

Return a complete graph on \(n\) nodes.

A Complete Graph is a graph in which all nodes are connected to all other nodes.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each complete graph will be displayed with the first (0) node at the top, with the rest following in a counterclockwise manner.

In the complete graph, there is a big difference visually in using the spring-layout algorithm vs. the position dictionary used in this constructor. The position dictionary flattens the graph, making it clear which nodes an edge is connected to. But the complete graph offers a good example of how the spring-layout works. The edges push outward (everything is connected), causing the graph to appear as a 3-dimensional pointy ball. (See examples below).

EXAMPLES:

We view many Complete graphs with a Sage Graphics Array, first with this constructor (i.e., the position dictionary filled):

sage: # needs sage.plot
sage: g = []
sage: j = []
sage: for i in range(9):
....:     k = graphs.CompleteGraph(i+3)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

>>> from sage.all import *
>>> # needs sage.plot
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...     k = graphs.CompleteGraph(i+Integer(3))
...     g.append(k)
>>> for i in range(Integer(3)):
...     n = []
...     for m in range(Integer(3)):
...         n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...     j.append(n)
>>> G = graphics_array(j)
>>> G.show()                          # long time

# needs sage.plot
g = []
j = []
for i in range(9):
    k = graphs.CompleteGraph(i+3)
    g.append(k)
for i in range(3):
    n = []
    for m in range(3):
        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
    j.append(n)
G = graphics_array(j)
G.show()                          # long time

We compare to plotting with the spring-layout algorithm:

sage: # needs networkx sage.plot
sage: import networkx
sage: g = []
sage: j = []
sage: for i in range(9):
....:     spr = networkx.complete_graph(i+3)
....:     k = Graph(spr)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

>>> from sage.all import *
>>> # needs networkx sage.plot
>>> import networkx
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...     spr = networkx.complete_graph(i+Integer(3))
...     k = Graph(spr)
...     g.append(k)
>>> for i in range(Integer(3)):
...     n = []
...     for m in range(Integer(3)):
...         n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...     j.append(n)
>>> G = graphics_array(j)
>>> G.show()                          # long time

# needs networkx sage.plot
import networkx
g = []
j = []
for i in range(9):
    spr = networkx.complete_graph(i+3)
    k = Graph(spr)
    g.append(k)
for i in range(3):
    n = []
    for m in range(3):
        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
    j.append(n)
G = graphics_array(j)
G.show()                          # long time

Compare the constructors (results will vary):

sage: # needs networkx
sage: import networkx
sage: t = cputime()
sage: n = networkx.complete_graph(389); spring389 = Graph(n)
sage: cputime(t)  # random
0.59203700000000126
sage: t = cputime()
sage: posdict389 = graphs.CompleteGraph(389)
sage: cputime(t)  # random
0.6680419999999998

>>> from sage.all import *
>>> # needs networkx
>>> import networkx
>>> t = cputime()
>>> n = networkx.complete_graph(Integer(389)); spring389 = Graph(n)
>>> cputime(t)  # random
0.59203700000000126
>>> t = cputime()
>>> posdict389 = graphs.CompleteGraph(Integer(389))
>>> cputime(t)  # random
0.6680419999999998

# needs networkx
import networkx
t = cputime()
n = networkx.complete_graph(389); spring389 = Graph(n)
cputime(t)  # random
t = cputime()
posdict389 = graphs.CompleteGraph(389)
cputime(t)  # random

We compare plotting:

sage: # needs networkx
sage: import networkx
sage: n = networkx.complete_graph(23)
sage: spring23 = Graph(n)
sage: posdict23 = graphs.CompleteGraph(23)
sage: spring23.show()                   # long time                             # needs sage.plot
sage: posdict23.show()                  # long time                             # needs sage.plot

>>> from sage.all import *
>>> # needs networkx
>>> import networkx
>>> n = networkx.complete_graph(Integer(23))
>>> spring23 = Graph(n)
>>> posdict23 = graphs.CompleteGraph(Integer(23))
>>> spring23.show()                   # long time                             # needs sage.plot
>>> posdict23.show()                  # long time                             # needs sage.plot

# needs networkx
import networkx
n = networkx.complete_graph(23)
spring23 = Graph(n)
posdict23 = graphs.CompleteGraph(23)
spring23.show()                   # long time                             # needs sage.plot
posdict23.show()                  # long time                             # needs sage.plot
sage.graphs.generators.basic.CompleteMultipartiteGraph(L)[source]

Return a complete multipartite graph.

INPUT:

  • L – list of integers; the respective sizes of the components

PLOTTING: Produce a layout of the vertices so that vertices in the same vertex set are adjacent and clearly separated from vertices in other vertex sets.

This is done by calculating the vertices of an \(r\)-gon then calculating the slope between adjacent vertices. We then ‘walk’ around the \(r\)-gon placing graph vertices in regular intervals between adjacent vertices of the \(r\)-gon.

Makes a nicely organized graph like in this picture: https://commons.wikimedia.org/wiki/File:Turan_13-4.svg

EXAMPLES:

A complete tripartite graph with sets of sizes \(5, 6, 8\):

sage: g = graphs.CompleteMultipartiteGraph([5, 6, 8]); g
Multipartite Graph with set sizes [5, 6, 8]: Graph on 19 vertices

>>> from sage.all import *
>>> g = graphs.CompleteMultipartiteGraph([Integer(5), Integer(6), Integer(8)]); g
Multipartite Graph with set sizes [5, 6, 8]: Graph on 19 vertices

g = graphs.CompleteMultipartiteGraph([5, 6, 8]); g

It clearly has a chromatic number of 3:

sage: g.chromatic_number()
3

>>> from sage.all import *
>>> g.chromatic_number()
3

g.chromatic_number()
sage.graphs.generators.basic.CorrelationGraph(seqs, alpha, include_anticorrelation)[source]

Return a correlation graph with a node per sequence in seqs.

Edges are added between nodes where the corresponding sequences have a correlation coefficient greater than alpha.

If include_anticorrelation is True, then edges are also added between nodes with correlation coefficient less than -alpha.

INPUT:

  • seqs – list of sequences, that is a list of lists

  • alpha – float; threshold on the correlation coefficient between two sequences for adding an edge

  • include_anticorrelation – boolean; whether to add edges between nodes with correlation coefficient less than -alpha or not

EXAMPLES:

sage: # needs numpy
sage: from sage.graphs.generators.basic import CorrelationGraph
sage: data = [[1,2,3], [4,5,6], [7,8,9999]]
sage: CG1 = CorrelationGraph(data, 0.9, False)
sage: CG2 = CorrelationGraph(data, 0.9, True)
sage: CG3 = CorrelationGraph(data, 0.1, True)
sage: CG1.edges(sort=False)
[(0, 0, None), (0, 1, None), (1, 1, None), (2, 2, None)]
sage: CG2.edges(sort=False)
[(0, 0, None), (0, 1, None), (1, 1, None), (2, 2, None)]
sage: CG3.edges(sort=False)
[(0, 0, None), (0, 1, None), (0, 2, None), (1, 1, None), (1, 2, None), (2, 2, None)]

>>> from sage.all import *
>>> # needs numpy
>>> from sage.graphs.generators.basic import CorrelationGraph
>>> data = [[Integer(1),Integer(2),Integer(3)], [Integer(4),Integer(5),Integer(6)], [Integer(7),Integer(8),Integer(9999)]]
>>> CG1 = CorrelationGraph(data, RealNumber('0.9'), False)
>>> CG2 = CorrelationGraph(data, RealNumber('0.9'), True)
>>> CG3 = CorrelationGraph(data, RealNumber('0.1'), True)
>>> CG1.edges(sort=False)
[(0, 0, None), (0, 1, None), (1, 1, None), (2, 2, None)]
>>> CG2.edges(sort=False)
[(0, 0, None), (0, 1, None), (1, 1, None), (2, 2, None)]
>>> CG3.edges(sort=False)
[(0, 0, None), (0, 1, None), (0, 2, None), (1, 1, None), (1, 2, None), (2, 2, None)]

# needs numpy
from sage.graphs.generators.basic import CorrelationGraph
data = [[1,2,3], [4,5,6], [7,8,9999]]
CG1 = CorrelationGraph(data, 0.9, False)
CG2 = CorrelationGraph(data, 0.9, True)
CG3 = CorrelationGraph(data, 0.1, True)
CG1.edges(sort=False)
CG2.edges(sort=False)
CG3.edges(sort=False)
sage.graphs.generators.basic.CycleGraph(n)[source]

Return a cycle graph with \(n\) nodes.

A cycle graph is a basic structure which is also typically called an \(n\)-gon.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each cycle graph will be displayed with the first (0) node at the top, with the rest following in a counterclockwise manner.

The cycle graph is a good opportunity to compare efficiency of filling a position dictionary vs. using the spring-layout algorithm for plotting. Because the cycle graph is very symmetric, the resulting plots should be similar (in cases of small \(n\)).

Filling the position dictionary in advance adds \(O(n)\) to the constructor.

EXAMPLES:

Compare plotting using the predefined layout and networkx:

sage: # needs networkx sage.plot
sage: import networkx
sage: n = networkx.cycle_graph(23)
sage: spring23 = Graph(n)
sage: posdict23 = graphs.CycleGraph(23)
sage: spring23.show()                   # long time
sage: posdict23.show()                  # long time

>>> from sage.all import *
>>> # needs networkx sage.plot
>>> import networkx
>>> n = networkx.cycle_graph(Integer(23))
>>> spring23 = Graph(n)
>>> posdict23 = graphs.CycleGraph(Integer(23))
>>> spring23.show()                   # long time
>>> posdict23.show()                  # long time

# needs networkx sage.plot
import networkx
n = networkx.cycle_graph(23)
spring23 = Graph(n)
posdict23 = graphs.CycleGraph(23)
spring23.show()                   # long time
posdict23.show()                  # long time

We next view many cycle graphs as a Sage graphics array. First we use the CycleGraph constructor, which fills in the position dictionary:

sage: # needs networkx sage.plot
sage: g = []
sage: j = []
sage: for i in range(9):
....:     k = graphs.CycleGraph(i+3)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

>>> from sage.all import *
>>> # needs networkx sage.plot
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...     k = graphs.CycleGraph(i+Integer(3))
...     g.append(k)
>>> for i in range(Integer(3)):
...     n = []
...     for m in range(Integer(3)):
...         n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...     j.append(n)
>>> G = graphics_array(j)
>>> G.show()                          # long time

# needs networkx sage.plot
g = []
j = []
for i in range(9):
    k = graphs.CycleGraph(i+3)
    g.append(k)
for i in range(3):
    n = []
    for m in range(3):
        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
    j.append(n)
G = graphics_array(j)
G.show()                          # long time

Compare to plotting with the spring-layout algorithm:

sage: # needs networkx sage.plot
sage: g = []
sage: j = []
sage: for i in range(9):
....:     spr = networkx.cycle_graph(i+3)
....:     k = Graph(spr)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

>>> from sage.all import *
>>> # needs networkx sage.plot
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...     spr = networkx.cycle_graph(i+Integer(3))
...     k = Graph(spr)
...     g.append(k)
>>> for i in range(Integer(3)):
...     n = []
...     for m in range(Integer(3)):
...         n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...     j.append(n)
>>> G = graphics_array(j)
>>> G.show()                          # long time

# needs networkx sage.plot
g = []
j = []
for i in range(9):
    spr = networkx.cycle_graph(i+3)
    k = Graph(spr)
    g.append(k)
for i in range(3):
    n = []
    for m in range(3):
        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
    j.append(n)
G = graphics_array(j)
G.show()                          # long time
sage.graphs.generators.basic.DartGraph()[source]

Return a dart graph with 5 nodes.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the dart graph is drawn as a dart, with the sharp part on the bottom.

EXAMPLES:

Construct and show a dart graph:

sage: g = graphs.DartGraph()
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.DartGraph()
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.DartGraph()
g.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.DiamondGraph()[source]

Return a diamond graph with 4 nodes.

A diamond graph is a square with one pair of diagonal nodes connected.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the diamond graph is drawn as a diamond, with the first node on top, second on the left, third on the right, and fourth on the bottom; with the second and third node connected.

EXAMPLES:

Construct and show a diamond graph:

sage: g = graphs.DiamondGraph()
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.DiamondGraph()
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.DiamondGraph()
g.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.EmptyGraph()[source]

Return an empty graph (0 nodes and 0 edges).

This is useful for constructing graphs by adding edges and vertices individually or in a loop.

PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.

EXAMPLES:

Add one vertex to an empty graph and then show:

sage: empty1 = graphs.EmptyGraph()
sage: empty1.add_vertex()
0
sage: empty1.show()                     # long time                             # needs sage.plot

>>> from sage.all import *
>>> empty1 = graphs.EmptyGraph()
>>> empty1.add_vertex()
0
>>> empty1.show()                     # long time                             # needs sage.plot

empty1 = graphs.EmptyGraph()
empty1.add_vertex()
empty1.show()                     # long time                             # needs sage.plot

Use for loops to build a graph from an empty graph:

sage: empty2 = graphs.EmptyGraph()
sage: for i in range(5):
....:     empty2.add_vertex()  # add 5 nodes, labeled 0-4
0
1
2
3
4
sage: for i in range(3):
....:     empty2.add_edge(i,i+1)  # add edges {[0:1],[1:2],[2:3]}
sage: for i in range(1, 4):
....:     empty2.add_edge(4,i)  # add edges {[1:4],[2:4],[3:4]}
sage: empty2.show()                     # long time                             # needs sage.plot

>>> from sage.all import *
>>> empty2 = graphs.EmptyGraph()
>>> for i in range(Integer(5)):
...     empty2.add_vertex()  # add 5 nodes, labeled 0-4
0
1
2
3
4
>>> for i in range(Integer(3)):
...     empty2.add_edge(i,i+Integer(1))  # add edges {[0:1],[1:2],[2:3]}
>>> for i in range(Integer(1), Integer(4)):
...     empty2.add_edge(Integer(4),i)  # add edges {[1:4],[2:4],[3:4]}
>>> empty2.show()                     # long time                             # needs sage.plot

empty2 = graphs.EmptyGraph()
for i in range(5):
    empty2.add_vertex()  # add 5 nodes, labeled 0-4
for i in range(3):
    empty2.add_edge(i,i+1)  # add edges {[0:1],[1:2],[2:3]}
for i in range(1, 4):
    empty2.add_edge(4,i)  # add edges {[1:4],[2:4],[3:4]}
empty2.show()                     # long time                             # needs sage.plot
sage.graphs.generators.basic.ForkGraph()[source]

Return a fork graph with 5 nodes.

A fork graph, sometimes also called chair graph, is 5 vertex tree.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the fork graph is drawn as a fork, with the sharp part on the bottom.

EXAMPLES:

Construct and show a fork graph:

sage: g = graphs.ForkGraph()
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.ForkGraph()
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.ForkGraph()
g.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.GemGraph()[source]

Return a gem graph with 5 nodes.

A gem graph is a fan graph (4,1).

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the gem graph is drawn as a gem, with the sharp part on the bottom.

EXAMPLES:

Construct and show a gem graph:

sage: g = graphs.GemGraph()
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.GemGraph()
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.GemGraph()
g.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.Grid2dGraph(p, q, set_positions=True)[source]

Return a \(2\)-dimensional grid graph with \(p \times q\) nodes (\(p\) rows and \(q\) columns).

A 2d grid graph resembles a \(2\) dimensional grid. All inner nodes are connected to their \(4\) neighbors. Outer (non-corner) nodes are connected to their \(3\) neighbors. Corner nodes are connected to their 2 neighbors.

INPUT:

  • p, q – two positive integers

  • set_positions – boolean (default: True); whether to set the position of the nodes

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, nodes are labelled in (row, column) pairs with \((0, 0)\) in the top left corner. Edges will always be horizontal and vertical - another advantage of filling the position dictionary.

EXAMPLES:

Construct and show a grid 2d graph Rows = \(5\), Columns = \(7\):

sage: g = graphs.Grid2dGraph(5,7)
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.Grid2dGraph(Integer(5),Integer(7))
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.Grid2dGraph(5,7)
g.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.GridGraph(dim_list)[source]

Return an \(n\)-dimensional grid graph.

INPUT:

  • dim_list – list of integers representing the number of nodes to extend in each dimension

PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.

EXAMPLES:

sage: G = graphs.GridGraph([2,3,4])
sage: G.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> G = graphs.GridGraph([Integer(2),Integer(3),Integer(4)])
>>> G.show()                          # long time                             # needs sage.plot

G = graphs.GridGraph([2,3,4])
G.show()                          # long time                             # needs sage.plot
sage: C = graphs.CubeGraph(4)
sage: G = graphs.GridGraph([2,2,2,2])
sage: C.show()                          # long time                             # needs sage.plot
sage: G.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> C = graphs.CubeGraph(Integer(4))
>>> G = graphs.GridGraph([Integer(2),Integer(2),Integer(2),Integer(2)])
>>> C.show()                          # long time                             # needs sage.plot
>>> G.show()                          # long time                             # needs sage.plot

C = graphs.CubeGraph(4)
G = graphs.GridGraph([2,2,2,2])
C.show()                          # long time                             # needs sage.plot
G.show()                          # long time                             # needs sage.plot
>>> from sage.all import *
>>> C = graphs.CubeGraph(Integer(4))
>>> G = graphs.GridGraph([Integer(2),Integer(2),Integer(2),Integer(2)])
>>> C.show()                          # long time                             # needs sage.plot
>>> G.show()                          # long time                             # needs sage.plot

C = graphs.CubeGraph(4)
G = graphs.GridGraph([2,2,2,2])
C.show()                          # long time                             # needs sage.plot
G.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.HouseGraph()[source]

Return a house graph with 5 nodes.

A house graph is named for its shape. It is a triangle (roof) over a square (walls).

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the house graph is drawn with the first node in the lower-left corner of the house, the second in the lower-right corner of the house. The third node is in the upper-left corner connecting the roof to the wall, and the fourth is in the upper-right corner connecting the roof to the wall. The fifth node is the top of the roof, connected only to the third and fourth.

EXAMPLES:

Construct and show a house graph:

sage: g = graphs.HouseGraph()
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.HouseGraph()
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.HouseGraph()
g.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.HouseXGraph()[source]

Return a house X graph with 5 nodes.

A house X graph is a house graph with two additional edges. The upper-right corner is connected to the lower-left. And the upper-left corner is connected to the lower-right.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the house X graph is drawn with the first node in the lower-left corner of the house, the second in the lower-right corner of the house. The third node is in the upper-left corner connecting the roof to the wall, and the fourth is in the upper-right corner connecting the roof to the wall. The fifth node is the top of the roof, connected only to the third and fourth.

EXAMPLES:

Construct and show a house X graph:

sage: g = graphs.HouseXGraph()
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.HouseXGraph()
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.HouseXGraph()
g.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.LadderGraph(n)[source]

Return a ladder graph with \(2 * n\) nodes.

A ladder graph is a basic structure that is typically displayed as a ladder, i.e.: two parallel path graphs connected at each corresponding node pair.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each ladder graph will be displayed horizontally, with the first n nodes displayed left to right on the top horizontal line.

EXAMPLES:

Construct and show a ladder graph with 14 nodes:

sage: g = graphs.LadderGraph(7)
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.LadderGraph(Integer(7))
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.LadderGraph(7)
g.show()                          # long time                             # needs sage.plot

Create several ladder graphs in a Sage graphics array:

sage: # needs sage.plot
sage: g = []
sage: j = []
sage: for i in range(9):
....:     k = graphs.LadderGraph(i+2)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

>>> from sage.all import *
>>> # needs sage.plot
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...     k = graphs.LadderGraph(i+Integer(2))
...     g.append(k)
>>> for i in range(Integer(3)):
...     n = []
...     for m in range(Integer(3)):
...         n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...     j.append(n)
>>> G = graphics_array(j)
>>> G.show()                          # long time

# needs sage.plot
g = []
j = []
for i in range(9):
    k = graphs.LadderGraph(i+2)
    g.append(k)
for i in range(3):
    n = []
    for m in range(3):
        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
    j.append(n)
G = graphics_array(j)
G.show()                          # long time
sage.graphs.generators.basic.MoebiusLadderGraph(n)[source]

Return a Möbius ladder graph with \(2n\) nodes

A Möbius ladder graph of order \(2n\) is a ladder graph of the same order that is connected at the ends with a single twist, i.e., a ladder graph bent around so that top meets bottom with a single twist. Alternatively, it can be described as a single cycle graph (of order \(2n\)) with the addition of edges (called \(rungs\)) joining the antipodal pairs of nodes. Also, note that the Möbius ladder graph graphs.MoebiusLadderGraph(n) is precisely the same graph as the circulant graph graphs.CirculantGraph(2 * n, [1, n]).

PLOTTING:

Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each Möbius ladder graph will be displayed with the first (0) node at the top, with the rest following in a counterclockwise manner.

INPUT:

  • n – a nonnegative integer; number of nodes is \(2n\)

OUTPUT:

  • G – a Möbius ladder graph of order \(2n\); note that a ValueError is returned if \(n < 0\)

EXAMPLES:

Construct and show a Möbius ladder graph with 26 nodes:

sage: g = graphs.MoebiusLadderGraph(13)
sage: g.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> g = graphs.MoebiusLadderGraph(Integer(13))
>>> g.show()                          # long time                             # needs sage.plot

g = graphs.MoebiusLadderGraph(13)
g.show()                          # long time                             # needs sage.plot

Create several Möbius ladder graphs in a Sage graphics array:

sage: # needs sage.plots
sage: g = []
sage: j = []
sage: for i in range(9):
....:    k = graphs.MoebiusLadderGraph(i+3)
....:    g.append(k)
sage: for i in range(3):
....:    n = []
....:    for m in range(3):
....:        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:    j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

>>> from sage.all import *
>>> # needs sage.plots
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...    k = graphs.MoebiusLadderGraph(i+Integer(3))
...    g.append(k)
>>> for i in range(Integer(3)):
...    n = []
...    for m in range(Integer(3)):
...        n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...    j.append(n)
>>> G = graphics_array(j)
>>> G.show()                          # long time

# needs sage.plots
g = []
j = []
for i in range(9):
   k = graphs.MoebiusLadderGraph(i+3)
   g.append(k)
for i in range(3):
   n = []
   for m in range(3):
       n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
   j.append(n)
G = graphics_array(j)
G.show()                          # long time

REFERENCES:

See also

LadderGraph(), CircularLadderGraph(), CirculantGraph()

AUTHORS:

  • Janmenjaya Panda (2024-05-26)

sage.graphs.generators.basic.PathGraph(n, pos=None)[source]

Return a path graph with \(n\) nodes.

A path graph is a graph where all inner nodes are connected to their two neighbors and the two end-nodes are connected to their one inner neighbors (i.e.: a cycle graph without the first and last node connected).

INPUT:

  • n – number of nodes of the path graph

  • pos – string (default: None); indicates the embedding to use between ‘circle’, ‘line’ or the default algorithm. See the plotting section below for more detail.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the graph may be drawn in one of two ways: The ‘line’ argument will draw the graph in a horizontal line (left to right) if there are less than 11 nodes. Otherwise the ‘line’ argument will append horizontal lines of length 10 nodes below, alternating left to right and right to left. The ‘circle’ argument will cause the graph to be drawn in a cycle-shape, with the first node at the top and then about the circle in a clockwise manner. By default (without an appropriate string argument) the graph will be drawn as a ‘circle’ if \(10 < n < 41\) and as a ‘line’ for all other \(n\).

EXAMPLES: Show default drawing by size: ‘line’: \(n \leq 10\)

sage: p = graphs.PathGraph(10)
sage: p.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> p = graphs.PathGraph(Integer(10))
>>> p.show()                          # long time                             # needs sage.plot

p = graphs.PathGraph(10)
p.show()                          # long time                             # needs sage.plot

‘circle’: \(10 < n < 41\)

sage: q = graphs.PathGraph(25)
sage: q.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> q = graphs.PathGraph(Integer(25))
>>> q.show()                          # long time                             # needs sage.plot

q = graphs.PathGraph(25)
q.show()                          # long time                             # needs sage.plot

‘line’: \(n \geq 41\)

sage: r = graphs.PathGraph(55)
sage: r.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> r = graphs.PathGraph(Integer(55))
>>> r.show()                          # long time                             # needs sage.plot

r = graphs.PathGraph(55)
r.show()                          # long time                             # needs sage.plot

Override the default drawing:

sage: s = graphs.PathGraph(5,'circle')
sage: s.show()                          # long time                             # needs sage.plot

>>> from sage.all import *
>>> s = graphs.PathGraph(Integer(5),'circle')
>>> s.show()                          # long time                             # needs sage.plot

s = graphs.PathGraph(5,'circle')
s.show()                          # long time                             # needs sage.plot
sage.graphs.generators.basic.StarGraph(n)[source]

Return a star graph with \(n + 1\) nodes.

A Star graph is a basic structure where one node is connected to all other nodes.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each star graph will be displayed with the first (0) node in the center, the second node (1) at the top, with the rest following in a counterclockwise manner. (0) is the node connected to all other nodes.

The star graph is a good opportunity to compare efficiency of filling a position dictionary vs. using the spring-layout algorithm for plotting. As far as display, the spring-layout should push all other nodes away from the (0) node, and thus look very similar to this constructor’s positioning.

EXAMPLES:

sage: import networkx                                                           # needs networkx

>>> from sage.all import *
>>> import networkx                                                           # needs networkx

import networkx                                                           # needs networkx

Compare the plots:

sage: # needs networkx sage.plot
sage: n = networkx.star_graph(23)
sage: spring23 = Graph(n)
sage: posdict23 = graphs.StarGraph(23)
sage: spring23.show()                   # long time
sage: posdict23.show()  # long time

>>> from sage.all import *
>>> # needs networkx sage.plot
>>> n = networkx.star_graph(Integer(23))
>>> spring23 = Graph(n)
>>> posdict23 = graphs.StarGraph(Integer(23))
>>> spring23.show()                   # long time
>>> posdict23.show()  # long time

# needs networkx sage.plot
n = networkx.star_graph(23)
spring23 = Graph(n)
posdict23 = graphs.StarGraph(23)
spring23.show()                   # long time
posdict23.show()  # long time

View many star graphs as a Sage Graphics Array

With this constructor (i.e., the position dictionary filled)

sage: # needs sage.plot
sage: g = []
sage: j = []
sage: for i in range(9):
....:     k = graphs.StarGraph(i+3)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

>>> from sage.all import *
>>> # needs sage.plot
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...     k = graphs.StarGraph(i+Integer(3))
...     g.append(k)
>>> for i in range(Integer(3)):
...     n = []
...     for m in range(Integer(3)):
...         n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...     j.append(n)
>>> G = graphics_array(j)
>>> G.show()                          # long time

# needs sage.plot
g = []
j = []
for i in range(9):
    k = graphs.StarGraph(i+3)
    g.append(k)
for i in range(3):
    n = []
    for m in range(3):
        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
    j.append(n)
G = graphics_array(j)
G.show()                          # long time

Compared to plotting with the spring-layout algorithm

sage: # needs networkx sage.plot
sage: g = []
sage: j = []
sage: for i in range(9):
....:     spr = networkx.star_graph(i+3)
....:     k = Graph(spr)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

>>> from sage.all import *
>>> # needs networkx sage.plot
>>> g = []
>>> j = []
>>> for i in range(Integer(9)):
...     spr = networkx.star_graph(i+Integer(3))
...     k = Graph(spr)
...     g.append(k)
>>> for i in range(Integer(3)):
...     n = []
...     for m in range(Integer(3)):
...         n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False))
...     j.append(n)
>>> G = graphics_array(j)
>>> G.show()                          # long time

# needs networkx sage.plot
g = []
j = []
for i in range(9):
    spr = networkx.star_graph(i+3)
    k = Graph(spr)
    g.append(k)
for i in range(3):
    n = []
    for m in range(3):
        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
    j.append(n)
G = graphics_array(j)
G.show()                          # long time
sage.graphs.generators.basic.Toroidal6RegularGrid2dGraph(p, q)[source]

Return a toroidal 6-regular grid.

The toroidal 6-regular grid is a 6-regular graph on \(p \times q\) vertices and its elements have coordinates \((i, j)\) for \(i \in \{0...p-1\}\) and \(j \in \{0...q-1\}\).

Its edges are those of the ToroidalGrid2dGraph(), to which are added the edges between \((i, j)\) and \(((i + 1) \% p, (j + 1) \% q)\).

INPUT:

  • p, q – integers

EXAMPLES:

The toroidal 6-regular grid on \(25\) elements:

sage: g = graphs.Toroidal6RegularGrid2dGraph(5,5)
sage: g.is_regular(k=6)
True
sage: g.is_vertex_transitive()                                                  # needs sage.groups
True
sage: g.line_graph().is_vertex_transitive()                                     # needs sage.groups
True
sage: g.automorphism_group().cardinality()                                      # needs sage.groups
300
sage: g.is_hamiltonian()                                                        # needs sage.numerical.mip
True

>>> from sage.all import *
>>> g = graphs.Toroidal6RegularGrid2dGraph(Integer(5),Integer(5))
>>> g.is_regular(k=Integer(6))
True
>>> g.is_vertex_transitive()                                                  # needs sage.groups
True
>>> g.line_graph().is_vertex_transitive()                                     # needs sage.groups
True
>>> g.automorphism_group().cardinality()                                      # needs sage.groups
300
>>> g.is_hamiltonian()                                                        # needs sage.numerical.mip
True

g = graphs.Toroidal6RegularGrid2dGraph(5,5)
g.is_regular(k=6)
g.is_vertex_transitive()                                                  # needs sage.groups
g.line_graph().is_vertex_transitive()                                     # needs sage.groups
g.automorphism_group().cardinality()                                      # needs sage.groups
g.is_hamiltonian()                                                        # needs sage.numerical.mip
sage.graphs.generators.basic.ToroidalGrid2dGraph(p, q)[source]

Return a toroidal 2-dimensional grid graph with \(p \times q\) nodes (\(p\) rows and \(q\) columns).

The toroidal 2-dimensional grid with parameters \(p,q\) is the 2-dimensional grid graph with identical parameters to which are added the edges \(((i, 0), (i, q - 1))\) and \(((0, i), (p - 1, i))\).

EXAMPLES:

The toroidal 2-dimensional grid is a regular graph, while the usual 2-dimensional grid is not

sage: tgrid = graphs.ToroidalGrid2dGraph(8,9)
sage: print(tgrid)
Toroidal 2D Grid Graph with parameters 8,9
sage: grid = graphs.Grid2dGraph(8,9)
sage: grid.is_regular()
False
sage: tgrid.is_regular()
True

>>> from sage.all import *
>>> tgrid = graphs.ToroidalGrid2dGraph(Integer(8),Integer(9))
>>> print(tgrid)
Toroidal 2D Grid Graph with parameters 8,9
>>> grid = graphs.Grid2dGraph(Integer(8),Integer(9))
>>> grid.is_regular()
False
>>> tgrid.is_regular()
True

tgrid = graphs.ToroidalGrid2dGraph(8,9)
print(tgrid)
grid = graphs.Grid2dGraph(8,9)
grid.is_regular()
tgrid.is_regular()