Mixed Multi-Graphs#

The phylozoo.core.primitives.m_multigraph module provides the MixedMultiGraph class, a mixed multigraph that supports both directed and undirected edges with parallel edges of both types. It serves as the foundation for SemiDirectedPhyNetwork and enables representation of phylogenetic networks with both tree-like and reticulate evolutionary relationships.

All classes and functions on this page can be imported from the mixed multigraph submodule:

from phylozoo.core.primitives.m_multigraph import MixedMultiGraph

Working with Mixed Multi-Graphs#

Creating and modifying mixed multi-graphs#

Mixed multi-graphs support both directed and undirected edges in one structure. You specify directed and undirected edge lists separately; between any given pair of nodes, edges must be either all directed or all undirected (mutual exclusivity). Parallel edges are allowed for both types.

Creating

Use directed_edges and undirected_edges as lists of (u, v) tuples or dicts with u and v. You can pass only one of them for a graph that is fully directed or fully undirected.

from phylozoo.core.primitives.m_multigraph import MixedMultiGraph

empty_graph = MixedMultiGraph()
tree_graph = MixedMultiGraph(undirected_edges=[(1, 2), (2, 3), (3, 4)])
network_graph = MixedMultiGraph(directed_edges=[(1, 2), (1, 3), (2, 4), (3, 4)])
mixed_graph = MixedMultiGraph(
    directed_edges=[(1, 3), (2, 3)],
    undirected_edges=[(3, 4), (4, 5), (4, 6)]
)

Optional nodes and attributes let you attach node or graph-level metadata:

attributed_graph = MixedMultiGraph(
    directed_edges=[{'u': 1, 'v': 2, 'weight': 1.0, 'type': 'hybrid'}],
    undirected_edges=[{'u': 2, 'v': 3, 'length': 0.5, 'bootstrap': 95}]
)
labeled_graph = MixedMultiGraph(
    directed_edges=[(1, 2)],
    undirected_edges=[(2, 3)],
    nodes=[{'id': 1, 'label': 'A'}, {'id': 2, 'label': 'B'}, {'id': 3, 'label': 'C'}]
)

Tip

For graphs without parallel edges, you can build or manipulate them in NetworkX (e.g. networkx.Graph or networkx.DiGraph) and then convert to MixedMultiGraph. See the NetworkX conversion section below.

Directed edges

Add or remove directed edges with add_directed_edge() and remove_directed_edge(); each edge has a unique key.

key1 = mixed_graph.add_directed_edge(1, 2, weight=1.0, type='reticulation')
key2 = mixed_graph.add_directed_edge(1, 2, weight=2.0)
mixed_graph.remove_directed_edge(1, 2, key=key1)

Batch operations for directed edges: add_directed_edges_from() and remove_directed_edges_from().

mixed_graph.add_directed_edges_from([(1, 4), (2, 4)])
mixed_graph.remove_directed_edges_from([(1, 4)])

Undirected edges

Undirected edges are added with add_undirected_edge() and removed with remove_edge() (which applies to undirected edges between the given pair). Parallel undirected edges are supported.

key3 = mixed_graph.add_undirected_edge(2, 3, length=0.5, bootstrap=95)
key4 = mixed_graph.add_undirected_edge(2, 3, length=0.7, bootstrap=87)
mixed_graph.remove_edge(2, 3, key=key3)

Batch operations for undirected edges: add_undirected_edges_from() and remove_edges_from().

mixed_graph.add_undirected_edges_from([(4, 5), (5, 6)])
mixed_graph.remove_edges_from([(5, 6)])

Mutual exclusivity

Between the same pair of nodes, all edges must be either directed or undirected. Adding a directed edge between a pair that currently has undirected edges (or the reverse) replaces those edges with the new type.

graph = MixedMultiGraph()
graph.add_undirected_edge(1, 2, weight=1.0)
graph.add_directed_edge(1, 2, weight=2.0)  # Replaces the undirected edge
assert graph.has_directed_edge(1, 2) and not graph.has_undirected_edge(1, 2)

Node operations

Nodes are added with optional attributes; the nodes view gives attribute access by node.

mixed_graph.add_node(5, label='taxon_A', type='leaf', support=100)
node_attrs = mixed_graph.nodes[5]
in_degree = mixed_graph.indegree(3)
out_degree = mixed_graph.outdegree(1)
undirected_degree = mixed_graph.undirected_degree(3)
total_degree = mixed_graph.degree(3)

You can add or remove multiple nodes with add_nodes_from(), remove_node(), and remove_nodes_from(), and generate_node_ids() returns an iterator of fresh integer IDs.

