Graph class

class Graph(graph, skip_validation=False)

Bases: object

Graph class representing a generic directed graph with edge attributes.

The graph is stored internally as a Dict[int, Dict[int, Dict[str, Any]]] (GraphRepresentation) where the keys of the outer dictionary are the vertex indices, the keys of the inner dictionary are the neighboring vertex indices, and the values of the inner dictionary are dictionaries containing edge attributes such as weight.

The Graph class provides methods to convert between adjacency list and edge list representations, as well as methods to check add edges and vertices. Consider using from_adjacency and from_edges class methods to create a Graph object from an adjacency list or edge list representation, respectively.

Parameters:

• graph (GraphRepresentation) – The graph represented as a dictionary where the keys are vertex indices and the values are dictionaries mapping neighboring vertex indices to edge attributes.

• skip_validation (bool)

Examples

Example of initializing a Graph object with an adjacency list representation:

from pygraphs import Graph

adjacency_list = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], []]
graph = Graph.from_adjacency(adjacency_list)

add_edge(u, v, data=None, *, weight_key='weight')

Add an edge to the graph. If the graph is weighted, a weight must be provided.

Parameters:

• u (Integral) – The index of the source vertex.

• v (Integral) – The index of the target vertex.

• data (Union[Real, Dict[str, Any]], (default: None)) – The edge attributes. If a real value is given, it will be treated as a weight.

• weight_key (str, optional (default: 'weight')) – The key to use for storing edge weights in the graph representation.

Returns:

This method does not return anything.

Return type:

None

add_edges(edges, *, weight_key='weight')

Add multiple edges to the graph.

Parameters:

• edges (Edges) – The edges to add to the graph.

• weight_key (str, optional (default: 'weight')) – The key to use for storing edge weights in the graph representation.

Returns:

This method does not return anything.

Return type:

None

add_n_vertices(n)

Add multiple vertices to the graph. The new vertices will have indices starting from the current number of vertices in the graph.

Parameters:

n (Integral) – The number of vertices to add.

Returns:

This method does not return anything.

Return type:

None

add_vertex()

Add a vertex to the graph. The new vertex will have an index equal to the current number of vertices in the graph.

Returns:

This method does not return anything.

Return type:

None

classmethod from_adjacency(adjacency, **kwargs)

Create a Graph object from an adjacency list representation.

• AdjacencyList: List[List[Integral]]]: A list of lists, where the outer list has a length equal to the number of vertices in the graph, and each inner list contains the neighbors (i.e., [v1, v2, ...]) of the corresponding vertex (from outer vertex to inner vertex). For a weighted graph, the form List[List[Tuple[Integral, Real]]] is used where the inner lists contain tuples of the form \((v, w)\), where \(v\) is a neighbor vertex and \(w\) is the weight of the edge connecting the vertex to its neighbor. To store more than weight, the form List[List[Tuple[Integral, Dict[str, Any]]]] is used.

See also

• pygraphs.adjacency_list_to_graph() to assemble the graph from an adjacency list.

Parameters:

• adjacency (AdjacencyList) – The graph represented as an adjacency list.

• **kwargs – Additionals arguments to pass to the conversion function.

Returns:

A Graph object representing the given adjacency list.

Return type:

Graph

classmethod from_edges(edges, n_vertices, **kwargs)

Create a Graph object from an edge list representation.

• Edges: List[Tuple[Integral, Integral]]: A list of tuples, where each tuple represents an edge \((u, v)\) in the graph (from vertex \(u\) to vertex \(v\)). For a undirected graph consider converting in pygraphs.Graph class and use the to_undirected method to duplicate \((u, v)\) into \((u, v)\) and \((v, u)\). For a weighted graph, the form List[Tuple[Integral, Integral, Real]] containing \((u, v, w)\) is used, where \(u\) and \(v\) are the vertices connected by the edge and \(w\) is the weight of the edge. To store more than weight, the form List[Tuple[Integral, Integral, Dict[str, Any]]] is used.

See also

• pygraphs.edges_list_to_graph() to assemble the graph from an edges list.

Parameters:

• edges (Union[Edges, WeightedEdges]) – The graph represented as an edge list.

• n_vertices (Integral) – The number of vertices in the graph. This is needed to determine the size of the adjacency list.

• **kwargs – Additionals arguments to pass to the conversion function.

Returns:

A Graph object representing the given edge list.

Return type:

Graph

is_directed(weight_match=True, weight_key='weight')

Check if the graph is directed.

A graph is considered undirected if every edge (u, v) has a corresponding edge (v, u). Otherwise it is directed.

If weight_match is True, then the graph is considered undirected only if every edge (u, v) has a corresponding edge (v, u) with the same weight. Otherwise, the weights of the edges are ignored when checking if the graph is directed.

By convention, an empty graph is considered undirected.

Parameters:

• weight_match (bool, optional (default: True)) – Whether to consider the weights of the edges when checking if the graph is directed.

