d_multigraph#

Directed multi-graph module.

This module provides the DirectedMultiGraph class and related functions for working with directed multi-graphs. A directed multi-graph allows multiple directed edges between the same pair of vertices. It is the underlying graph structure for directed phylogenetic networks, where multiple edges can represent parallel arcs.

Main Class#

Directed multi-graph module.

This module provides the DirectedMultiGraph class for working with directed multi-graphs.

class phylozoo.core.primitives.d_multigraph.base.DirectedMultiGraph(edges: list[tuple[T, T] | tuple[T, T, int] | dict[str, Any]] | None = None, attributes: dict[str, Any] | None = None)[source]#

Bases: IOMixin

Directed multi-graph where all edges are directed.

This class uses composition with a NetworkX MultiDiGraph:

  • _graph: nx.MultiDiGraph for directed edges

  • _combined: nx.MultiGraph combining all edges as undirected for connectivity analysis

This class allows parallel directed edges (multiple directed edges between the same nodes), including self-loops; each parallel edge can have different parameters (weights, attributes, etc.) via edge keys.

Parameters:

edges (list[tuple[T, T] | tuple[T, T, int] | dict[str, Any]] | None, optional) –

List of directed edges. Can be:

  • (u, v) tuples (key auto-generated)

  • (u, v, key) tuples (explicit key)

  • Dict with ‘u’, ‘v’ keys and optional ‘key’ and edge attributes

If keys are not provided, they will be auto-generated. By default None.

Notes

The underlying graphs (_graph, _combined) are accessible but should NOT be modified directly. All modifications must go through the class methods (add_edge, remove_edge, etc.) to ensure state synchronization. Direct modification will desynchronize the graphs and cause incorrect behavior.

Supported I/O formats:

  • dot (default): .dot, .gv

  • edgelist: .el

Examples

>>> G = DirectedMultiGraph()
>>> key1 = G.add_edge(1, 2, weight=1.0)
>>> key2 = G.add_edge(1, 2, weight=2.0)  # Parallel edge
>>> key1 != key2
True

>>> from phylozoo.core.primitives.d_multigraph.features import number_of_connected_components
>>> number_of_connected_components(G)
1

>>> # Initialize with edges (including attributes)
>>> G2 = DirectedMultiGraph(
...     edges=[(1, 2), {'u': 2, 'v': 3, 'weight': 5.0}]
... )
>>> G2.number_of_edges()
2
_graph#

NetworkX MultiDiGraph storing directed edges. Warning: Do not modify directly. Use class methods instead.

Type:

nx.MultiDiGraph

_combined#

Combined undirected view of all edges for connectivity analysis. Warning: Do not modify directly. Use class methods instead.

Type:

nx.MultiGraph

class EdgeView(items: list[tuple[T, T]], callable_func: callable)[source]#

Bases: object

Edge view that works as both attribute and method, similar to NetworkX’s EdgeView.

This class provides a list-like interface for edges while also being callable as a method to get iterators with keys or data.

__call__(keys: bool = False, data: bool | str = False)[source]#

Call as method to get iterator with keys or data.

Parameters:

  • keys (bool, optional) – If True, return edge keys. By default False.

  • data (bool | str, optional) – If False (default), no edge data is included. If True, return edge data dictionaries. If string, return value of that edge attribute.

Returns:

Iterator over edges. Format depends on keys and data parameters.

Return type:

Iterator

__contains__(item: tuple[T, T]) → bool[source]#

Check if edge in view.

__iter__()[source]#

Iterate over edges.

__len__() → int[source]#

Number of edges.

__repr__() → str[source]#

String representation.

class NodeView(items: set[T], callable_func: callable)[source]#

Bases: object

Node view that works as both attribute and method, similar to NetworkX’s NodeView.

This class provides a set-like interface for nodes while also being callable as a method to get iterators or node data.

__and__(other)[source]#

Intersection with other set.

__call__(data: bool | str = False)[source]#

Call as method to get iterator or node data.

Parameters:

data (bool | str, optional) – If False (default), return iterator over nodes. If True, return iterator of (node, data_dict) tuples. If string, return iterator of (node, attribute_value) tuples.

Returns:

Iterator over nodes or (node, data) tuples.

Return type:

Iterator[T] | Iterator[tuple[T, Any]]

__contains__(item: T) → bool[source]#

Check if node in view.

__iter__()[source]#

Iterate over nodes.

__len__() → int[source]#

Number of nodes.

__or__(other)[source]#

Union with other set.

__repr__() → str[source]#

String representation.

issubset(other)[source]#

Check if this is a subset of other.

__contains__(v: T) → bool[source]#

Check if node v is in the graph.

Parameters:

v (T) – Node to check.

Returns:

True if v is in the graph, False otherwise.

Return type:

bool

Examples

>>> G = DirectedMultiGraph()
>>> G.add_node(1)
>>> 1 in G
True
>>> 2 in G
False
__getitem__(v: T) → dict[T, dict[int, dict[str, Any]]][source]#

Return adjacency dict for node v.

Parameters:

v (T) – Node.

Returns:

Adjacency dict (actually returns NetworkX’s AdjacencyView, which is dict-like and supports all dict operations).

Return type:

dict[T, dict[int, dict[str, Any]]]

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2, weight=1.0)
0
>>> G[1]
{2: {0: {'weight': 1.0}}}
__iter__() → Iterator[T][source]#

Iterate over nodes.

Returns:

Iterator over nodes.

Return type:

Iterator[T]

Examples

>>> G = DirectedMultiGraph()
>>> G.add_nodes_from([1, 2, 3])
>>> list(G)
[1, 2, 3]
__len__() → int[source]#

Return the number of nodes.

Returns:

Number of nodes.

Return type:

int

Examples

