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

1

https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#Bridge-Finding_with_Chain_Decompositions

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