# US 8,786,602 B2 · System and method for hierarchically decomposing process model

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,786,602 B2
- Document ID: US8786602B2
- Status: Granted
- Kind: B2
- Application number: 12/241,195
- Filed: 2008-09-30
- Published: 2010-04-01
- Granted: 2014-07-22
- Earliest claimed: 2008-09-30
- Assignees: International Business Machines Corporation
- Applicants: Jana Koehler; Simon Danie Moser; Jussi H. Vanhatalo; Hagen Voelzer
- Inventors: Jana Koehler; Simon Danie Moser; Jussi H. Vanhatalo; Hagen Voelzer
- Web page: https://patentgrep.com/patent/US8786602B2

## CPC

- G06T 11/26: Drawing of charts or graphs
- G06T 11/23: using straight lines or curves
- G06T 11/40: Filling planar surfaces by adding surface attributes, e.g. adding colours or textures
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A system and associated method for hierarchically decomposing a workflow graph G into a process structure tree PST. The workflow graph G is a two-terminal graph parsed into a tree T having triconnected components. Boundary pairs of all triconnected components in T are computed and fragments are discovered with boundary pairs. T is restructured into PST pursuant to categories of triconnected components in T. PST is deterministic and modular. PST represents a block-based process model that has fine blocks of execution units. PST is computed in time linear to the number of edges in G.

## Claims

### Claim 1

A method for hierarchically decomposing a two-terminal graph G into a process structure tree PST, the method comprising:
parsing G into a tree T comprising triconnected components;
finding all existing fragments from the triconnected components in T;
restructuring T such that PST consists of restructured T, and
transmitting PST to an output device of a computer system,
wherein G is defined as a two-terminal graph that is a directed graph without self-loops such that there is at most one source node s of G, and at most one sink node t of G, wherein t≠s and each node of G is on a directed path from s to t,
wherein a triconnected component of said triconnected components is a bond, a polygon, or a 3-connected graph, and each triconnected component determines a respective boundary pair comprising two boundary nodes,
wherein the respective boundary pair determines a respective fragment F of G, wherein F is a connected subgraph of G that has said two boundary nodes as an entry of F and an exit of F,
wherein PST is a tree of canonical fragments of G such that a parent P of a canonical fragment of said canonical fragments is the smallest canonical fragment of G that properly contains the canonical fragment, and
wherein the canonical fragment is a fragment of a program that does not overlap with any other fragment of the program, and wherein the program is executable by a microprocessor.

### Claim 2 (depends on 1)

The method of claim 1, said finding comprising:
selecting, in an order according to a post-order traversal of T, a triconnected component TCC of said triconnected components in T that is not previously selected by said selecting;
computing an outgoing edge count and an incoming edge count for each boundary node of two boundary nodes of TCC;
updating an incoming edge count and an outgoing edge count for each boundary node of two boundary nodes of a parent of TCC with a result from said computing; and
determining that a first boundary node of said two boundary nodes of TCC is an entry of TCC and that a second boundary node of said two boundary nodes of TCC is an exit of TCC and consequently determining that TCC is a fragment.

### Claim 3 (depends on 1)

The method of claim 1, said finding comprising:
selecting, in an order according to a post-order traversal of T, a triconnected component TCC of said triconnected components in T that is not previously selected by said selecting;
computing an outgoing edge count and an incoming edge count for each boundary node of two boundary nodes of TCC;
updating an incoming edge count and an outgoing edge count for each boundary node of two boundary nodes of a parent of TCC with a result from said computing;
determining that TCC does not comprise either an entry or an exit, followed by determining that TCC is not a fragment;
determining that the parent of TCC is a polygon and subsequently counting entries and exits of all children of the parent; and
determining that TCC is a polygon and subsequently ordering all children of TCC.

### Claim 4 (depends on 1)

The method of claim 1, said finding comprising:
selecting, in an order according to a post-order traversal of T, a triconnected component TCC of said triconnected components in T that is not previously selected by said selecting;
computing an outgoing edge count and an incoming edge count for each boundary node of two boundary nodes of TCC;
updating an incoming edge count and an outgoing edge count for each boundary node of two boundary nodes of a parent of TCC with a result from said computing;
determining that TCC does not comprise either an entry or an exit, followed by determining that TCC is not a fragment;
determining that the parent of TCC is not a polygon and subsequently determining that TCC is a polygon; and
ordering all children of TCC that is determined to be a polygon.

### Claim 5 (depends on 1)

