Directed Multi-Graphs#

The phylozoo.core.primitives.d_multigraph module provides the DirectedMultiGraph class, a directed multigraph that supports parallel edges between nodes. This class serves as the foundation for DirectedPhyNetwork and enables representation of complex phylogenetic relationships with reticulations, , and other directed graph structures. It builds on the networkx.MultiDiGraph class.

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

from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph

Working with Directed Multi-Graphs#

Creating and modifying directed multi-graphs#

You can build a directed multi-graph from scratch (empty or from an edge list), add or remove edges and nodes, and query structure such as neighbors and degrees. Each edge has a unique key so that parallel edges between the same pair of nodes are distinct.

Construct a graph with no arguments for an empty graph, or pass edges as a list of (u, v) tuples or dicts with u and v keys. Repeated (u, v) pairs create parallel edges.

from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph

empty_graph = DirectedMultiGraph()
graph = DirectedMultiGraph(edges=[(1, 2), (2, 3), (3, 1)])
parallel_graph = DirectedMultiGraph(edges=[(1, 2), (1, 2), (1, 2)])

You can attach arbitrary attributes to edges (e.g. weight, label) and to the graph itself via the attributes argument:

attributed_graph = DirectedMultiGraph(edges=[
    {'u': 1, 'v': 2, 'weight': 1.0, 'label': 'edge1'},
    {'u': 2, 'v': 3, 'weight': 2.0, 'type': 'reticulation'}
])
annotated_graph = DirectedMultiGraph(
    edges=[(1, 2), (2, 3)],
    attributes={'source': 'simulation', 'version': '1.0'}
)

Tip

For graphs without parallel edges, you can build or manipulate them in NetworkX (e.g. networkx.DiGraph) and then convert to DirectedMultiGraph. See the section on “NetworkX Conversion” below.

Edge operations

The add_edge() method adds a new edge and returns the key of the new edge. Multiple edges between the same nodes are allowed (parallel edges).

graph = DirectedMultiGraph()
key1 = graph.add_edge(1, 2, weight=1.0, label='primary')
key2 = graph.add_edge(1, 2, weight=2.0, label='secondary')
key3 = graph.add_edge(2, 3, key=10, edge_type='reticulation')

To remove an edge between two nodes, use the key and remove_edge().

graph.remove_edge(1, 2, key=key1)

For adding or removing many edges at once, use add_edges_from() and remove_edges_from():

graph.add_edges_from([(1, 2), (2, 3), (3, 1)])
graph.remove_edges_from([(2, 3)])  # (u, v) or (u, v, key)

Node operations

Add nodes with optional attributes; the nodes view lets you read attributes by node.

graph.add_node(4, label='taxon_A', type='leaf', bootstrap=95)
node_attrs = graph.nodes[4]

To add or remove multiple nodes at once, use add_nodes_from(), remove_node(), and remove_nodes_from(). The generate_node_ids() method returns an iterator of fresh integer IDs.

graph.add_nodes_from([5, 6, 7], type='internal')
graph.remove_node(7)
ids = list(graph.generate_node_ids(3))

Accessing graph structure

Counts and membership are available via number_of_nodes() and number_of_edges(); use v in graph for node membership and has_edge() for edge membership. Iterate over nodes and edges for all nodes and (u, v, key) tuples.

num_nodes = graph.number_of_nodes()
num_edges = graph.number_of_edges()
nodes = list(graph.nodes())
edges = list(graph.edges())
edge_data = graph.get_edge_data(1, 2, key=0)

For connectivity and degrees, use successors() and predecessors() for neighbors by direction, and outdegree(), indegree(), and degree() for in-, out-, and total degree.

successors = list(graph.successors(2))
predecessors = list(graph.predecessors(2))
out_degree = graph.outdegree(2)
in_degree = graph.indegree(2)
total_degree = graph.degree(2)

neighbors() returns all nodes adjacent to a vertex (predecessors and successors combined). For edges incident to a vertex, use incident_parent_edges() (incoming) and incident_child_edges() (outgoing); both support keys and data. copy() returns a shallow copy of the graph, and clear() removes all nodes and edges.

neighbors = list(graph.neighbors(2))
incoming = list(graph.incident_parent_edges(2, keys=True))
outgoing = list(graph.incident_child_edges(2, keys=True))
graph_copy = graph.copy()
graph_copy.clear()