>>> G = DirectedMultiGraph()
>>> G.add_nodes_from([1, 2, 3])
>>> len(G)
3
__repr__() → str[source]#

Return a concise representation.

Returns:

Representation containing counts of nodes and edges.

Return type:

str

add_edge(u: T, v: T, key: int | None = None, **attr: Any) → int[source]#

Add directed edge (u, v) to the graph.

Parallel directed edges are allowed. Each parallel edge can have different attributes (weights, etc.) via the key parameter.

Parameters:

  • u (T) – Source node.

  • v (T) – Target node.

  • key (int | None, optional) – Edge key. If None, auto-generates a key. By default None.

  • **attr – Edge attributes (e.g., weight, label, etc.).

Returns:

The key of the added edge.

Return type:

int

Raises:

Examples

>>> G = DirectedMultiGraph()
>>> key1 = G.add_edge(1, 2, weight=1.0)
>>> key2 = G.add_edge(1, 2, weight=2.0)  # Parallel edge
>>> key1 != key2
True
add_edges_from(edges: list[tuple[T, T] | tuple[T, T, int]], **attr: Any) → None[source]#

Add all edges in ‘edges’ to the graph.

Parameters:

  • edges (list[tuple[T, T] | tuple[T, T, int]]) – List of edges. Can be (u, v) or (u, v, key) tuples.

  • **attr – Edge attributes applied to all edges.

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edges_from([(1, 2), (2, 3), (3, 1)])
add_node(v: T, **attr: Any) → None[source]#

Add node v to the graph.

Parameters:

  • v (T) – Node to add.

  • **attr – Node attributes.

Raises:

Examples

>>> G = DirectedMultiGraph()
>>> G.add_node(1, weight=2.0)
>>> 1 in G
True
add_nodes_from(nodes: list[T] | set[T], **attr: Any) → None[source]#

Add nodes from iterable.

Parameters:

  • nodes (list[T] | set[T]) – Iterable of nodes.

  • **attr – Attributes to add to all nodes.

Examples

>>> G = DirectedMultiGraph()
>>> G.add_nodes_from([1, 2, 3])
>>> len(G)
3
clear() → None[source]#

Clear the whole directed multi-graph.

Removes all nodes and edges.

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> G.clear()
>>> len(G.nodes())
0
property combined_graph: MultiGraph#

Get combined undirected graph for NetworkX algorithms.

Returns:

Combined graph treating all edges as undirected.

Return type:

nx.MultiGraph

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> nx.is_connected(G.combined_graph)
True
copy() → DirectedMultiGraph[source]#

Create a copy of the graph.

Returns:

A copy of the graph.

Return type:

DirectedMultiGraph

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> H = G.copy()
>>> H.add_edge(2, 3)
0
>>> G.number_of_edges()
1
>>> H.number_of_edges()
2
degree(v: T) → int[source]#

Return the total degree of vertex v.

The degree is the sum of incoming and outgoing directed edges.

Parameters:

v (T) – Vertex.

Returns:

Total degree of v. Returns 0 if v is not in the graph.

Return type:

int

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(3, 2)
0
>>> G.degree(2)
2
>>> G.degree(99)  # Node not in graph
0
property edges: EdgeView#

Get all edges (works as both attribute and method).

When accessed as attribute, returns an EdgeView object (list-like). When called as method, returns an iterator.

Returns:

Edge view object that’s both callable and list-like.

Return type:

EdgeView

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> G.edges  # Attribute access
[(1, 2), (2, 3)]
>>> list(G.edges())  # Method call
[(1, 2), (2, 3)]
>>> list(G.edges(keys=True))  # With keys
[(1, 2, 0), (2, 3, 0)]
>>> list(G.edges(data=True))  # With data
[(1, 2, {}), (2, 3, {})]
>>> list(G.edges(keys=True, data=True))  # With keys and data
[(1, 2, 0, {}), (2, 3, 0, {})]
edges_iter(keys: bool = False, data: bool | str = False) → Iterator[tuple[T, T] | tuple[T, T, int] | tuple[T, T, Any] | tuple[T, T, dict[str, Any]] | tuple[T, T, int, Any] | tuple[T, T, int, dict[str, Any]]][source]#

Return an iterator over edges.

Parameters:

  • keys (bool, optional) – If True, return edge keys. By default False.

  • data (bool | str, optional) – If False (default), no edge data is included. If True, return edge data dictionaries. If string, return value of that edge attribute.

Returns:

Iterator over edges. Format depends on keys and data parameters.

Return type:

Iterator

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2, weight=1.0)
0
>>> list(G.edges_iter())
[(1, 2)]
>>> list(G.edges_iter(keys=True))
[(1, 2, 0)]
>>> list(G.edges_iter(data=True))
[(1, 2, {'weight': 1.0})]
>>> list(G.edges_iter(keys=True, data='weight'))
[(1, 2, 0, 1.0)]
generate_node_ids(count: int) → Iterator[int][source]#

Generate new integer node IDs that are not in the graph.

Finds the largest integer node ID in the graph and generates count consecutive integer IDs starting from max + 1.

Parameters:

count (int) – Number of node IDs to generate.

Yields:

int – Consecutive integer node IDs starting from max + 1.

Raises:

PhyloZooValueError – If count is negative.

Examples

>>> G = DirectedMultiGraph()
>>> G.add_node(1)
>>> G.add_node(5)
>>> list(G.generate_node_ids(3))
[6, 7, 8]
>>> G = DirectedMultiGraph()
>>> list(G.generate_node_ids(2))
[0, 1]
has_edge(u: T, v: T, key: int | None = None) → bool[source]#

Check if edge exists.

Parameters:

  • u (T) – Source node.

  • v (T) – Target node.

  • key (int | None, optional) – Edge key. By default None.

Returns:

True if edge exists, False otherwise.

