easygraph.functions.path package

Submodules

easygraph.functions.path.average_shortest_path_length module

easygraph.functions.path.average_shortest_path_length.average_shortest_path_length(G, weight=None, method=None)[source]

Returns the average shortest path length.

The average shortest path length is

\[\begin{split}a =\sum_{\substack{s,t \in V \\ s\neq t}} \frac{d(s, t)}{n(n-1)}\end{split}\]

where V is the set of nodes in G, d(s, t) is the shortest path from s to t, and n is the number of nodes in G.

Changed in version 3.0: An exception is raised for directed graphs that are not strongly connected.

Parameters:

  • G (EasyGraph graph)

  • weight (None, string or function, optional (default = None)) – If None, every edge has weight/distance/cost 1. If a string, use this edge attribute as the edge weight. Any edge attribute not present defaults to 1. If this is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number.

  • method (string, optional (default = 'unweighted' or 'dijkstra')) – The algorithm to use to compute the path lengths. Supported options are ‘unweighted’, ‘dijkstra’, ‘bellman-ford’, ‘floyd-warshall’ and ‘floyd-warshall-numpy’. Other method values produce a ValueError. The default method is ‘unweighted’ if weight is None, otherwise the default method is ‘dijkstra’.

Raises:

  • NetworkXPointlessConcept – If G is the null graph (that is, the graph on zero nodes).

  • NetworkXError – If G is not connected (or not strongly connected, in the case of a directed graph).

  • ValueError – If method is not among the supported options.

Examples

>>> G = eg.path_graph(5)
>>> eg.average_shortest_path_length(G)
2.0

For disconnected graphs, you can compute the average shortest path length for each component

>>> G = eg.Graph([(1, 2), (3, 4)])
>>> for C in (G.subgraph(c).copy() for c in eg.connected_components(G)):
...     print(eg.average_shortest_path_length(C))
1.0
1.0

easygraph.functions.path.bridges module

easygraph.functions.path.bridges.bridges(G, root=None)[source]

Generate all bridges in a graph.

A bridge in a graph is an edge whose removal causes the number of connected components of the graph to increase. Equivalently, a bridge is an edge that does not belong to any cycle.

Parameters:

  • G (undirected graph)

  • root (node (optional)) – A node in the graph G. If specified, only the bridges in the connected component containing this node will be returned.

Yields:

e (edge) – An edge in the graph whose removal disconnects the graph (or causes the number of connected components to increase).

Raises:

NodeNotFound – If root is not in the graph G.

Examples

>>> list(eg.bridges(G))
[(9, 10)]

Notes

This is an implementation of the algorithm described in _[1]. An edge is a bridge if and only if it is not contained in any chain. Chains are found using the chain_decomposition() function.

Ignoring polylogarithmic factors, the worst-case time complexity is the same as the chain_decomposition() function, $O(m + n)$, where $n$ is the number of nodes in the graph and $m$ is the number of edges.

References

easygraph.functions.path.bridges.has_bridges(G, root=None)[source]

Decide whether a graph has any bridges.

A bridge in a graph is an edge whose removal causes the number of connected components of the graph to increase.

Parameters:

  • G (undirected graph)

  • root (node (optional)) – A node in the graph G. If specified, only the bridges in the connected component containing this node will be considered.

Returns:

Whether the graph (or the connected component containing root) has any bridges.

Return type:

bool

Raises:

NodeNotFound – If root is not in the graph G.

Examples

>>> eg.has_bridges(G)
True

Notes

This implementation uses the easygraph.bridges() function, so it shares its worst-case time complexity, $O(m + n)$, ignoring polylogarithmic factors, where $n$ is the number of nodes in the graph and $m$ is the number of edges.

easygraph.functions.path.diameter module

easygraph.functions.path.diameter.diameter(G, e=None)[source]

Returns the diameter of the graph G.

The diameter is the maximum eccentricity.

Parameters:

  • G (EasyGraph graph) – A graph

  • e (eccentricity dictionary, optional) – A precomputed dictionary of eccentricities.

Returns:

d – Diameter of graph

Return type:

integer

Examples

>>> G = eg.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> eg.diameter(G)
3

See also

eccentricity

easygraph.functions.path.diameter.eccentricity(G, v=None, sp=None)[source]

Returns the eccentricity of nodes in G.

The eccentricity of a node v is the maximum distance from v to all other nodes in G.

