Word paths¶

This module implements word paths, which is an application of Combinatorics on Words to Discrete Geometry. A word path is the representation of a word as a discrete path in a vector space using a one-to-one correspondence between the alphabet and a set of vectors called steps. Many problems surrounding 2d lattice polygons (such as questions of self-intersection, area, inertia moment, etc.) can be solved in linear time (linear in the length of the perimeter) using theory from Combinatorics on Words.

On the square grid, the encoding of a path using a four-letter alphabet (for East, North, West and South directions) is also known as the Freeman chain code [1,2] (see [3] for further reading).

AUTHORS:

• Arnaud Bergeron (2008) : Initial version, path on the square grid

• Sébastien Labbé (2009-01-14) : New classes and hierarchy, doc and functions.

EXAMPLES:

The combinatorial class of all paths defined over three given steps:

sage: P = WordPaths('abc', steps=[(1,2), (-3,4), (0,-3)]); P
Word Paths over 3 steps

>>> from sage.all import *
>>> P = WordPaths('abc', steps=[(Integer(1),Integer(2)), (-Integer(3),Integer(4)), (Integer(0),-Integer(3))]); P
Word Paths over 3 steps

P = WordPaths('abc', steps=[(1,2), (-3,4), (0,-3)]); P

This defines a one-to-one correspondence between alphabet and steps:

sage: d = P.letters_to_steps()
sage: sorted(d.items())
[('a', (1, 2)), ('b', (-3, 4)), ('c', (0, -3))]

>>> from sage.all import *
>>> d = P.letters_to_steps()
>>> sorted(d.items())
[('a', (1, 2)), ('b', (-3, 4)), ('c', (0, -3))]

d = P.letters_to_steps()
sorted(d.items())

Creation of a path from the combinatorial class P defined above:

sage: p = P('abaccba'); p
Path: abaccba

>>> from sage.all import *
>>> p = P('abaccba'); p
Path: abaccba

p = P('abaccba'); p

Many functions can be used on p: the coordinates of its trajectory, ask whether p is a closed path, plot it and many other:

sage: list(p.points())
[(0, 0), (1, 2), (-2, 6), (-1, 8), (-1, 5), (-1, 2), (-4, 6), (-3, 8)]
sage: p.is_closed()
False
sage: p.plot()                                                                      # needs sage.plot
Graphics object consisting of 3 graphics primitives

>>> from sage.all import *
>>> list(p.points())
[(0, 0), (1, 2), (-2, 6), (-1, 8), (-1, 5), (-1, 2), (-4, 6), (-3, 8)]
>>> p.is_closed()
False
>>> p.plot()                                                                      # needs sage.plot
Graphics object consisting of 3 graphics primitives

list(p.points())
p.is_closed()
p.plot()                                                                      # needs sage.plot

To obtain a list of all the available word path specific functions, use help(p):

sage: help(p)
Help on FiniteWordPath_2d_str in module sage.combinat.words.paths object:
...
Methods inherited from FiniteWordPath_2d:
...
Methods inherited from FiniteWordPath_all:
...

>>> from sage.all import *
>>> help(p)
Help on FiniteWordPath_2d_str in module sage.combinat.words.paths object:
...
Methods inherited from FiniteWordPath_2d:
...
Methods inherited from FiniteWordPath_all:
...

help(p)

Since p is a finite word, many functions from the word library are available:

sage: p.crochemore_factorization()
(a, b, a, c, c, ba)
sage: p.is_palindrome()
False
sage: p[:3]
Path: aba
sage: len(p)
7

>>> from sage.all import *
>>> p.crochemore_factorization()
(a, b, a, c, c, ba)
>>> p.is_palindrome()
False
>>> p[:Integer(3)]
Path: aba
>>> len(p)
7

p.crochemore_factorization()
p.is_palindrome()
p[:3]
len(p)

P also herits many functions from Words:

sage: P = WordPaths('rs', steps=[(1,2), (-1,4)]); P
Word Paths over 2 steps
sage: P.alphabet()
{'r', 's'}
sage: list(P.iterate_by_length(3))
[Path: rrr,
 Path: rrs,
 Path: rsr,
 Path: rss,
 Path: srr,
 Path: srs,
 Path: ssr,
 Path: sss]

>>> from sage.all import *
>>> P = WordPaths('rs', steps=[(Integer(1),Integer(2)), (-Integer(1),Integer(4))]); P
Word Paths over 2 steps
>>> P.alphabet()
{'r', 's'}
>>> list(P.iterate_by_length(Integer(3)))
[Path: rrr,
 Path: rrs,
 Path: rsr,
 Path: rss,
 Path: srr,
 Path: srs,
 Path: ssr,
 Path: sss]

P = WordPaths('rs', steps=[(1,2), (-1,4)]); P
P.alphabet()
list(P.iterate_by_length(3))

When the number of given steps is half the size of alphabet, the opposite of vectors are used:

sage: P = WordPaths('abcd', [(1,0), (0,1)])
sage: sorted(P.letters_to_steps().items())
[('a', (1, 0)), ('b', (0, 1)), ('c', (-1, 0)), ('d', (0, -1))]

