graphit.graph_algorithms package

graphit.graph_algorithms.centrality module

Functions for calculating node centrality measures in a graph

graphit.graph_algorithms.centrality.brandes_betweenness_centrality(graph, nodes=None, normalized=True, weight=None, endpoints=False)

Brandes algorithm for betweenness centrality.

Betweenness centrality is an indicator of a node’s centrality in a network. It is equal to the number of shortest paths from all vertices to all others that pass through that node. A node with high betweenness centrality has a large influence on the transfer of items through the network, under the assumption that item transfer follows the shortest paths.

Original publication: Brandes, Ulrik. “A faster algorithm for betweenness centrality*.” Journal of mathematical sociology 25.2 (2001): 163-177.

Parameters

  • graph (:graphit:Graph) – Graph to calculate Brandes betweenness centrality

  • nodes (:py:list) – nodes to calculate centrality for. Defaults to all nodes

  • normalized (bool) – normalize betweenness centrality measure between 0 and 1

  • endpoints (:py:bool) – include the endpoints in the shortest path counts

  • weight (string) – edge attribute to use as edge weight

Return type

:py:dict

graphit.graph_algorithms.centrality.eigenvector_centrality(graph, max_iter=100, tolerance=1e-06, weight=None, start_value=None)

Eigenvector centrality for nodes in the graph (like Google’s PageRank).

Eigenvector centrality is a measure of the importance of a node in a directed network. It rewards nodes with a high potential of (indirectly) connecting to high-scoring nodes. Nodes with no incoming connections have a score of zero. If you want to measure outgoing connections, reversed should be False.

The eigenvector calculation is done by the power iteration method. It has no guarantee of convergence. A starting vector for the power iteration can be given in the start dict.

You can adjust the importance of a node with the rating dictionary, which links node id’s to a score.

The algorithm is adapted from NetworkX, Aric Hagberg (hagberg@lanl.gov): https://networkx.lanl.gov/attachment/ticket/119/eigenvector_centrality.py

Parameters

  • graph (:graphit:Graph) – Graph to calculate eigenvector centrality for

  • max_iter (:py:int) – maximum number of iterations to reach convergance

  • weight (string) – edge attribute to use as weight. 1 if not defined

  • tolerance (:py:float) – iteration convergence criterion

  • start_value (:py:dict) – starting value of eigenvector iteration for each node

Returns

eigenvector centrality for each node in the graph

Return type

:py:dict

graphit.graph_algorithms.connectivity module

Functions for calculating node connectivity.

graphit.graph_algorithms.connectivity.adjacency(graph, directed=False, reverse=False, stochastic=False, heuristic=None)

An edge weight map indexed by node id’s.

A dictionary indexed by node id1’s in which each value is a dictionary of connected node id2’s linking to the edge weight. If directed, edges go from id1 to id2, but not the other way. If stochastic, all the weights for the neighbors of a given node sum to 1. A heuristic can be a function that takes two node id’s and returns an additional cost for movement between the two nodes.

graphit.graph_algorithms.connectivity.is_reachable(graph, root, destination)

Returns True if given node can be reached over traversable edges.

Parameters

  • graph (:graphit:Graph) – Graph to query

  • root (:py:int) – source node ID

  • destination (:py:int) – destintion node ID

Return type

:py:bool

graphit.graph_algorithms.connectivity.nodes_are_interconnected(graph, nodes)

Are all the provided nodes directly connected with one another

Parameters

  • graph (:graphit:Graph) – Graph to query

  • nodes (:py:list) – nodes to test connectivity for

Return type

:py:bool

graphit.graph_algorithms.path_traversal module

Functions for traversing graph nodes and edges in depth-first-search and breath-first-search order.

graphit.graph_algorithms.path_traversal.dfs_paths(graph, start, goal, method='dfs', cutoff=None)

Return all possible paths between two nodes.

Setting method to ‘bfs’ returns the shortest path first