Parameters:

  • G (EasyGraph graph) – A graph

  • v (node, optional) – Return value of specified node

  • sp (dict of dicts, optional) – All pairs shortest path lengths as a dictionary of dictionaries

Returns:

ecc – A dictionary of eccentricity values keyed by node.

Return type:

dictionary

Examples

>>> G = eg.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> dict(eg.eccentricity(G))
{1: 2, 2: 3, 3: 2, 4: 2, 5: 3}

>>> dict(eg.eccentricity(G, v=[1, 5]))  # This returns the eccentrity of node 1 & 5
{1: 2, 5: 3}

easygraph.functions.path.mst module

easygraph.functions.path.mst.maximum_spanning_edges(G, algorithm='kruskal', weight='weight', data=True, ignore_nan=False)[source]

Generate edges in a maximum spanning forest of an undirected weighted graph.

A maximum spanning tree is a subgraph of the graph (a tree) with the maximum possible sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph.

Parameters:

  • G (undirected Graph) – An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.

  • algorithm (string) – The algorithm to use when finding a maximum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.

  • weight (string) – Edge data key to use for weight (default ‘weight’).

  • data (bool, optional) – If True yield the edge data along with the edge.

  • ignore_nan (bool (default: False)) – If a NaN is found as an edge weight normally an exception is raised. If ignore_nan is True then that edge is ignored instead.

Returns:

edges – An iterator over edges in a maximum spanning tree of G. Edges connecting nodes u and v are represented as tuples: (u, v, k, d) or (u, v, k) or (u, v, d) or (u, v)

Return type:

iterator

Examples

>>> from easygraph.functions.basic import mst

Find maximum spanning edges by Kruskal’s algorithm

>>> G.add_edge(0, 3, weight=2)
>>> mst = mst.maximum_spanning_edges(G, algorithm="kruskal", data=False)
>>> edgelist = list(mst)
>>> sorted(sorted(e) for e in edgelist)
[[0, 1], [0, 3], [1, 2]]

Find maximum spanning edges by Prim’s algorithm

>>> G.add_edge(0, 3, weight=2)  # assign weight 2 to edge 0-3
>>> mst = mst.maximum_spanning_edges(G, algorithm="prim", data=False)
>>> edgelist = list(mst)
>>> sorted(sorted(e) for e in edgelist)
[[0, 1], [0, 3], [2, 3]]

Notes

For Borůvka’s algorithm, each edge must have a weight attribute, and each edge weight must be distinct.

For the other algorithms, if the graph edges do not have a weight attribute a default weight of 1 will be used.

Modified code from David Eppstein, April 2006 http://www.ics.uci.edu/~eppstein/PADS/

easygraph.functions.path.mst.maximum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False)[source]

Returns a maximum spanning tree or forest on an undirected graph G.

Parameters:

  • G (undirected graph) – An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.

  • weight (str) – Data key to use for edge weights.

  • algorithm (string) – The algorithm to use when finding a maximum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.

  • ignore_nan (bool (default: False)) – If a NaN is found as an edge weight normally an exception is raised. If ignore_nan is True then that edge is ignored instead.

Returns:

G – A maximum spanning tree or forest.

Return type:

EasyGraph Graph

Examples

>>> G.add_edge(0, 3, weight=2)
>>> T = eg.maximum_spanning_tree(G)
>>> sorted(T.edges(data=True))
[(0, 1, {}), (0, 3, {'weight': 2}), (1, 2, {})]

Notes

For Borůvka’s algorithm, each edge must have a weight attribute, and each edge weight must be distinct.

For the other algorithms, if the graph edges do not have a weight attribute a default weight of 1 will be used.

There may be more than one tree with the same minimum or maximum weight. See easygraph.tree.recognition for more detailed definitions.

Isolated nodes with self-loops are in the tree as edgeless isolated nodes.

easygraph.functions.path.mst.minimum_spanning_edges(G, algorithm='kruskal', weight='weight', data=True, ignore_nan=False)[source]

Generate edges in a minimum spanning forest of an undirected weighted graph.

A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph.

Parameters:

  • G (undirected Graph) – An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.

  • algorithm (string) – The algorithm to use when finding a minimum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.

  • weight (string) – Edge data key to use for weight (default ‘weight’).

  • data (bool, optional) – If True yield the edge data along with the edge.

  • ignore_nan (bool (default: False)) – If a NaN is found as an edge weight normally an exception is raised. If ignore_nan is True then that edge is ignored instead.