>>> from sage.all import *
>>> P = WordPaths('abcd', [(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> sorted(P.letters_to_steps().items())
[('a', (1, 0)), ('b', (0, 1)), ('c', (-1, 0)), ('d', (0, -1))]

P = WordPaths('abcd', [(1,0), (0,1)])
sorted(P.letters_to_steps().items())

Some built-in combinatorial classes of paths:

sage: P = WordPaths('abAB', steps='square_grid'); P
Word Paths on the square grid

>>> from sage.all import *
>>> P = WordPaths('abAB', steps='square_grid'); P
Word Paths on the square grid

P = WordPaths('abAB', steps='square_grid'); P

sage: D = WordPaths('()', steps='dyck'); D
Finite Dyck paths
sage: d = D('()()()(())'); d
Path: ()()()(())
sage: d.plot()                                                                      # needs sage.plot
Graphics object consisting of 3 graphics primitives

>>> from sage.all import *
>>> D = WordPaths('()', steps='dyck'); D
Finite Dyck paths
>>> d = D('()()()(())'); d
Path: ()()()(())
>>> d.plot()                                                                      # needs sage.plot
Graphics object consisting of 3 graphics primitives

D = WordPaths('()', steps='dyck'); D
d = D('()()()(())'); d
d.plot()                                                                      # needs sage.plot

sage: # needs sage.rings.number_field
sage: P = WordPaths('abcdef', steps='triangle_grid')
sage: p = P('babaddefadabcadefaadfafabacdefa')
sage: p.plot()                                                                      # needs sage.plot
Graphics object consisting of 3 graphics primitives

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P = WordPaths('abcdef', steps='triangle_grid')
>>> p = P('babaddefadabcadefaadfafabacdefa')
>>> p.plot()                                                                      # needs sage.plot
Graphics object consisting of 3 graphics primitives

# needs sage.rings.number_field
P = WordPaths('abcdef', steps='triangle_grid')
p = P('babaddefadabcadefaadfafabacdefa')
p.plot()                                                                      # needs sage.plot

Vector steps may be in more than 2 dimensions:

sage: d = [(1,0,0), (0,1,0), (0,0,1)]
sage: P = WordPaths(alphabet='abc', steps=d); P
Word Paths over 3 steps
sage: p = P('abcabcabcabcaabacabcababcacbabacacabcaccbcac')
sage: p.plot()                                                                      # needs sage.plot
Graphics3d Object

>>> from sage.all import *
>>> d = [(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))]
>>> P = WordPaths(alphabet='abc', steps=d); P
Word Paths over 3 steps
>>> p = P('abcabcabcabcaabacabcababcacbabacacabcaccbcac')
>>> p.plot()                                                                      # needs sage.plot
Graphics3d Object

d = [(1,0,0), (0,1,0), (0,0,1)]
P = WordPaths(alphabet='abc', steps=d); P
p = P('abcabcabcabcaabacabcababcacbabacacabcaccbcac')
p.plot()                                                                      # needs sage.plot

sage: d = [(1,3,5,1), (-5,1,-6,0), (0,0,1,9), (4,2,-1,0)]
sage: P = WordPaths(alphabet='rstu', steps=d); P
Word Paths over 4 steps
sage: p = P('rtusuusususuturrsust'); p
Path: rtusuusususuturrsust
sage: p.end_point()
(5, 31, -26, 30)

>>> from sage.all import *
>>> d = [(Integer(1),Integer(3),Integer(5),Integer(1)), (-Integer(5),Integer(1),-Integer(6),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(9)), (Integer(4),Integer(2),-Integer(1),Integer(0))]
>>> P = WordPaths(alphabet='rstu', steps=d); P
Word Paths over 4 steps
>>> p = P('rtusuusususuturrsust'); p
Path: rtusuusususuturrsust
>>> p.end_point()
(5, 31, -26, 30)

d = [(1,3,5,1), (-5,1,-6,0), (0,0,1,9), (4,2,-1,0)]
P = WordPaths(alphabet='rstu', steps=d); P
p = P('rtusuusususuturrsust'); p
p.end_point()

sage: CubePaths = WordPaths('abcABC', steps='cube_grid'); CubePaths
Word Paths on the cube grid
sage: CubePaths('abcabaabcabAAAAA').plot()                                          # needs sage.plot
Graphics3d Object

>>> from sage.all import *
>>> CubePaths = WordPaths('abcABC', steps='cube_grid'); CubePaths
Word Paths on the cube grid
>>> CubePaths('abcabaabcabAAAAA').plot()                                          # needs sage.plot
Graphics3d Object

CubePaths = WordPaths('abcABC', steps='cube_grid'); CubePaths
CubePaths('abcabaabcabAAAAA').plot()                                          # needs sage.plot

The input data may be a str, a list, a tuple, a callable or a finite iterator:

sage: P = WordPaths([0, 1, 2, 3])
sage: P([0,1,2,3,2,1,2,3,2])
Path: 012321232
sage: P((0,1,2,3,2,1,2,3,2))
Path: 012321232
sage: P(lambda n:n%4, length=10)
Path: 0123012301
sage: P(iter([0,3,2,1]), length='finite')
Path: 0321

>>> from sage.all import *
>>> P = WordPaths([Integer(0), Integer(1), Integer(2), Integer(3)])
>>> P([Integer(0),Integer(1),Integer(2),Integer(3),Integer(2),Integer(1),Integer(2),Integer(3),Integer(2)])
Path: 012321232
>>> P((Integer(0),Integer(1),Integer(2),Integer(3),Integer(2),Integer(1),Integer(2),Integer(3),Integer(2)))
Path: 012321232
>>> P(lambda n:n%Integer(4), length=Integer(10))
Path: 0123012301
>>> P(iter([Integer(0),Integer(3),Integer(2),Integer(1)]), length='finite')
Path: 0321

P = WordPaths([0, 1, 2, 3])
P([0,1,2,3,2,1,2,3,2])
P((0,1,2,3,2,1,2,3,2))
P(lambda n:n%4, length=10)
P(iter([0,3,2,1]), length='finite')

REFERENCES:

• [1] Freeman, H.: On the encoding of arbitrary geometric configurations. IRE Trans. Electronic Computer 10 (1961) 260-268.

• [2] Freeman, H.: Boundary encoding and processing. In Lipkin, B., Rosenfeld, A., eds.: Picture Processing and Psychopictorics, Academic Press, New York (1970) 241-266.

• [3] Braquelaire, J.P., Vialard, A.: Euclidean paths: A new representation of boundary of discrete regions. Graphical Models and Image Processing 61 (1999) 16-43.

• [4] Wikipedia article Regular_tiling

• [5] Wikipedia article Dyck_word

class sage.combinat.words.paths.FiniteWordPath_2d[source]¶

Bases: FiniteWordPath_all

animate()[source]¶

Return an animation object illustrating the path growing step by step.

EXAMPLES:

Sage

sage: P = WordPaths('abAB')
sage: p = P('aaababbb')
sage: a = p.animate(); print(a)                                             # needs sage.plot
Animation with 9 frames
sage: show(a)                       # long time, optional - imagemagick, needs sage.plot
sage: show(a, delay=35, iterations=3)       # long time, optional - imagemagick, needs sage.plot

Python

>>> from sage.all import *
>>> P = WordPaths('abAB')
>>> p = P('aaababbb')
>>> a = p.animate(); print(a)                                             # needs sage.plot
Animation with 9 frames
>>> show(a)                       # long time, optional - imagemagick, needs sage.plot
>>> show(a, delay=Integer(35), iterations=Integer(3))       # long time, optional - imagemagick, needs sage.plot

Sage Live

P = WordPaths('abAB')
p = P('aaababbb')
a = p.animate(); print(a)                                             # needs sage.plot
show(a)                       # long time, optional - imagemagick, needs sage.plot
show(a, delay=35, iterations=3)       # long time, optional - imagemagick, needs sage.plot

Sage

sage: # needs sage.rings.number_field
sage: P = WordPaths('abcdef', steps='triangle')
sage: p =  P('abcdef')
sage: a = p.animate(); print(a)                                             # needs sage.plot
Animation with 8 frames
sage: show(a)                       # long time, optional - imagemagick, needs sage.plot

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P = WordPaths('abcdef', steps='triangle')
>>> p =  P('abcdef')
>>> a = p.animate(); print(a)                                             # needs sage.plot
Animation with 8 frames
>>> show(a)                       # long time, optional - imagemagick, needs sage.plot

Sage Live

# needs sage.rings.number_field
P = WordPaths('abcdef', steps='triangle')
p =  P('abcdef')
a = p.animate(); print(a)                                             # needs sage.plot
show(a)                       # long time, optional - imagemagick, needs sage.plot

If the path is closed, the plain polygon is added at the end of the animation:

Sage

sage: P = WordPaths('abAB')
sage: p = P('ababAbABABaB')
sage: a = p.animate(); print(a)                                             # needs sage.plot
Animation with 14 frames
sage: show(a)                       # long time, optional - imagemagick, needs sage.plot

Python

>>> from sage.all import *
>>> P = WordPaths('abAB')
>>> p = P('ababAbABABaB')
>>> a = p.animate(); print(a)                                             # needs sage.plot
Animation with 14 frames
>>> show(a)                       # long time, optional - imagemagick, needs sage.plot

Sage Live

P = WordPaths('abAB')
p = P('ababAbABABaB')
a = p.animate(); print(a)                                             # needs sage.plot
show(a)                       # long time, optional - imagemagick, needs sage.plot

Another example illustrating a Fibonacci tile:

Sage

sage: w = words.fibonacci_tile(2)
sage: a = w.animate(); print(a)                                             # needs sage.plot
Animation with 54 frames
sage: show(a)                       # long time, optional - imagemagick, needs sage.plot

Python

>>> from sage.all import *
>>> w = words.fibonacci_tile(Integer(2))
>>> a = w.animate(); print(a)                                             # needs sage.plot
Animation with 54 frames
>>> show(a)                       # long time, optional - imagemagick, needs sage.plot

Sage Live

w = words.fibonacci_tile(2)
a = w.animate(); print(a)                                             # needs sage.plot
show(a)                       # long time, optional - imagemagick, needs sage.plot

The first 4 Fibonacci tiles in an animation:

Sage

sage: # needs sage.plot
sage: a = words.fibonacci_tile(0).animate()
sage: b = words.fibonacci_tile(1).animate()
sage: c = words.fibonacci_tile(2).animate()
sage: d = words.fibonacci_tile(3).animate()
sage: print(a*b*c*d)
Animation with 296 frames
sage: show(a*b*c*d)                 # long time, optional - imagemagick

Python

>>> from sage.all import *
>>> # needs sage.plot
>>> a = words.fibonacci_tile(Integer(0)).animate()
>>> b = words.fibonacci_tile(Integer(1)).animate()
>>> c = words.fibonacci_tile(Integer(2)).animate()
>>> d = words.fibonacci_tile(Integer(3)).animate()
>>> print(a*b*c*d)
Animation with 296 frames
>>> show(a*b*c*d)                 # long time, optional - imagemagick

Sage Live

# needs sage.plot
a = words.fibonacci_tile(0).animate()
b = words.fibonacci_tile(1).animate()
c = words.fibonacci_tile(2).animate()
d = words.fibonacci_tile(3).animate()
print(a*b*c*d)
show(a*b*c*d)                 # long time, optional - imagemagick

Note

If ImageMagick is not installed, you will get an error message like this:

convert: not found

Error: ImageMagick does not appear to be installed. Saving an
animation to a GIF file or displaying an animation requires
ImageMagick, so please install it and try again.

See www.imagemagick.org, for example.

area()[source]¶

Return the area of a closed path.

INPUT:

• self – a closed path

EXAMPLES:

Sage

sage: P = WordPaths('abcd',steps=[(1,1),(-1,1),(-1,-1),(1,-1)])
sage: p = P('abcd')
sage: p.area()          #todo: not implemented
2

Python

>>> from sage.all import *
>>> P = WordPaths('abcd',steps=[(Integer(1),Integer(1)),(-Integer(1),Integer(1)),(-Integer(1),-Integer(1)),(Integer(1),-Integer(1))])
>>> p = P('abcd')
>>> p.area()          #todo: not implemented
2

Sage Live

P = WordPaths('abcd',steps=[(1,1),(-1,1),(-1,-1),(1,-1)])
p = P('abcd')
p.area()          #todo: not implemented

height()[source]¶

Return the height of self.

The height of a \(2d\)-path is merely the difference between the highest and the lowest \(y\)-coordinate of each points traced by it.

OUTPUT: nonnegative real number

EXAMPLES:

Sage

sage: Freeman = WordPaths('abAB')
sage: Freeman('aababaabbbAA').height()
5

Python

>>> from sage.all import *
>>> Freeman = WordPaths('abAB')
>>> Freeman('aababaabbbAA').height()
5

Sage Live

Freeman = WordPaths('abAB')
Freeman('aababaabbbAA').height()

The function is well-defined if self is not simple or close:

Sage

sage: Freeman('aabAAB').height()
1
sage: Freeman('abbABa').height()
2

Python

>>> from sage.all import *
>>> Freeman('aabAAB').height()
1
>>> Freeman('abbABa').height()
2

Sage Live

Freeman('aabAAB').height()
Freeman('abbABa').height()

This works for any \(2d\)-paths:

Sage

sage: Paths = WordPaths('ab', steps=[(1,0),(1,1)])
sage: p = Paths('abbaa')
sage: p.height()
2
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.height()
2
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')                # needs sage.rings.number_field
sage: w.height()                                                            # needs sage.rings.number_field
2.59807621135332

Python

>>> from sage.all import *
>>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(Integer(1),Integer(1))])
>>> p = Paths('abbaa')
>>> p.height()
2
>>> DyckPaths = WordPaths('ab', steps='dyck')
>>> p = DyckPaths('abaabb')
>>> p.height()
2
>>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC')                # needs sage.rings.number_field
>>> w.height()                                                            # needs sage.rings.number_field
2.59807621135332