Return type:

bool

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.has_edge(1, 2)
True
>>> G.has_edge(2, 3)
False
incident_child_edges(v: T, keys: bool = False, data: bool | str = False) → Iterator[tuple[T, T] | tuple[T, T, int] | tuple[T, T, Any] | tuple[T, T, dict[str, Any]] | tuple[T, T, int, Any] | tuple[T, T, int, dict[str, Any]]][source]#

Return an iterator over edges leaving node v (to child nodes).

Parameters:

  • v (T) – Node.

  • keys (bool, optional) – If True, return edge keys. By default False.

  • data (bool | str, optional) – If False (default), no edge data is included. If True, return edge data dictionaries. If string, return value of that edge attribute.

Returns:

Iterator over outgoing edges. Format depends on keys and data parameters.

Return type:

Iterator

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2, weight=1.0)
0
>>> G.add_edge(1, 3, weight=2.0)
0
>>> list(G.incident_child_edges(1))
[(1, 2), (1, 3)]
>>> list(G.incident_child_edges(1, keys=True, data=True))
[(1, 2, 0, {'weight': 1.0}), (1, 3, 0, {'weight': 2.0})]
>>> list(G.incident_child_edges(1, data='weight'))
[(1, 2, 1.0), (1, 3, 2.0)]
incident_parent_edges(v: T, keys: bool = False, data: bool | str = False) → Iterator[tuple[T, T] | tuple[T, T, int] | tuple[T, T, Any] | tuple[T, T, dict[str, Any]] | tuple[T, T, int, Any] | tuple[T, T, int, dict[str, Any]]][source]#

Return an iterator over edges entering node v (from parent nodes).

Parameters:

  • v (T) – Node.

  • keys (bool, optional) – If True, return edge keys. By default False.

  • data (bool | str, optional) – If False (default), no edge data is included. If True, return edge data dictionaries. If string, return value of that edge attribute.

Returns:

Iterator over incoming edges. Format depends on keys and data parameters.

Return type:

Iterator

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2, weight=1.0)
0
>>> G.add_edge(3, 2, weight=2.0)
0
>>> list(G.incident_parent_edges(2))
[(1, 2), (3, 2)]
>>> list(G.incident_parent_edges(2, keys=True, data=True))
[(1, 2, 0, {'weight': 1.0}), (3, 2, 0, {'weight': 2.0})]
>>> list(G.incident_parent_edges(2, data='weight'))
[(1, 2, 1.0), (3, 2, 2.0)]
indegree(v: T) → int[source]#

Return the indegree of vertex v.

The indegree is the number of directed edges pointing to v.

Parameters:

v (T) – Vertex.

Returns:

Indegree of v. Returns 0 if v is not in the graph.

Return type:

int

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(3, 2)
0
>>> G.indegree(2)
2
>>> G.indegree(99)  # Node not in graph
0
neighbors(v: T) → Iterator[T][source]#

Return an iterator over neighbors of node v.

For directed graphs, neighbors include both predecessors and successors.

Parameters:

v (T) – Node.

Returns:

Iterator over neighbors.

Return type:

Iterator[T]

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(3, 2)
0
>>> list(G.neighbors(2))
[1, 3]
property nodes: NodeView#

Get all nodes (works as both attribute and method).

When accessed as attribute, returns a NodeView object (set-like). When called as method, returns an iterator.

Returns:

Node view object that’s both callable and set-like.

Return type:

NodeView

Examples

>>> G = DirectedMultiGraph()
>>> G.add_nodes_from([1, 2, 3])
>>> G.nodes  # Attribute access
{1, 2, 3}
>>> list(G.nodes())  # Method call
[1, 2, 3]
>>> list(G.nodes(data=True))  # Method call with data
[(1, {}), (2, {}), (3, {})]
nodes_iter(data: bool | str = False) → Iterator[T] | Iterator[tuple[T, Any]][source]#

Return an iterator over nodes.

Parameters:

data (bool | str, optional) – If False (default), return iterator over nodes. If True, return iterator of (node, data_dict) tuples. If string, return iterator of (node, attribute_value) tuples for the given attribute name.

Returns:

Iterator over nodes or (node, data) tuples.

Return type:

Iterator[T] | Iterator[tuple[T, Any]]

Examples

>>> G = DirectedMultiGraph()
>>> G.add_node(1, weight=2.0)
>>> G.add_node(2, weight=3.0)
>>> list(G.nodes_iter())
[1, 2]
>>> list(G.nodes_iter(data=True))
[(1, {'weight': 2.0}), (2, {'weight': 3.0})]
>>> list(G.nodes_iter(data='weight'))
[(1, 2.0), (2, 3.0)]
number_of_edges() → int[source]#

Return the number of edges.

Returns:

Number of edges.

Return type:

int

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> G.number_of_edges()
2
number_of_nodes() → int[source]#

Return the number of nodes.

Returns:

Number of nodes.

Return type:

int

Examples

>>> G = DirectedMultiGraph()
>>> G.add_nodes_from([1, 2, 3])
>>> G.number_of_nodes()
3
outdegree(v: T) → int[source]#

Return the outdegree of vertex v.

The outdegree is the number of directed edges pointing from v.

Parameters:

v (T) – Vertex.

Returns:

Outdegree of v. Returns 0 if v is not in the graph.

Return type:

int

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(1, 3)
0
>>> G.outdegree(1)
2
>>> G.outdegree(99)  # Node not in graph
0
predecessors(v: T) → Iterator[T][source]#

Return an iterator over predecessor nodes of v.

Parameters:

v (T) – Node.

Returns:

Iterator over predecessor nodes.

Return type:

Iterator[T]

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(3, 2)
0
>>> list(G.predecessors(2))
[1, 3]
remove_edge(u: T, v: T, key: int | None = None) → None[source]#