Returns:

edges – An iterator over edges in a maximum spanning tree of G. Edges connecting nodes u and v are represented as tuples: (u, v, k, d) or (u, v, k) or (u, v, d) or (u, v)

Return type:

iterator

Examples

>>> from easygraph.functions.basic import mst

Find minimum spanning edges by Kruskal’s algorithm

>>> G.add_edge(0, 3, weight=2)
>>> mst = mst.minimum_spanning_edges(G, algorithm="kruskal", data=False)
>>> edgelist = list(mst)
>>> sorted(sorted(e) for e in edgelist)
[[0, 1], [1, 2], [2, 3]]

Find minimum spanning edges by Prim’s algorithm

>>> G.add_edge(0, 3, weight=2)
>>> mst = mst.minimum_spanning_edges(G, algorithm="prim", data=False)
>>> edgelist = list(mst)
>>> sorted(sorted(e) for e in edgelist)
[[0, 1], [1, 2], [2, 3]]

Notes

For Borůvka’s algorithm, each edge must have a weight attribute, and each edge weight must be distinct.

For the other algorithms, if the graph edges do not have a weight attribute a default weight of 1 will be used.

Modified code from David Eppstein, April 2006 http://www.ics.uci.edu/~eppstein/PADS/

easygraph.functions.path.mst.minimum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False)[source]

Returns a minimum spanning tree or forest on an undirected graph G.

Parameters:

  • G (undirected graph) – An undirected graph. If G is connected, then the algorithm finds a spanning tree. Otherwise, a spanning forest is found.

  • weight (str) – Data key to use for edge weights.

  • algorithm (string) – The algorithm to use when finding a minimum spanning tree. Valid choices are ‘kruskal’, ‘prim’, or ‘boruvka’. The default is ‘kruskal’.

  • ignore_nan (bool (default: False)) – If a NaN is found as an edge weight normally an exception is raised. If ignore_nan is True then that edge is ignored instead.

Returns:

G – A minimum spanning tree or forest.

Return type:

EasyGraph Graph

Examples

>>> G.add_edge(0, 3, weight=2)
>>> T = eg.minimum_spanning_tree(G)
>>> sorted(T.edges(data=True))
[(0, 1, {}), (1, 2, {}), (2, 3, {})]

Notes

For Borůvka’s algorithm, each edge must have a weight attribute, and each edge weight must be distinct.

For the other algorithms, if the graph edges do not have a weight attribute a default weight of 1 will be used.

Isolated nodes with self-loops are in the tree as edgeless isolated nodes.

easygraph.functions.path.path module

easygraph.functions.path.path.Dijkstra(G, node, weight='weight')[source]

Returns the length of paths from the certain node to remaining nodes

Parameters:

  • G (graph) – weighted graph

  • node (int)

Returns:

result_dict – the length of paths from the certain node to remaining nodes

Return type:

dict

Examples

Returns the length of paths from node 1 to remaining nodes

>>> Dijkstra(G,node=1,weight="weight")
easygraph.functions.path.path.Floyd(G, weight='weight')[source]

Returns the length of paths from all nodes to remaining nodes

Parameters:

G (graph) – weighted graph

Returns:

result_dict – the length of paths from all nodes to remaining nodes

Return type:

dict

Examples

Returns the length of paths from all nodes to remaining nodes

>>> Floyd(G,weight="weight")
easygraph.functions.path.path.Kruskal(G, weight='weight')[source]

Returns the edges that make up the minimum spanning tree

Parameters:

G (graph) – weighted graph

Returns:

result_dict – the edges that make up the minimum spanning tree

Return type:

dict

Examples

Returns the edges that make up the minimum spanning tree

>>> Kruskal(G,weight="weight")
easygraph.functions.path.path.Prim(G, weight='weight')[source]

Returns the edges that make up the minimum spanning tree

Parameters:

G (graph) – weighted graph

Returns:

result_dict – the edges that make up the minimum spanning tree

Return type:

dict

Examples

Returns the edges that make up the minimum spanning tree

>>> Prim(G,weight="weight")
easygraph.functions.path.path.Spfa(G, node, weight='weight')[source]
easygraph.functions.path.path.multi_source_dijkstra(G, sources, weight='weight', target=None)[source]
easygraph.functions.path.path.single_source_bfs(G, source, target=None)[source]
easygraph.functions.path.path.single_source_dijkstra(G, source, weight='weight', target=None)[source]

Module contents