bcomps

Decompose graphs into biconnected components

TLDR

Decompose graph into biconnected components

$ bcomps [input.gv] > [output.gv]

Print number of blocks and cutvertices

$ bcomps -v [input.gv]

Print each component as separate graph

$ bcomps -x [input.gv]

Print block-cutvertex tree

$ bcomps -t [input.gv]

Write components to separate files

$ bcomps -o [output.gv] [input.gv]

Silent mode with statistics only

$ bcomps -sv [input.gv]

SYNOPSIS

bcomps [-stvx?] [-o outfile] [files]

bcomps decomposes graphs into their biconnected components, printing the components to standard output. A biconnected component is a maximal subgraph that remains connected after removal of any single vertex.The tool is part of the Graphviz graph visualization suite and works with DOT language graph files.

PARAMETERS

-s

Silent mode; no output graph printed (implies -v)

-t

Print the underlying block-cutvertex tree

-v

Print number of blocks and cutvertices

-x

Print each biconnected component as separate root graph

-o outfile

Write each root graph to different file derived from outfile

Display help information

OUTPUT FORMAT

By default, each input graph is printed with blocks as subgraphs. Subgraph names concatenate the input graph name, "bcc", and the block number.When both -o and -x are used, each block is written to a separate file. If outfile does not have a suffix, the nth block of the ith graph is written to outfileni (the 0th block of the 0th graph is written to outfile itself). If outfile has a suffix (e.g., base.sfx), the files follow the same pattern with .sfx appended. Block-cutvertex trees are written to outfilenT.

RETURN VALUES

All input graphs are biconnected

non-zero

Any graph has multiple blocks or an error occurred

INSTALL

sudo apt install graphviz

sudo dnf install graphviz

sudo pacman -S graphviz

sudo apk add graphviz

sudo zypper install graphviz

brew install graphviz

nix profile install nixpkgs#graphviz

CAVEATS

Input files must be in Graphviz DOT format. The tool identifies articulation points (cutvertices) that separate components. Large graphs may require significant processing time.