Remove edge (u, v) from the graph.

Parameters:

  • u (T) – Source node.

  • v (T) – Target node.

  • key (int | None, optional) – Edge key. If None, removes one edge. By default None.

Raises:

PhyloZooValueError – If no edge (u, v) exists with the specified key.

Examples

>>> G = DirectedMultiGraph()
>>> key = G.add_edge(1, 2)
0
>>> G.remove_edge(1, 2, key=key)
remove_edges_from(edges: list[tuple[T, T] | tuple[T, T, int]]) → None[source]#

Remove all edges in ‘edges’ from the graph.

Parameters:

edges (list[tuple[T, T] | tuple[T, T, int]]) – List of edges to remove. Can be (u, v) or (u, v, key) tuples.

Raises:

PhyloZooValueError – If the edge format is invalid.

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> G.remove_edges_from([(1, 2), (2, 3)])
remove_node(v: T) → None[source]#

Remove node v from the graph.

Also removes all edges incident to v.

Parameters:

v (T) – Node to remove.

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> G.remove_node(2)
>>> list(G.nodes())
[1, 3]
remove_nodes_from(nodes: list[T] | set[T]) → None[source]#

Remove all nodes in ‘nodes’ from the graph.

Parameters:

nodes (list[T] | set[T]) – Iterable of nodes to remove.

Examples

>>> G = DirectedMultiGraph()
>>> G.add_node(1)
>>> G.add_node(2)
>>> G.add_node(3)
>>> G.remove_nodes_from([1, 2])
>>> list(G.nodes())
[3]
set_graph_attribute(key: str, value: Any) → None[source]#

Set a graph attribute in all underlying graphs.

Sets the same attribute value in the graph and combined graph’s .graph attribute dictionaries.

Parameters:

  • key (str) – The attribute key.

  • value (Any) – The attribute value.

Examples

>>> G = DirectedMultiGraph()
>>> G.set_graph_attribute('probability', 0.5)
>>> G._graph.graph.get('probability')
0.5
>>> G._combined.graph.get('probability')
0.5
successors(v: T) → Iterator[T][source]#

Return an iterator over successor nodes of v.

Parameters:

v (T) – Node.

Returns:

Iterator over successor nodes.

Return type:

Iterator[T]

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(1, 3)
0
>>> list(G.successors(1))
[2, 3]

Features#

Graph features module.

This module provides functions to extract and identify features of DirectedMultiGraph instances (e.g., connectivity, self-loops, etc.).

phylozoo.core.primitives.d_multigraph.features.bi_edge_connected_components(graph: DirectedMultiGraph) → Iterator[set[T]][source]#

Get bi-edge connected components (2-edge-connected components) of the the underlying undirected graph.

A bi-edge connected component is a maximal subgraph that remains connected after removing any single edge. This is equivalent to finding connected components after removing all bridges (cut edges).

Parameters:

graph (DirectedMultiGraph) – The graph to analyze.

Returns:

Iterator over sets of nodes in each bi-edge connected component.

Return type:

Iterator[set[T]]

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> # Graph with cycle: 1-2-3-1, edge 3-4 is bridge
>>> # Bi-edge connected components: {1, 2, 3}, {4}
>>> G = DirectedMultiGraph()
>>> _ = G.add_edge(1, 2)
>>> _ = G.add_edge(2, 3)
>>> _ = G.add_edge(3, 1)
>>> _ = G.add_edge(3, 4)
>>> comps = list(bi_edge_connected_components(G))
>>> {1, 2, 3} in comps
True
>>> {4} in comps
True
>>> # Graph with two cycles connected by bridge: 1-2-3-1 and 4-5-6-4, connected via bridge 3-4
>>> # Bi-edge connected components: {1, 2, 3}, {4, 5, 6}
>>> G2 = DirectedMultiGraph()
>>> _ = G2.add_edge(1, 2)
>>> _ = G2.add_edge(2, 3)
>>> _ = G2.add_edge(3, 1)
>>> _ = G2.add_edge(3, 4)  # Bridge
>>> _ = G2.add_edge(4, 5)
>>> _ = G2.add_edge(5, 6)
>>> _ = G2.add_edge(6, 4)
>>> comps2 = list(bi_edge_connected_components(G2))
>>> {1, 2, 3} in comps2
True
>>> {4, 5, 6} in comps2
True
phylozoo.core.primitives.d_multigraph.features.biconnected_components(graph: DirectedMultiGraph) → Iterator[set[T]][source]#

Get biconnected components of the underlying undirected graph.

Parameters:

graph (DirectedMultiGraph) – The graph to analyze.

Returns:

Iterator over sets of nodes in each biconnected component.

Return type:

Iterator[set[T]]

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> G = DirectedMultiGraph()
>>> # Single connected component with two biconnected components:
>>> # Cycle 1: 1-2-3-1 and Cycle 2: 3-4-5-3 (articulation at 3)
>>> _ = G.add_edge(1, 2)
>>> _ = G.add_edge(2, 3)
>>> _ = G.add_edge(3, 1)
>>> _ = G.add_edge(3, 4)
>>> _ = G.add_edge(4, 5)
>>> _ = G.add_edge(5, 3)
>>> comps = list(biconnected_components(G))
>>> {1, 2, 3} in comps  # first cycle
True
>>> {3, 4, 5} in comps  # second cycle sharing articulation 3
True
phylozoo.core.primitives.d_multigraph.features.connected_components(graph: DirectedMultiGraph) → Iterator[set[T]][source]#

Get weakly connected components.

Parameters:

graph (DirectedMultiGraph) – The graph to analyze.

Returns:

Iterator over sets of nodes in each component.

Return type:

