dnetwork.generator#

Level-k generators for directed phylogenetic networks.

This module provides classes and functions for working with level-k generators of directed phylogenetic networks. Generators are minimal biconnected components that represent the core structure of level-k directed phylogenetic networks. It also provides utilities for attaching leaves to generators to obtain full directed phylogenetic networks.

Main Class#

Base module for directed level-k generators.

This module provides the DirectedGenerator class for representing level-k generators of directed phylogenetic networks. Generators are minimal biconnected components that represent the core structure of level-k networks. These are not networks themselves, but simplified structures used to build networks.

class phylozoo.core.network.dnetwork.generator.base.DirectedGenerator(graph: DirectedMultiGraph[T])[source]#

Bases: object

A level-k generator for directed phylogenetic networks.

A generator is a biconnected component that represents the core structure of a level-k network. Generators use DirectedMultiGraph directly and have their own validation rules. These are not networks themselves, but simplified structures used to build networks.

Parameters:: graph (DirectedMultiGraph) – The underlying graph structure of the generator. Should be biconnected.

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph

>>> # Create a level-1 generator (root with parallel edges to hybrid node)
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])  # Parallel edges
>>> generator = DirectedGenerator(gen_graph)
>>> generator.level
1
>>> generator.hybrid_nodes
{4}

>>> # Create a level-0 generator (single node)
>>> gen_graph0 = DirectedMultiGraph()
>>> gen_graph0.add_node(1)
>>> generator0 = DirectedGenerator(gen_graph0)
>>> generator0.level
0

_graph#

Internal graph structure using DirectedMultiGraph. Warning: Do not modify directly.

Type:: DirectedMultiGraph[T]

_sides#

Cached list of sides (attachment points). Computed lazily.

Type:: list[Side] | None

__repr__() → str[source]#: String representation of the generator.

property edge_sides: list[DirEdgeSide]#

Get all edge sides of this generator.

Returns all edges in the generator as DirEdgeSide objects, including both parallel and non-parallel edges.

Returns:: List of all edges as DirEdgeSide objects.
Return type:: list[DirEdgeSide]

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])
>>> generator = DirectedGenerator(gen_graph)
>>> edge_sides = generator.edge_sides
>>> len(edge_sides) > 0
True

property graph: DirectedMultiGraph[T]#: Get the underlying graph structure.

property hybrid_nodes: set[T]#

Get all hybrid nodes of this generator.

A hybrid node is a node with in-degree >= 2.

Returns:: Set of all hybrid node identifiers.
Return type:: set[T]

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])
>>> generator = DirectedGenerator(gen_graph)
>>> hybrid_nodes = generator.hybrid_nodes
>>> 4 in hybrid_nodes
True

property hybrid_sides: list[HybridSide]#

Get all hybrid sides of this generator.

Returns all hybrid nodes (in-degree >= 2) with out-degree 0 as HybridSide objects.

Returns:: List of all hybrid nodes with out-degree 0 as HybridSide objects.
Return type:: list[HybridSide]

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])
>>> generator = DirectedGenerator(gen_graph)
>>> hybrid_sides = generator.hybrid_sides
>>> len(hybrid_sides) > 0
True

property level: int#

Get the level of this generator.

The level is the number of hybrid nodes in the generator.

Returns:: The level of the generator.
Return type:: int

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])
>>> generator = DirectedGenerator(gen_graph)
>>> generator.level
1

property non_parallel_edge_sides: list[DirEdgeSide]#

Get all non-parallel edge sides of this generator.

Returns all edges that are not part of parallel edge groups.

Returns:: List of non-parallel edge sides.
Return type:: list[DirEdgeSide]

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> # Level-1 generator with only parallel edges (no non-parallel)
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])
>>> generator = DirectedGenerator(gen_graph)
>>> non_parallel = generator.non_parallel_edge_sides
>>> len(non_parallel) == 0
True

property parallel_edge_sides: list[tuple[DirEdgeSide, ...]]#

Get tuples of parallel edge sides.

Returns groups of DirEdgeSide objects that represent parallel edges (multiple edges between the same pair of nodes).

Returns:: List of tuples, where each tuple contains DirEdgeSide objects representing parallel edges between the same pair of nodes.
Return type:: list[tuple[DirEdgeSide, …]]

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])
>>> generator = DirectedGenerator(gen_graph)
>>> parallel = generator.parallel_edge_sides
>>> len(parallel) > 0
True

property root_node: T#

Get the root node of the generator.

The root node is the unique node with in-degree 0.