Sage Live

Paths = WordPaths('ab', steps=[(1,0),(1,1)])
p = Paths('abbaa')
p.height()
DyckPaths = WordPaths('ab', steps='dyck')
p = DyckPaths('abaabb')
p.height()
w = WordPaths('abcABC', steps='triangle')('ababcaaBC')                # needs sage.rings.number_field
w.height()                                                            # needs sage.rings.number_field

height_vector()[source]¶

Return the height at each point.

EXAMPLES:

Sage

sage: Paths = WordPaths('ab', steps=[(1,0),(0,1)])
sage: p = Paths('abbba')
sage: p.height_vector()
[0, 0, 1, 2, 3, 3]

Python

>>> from sage.all import *
>>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(Integer(0),Integer(1))])
>>> p = Paths('abbba')
>>> p.height_vector()
[0, 0, 1, 2, 3, 3]

Sage Live

Paths = WordPaths('ab', steps=[(1,0),(0,1)])
p = Paths('abbba')
p.height_vector()

plot(pathoptions={'rgbcolor': 'red', 'thickness': 3}, fill=True, filloptions={'rgbcolor': 'red', 'alpha': 0.2}, startpoint=True, startoptions={'rgbcolor': 'red', 'pointsize': 100}, endarrow=True, arrowoptions={'rgbcolor': 'red', 'arrowsize': 20, 'width': 3}, gridlines=False, gridoptions={})[source]¶

Return a 2d Graphics illustrating the path.

INPUT:

• pathoptions – (dict, default:dict(rgbcolor=’red’,thickness=3)), options for the path drawing

• fill – boolean (default: True); if fill is True and if the path is closed, the inside is colored

• filloptions – (dict, default:dict(rgbcolor=’red’,alpha=0.2)), options for the inside filling

• startpoint – boolean (default: True); draw the start point?

• startoptions – (dict, default:dict(rgbcolor=’red’,pointsize=100)) options for the start point drawing

• endarrow – boolean (default: True); draw an arrow end at the end?

• arrowoptions – (dict, default:dict(rgbcolor=’red’,arrowsize=20, width=3)) options for the end point arrow

• gridlines – boolean (default: False); show gridlines?

• gridoptions – (dict, default: {}), options for the gridlines

EXAMPLES:

A non closed path on the square grid:

Sage

sage: P = WordPaths('abAB')
sage: P('abababAABAB').plot()                                               # needs sage.plot
Graphics object consisting of 3 graphics primitives

Python

>>> from sage.all import *
>>> P = WordPaths('abAB')
>>> P('abababAABAB').plot()                                               # needs sage.plot
Graphics object consisting of 3 graphics primitives

Sage Live

P = WordPaths('abAB')
P('abababAABAB').plot()                                               # needs sage.plot

A closed path on the square grid:

Sage

sage: P('abababAABABB').plot()                                              # needs sage.plot
Graphics object consisting of 4 graphics primitives

Python

>>> from sage.all import *
>>> P('abababAABABB').plot()                                              # needs sage.plot
Graphics object consisting of 4 graphics primitives

Sage Live

P('abababAABABB').plot()                                              # needs sage.plot

A Dyck path:

Sage

sage: P = WordPaths('()', steps='dyck')
sage: P('()()()((()))').plot()                                              # needs sage.plot
Graphics object consisting of 3 graphics primitives

Python

>>> from sage.all import *
>>> P = WordPaths('()', steps='dyck')
>>> P('()()()((()))').plot()                                              # needs sage.plot
Graphics object consisting of 3 graphics primitives

Sage Live

P = WordPaths('()', steps='dyck')
P('()()()((()))').plot()                                              # needs sage.plot

A path in the triangle grid:

Sage

sage: # needs sage.rings.number_field
sage: P = WordPaths('abcdef', steps='triangle_grid')
sage: P('abcdedededefab').plot()                                            # needs sage.plot
Graphics object consisting of 3 graphics primitives

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P = WordPaths('abcdef', steps='triangle_grid')
>>> P('abcdedededefab').plot()                                            # needs sage.plot
Graphics object consisting of 3 graphics primitives

Sage Live

# needs sage.rings.number_field
P = WordPaths('abcdef', steps='triangle_grid')
P('abcdedededefab').plot()                                            # needs sage.plot

A polygon of length 220 that tiles the plane in two ways:

Sage

