sdnetwork.generator#

Level-k generators for semi-directed phylogenetic networks.

This module provides classes for representing level-k generators of semi-directed phylogenetic networks. Generators are minimal biconnected components that represent the core structure of level-k semi-directed phylogenetic networks.

Main Class#

Base module for semi-directed level-k generators.

This module provides the SemiDirectedGenerator class for representing level-k generators of semi-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.

Unlike DirectedGenerator, SemiDirectedGenerator allows both directed and undirected edges.

class phylozoo.core.network.sdnetwork.generator.base.SemiDirectedGenerator(graph: MixedMultiGraph[T])[source]#

Bases: object

A level-k generator for semi-directed phylogenetic networks.

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

Unlike DirectedGenerator, SemiDirectedGenerator allows both directed and undirected edges.

Parameters:

graph (MixedMultiGraph) – The underlying graph structure of the generator. Should be biconnected.

Examples

>>> from phylozoo.core.primitives.m_multigraph import MixedMultiGraph
>>> # Create a generator with both directed and undirected edges
>>> gen_graph = MixedMultiGraph(
...     directed_edges=[(0, 1), (0, 1)],  # Parallel directed edges
...     undirected_edges=[(1, 2)]  # Undirected edge
... )
>>> generator = SemiDirectedGenerator(gen_graph)
>>> generator.level
1
>>> generator.hybrid_nodes
{1}
_graph#

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

Type:

MixedMultiGraph[T]

__repr__() → str[source]#

String representation of the generator.

property directed_edge_sides: list[DirEdgeSide]#

Get all directed edge sides of this generator.

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

Returns:

List of all directed edges as DirEdgeSide objects.

Return type:

list[DirEdgeSide]

property edge_sides: list[DirEdgeSide | UndirEdgeSide | BidirectedEdgeSide]#

Get all edge sides (directed, undirected, and bidirected).

Level-0 has no edges. Level-1 has one undirected self-loop (bidirected edge). Level >= 2 has directed and undirected edge sides.

Returns:

List of all edge sides.

Return type:

list[DirEdgeSide | UndirEdgeSide | BidirectedEdgeSide]

