model
E?cient detection of con?icts in graph-based
model transformation
Leen Lambers,Hartmut Ehrig2,1
Institut f¨u r Softwaretechnik und Theoretische Informatik
Technische Universit¨a t Berlin
Germany
Fernando Orejas3
Dept.L.S.I.
Tech.Univ.Catalonia
Barcelona,Spain
Abstract
Using graph transformation as a formalism to specify model transformation,ter-mination and con?uence of the graph transformation system are often required properties.Only under these two conditions,existence and uniqueness of the out-coming model is ensured.Verifying con?uence of a graph transformation system can be reduced to checking both local con?uence and termination.
A graph transformation system is locally con?uent,if all its con?icts in a minimal context can be resolved.Formally,this means,that all critical pairs of the graph transformation system should be strictly con?uent.Thus,answering the question of local con?uence of a graph transformation system,requires the following two steps. At?rst the computation of all critical pairs is necessary.Secondly this set of criti-cal pairs has to be tested for strict con?uence.This paper concentrates on the?rst step,proposing an e?cient method to compute the set of all critical pairs of a given graph transformation system.E?ciency is obtained because of the following two main reasons.At?rst all pairs of rules are analyzed to check if they can actually cause a con?ict.Then for each con?ict inducing pair of rules,the set of critical pairs is computed in a constructive way,avoiding needless computations.
The overall goal of this paper is to encourage tool development and enhancement concerning the detection of con?icts in a graph transformation system.It should be an aid to translate the main theoretical results concerning con?uence of a graph transformation system into practical methods for the analysis of model transforma-tions speci?ed with graph transformation.
Key words:con?ict,con?uence,critical pair,model
transformation,graph transformation
c 2005Publishe
d by Elsevier Scienc
e B.V.
1Introduction
A graph transformation system(gts)exhibits functional behavior if it is ter-minating and con?uent.This is an important feature if graph transformation is used,to specify model transformation[3].Imagine,that we use a con?uent and terminating gts S,to translate one model into another one.In praxis, some graph transformation tool executes the model transformation.Despite the nondeterministic rule application,the transformation has the following two characteristics.On the one hand,we can be sure,that the outcoming model exists,since the gts S is terminating.On the other hand,the outcom-ing model is unique,because of con?uency of S.Thus,each run of S to an input model yields one speci?c output model.Formally,this means,that S operates as a function S:M1→M2on the set M1of input models,generating a unique element of M2,the set of output models of the model transformation. How to ensure termination of a gts is described in[4].An established result in term rewriting[8]is,that if a rewrite system is locally con?uent and termi-nating,it is also con?uent.So the question is,how to ensure local con?uence of a gts.In[6],the so called critical pair lemma states,that a gts is locally con?uent if all its critical pairs are strictly con?uent.Critical pairs are con-?ict situations of the graph transformation system in a minimal context.This paper is concerned with the e?cient detection of these critical pairs.Once detected,they should be checked for strict con?uence to conclude local con-?uence of the gts.
E?cient con?ict detection is obtained,because of the following two reasons. At?rst,rules are analyzed,to check if they can actually cause a con?ict. Secondly,the minimal context of each con?ict is computed in a constructive way.Therefore needless computations,checking for a con?ict in each possible minimal context,are avoided.AGG[10]is a graph transformation tool,which allows an automatic detection of the set of critical pairs of a gts.Implement-ing the optimizations,explained in this paper,should improve its e?ciency. Moreover an algorithm is recommended for other graph transformation tool developers,with the intention to implement critical pair detection.
We begin this paper with some de?nitions for the used graph transformation approach[2].Then the concept of critical pair and con?ict is rehearsed.The main part of this paper is concerned with explaining how to compute in an e?cient way the set of all critical pairs of a gts.
1Email:ehrig@cs.tu-berlin.de
2Email:leen@cs.tu-berlin.de
3Email:orejas@https://www.wendangku.net/doc/ea3425911.html,
2
2Graph Transformation
The theory of con?uence and critical pairs has been worked out for di?erent graph transformation approaches[9].This paper explains how to apply the theory of con?uence and critical pairs,developed for graph transformation in the double pushout approach[6].Thus in this paragraph we shortly repeat the main de?nitions.
De?nition2.1[graph and graph morphism]A graph G=(G E,G V,s,t)con-sists of a set G E of edges,a set G V of vertices and two mappings s,t:G E→G V,assigning to each edge e∈G E a source q=s(e)∈G V and target z=t(e)∈G V.A graph morphism f:G1→G2between two graphs G i= (G i,E,G i,V,s i,t i),(i=1,2)is a pair f=(f E:G E,1→G E,2,f V:G V,1→G V,2) of mappings,such that f V?s1=s2?f E and f V?t1=t2?f E.A graph morphism f:G1→G2is injective(resp.surjective)if f V and f E are injec-tive(resp.surjective)mappings.A graph isomorphism is an injective and surjective graph morphism.A graph inclusion i:H→G is a graph mor-phism,with i V:v→v and i E:e→e.H is a subgraph of G if there exists a graph inclusion i:H→G.Two graph morphisms m1:L1→G and m2:L2→G are jointly surjective if m1,V(L1,V)∪m2,V(L2,V)=G V and m1,E(L1,E)∪m2,E(L2,E)=G E.A pair of jointly surjective morphisms (m1,m2)is also called an overlapping of L1and L2.A graph projection p is a graph morphism from a subgraph G of G1×G2into G1(resp.G2)with p V:G V→G1,V(resp.G2,V)and p E:G E→G1,E(resp.G2,E)projections. Remark:Throughout this paper often f is used,instead of explicitly writing f V and/or f E.
De?nition2.2[category Graph]The category having graphs as objects and graph morphisms as arrows is called Graph.
De?nition2.3[rule]A graph transformation rule p:L l←K r→R consists of a rule name p and a pair of injective graph morphisms l:K→L and r:K→R.The graphs L,K and R are called the left-hand side(lhs),the interface,and the right-hand side(rhs)of p,respectively.The rule p is non-deleting if l:K→L is an isomorphism.Remark:If l is a graph inclusion, then a rule is non-deleting if L=K.
De?nition2.4[graph transformation system]A graph transformation sys-tem consists of a set of rules(p:L l←K r→R)p∈P with P the set of rule names.
De?nition2.5[match]Given a rule p:L l←K r→R and a graph G,one can try to apply p to G if there is an occurence of L in G i.e.an injective graph morphism,called match m:L→G.Remark:In general a match doesn’t have to be injective.Here we restrict to injective matches.
De?nition2.6[direct graph transformation]Given a graph G,a rule p:L l←
3
K r →R and a match m :L →G ,a direct graph transformation from G to H using p exists if and only if the double pushout (DPO)diagram
L m K
l r R can be constructed.In this case we write G p,m
?H .Since pushouts in Graph always exist,the DPO can be constructed if the pushout complement of K →L →G exists.If so,we say that,the match m satis?es the gluing condition of rule p .Note,that since a match in this paper is injective,the identi?cation condition is always full?lled.
De?nition 2.7[graph transformation]A graph transformation over a graph transformation system G is either a graph G ,or a sequence of direct graph transformations G i ?1p i ?G i ,with p i a rule in G .3Con?icts and Critical Pairs
Given a graph G ,we may have several rules that can be applied to G .However,this situation is not necessarily a con?ictive one.In particular if we have two
rules p 1:L 1l 1←K 1r 1→R 1and p 2:L 2l 2←K 2r 2→R 2such that they can both
be applied to G via the matches m 1and m 2,the situation is not a con?ict if,after applying any of the rules,we can still apply the other one,i.e.if the transformation de?ned by the former does not destroy the application of the latter.The following de?nitions characterize this situation:
De?nition 3.1[parallel independence]Two direct transformations G (p 1,m 1)=?H 1and G (p 2,m 2)=?H 2are parallel independent if
m 1(L 1)∩m 2(L 2)?m 1(l 1(K 1))∩m 2(l 2(K 2))
This condition can be expressed categorically in the following way:
?h 1:L 1→D 2:d 2?h 1=m 1∧?h 2:L 2→D 1:d 1?h 2=m 2
R 1
K 1L 1h 1m 1@@@@@@@@L 2h 2m 2~~~~~~~~K 2R 211d 1e 1G 2d 2e 22
De?nition 3.2[con?ict]Two direct transformations G (p 1,m 1)
?H 1and G (p 2,m 2)?
H 2are in con?ict if they are not parallel independent.Remark:This type of con?ict is also called delete-use-con?ict.In particular rule p 2deletes some-thing,what p 1uses if m 1(L 1)∩m 2(L 2)?m 2(l 2(K 2))and/or p 1deletes some-thing,what p 2uses if m 1(L 1)∩m 2(L 2)?m 1(l 1(K 1)).A minimal (in the sense that the graphs G considered are as small as possible)con?ict situation can be characterized by the notion of critical pair:
4
De?nition 3.3[critical pair]A critical pair is a pair of direct transformations K (p 1,m 1)?P 1and K
(p 2,m 2)?P 2in con?ict,s.t.m 1and m 2are jointly surjective morphisms.
R 1K 1L 1m 1@@@@@@@@L 2m 2~~~~~~~~K 2R 2P 1D 1d 1e 1K D 2d 2e 2
P 2Two notions that are important for the rest of the paper are the concepts of boundary and context introduced in [5]:
De?nition 3.4[boundary -context]The boundary B of an injective graph morphism f :A →A consists of all nodes a ∈A such that f (a )is adjacent to an edge in A \f (A ).The context C =A \f (A )∪f (b (B ))can be glued to A over the boundary B obtaining the pushout object A .This situation is expressed by the following pushout,called boundary pushout with b,c and g graph inclusions.
B
c A f g
A Remark:As described in [5]the boundary pushout is an inital pushout.4E?cient Con?ict Detection
Looking at the critical pair de?nition,a straightforward way of computing the set of critical pairs of two rules p 1:L 1←K 1→R 1and p 2:L 2←K 2→R 2is expressed by the following algorithm:
CP =empty;
compute all jointly surjective m1:L1->K and m2:L2->K;
for each pair (m1,m2)
if (m1and m2fullfill gluing condition)
compute (T1,T2)induced by (p1,m1)and (p2,m2);
if (T1and T2are in conflict)
CP =CP U {(T1,T2)};
return CP;
This way of computing can be made more e?ciently because of the following reasons.
(i)It is not necessary to compute any overlapping (m 1,m 2)of L 1and L 2if
both rules are non-deleting.
(ii)If one of the rules is non-deleting and the other one is deleting,it is not
necessary to compute all overlappings (m 1,m 2)of L 1and L 2.It is enough
5
to compute directly those overlappings which will lead to a critical pair. The next paragraphs explain these two optimization steps in more detail and show their correctness.
4.11st Optimization
In the?rst optimization step we need to check if rules are deleting or non-deleting.In that way we can avoid computing overlappings of two non-deleting rules.This would be redundant since the set of critical pairs of two non-deleting rules is empty,as shown in the following lemma.
Lemma4.1Given two non-deleting rules p1:L1l1←K1r1→R1and p2:L2l2←K2r2→R2,each pair of direct graph transformations H1p1,m1
?G p2,m2
?H2is parallel independent.
Proof.We have to prove,that m1(L1)∩m2(L2)?m1(l1(K1))∩m2(l2(K2)). Since for non-deleting rules l1:K1→L1and l2:K2→L2are isomorphisms, because of surjectivity l1(K1)=L1and l2(K2)=L2.Thus,m1(L1)∩m2(L2)?m1(l1(K1))∩m2(l2(K2))=m1(L1)∩m2(L2)holds.2
A rule p:L l←K r→R is non-deleting if l is an isomorphism.There are several ways to check this,depending on how graphs and graph morphisms are stored in the relative system.The following lemma proves,that checking if l is an isomorphism actually corresponds to checking if the context C of l is equal to the empty graph.This method is preferred here,since the context graph C can be reused in the algorithm for detecting the critical pairs.The 2nd optimization in the following paragraph explains why.If graphs are stored by their adjaceny matrix,the computation of the context graph C of l is of quadratic complexity in the number of nodes and edges in L.
Lemma4.2A rule L l←K r→R is a non-deleting rule if and only if the context C of l:K→L is equal to the empty graph.
C g
B
b
c
l R
Proof.
?Since C=L\l(K)∪l(b(B))is equal to the empty graph,L\l(K)is also equal to the empty graph.Therefore L=l(K)and since l is also an injective graph morphism,we can conclude,that l is an isomorphism.
?If l is an isomorphism,we know,that L=l(K)or L\l(K)is equal to the empty graph.Therefore,also the boundary B is equal to the empty graph. Conclusion:C=L\l(K)∪l(b(B))is equal to the empty graph.
2
6
4.22nd Optimization
After detecting the deleting rules we keep only those pairs of rules,with one non-deleting and one deleting rule.For such a pair of rules,it is possible to compute only those overlappings,which lead to a critical pair.This can be achieved by identifying in the overlapping at least one element,which is deleted by the deleting rule,with an element of the lhs of the other rule.The construction of such a special overlapping is formulated in detail in the following de?nition and theorem.Moreover in the theorem it is shown,that this optimization is correct.This means,that computing only this kind of special overlappings,leads us anyhow to the set of all critical pairs.
De?nition 4.3[con?ict conditions -compatibility conditions]Given a non-
deleting rule p 1:L 1l 1←K 1r 1→R 1and a rule p 2:L 2l 2←K 2r 2→R 2,with B 2the
boundary,C 2the context of l 2:L 2←K 2
?
a graph S and two morphisms o 1:S →L 1,o 2:S →C 2satisfy the con?ict conditions if and only if S is a minimal (i.e.there doesn’t exist a graph S ,satisfying the following conditions and being a real subgraph of S )graph such that the following holds:
(i)S is a subgraph of L 1×C 2,with injective projections o 1:S →L 1and
o 2:S →C 2
(ii)o 2(S )is not a subgraph of B 2?
two morphisms m 1:L 1→K and m 2:L 2→K satisfy the compatibility conditions with respect to (S,o 1:S →L 1,o 2:S →C 2)if and only if (i)m 1and m 2are jointly surjective
(ii)m 1?o 1=m 2?g 2?o 2
(iii)m 1(resp.m 2)satis?es the gluing condition of p 1(resp.p 2)Theorem 4.4Given a non-deleting rule p 1:L 1l 1←K 1r
1→R 1and a rule
p 2:L 2l 2←K 2r 2→R 2,the following holds:?Each (S,o 1,o 2),satisfying the con?ict conditions and each pair of graph morphisms m 1:L 1→K and m 2:L 2→K ,satisfying the compatibility conditions with respect to (S,o 1,o 2)gives rise to a critical pair P 1p 1,m 1?K p 2,m 2?P 2.
S o 2A A A A A A A A o 1 C 2g 2B 2b 2c 2R 1K 1l 1r 1L 1m 1@@@@@@@@L 2m 2}}}}}}}}K 2l 2r 2R 211d 1e 1K 2d 2
e 22?For each critical pair P 1p 1,m 1
?K p 2,m 2?P 2there exists a graph S and mor-
7
phisms o 1:S →L 1,o 2:S →C 2such that (S,o 1,o 2)satis?es the con?ict conditions and the matches m 1:L 1→K and m 2:L 2→K satisfy the compatibility conditions with respect to (S,o 1,o 2).
Proof.
?Because of the 3rd compatibility condition,the pair of direct transforma-tions L 1p 1,m 1?P 1and L 2p 2,m 2?P 2exists.The 1st compatibility condition ensures,that m 1and m 2are jointly surjective,thus it su?ces to show that m 1(L 1)∩m 2(L 2)?m 2(l 2(K 2))to prove that the direct transformations L 1p 1,m 1?P 1and L 2p 2,m 2?P 2are in con?ict and to conclude that they form a critical pair.So we should ?nd an element y ∈m 1(L 1)∩m 2(L 2)s.t.y ∈m 2(l 2(K 2)).Because of the con?ict conditions of S ,there exists an x in S V or S E such that o 2(x )∈C 2\c 2(B 2)=C 2\B 2.This is,because otherwise o 2(S )would be a subgraph of B 2.Because of o 2(x )∈C 2\B 2and the fact that (2)is a pushout,g 2(o 2(x ))∈l 2(K 2).Since m 2is in-jective,also m 2(g 2(o 2(x )))∈m 2(l 2(K 2)).The 2nd compatibility condition says,that ?x ∈S :m 1(o 1(x ))=m 2(g 2(o 2(x ))).Thus,we have found an y =m 2(g 2(o 2(x )))∈m 1(L 1)∩m 2(L 2)s.t.y ∈m 2(l 2(K 2)).
?At ?rst we can build the pullback of m 1and m 2?g 2,obtaining a pullback object S subgraph of L 1×C 2and induced injective graph projections o 1:S →L 1and o 2:S →C 2.S i o 2A A A A A A A A o 1S o 2(1)o 1~~~~~~~~C 2g 2B 2(2)b 2c 2R 1K 1l 1r 1L 1m 1@@@@@@@@2m 2
}}}}}}}}2l 2r 2R 211d 1e 1K 2d 2e 2
2Since the critical pair consists of two direct transformations in con?ict and p 1is a non-deleting rule,we know that,there exists an y ∈m 1(L 1)∩m 2(L 2),such that y ∈m 2(l 2(K 2)).This is,because since m 1(L 1)∩m 2(L 2)?m 1(l 1(K 1))∩m 2(l 2(K 2)))and since l 1is an isomorphism each y ∈m 1(L 1)holds a preimage x in L 1and each x in L 1holds a preimage z in K 1.This means,that m 1(L 1)∩m 2(L 2)?m 1(l 1(K 1)).Then,it follows that m 1(L 1)∩m 2(L 2)?m 2(l 2(K 2)).Thus,there exist x 1∈L 1and x 2∈L 2s.t.m 2(x 2)=y =m 1(x 1),but there exists no k ∈K 2s.t.l 2(k )=x 2.Because of this and the fact that (2)is a pushout,there exists c ∈C 2\B 2s.t.g 2(c )=x 2.Thus,we have that m 1(x 1)=m 2(x 2)=m 2(g 2(c )).Since
(1)is a pullback,this means,that S is not equal to the empty graph.In fact,there exists an s ∈S s.t.o 2(s )=c and o 1(s )=x 1.Since o 2(s )=c and c ∈C 2\B 2,o 2(S )can’t be a subgraph of B 2.Thus (S ,o 1,o 2)full?lls the con?ict conditions if S in addition would be minimal.If it is not,then
8
we take a minimal subgraph S of S ,with projections o1:S→L1and
o2:S→C2s.t.o2(S)is not a subgraph of B2.Then(S,o1,o2)satis?es the con?ict conditions.The matches(m1,m2)of the critical pair are by
de?nition jointly surjective and they full?ll the gluing condition of p1resp.
p2.Since(1)is a pullback and S is a subgraph of S ,m1?o1=m2?g2?o2. Thus(m1,m2)full?ll the compatibility conditions with respect to(S,o1,o2).
2
5Critical Pair Algorithm
The optimization steps in the last paragraph help us to compute in an e?cient way the set of critical pairs of two non-deleting rules or of one deleting and one non-deleting rule.The following algorithm computes the set of critical pairs CP=CP1∪CP2,induced by the rules p1:L1l1←K1r1→R1and
p2:L2l2←K2r2→R2.Note,that CP1(resp.CP2)is the set of critical pairs, expressing the delete-use-con?icts in which p2(resp.p1)uses something,what
is deleted by p1(resp.p2),comp.is an abbreviation of compatibility and
T1(resp.T2)is a direct transformation induced by a match m1(resp.m2), satisfying the gluing condition and the rule p1(resp.p2).
CP_1=empty;
CP_2=empty;
compute context C1of l1;
compute context C2of l2;
if(C1!=empty and C2=empty)
compute all S of L2and C1,satisfying conflict conditions;
for each S
compute all m1:L1->K and m2:L2->K,satisfying comp.conditions;
if(m1and m2fullfill gluing condition)
compute(T1,T2)induced by(p1,m1)and(p2,m2);
CP_1=CP_1U{(T1,T2)};
if(C2!=empty and C1=empty)
compute all S of L1and C2,satisfying conflict conditions;
for each S
compute all m1:L1->K and m2:L2->K,satisfying comp.conditions;
if(m1and m2fullfill gluing condition)
compute(T1,T2)induced by(p1,m1)and(p2,m2);
CP_2=CP_2U{(T1,T2)};
return(CP_1,CP_2);
Note,that this algorithm avoids computing overlappings of a pair of non-deleting rules.The?rst optimization tells us,that this is the case if the context graphs C1and C2are both empty.Secondly,not all possible overlappings m1 and m2are computed,but only those,satisfying the compatibility conditions over a graphs S,satisfying the con?ict conditions.The second optimization
9
Fig.1.Example:all possible overlappings of L1and L2
Fig.2.Example:construction of critical overlapping of L1and L2
tells us,that if m1and m2full?ll the gluing condition,the pair of induced direct transformations T1and T2is a critical pair.It is not necessary anymore to check if T1and T2are in con?ict,because the1st part of Theorem4.4tells us, that they automatically are.Moreover following this algorithm we de?nitely get all critical pairs,because this is proven in the2nd part of Theorem4.4. The computation of critical pairs of a pair of rules,as proposed in the begin-ning of this paragraph before making the optimizations is exponential in the number of nodes and edges of L1and L2because of the computation of all overlappings(m1,m2).For example in Figure1we have two lhs’s of two rules and all their possible overlappings.For the case of pairs of rules,consisting of at least one non-deleting rule we can apply the recommended two optimiza-
10
tions.For example in Figure2we have one deleting and one non-deleting rule and can apply the second optimization,leading us directly to the only critical pair for this pair of rules.This is because only one graph S satis?es the con?ict conditions of these rules and only one pair of overlappings satis?es the compatibility conditions with respect to this graph S.In the case of two non-deleting rules the algorithm is of quadratic complexity in the number of nodes and edges of L1and L2,because in this case only the computation of the context graphs is carried out.
6Summary and Outlook
Con?ict detection is a necessary step in checking functional behavior of a graph-based model transformation.A critical pair describes in a formal way a con?ict situation occuring in a minimal context.The set of critical pairs,i.e. all minimal con?icts,can be computed in an e?cient and constructive way. At?rst,each pair of rules is analyzed,?ltering out only the con?ict inducing pair of rules.Secondly,the minimal context of each con?ict,described by the critical pair de?nition,is computed in a constructive way.Therefore needless computations,checking for a con?ict in each possible minimal context,are avoided.Further necessary steps in checking functional behavior are analysis of all minimal con?icts for strict con?uence and checking for termination of the graph transformation system.
Note,that in this paper an e?cient con?ict detection is proposed for a pair of non-deleting rules or a pair of one deleting and one non-deleting rule.The case of two deleting rules and the case of having transformations with non-injective matches still have to be investigated.Moreover we should point out the possibility of further improvement of the proposed algorithm.Therefore we would need an extension of the theory which ensures the fact that each critical pair possesses a unique graph S,satisfying the con?ict conditions, over which the critical pair can be constructed.Then we could rule out the possibility of computing the same critical pair more than once.This kind of extensions and the theoretical results already available in this paper can be formulated as well in the context of adhesive HLR categories[6],which will be done in a following paper.
Further future work consists of extending con?ict detection to other kinds of con?icts,adding negative application conditions(NAC’s)[1],typing and attributes[7]to the graph transformation formalism.Therefore,at?rst the results in[6]about local con?uence and critical pairs should be extended to gts with NAC’s.In addition we are working on?nding a necessary and su?-cient condition for a graph transformation system to be locally con?uent.In [6]only a su?cient condition is formulated.This means,that it is not known yet if a graph transformation system can be locally con?uent if not all of its critical pairs are strictly con?uent.Then for these extended graph transfor-mation formalism again the mechanism of at?rst analysing all pairs of rules
11
and afterwards e?cient computation of the minimal context of each con?ict should be worked out.
Acknowledgements.This work in collaboration partly arose during a re-search stay of the?rst author with a SEGRAVIS(HPRN-CT-2002-00275) grant in february and march’05at the UPC in Barcelona.The work of Fernando Orejas has been partially supported by the Spanish project GRAM-MARS(TIN2004-07925-C03-01).Further on we are grateful to Enrico Bier-mann,Olga Runge and Gabi Taentzer for the suggestive discussions on the implementation of critical pair detection in AGG[10].
References
[1]Annegret Habel,R.H.and G.Taentzer,Graph grammars with negative
application conditions(1996).
[2]Corradini,A.,U.Montanari,F.Rossi,H.Ehrig,R.Heckel and M.L¨o we,
Algebraic Approaches to Graph Transformation I:Basic Concepts and Double Pushout Approach,in:G.Rozenberg,editor,Handbook of Graph Grammars and Computing by Graph Transformation,Volume1:Foundations,World Scienti?c, 1997pp.163–245.
[3]de Lara,J.and G.Taentzer,Automated Model Transformation and its
Validation using AT oM3and AGG,in: A.Blackwell,K.Marriott and
A.Shimojima,editors,Diagrammatic Representation and Inference(2004).
[4]Ehrig,H.,K.Ehrig,J.de Lara,G.Taentzer, D.Varr′o and S.Varr′o-
Gyapay,Termination criteria for model transformation,in:Proc.Fundamental Approaches to Software Engineering(FASE),Lecture Notes in Computer Science(2005),pp.00–00,to appear.
URL http://tfs.cs.tu-berlin.de/~ehrig/public/EEL+05.pdf
[5]Ehrig,H.,K.Ehrig, A.Habel and K.-H.Pennemann,Constraints and
application conditions:From graphs to high-level structures,in: F.Parisi-Presicce,P.Bottoni and G.Engels,editors,Proc.2nd Int.Conference on Graph Transformation(ICGT’04),LNCS3256(2004),pp.287–303.
URL http://www.cs.tu-berlin.de/~ehrig/publications/ICGT04paper3.
[6]Ehrig,H.,A.Habel,J.Padberg and U.Prange,Adhesive high-level replacement
categories and systems,in:F.Parisi-Presicce,P.Bottoni and G.Engels,editors, Proc.2nd Int.Conference on Graph Transformation(ICGT’04),LNCS3256 (2004),pp.144–160.
URL http://www.cs.tu-berlin.de/~ehrig/publications/ICGT04paper1.
[7]Ehrig,H.,U.Prange and G.Taentzer,Fundamental theory for typed attributed
graph transformation,in:F.Parisi-Presicce,P.Bottoni and G.Engels,editors, Proc.2nd Int.Conference on Graph Transformation(ICGT’04),Rome,Italy,
12
LNCS3256,Springer,2004pp.161–177.
URL http://www.cs.tu-berlin.de/~ehrig/publications/ICGT04paper2.
[8]Huet,G.,Con?uent reductions:Abstract properties and applications to term
rewriting systems(1980).
[9]Plump, D.,Hypergraph Rewriting:Critical Pairs and Undecidability of
Con?uence,in:M.Sleep,M.Plasmeijer and M.C.van Eekelen,editors,Term Graph Rewriting,Wiley,1993pp.201–214.
[10]Taentzer,G.,AGG:A Graph Transformation Environment for Modeling and
Validation of Software,in:J.Pfaltz,M.Nagl and B.Boehlen,editors, Application of Graph Transformations with Industrial Relevance(AGTIVE’03), LNCS3062,Springer,2004pp.446–456.
13
Fluent多相流模型选择
FLUENT多相流模型 分类 1、气液或液液流动 气泡流动：连续流体中存在离散的气泡或液泡 液滴流动：连续相为气相，其它相为液滴 栓塞（泡状）流动：在连续流体中存在尺寸较大的气泡 分层自由流动：由明显的分界面隔开的非混合流体流动。 2、气固两相流动 粒子负载流动：连续气体流动中有离散的固体粒子 气力输运：流动模式依赖，如固体载荷、雷诺数和例子属性等。最典型的模式有沙子的流动，泥浆流，填充床以及各相同性流 流化床：有一个盛有粒子的竖直圆筒构成，气体从一个分散器进入筒内，从床底不断冲入的气体使得颗粒得以悬浮。 3、液固两相流动 泥浆流：流体中的大量颗粒流动。颗粒的stokes数通常小于1。大于1是成为流化了的液固流动。 水力运输：在连续流体中密布着固体颗粒 沉降运动：在有一定高度的盛有液体的容器内，初始时刻均匀散布着颗粒物质，随后，流体会出现分层。 4、三相流 以上各种情况的组合 多相流动系统的实例 气泡流：抽吸、通风、空气泵、气穴、蒸发、浮选、洗刷。 液滴流：抽吸、喷雾、燃烧室、低温泵、干燥机、蒸发、气冷、洗刷。 栓塞流：管道或容器中有大尺度气泡的流动 分层流：分离器中的晃动、核反应装置沸腾和冷凝 粒子负载流：旋风分离器、空气分类器、洗尘器、环境尘埃流动 气力输运：水泥、谷粒和金属粉末的输运 流化床：流化床反应器、循环流化床 泥浆流：泥浆输运、矿物处理 水力输运：矿物处理、生物医学、物理化学中的流体系统 沉降流动：矿物处理。 多相流模型的选择原则 1、基本原则
1)对于体积分数小于10%的气泡、液滴和粒子负载流动，采用离散相 模型。 2)对于离散相混合物或者单独的离散相体积率超出10%的气泡、液滴 和粒子负载流动，采用混合模型或欧拉模型。 3)对于栓塞流、泡状流，采用VOF模型 4)对于分层/自由面流动，采用VOF模型 5)对于气动输运，均匀流动采用混合模型，粒子流采用欧拉模型。 6)对于流化床，采用欧拉模型 7)泥浆和水力输运，采用混合模型或欧拉模型。 8)沉降采用欧拉模型 9)对于更一般的，同时包含多种多相流模式的情况，应根据最感兴趣 的流动特种，选择合适的流动模型。此时由于模型只是对部分流动特 征采用了较好的模拟，其精度必然低于只包含单个模式的流动。 2、混合模型和欧拉模型的选择原则 VOF模型适合于分层的或自由表面流，而混合模型和欧拉模型适合于流动中有相混合或分离，或者分散相的体积分数超过10%的情况（小于10%可使用离散相模型）。 1)如果分散相有宽广的分布（如颗粒的尺寸分布很宽），最好采用混 合模型，反之使用欧拉模型。 2)如果相间曳力规律一直，欧拉模型通常比混合模型更精确；若相间 曳力规律不明确，最好选用混合模型。 3)如果希望减小计算了，最好选用混合模型，它比欧拉模型少解一部 分方程；如果要求精度而不在意计算量，欧拉模型可能是更好的选择。 但是要注意，复杂的欧拉模型比混合模型的稳定性差，可能会遇到收 敛困难。
多级混合模型
多级混合模型 假定条件：① 每一级内为全混流； ② 级际间无返混；③ 各釜体积相同。 图4-7 多级全混流串联模型 因NV i =V ，且假定物料流率为v ，则： v V t = N t Nv V t i == 在多级全混流串联模型中，在系统入口处阶跃注入浓度为C 0的示踪物，对第i 个反应器进行示踪物的物料衡算，有： dt t dC V v t C v t C i i i i )()()(1=-- （1） 因：v V N t i =，故： )()()(1t C t N t C t N dt t dC i i i -=+ （2）
（dx Qe ye pdx pdx ??=?） 当t=0时，第i 个反应器中示踪物的浓度C i （t ）=0，积分上式得： dt e t C e t N t C t Nt t i t Nt i /01)()()(?--= （3） 对于第一级，01C C i =-，所以上式可变为： dt e e t N C t C t Nt t t Nt /0)(01)(?-= （4） 对上进行积分便可以得到第一级反应器出口示踪物 的应答曲线： )(011) (t Nt e C t C --= （5） 同样，对于第二级反应器：11 C C i =-，代入到（3）式，得： dt e e C e t N t C t Nt t t Nt t Nt /0)(0)(2)1()(?---= （6） 进行积分可以得到第二级反应器出口示踪物的应答曲线： )1(1) ()(02t Nt e C t C t Nt +-=- （7）
用同样方法依次类推便可以得出第N 级出口示踪 物的应答曲线：式（4-27）。式中：N t vN V s ==τ，为对单个釜而言的平均停留时间。式（4-27）即为多级全混流模型的分布函数计算式。
实验分析数据流和绘制数据流图
实验报告课程名称_软件工程导论__________ 学院____计算机工程学院_________班级14软件1班 学号2014144141 姓名秦川 2016年11月8日
批阅教师时间实验成绩 课程名称软件工程 学号2014144141姓名秦川实验日期2016.11.8实验名称实验2分析数据流和绘制数据流图 实验目的： 1、掌握数据流的分析方法 2、掌握数据流图的绘制 实验内容： 任务一绘制数据流图 任务二分析数据流和绘制数据流图 案例一：总务办公管理系统 案例二：火车票预订系统 实验原理： 数据流图（DFD）是软件系统系统的逻辑模型，仅仅描绘数据在软件中流动（从输入移动到输出）的过程中所经受的变换（即加工处理）。 数据流图的绘制方法：根据数据流图的四种成分：源点或终点，处理，数据存储和数据流，从问题描述中提取数据流图的四种成分；然后依据“自顶向下、从左到右、由粗到细、逐步求精”的基本原则进行绘制。 基本符号如下：
实验过程与结果： 1．运行Microsoft Office Visio2007 运行Microsoft Office Visio2007 2．选择“软件和数据库”中的“数据流模型图”模板 选中数据流模型图模板
3．用鼠标选拉图标进行绘图 任务一绘制数据流图 试绘制工资管理系统的数据流图，根据数据流图的符号说明仔细理解下图含义： 这是学校教职工工资管理系统，教师根据课时表，职工根据任务表来确定个人工资情况，数据按以下方向传递： 首先，对课时表或任务表进行审核，审核后的数据经排序形成专用表格； 再进行一系列额外计算，包括个人所得说、住房公积金、保险费得出具体所发工资，并将工资表发给银行； 然后，向教职工展示工资所得明细； 最后，形成编制报表，更新分类表后，交于会计。 其中，人事科负责人事数据，教师与职工的工资由银行发放，会计做好报表的统计。
(推荐)FLUENT中两相流、多相流中模型的的选择问题
两相流：通常把含有大量固体或液体颗粒的气体或液体流动称为两相流；其中含有多种尺寸组颗粒群为一个“相”，气体或液体为另一“相”，由此就有气—液，气—固，液—固等两相流之分。 两相流的研究：对两相流的研究有两种不同的观点：一是把流体作为连续介质，而把颗粒群作为离散体系；而另一是除了把流体作为连续介质外，还把颗粒群当作拟连续介质或拟流体。 引入两种坐标系：即拉格朗日坐标和欧拉坐标，以变形前的初始坐标为自变量称为拉格朗日Langrangian 坐标或物质坐标；以变形后瞬时坐标为自变量称为欧拉Eulerian 坐标或空间坐标。 一.离散相模型 FLUENT在求解连续相的输运方程的同时，在拉格朗日坐标下模拟流场中离散相的第二相； 离散相模型解决的问题：煤粉燃烧、颗粒分离、喷雾干燥、液体燃料的燃烧等； 应用范围：FLUENT中的离散相模型假定第二相体积分数一般说来要小于10-12%（但颗粒质量承载率可以大于10-12%，即可模拟离散相质量流率等/大于连续相的流动）；不适用于模拟在连续相中无限期悬浮的颗粒流问题，包括：搅拌釜、流化床等； 颗粒-颗粒之间的相互作用、颗粒体积分数对连续相的影响未考虑； 湍流中颗粒处理的两种模型：Stochastic Tracking，应用随机方法来考虑瞬时湍流速度对颗粒轨道的影响；Cloud Tracking，运用统计方法来跟踪颗粒围绕某一平均轨道的湍流扩散。通过计算颗粒的系统平均运动方程得到颗粒的某个“平均轨道” 二.多相流模型 FLUENT中提供的模型： VOF模型(Volume of Fluid Model) 混合模型(Mixture Model) 欧拉模型(Eulerian Model) 1.VOF模型(Volume of Fluid Model) VOF模型用来处理没有相互穿插的多相流问题，在处理两相流中，假设计算的每个控制容积中第一相的体积含量为α1，如果α1=0，表示该控制容积中不含第一相，如果α1=1，则表示该控制容积中只含有第一相，如果0<α1<1，表示该控制容积中有两相交界面； VOF方法是用体积率函数表示流体自由面的位置和流体所占的体积，其方法占内存小，是一种简单而有效的方法。 2.混合模型(Mixture Model) 用混合特性参数描述的两相流场的场方程组称为混合模型； 考虑了界面传递特性以及两相间的扩散作用和脉动作用；使用了滑移速度的概念，允许相以不同的速度运动； 用于模拟各相有不同速度的多相流；也用于模拟有强烈耦合的各向同性多相流和各相以相同速度运动的多相流； 缺点：界面特性包括不全，扩散和脉动特性难于处理。 3.欧拉模型(Eulerian Model) 欧拉模型指的是欧拉—欧拉模型； 把颗粒和气体看成两种流体，空间各点都有这两种流体各自不同的速度、温度和密度，这些流体其存在在同一空间并相互渗透，但各有不同的体积分数，相互间有滑移；
多相流模拟知识讲解
多相流模拟
多相流模拟介绍 自然界和工程问题中会遇到大量的多相流动。物质一般具有气态、液态和固态三相，但是多相流系统中相的概念具有更为广泛的意义。在多项流动中，所谓的“相”可以定义为具有相同类别的物质，该类物质在所处的流动中具有特定的惯性响应并与流场相互作用。比如说，相同材料的固体物质颗粒如果具有不同尺寸，就可以把它们看成不同的相，因为相同尺寸粒子的集合对流场有相似的动力学响应。本章大致介绍一下Fluent中的多相流建模。 多相流动模式 我们可以根据下面的原则对多相流分成四类： ?气-液或者液-液两相流： o气泡流动：连续流体中的气泡或者液泡。 o液滴流动：连续气体中的离散流体液滴。 o活塞流动：在连续流体中的大的气泡 o分层自由面流动：由明显的分界面隔开的非混合流体流动。 ?气-固两相流： o充满粒子的流动：连续气体流动中有离散的固体粒子。 o气动输运：流动模式依赖诸如固体载荷、雷诺数和粒子属性等因素。最典型的模式有沙子的流动，泥浆流，填充床，以及各向同性流。 o流化床：由一个盛有粒子的竖直圆筒构成，气体从一个分散器导入筒内。从床底不断充入的气体使得颗粒得以悬浮。改变气体的流量，就会有气泡不断的出 现并穿过整个容器，从而使得颗粒在床内得到充分混合。 ?液-固两相流
o泥浆流：流体中的颗粒输运。液-固两相流的基本特征不同于液体中固体颗粒的流动。在泥浆流中，Stokes数通常小于1。当Stokes数大于1时，流动成为 流化（fluidization）了的液-固流动。 o水力运输：在连续流体中密布着固体颗粒 o沉降运动：在有一定高度的成有液体的容器内，初始时刻均匀散布着颗粒物质。随后，流体将会分层，在容器底部因为颗粒的不断沉降并堆积形成了淤积 层，在顶部出现了澄清层，里面没有颗粒物质，在中间则是沉降层，那里的粒 子仍然在沉降。在澄清层和沉降层中间，是一个清晰可辨的交界面。 三相流 (上面各种情况的组合) 多相系统的例子 ?气泡流例子：抽吸，通风，空气泵，气穴，蒸发，浮选，洗刷 ?液滴流例子：抽吸，喷雾，燃烧室，低温泵，干燥机，蒸发，气冷，刷洗 ?活塞流例子：管道或容器内有大尺度气泡的流动 ?分层自由面流动例子：分离器中的晃动，核反应装置中的沸腾和冷凝 ?粒子负载流动例子：旋风分离器，空气分类器，洗尘器，环境尘埃流动 ?风力输运例子：水泥、谷粒和金属粉末的输运 ?流化床例子：流化床反应器，循环流化床 ?泥浆流例子: 泥浆输运，矿物处理 ?水力输运例子：矿物处理，生物医学及物理化学中的流体系统 ?沉降例子：矿物处理 多相建模方法 计算流体力学的进展为深入了解多相流动提供了基础。目前有两种数值计算的方法处理多相流：欧拉－拉格朗日方法和欧拉－欧拉方法。 欧拉－拉格朗日方法
变差函数的概念与计算分析
变差函数的概念与计算 谷跃民编写 在地质统计学随机模拟工作中，统计归纳区域变量的分布和变差函数，是用好随机模拟技术最关键的两项工作，其中区域变量分布统计比较容易理解，变差函数计算过程相对复杂，影响了解释人员对它的直观理解，为了使解释生产人员快速了解变差函数，准确使用相关工具软件，并能依据现有的资料和对工区地质情况的先验信息，统计归纳出合乎实际的变差函数，作者在学习相关知识的基础上，对学习材料进行了初步总结，试图用通俗的方式，对变差函数的概念和统计归纳方法与大家共同进行探讨。 一、变差函数的基本概念 在地质统计学中，变差函数是最基本与最重要的模拟工具，它用于描述数据值的空间互相关，数据点在空间上相距越远，相关性就变得越小，变差函数就是模拟这种现象的数学函数，通常用一张图来展示，用X轴表示滞后距离，用Y 轴表示方差，可以从区域变量 抽取的样本值中计算归纳出来， 见图1，它通过变程来反映变量 的影响范围，V(h)为变差函数值， Lag(h)为滞后距。 变差函数可以用四个参数来描 述： 1、变差函数类型：决定了随着滞图1 变差函数图示 后距的增加变差（方差）变化的快慢， 在JASON STATMOD MC中，使用GAUSSIAN和EXPONENTIAL曲线类型； 2、变程a：指的是在超过这个距离后，数据点之间就不再有明显的相关性，也称作影响距离； 3、块金效应C0：表示在距离为0时的方差值，用来表示相距很近的两点的样品变化情况； 4、先验方差：Sill=C+C0也叫基台值，它反映变量的变化幅度。 二、变差函数的估算与拟合
1、变差函数的计算公式与估算 变差函数的定义是：区域化变量Z(x)和Z(x+h)两点之差的方差之半，定义为Z(x)的变差函数，数学定义如下： h为滞后距。 如果有了区域化变量Z(x)的一部分采样，就可以估算该区域化变量的Z(x)变差函数，具体计算公式如下： i为样本序号。 2、变差函数的估算示例 为了能更直观、更深刻地体会它的具体意义，下面举两个计算实例，各具体计算两个变差函数值，通过具体计算过程，就会知道什么样的资料可以满足变差函数估算的要求，具体在资料条件会出现怎样的异常，这两个实例分别为两种区域变量类型，一个是垂向区域变量类型，可以理解为井曲线等，一个是平面区域变量类型，可以理解为孔隙度平面变化等。 （1）垂向区域变量类型变差函数值计算示例。 右图为一口井的孔隙度曲线，纵向 采样间隔为1米，右侧为其数值，首先 根据公式1-2，求取h=1米时，v(1) 的数值，步骤如下： ①将数据下移1米，与原始数据对齐； 见图3a； ②找到对应数据对，求得各数据对的差
多相流模型和离散相模型的区别
多相流模型和离散相模型的区别 2008-03-30 10:18 两相流：通常把含有大量固体或液体颗粒的气体或液体流动称为两相流；其中含有多种尺寸组颗粒群为一个“相”，气体或液体为另一“相”，由此就有气—液，气—固，液—固等两相流之分。 两相流的研究：对两相流的研究有两种不同的观点：一是把流体作为连续介质，而把颗粒群作为离散体系；而另一是除了把流体作为连续介质外，还把颗粒群当作拟连续介质或拟流体。 引入两种坐标系：即拉格朗日坐标和欧拉坐标，以变形前的初始坐标为自变量称为拉格朗日Langrangian 坐标或物质坐标；以变形后瞬时坐标为自变量称为欧拉Eulerian 坐标或空间坐标。 离散相模型 FLUENT在求解连续相的输运方程的同时，在拉格朗日坐标下模拟流场中离散相的第二相；← ←离散相模型解决的问题：煤粉燃烧、颗粒分离、喷雾干燥、液体燃料的燃烧等； ←应用范围：FLUENT中的离散相模型假定第二相体积分数一般说来要小于10-12%（但颗粒质量承载率可以大于10-12%，即可模拟离散相质量流率等/大于连续相的流动）；不适用于模拟在连续相中无限期悬浮的颗粒流问题，包括：搅拌釜、流化床等； ←颗粒-颗粒之间的相互作用、颗粒体积分数对连续相的影响未考虑； 湍流中颗粒处理的两种模型：Stochastic← Tracking，应用随机方法来考虑瞬时湍流速度对颗粒轨道的影响；Cloud Tracking，运用统计方法来跟踪颗粒围绕某一平均轨道的湍流扩散。通过计算颗粒的系统平均运动方程得到颗粒的某个“平均轨道” 多相流模型 FLUENT中提供的模型： VOF模型(Volume of Fluid← Model) 混合模型(Mixture Model)← 欧拉模型(Eulerian Model)← VOF模型(Volume of Fluid Model) ← VOF模型用来处理没有相互穿插的多相流问题，在处理两相流中，假设计算的每个控制容积中第一相的体积含量为α1，如果α1=0，表示该控制容积中不含第一相，如果α1=1，则表示该控制容积中只含有第一相，如果0<α1<1，表示该控制容积中有两相交界面； ← VOF方法是用体积率函数表示流体自由面的位置和流体所占的体积，其方法占内存小，是一种简单而有效的方法。 混合模型(Mixture Model) 用混合特性参数描述的两相流场的场方程组称为混合模型；← ←考虑了界面传递特性以及两相间的扩散作用和脉动作用；使用了滑移速度的概念，允许相以不同的速度运动； ←用于模拟各相有不同速度的多相流；也用于模拟有强烈耦合的各向同性多相流和各相以相同速度运动的多相流； ←缺点：界面特性包括不全，扩散和脉动特性难于处理。
公共政策学中的多源流分析模型
社会环境问题流 政策流 政治流 政策窗口议程建立 过程理论 政策是政治活动 “自下而上”的大众驱动型的政策制定模型的一部分。这个流线图表示了社会环境导致议程建立的过程。多源流分析模型前提变量独立变量干涉变量因变量
多源流理论 1995年美国政治家约翰·W·金登在科恩的“垃圾桶模型”的基础上提出了多源流分析的基本框架。多源流理论是一种比较有创见性、解释力和发展潜力的理论模型。而他认为，在政策系统中存在着问题流、政策流和政治流3中不同的源流。 问题流：人们对某一理想状态的知觉与所观察的状况之间的不匹配变成了问题，是必须对其采取某种行动的状况。 政策流：在政策原汤中漂浮的各种思想，有的是对未来的模糊概念，有的是专门设计的政策建议。思想之间相互作用，只有符合某种标准的思想才能坚持下来。 政治流：由诸如公众情绪，压力集团间的竞争、选举结果、政党或者一时形态在议会中的分布状况以及政府的变更等因素构成。对于议程状态有明显的促进作用或抑制作用。
问题在社会四处漂流，但不是所有的问题都能够得到政策制定者的关注从而上升到政策议程，只有当“各种问题开始引起政府内部及其周围人们的关注”的时候才能被识别。 就政策流来说，”有一个其工作重心就是要产生政策建议的政策共同体，构成整个共同体的人员包括专家和官僚、规划评估方面的人员、预算部门的人员、国会的办事人员、学者、压力集团以及研究人员。他们各自都有自己最得意的想法或自己的打算；他们在这些政策共同体中四处散发自己的思想。在这种选择过程中，有些思想政策建议得到了重视，而另一些思想则被抛弃”。 而“政治溪流中包括像国民情绪的摇摆不定、公共舆论的变化莫测、行政当局的更换、党派或意识形态在国会中分布状况的改变以及利益集团的影响这样的因素。这条溪流中实践的发生往往不依赖于问题溪流和建议溪流”。 这3条源流彼此独立，其发生、发展和运作都不依赖于其他源流，但它们在某一关键时间点上汇合到一起，从而打开政策窗口，问题就会被提上政策议程。政策窗口的开启时“政策建议的倡导者提出其最得意的解决办法的机会，或者是他们促使其特殊问题受到关注的机会”，最可能促使政策窗口开启的是社会事件或政治事件。但是政策窗口并不经常打开，且打开的时间也不长。政策建议的倡导者需要抓住并利用“政策之窗”开启的机会促使自己的政策主张与问题流、政治流相结合，上升到政策议程，达到政策结果。
数据流图模型建立
数据流图模型建立（功能模型） 最初，结构化分析方法仅讨论数据流建模。目标系统被表示成如图4-2-1所示的数据变换流程图。系统的功能体现在核心的数据变换中。 图4-2-1数据流图（DFD） 功能建模的思想就是用抽象模型的概念，按照软件内部数据传递、变换的关系，自顶向下逐层分解，直到找到满足功能要求的所有可实现的软件为止。根据DeMarco的论述，功能模型使用了数据流图来表达系统内数据的运动情况，而数据流的变换则用结构化英语、判定表与判定树来描述。 一、数据流图 图4-2-2是描述储户携带存折去银行办理取款手续的数据流图。从图中可以看到，数据流图的基本图形元素有四种，如图4-2-3所示。 图4-2-2办理取款手续的数据流图 图4-2-3DFD的基本图形符号 在数据流图中，如果有两个以上数据流指向一个加工，或是从一个加工中引出两个以上的数据流，这些数据流之间往往存在一定的关系。为表达这些关系，在这些数据流的加工可以标上不同的标记符号。所用符号及其含意在图4-2-4中给出。
图4-2-4表明多个数据流与加工之间关系的符号 二、分层数据流图 为了表达数据处理过程的数据加工情况，用一个数据流图是不够的。稍为复杂的实际问题，在数据流图上常常出现十几个甚至几十个加工。这样的数据流图看起来很不清楚。层次结构的数据流图能很好地解决这一问题。按照系统的层次结构进行逐步分解，并以分层的数据流图反映这种结构关系，能清楚地表达和容易理解整个系统。 图4-2-5给出分层数据流图的示例。数据处理S包括3个子系统1、2、3。顶层下面的第一层数据流图为DFD／L1。第二层数据流图DFD／L2.1、DFD／L2.2及DFD／L2.3分别是子系统1、2和3的细化。对任何一层数据流图来说，我们称它的上层图为父图，在它下一层的图则称为子图。 图4-2-5分层数据流图 画数据流图的基本步骤概括地说，就是自外向内，自顶向下，逐层细化，完善求精。检查和修改的原则为： ①数据流图上所有图形符号只限于前述四种基本图形元素。 ②顶层数据流图必须包括前述四种基本元素，缺一不可。 ③顶层数据流图上的数据流必须封闭在外部实体之间。 ④每个加工至少有一个输入数据流和一个输出数据流。 ⑤在数据流图中，需按层给加工框编号。编号表明该加工处在哪一层，以及上下层的父图与子图的对应关系。
第20章 通用多相流模型--60页 多相流数据后处理
20.通用多相流模型（General Multiphase Models） 本章讨论了在FLUENT中可用的通用的多相流模型。第18章提供了多相流模型的简要介绍。第19章讨论了Lagrangian离散相模型，第21章讲述了FLUENT中的凝固和熔化模型。20.1选择通用多相流模型（Choosing a General Multiphase Model） 20.2VOF模型(Volume of Fluid(VOF)Model) 20.3混合模型(Mixture Model) 20.4欧拉模型(Eulerian Model) 20.5气穴影响(Cavity Effects) 20.6设置通用多相流问题(Setting Up a General Multiphase Problem) 20.7通用多相流问题求解策略(Solution Strategies for General Multiphase Problems) 20.8通用多相流问题后处理(Postprocessing for General Multiphase Problems) 20.1选择通用的多相流模型（Choosing a General Multiphase Model） 正如在Section 18.4中讨论过的，VOF模型适合于分层的或自由表面流，而mixture和Eulerian 模型适合于流动中有相混合或分离，或者分散相的volume fraction超过10%的情形。（流动中分散相的volume fraction小于或等于10%时可使用第19章讨论过的离散相模型）。 为了在mixture模型和Eulerian模型之间作出选择，除了Section18.4中详细的指导外，你还应考虑以下几点： ★如果分散相有着宽广的分布，mixture模型是最可取的。如果分散相只集中在区域的一部分，你应当使用Eulerian模型。 ★如果应用于你的系统的相间曳力规律是可利用的（either within FLUENT or through a user-defined function），Eulerian模型通常比mixture模型能给出更精确 的结果。如果相间的曳力规律不知道或者它们应用于你的系统是有疑问的， mixture模型可能是更好的选择。 ★如果你想解一个需要计算付出较少的简单的问题，mixture模型可能是更好的选择，因为它比Eulerian模型要少解一部分方程。如果精度比计算付出更重要， Eulerian模型是更好的选择。但是请记住，复杂的Eulerian模型比mixture模型 的计算稳定性要差。 三种模型概要的讲述，包括它们各自的局限，在Sections20.1.1，20.1.2，20.1.3中给出。 三种模型详细的讲述在Sections20.2,20.3和20.4中给出。 20.1.1VOF模型的概述及局限(Overview and Limitations of the VOF Model) 概述（Overview） VOF模型通过求解单独的动量方程和处理穿过区域的每一流体的volume fraction来模拟两种或三种不能混合的流体。典型的应用包括预测， jet breakup、流体中大泡的运动（the motion of large bubbles in a liquid）、the motion of liquid after a dam break和气液界面的稳态和瞬态处理（the steady or transient tracking of any liquid-gas interface）。 局限（limitations） 下面的一些限制应用于FLUENT中的VOF模型： ★你必须使用segregated solver. VOF 模型不能用于coupled solvers. ★所有的控制容积必须充满单一流体相或者相的联合；VOF模型不允许在那些空的区域中没有任何类型的流体存在。 ★只有一相是可压缩的。
Fluent多相流模型选择与设定
1.多相流动模式 我们可以根据下面的原则对多相流分成四类： ?气-液或者液-液两相流： o 气泡流动：连续流体中的气泡或者液泡。 o 液滴流动：连续气体中的离散流体液滴。 o 活塞流动: 在连续流体中的大的气泡 o 分层自由面流动：由明显的分界面隔开的非混合流体流动。 ?气-固两相流： o 充满粒子的流动：连续气体流动中有离散的固体粒子。 o 气动输运：流动模式依赖诸如固体载荷、雷诺数和粒子属性等因素。最典型的模式有沙子的流动，泥浆流，填充床，以及各向同性流。 o 流化床：由一个盛有粒子的竖直圆筒构成，气体从一个分散器导入筒内。从 床底不断充入的气体使得颗粒得以悬浮。改变气体的流量，就会有气泡不断 的出现并穿过整个容器，从而使得颗粒在床内得到充分混合。 ?液-固两相流 o 泥浆流：流体中的颗粒输运。液-固两相流的基本特征不同于液体中固体颗 粒的流动。在泥浆流中，Stokes 数通常小于1。当Stokes数大于1 时，流动成为流化（fluidization）了的液-固流动。 o 水力运输: 在连续流体中密布着固体颗粒 o 沉降运动: 在有一定高度的成有液体的容器内，初始时刻均匀散布着颗粒物 质。随后，流体将会分层，在容器底部因为颗粒的不断沉降并堆积形成了淤 积层，在顶部出现了澄清层，里面没有颗粒物质，在中间则是沉降层，那里 的粒子仍然在沉降。在澄清层和沉降层中间，是一个清晰可辨的交界面。 ?三相流 (上面各种情况的组合) 各流动模式对应的例子如下： ?气泡流例子：抽吸，通风，空气泵，气穴，蒸发，浮选，洗刷 ?液滴流例子：抽吸，喷雾，燃烧室，低温泵，干燥机，蒸发，气冷，刷洗?活塞流例子：管道或容器内有大尺度气泡的流动 ?分层自由面流动例子：分离器中的晃动，核反应装置中的沸腾和冷凝 ?粒子负载流动例子：旋风分离器，空气分类器，洗尘器，环境尘埃流动 ?风力输运例子：水泥、谷粒和金属粉末的输运
数据流图试验
数据流图实验 一、实验目的 通过绘制数据流图掌握数据流图的基本原理，并能对简单问题进行数据流图的分析，独立地完成数据流图的分析与设计。此外，学会使用Case工具完成数据流图和系统流程图的分析与实现。 二、实验内容 实验内容如下： a)用visio绘制出如下定货系统的SFD（系统流程图）的模型。 图1 某定货系统SFD b)用visio绘制教材中分别绘制出定货系统的DFD的顶层模型、 第一层模型和第二层模型。（具体参考课本上P69~P70的图 3.4，图3.5和图3.6） c)用visio 绘制如下图所示的取款手续的数据流图。
图2 取款手续 d)请结合目前的银行柜台取款手续，对图2的取款数据流图进行 改进，绘制当前银行柜台取款过程的顶层和第一层数据流图。 三、实验结果 一张系统流程图和六张数据流图，要求把画出的系统流程图和数据流图打印后粘贴在实验报告中。实验报告一份。 四、成绩评定 该实验成绩满分5分，即占总成绩的5%。 五、附录：Visio中SFD和DFD绘制的基本使用 Step1:安装Visio，本说明书中使用的是Visio2003，大家也可下载Visio2007等新版本，如下图：（注：下图表示计算机已经安装了Visio，大家只要根据安装向导StepbyStep的完成安装即可）
图3 Visio安装 Step2: 打开visio，绘制系统的系统流程图，选择“流程图”下的“基本流程图”，先选择好图形的基本物理元素，如下图： 图4 系统流程图基本物理元素
Step3:绘制数据流之后得到完整的系统流程图（SFD） 图5 完整的系统流程图 Step4: 绘制DFD，选择“软件”中的“数据流模型图”来进行DFD 的绘制，首先也是先将基本元素选择好，如下图： 图6 顶层模型基本元素 Step5: 绘制数据流，并为数据流命名，得到课本图2.5“定货系统”完整的顶层数据流图，如下图：
巧用Solidworks零部件阵列实现链条快速建模
巧用Solidworks零部件阵列实现链条快速建模 关键字: Solidworks链传动建模零部件阵列 本文介绍了Solidworks中链条的三维造型是实现链传动建模的难点，长期以来得到了广泛的关注。利用“零部件阵列”实现了链条的快速建模，节省了大量的建模时间，为机械产品设计时的虚拟装配、干涉检查与展示交流提供了可能，具有一定的实际应用价值。 0 引言 链传动结构紧凑；没有弹性滑动和打滑，能保持准确的平均传动比；需要的张紧力小，作用于轴的压力小，可减少轴承的摩擦损失；能在温度较高、有油污等恶劣环境条件下工作；广泛用于交通运输、农业、轻工、矿山、石油化工和机床工业。 三维模型是现代机械产品设计、制造、装配、仿真等一切工作的基础。Solidworks中链条的三维造型是实现链传动建模的难点，长期以来得到了广泛的关注。目前，只有袁彬等人提出了导入全部链节进行装配的链条建模方法。这一方法让链条装配得十分美观，为以后设计链传动打下了坚实的基础。但是，这种方法链条的整体装配关系很复杂，要求计算机具有较高的硬件配置且操作比较繁锁，容易出现装配关系过定义等出错的情况。本文根据多年使用Solidworks建模昀经验，提出了建立一个链节单元，在装配体环境中利用“零部件阵列”实现链条快速建模的方法。 1 链轮建模 根据工作要求，取小链轮齿数17、大链轮齿数38、节距31.75。查机械设计手册，利用Solidworks拉伸、旋转、切除、阵列等基本造型方法可以得到主动链轮与从动链轮的零件模型，如图1-2所示。 图1 主动链轮 图2 从动链轮 2 链节建模 滚子链由内链板、外链板、销轴、套筒和滚子组成。查机械设计手册得到图3所示20A型链节相关尺寸，在SolidWorks 2010中分别将这几个零件单独进行建模然后进行装配，可以得到一个链节装配体（如图6所示）。为简化建模过程，本文的链节仅由一个内链节（如图4所示）与二个外链节（如图5所示）组成。
基于分数阶和非局部全变差模型的图像去模糊
2018年7月计算机工程与设计July 2018 第 39 卷第 7 期COMPUTERENGINEERINGANDDESIGN Vol. 39 No. 7 基于分数阶和非局部全变差模型的图像去模糊 向雨晴，杨晓梅+ (四川大学电气信息学院，四川成都610065) 摘要：为减少阶梯效应，同时更好地利用图像本身的信息，提出一种结合分数阶全变差（F O T V)和非局部全变差(N L T V)模型的非盲去模糊图像重建方法。分别用F O T V和N L T V约束由全局梯度提取法（G G ES)分解而成的平滑区和 纹理区，建立图像非盲去模糊的正则化模型，分别采用交替方向乘子法（A D M M)和分裂B re g m a n操作符（BO S)算法求 解两个子问题。充分的实验结果表明，该模型减少了平滑区的阶梯效应，更好地恢复了图像的纹理细节，验证了该模型的和算法的效。 关键词"非盲去模糊；分数阶全变差；非局部全变差；交替方向乘子法；正则化 中图法分类号：T P391.41 文献标识号：A文章编号：1000-7024 (2018)07-2002-06 doi： 10.16208/.. is s n l000-7024. 2018. 07. 034 Fractional-order and non-local total variation based image deblurring X I A N G Y u-q i n g，Y A N G X ia o-m e id (School o f E le ctrica l E ngineering and In fo rm a tio n，Sichuan U n iv e rs ity，C hengdu610065, C hina) Abstract：T o reduce the staircase a rtifa cts and use m ore in fo rm a tio n o f the b lu rre d image its e lf，an image reconstruction m ethod o f no n-b lin d d e b lu rrin g b y com bining the fra c tio n ll order t o t ll va riatio n(F O T V)and the non-local to ta l v dels was proposed.T h e F O T V and N L T V regularization w ere used to constrain the fla t and te xtu re regions decomposed thro u g h global gradient e xtra ctio n scheme(G O E S)，respectively，and a regularization o p tim ization m odel o f no n-b lin d d e b lu rrin g was constructed.A lte rn a tin g d irection m ethod o f m u ltip lie rs(A D M M)was used to solve the F O T V sub-problem s，w h ile the algo-rith m o f Bregm an operator s p littin g(B O S)was used to solve N L T V sub-problem s.L o ts o f m onstrate th a t the p roposed m ethod contains the advantages o f F O T V and N L T V，it can n o t o n ly reduce the staircase artifacts in fla t regions，b u t also reconstruct m ore te xtu re details o f the b lu rre d images.T h e fe a s ib m ethod and corresponding a lg o rith m are ve rified. Key words：non-b lin d d e b lu rrin g；fractio n a l-o rd e r to ta l v a ria tio n；non-local to ta l v a ria tio n；a lternating d irection m ethod of m u ltip lie rs；regularization /引言 作为一种基础的图像复原技术，图像去模糊广泛应用 于各个图像领域。图像模糊过程在数学上可看成模糊核和 原始清晰图像卷积运算后加噪声的操作，可表示为 f= ##$%&⑴ 式中：！表示退化图像，$表示原始清晰图像，#表示模糊 核，#表示卷积运算，&表示附加噪声。本文讨论的是已 知f* #求$的非盲去模糊逆问题，基于正则化的全变差 (T V)方法经常用于求解此类问题。L.R u d m等提出基于T V的图像R O F去噪模型，其强大的边缘保护能力使之应 用到去模糊及图像重建等领域[1’2]，但该模型会使图像产生 阶梯效应，对纹理细节的恢复也并不具有优势。 为了更好地利用图像本身的先验信息，文献％]提出 基于非局部全变差（N L T V)正则化的图像重建模型，更 好地恢复了图像纹理细节。为减少阶梯效应和避免高阶全 变差（H O T V)模型的边缘过平滑的缺点，基于T V的衍 生形式— —分数阶全变差（F O T V)模型得到提出和应 用％，]。考虑到综合利用N L T V和F O T V的优势，本文运 用全局梯度提取法（G G ES)67&把图像分成平滑和细节两 收稿日期：2017-06-02)修订日期：2017-09-01 作者简介：向雨晴（1992-），女，湖北孝感人，硕士研究生，研究方向为数字图像处理；+通讯作者：杨晓梅（1973-)，女，四川乐山人，博士，副教授，研究方向为医学图像处理、模式识别、计算机视觉。E-mail: yangxiaomei@https://www.wendangku.net/doc/ea3425911.html,
流模型
流模型 一、流模型的思想 网络流在具体问题中的应用，最关键的部分在与模型的构造。 对于调度领域中的不同问题，可以将其转化为网络流问题进行解决。通讯网络中的数据的路径选择问题，是安排一些数据包由发点到收点的传输路径。在传输网络中，数据包经过每一条边需要一单位时间，同时一条边每次仅允许一个数据包通过。目标是极小化所有数据包传送到终点时间。若该问题中，不同种类的数据包传输路径已经提前给出，那么，其类似于调度领域中的车间作业问题为: 满足如下约束： 1.工件之间不存在优先关系，一旦一个机器开始一个工件某 阶段的加工，在此次加工过程完成之前不能加工其他 工件。 2.每次每台机器只能加工一个工件，且加工过程不允许中断。 3.每个工件各阶段的加工过程必须按照事先给定的顺序在对 应的机器上进行加工。 目标函数为极小化最大完工时间。 因为在调度问题中有诸多限制条件没有完全一致的网络流模型，所以我们需要根据不同的问题构造相应的模型。对应于此处的车间作业问题，因为工件种类的多样性，我们不仅要选择工件的类型，还要安排不同工件在同一台机器上的加工顺序。对应于通讯网络中的数据
的路径选择问题，在数据包的传输过程中不仅要选择数据包的传输路径，还需要选择数据包的类型。 建好模型之后，根据其特点我们可以不仅仅拘泥于传统的解决调度问题的方法，可以与网络流问题中的方法结合，寻找速度更快、结果更好的解决方案。 二、 流模型的应用 我们以前面提到过的车间作业问题为例。问题描述如下： 在J 台机器上安排I 种工件进行加工。第i 种工件包含i J 个阶段，每 个阶段由一个特定机器进行加工，工件i 的完工时间为：属于工件类i 的工件最后一个加工阶段i J 完成的时刻。(,)i j 代表工件i 在j 阶段的 工时，用,p i j 表示。假设工件类i 的数目为i n 。传统的车间作业问题每个工件类型仅包含一个工件，即初始工件类型向量为(1,1,...1)，是传统的NP -难问题，即使例子的规模很小也很难解。 文中首先考虑车间排序问题的松弛流控制问题，在这里我们将离散的工件用连续流进行替代，这种方法源自多级排队网络的最优控制，多级排队网络的最优控制是车间排序问题的一种随机、动态的形式。其次，通过对排序问题线性规划松弛解的舍入，可以构造解决排序问题的近似算法。这是找到解决该问题整体方案的两个重要指导思想。 应用流控制问题的最优解构造一个目标值为max C O +的可行的排序，如果适当增加初始给定的工件数量，算法的最优目标值为max (1)C O +。类似的，对于通讯网络中的数据的路径选择问题提出
多级安全工作流授权模型
收稿日期:2001208213. 作者简介:洪 帆(19422),女,教授;武汉,华中科技大学计算机科学与技术学院(430074). ①Atluri V.,Huang W K.An authorization model for workflows ,proc.of the fifth european symposium on research in computer security ,1996.9 多级安全工作流授权模型 洪 帆 李 静 (华中科技大学计算机科学与技术学院) 摘要:论述了用于工作流管理系统中的工作流授权模型.针对工作流在多级安全环境下的应用,提出了一种多级安全工作流授权模型.模型增加了安全级及任务相关性的表示,对原模型的授权规则进行了改造.提出了判断可达性的算法,对新模型的终点是否可达进行了分析.关 键 词:工作流;多级安全;授权;相关性;可达性 中图分类号:TP309 文献标识码:A 文章编号:167124512(2002)0120020203 目前,工作流管理系统(WFMS )作为协调 信息资源与人力资源的手段越来越受到研究机构与产业界的重视.Atluri 等提出了一种实现动态授权的工作流授权模型①(WAM ),该模型能够根据任务的执行情况动态地授予相关权限,但该模型无法适应多级安全需求. 本文在研究了WAM 的基础上,提出了一种新的授权模型2多级安全工作流授权模型(ML S WAM ),文中对模型进行了描述及分析. 1 工作流授权模型 通常,一个工作流由若干个完成独立功能的任务构成,这些任务相互联系,具有一定的相关性,因此要以一种协同的方式进行.为了确保任务能被合法主体在任务的真正执行期间按规定权限执行,相关的工作流授权机制就应体现在工作流管理系统中.图1显示了商品销售处理的情况,某公司的商品销售包括4项任务:确认订单(w 1)、检查货款(w 2)、从仓库中提货(w 3) 和 图1 商品销售系统流程图 发送商品(w 4).当收到来自客户的一份订单时, 系统首先授权给销售部人员进行相关活动,在核 实订单及检查货款已到公司后,销售部将开出一张提货单,以提货单的形式授权给储运部从仓库中提取提货单上所标明的商品,提出了所有商品后该提货单失效,由储运部发出发货单,授权货运部将商品送至客户手中.上述情况的授权流必须与工作流进程同步,从而保证权限的实时授予与撤销. 根据WAM ,一个工作流是一个任务偏序集,即W ={w 1,w 2,…,w n },对任务的授权通过授权模版(A T )来实现.它形式化定义了任务、授权模版和授权,另外还制定了权限授予与撤消规则. 定义1 任务w i =(O P i ,Γin i ,Γout i ,[τξi ,τμi ]),式中O P i 表示w i 中的执行的操作集,Γin i A Γ表示允许输入的客体类型集,Γout i A Γ表示输出的客体类型集,[τξi ,τμi ]表示任务执行的有效期,也就是说任务必须在τξi 之后开始执行,在τμi 之前结束. 定义2 授权模版A T (w i )=(s i ,(γi ,-),pr i ),表示授予主体s i 相关权限对类型为γi 的客体进行操作pr i .一个任务可以有多个授权模版,用A T 表示授权模版集. 定义3 授权是一个四元组,即P i =(s i ,o i ,pr i ,[τb i ,τe i ]),表示在τb i 时刻授予主体s i 对客体o i 执行pr i 操作的权限,在τe i 时刻撤消其权限. 假定有任务w i =(O P i ,Γin i ,Γout i ,[τξi ,第30卷第1期 华 中 科 技 大 学 学 报(自然科学版) Vol.30 No.12002年 1月 J.Huazhong Univ.of Sci.&Tech.(Nature Science Edition ) Jan. 2002