sage: P = WordPaths('abAB')
sage: P('aBababAbabaBaBABaBabaBaBABAbABABaBabaBaBABaBababAbabaBaBABaBabaBaBABAbABABaBABAbAbabAbABABaBABAbABABaBabaBaBABAbABABaBABAbAbabAbABAbAbabaBababAbABAbAbabAbABABaBABAbAbabAbABAbAbabaBababAbabaBaBABaBababAbabaBababAbABAbAbab').plot()  # needs sage.plot
Graphics object consisting of 4 graphics primitives

Python

>>> from sage.all import *
>>> P = WordPaths('abAB')
>>> P('aBababAbabaBaBABaBabaBaBABAbABABaBabaBaBABaBababAbabaBaBABaBabaBaBABAbABABaBABAbAbabAbABABaBABAbABABaBabaBaBABAbABABaBABAbAbabAbABAbAbabaBababAbABAbAbabAbABABaBABAbAbabAbABAbAbabaBababAbabaBaBABaBababAbabaBababAbABAbAbab').plot()  # needs sage.plot
Graphics object consisting of 4 graphics primitives

Sage Live

P = WordPaths('abAB')
P('aBababAbabaBaBABaBabaBaBABAbABABaBabaBaBABaBababAbabaBaBABaBabaBaBABAbABABaBABAbAbabAbABABaBABAbABABaBabaBaBABAbABABaBABAbAbabAbABAbAbabaBababAbABAbAbabAbABABaBABAbAbabAbABAbAbabaBababAbabaBaBABaBababAbabaBababAbABAbAbab').plot()  # needs sage.plot

With gridlines:

Sage

sage: P('ababababab').plot(gridlines=True)                                  # needs sage.plot

Python

>>> from sage.all import *
>>> P('ababababab').plot(gridlines=True)                                  # needs sage.plot

Sage Live

P('ababababab').plot(gridlines=True)                                  # needs sage.plot

plot_directive_vector(options={'rgbcolor': 'blue'})[source]¶

Return an arrow 2d graphics that goes from the start of the path to the end.

INPUT:

• options – dictionary, default: {‘rgbcolor’: ‘blue’} graphic options for the arrow

If the start is the same as the end, a single point is returned.

EXAMPLES:

Sage

sage: P = WordPaths('abcd'); P
Word Paths on the square grid
sage: p = P('aaaccaccacacacaccccccbbdd'); p
Path: aaaccaccacacacaccccccbbdd
sage: R = p.plot() + p.plot_directive_vector()                              # needs sage.plot
sage: R.axes(False)                                                         # needs sage.plot
sage: R.set_aspect_ratio(1)                                                 # needs sage.plot
sage: R.plot()                                                              # needs sage.plot
Graphics object consisting of 4 graphics primitives

Python

>>> from sage.all import *
>>> P = WordPaths('abcd'); P
Word Paths on the square grid
>>> p = P('aaaccaccacacacaccccccbbdd'); p
Path: aaaccaccacacacaccccccbbdd
>>> R = p.plot() + p.plot_directive_vector()                              # needs sage.plot
>>> R.axes(False)                                                         # needs sage.plot
>>> R.set_aspect_ratio(Integer(1))                                                 # needs sage.plot
>>> R.plot()                                                              # needs sage.plot
Graphics object consisting of 4 graphics primitives

Sage Live

P = WordPaths('abcd'); P
p = P('aaaccaccacacacaccccccbbdd'); p
R = p.plot() + p.plot_directive_vector()                              # needs sage.plot
R.axes(False)                                                         # needs sage.plot
R.set_aspect_ratio(1)                                                 # needs sage.plot
R.plot()                                                              # needs sage.plot

width()[source]¶

Return the width of self.

The height of a \(2d\)-path is merely the difference between the rightmost and the leftmost \(x\)-coordinate of each points traced by it.

OUTPUT: nonnegative real number

EXAMPLES:

Sage

sage: Freeman = WordPaths('abAB')
sage: Freeman('aababaabbbAA').width()
5

Python

>>> from sage.all import *
>>> Freeman = WordPaths('abAB')
>>> Freeman('aababaabbbAA').width()
5

Sage Live

Freeman = WordPaths('abAB')
Freeman('aababaabbbAA').width()

The function is well-defined if self is not simple or close:

Sage

sage: Freeman('aabAAB').width()
2
sage: Freeman('abbABa').width()
1

Python

>>> from sage.all import *
>>> Freeman('aabAAB').width()
2
>>> Freeman('abbABa').width()
1

Sage Live

Freeman('aabAAB').width()
Freeman('abbABa').width()

This works for any \(2d\)-paths:

Sage

sage: Paths = WordPaths('ab', steps=[(1,0),(1,1)])
sage: p = Paths('abbaa')
sage: p.width()
5
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.width()
6
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')             # needs sage.rings.number_field
sage: w.width()                                                          # needs sage.rings.number_field
4.50000000000000

Python

>>> from sage.all import *
>>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(Integer(1),Integer(1))])
>>> p = Paths('abbaa')
>>> p.width()
5
>>> DyckPaths = WordPaths('ab', steps='dyck')
>>> p = DyckPaths('abaabb')
>>> p.width()
6
>>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC')             # needs sage.rings.number_field
>>> w.width()                                                          # needs sage.rings.number_field
4.50000000000000

Sage Live

Paths = WordPaths('ab', steps=[(1,0),(1,1)])
p = Paths('abbaa')
p.width()
DyckPaths = WordPaths('ab', steps='dyck')
p = DyckPaths('abaabb')
p.width()
w = WordPaths('abcABC', steps='triangle')('ababcaaBC')             # needs sage.rings.number_field
w.width()                                                          # needs sage.rings.number_field

width_vector()[source]¶

Return the width at each point.

EXAMPLES:

Sage

sage: Paths = WordPaths('ab', steps=[(1,0),(0,1)])
sage: p = Paths('abbba')
sage: p.width_vector()
[0, 1, 1, 1, 1, 2]

Python

>>> from sage.all import *
>>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(Integer(0),Integer(1))])
>>> p = Paths('abbba')
>>> p.width_vector()
[0, 1, 1, 1, 1, 2]

Sage Live

Paths = WordPaths('ab', steps=[(1,0),(0,1)])
p = Paths('abbba')
p.width_vector()

xmax()[source]¶

Return the maximum of the x-coordinates of the path.

EXAMPLES:

Sage

sage: P = WordPaths('0123')
sage: p = P('0101013332')
sage: p.xmax()
3

Python

>>> from sage.all import *
>>> P = WordPaths('0123')
>>> p = P('0101013332')
>>> p.xmax()
3

Sage Live

P = WordPaths('0123')
p = P('0101013332')
p.xmax()

This works for any \(2d\)-paths:

Sage

sage: Paths = WordPaths('ab', steps=[(1,-1),(-1,1)])
sage: p = Paths('ababa')
sage: p.xmax()
1
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.xmax()
6
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')                # needs sage.rings.number_field
sage: w.xmax()                                                              # needs sage.rings.number_field
4.50000000000000

Python

>>> from sage.all import *
>>> Paths = WordPaths('ab', steps=[(Integer(1),-Integer(1)),(-Integer(1),Integer(1))])
>>> p = Paths('ababa')
>>> p.xmax()
1
>>> DyckPaths = WordPaths('ab', steps='dyck')
>>> p = DyckPaths('abaabb')
>>> p.xmax()
6
>>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC')                # needs sage.rings.number_field
>>> w.xmax()                                                              # needs sage.rings.number_field
4.50000000000000

Sage Live

Paths = WordPaths('ab', steps=[(1,-1),(-1,1)])
p = Paths('ababa')
p.xmax()
DyckPaths = WordPaths('ab', steps='dyck')
p = DyckPaths('abaabb')
p.xmax()
w = WordPaths('abcABC', steps='triangle')('ababcaaBC')                # needs sage.rings.number_field
w.xmax()                                                              # needs sage.rings.number_field

xmin()[source]¶

Return the minimum of the x-coordinates of the path.

EXAMPLES:

Sage

sage: P = WordPaths('0123')
sage: p = P('0101013332')
sage: p.xmin()
0