mixed_graph.add_nodes_from([7, 8, 9], type='internal')
mixed_graph.remove_node(9)

Accessing graph structure

Use number_of_nodes() and number_of_edges() for counts. The directed_edges and undirected_edges views yield (u, v, key) tuples; edges returns all edges. neighbors() returns all nodes adjacent to a vertex (via any edge type).

num_nodes = mixed_graph.number_of_nodes()
num_edges = mixed_graph.number_of_edges()
directed_edges = list(mixed_graph.directed_edges())
undirected_edges = list(mixed_graph.undirected_edges())
all_edges = list(mixed_graph.edges())
neighbors = list(mixed_graph.neighbors(3))

Use has_edge() for edge membership (optionally with a key). For edges incident to a vertex, use incident_parent_edges(), incident_child_edges(), and incident_undirected_edges(). copy() returns a shallow copy; clear() removes all nodes and edges.

mixed_graph.has_edge(1, 3, key=0)
incoming = list(mixed_graph.incident_parent_edges(3, keys=True))
outgoing = list(mixed_graph.incident_child_edges(1, keys=True))
undir_at_3 = list(mixed_graph.incident_undirected_edges(3))
graph_copy = mixed_graph.copy()
graph_copy.clear()

File Input/Output#

Mixed multi-graphs support reading and writing in PhyloZoo DOT format (default), which preserves the directed/undirected edge distinction:

PhyloZoo DOT (default): Extended DOT format for mixed graphs — see DOT format

# Load from file (auto-detects format by extension)
mixed_graph = MixedMultiGraph.load("phylogenetic_network.pzdot")

# Load with explicit format
mixed_graph = MixedMultiGraph.load("network.txt", format="phylozoo-dot")

# Save to file
mixed_graph.save("output.pzdot")

Graph Analysis Features#

Mixed multi-graphs provide specialized algorithms for phylogenetic network analysis.

Connectivity

The is_connected() function checks weak connectivity (ignoring edge directions).

The number_of_connected_components() function counts the number of connected components.

The connected_components() function returns an iterator over all connected components.

from phylozoo.core.primitives.m_multigraph.features import (
    is_connected, number_of_connected_components, connected_components
)

# Check weak connectivity (ignoring edge directions)
connected = is_connected(mixed_graph)

# Count connected components
num_components = number_of_connected_components(mixed_graph)

# Get all connected components
for component in connected_components(mixed_graph):
    print(f"Component: {component}")

Source components

The source_components() function finds source components (nodes with no incoming directed edges), which is important for phylogenetic network analysis.

from phylozoo.core.primitives.m_multigraph.features import source_components

# Find source components (no incoming directed edges)
sources = source_components(mixed_graph)  # List of (nodes, directed_edges, undirected_edges) tuples

Biconnectivity

The biconnected_components() function returns an iterator over biconnected components.

The bi_edge_connected_components() function returns an iterator over bi-edge-connected components.

from phylozoo.core.primitives.m_multigraph.features import (
    biconnected_components, bi_edge_connected_components
)

# Get biconnected components
for component in biconnected_components(mixed_graph):
    print(f"Biconnected component: {component}")

# Get bi-edge-connected components
for component in bi_edge_connected_components(mixed_graph):
    print(f"Bi-edge-connected component: {component}")

Cut edges and vertices

The cut_edges() function finds all cut edges.

The cut_vertices() function finds all cut vertices.

from phylozoo.core.primitives.m_multigraph.features import cut_edges, cut_vertices

# Find cut edges
cuts = cut_edges(mixed_graph)  # Returns list of (u, v, key) tuples

# Find cut vertices
cut_nodes = cut_vertices(mixed_graph)  # Returns set of nodes

Up-down paths

The updown_path_vertices() function finds all vertices that lie on an up-down path between two given vertices (a path that first goes up via directed edges, then down via directed edges).

from phylozoo.core.primitives.m_multigraph.features import updown_path_vertices

# Find vertices on up-down paths between x and y
vertices = updown_path_vertices(mixed_graph, x=1, y=5)

Parallel edges and self-loops

The has_parallel_edges() function checks if the graph contains any parallel edges.

The has_self_loops() function checks for edges connecting a node to itself.

from phylozoo.core.primitives.m_multigraph.features import (
    has_parallel_edges, has_self_loops
)

# Check for parallel edges
has_parallel = has_parallel_edges(mixed_graph)

# Check for self-loops
has_loops = has_self_loops(mixed_graph)