File Input/Output#

Directed multi-graphs support reading and writing in standard graph formats:

DOT (default): GraphViz format for visualization and storage — see DOT format
Edge list: Simple text format with one edge per line — see Edge list format

# Load from file (auto-detects format by extension)
graph = DirectedMultiGraph.load("phylogeny.dot")

# Load with explicit format
graph = DirectedMultiGraph.load("phylogeny.edgelist", format="edgelist")

# Save to file
graph.save("output.dot")
graph.save("output.edgelist", format="edgelist")

Graph Analysis Features#

The directed multi-graph module provides algorithms for analyzing graph properties.

Connectivity

The is_connected() function checks if a graph is weakly connected (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.d_multigraph.features import (
    is_connected, number_of_connected_components, connected_components
)

# Check if graph is weakly connected (ignoring edge directions)
connected = is_connected(graph)

# Count connected components
num_components = number_of_connected_components(graph)

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

Biconnectivity

The biconnected_components() function returns an iterator over biconnected components (maximal sets of nodes where any two nodes are connected by at least two node-disjoint paths).

The bi_edge_connected_components() function returns an iterator over bi-edge-connected components (maximal sets of nodes where any two nodes are connected by at least two edge-disjoint paths).

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

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

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

Cut edges and vertices

The cut_edges() function finds all cut edges (edges whose removal increases the number of connected components).

The cut_vertices() function finds all cut vertices (nodes whose removal increases the number of connected components).

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

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

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

Parallel edges and self-loops

The has_parallel_edges() function checks if the graph contains any parallel edges (multiple edges between the same pair of nodes).

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

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

# Check for parallel edges
has_parallel = has_parallel_edges(graph)

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

Isomorphism

The is_isomorphic() function checks if two graphs have the same structure regardless of node labeling. This is useful for comparing phylogenetic networks that may have different node labels but identical topologies.

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

graph1 = DirectedMultiGraph(edges=[(1, 2), (2, 3)])
graph2 = DirectedMultiGraph(edges=[(4, 5), (5, 6)])

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

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

# With edge attributes
isomorphic_with_edges = is_isomorphic(graph1, graph2, edge_attrs=['weight'])

Graph Transformations#

The directed 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.d_multigraph.transformations import identify_vertices

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

Degree-2 node suppression

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

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

# Suppress a degree-2 node
suppress_degree2_node(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.d_multigraph.transformations import identify_parallel_edge

# Merge all parallel edges between nodes 1 and 2
identify_parallel_edge(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.d_multigraph.transformations import subgraph

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

NetworkX Conversion#

Convert from NetworkX graphs to DirectedMultiGraph. The digraph_to_directedmultigraph() function converts a NetworkX DiGraph to a DirectedMultiGraph, and the multidigraph_to_directedmultigraph() function converts a NetworkX MultiDiGraph to a DirectedMultiGraph.

import networkx as nx
from phylozoo.core.primitives.d_multigraph.conversions import (
    digraph_to_directedmultigraph,
    multidigraph_to_directedmultigraph
)

# Convert from NetworkX DiGraph
nx_digraph = nx.DiGraph()
nx_digraph.add_edge(1, 2, weight=1.0)
dmg_from_digraph = digraph_to_directedmultigraph(nx_digraph)

# Convert from NetworkX MultiDiGraph
nx_multidigraph = nx.MultiDiGraph()
nx_multidigraph.add_edge(1, 2, key=0, weight=1.0)
nx_multidigraph.add_edge(1, 2, key=1, weight=2.0)
dmg_from_multidigraph = multidigraph_to_directedmultigraph(nx_multidigraph)

Tip

The class stores two NetworkX graphs that can be accessed for further use with NetworkX algorithms. The whole directed multigraph is stored as a networkx.MultiDiGraph in the _graph attribute . The _combined attribute stores a completely undirected view of the graph as a networkx.MultiGraph for quick connectivity analyses.

Directed Multi-Graphs#

Working with Directed Multi-Graphs#

Creating and modifying directed multi-graphs#

File Input/Output#

Graph Analysis Features#

Graph Transformations#

NetworkX Conversion#

See Also#

This Page