google-code-export / umple

Automatically exported from code.google.com/p/umple
1 stars 0 forks source link

Implement a suite of graph walkng and analysis algorithms #497

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago
We need in several contexts to analyse the various graphs in an Umple model.

1. The state machine graph (nodes = states, arcs = transitions, but accounting 
for nesting)
2. The graph formed by associations (nodes = classes, interfaces, etc; arcs = 
associations)
3. The graphs (tree) formed by constraint expressions (nodes = variables, arcs 
= operators).

We need to compute numerous algorithms on these
 - Basic walking (e.g. depth first and/or breadth first, with marking of visits)
 - Enumerate cycles, simple number of cycles
 - Unreachable elements (at least in state machines)
 - Cyclomatic complexity
 - etc

Applications
  - Metrics
  - Model analysis (finding faults such as unreachable states, issue 492 )
  - Diagram drawing (improving current generators)

To do this we need a basic walking infrastructure in place first, then to 
implement the 

Original issue reported on code.google.com by TimothyCLethbridge on 4 Feb 2014 at 8:45

GoogleCodeExporter commented 9 years ago
As an example, the following will enumerate the cycles (circuits)
http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf

Original comment by TimothyCLethbridge on 5 Feb 2014 at 2:10

GoogleCodeExporter commented 9 years ago
See also issue 367

Original comment by TimothyCLethbridge on 21 Feb 2014 at 2:55