Returns:: The root node identifier.
Return type:: T
Raises:: PhyloZooGeneratorDegreeError – If there is no root node or multiple root nodes.

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])
>>> generator = DirectedGenerator(gen_graph)
>>> generator.root_node
8

property sides: list[Side]#

Get all sides (attachment points) of this generator.

For level-0 (single vertex), returns a single IsolatedNodeSide for that vertex. Otherwise returns edge sides and hybrid sides.

Returns:: List of all sides (IsolatedNodeSide for level-0; DirEdgeSide and HybridSide for level >= 1).
Return type:: list[Side]

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])
>>> generator = DirectedGenerator(gen_graph)
>>> sides = generator.sides
>>> len(sides) > 0
True

validate() → None[source]#

Validate the generator structure.

Checks that:

The generator is not empty
Single node generators have no self-loops
Structural constraints (biconnected, no self-loops, acyclic)
Degree constraints (single root, no degree-1 nodes, etc.)

Raises:: ValueError – If any validation constraint is violated.

phylozoo.core.network.dnetwork.generator.base.generators_from_network(network: DirectedPhyNetwork) → Iterator[DirectedGenerator][source]#

Extract generators from a directed phylogenetic network.

This function extracts all internal blobs from the network and converts them into generators. The network must be binary and have no parallel edges.

Parameters:

network (DirectedPhyNetwork) – The directed phylogenetic network to extract generators from.

Yields:

DirectedGenerator – A generator for each internal blob in the network.

Raises:

PhyloZooNotImplementedError – If the network is not binary.
PhyloZooGeneratorWarning – If the network has parallel edges.

Examples

>>> from phylozoo.core.network.dnetwork import DirectedPhyNetwork
>>> # Level-1 network with a single hybrid node
>>> net = DirectedPhyNetwork(
...     edges=[
...         (8, 5), (8, 6),  # Root to tree nodes
...         (5, 4), (6, 4),  # Both lead to hybrid node 4
...         (4, 7),          # Hybrid to tree node
...         (5, 1), (6, 2), (7, 3), (7, 9)  # Tree nodes to leaves
...     ],
...     nodes=[
...         (1, {'label': 'A'}), (2, {'label': 'B'}),
...         (3, {'label': 'C'}), (9, {'label': 'D'})
...     ]
... )
>>> generators = list(generators_from_network(net))
>>> len(generators) > 0
True

Sides#

Side module for directed level-k generators.

This module provides the Side class and its subclasses for representing attachment points (sides) of generators.

class phylozoo.core.network.dnetwork.generator.side.DirEdgeSide(u: T, v: T, key: int)[source]#

Bases: EdgeSide

Represents a directed edge side of a generator.

A directed edge side is an edge (possibly parallel) that serves as an attachment point. The edge is identified by its endpoints and key.

Parameters:

u (T) – The source node of the edge.
v (T) – The target node of the edge.
key (int) – The edge key for parallel edges.

Examples

>>> edge_side = DirEdgeSide(u=8, v=4, key=0)
>>> edge_side.u
8
>>> edge_side.v
4
>>> edge_side.key
0

key: int#

u: T#

v: T#

class phylozoo.core.network.dnetwork.generator.side.EdgeSide[source]#

Bases: Side

Base class for edge sides (attachment along an edge).

DirEdgeSide is the concrete directed-edge implementation.

class phylozoo.core.network.dnetwork.generator.side.HybridSide(node: T)[source]#

Bases: NodeSide

Represents a hybrid node side of a generator.

A hybrid side is a node with in-degree >= 2 and out-degree 0 that serves as an attachment point. HybridSide is a NodeSide (attachment at a vertex).

Parameters:: node (T) – The node identifier for this hybrid side.

Examples

>>> hybrid_side = HybridSide(node=3)
>>> hybrid_side.node
3
>>> isinstance(hybrid_side, NodeSide)
True

class phylozoo.core.network.dnetwork.generator.side.IsolatedNodeSide(node: T)[source]#

Bases: NodeSide

Node side for the single vertex of a level-0 generator.

A level-0 generator has one vertex and no edges. IsolatedNodeSide represents that vertex as the only attachment point (as opposed to HybridSide, which is for hybrid nodes). When attaching leaves for binary networks, exactly three leaves must be attached to this side.

Parameters:: node (T) – The node identifier (the unique vertex of the level-0 generator).

Examples

>>> side = IsolatedNodeSide(node=0)
>>> side.node
0
>>> isinstance(side, NodeSide)
True

