Archeometer v0.5.0

Archeometer.Analysis.DSM (Archeometer v0.5.0)

Defines algorithms for Design Structure Matrix (DSM) analysis.

A DSM represents a graph of dependencies between components or processes, in this case, between Elixir modules.

See DSM Web.

In this implementation, the DSM is represented by the DSM struct, with the following attributes:

  • nodes. A List of of nodes that besides enumerating the nodes, defines at the same time the order of rows and columns. They have always the same order.
  • edges. The edges of the graph, in the form of a map, with a key representing existing edges within the matrix in the form of {row, col}, and values can be one of :+ or :*. :+ is used when row and col have the same value, and :* is used whenever the module represented by col has a dependency on module represented by row.
  • groups. Its a map of identified cyclic groups within the graph, every key is just an identifier for the gruop, and the value is a list of the nodes conforming that gruop. The value of groups is calculated by the algorithm and not expected to be set by the user.
  • n_groups. This is used for internal use of the algorithms only and not expected to be of any use to final users.

Functions gen_dsm/1 and gen_dsm/4 are used to create a DSM respectively from an adjacency list or from information in an Archeometer database.

The only analysis algorith currently implemented is called triangularization, and you can use it with the function triangularize/1. It helps you find groups of nodes that form cycles.

Link to this section Summary

Functions

cyclic_deps_groups(dsm)

Gets a list of module groups with cyclic dependencies.

find_cycle(mtx)
gen_dsm(xrefs)

Creates a DSM from an adjacency list

gen_dsm(app, namespace, db_name \\ Archeometer.Repo.default_db_name(), skip_tests \\ true)

Generates a DSM using module xref information from an Archeometer DB.

largest_cyclic_deps_group(a, b)

Gets the largest group of modules with cyclical dependencies from a triangularized DSM.

leaves(mtx)

Finds the leave nodes in a DSM.

roots(mtx)

Finds the root nodes in a DSM.

triangularize(mtx)

Reorders a DSM to find dependency cycles.

Link to this section Functions

Link to this function

cyclic_deps_groups(dsm)

Gets a list of module groups with cyclic dependencies.

Link to this function

find_cycle(mtx)

Link to this function

gen_dsm(xrefs)

Creates a DSM from an adjacency list

examples

 Examples 

iex> adj_list = %{
...>   1 => [2, 3],
...>   2 => [3, 4],
...>   3 => [4],
...>   4 => [3]
...> }
%{1 => [2, 3], 2 => [3, 4], 3 => [4], 4 => [3]}
iex> Archeometer.Analysis.DSM.gen_dsm(adj_list)
%Archeometer.Analysis.DSM{
  edges: %{
    {1, 1} => :+,
    {2, 1} => :*,
    {2, 2} => :+,
    {3, 1} => :*,
    {3, 2} => :*,
    {3, 3} => :+,
    {3, 4} => :*,
    {4, 2} => :*,
    {4, 3} => :*,
    {4, 4} => :+
  },
  groups: %{},
  n_groups: 0,
  nodes: [1, 2, 3, 4]
}
Link to this function

gen_dsm(app, namespace, db_name \\ Archeometer.Repo.default_db_name(), skip_tests \\ true)

Generates a DSM using module xref information from an Archeometer DB.

parameters

 Parameters

  • app is an application name, in the case of an umbrella project, it's the name of one of the child applications.
  • namespace is a "namespace" to narrow the set of modules considered for createing the DSM. The term "namespace" is meant very broadly since Elixir doesn't have that concept. Namespace can be interpreted as a string matching the beginning of the module names to be considered, such as "Foo" or "Foo.Bar", after which a last part of the name must be given to create a full module name. For example the "namespace" Foo will include in the analysis modules such as Foo.Bar and Foo.Baz but not FooBar or Food.
  • db_name is the name of the database file to be used.
  • skip_tests is a boolean indicating if test related modules should be skipped.

examples

 Examples

Using Archeometer provided test database.

iex> Archeometer.Analysis.DSM.gen_dsm(
...>  "jissai",
...>  "Jissai.Reports",
...>  "./test/resources/db/archeometer_jissai.db",
...>  true
...>)
{:ok,
 %Archeometer.Analysis.DSM{
   edges: %{
     {21, 21} => :+,
     {22, 21} => :*,
     {22, 22} => :+,
     {23, 21} => :*,
     {23, 23} => :+,
     {24, 21} => :*,
     {24, 24} => :+
   },
   groups: %{},
   n_groups: 0,
   nodes: [21, 22, 23, 24]
 },
 %{
   21 => "Jissai.Reports",
   22 => "Jissai.Reports.Attendance",
   23 => "Jissai.Reports.ClassDynamic",
   24 => "Jissai.Reports.Participant"
 }}