The method of claim 1, said finding comprising:
selecting, in an order according to a post-order traversal of T, a triconnected component TCC of said triconnected components in T that is not previously selected by said selecting;
computing an outgoing edge count and an incoming edge count for each boundary node of two boundary nodes of TCC;
updating an incoming edge count and an outgoing edge count for each boundary node of two boundary nodes of a parent of TCC with a result from said computing;
determining that TCC does not comprise either an entry or an exit, followed by determining that TCC is not a fragment; and
determining that the parent of TCC is not a polygon and subsequently determining that TCC is not a polygon.

### Claim 6 (depends on 1)

The method of claim 1, said restructuring comprising:
creating a list of children of a component C upon which said restructuring is performed;
confirming that the children of C in the list are already restructured by said restructuring;
determining that C is a polygon and that C is a fragment;
adding a child of C for each child of C that is not merged to another child of C.

### Claim 7 (depends on 1)

The method of claim 1, said restructuring comprising:
creating a list of children of a component C upon which said restructuring is performed;
confirming that the children of C in the list are already restructured by said restructuring;
determining that C is a polygon and that C is not a fragment;
adding a maximal sequence of C for each child of C that is not merged to another child of C.

### Claim 8 (depends on 1)

The method of claim 1, said restructuring comprising:
creating a list of children of a component C upon which said restructuring is performed;
confirming that the children of C in the list are already restructured by said restructuring;
determining that C is a bond and that C is a maximal fragment;
categorizing branches of C by a direction of the branches, wherein C comprises a maximal directed bond fragment, a maximal undirected bond fragment, a maximal semi-pure bond fragment, and/or a maximal pure bond fragment;
discovering the maximal semi-pure bond fragment; and
creating a substructure of C by adding reverse pure branches as children of C, adding a pure bond fragment as a child of a member, adding the maximal semi-pure bond fragment as a child of the maximal undirected bond fragment or C, and adding the maximal undirected bond fragment as a child of C,
wherein the member is selected from the group consisting of the discovered maximal semi-pure bond fragment, the maximal directed bond fragment, and C.

### Claim 9 (depends on 1)

The method of claim 1, said restructuring comprising:
creating a list of children of a component C upon which said restructuring is performed;
confirming that the children of C in the list are already restructured by said restructuring;
determining that C is a bond and that C is not a fragment, wherein C comprises two maximal pure bond fragments and one maximal semi-pure bond fragment;
categorizing branches of C by a direction of the branches, wherein C comprises a directed bond fragment, a undirected bond fragment, a semi-pure bond fragment, and/or a pure bond fragment;
discovering the semi-pure bond fragment; and
creating a substructure of C by adding a pure bond fragment of said two pure bond fragments as a child of the discovered semi-pure bond fragment, adding a reverse pure bond fragment as a child of C, adding the semi-pure bond fragment as a child of C, and adding all descendant fragments of undirected branches of C as children of C.

### Claim 10

An apparatus comprising a computer program product, said computer program product comprising a computer readable storage medium having a computer readable program code embodied therein, said computer readable program code containing instructions configured to be executed by a processor of a computer system to implement a method for hierarchically decomposing a two-terminal graph G into a process structure tree PST, the method comprising:
parsing G into a tree T comprising triconnected components;
finding all existing fragments from the triconnected components in T;
restructuring T such that PST consists of restructured T, and
transmitting PST to an output device of a computer system,
wherein G is defined as a two-terminal graph that is a directed graph without self-loops such that there is at most one source node s of G, and at most one sink node t of G, wherein t≠s and each node of G is on a directed path from s to t,
wherein a triconnected component of said triconnected components is a bond, a polygon, or a 3-connected graph, and each triconnected component determines a respective boundary pair comprising two boundary nodes,
wherein the respective boundary pair determines a respective fragment F of G, wherein F is a connected subgraph of G that has said two boundary nodes as an entry of F and an exit of F,
wherein PST is a tree of canonical fragments of G such that a parent P of a canonical fragment of said canonical fragments is the smallest canonical fragment of G that properly contains the canonical fragment, and
wherein the canonical fragment is a fragment of a program that does not overlap with any other fragment of the program, and wherein the program is executable by a microprocessor.

### Claim 11 (depends on 10)

The apparatus of claim 10, said finding comprising:
selecting, in an order according to a post-order traversal of T, a triconnected component TCC of said triconnected components in T that is not previously selected by said selecting;
computing an outgoing edge count and an incoming edge count for each boundary node of two boundary nodes of TCC;
updating an incoming edge count and an outgoing edge count for each boundary node of two boundary nodes of a parent of TCC with a result from said computing; and
determining that a first boundary node of said two boundary nodes of TCC is an entry of TCC and that a second boundary node of said two boundary nodes of TCC is an exit of TCC and consequently determining that TCC is a fragment.