Iterator[set[T]]

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(3, 4)
0
>>> list(connected_components(G))
[{1, 2}, {3, 4}]
phylozoo.core.primitives.d_multigraph.features.cut_edges(graph: DirectedMultiGraph, keys: bool = False, data: bool | str = False) → set[tuple[T, T]] | set[tuple[T, T, int]] | set[tuple[T, T, Any]] | set[tuple[T, T, int, Any]] | list[tuple[T, T, dict[str, Any]]] | list[tuple[T, T, int, dict[str, Any]]][source]#

Find all cut-edges (bridges) in the graph.

A cut-edge is an edge whose removal increases the number of weakly connected components.

Parameters:

  • graph (DirectedMultiGraph) – The graph to analyze.

  • keys (bool, optional) – If True, return 3-tuples (u, v, key). If False, return 2-tuples (u, v). Default is False.

  • data (bool | str, optional) – If False, return edges without data. If True, return edges with full data dict. If a string, return edges with the value of that attribute. Default is False.

Returns:

Cut-edges. Format depends on keys and data parameters:

  • keys=False, data=False: {(u, v), …} (set)

  • keys=True, data=False: {(u, v, key), …} (set)

  • keys=False, data=True: [(u, v, data_dict), …] (list, since dicts are unhashable)

  • keys=True, data=True: [(u, v, key, data_dict), …] (list, since dicts are unhashable)

  • keys=False, data=’attr’: {(u, v, attr_value), …} (set)

  • keys=True, data=’attr’: {(u, v, key, attr_value), …} (set)

Return type:

set or list

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> from phylozoo.core.primitives.d_multigraph.features import cut_edges
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> edges = cut_edges(G)
>>> (1, 2) in edges and (2, 3) in edges
True
>>> edges_with_keys = cut_edges(G, keys=True)
>>> (1, 2, 0) in edges_with_keys and (2, 3, 0) in edges_with_keys
True

Notes

This function uses Tarjan’s algorithm for finding bridges, which runs in O(V + E) time. The algorithm works on the underlying undirected (weakly connected) representation. Parallel edges are never bridges, so this implementation optimizes by iterating through edges once and checking bridge membership.

phylozoo.core.primitives.d_multigraph.features.cut_vertices(graph: DirectedMultiGraph, data: bool | str = False) → set[T] | set[tuple[T, Any]] | list[tuple[T, dict[str, Any]]][source]#

Find all cut-vertices (articulation points) in the graph.

A cut-vertex is a vertex whose removal increases the number of weakly connected components.

Parameters:

  • graph (DirectedMultiGraph) – The graph to analyze.

  • data (bool | str, optional) – If False, return vertices without data. If True, return vertices with full data dict. If a string, return vertices with the value of that attribute. Default is False.

Returns:

Cut-vertices. Format depends on data parameter:

  • data=False: {v, …} (set)

  • data=True: [(v, data_dict), …] (list, since dicts are unhashable)

  • data=’attr’: {(v, attr_value), …} (set)

Return type:

set or list

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> from phylozoo.core.primitives.d_multigraph.features import cut_vertices
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> G.add_edge(2, 4)
0
>>> vertices = cut_vertices(G)
>>> 2 in vertices
True
>>> 1 in vertices
False

Notes

This function uses NetworkX’s articulation_points algorithm, which runs in O(V + E) time. The algorithm works on the underlying undirected (weakly connected) representation.

phylozoo.core.primitives.d_multigraph.features.has_parallel_edges(graph: DirectedMultiGraph) → bool[source]#

Check if the graph has any parallel edges.

Parallel edges are multiple edges between the same pair of nodes in the same direction.

Parameters:

graph (DirectedMultiGraph) – The graph to check.

Returns:

True if the graph has at least one pair of parallel edges, False otherwise.

Return type:

bool

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> has_parallel_edges(G)
False
>>> G.add_edge(1, 2)  # Add parallel edge
1
>>> has_parallel_edges(G)
True
phylozoo.core.primitives.d_multigraph.features.has_self_loops(graph: DirectedMultiGraph) → bool[source]#

Check whether the directed multigraph contains any self-loops.

Parameters:

graph (DirectedMultiGraph) – The graph to inspect.

Returns:

True if at least one self-loop exists, False otherwise.

Return type:

bool

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> from phylozoo.core.primitives.d_multigraph.features import has_self_loops
>>> G = DirectedMultiGraph()
>>> has_self_loops(G)
False
>>> G.add_edge(1, 1)
0
>>> has_self_loops(G)
True
phylozoo.core.primitives.d_multigraph.features.is_connected(graph: DirectedMultiGraph) → bool[source]#

Check if graph is weakly connected.

Parameters:

graph (DirectedMultiGraph) – The graph to check.

Returns:

True if graph is connected, False otherwise.

Return type:

bool

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> is_connected(G)
True
phylozoo.core.primitives.d_multigraph.features.number_of_connected_components(graph: DirectedMultiGraph) → int[source]#

Return the number of weakly connected components.

Parameters:

graph (DirectedMultiGraph) – The graph to analyze.

Returns:

Number of connected components.

Return type:

int

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(3, 4)
0
>>> number_of_connected_components(G)
2

Transformations#

Graph transformations module.

This module provides functions to transform DirectedMultiGraph instances (e.g., identify nodes, suppress degree-2 nodes, etc.).

phylozoo.core.primitives.d_multigraph.transformations.identify_parallel_edge(graph: DirectedMultiGraph, u: T, v: T, merged_attrs: dict[str, Any] | None = None) → None[source]#

Identify all parallel edges between two nodes by keeping one edge.

This function removes all parallel edges between u and v except one, effectively merging them into a single edge. The first edge (lowest key) is kept, and all others are removed.

