Quiver Paths#

sage.quivers.paths.NewQuiverPath(Q, start, end, biseq_data)[source]#

Return a new quiver path for given defining data.

INPUT:

  • Q, the path semigroup of a quiver

  • start, an integer, the label of the startpoint

  • end, an integer, the label of the endpoint

  • biseq_data, a tuple formed by

    • A string, encoding a bitmap representing the path as integer at base \(32\),

    • the number of bits used to store the path,

    • the number of bits used to store a single item

    • the number of items in the path.

class sage.quivers.paths.QuiverPath[source]#

Bases: MonoidElement

Class for paths in a quiver.

A path is given by two vertices, start and end, and a finite (possibly empty) list of edges \(e_1, e_2, \ldots, e_n\) such that the initial vertex of \(e_1\) is start, the final vertex of \(e_i\) is the initial vertex of \(e_{i+1}\), and the final vertex of \(e_n\) is end. In the case where no edges are specified, we must have start = end and the path is called the trivial path at the given vertex.

Note

Do not use this constructor directly! Instead, pass the input to the path semigroup that shall be the parent of this path.

EXAMPLES:

Specify a path by giving a list of edges:

sage: Q = DiGraph({1:{2:['a','d'], 3:['e']}, 2:{3:['b']}, 3:{1:['f'], 4:['c']}})
sage: F = Q.path_semigroup()
sage: p = F([(1, 2, 'a'), (2, 3, 'b')])
sage: p
a*b

>>> from sage.all import *
>>> Q = DiGraph({Integer(1):{Integer(2):['a','d'], Integer(3):['e']}, Integer(2):{Integer(3):['b']}, Integer(3):{Integer(1):['f'], Integer(4):['c']}})
>>> F = Q.path_semigroup()
>>> p = F([(Integer(1), Integer(2), 'a'), (Integer(2), Integer(3), 'b')])
>>> p
a*b

Paths are not unique, but different representations of “the same” path yield equal paths:

sage: q = F([(1, 1)]) * F([(1, 2, 'a'), (2, 3, 'b')]) * F([(3, 3)])
sage: p is q
False
sage: p == q
True

>>> from sage.all import *
>>> q = F([(Integer(1), Integer(1))]) * F([(Integer(1), Integer(2), 'a'), (Integer(2), Integer(3), 'b')]) * F([(Integer(3), Integer(3))])
>>> p is q
False
>>> p == q
True

The * operator is concatenation of paths. If the two paths do not compose, its result is None:

sage: print(p*q)
None
sage: p*F([(3, 4, 'c')])
a*b*c
sage: F([(2,3,'b'), (3,1,'f')])*p
b*f*a*b

>>> from sage.all import *
>>> print(p*q)
None
>>> p*F([(Integer(3), Integer(4), 'c')])
a*b*c
>>> F([(Integer(2),Integer(3),'b'), (Integer(3),Integer(1),'f')])*p
b*f*a*b

The length of a path is the number of edges in that path. Trivial paths are therefore length-\(0\):

sage: len(p)
2
sage: triv = F([(1, 1)])
sage: len(triv)
0

>>> from sage.all import *
>>> len(p)
2
>>> triv = F([(Integer(1), Integer(1))])
>>> len(triv)
0

List index and slice notation can be used to access the edges in a path. QuiverPaths can also be iterated over. Trivial paths have no elements:

sage: for x in p: print(x)
(1, 2, 'a')
(2, 3, 'b')
sage: list(triv)
[]

>>> from sage.all import *
>>> for x in p: print(x)
(1, 2, 'a')
(2, 3, 'b')
>>> list(triv)
[]

There are methods giving the initial and terminal vertex of a path:

sage: p.initial_vertex()
1
sage: p.terminal_vertex()
3

>>> from sage.all import *
>>> p.initial_vertex()
1
>>> p.terminal_vertex()
3
complement(subpath)[source]#

Return a pair (a,b) of paths s.t. self = a*subpath*b, or (None, None) if subpath is not a subpath of this path.

Note

a is chosen of minimal length.

EXAMPLES:

sage: S = DiGraph({1:{1:['a','b','c','d']}}).path_semigroup()
sage: S.inject_variables()
Defining e_1, a, b, c, d
sage: (b*c*a*d*b*a*d*d).complement(a*d)
(b*c, b*a*d*d)
sage: (b*c*a*d*b).complement(a*c)
(None, None)