Python

>>> from sage.all import *
>>> P = WordPaths('0123')
>>> p = P('0101013332')
>>> p.xmin()
0

Sage Live

P = WordPaths('0123')
p = P('0101013332')
p.xmin()

This works for any \(2d\)-paths:

Sage

sage: Paths = WordPaths('ab', steps=[(1,0),(-1,1)])
sage: p = Paths('abbba')
sage: p.xmin()
-2
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.xmin()
0
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')              # needs sage.rings.number_field
sage: w.xmin()                                                            # needs sage.rings.number_field
0.000000000000000

Python

>>> from sage.all import *
>>> Paths = WordPaths('ab', steps=[(Integer(1),Integer(0)),(-Integer(1),Integer(1))])
>>> p = Paths('abbba')
>>> p.xmin()
-2
>>> DyckPaths = WordPaths('ab', steps='dyck')
>>> p = DyckPaths('abaabb')
>>> p.xmin()
0
>>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC')              # needs sage.rings.number_field
>>> w.xmin()                                                            # needs sage.rings.number_field
0.000000000000000

Sage Live

Paths = WordPaths('ab', steps=[(1,0),(-1,1)])
p = Paths('abbba')
p.xmin()
DyckPaths = WordPaths('ab', steps='dyck')
p = DyckPaths('abaabb')
p.xmin()
w = WordPaths('abcABC', steps='triangle')('ababcaaBC')              # needs sage.rings.number_field
w.xmin()                                                            # needs sage.rings.number_field

ymax()[source]¶

Return the maximum of the y-coordinates of the path.

EXAMPLES:

Sage

sage: P = WordPaths('0123')
sage: p = P('0101013332')
sage: p.ymax()
3

Python

>>> from sage.all import *
>>> P = WordPaths('0123')
>>> p = P('0101013332')
>>> p.ymax()
3

Sage Live

P = WordPaths('0123')
p = P('0101013332')
p.ymax()

This works for any \(2d\)-paths:

Sage

sage: Paths = WordPaths('ab', steps=[(1,-1),(-1,1)])
sage: p = Paths('ababa')
sage: p.ymax()
0
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.ymax()
2
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')                # needs sage.rings.number_field
sage: w.ymax()                                                              # needs sage.rings.number_field
2.59807621135332

Python

>>> from sage.all import *
>>> Paths = WordPaths('ab', steps=[(Integer(1),-Integer(1)),(-Integer(1),Integer(1))])
>>> p = Paths('ababa')
>>> p.ymax()
0
>>> DyckPaths = WordPaths('ab', steps='dyck')
>>> p = DyckPaths('abaabb')
>>> p.ymax()
2
>>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC')                # needs sage.rings.number_field
>>> w.ymax()                                                              # needs sage.rings.number_field
2.59807621135332

Sage Live

Paths = WordPaths('ab', steps=[(1,-1),(-1,1)])
p = Paths('ababa')
p.ymax()
DyckPaths = WordPaths('ab', steps='dyck')
p = DyckPaths('abaabb')
p.ymax()
w = WordPaths('abcABC', steps='triangle')('ababcaaBC')                # needs sage.rings.number_field
w.ymax()                                                              # needs sage.rings.number_field

ymin()[source]¶

Return the minimum of the y-coordinates of the path.

EXAMPLES:

Sage

sage: P = WordPaths('0123')
sage: p = P('0101013332')
sage: p.ymin()
0

Python

>>> from sage.all import *
>>> P = WordPaths('0123')
>>> p = P('0101013332')
>>> p.ymin()
0

Sage Live

P = WordPaths('0123')
p = P('0101013332')
p.ymin()

This works for any \(2d\)-paths:

Sage

sage: Paths = WordPaths('ab', steps=[(1,-1),(-1,1)])
sage: p = Paths('ababa')
sage: p.ymin()
-1
sage: DyckPaths = WordPaths('ab', steps='dyck')
sage: p = DyckPaths('abaabb')
sage: p.ymin()
0
sage: w = WordPaths('abcABC', steps='triangle')('ababcaaBC')              # needs sage.rings.number_field
sage: w.ymin()                                                            # needs sage.rings.number_field
0.000000000000000

Python

>>> from sage.all import *
>>> Paths = WordPaths('ab', steps=[(Integer(1),-Integer(1)),(-Integer(1),Integer(1))])
>>> p = Paths('ababa')
>>> p.ymin()
-1
>>> DyckPaths = WordPaths('ab', steps='dyck')
>>> p = DyckPaths('abaabb')
>>> p.ymin()
0
>>> w = WordPaths('abcABC', steps='triangle')('ababcaaBC')              # needs sage.rings.number_field
>>> w.ymin()                                                            # needs sage.rings.number_field
0.000000000000000

Sage Live

Paths = WordPaths('ab', steps=[(1,-1),(-1,1)])
p = Paths('ababa')
p.ymin()
DyckPaths = WordPaths('ab', steps='dyck')
p = DyckPaths('abaabb')
p.ymin()
w = WordPaths('abcABC', steps='triangle')('ababcaaBC')              # needs sage.rings.number_field
w.ymin()                                                            # needs sage.rings.number_field

class sage.combinat.words.paths.FiniteWordPath_2d_callable(parent, callable, length=None)[source]¶

Bases: WordDatatype_callable, FiniteWordPath_2d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_2d_callable_with_caching(parent, callable, length=None)[source]¶

Bases: WordDatatype_callable_with_caching, FiniteWordPath_2d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_2d_iter(parent, iter, length=None)[source]¶

Bases: WordDatatype_iter, FiniteWordPath_2d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_2d_iter_with_caching(parent, iter, length=None)[source]¶

Bases: WordDatatype_iter_with_caching, FiniteWordPath_2d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_2d_list[source]¶

Bases: WordDatatype_list, FiniteWordPath_2d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_2d_str[source]¶

Bases: WordDatatype_str, FiniteWordPath_2d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_2d_tuple[source]¶

Bases: WordDatatype_tuple, FiniteWordPath_2d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_3d[source]¶

Bases: FiniteWordPath_all

plot(pathoptions={'rgbcolor': 'red', 'arrow_head': True, 'thickness': 3}, startpoint=True, startoptions={'rgbcolor': 'red', 'size': 10})[source]¶

INPUT:

• pathoptions – (dict, default:dict(rgbcolor=’red’,arrow_head=True, thickness=3)), options for the path drawing

• startpoint – boolean (default: True); draw the start point?

• startoptions – (dict, default:dict(rgbcolor=’red’,size=10)) options for the start point drawing

EXAMPLES:

Sage

sage: d = ( vector((1,3,2)), vector((2,-4,5)) )
sage: P = WordPaths(alphabet='ab', steps=d); P
Word Paths over 2 steps
sage: p = P('ababab'); p
Path: ababab
sage: p.plot()                                                              # needs sage.plot
Graphics3d Object

sage: P = WordPaths('abcABC', steps='cube_grid')
sage: p = P('abcabcAABBC')
sage: p.plot()                                                              # needs sage.plot
Graphics3d Object

Python

>>> from sage.all import *
>>> d = ( vector((Integer(1),Integer(3),Integer(2))), vector((Integer(2),-Integer(4),Integer(5))) )
>>> P = WordPaths(alphabet='ab', steps=d); P
Word Paths over 2 steps
>>> p = P('ababab'); p
Path: ababab
>>> p.plot()                                                              # needs sage.plot
Graphics3d Object

>>> P = WordPaths('abcABC', steps='cube_grid')
>>> p = P('abcabcAABBC')
>>> p.plot()                                                              # needs sage.plot
Graphics3d Object

Sage Live

d = ( vector((1,3,2)), vector((2,-4,5)) )
P = WordPaths(alphabet='ab', steps=d); P
p = P('ababab'); p
p.plot()                                                              # needs sage.plot
P = WordPaths('abcABC', steps='cube_grid')
p = P('abcabcAABBC')
p.plot()                                                              # needs sage.plot