Edge attributes are handled as follows:

  • If merged_attrs is provided: these attributes are used directly for the kept edge. This allows the caller to apply special merging logic before identification.

  • If merged_attrs is None: attributes are merged by taking the first edge’s data, then subsequent edges’ data overriding. For attributes present in multiple edges, the last edge’s value overrides earlier values.

Parameters:

  • graph (DirectedMultiGraph) – The directed multigraph to modify. This function modifies the graph in place.

  • u (T) – Source node.

  • v (T) – Target node.

  • merged_attrs (dict[str, Any] | None, optional) –

    Pre-merged attributes to use for the kept edge. If None, attributes are merged by taking the first edge’s data first, then subsequent edges’ data overriding.

    When provided, these attributes will be used directly for the kept edge. This is useful when special attribute handling is needed.

Raises:

PhyloZooValueError – If either node is not in the graph, or if no edges exist between u and v.

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2, weight=1.0)
0
>>> G.add_edge(1, 2, weight=2.0)
1
>>> G.add_edge(1, 2, label='test')
2
>>> identify_parallel_edge(G, 1, 2)
>>> G.number_of_edges(1, 2)
1
>>> # With custom merged attributes
>>> G2 = DirectedMultiGraph()
>>> G2.add_edge(1, 2, weight=1.0)
0
>>> G2.add_edge(1, 2, weight=2.0)
1
>>> identify_parallel_edge(G2, 1, 2, merged_attrs={'weight': 3.0, 'merged': True})
>>> edge_data = G2._graph[1][2][0]
>>> edge_data['weight']
3.0
>>> edge_data['merged']
True
phylozoo.core.primitives.d_multigraph.transformations.identify_vertices(graph: DirectedMultiGraph, vertices: list[T], merged_attrs: dict[str, Any] | None = None) → None[source]#

Identify multiple vertices by keeping the first vertex.

This function identifies all vertices in the list with the first vertex. All edges incident to the other vertices are moved to the first vertex, and the other vertices are removed. The first vertex’s attributes are preserved (or replaced with merged_attrs if provided).

This operation modifies the graph in place. Identification may create new parallel edges. Self-loops are not created (edges from a vertex to itself are removed).

Parameters:

  • graph (DirectedMultiGraph) – The directed multigraph to modify. This function modifies the graph in place.

  • vertices (list[T]) – List of vertices to identify. The first vertex will be kept, and all others will be merged into it.

  • merged_attrs (dict[str, Any] | None, optional) – Attributes to use for the kept vertex. If None, the first vertex’s attributes are preserved. If provided, these attributes replace the first vertex’s attributes.

Raises:

PhyloZooValueError – If the vertices list is empty, if any vertex is not in the graph, or if identification would create edges in both directions between the same pair of nodes (u->v and v->u), which is not allowed.

Notes

This function does not create self-loops. Any edges that would become self-loops after identification are removed.

Identification may create parallel edges. However, if identification would result in edges in both directions between the same pair of nodes (e.g., both u->v and v->u), a ValueError is raised as this violates the graph’s constraints.

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> G.add_edge(3, 4)
0
>>> identify_vertices(G, [1, 2, 3])
>>> list(G.nodes())
[1, 4]
>>> G.has_edge(1, 4)
True
phylozoo.core.primitives.d_multigraph.transformations.subgraph(graph: DirectedMultiGraph, nodes: Iterable[T]) → DirectedMultiGraph[source]#

Return the induced subgraph of graph on the given nodes.

The returned object is a new DirectedMultiGraph instance containing only the specified nodes and any edges (including parallel edges and their keys/attributes) whose endpoints are both in nodes. Node and edge attributes are preserved.

Parameters:

  • graph (DirectedMultiGraph) – Source directed multigraph.

  • nodes (Iterable[T]) – Iterable of node identifiers to include in the induced subgraph.

Returns:

A new DirectedMultiGraph containing the induced subgraph.

Return type:

DirectedMultiGraph

Raises:

PhyloZooValueError – If any node in nodes is not present in graph.

Examples

>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2, weight=1.0)
0
>>> G.add_edge(2, 3, weight=2.0)
0
>>> H = subgraph(G, [1, 2])
>>> list(H.nodes())
[1, 2]
>>> list(H.edges_iter(keys=True, data=True))
[(1, 2, 0, {'weight': 1.0})]
phylozoo.core.primitives.d_multigraph.transformations.suppress_degree2_node(graph: DirectedMultiGraph, node: T, merged_attrs: dict[str, Any] | None = None) → None[source]#

Suppress a single degree-2 node in a directed multigraph in place.

A degree-2 node has exactly two incident edges. For a directed multigraph, the only valid configuration is indegree=1 and outdegree=1 (u->x->v). Suppression connects the two neighbors directly: u->x->v becomes u->v.

Invalid configurations that raise ValueError:

  • indegree=2, outdegree=0: Multiple incoming directed edges

  • indegree=0, outdegree=2: Multiple outgoing directed edges

This operation modifies the graph in place. Suppression may create parallel edges.

Edge attributes are handled as follows:

  • If merged_attrs is provided: these attributes are used directly for the new edge. This allows the caller to apply special merging logic before suppression.

  • If merged_attrs is None: attributes are merged by taking the incoming edge’s data first, then the outgoing edge’s data overriding. For attributes present in both edges, the outgoing edge’s value overrides the incoming edge’s value.

Parameters:

  • graph (DirectedMultiGraph) – The directed multigraph to modify. This function modifies the graph in place.

  • node (T) – The degree-2 node to suppress.

  • merged_attrs (dict[str, Any] | None, optional) –

    Pre-merged attributes to use for the resulting edge. If None, attributes are merged by taking incoming edge data first, then outgoing edge data overriding.

    When provided, these attributes will be used directly for the new edge created during suppression. This is useful when special attribute handling is needed.

Raises:

PhyloZooValueError – If the node is not degree-2, or has an invalid edge configuration (indegree=2 with outdegree=0, or indegree=0 with outdegree=2).

Examples

>>> from phylozoo.core.primitives.d_multigraph.base import DirectedMultiGraph
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2)
0
>>> G.add_edge(2, 3)
0
>>> suppress_degree2_node(G, 2)
>>> list(G.edges())
[(1, 3)]

Conversions#

Conversion functions for DirectedMultiGraph.

This module provides functions for converting NetworkX graphs to DirectedMultiGraph.

phylozoo.core.primitives.d_multigraph.conversions.digraph_to_directedmultigraph(graph: DiGraph) → DirectedMultiGraph[source]#

Create a DirectedMultiGraph from a NetworkX DiGraph.

All edges from the DiGraph are added as directed edges.

Parameters:

graph (nx.DiGraph) – NetworkX DiGraph to convert.

Returns:

New DirectedMultiGraph instance with all edges as directed.

Return type:

DirectedMultiGraph

Examples

>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edge(1, 2, weight=5.0)
>>> G.add_edge(2, 3)
>>> M = digraph_to_directedmultigraph(G)
>>> M.number_of_edges()
2
phylozoo.core.primitives.d_multigraph.conversions.multidigraph_to_directedmultigraph(graph: MultiDiGraph) → DirectedMultiGraph[source]#

Create a DirectedMultiGraph from a NetworkX MultiDiGraph.

All edges from the MultiDiGraph are added as directed edges, preserving parallel edges and their keys.

Parameters:

graph (nx.MultiDiGraph) – NetworkX MultiDiGraph to convert.

Returns:

New DirectedMultiGraph instance with all edges as directed.

Return type:

DirectedMultiGraph

Examples

>>> import networkx as nx
>>> G = nx.MultiDiGraph()
>>> G.add_edge(1, 2, key=0, weight=1.0)
0
>>> G.add_edge(1, 2, key=1, weight=2.0)
1
>>> M = multidigraph_to_directedmultigraph(G)
>>> M.number_of_edges()
2

Isomorphism#

Isomorphism module for directed multi-graphs.

This module provides functions for checking graph isomorphism between DirectedMultiGraph instances.

phylozoo.core.primitives.d_multigraph.isomorphism.is_isomorphic(G1: DirectedMultiGraph[T], G2: DirectedMultiGraph[T], node_attrs: list[str] | None = None, edge_attrs: list[str] | None = None, graph_attrs: list[str] | None = None) → bool[source]#

Check if two directed multi-graphs are isomorphic.

Two graphs are isomorphic if there exists a bijection between their node sets that preserves adjacency, edge direction, and parallel edges. Optionally, node attributes, edge attributes, and graph-level attributes can be required to match as well.

Parameters:

  • G1 (DirectedMultiGraph) – First directed multi-graph.

  • G2 (DirectedMultiGraph) – Second directed multi-graph.

  • node_attrs (list[str] | None, optional) – List of node attribute names to match. If None, node attributes are ignored. Nodes must have matching values for all specified attributes to be considered isomorphic. If a node doesn’t have an attribute, it matches only with nodes that also don’t have that attribute. By default None.

  • edge_attrs (list[str] | None, optional) – List of edge attribute names to match. If None, edge attributes are ignored. Edges must have matching values for all specified attributes. If an edge doesn’t have an attribute, it matches only with nodes that also don’t have that attribute. By default None.

  • graph_attrs (list[str] | None, optional) – List of graph-level attribute names to match. If None, graph attributes are ignored. Graph attributes are checked before isomorphism checking for efficiency. By default None.

Returns:

True if the graphs are isomorphic, False otherwise.

Return type:

bool

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> G1 = DirectedMultiGraph(edges=[(1, 2), (2, 3)])
>>> G2 = DirectedMultiGraph(edges=[(4, 5), (5, 6)])
>>> is_isomorphic(G1, G2)
True
>>> # With node labels: graphs are isomorphic if labels match
>>> G1.add_node(1, label='A')
>>> G1.add_node(2, label='B')
>>> G2.add_node(4, label='A')
>>> G2.add_node(5, label='B')
>>> is_isomorphic(G1, G2, node_attrs=['label'])
True
>>> # Different labels: not isomorphic
>>> G2.add_node(4, label='C')  # Update label
>>> is_isomorphic(G1, G2, node_attrs=['label'])
False
>>> # Multiple node attributes
>>> G1.add_node(1, type='leaf')
>>> G2.add_node(4, type='leaf')
>>> is_isomorphic(G1, G2, node_attrs=['label', 'type'])
False  # Still false because label 'C' != 'A'
>>> # Edge attributes
>>> G3 = DirectedMultiGraph(edges=[{'u': 1, 'v': 2, 'weight': 1.0}])
>>> G4 = DirectedMultiGraph(edges=[{'u': 3, 'v': 4, 'weight': 1.0}])
>>> is_isomorphic(G3, G4, edge_attrs=['weight'])
True
>>> # Graph attributes
>>> G5 = DirectedMultiGraph(attributes={'version': '1.0'})
>>> G6 = DirectedMultiGraph(attributes={'version': '1.0'})
>>> is_isomorphic(G5, G6, graph_attrs=['version'])
True
>>> # Parallel edges are preserved
>>> G7 = DirectedMultiGraph(edges=[(1, 2), (1, 2)])
>>> G8 = DirectedMultiGraph(edges=[(3, 4), (3, 4)])
>>> is_isomorphic(G7, G8)
True
>>> # Different number of parallel edges: not isomorphic
>>> G9 = DirectedMultiGraph(edges=[(1, 2)])
>>> is_isomorphic(G7, G9)
False

Notes

  • Graph attributes are checked first for efficiency (early exit if they don’t match).

  • NetworkX’s efficient categorical matching functions are used internally.