>>> from sage.all import *
>>> S = DiGraph({Integer(1):{Integer(1):['a','b','c','d']}}).path_semigroup()
>>> S.inject_variables()
Defining e_1, a, b, c, d
>>> (b*c*a*d*b*a*d*d).complement(a*d)
(b*c, b*a*d*d)
>>> (b*c*a*d*b).complement(a*c)
(None, None)
degree()[source]#

Return the length of the path.

length() and degree() are aliases

gcd(P)[source]#

Greatest common divisor of two quiver paths, with co-factors.

For paths, by “greatest common divisor”, we mean the largest terminal segment of the first path that is an initial segment of the second path.

INPUT:

A QuiverPath P

OUTPUT:

  • QuiverPath`s ``(C1,G,C2)` such that self = C1*G and P = G*C2, or

  • (None, None, None), if the paths do not overlap (or belong to different quivers).

EXAMPLES:

sage: Q = DiGraph({1:{2:['a']}, 2:{1:['b'], 3:['c']}, 3:{1:['d']}}).path_semigroup()
sage: p1 = Q(['c','d','a','b','a','c','d'])
sage: p1
c*d*a*b*a*c*d
sage: p2 = Q(['a','b','a','c','d','a','c','d','a','b'])
sage: p2
a*b*a*c*d*a*c*d*a*b
sage: S1, G, S2 = p1.gcd(p2)
sage: S1, G, S2
(c*d, a*b*a*c*d, a*c*d*a*b)
sage: S1*G == p1
True
sage: G*S2 == p2
True
sage: p2.gcd(p1)
(a*b*a*c*d*a, c*d*a*b, a*c*d)

>>> from sage.all import *
>>> Q = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(1):['b'], Integer(3):['c']}, Integer(3):{Integer(1):['d']}}).path_semigroup()
>>> p1 = Q(['c','d','a','b','a','c','d'])
>>> p1
c*d*a*b*a*c*d
>>> p2 = Q(['a','b','a','c','d','a','c','d','a','b'])
>>> p2
a*b*a*c*d*a*c*d*a*b
>>> S1, G, S2 = p1.gcd(p2)
>>> S1, G, S2
(c*d, a*b*a*c*d, a*c*d*a*b)
>>> S1*G == p1
True
>>> G*S2 == p2
True
>>> p2.gcd(p1)
(a*b*a*c*d*a, c*d*a*b, a*c*d)

We test that a full overlap is detected:

sage: p2.gcd(p2)
(e_1, a*b*a*c*d*a*c*d*a*b, e_1)

>>> from sage.all import *
>>> p2.gcd(p2)
(e_1, a*b*a*c*d*a*c*d*a*b, e_1)

The absence of an overlap is detected:

sage: p2[2:-1]
a*c*d*a*c*d*a
sage: p2[1:]
b*a*c*d*a*c*d*a*b
sage: print(p2[2:-1].gcd(p2[1:]))
(None, None, None)

>>> from sage.all import *
>>> p2[Integer(2):-Integer(1)]
a*c*d*a*c*d*a
>>> p2[Integer(1):]
b*a*c*d*a*c*d*a*b
>>> print(p2[Integer(2):-Integer(1)].gcd(p2[Integer(1):]))
(None, None, None)
has_prefix(subpath)[source]#

Tells whether this path starts with a given sub-path.

INPUT:

subpath, a path in the same path semigroup as this path.

OUTPUT:

0 or 1, which stands for False resp. True.

EXAMPLES:

sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']}, 2:{0:['e'],2:['f']}}).path_semigroup()
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: (c*b*e*a).has_prefix(b*e)
0
sage: (c*b*e*a).has_prefix(c*b)
1
sage: (c*b*e*a).has_prefix(e_1)
1
sage: (c*b*e*a).has_prefix(e_2)
0

>>> from sage.all import *
>>> S = DiGraph({Integer(0):{Integer(1):['a'], Integer(2):['b']}, Integer(1):{Integer(0):['c'], Integer(1):['d']}, Integer(2):{Integer(0):['e'],Integer(2):['f']}}).path_semigroup()
>>> S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
>>> (c*b*e*a).has_prefix(b*e)
0
>>> (c*b*e*a).has_prefix(c*b)
1
>>> (c*b*e*a).has_prefix(e_1)
1
>>> (c*b*e*a).has_prefix(e_2)
0
has_subpath(subpath)[source]#