• weight_key (str, optional (default: 'weight')) – The key to use for storing edge weights in the graph representation.

Returns:

True if the graph is directed, False otherwise.

Return type:

bool

is_weight_symmetric(weight_key='weight', *, atol=1e-06)

Check if the graph has symmetric weights, meaning that for every edge (u, v) with weight w, if there is a corresponding edge (v, u), it must also have weight w.

By convention, an empty graph is considered to have symmetric weights.

Parameters:

• weight_key (str, optional (default: 'weight')) – The key to use for storing edge weights in the graph representation.

• atol (float (default: 1e-6)) – Absolute tolerance.

Returns:

True if the graph has symmetric weights, False otherwise.

Return type:

bool

property n_edges: int

Get the number of edges in the graph for the directed graph.

For an undirected graph, the number of edges is half the number of edges in the directed version of the graph.

if graph.is_directed():
    n_edges = graph.n_edges

else:
    n_edges = graph.n_edges // 2

Returns:

The number of edges in the graph.

Return type:

int

property n_vertices: int

Get the number of vertices in the graph.

Returns:

The number of vertices in the graph.

Return type:

int

remove_edge(u, v)

Remove an edge from the graph.

Parameters:

• u (Integral) – The index of the source vertex.

• v (Integral) – The index of the target vertex.

Returns:

This method does not return anything.

Return type:

None

remove_edges(edges)

Remove multiple edges from the graph.

Parameters:

edges (Sequence[Tuple[Integral, Integral]]) – A sequence of edges to remove. Each edge should be represented as a tuple of the form \((u, v)\), where \(u\) and \(v\) are vertex indices.

Returns:

This method does not return anything.

Return type:

None

remove_n_vertices(vertices)

Remove multiple vertices from the graph. This will also remove all edges incident to the removed vertices.

Important

Removing vertices will shift the indices of all vertices with indices greater than the removed vertices down by the number of removed vertices.

Parameters:

vertices (Sequence[Integral]) – A sequence of vertex indices to remove.

Returns:

This method does not return anything.

Return type:

None

remove_vertex(vertex)

Remove a vertex from the graph. This will also remove all edges incident to the vertex.

Important

Removing a vertex will shift the indices of all vertices with indices greater than the removed vertex down by 1.

Parameters:

vertex (Integral) – The index of the vertex to remove.

Returns:

This method does not return anything.

Return type:

None

to_adjacency(**kwargs)

Get the adjacency list representation of the graph.

• AdjacencyList: List[List[Integral]]]: A list of lists, where the outer list has a length equal to the number of vertices in the graph, and each inner list contains the neighbors (i.e., [v1, v2, ...]) of the corresponding vertex (from outer vertex to inner vertex). For a weighted graph, the form List[List[Tuple[Integral, Real]]] is used where the inner lists contain tuples of the form \((v, w)\), where \(v\) is a neighbor vertex and \(w\) is the weight of the edge connecting the vertex to its neighbor. To store more than weight, the form List[List[Tuple[Integral, Dict[str, Any]]]] is used.

See also

• pygraphs.graph_to_adjacency_list() to assemble the graph into an adjacency list.

Parameters:

**kwargs – Additionals arguments to pass to the conversion function.

Returns:

The adjacency list representation of the graph.

Return type:

Union[AdjacencyList, WeightedAdjacencyList]

to_clean()

Return the same graph without edge attributes.

Returns:

A new Graph object representing the clean version of the original graph.

Return type:

Graph

to_edges(**kwargs)

Get the edge list representation of the graph.

• Edges: List[Tuple[Integral, Integral]]: A list of tuples, where each tuple represents an edge \((u, v)\) in the graph (from vertex \(u\) to vertex \(v\)). For a undirected graph consider converting in pygraphs.Graph class and use the to_undirected method to duplicate \((u, v)\) into \((u, v)\) and \((v, u)\). For a weighted graph, the form List[Tuple[Integral, Integral, Real]] containing \((u, v, w)\) is used, where \(u\) and \(v\) are the vertices connected by the edge and \(w\) is the weight of the edge. To store more than weight, the form List[Tuple[Integral, Integral, Dict[str, Any]]] is used.

See also

• pygraphs.graph_to_edges_list() to assemble the graph into an edges list.

Parameters:

**kwargs – Additionals arguments to pass to the conversion function.

Returns:

The edge list representation of the graph.

Return type:

Union[Edges, WeightedEdges]

to_reversed()

Return the same graph with all edge reversed. :returns: A new Graph object representing the reserved version of the original graph. :rtype: Graph

Return type:

Graph

to_undirected()

Return a new graph that is the undirected version of the current graph by adding a reverse edge for each edge in the original graph.

If the graph is already undirected, a copy of the graph is returned.

Warning

If two edges wexist between the same pair of vertices and differents attributes in the original graph, an error will be raised since it is not possible to create an undirected graph with symmetric data in this case.

Returns:

A new Graph object representing the undirected version of the original graph.

Return type:

Graph