I/O#

Directed multi-graph I/O module.

This module provides format handlers for reading and writing directed multi-graphs to/from files. Format handlers are registered with FormatRegistry for use with the IOMixin system.

The following format handlers are defined and registered:

  • dot: DOT format (Graphviz) (extensions: .dot, .gv) - Writer: to_dot() - Converts DirectedMultiGraph to DOT string - Reader: from_dot() - Parses DOT string to DirectedMultiGraph

  • edgelist: Edge-list format (extensions: .el) - Writer: to_edgelist() - Converts DirectedMultiGraph to edge-list string - Reader: from_edgelist() - Parses edge-list string to DirectedMultiGraph

These handlers are automatically registered when this module is imported. DirectedMultiGraph inherits from IOMixin, so you can use:

  • graph.save(‘file.dot’) - Save to file (auto-detects format)

  • graph.load(‘file.dot’) - Load from file (auto-detects format)

  • graph.to_string(format=’dot’) - Convert to string

  • graph.from_string(string, format=’edgelist’) - Parse from string

  • DirectedMultiGraph.convert(‘in.dot’, ‘out.el’) - Convert between formats

Notes

DOT format supports: - Node attributes (label, shape, color, etc.) - Edge attributes (label, weight, color, etc.) - Graph attributes - Parallel edges (multigraph support)

Edge-list format: - Simple text format: one edge per line - Format: u v or u v key or u v key attr1=value1 attr2=value2 - Uses node_id as the label/name

phylozoo.core.primitives.d_multigraph.io.from_dot(dot_string: str, **kwargs: Any) → DirectedMultiGraph[source]#

Parse a DOT format string and create a DirectedMultiGraph.

Parameters:

  • dot_string (str) – DOT format string containing graph data.

  • **kwargs – Additional arguments (currently unused, for compatibility).

Returns:

Parsed directed multi-graph.

Return type:

DirectedMultiGraph

Raises:

PhyloZooParseError – If the DOT string is malformed or cannot be parsed.

Examples

>>> from phylozoo.core.primitives.d_multigraph.io import from_dot
>>>
>>> dot_str = '''digraph {
...     1 [label="Node1"];
...     2 [label="Node2"];
...     1 -> 2 [weight=1.0];
...     2 -> 3 [weight=2.0];
... }'''
>>>
>>> G = from_dot(dot_str)
>>> G.number_of_nodes()
3
>>> G.number_of_edges()
2

Notes

This parser expects:

  • digraph declaration

  • Node declarations (optional attributes)

  • Edge declarations (optional attributes)

  • Graph attributes (optional)

  • Support for parallel edges

phylozoo.core.primitives.d_multigraph.io.from_edgelist(edgelist_string: str, **kwargs: Any) → DirectedMultiGraph[source]#

Parse an edge-list format string and create a DirectedMultiGraph.

Parameters:

  • edgelist_string (str) – Edge-list format string containing graph data.

  • **kwargs – Additional arguments (currently unused, for compatibility).

Returns:

Parsed directed multi-graph.

Return type:

DirectedMultiGraph

Raises:

PhyloZooParseError – If the edge-list string is malformed or cannot be parsed.

Examples

>>> from phylozoo.core.primitives.d_multigraph.io import from_edgelist
>>>
>>> el_str = '''1 2
... 2 3 weight=2.0
... 3 4 0 key1=value1'''
>>>
>>> G = from_edgelist(el_str)
>>> G.number_of_nodes()
4
>>> G.number_of_edges()
3

Notes

This parser expects:

  • One edge per line

  • Format: u v or u v key or u v key attr1=value1 attr2=value2

  • Uses node_id as the label/name

phylozoo.core.primitives.d_multigraph.io.to_dot(graph: DirectedMultiGraph, **kwargs: Any) → str[source]#

Convert a DirectedMultiGraph to a DOT format string.

Parameters:

  • graph (DirectedMultiGraph) – The directed multi-graph to convert.

  • **kwargs – Additional arguments (currently unused, for compatibility).

Returns:

The DOT format string representation of the graph.

Return type:

str

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> from phylozoo.core.primitives.d_multigraph.io import to_dot
>>>
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2, weight=1.0)
0
>>> G.add_edge(2, 3, weight=2.0)
0
>>> dot_str = to_dot(G)
>>> 'digraph' in dot_str
True
>>> '1 -> 2' in dot_str
True

Notes

The DOT format includes:

  • digraph declaration

  • Node declarations with attributes

  • Edge declarations with attributes

  • Graph attributes (if any)

  • Support for parallel edges (multigraph)

phylozoo.core.primitives.d_multigraph.io.to_edgelist(graph: DirectedMultiGraph, **kwargs: Any) → str[source]#

Convert a DirectedMultiGraph to an edge-list format string.

Parameters:

  • graph (DirectedMultiGraph) – The directed multi-graph to convert.

  • **kwargs – Additional arguments (currently unused, for compatibility).

Returns:

The edge-list format string representation of the graph.

Return type:

str

Examples

>>> from phylozoo.core.primitives.d_multigraph import DirectedMultiGraph
>>> from phylozoo.core.primitives.d_multigraph.io import to_edgelist
>>>
>>> G = DirectedMultiGraph()
>>> G.add_edge(1, 2, weight=1.0)
0
>>> G.add_edge(2, 3, weight=2.0)
0
>>> el_str = to_edgelist(G)
>>> '1 2' in el_str
True
>>> '2 3' in el_str
True

Notes

The edge-list format:

  • One edge per line

  • Format: u v or u v key or u v key attr1=value1 attr2=value2

  • Uses node_id as the label/name

  • Includes edge keys for parallel edges

  • Includes edge attributes if present

On this page
Edit on GitHub

This Page