### Claim 12 (depends on 10)

The apparatus of claim 10, said finding comprising:
selecting, in an order according to a post-order traversal of T, a triconnected component TCC of said triconnected components in T that is not previously selected by said selecting;
computing an outgoing edge count and an incoming edge count for each boundary node of two boundary nodes of TCC;
updating an incoming edge count and an outgoing edge count for each boundary node of two boundary nodes of a parent of TCC with a result from said computing;
determining that TCC does not comprise either an entry or an exit, followed by determining that TCC is not a fragment;
determining that the parent of TCC is a polygon and subsequently counting entries and exits of all children of the parent; and
determining that TCC is a polygon and subsequently ordering all children of TCC.

### Claim 13 (depends on 10)

The apparatus of claim 10, said finding comprising:
selecting, in an order according to a post-order traversal of T, a triconnected component TCC of said triconnected components in T that is not previously selected by said selecting;
computing an outgoing edge count and an incoming edge count for each boundary node of two boundary nodes of TCC;
updating an incoming edge count and an outgoing edge count for each boundary node of two boundary nodes of a parent of TCC with a result from said computing;
determining that TCC does not comprise either an entry or an exit, followed by determining that TCC is not a fragment;
determining that the parent of TCC is not a polygon and subsequently determining that TCC is a polygon; and
ordering all children of TCC that is determined to be a polygon.

### Claim 14 (depends on 10)

The apparatus of claim 10, said finding comprising:
selecting, in an order according to a post-order traversal of T, a triconnected component TCC of said triconnected components in T that is not previously selected by said selecting;
computing an outgoing edge count and an incoming edge count for each boundary node of two boundary nodes of TCC;
updating an incoming edge count and an outgoing edge count for each boundary node of two boundary nodes of a parent of TCC with a result from said computing;
determining that TCC does not comprise either an entry or an exit, followed by determining that TCC is not a fragment; and
determining that the parent of TCC is not a polygon and subsequently determining that TCC is not a polygon.

### Claim 15 (depends on 10)

The apparatus of claim 10, said restructuring comprising:
creating a list of children of a component C upon which said restructuring is performed;
confirming that the children of C in the list are already restructured by said restructuring;
determining that C is a polygon and that C is a fragment;
adding a child of C for each child of C that is not merged to another child of C.

### Claim 16 (depends on 10)

The apparatus of claim 10, said restructuring comprising:
creating a list of children of a component C upon which said restructuring is performed;
confirming that the children of C in the list are already restructured by said restructuring;
determining that C is a polygon and that C is not a fragment;
adding a maximal sequence of C for each child of C that is not merged to another child of C.

### Claim 17 (depends on 10)

The apparatus of claim 10, said restructuring comprising:
creating a list of children of a component C upon which said restructuring is performed;
confirming that the children of C in the list are already restructured by said restructuring;
determining that C is a bond and that C is a maximal fragment;
categorizing branches of C by a direction of the branches, wherein C comprises a maximal directed bond fragment, a maximal undirected bond fragment, a maximal semi-pure bond fragment, and/or a maximal pure bond fragment;
discovering the maximal semi-pure bond fragment; and
creating a substructure of C by adding reverse pure branches as children of C, adding a pure bond fragment as a child of a member, adding the maximal semi-pure bond fragment as a child of the maximal undirected bond fragment or C, and adding the maximal undirected bond fragment as a child of C,
wherein the member is selected from the group consisting of the discovered maximal semi-pure bond fragment, the maximal directed bond fragment, and C.

### Claim 18 (depends on 10)

The apparatus of claim 10, said restructuring comprising:
creating a list of children of a component C upon which said restructuring is performed;
confirming that the children of C in the list are already restructured by said restructuring;
determining that C is a bond and that C is not a fragment, wherein C comprises two maximal pure bond fragments and one maximal semi-pure bond fragment;
categorizing branches of C by a direction of the branches, wherein C comprises a directed bond fragment, a undirected bond fragment, a semi-pure bond fragment, and/or a pure bond fragment;
discovering the semi-pure bond fragment; and
creating a substructure of C by adding a pure bond fragment of said two pure bond fragments as a child of the discovered semi-pure bond fragment, adding a reverse pure bond fragment as a child of C, adding the semi-pure bond fragment as a child of C, and adding all descendant fragments of undirected branches of C as children of C.

### Claim 19 (depends on 10)

The apparatus of claim 10, wherein the apparatus comprises the computer system, and wherein the computer system comprises the computer program product.