Link to this function

largest_cyclic_deps_group(a, b)

Gets the largest group of modules with cyclical dependencies from a triangularized DSM.

If both arguments are maps, then it is assumed they are the DSM and the modules.

Otherwise there are treated as the namespace and the database name, and will perfom an extra query to get the DSM and the modules.

Link to this function

leaves(mtx)

Finds the leave nodes in a DSM.

Leave nodes are the ones that no dependencies upon other nodes.

Link to this function

roots(mtx)

Finds the root nodes in a DSM.

Root nodes are the ones that no othe node has dependencies upon.

Link to this function

triangularize(mtx)

Reorders a DSM to find dependency cycles.

The cycles are identified in the groups attribute of the resulting DSM.

examples

 Examples

A DSM with one cycle

iex> dsm = %Archeometer.Analysis.DSM{
...>   edges: %{
...>     {1, 1} => :+,
...>     {2, 1} => :*,
...>     {2, 2} => :+,
...>     {3, 1} => :*,
...>     {3, 2} => :*,
...>     {3, 3} => :+,
...>     {3, 4} => :*,
...>     {4, 2} => :*,
...>     {4, 3} => :*,
...>     {4, 4} => :+
...>   },
...>   groups: %{},
...>   n_groups: 0,
...>   nodes: [1, 2, 3, 4]
...> }
iex> Archeometer.Analysis.DSM.triangularize(dsm)
%Archeometer.Analysis.DSM{
  edges: %{
    {1, 1} => :+,
    {2, 1} => :*,
    {2, 2} => :+,
    {3, 1} => :*,
    {3, 2} => :*,
    {3, 3} => :+,
    {3, 4} => :*,
    {4, 2} => :*,
    {4, 3} => :*,
    {4, 4} => :+
  },
  groups: %{"g1" => [3, 4]},
  n_groups: 1,
  nodes: [1, 2, 3, 4]
}

As you can see, it detected the only existing cycle, formed by nodes [3, 4]. The nodes of the DSM are reordered such that the only nodes above the diagonal, are the ones forming part of a cycle.

Now a DSM with two cycles

iex> dsm = %Archeometer.Analysis.DSM{
...>   edges: %{
...>     {1, 1} => :+,
...>     {2, 1} => :*,
...>     {2, 2} => :+,
...>     {2, 3} => :*,
...>     {3, 1} => :*,
...>     {3, 2} => :*,
...>     {3, 3} => :+,
...>     {4, 4} => :+,
...>     {4, 5} => :*,
...>     {5, 4} => :*,
...>     {5, 5} => :+
...>   },
...>   groups: %{},
...>   n_groups: 0,
...>   nodes: [1, 2, 3, 4, 5]
...> }
iex> Archeometer.Analysis.DSM.triangularize(dsm)
%Archeometer.Analysis.DSM{
  edges: %{
    {1, 1} => :+,
    {2, 1} => :*,
    {2, 2} => :+,
    {2, 3} => :*,
    {3, 1} => :*,
    {3, 2} => :*,
    {3, 3} => :+,
    {4, 4} => :+,
    {4, 5} => :*,
    {5, 4} => :*,
    {5, 5} => :+
  },
  groups: %{"g1" => [2, 3], "g2" => [4, 5]},
  n_groups: 2,
  nodes: [1, 2, 3, 4, 5]
}

It correctly detects the two cycles: [2, 3] and [4, 5].

Now a DSM with a cycle of 3 nodes

iex> dsm = %Archeometer.Analysis.DSM{
...>   edges: %{
...>     {1, 1} => :+,
...>     {2, 1} => :*,
...>     {2, 2} => :+,
...>     {2, 4} => :*,
...>     {3, 2} => :*,
...>     {3, 3} => :+,
...>     {4, 3} => :*,
...>     {4, 4} => :+
...>   },
...>   groups: %{},
...>   n_groups: 0,
...>   nodes: [1, 2, 3, 4]
...> }
iex> Archeometer.Analysis.DSM.triangularize(dsm)
%Archeometer.Analysis.DSM{
  edges: %{
    {1, 1} => :+,
    {2, 1} => :*,
    {2, 2} => :+,
    {2, 4} => :*,
    {3, 2} => :*,
    {3, 3} => :+,
    {4, 3} => :*,
    {4, 4} => :+
  },
  groups: %{"g1" => [2, 3, 4]},
  n_groups: 1,
  nodes: [1, 2, 3, 4]
}

The cycle is correctly detected: [2, 3, 4].