Quiver Paths#
- sage.quivers.paths.NewQuiverPath(Q, start, end, biseq_data)#
Return a new quiver path for given defining data.
INPUT:
Q
, the path semigroup of a quiverstart
, an integer, the label of the startpointend
, an integer, the label of the endpointbiseq_data
, a tuple formed byA 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#
Bases:
MonoidElement
Class for paths in a quiver.
A path is given by two vertices,
start
andend
, and a finite (possibly empty) list of edges \(e_1, e_2, \ldots, e_n\) such that the initial vertex of \(e_1\) isstart
, the final vertex of \(e_i\) is the initial vertex of \(e_{i+1}\), and the final vertex of \(e_n\) isend
. In the case where no edges are specified, we must havestart = 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
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
The
*
operator is concatenation of paths. If the two paths do not compose, its result isNone
: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
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
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) []
There are methods giving the initial and terminal vertex of a path:
sage: p.initial_vertex() 1 sage: p.terminal_vertex() 3
- complement(subpath)#
Return a pair
(a,b)
of paths s.t.self = a*subpath*b
, or(None, None)
ifsubpath
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)
- degree()#
Return the length of the path.
length()
anddegree()
are aliases
- gcd(P)#
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 thatself = C1*G
andP = 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)
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)
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)
- has_prefix(subpath)#
Tells whether this path starts with a given sub-path.
INPUT:
subpath
, a path in the same path semigroup as this path.OUTPUT:
0
or1
, which stands forFalse
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
- has_subpath(subpath)#
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
- initial_vertex()#
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
- length()#
Return the length of the path.
length()
anddegree()
are aliases
- reversal()#
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
- terminal_vertex()#
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