class phylozoo.core.network.dnetwork.generator.side.NodeSide(node: T)[source]#

Bases: Side

Represents a node side of a generator (attachment at a vertex).

Subclasses: IsolatedNodeSide for the single-vertex (level-0) generator; HybridSide for hybrid nodes (in-degree >= 2).

Parameters:: node (T) – The node identifier.

Examples

>>> node_side = NodeSide(node=0)
>>> node_side.node
0

node: T#

class phylozoo.core.network.dnetwork.generator.side.Side[source]#

Bases: object

Base class for sides (attachment points) of a generator.

A side is a node or an edge where additional structure (leaves, trees) can be attached when building generators from lower-level generators.

Subclasses: NodeSide (and HybridSide) for node attachment; EdgeSide and DirEdgeSide for edge attachment.

Attachment#

Attachment utilities for directed level-k generators.

This module provides functions for attaching leaves (taxa) to the sides of a DirectedGenerator to obtain a full DirectedPhyNetwork.

Leaves are generated as new nodes in the underlying DirectedMultiGraph and are attached either to node sides (NodeSide / HybridSide) or along edge sides (DirEdgeSide), depending on the side type.

phylozoo.core.network.dnetwork.generator.attachment.attach_leaves_to_generator(generator: DirectedGenerator[T], side_taxa: Mapping[Side, Sequence[str]]) → DirectedPhyNetwork[T][source]#

Attach leaves to a generator to build a binary directed phylogenetic network.

This function takes a DirectedGenerator and a mapping from sides to ordered lists of taxa. It returns a DirectedPhyNetwork obtained by attaching new leaf nodes to the generator’s underlying graph:

Every HybridSide of the generator must appear in side_taxa with exactly one taxon (cannot be omitted or empty).
Every IsolatedNodeSide (the single side when the generator has level 0) must appear in side_taxa with exactly three taxa (cannot be omitted or empty).
DirEdgeSide sides may be omitted or given an empty list; they receive no leaves.

Parameters:

generator (DirectedGenerator[T]) – The generator whose sides will receive attached leaves.
side_taxa (Mapping[Side, Sequence[str]]) – Mapping from sides of generator to ordered sequences of taxon labels. The order of taxa for each side determines the attachment order along that side. The order of sides in the mapping is not important.

Returns:

A directed phylogenetic network obtained by attaching leaves to the generator according to side_taxa.

Return type:

DirectedPhyNetwork[T]

Raises:

PhyloZooValueError – If a required side (hybrid or level-0 node side) is missing from side_taxa or has the wrong number of taxa; if fewer than two taxa are attached in total; or if a side refers to a node or edge not present in the generator.

Examples

Build a level-1 directed generator from a directed multigraph (root 0, hybrid 1, two parallel edges), then attach leaves to the hybrid and one edge side:

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> from phylozoo.core.network.dnetwork.generator.base import DirectedGenerator
>>> dmg = DirectedMultiGraph(edges=[(0, 1), (0, 1)])
>>> gen = DirectedGenerator(dmg)
>>> hybrid_side = gen.hybrid_sides[0]
>>> edge_side = gen.edge_sides[0]
>>> network = attach_leaves_to_generator(
...     gen, {hybrid_side: ["H"], edge_side: ["A", "B"]}
... )
>>> sorted(network.taxa)
['A', 'B', 'H']

Construction#

Construction module for building level-k generators from level-(k-1) generators.

This module implements the R1 and R2 transformation rules from [Gambette et al., 2009] to construct all level-k directed generators from level-(k-1) generators.

phylozoo.core.network.dnetwork.generator.construction.all_level_k_generators(k: int) → set[DirectedGenerator][source]#

Generate all (strict) level-k generators.

This function constructs all (strict) level-k generators by starting with level-0 generators and iteratively applying R1 and R2 rules from [Gambette et al., 2009].

Parameters:: k (int) – The level of generators to generate.
Returns:: Set of all level-k generators (up to isomorphism).
Return type:: set[DirectedGenerator]
Raises:: PhyloZooValueError – If level is negative.

Notes

Validation is deferred during construction for performance optimization. The algorithm provably produces valid generators, so validation is skipped by default. To validate a generator, call gen.validate() explicitly.

Examples

>>> # Get all level-1 generators
>>> level1 = all_level_k_generators(1)
>>> len(level1) == 1
True
>>> # Get all level-2 generators
>>> level2 = all_level_k_generators(2)
>>> len(level2) == 4
True

dnetwork.generator#

Main Class#

Sides#

Attachment#

Construction#

This Page