class sage.combinat.words.paths.FiniteWordPath_3d_callable(parent, callable, length=None)[source]¶

Bases: WordDatatype_callable, FiniteWordPath_3d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_3d_callable_with_caching(parent, callable, length=None)[source]¶

Bases: WordDatatype_callable_with_caching, FiniteWordPath_3d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_3d_iter(parent, iter, length=None)[source]¶

Bases: WordDatatype_iter, FiniteWordPath_3d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_3d_iter_with_caching(parent, iter, length=None)[source]¶

Bases: WordDatatype_iter_with_caching, FiniteWordPath_3d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_3d_list[source]¶

Bases: WordDatatype_list, FiniteWordPath_3d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_3d_str[source]¶

Bases: WordDatatype_str, FiniteWordPath_3d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_3d_tuple[source]¶

Bases: WordDatatype_tuple, FiniteWordPath_3d, FiniteWord_class

class sage.combinat.words.paths.FiniteWordPath_all[source]¶

Bases: SageObject

directive_vector()[source]¶

Return the directive vector of self.

The directive vector is the vector starting at the start point and ending at the end point of the path self.

EXAMPLES:

Sage

sage: # needs sage.rings.number_field
sage: WordPaths('abcdef')('abababab').directive_vector()
(6, 2*sqrt3)
sage: WordPaths('abAB')('abababab').directive_vector()
(4, 4)
sage: P = WordPaths('abcABC', steps='cube_grid')
sage: P('ababababCC').directive_vector()
(4, 4, -2)
sage: WordPaths('abcdef')('abcdef').directive_vector()
(0, 0)
sage: P = WordPaths('abc', steps=[(1,3,7,9),(-4,1,0,0),(0,32,1,8)])
sage: P('abcabababacaacccbbcac').directive_vector()
(-16, 254, 63, 128)

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> WordPaths('abcdef')('abababab').directive_vector()
(6, 2*sqrt3)
>>> WordPaths('abAB')('abababab').directive_vector()
(4, 4)
>>> P = WordPaths('abcABC', steps='cube_grid')
>>> P('ababababCC').directive_vector()
(4, 4, -2)
>>> WordPaths('abcdef')('abcdef').directive_vector()
(0, 0)
>>> P = WordPaths('abc', steps=[(Integer(1),Integer(3),Integer(7),Integer(9)),(-Integer(4),Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(32),Integer(1),Integer(8))])
>>> P('abcabababacaacccbbcac').directive_vector()
(-16, 254, 63, 128)

Sage Live

# needs sage.rings.number_field
WordPaths('abcdef')('abababab').directive_vector()
WordPaths('abAB')('abababab').directive_vector()
P = WordPaths('abcABC', steps='cube_grid')
P('ababababCC').directive_vector()
WordPaths('abcdef')('abcdef').directive_vector()
P = WordPaths('abc', steps=[(1,3,7,9),(-4,1,0,0),(0,32,1,8)])
P('abcabababacaacccbbcac').directive_vector()

end_point()[source]¶

Return the end point of the path.

EXAMPLES:

Sage

sage: # needs sage.rings.number_field
sage: WordPaths('abcdef')('abababab').end_point()
(6, 2*sqrt3)
sage: WordPaths('abAB')('abababab').end_point()
(4, 4)
sage: P = WordPaths('abcABC', steps='cube_grid')
sage: P('ababababCC').end_point()
(4, 4, -2)
sage: WordPaths('abcdef')('abcdef').end_point()
(0, 0)
sage: P = WordPaths('abc', steps=[(1,3,7,9),(-4,1,0,0),(0,32,1,8)])
sage: P('abcabababacaacccbbcac').end_point()
(-16, 254, 63, 128)

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> WordPaths('abcdef')('abababab').end_point()
(6, 2*sqrt3)
>>> WordPaths('abAB')('abababab').end_point()
(4, 4)
>>> P = WordPaths('abcABC', steps='cube_grid')
>>> P('ababababCC').end_point()
(4, 4, -2)
>>> WordPaths('abcdef')('abcdef').end_point()
(0, 0)
>>> P = WordPaths('abc', steps=[(Integer(1),Integer(3),Integer(7),Integer(9)),(-Integer(4),Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(32),Integer(1),Integer(8))])
>>> P('abcabababacaacccbbcac').end_point()
(-16, 254, 63, 128)

Sage Live

# needs sage.rings.number_field
WordPaths('abcdef')('abababab').end_point()
WordPaths('abAB')('abababab').end_point()
P = WordPaths('abcABC', steps='cube_grid')
P('ababababCC').end_point()
WordPaths('abcdef')('abcdef').end_point()
P = WordPaths('abc', steps=[(1,3,7,9),(-4,1,0,0),(0,32,1,8)])
P('abcabababacaacccbbcac').end_point()

is_closed()[source]¶

Return True if the path is closed.

A path is closed if the origin and the end of the path are equal.

EXAMPLES:

Sage

sage: P = WordPaths('abcd', steps=[(1,0),(0,1),(-1,0),(0,-1)])
sage: P('abcd').is_closed()
True
sage: P('abc').is_closed()
False
sage: P().is_closed()
True
sage: P('aacacc').is_closed()
True

Python

>>> from sage.all import *
>>> P = WordPaths('abcd', steps=[(Integer(1),Integer(0)),(Integer(0),Integer(1)),(-Integer(1),Integer(0)),(Integer(0),-Integer(1))])
>>> P('abcd').is_closed()
True
>>> P('abc').is_closed()
False
>>> P().is_closed()
True
>>> P('aacacc').is_closed()
True

Sage Live

P = WordPaths('abcd', steps=[(1,0),(0,1),(-1,0),(0,-1)])
P('abcd').is_closed()
P('abc').is_closed()
P().is_closed()
P('aacacc').is_closed()

is_simple()[source]¶

Return True if the path is simple.

A path is simple if all its points are distinct.

If the path is closed, the last point is not considered.

EXAMPLES:

Sage

sage: # needs sage.rings.number_field
sage: P = WordPaths('abcdef', steps='triangle_grid'); P
Word Paths on the triangle grid
sage: P('abc').is_simple()
True
sage: P('abcde').is_simple()
True
sage: P('abcdef').is_simple()
True
sage: P('ad').is_simple()
True
sage: P('aabdee').is_simple()
False

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P = WordPaths('abcdef', steps='triangle_grid'); P
Word Paths on the triangle grid
>>> P('abc').is_simple()
True
>>> P('abcde').is_simple()
True
>>> P('abcdef').is_simple()
True
>>> P('ad').is_simple()
True
>>> P('aabdee').is_simple()
False

Sage Live

# needs sage.rings.number_field
P = WordPaths('abcdef', steps='triangle_grid'); P
P('abc').is_simple()
P('abcde').is_simple()
P('abcdef').is_simple()
P('ad').is_simple()
P('aabdee').is_simple()

is_tangent()[source]¶

The is_tangent() method, which is implemented for words, has an extended meaning for word paths, which is not implemented yet.

AUTHOR:

• Thierry Monteil

plot_projection(v=None, letters=None, color=None, ring=None, size=12, kind='right')[source]¶

Return an image of the projection of the successive points of the path into the space orthogonal to the given vector.

INPUT:

• self – a word path in a 3 or 4 dimension vector space

• v – vector (default: None); if None, the directive vector (i.e. the end point minus starting point) of the path is considered.

• letters – iterable (default: None); of the letters to be projected. If None, then all the letters are considered.

• color – dictionary (default: None); of the letters mapped to colors. If None, automatic colors are chosen.

• ring – ring (default: None); where to do the computations. If None, RealField(53) is used.

• size – number (default: 12); size of the points

• kind – string (default: 'right'); either 'right' or 'left'. The color of a letter is given to the projected prefix to the right or the left of the letter.

OUTPUT: 2d or 3d Graphic object

EXAMPLES:

The Rauzy fractal:

Sage

sage: # needs sage.rings.number_field
sage: s = WordMorphism('1->12,2->13,3->1')
sage: D = s.fixed_point('1')
sage: v = s.pisot_eigenvector_right()
sage: P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
sage: w = P(D[:200])
sage: w.plot_projection(v)  # long time (2s)
Graphics object consisting of 200 graphics primitives

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> s = WordMorphism('1->12,2->13,3->1')
>>> D = s.fixed_point('1')
>>> v = s.pisot_eigenvector_right()
>>> P = WordPaths('123',[(Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0)),(Integer(0),Integer(0),Integer(1))])
>>> w = P(D[:Integer(200)])
>>> w.plot_projection(v)  # long time (2s)
Graphics object consisting of 200 graphics primitives

Sage Live

# needs sage.rings.number_field
s = WordMorphism('1->12,2->13,3->1')
D = s.fixed_point('1')
v = s.pisot_eigenvector_right()
P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
w = P(D[:200])
w.plot_projection(v)  # long time (2s)

In this case, the abelianized vector doesn’t give a good projection:

Sage

sage: w.plot_projection()  # long time (2s)                                 # needs sage.rings.number_field
Graphics object consisting of 200 graphics primitives

Python

>>> from sage.all import *
>>> w.plot_projection()  # long time (2s)                                 # needs sage.rings.number_field
Graphics object consisting of 200 graphics primitives

Sage Live

w.plot_projection()  # long time (2s)                                 # needs sage.rings.number_field

You can project only the letters you want:

Sage

sage: w.plot_projection(v, letters='12')  # long time (2s)                  # needs sage.rings.number_field
Graphics object consisting of 168 graphics primitives

Python

>>> from sage.all import *
>>> w.plot_projection(v, letters='12')  # long time (2s)                  # needs sage.rings.number_field
Graphics object consisting of 168 graphics primitives

Sage Live

w.plot_projection(v, letters='12')  # long time (2s)                  # needs sage.rings.number_field

You can increase or decrease the precision of the computations by changing the ring of the projection matrix:

Sage

sage: w.plot_projection(v, ring=RealField(20))  # long time (2s)            # needs sage.rings.number_field
Graphics object consisting of 200 graphics primitives

Python

>>> from sage.all import *
>>> w.plot_projection(v, ring=RealField(Integer(20)))  # long time (2s)            # needs sage.rings.number_field
Graphics object consisting of 200 graphics primitives

Sage Live

w.plot_projection(v, ring=RealField(20))  # long time (2s)            # needs sage.rings.number_field

You can change the size of the points:

Sage

sage: w.plot_projection(v, size=30)  # long time (2s)                       # needs sage.rings.number_field
Graphics object consisting of 200 graphics primitives

Python

>>> from sage.all import *
>>> w.plot_projection(v, size=Integer(30))  # long time (2s)                       # needs sage.rings.number_field
Graphics object consisting of 200 graphics primitives

Sage Live

w.plot_projection(v, size=30)  # long time (2s)                       # needs sage.rings.number_field

You can assign the color of a letter to the projected prefix to the right or the left of the letter:

Sage

sage: w.plot_projection(v, kind='left')  # long time (2s)                   # needs sage.rings.number_field
Graphics object consisting of 200 graphics primitives

Python

>>> from sage.all import *
>>> w.plot_projection(v, kind='left')  # long time (2s)                   # needs sage.rings.number_field
Graphics object consisting of 200 graphics primitives

Sage Live

w.plot_projection(v, kind='left')  # long time (2s)                   # needs sage.rings.number_field

To remove the axis, do like this:

Sage

sage: # needs sage.rings.number_field
sage: r = w.plot_projection(v)                                              # needs sage.plot
sage: r.axes(False)                                                         # needs sage.plot
sage: r                             # long time (2s)                        # needs sage.plot
Graphics object consisting of 200 graphics primitives

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> r = w.plot_projection(v)                                              # needs sage.plot
>>> r.axes(False)                                                         # needs sage.plot
>>> r                             # long time (2s)                        # needs sage.plot
Graphics object consisting of 200 graphics primitives

Sage Live

# needs sage.rings.number_field
r = w.plot_projection(v)                                              # needs sage.plot
r.axes(False)                                                         # needs sage.plot
r                             # long time (2s)                        # needs sage.plot

You can assign different colors to each letter:

Sage

sage: # needs sage.rings.number_field
sage: color = {'1': 'purple', '2': (.2,.3,.4), '3': 'magenta'}
sage: w.plot_projection(v, color=color)     # long time (2s)                # needs sage.plot
Graphics object consisting of 200 graphics primitives

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> color = {'1': 'purple', '2': (RealNumber('.2'),RealNumber('.3'),RealNumber('.4')), '3': 'magenta'}
>>> w.plot_projection(v, color=color)     # long time (2s)                # needs sage.plot
Graphics object consisting of 200 graphics primitives

Sage Live

# needs sage.rings.number_field
color = {'1': 'purple', '2': (.2,.3,.4), '3': 'magenta'}
w.plot_projection(v, color=color)     # long time (2s)                # needs sage.plot

The 3d-Rauzy fractal:

Sage

sage: # needs sage.rings.number_field
sage: s = WordMorphism('1->12,2->13,3->14,4->1')
sage: D = s.fixed_point('1')
sage: v = s.pisot_eigenvector_right()
sage: P = WordPaths('1234',[(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)])
sage: w = P(D[:200])
sage: w.plot_projection(v)                                                  # needs sage.plot
Graphics3d Object

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> s = WordMorphism('1->12,2->13,3->14,4->1')
>>> D = s.fixed_point('1')
>>> v = s.pisot_eigenvector_right()
>>> P = WordPaths('1234',[(Integer(1),Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(0),Integer(1))])
>>> w = P(D[:Integer(200)])
>>> w.plot_projection(v)                                                  # needs sage.plot
Graphics3d Object

Sage Live

# needs sage.rings.number_field
s = WordMorphism('1->12,2->13,3->14,4->1')
D = s.fixed_point('1')
v = s.pisot_eigenvector_right()
P = WordPaths('1234',[(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)])
w = P(D[:200])
w.plot_projection(v)                                                  # needs sage.plot

The dimension of vector space of the parent must be 3 or 4:

Sage

sage: # needs sage.rings.number_field
sage: P = WordPaths('ab', [(1, 0), (0, 1)])
sage: p = P('aabbabbab')
sage: p.plot_projection()                                                   # needs sage.plot
Traceback (most recent call last):
...
TypeError: The dimension of the vector space (=2) must be 3 or 4

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P = WordPaths('ab', [(Integer(1), Integer(0)), (Integer(0), Integer(1))])
>>> p = P('aabbabbab')
>>> p.plot_projection()                                                   # needs sage.plot
Traceback (most recent call last):
...
TypeError: The dimension of the vector space (=2) must be 3 or 4

Sage Live

# needs sage.rings.number_field
P = WordPaths('ab', [(1, 0), (0, 1)])
p = P('aabbabbab')
p.plot_projection()                                                   # needs sage.plot

points(include_last=True)[source]¶

Return an iterator yielding a list of points used to draw the path represented by this word.

INPUT:

• include_last – boolean (default: True); whether to include the last point

EXAMPLES:

A simple closed square:

Sage

sage: P = WordPaths('abAB')
sage: list(P('abAB').points())
[(0, 0), (1, 0), (1, 1), (0, 1), (0, 0)]

Python

>>> from sage.all import *
>>> P = WordPaths('abAB')
>>> list(P('abAB').points())
[(0, 0), (1, 0), (1, 1), (0, 1), (0, 0)]

Sage Live

P = WordPaths('abAB')
list(P('abAB').points())

A simple closed square without the last point:

Sage

sage: list(P('abAB').points(include_last=False))
[(0, 0), (1, 0), (1, 1), (0, 1)]

Python

