Skip to content

About

Modular decomposition of directed graphs

Resources

Stars

14 stars

Watchers

1 watching

Forks

Latest commit

 

History

38 Commits

Folders and files

Repository files navigation

GraphModularDecomposition.jl

This package implements modular decomposition of directed graphs using algorithms from the following papers:

  • Habib, Paul & Viennot 1999: "Partition refinement techniques: an interesting algorithmic tool kit"
  • Capelle, Habib & de Montgolfier 2002: "Graph decompositions and factorizing permutations"
  • McConnell & Montgolfier 2004: "Linear-time modular decomposition of directed graphs"
  • Habib & Paul 2009: "A survey on algorithmic aspects of modular decomposition"

The strong module tree construction code uses an efficient and novel (to me at least) approach to manipulating trees: instead of building tree data structures explicitly, since the tree operations always keep the leaves in the same order, it works with counts of how many open and close "parentheses" occur before and after each node, thereby implicitly maintaining a tree structure by changing how nodes are parenthesized. This technique allows allocating linear storage once at the start of the algorithm, rather than needing to continually allocate and free tree data structures. The entire computation is done by incrementing and decrementing a few vectors of per-node "parens" counters. Only at the end when the final tree structure is determined is an actual tree created.

About

Modular decomposition of directed graphs

Resources

Stars

14 stars

Watchers

1 watching

Forks

Releases

Packages

Used by

Contributors

Languages