phylox.isomorphism.base

A module for checking isomorphism between phylogenetic networks and counting automorphisms of phylogenetic networks.

Currently mostly uses the networkx isomorphism checker, extended with some specifics for phylogenetic networks such as labels and partial isomorphisms.

Module Attributes

`ISOM_LABEL_ATTR`	The node attribute used to store the isomorphism label of a node.
`ISOM_LABEL_PREFIX`	The prefix used for isomorphism labels.
`AUTOMORPHISM_LABEL_PREFIX`	The prefix used for automorphism labels.

Functions

`count_automorphisms`(network[, ...])	Determines the number of automorphisms of a network.
`is_isomorphic`(network1, network2[, ...])	Determines whether two networks are labeled isomorphic.

phylox.isomorphism.base.ISOM_LABEL_ATTR = 'isomorphism_label': The node attribute used to store the isomorphism label of a node.

phylox.isomorphism.base.ISOM_LABEL_PREFIX = 'isomorphism_label_prefix_': The prefix used for isomorphism labels.

phylox.isomorphism.base.AUTOMORPHISM_LABEL_PREFIX = 'automorphism_label_prefix_': The prefix used for automorphism labels.

phylox.isomorphism.base.is_isomorphic(network1, network2, partial_isomorphism=None, ignore_labels=False, label_attr='label', use_mu_vector=False)

Determines whether two networks are labeled isomorphic.

Parameters:

network1 – a phylogenetic network, i.e., a DAG with leaf labels stored as the node attribute LABEL_ATTR.
network2 – a phylogenetic network, i.e., a DAG with leaf labels stored as the node attribute LABEL_ATTR.
partial_isomorphism – a list of node pairs, one from network1 and one from network2 each. These pairs are mapped to each other.
ignore_labels – ignore node labels (attr LABEL_ATTR) when deciding isomorphism.
label_attr – the label attr for the nodes to use instead of the default node attr LABEL_ATTR.
use_mu_vector – Compute mu-vectors for all nodes and use the fact that mu-vectors are retained by an isomorphism.

Returns:

True if the networks are labeled isomorphic, False otherwise.

Example:

>>> from phylox import DiNetwork
>>> from phylox.isomorphism.base import is_isomorphic
>>> network1 = DiNetwork(
...     edges=[(0,1),(1,2),(1,3),(2,3),(2,4),(3,5)],
...     labels=[(4, "A"), (5, "B")],
... )
>>> network2 = DiNetwork(
...     edges=[(0,1),(1,2),(1,3),(2,3),(2,5),(3,6)],
...     labels=[(5, "B"), (6, "A")],
... )
>>> is_isomorphic(network1, network2, ignore_labels=True)
True
>>> is_isomorphic(network1, network2, ignore_labels=False)
False
>>> is_isomorphic(network1, network2, partial_isomorphism=[(4,6)], ignore_labels=True)
False

phylox.isomorphism.base.count_automorphisms(network, ignore_labels=False, use_mu_vector=True)

Determines the number of automorphisms of a network.

Parameters:

network – a phylogenetic network, i.e., a DAG with leaf labels.
ignore_labels – if True, the automorphisms are counted without considering the labels of the nodes.

Returns:

the number of automorphisms of the network.

Example:

>>> from phylox import DiNetwork
>>> from phylox.isomorphism.base import count_automorphisms
>>> network = DiNetwork(
...     edges=[(-1,0), (0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)],
...     labels=[(3, "A"), (4, "B"), (5, "C"), (6, "C")],
... )
>>> count_automorphisms(network, ignore_labels=True)
8
>>> count_automorphisms(network, ignore_labels=False)
2
>>> count_automorphisms(network, ignore_labels=True, use_mu_vector=False)
8
>>> count_automorphisms(network, ignore_labels=False, use_mu_vector=False)
2