>>> from sage.all import *
>>> list(P('abAB').points(include_last=False))
[(0, 0), (1, 0), (1, 1), (0, 1)]

Sage Live

list(P('abAB').points(include_last=False))

Sage

sage: list(P('abaB').points())
[(0, 0), (1, 0), (1, 1), (2, 1), (2, 0)]

Python

>>> from sage.all import *
>>> list(P('abaB').points())
[(0, 0), (1, 0), (1, 1), (2, 1), (2, 0)]

Sage Live

list(P('abaB').points())

projected_path(v=None, ring=None)[source]¶

Return the path projected into the space orthogonal to the given vector.

INPUT:

• v – vector (default: None); if None, the directive vector (i.e. the end point minus starting point) of the path is considered.

• ring – ring (default: None); where to do the computations. If None, RealField(53) is used.

OUTPUT: word path

EXAMPLES:

The projected path of the tribonacci word:

Sage

sage: # needs sage.rings.number_field
sage: s = WordMorphism('1->12,2->13,3->1')
sage: D = s.fixed_point('1')
sage: v = s.pisot_eigenvector_right()
sage: P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
sage: w = P(D[:1000])
sage: p = w.projected_path(v)
sage: p
Path: 1213121121312121312112131213121121312121...
sage: p[:20].plot()                                                         # needs sage.plot
Graphics object consisting of 3 graphics primitives

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> s = WordMorphism('1->12,2->13,3->1')
>>> D = s.fixed_point('1')
>>> v = s.pisot_eigenvector_right()
>>> P = WordPaths('123',[(Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0)),(Integer(0),Integer(0),Integer(1))])
>>> w = P(D[:Integer(1000)])
>>> p = w.projected_path(v)
>>> p
Path: 1213121121312121312112131213121121312121...
>>> p[:Integer(20)].plot()                                                         # needs sage.plot
Graphics object consisting of 3 graphics primitives

Sage Live

# needs sage.rings.number_field
s = WordMorphism('1->12,2->13,3->1')
D = s.fixed_point('1')
v = s.pisot_eigenvector_right()
P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
w = P(D[:1000])
p = w.projected_path(v)
p
p[:20].plot()                                                         # needs sage.plot

The ring argument allows to change the precision of the projected steps:

Sage

sage: # needs sage.rings.number_field
sage: p = w.projected_path(v, RealField(10))
sage: p
Path: 1213121121312121312112131213121121312121...
sage: p.parent().letters_to_steps()
{'1': (-0.53, 0.00), '2': (0.75, -0.48), '3': (0.41, 0.88)}

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> p = w.projected_path(v, RealField(Integer(10)))
>>> p
Path: 1213121121312121312112131213121121312121...
>>> p.parent().letters_to_steps()
{'1': (-0.53, 0.00), '2': (0.75, -0.48), '3': (0.41, 0.88)}

Sage Live

# needs sage.rings.number_field
p = w.projected_path(v, RealField(10))
p
p.parent().letters_to_steps()

projected_point_iterator(v=None, ring=None)[source]¶

Return an iterator of the projection of the orbit points of the path into the space orthogonal to the given vector.

INPUT:

• v – vector (default: None); if None, the directive vector (i.e. the end point minus starting point) of the path is considered

• ring – ring (default: None); where to do the computations. If None, RealField(53) is used.

OUTPUT: iterator of points

EXAMPLES:

Projected points of the Rauzy fractal:

Sage

sage: # needs sage.rings.number_field
sage: s = WordMorphism('1->12,2->13,3->1')
sage: D = s.fixed_point('1')
sage: v = s.pisot_eigenvector_right()
sage: P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
sage: w = P(D[:200])
sage: it = w.projected_point_iterator(v)
sage: for i in range(6): next(it)
(0.000000000000000, 0.000000000000000)
(-0.526233343362516, 0.000000000000000)
(0.220830337618112, -0.477656250512816)
(-0.305403005744404, -0.477656250512816)
(0.100767309386062, 0.400890564600664)
(-0.425466033976454, 0.400890564600664)

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> s = WordMorphism('1->12,2->13,3->1')
>>> D = s.fixed_point('1')
>>> v = s.pisot_eigenvector_right()
>>> P = WordPaths('123',[(Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0)),(Integer(0),Integer(0),Integer(1))])
>>> w = P(D[:Integer(200)])
>>> it = w.projected_point_iterator(v)
>>> for i in range(Integer(6)): next(it)
(0.000000000000000, 0.000000000000000)
(-0.526233343362516, 0.000000000000000)
(0.220830337618112, -0.477656250512816)
(-0.305403005744404, -0.477656250512816)
(0.100767309386062, 0.400890564600664)
(-0.425466033976454, 0.400890564600664)

Sage Live

# needs sage.rings.number_field
s = WordMorphism('1->12,2->13,3->1')
D = s.fixed_point('1')
v = s.pisot_eigenvector_right()
P = WordPaths('123',[(1,0,0),(0,1,0),(0,0,1)])
w = P(D[:200])
it = w.projected_point_iterator(v)
for i in range(6): next(it)

Projected points of a 2d path:

Sage

sage: P = WordPaths('ab','ne')
sage: p = P('aabbabbab')
sage: it = p.projected_point_iterator(ring=RealField(20))
sage: for i in range(8): next(it)
(0.00000)
(0.78087)
(1.5617)
(0.93704)
(0.31235)
(1.0932)
(0.46852)
(-0.15617)

Python

>>> from sage.all import *
>>> P = WordPaths('ab','ne')
>>> p = P('aabbabbab')
>>> it = p.projected_point_iterator(ring=RealField(Integer(20)))
>>> for i in range(Integer(8)): next(it)
(0.00000)
(0.78087)
(1.5617)
(0.93704)
(0.31235)
(1.0932)
(0.46852)
(-0.15617)

Sage Live

P = WordPaths('ab','ne')
p = P('aabbabbab')
it = p.projected_point_iterator(ring=RealField(20))
for i in range(8): next(it)

start_point()[source]¶

Return the starting point of self.

OUTPUT: vector

EXAMPLES:

Sage

sage: # needs sage.rings.number_field
sage: WordPaths('abcdef')('abcdef').start_point()
(0, 0)
sage: WordPaths('abcdef', steps='cube_grid')('abcdef').start_point()
(0, 0, 0)
sage: P = WordPaths('ab', steps=[(1,0,0,0),(0,1,0,0)])
sage: P('abbba').start_point()
(0, 0, 0, 0)

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> WordPaths('abcdef')('abcdef').start_point()
(0, 0)
>>> WordPaths('abcdef', steps='cube_grid')('abcdef').start_point()
(0, 0, 0)
>>> P = WordPaths('ab', steps=[(Integer(1),Integer(0),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0),Integer(0))])
>>> P('abbba').start_point()
(0, 0, 0, 0)

Sage Live

# needs sage.rings.number_field
WordPaths('abcdef')('abcdef').start_point()
WordPaths('abcdef', steps='cube_grid')('abcdef').start_point()
P = WordPaths('ab', steps=[(1,0,0,0),(0,1,0,0)])
P('abbba').start_point()

tikz_trajectory()[source]¶

Return the trajectory of self as a tikz string.

EXAMPLES:

Sage

sage: # needs sage.rings.number_field
sage: P = WordPaths('abcdef')
sage: p = P('abcde')
sage: p.tikz_trajectory()
'(0.000, 0.000) -- (1.00, 0.000) -- (1.50, 0.866) -- (1.00, 1.73) -- (0.000, 1.73) -- (-0.500, 0.866)'

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P = WordPaths('abcdef')
>>> p = P('abcde')
>>> p.tikz_trajectory()
'(0.000, 0.000) -- (1.00, 0.000) -- (1.50, 0.866) -- (1.00, 1.73) -- (0.000, 1.73) -- (-0.500, 0.866)'

Sage Live

# needs sage.rings.number_field
P = WordPaths('abcdef')
p = P('abcde')
p.tikz_trajectory()