Maxplus Function
Last update : 18/05/2014

saturation_graph - saturation graph ( flowshop graph ) ( maxplus )

Calling Sequence

gh=Lsaturation_graph(g)
gh=Rsaturation_graph(g)

Parameters

Description

Computes the left (L) and right (R) saturation graph, that is the arcs that saturate the left/right generalized eigenvector equality of a bivalued graph. The generalized eigenelements are computed by semihoward.

The right saturation graph is the graph where saturating predecessors of i are the nodes belonging to { j : Aij Vj = Vi }, where Aij denotes the weight associated to the edge from node j to node i. The corresponding graph is called G(A'), it uses the dynamical system orientation convention which is the opposite of the one used for Markov (called G(A)).

The left saturation graph is the graph where the set of the saturating successors of i is { j : Vj Aji = Vi }.

In particular, they can be used to see the bottleneck of event-graphs. In this case A is the matrix with entries T-Nxdiag(l) [resp. T-diag(l)xN] for the right [resp. left] saturation graph where T denotes the processing times, N the initial marking and l are the generalized eigenvalues. For an irreducible event graph there exists a unique eigenvalue and l is a vector with constant entries equal to this eigen value.

- The graph must have a structure analogous to the one generated by flowshop_graph.

- Sometimes, it is useful to move the position of the nodes (with the metanet editor) to see the special structures of these saturation graphs.

Examples

PT=#([2,1;%0,1;4,%0]);
xsetech([0 0 0.5 0.5]);
[g,T,N]=flowshop_graph(PT,[1,1,1],[2,2],50);

// Right saturation graph
show_graph(Rsaturation_graph(g));
[l,v]=semihoward(T,N)
(#(full(T))-full(#(plustimes(N)*diag(plustimes(l)))))*v==v

// Left saturation graph
show_graph(Lsaturation_graph(g));
[l,v]=semihoward(T',N')
v'*(#(full(T))-full(#(diag(plustimes(l))*plustimes(N))))==v'
 

See Also

maxplus,  flowshop_graph,  flowshop,  show_cr_graph,