property graph: MixedMultiGraph[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 (from directed edges). Level-1 generators are one node with one undirected self-loop (bidirected edge); that node is the single hybrid.

Returns:

Set of all hybrid node identifiers.

Return type:

set[T]

Examples

>>> from phylozoo.core.primitives.m_multigraph import MixedMultiGraph
>>> gen_graph = MixedMultiGraph(directed_edges=[(0, 1), (0, 1)])
>>> generator = SemiDirectedGenerator(gen_graph)
>>> hybrid_nodes = generator.hybrid_nodes
>>> 1 in hybrid_nodes
True
property hybrid_sides: list[HybridSide]#

Get all hybrid sides of this generator.

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

Returns:

List of all hybrid nodes with out-degree 0 as HybridSide objects.

Return type:

list[HybridSide]

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.m_multigraph import MixedMultiGraph
>>> gen_graph = MixedMultiGraph(directed_edges=[(0, 1), (0, 1)])
>>> generator = SemiDirectedGenerator(gen_graph)
>>> generator.level
1
property non_parallel_directed_edge_sides: list[DirEdgeSide]#

Get all non-parallel directed edge sides of this generator.

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

Returns:

List of non-parallel directed edge sides.

Return type:

list[DirEdgeSide]

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

Get tuples of parallel directed edge sides.

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

Returns:

List of tuples, where each tuple contains DirEdgeSide objects representing parallel directed edges between the same pair of nodes.

Return type:

list[tuple[DirEdgeSide, …]]

property sides: list[Side]#

Get all sides (attachment points) of this generator.

Level-0: single node → [IsolatedNodeSide(node)]. Level-1: one node, one bidirected edge → hybrid_sides + edge_sides. Level >= 2: hybrid_sides + edge_sides.

Returns:

List of all sides.

Return type:

list[Side]

property undirected_edge_sides: list[UndirEdgeSide]#

Get all undirected edge sides (excluding the level-1 bidirected self-loop).

Level-0 has no edges. Level-1 has only the undirected self-loop, which is represented as BidirectedEdgeSide in edge_sides, not here.

Returns:

List of undirected edges with u != v.

Return type:

list[UndirEdgeSide]

validate() → None[source]#

Validate the generator structure.

A semi-directed generator is valid if it can be rooted on an edge as a directed generator. This is done by:

  1. Finding source components

  2. Finding an edge in the source component

  3. Subdividing that edge

  4. Orienting away from the subdivision vertex

  5. Checking if the result is a valid DirectedGenerator

Level-0: single node, no edges. Level-1: single node, one undirected self-loop (bidirected edge). Level >= 2: structural constraints and rootability as above.

Raises:

PhyloZooGeneratorStructureError – If any validation constraint is violated.

Sides#

Side module for semi-directed level-k generators.

This module provides UndirEdgeSide (subclass of EdgeSide) for undirected edge sides, BidirectedEdgeSide (subclass of EdgeSide) for the level-1 bidirected self-loop, and re-exports Side, NodeSide, IsolatedNodeSide, HybridSide, EdgeSide, and DirEdgeSide from the directed generator module.

class phylozoo.core.network.sdnetwork.generator.side.BidirectedEdgeSide(node: T, key: int)[source]#

Bases: EdgeSide

Represents the bidirected edge of a level-1 semi-directed generator.

A level-1 semi-directed generator is a single node with an undirected self-loop (bidirected edge). This cannot be represented as a directed self-loop in the underlying graph, so it is stored as an undirected self-loop. BidirectedEdgeSide identifies that edge by the node and the edge key.

Parameters:

  • node (T) – The single node incident to the undirected self-loop.

  • key (int) – The edge key for the undirected self-loop.

Examples

>>> side = BidirectedEdgeSide(node=0, key=0)
>>> side.node
0
>>> side.key
0
key: int#
node: T#
class phylozoo.core.network.sdnetwork.generator.side.UndirEdgeSide(u: T, v: T, key: int)[source]#

Bases: EdgeSide

Represents an undirected edge side of a generator.

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

Parameters:

  • u (T) – The first node of the edge.

  • v (T) – The second node of the edge.

  • key (int) – The edge key for parallel edges.

Examples

>>> edge_side = UndirEdgeSide(u=1, v=2, key=0)
>>> edge_side.u
1
>>> edge_side.v
2
>>> edge_side.key
0
key: int#
u: T#
v: T#

Attachment#

Attachment utilities for semi-directed level-k generators.

This module provides functions for attaching leaves (taxa) to the sides of a SemiDirectedGenerator to obtain a full semi-directed phylogenetic network (as a SemiDirectedPhyNetwork).

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

phylozoo.core.network.sdnetwork.generator.attachment.attach_leaves_to_generator(generator: SemiDirectedGenerator[T], side_taxa: Mapping[Side, Sequence[str]]) → SemiDirectedPhyNetwork[T][source]#

Attach leaves to a semi-directed generator to build a binary semi-directed network.

Takes a SemiDirectedGenerator and a mapping from sides to ordered lists of taxa. Returns a SemiDirectedPhyNetwork by attaching new leaf nodes to the generator’s underlying graph:

  • Every HybridSide must appear in side_taxa with exactly one taxon.

  • Every IsolatedNodeSide (level-0) must appear with exactly three taxa.

  • Edge sides (DirEdgeSide, UndirEdgeSide, BidirectedEdgeSide) may be omitted or given an empty list.

Parameters:

  • generator (SemiDirectedGenerator[T]) – The generator whose sides will receive attached leaves.

  • side_taxa (Mapping[Side, Sequence[str]]) – Mapping from sides to ordered sequences of taxon labels.

Returns:

A semi-directed phylogenetic network with leaves attached per side_taxa.

Return type:

SemiDirectedPhyNetwork[T]

Raises:

PhyloZooValueError – If a required side is missing 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. For a level-1 generator, the single BidirectedEdgeSide must also receive at least one taxon.

Examples

Build a level-1 semi-directed generator from a mixed multigraph (one node with an undirected self-loop), then attach leaves to the hybrid and bidirected edge sides:

>>> from phylozoo.core.primitives.m_multigraph import MixedMultiGraph
>>> from phylozoo.core.network.sdnetwork.generator.base import SemiDirectedGenerator
>>> mm = MixedMultiGraph(undirected_edges=[(1, 1)])
>>> gen = SemiDirectedGenerator(mm)
>>> hybrid_side = gen.hybrid_sides[0]
>>> bidir_side = gen.edge_sides[0]
>>> network = attach_leaves_to_generator(
...     gen, {hybrid_side: ["H"], bidir_side: ["P", "Q"]}
... )
>>> sorted(network.taxa)
['H', 'P', 'Q']

Construction#

Construction module for semi-directed level-k generators.

This module provides functions for constructing semi-directed generators from directed generators.

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

Generate all (strict) level-k semi-directed generators.

This function constructs all (strict) level-k semi-directed generators by:

  1. Getting all level-k directed generators

  2. Semi-directing each one

  3. Filtering out isomorphic generators

Parameters:

k (int) – The level of generators to generate.

Returns:

Set of all level-k semi-directed generators (up to isomorphism).

Return type:

set[SemiDirectedGenerator]

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 semi-directed generators
>>> level1 = all_level_k_generators(1)
>>> len(level1) == 1
True
>>> # Get all level-2 semi-directed generators
>>> level2 = all_level_k_generators(2)
>>> len(level2) == 2
True
phylozoo.core.network.sdnetwork.generator.construction.dgenerator_to_sdgenerator(d_generator: DirectedGenerator) → SemiDirectedGenerator[source]#

Convert a DirectedGenerator to a SemiDirectedGenerator.

This function semi-directs a directed generator by:

  1. Converting all edges to undirected, except those entering a hybrid node (a node with in-degree >= 2).

  2. Suppressing the degree-2 root node.

Parameters:

d_generator (DirectedGenerator) – The directed generator to convert.

Returns:

A new semi-directed generator with non-hybrid edges undirected and the degree-2 root suppressed.

Return type:

SemiDirectedGenerator

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> from phylozoo.core.network.dnetwork.generator.base import DirectedGenerator
>>> # Create a level-1 directed generator (root with parallel edges to hybrid)
>>> gen_graph = DirectedMultiGraph(edges=[(8, 4), (8, 4)])
>>> d_gen = DirectedGenerator(gen_graph)
>>> sd_gen = dgenerator_to_sdgenerator(d_gen)
>>> sd_gen.level
1
>>> # Level-1 is represented as one node with one undirected self-loop (bidirected edge)
>>> sd_gen.graph.number_of_nodes()
1
>>> sd_gen.graph.number_of_edges()
1
>>> list(sd_gen.graph.undirected_edges_iter(keys=True))
[(4, 4, 0)]