Parameters

  • graph (graph class instance) – graph to search

  • start (:py:int) – root node to start the search from

  • goal (:py:int) – target node

  • method (:py:str) – search method. Depth-first search (dfs, default) and Breath-first search (bfs) supported.

  • cutoff (:py:int) – only return paths with length up to cutoff

Return type

generator object

graphit.graph_algorithms.path_traversal.dfs_nodes(graph, start, method='dfs', max_depth=None)

Node implementation of depth-first-search and breath-first-search

Parameters

  • graph (graph class instance) – graph to search

  • start (node ID or Node object) – root node to start the search from

  • method (:py:str) – search method. Depth-first search (dfs, default) and Breath-first search (bfs) supported.

  • max_depth (:py:int, default equals number of nodes in graph) – maximum search depth

Returns

A generator of nodes in dfs or bfs mode.

Return type

:py:generator

graphit.graph_algorithms.path_traversal.dfs_edges(graph, start, method='dfs', max_depth=None, edge_based=False)

Edge implementation of depth-first-search and breath-first-search

This function uses dfs or bfs to traverse the nodes of the graph reporting the connected edges. A list of visited nodes is used to guide graph traversal but this does not guaranty that all edges will be visited. Use the edge_based argument to switch to a true edge based graph traversal.

Parameters

  • graph (graph class instance) – graph to search

  • start (node ID or Node object) – root node to start the search from

  • method (:py:str) – search method. Depth-first search (dfs, default) and Breath-first search (bfs) supported.

  • max_depth (:py:int, default equals number of nodes in graph) – maximum search depth

  • edge_based (:py:bool) – traverse over edges instead of nodes

Returns

A generator of edges in dfs or bfs mode.

Return type

:py:generator

graphit.graph_algorithms.shortest_path module

Functions for calculating the shortest paths in a graph.

graphit.graph_algorithms.shortest_path.dijkstra_shortest_path(graph, start, goal=None, weight=None)

Dijkstra algorithm for finding shortest paths.

In contrast to depth- or breath first search, Dijkstra’s algorithm supports weighted graphs using a priority queue. The weight attribute defined the edge data attribute to use as weight which defaults to 1 if not defined or not found.

If the target node is not specified, the path search will continue untill the leaf node(s) are reached.

Original publication: Dijkstra, E. W. (1959). “A note on two problems in connexion with graphs” Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390.

Parameters

  • graph (graph class instance) – graph to search

  • start (:py:int) – root node to start the search from

  • goal (:py:int) – target node

  • weight (:py:str) – edge attribute to use as edge weight

Return type

:py:list

Module contents

graphit.graph_algorithms.degree(graph, nodes=None, weight=None)

Return the degree of nodes in the graph

The degree (or valency) of a graph node are the number of edges connected to the node, with loops counted twice. The method supports weighted degrees in which the connected nodes are multiplied by a weight factor stored as attribute in the edges.

Parameters

  • graph (Graph class instance) – Graph to return the degree of nodes for

  • nodes (list) – nodes to return the degree for, None uses all nodes in the graph.

  • weight (string) – Weight factor attribute in the edges

Returns

degree of each node

Return type

list of tuples (node, degree)

graphit.graph_algorithms.node_neighbors(graph, nid)

Return de neighbor nodes of the node.

This method is not hierarchical and thus the root node has no effect.

Directed graphs and/or masked behaviour: masked nodes or directed nodes not having an edge from source to node will not be returned.

Parameters

  • graph (Graph class instance) – Graph to query

  • nid (:py:int) – node ID to return neighbors for

graphit.graph_algorithms.size(graph, weight=None, is_directed=None)

The graph size equals the total number of edges it contains

Parameters

  • graph (:graphit:Graph) – graph to calculate size for

  • weight (:py:str) – edge attribute name containing a weight value

Returns

graph size

Return type

:py:int, :py:float