Tells whether this path contains a given sub-path.

INPUT:

subpath, a path of positive length in the same path semigroup as this path.

EXAMPLES:

sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']}, 2:{0:['e'],2:['f']}}).path_semigroup()
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: (c*b*e*a).has_subpath(b*e)
1
sage: (c*b*e*a).has_subpath(b*f)
0
sage: (c*b*e*a).has_subpath(e_1)
Traceback (most recent call last):
...
ValueError: we only consider sub-paths of positive length
sage: (c*b*e*a).has_subpath(None)
Traceback (most recent call last):
...
ValueError: the given sub-path is empty

>>> from sage.all import *
>>> S = DiGraph({Integer(0):{Integer(1):['a'], Integer(2):['b']}, Integer(1):{Integer(0):['c'], Integer(1):['d']}, Integer(2):{Integer(0):['e'],Integer(2):['f']}}).path_semigroup()
>>> S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
>>> (c*b*e*a).has_subpath(b*e)
1
>>> (c*b*e*a).has_subpath(b*f)
0
>>> (c*b*e*a).has_subpath(e_1)
Traceback (most recent call last):
...
ValueError: we only consider sub-paths of positive length
>>> (c*b*e*a).has_subpath(None)
Traceback (most recent call last):
...
ValueError: the given sub-path is empty
initial_vertex()[source]#

Return the initial vertex of the path.

OUTPUT:

  • integer, the label of the initial vertex

EXAMPLES:

sage: Q = DiGraph({1:{2:['a']}, 2:{3:['b']}}).path_semigroup()
sage: y = Q([(1, 2, 'a'), (2, 3, 'b')])
sage: y.initial_vertex()
1

>>> from sage.all import *
>>> Q = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b']}}).path_semigroup()
>>> y = Q([(Integer(1), Integer(2), 'a'), (Integer(2), Integer(3), 'b')])
>>> y.initial_vertex()
1
length()[source]#

Return the length of the path.

length() and degree() are aliases

reversal()[source]#

Return the path along the same edges in reverse order in the opposite quiver.

EXAMPLES:

sage: Q = DiGraph({1:{2:['a']}, 2:{3:['b']}, 3:{4:['c'], 1:['d']}}).path_semigroup()
sage: p = Q([(1, 2, 'a'), (2, 3, 'b'), (3, 1, 'd'), (1, 2, 'a'), (2, 3, 'b'), (3, 4, 'c')])
sage: p
a*b*d*a*b*c
sage: p.reversal()
c*b*a*d*b*a
sage: e = Q.idempotents()[0]
sage: e
e_1
sage: e.reversal()
e_1

>>> from sage.all import *
>>> Q = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b']}, Integer(3):{Integer(4):['c'], Integer(1):['d']}}).path_semigroup()
>>> p = Q([(Integer(1), Integer(2), 'a'), (Integer(2), Integer(3), 'b'), (Integer(3), Integer(1), 'd'), (Integer(1), Integer(2), 'a'), (Integer(2), Integer(3), 'b'), (Integer(3), Integer(4), 'c')])
>>> p
a*b*d*a*b*c
>>> p.reversal()
c*b*a*d*b*a
>>> e = Q.idempotents()[Integer(0)]
>>> e
e_1
>>> e.reversal()
e_1
terminal_vertex()[source]#

Return the terminal vertex of the path.

OUTPUT:

  • integer, the label of the terminal vertex

EXAMPLES:

sage: Q = DiGraph({1:{2:['a']}, 2:{3:['b']}}).path_semigroup()
sage: y = Q([(1, 2, 'a'), (2, 3, 'b')])
sage: y.terminal_vertex()
3

>>> from sage.all import *
>>> Q = DiGraph({Integer(1):{Integer(2):['a']}, Integer(2):{Integer(3):['b']}}).path_semigroup()
>>> y = Q([(Integer(1), Integer(2), 'a'), (Integer(2), Integer(3), 'b')])
>>> y.terminal_vertex()
3