Process graph: Difference between revisions

Revision as of 22:11, 22 June 2017

Latest revision as of 21:45, 17 September 2023

(22 intermediate revisions by 13 users not shown)

Line 1:

{{short description|Type of graph used in workflow modeling}}

{{multiple issues|

In [[mathematics]] [[graph theory]] a '''process- graph''' or P-graph is a [[directed graph|directed]] [[bipartite graph]] used in [[workflow]] [[Conceptual model|modeling]].

{{Orphan|date=August 2012}}

{{context|date=November 2010}}

}}

==Description==

In [[graph theory]] a '''process-graph''' or P-graph is a [[directed graph|directed]] [[bipartite graph]] used in [[workflow]] [[Conceptual model|modeling]].

TheWith a process graph, the [[vertex (graph theory)|vertices]] of the [[Graph (discrete mathematics)|graph]] are of two types, operation (O) and material (M). The twoThese vertex types form two [[:wikt:disjunctive|disjunctive]] [[set (mathematics)|set]]s. The [[edge (geometry)|edges]] of the graph link the O and M vertices. An edge from an operation vertex (O) connects to a material vertex (M) if M is the output of O, such as a 'document' (material) that is output by a 'write-up' (operation). An edge from M to O indicates that M is an element of the input set of O, e.g. a document may be part of the input to a 'review' operation.

The [[vertex (graph theory)|vertices]] of the [[Graph (discrete mathematics)|graph]] are of two types, operation (O) and material (M). The two vertex types form two [[:wikt:disjunctive|disjunctive]] [[set (mathematics)|set]]s. The [[edge (geometry)|edges]] of the graph link the O and M vertices. An edge from an operation vertex (O) connects to a material vertex (M) if M is the output of O, such as a 'document' (material) that is output by a 'write-up' (operation). An edge from M to O indicates that M is an element of the input set of O, e.g. a document may be part of the input to a 'review' operation.

==Applications==

Process-graph is in use in different fields of application in [[Process Network Synthesis]] (PNS) .<ref>{{cite journal|last1=Friedler|first1=F.|last2=Huang|first2=Y.W.|last3=Fan|first3=L.T.|title=Combinatorial Algorithms for Process Synthesis|journal=Computers Chemical Engineering|date=1992|volume=16 |issue=Suppl. 1|issue=0|pages=313–320|doi=10.1016/S0098-1354(09)80037-9|url=http://www.sciencedirect.com/science/article/pii/S0098135409800379|accessdate=11 August 2014}}</ref> An example for an application is [[Process Network Synthesis]].<ref>{{cite book|last1=Friedler|first1=F.|title=State of the Art in Global Optimization|volume=7|last2=Varga|first2=J. B.|last3=Feher|first3=E.|last4=Fan|first4=L. T.|title=Combinatorially Accelerated Branch-and-Bound Method for Solving the MIP Model of Process Network Synthesis|date=1996|publisher=Kluwer Academic Publishers|___location=Dordrecht|pages=609–626|edition=7|isbn=978-0-7923-4351-46|url=http://dx.doi.org/=10.1007/978-1-4613-3437-8_35|chapter=Combinatorially Accelerated Branch-and-Bound Method for Solving the MIP Model of Process Network Synthesis|series=Nonconvex Optimization and Its Applications}}</ref> The method is in scientific use to find optimum process chains in chemical formulas, energy technology networks and other optimisation problems like evacuation routes in buildings or transportation routes.

Process graphs are also used in understanding the control flow of multi-threaded processes. If there are n concurrent threads running, a process graph models the execution of n concurrent threads and their trajectories through an n dimensional Cartesian plane. The origin of the graph corresponds to the initial state where none of the threads have completed an instruction. Each directed edge corresponds to the execution of an instruction and transition to other. Valid edges can either go up or right because programs cannot run backward for the edges to left or down. Since two threads can't complete the same instruction at the same time, diagonal edges are not allowed.

==References==

Line 15 ⟶ 13:

==External links==

* [https://web.archive.org/web/20140714150854/http://www.p-graph.com/wiki/index.php/Process_Graph_%28P(P-graph%29)/ P-Graph wiki]

* [http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291097-0037%28199803%2931:2%3C119::AID-NET6%3E3.0.CO;2-K/references/ Process Network Synthesis Problem Definition]