Isomorphism

The is_isomorphic() function compares graph structures while respecting the mixed edge types, checking if two graphs have the same topology regardless of node labeling.

from phylozoo.core.primitives.m_multigraph.isomorphism import is_isomorphic

graph1 = MixedMultiGraph(
    directed_edges=[(1, 3)],
    undirected_edges=[(3, 4)]
)
graph2 = MixedMultiGraph(
    directed_edges=[(2, 4)],
    undirected_edges=[(4, 5)]
)

# Basic isomorphism check
isomorphic = is_isomorphic(graph1, graph2)

# With node attributes
graph1.add_node(1, label='root')
graph2.add_node(2, label='root')
isomorphic_with_attrs = is_isomorphic(graph1, graph2, node_attrs=['label'])

Graph Transformations#

The mixed multi-graph module provides functions for transforming graph structures.

Vertex identification

The identify_vertices() function merges multiple vertices into a single vertex, combining their incident edges.

from phylozoo.core.primitives.m_multigraph.transformations import identify_vertices

# Merge vertices 1, 2, and 3 into a single vertex
identify_vertices(mixed_graph, [1, 2, 3])

Orientation

The orient_away_from_vertex() function orients all undirected edges away from a given root vertex, converting the mixed graph to a directed graph.

from phylozoo.core.primitives.m_multigraph.transformations import orient_away_from_vertex

# Orient all edges away from root vertex
directed_graph = orient_away_from_vertex(mixed_graph, root=1)

Degree-2 node suppression

The suppress_degree2_node() function removes a degree-2 node and connects its neighbors directly.

from phylozoo.core.primitives.m_multigraph.transformations import suppress_degree2_node

# Suppress a degree-2 node
suppress_degree2_node(mixed_graph, node=5)

Parallel edge identification

The identify_parallel_edge() function merges all parallel edges between two nodes into a single edge.

from phylozoo.core.primitives.m_multigraph.transformations import identify_parallel_edge

# Merge all parallel edges between nodes 1 and 2
identify_parallel_edge(mixed_graph, u=1, v=2)

Subgraph extraction

The subgraph() function creates a subgraph containing only the specified nodes and their incident edges.

from phylozoo.core.primitives.m_multigraph.transformations import subgraph

# Extract subgraph with specific nodes
sub = subgraph(mixed_graph, nodes=[1, 2, 3, 4])

NetworkX Conversion#

Convert from various NetworkX graph types. The graph_to_mixedmultigraph() function converts a NetworkX Graph to a MixedMultiGraph, the multigraph_to_mixedmultigraph() function converts a NetworkX MultiGraph to a MixedMultiGraph, and the multidigraph_to_mixedmultigraph() function converts a NetworkX MultiDiGraph to a MixedMultiGraph. Also, the directedmultigraph_to_mixedmultigraph() function converts a DirectedMultiGraph to a MixedMultiGraph.

import networkx as nx
from phylozoo.core.primitives.m_multigraph.conversions import (
    graph_to_mixedmultigraph,
    multigraph_to_mixedmultigraph,
    multidigraph_to_mixedmultigraph
)

# Convert undirected NetworkX Graph
nx_graph = nx.Graph()
nx_graph.add_edge(1, 2, weight=1.0)
mmg_from_graph = graph_to_mixedmultigraph(nx_graph)

# Convert undirected NetworkX MultiGraph
nx_multigraph = nx.MultiGraph()
nx_multigraph.add_edge(1, 2, key=0, weight=1.0)
mmg_from_multigraph = multigraph_to_mixedmultigraph(nx_multigraph)

# Convert directed NetworkX MultiDiGraph
nx_multidigraph = nx.MultiDiGraph()
nx_multidigraph.add_edge(1, 2, key=0, weight=1.0)
mmg_from_multidigraph = multidigraph_to_mixedmultigraph(nx_multidigraph)

# Convert from DirectedMultiGraph
from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
from phylozoo.core.primitives.m_multigraph.conversions import directedmultigraph_to_mixedmultigraph

dmg = DirectedMultiGraph(edges=[(1, 2), (2, 3)])
mmg_from_dmg = directedmultigraph_to_mixedmultigraph(dmg)

Tip

The class stores three NetworkX graphs that can be accessed for further use with NetworkX algorithms. The undirected edges are stored as a networkx.MultiGraph in the _undirected attribute, the directed edges as a networkx.MultiDiGraph in the _directed attribute, and the _combined attribute stores a combined undirected view of the graph as a networkx.MultiGraph for quick connectivity analyses.