#5038: Add word path support
---------------------------+------------------------------------------------
Reporter: slabbe | Owner: slabbe
Type: defect | Status: new
Priority: major | Milestone: sage-combinat
Component: combinatorics | Keywords:
---------------------------+------------------------------------------------
This module implements word paths which belongs to Discrete Geometry seen
from Combinatorics on Words point of view. A word path is the
representation of a word
as a discrete path in a two (or more) dimensions space using a one-to-one
correspondence between the alphabet and a set of vectors called steps.
Using combinatorics on words, many problems on discrete polygons on 2d
lattice grid may be solved in linear time in length of the perimeter
(self-intersecting, area, inertia moment, etc.). For now, the goal is to
create all the classes hierarchy. Cool algorithms will come into an other
ticket.
Here are some examples taken from the documentation of the current state
of paths.py available in the sage-combinat tree.
The combinatorial class of all paths defined over three given steps:
{{{
sage: P = WordPaths('abc', steps=[(1,2), (-3,4), (0,-3)]); P
Finite Word Paths over 3 steps
}}}
Creation of a path from the combinatorial class P:
{{{
sage: p = P('abaccba'); p
Path: abaccba
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()
}}}
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
}}}
Some built-in combinatorial classes of paths:
{{{
sage: P = WordPaths('abAB', steps='square_grid'); P
Finite Word Paths on the square grid
}}}
{{{
sage: D = WordPaths('()', steps='dyck'); D
Finite Dyck paths
sage: d = D('()()()(())'); d
Path: ()()()(())
sage: d.plot()
}}}
{{{
sage: P = WordPaths('abcdef', steps='triangle_grid')
sage: p = P('babaddefadabcadefaadfafabacdefa')
sage: p.plot()
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5038>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
