combinat::graphPaths – paths in a directed graph with labelled arrows
combinat::graphPaths(graph) provides methods for counting, listing, and manipulating paths in the directed graph graph with no circuits.
→ Examples
Details:
-
A directed graph 
is the data of two disjoint sets 
(the set of vertices) and 
(the set of arrows) together with two maps 
(the source map) and 
(the target map). If 
is an arrow, the vertex 
(resp. 
) is called the source (resp. the target) of 
. Each arrow is here identified to its label.
-
If 
is an directed graph, a path in 
is a sequence 
of 
arrows such that the source of the arrow 
is equal to the target of 
for each 
. The path is then denoted by 
, its source (resp. target) is the source of 
(resp. of 
) and its length is 
. For each vertex 
we add a stationnary path (considered as an empty sequence of arrows) 
with source and target equal to 
and with length 
.
-
Assume that 
is a directed graph. If 
and 
are two paths in 
, the concatenation 
of 
and 
is defined when the source 
is equal to the target of 
. The path 
is then given by concatenating the sequence of arrows of 
with the one of 
.
-
Let 
be a directed graph and assume that the vertices of 
are ordered: 
, then the adjacency matrix is the 
matrix 
such that 
is equal to the number of arrows of 
with source 
and target 
.
-
A directed graph is encoded by a list graph with two elements. The first element graph[1] of graph is the number of vertices of the graph. We always assume that the vertices are 1,2,...,graph[1]. The second element graph[2] of graph is a table which assigns to each arrow a list containing its source and its target.
-
If graph encodes a directed graph 
, the path 
in 
(with 
and 
an arrow for each 
) with source x and target y is encoded by the list [y, alpha[n],..., alpha[1], x]. In particular, the stationnary path at the vertex x is encoded by [x, x].
-
If graph is a directed graph, then combinat::graphPaths(graph) represents the combinatorial class of the paths in this graphi graph, also called here the ambient graph.
Entries
|
"domtype"
|
The MuPAD domain used to represent paths: DOM_LIST
|
isA – tests if an object is a path in the given graph
combinat::graphPaths::isA(any type p)
Returns TRUE if p is a path in the ambient graph and FALSE otherwise.
count – number of paths
combinat::graphPaths::count(<constraints>)
Returns the number of paths in the ambient graph, one can specify the target and/or the source.
source – source of a path
combinat::graphPaths::source(path p)
Returns the source of the path p.
target – target of a path
combinat::graphPaths::target(path p)
Returns the target of the path p.
length – length of a path
combinat::graphPaths::length(path p)
Returns the length of the path p.
_concat – concatenation of two paths
combinat::graphPaths::_concat(path v, path u)
Returns the concatenation v.u of the paths v and u when it is defined and FAIL otherwise.
edgesLeaving – arrows starting from a vertex
combinat::graphPaths::edgesLeaving(vertex x)
Returns the list of the arrows with source x.
edgesArrivingAt – arrows ending at a vertex
combinat::graphPaths::edgesArrivingAt(vertex x)
Returns the list of the arrows with target x.
adjacencyMatrix – adjacency matrix of the graph
combinat::graphPaths::adjacencyMatrix(directed graph graph)
Returns the adjacency matrix of the graph graph: this is a square matrix of size graph[1] x graph[1], whose value at row i and column j is equal to the number of arrows with source i and target j.
countMatrix – matrix counting the paths in the graph
combinat::graphPaths::countMatrix()
Returns a square matrix of size graph[1] x graph[1], whose value at row i and column j is equal to the number of paths with source i and target j.
maxLength – the maximal length of the paths in the ambient graph
combinat::graphPaths::maxLength()
Returns the maximal length of the paths in the graph.
Example 1:
Consider the following graph:
graph := [4,table(a=[1,2], b=[1,2], c=[2,3], d=[3,4], e=[2,4])]:
alias(S = combinat::graphPaths(graph)):
S::isA([1, 1])
S::isA([2, a, 1])
S::isA([4, d, c, a, 1])
S::isA([2, b, a, 1])
S::source([1, 1])
S::source([4, e, b, 1])
S::target([1, 1])
S::target([4, e, b, 1])
S::length([1, 1])
S::length([2, a, 1])
S::length([4, d, c, a, 1])
S::list()
S::list(Source = 1, Target = 4)
S::_concat([2, a, 1], [1, 1])
S::_concat([4, e, a, 1], [1, 1])
S::_concat([2, a, 1], [2, b, 1])
S::edgesLeaving(2)
S::edgesArrivingAt(2)
S::adjacencyMatrix()
S::countMatrix()
S::maxLength()
Changes in MuPAD 3.2
New Function.