Submodules¶

halp.utilities.directed_graph_transformations module¶

halp.utilities.directed_graph_transformations.from_networkx_digraph(nx_digraph)[source]¶

Returns a DirectedHypergraph object that is the graph equivalent of the given NetworkX DiGraph object.

Parameters:	nx_digraph – the NetworkX directed graph object to transform.
Returns:	DirectedHypergraph – hypergraph object equivalent to the NetworkX directed graph.
Raises:	TypeError – Transformation only applicable to directed NetworkX graphs

halp.utilities.directed_graph_transformations.to_graph_decomposition(H)[source]¶

Returns a DirectedHypergraph object that has the same nodes (and corresponding attributes) as the given hypergraph, except that for all hyperedges in the given hypergraph, each node in the tail of the hyperedge is pairwise connected to each node in the head of the hyperedge in the new hypergraph. Said another way, each of the original hyperedges are decomposed in the new hypergraph into fully-connected bipartite components.

Parameters:	H – the hypergraph to decompose into a graph.
Returns:	DirectedHypergraph – the decomposed hypergraph.
Raises:	TypeError – Transformation only applicable to directed hypergraphs

halp.utilities.directed_graph_transformations.to_networkx_digraph(H)[source]¶

Returns a NetworkX DiGraph object that is the graph decomposition of the given hypergraph. See “to_graph_decomposition()” for more details.

Parameters:	H – the hypergraph to decompose into a graph.
Returns:	nx.DiGraph – NetworkX DiGraph object representing the decomposed hypergraph.
Raises:	TypeError – Transformation only applicable to directed hypergraphs

halp.utilities.directed_matrices module¶

halp.utilities.directed_matrices.fast_inverse(M)[source]¶

Computes the inverse of a diagonal matrix.

Parameters:	H – the diagonal matrix to find the inverse of.
Returns:	sparse.csc_matrix – the inverse of the input matrix as a sparse matrix.

halp.utilities.directed_matrices.get_head_incidence_matrix(H, nodes_to_indices, hyperedge_ids_to_indices)[source]¶

Creates the incidence matrix of the head nodes of the given hypergraph as a sparse matrix.

Parameters:	H – the hypergraph for which to create the incidence matrix of. nodes_to_indices – for each node, maps the node to its corresponding integer index. hyperedge_ids_to_indices – for each hyperedge ID, maps the hyperedge ID to its corresponding integer index.
Returns:	sparse.csc_matrix – the incidence matrix as a sparse matrix.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_matrices.get_hyperedge_degree_matrix(M)[source]¶

Creates the diagonal matrix of hyperedge degrees D_e as a sparse matrix, where a hyperedge degree is the cardinality of the hyperedge.

Parameters:	M – the incidence matrix of the hypergraph to find the D_e matrix on.
Returns:	sparse.csc_matrix – the diagonal hyperedge degree matrix as a sparse matrix.

halp.utilities.directed_matrices.get_hyperedge_id_mapping(H)[source]¶

Generates mappings between the set of hyperedge IDs and integer indices (where every hyperedge ID corresponds to exactly 1 integer index).

Parameters:	H – the hypergraph to find the hyperedge ID mapping on.
Returns:	dict – for each integer index, maps the index to the hyperedge ID. dict – for each hyperedge ID, maps the hyperedge ID to the integer index.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_matrices.get_hyperedge_weight_matrix(H, hyperedge_ids_to_indices)[source]¶

Creates the diagonal matrix W of hyperedge weights as a sparse matrix.

Parameters:	H – the hypergraph to find the weights. hyperedge_weights – the mapping from the indices of hyperedge IDs to the corresponding hyperedge weights.
Returns:	sparse.csc_matrix – the diagonal edge weight matrix as a sparse matrix.

halp.utilities.directed_matrices.get_node_mapping(H)[source]¶

Generates mappings between the set of nodes and integer indices (where every node corresponds to exactly 1 integer index).

Parameters:	H – the hypergraph to find the node mapping on.
Returns:	dict – for each integer index, maps the index to the node. dict – for each node, maps the node to the integer index.

halp.utilities.directed_matrices.get_tail_incidence_matrix(H, nodes_to_indices, hyperedge_ids_to_indices)[source]¶

Creates the incidence matrix of the tail nodes of the given hypergraph as a sparse matrix.

Parameters:	H – the hypergraph for which to create the incidence matrix of. nodes_to_indices – for each node, maps the node to its corresponding integer index. hyperedge_ids_to_indices – for each hyperedge ID, maps the hyperedge ID to its corresponding integer index.
Returns:	sparse.csc_matrix – the incidence matrix as a sparse matrix.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_matrices.get_vertex_degree_matrix(M, W)[source]¶

Creates the diagonal maxtrix D_v of vertex degrees as a sparse matrix, where a vertex degree is the sum of the weights of all hyperedges in the vertex’s star.

Parameters:	M – the incidence matrix of the hypergraph to find the D_v matrix on. W – the diagonal hyperedge weight matrix of the hypergraph.
Returns:	sparse.csc_matrix – the diagonal vertex degree matrix as a sparse matrix.

halp.utilities.directed_statistics module¶

halp.utilities.directed_statistics.hyperedge_cardinality_pairs_list(H)[source]¶

Returns a list of 2-tuples of (|tail|, |head|) for each hyperedge in the hypergraph.

Parameters:	H – the hypergraph whose cardinality ratios will be operated on.
Returns:	list – list of 2-tuples for each hyperedge’s cardinality.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.hyperedge_cardinality_ratio_list(H)[source]¶

Returns a list of the hypergraph’s hyperedges’ cardinality ratios. Use this to manually perform statistics on the hypergraph’s hyperedges’ cardinality ratios or to avoid the performance cost of calling several built-in statistics functions.

Parameters:	H – the hypergraph whose cardinality ratios are to be returned.
Returns:	list – cardinality ratios for each hyperedge in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.hyperedge_head_cardinality_list(H)[source]¶

Returns a list of the hypergraph’s hyperedges’ head cardinalities. Use this to manually perform statistics on the hypergraph’s hyperedges’ head cardinalities or to avoid the performance cost of calling several built-in statistics functions.

Parameters:	H – the hypergraph whose head cardinalities are to be returned.
Returns:	list – head cardinalities for each hyperedge in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.hyperedge_tail_cardinality_list(H)[source]¶

Returns a list of the hypergraph’s hyperedges’ tail cardinalities. Use this to manually perform statistics on the hypergraph’s hyperedges’ tail cardinalities or to avoid the performance cost of calling several built-in statistics functions.

Parameters:	H – the hypergraph whose tail cardinalities are to be returned.
Returns:	list – tail cardinalities for each hyperedge in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.indegree_list(H)[source]¶

Returns a list of the hypergraph’s nodes’ indegrees. Use this to manually perform statistics on the hypergraph’s nodes’ indegrees or to avoid the performance cost of calling several built-in statistics functions.

Parameters:	H – the hypergraph whose indegrees are to be returned.
Returns:	list – indegrees for each node in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.max_hyperedge_cardinality_ratio(H)[source]¶

Returns the hypergraph’s largest hyperedge cardinality ratio.

Parameters:	H – the hypergraph whose max hyperedge cardinality ratio is to be determined.
Returns:	int – the max hyperedge cardinality ratio in the graph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.max_hyperedge_head_cardinality(H)[source]¶

Returns the hypergraph’s largest hyperedge head cardinality.

Parameters:	H – the hypergraph whose max hyperedge head cardinality is to be determined.
Returns:	int – the max hyperedge head cardinality in the graph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.max_hyperedge_tail_cardinality(H)[source]¶

Returns the hypergraph’s largest hyperedge tail cardinality.

Parameters:	H – the hypergraph whose max hyperedge tail cardinality is to be determined.
Returns:	int – the max hyperedge tail cardinality in the graph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.max_indegree(H)[source]¶

Returns the hypergraph’s largest indegree.

Parameters:	H – the hypergraph whose max indegree is to be determined.
Returns:	int – the max indegree in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.max_outdegree(H)[source]¶

Returns the hypergraph’s largest outdegree.

Parameters:	H – the hypergraph whose max outdegree is to be determined.
Returns:	int – the max outdegree in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.mean_hyperedge_cardinality_ratio(H)[source]¶

Returns the hypergraph’s mean hyperedge cardinality ratio.

Parameters:	H – the hypergraph whose mean hyperedge cardinality ratio is to be determined.
Returns:	int – the mean hyperedge cardinality ratio in the graph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.mean_hyperedge_head_cardinality(H)[source]¶

Returns the hypergraph’s mean hyperedge head cardinality.

Parameters:	H – the hypergraph whose np.mean hyperedge head cardinality is to be determined.
Returns:	float – the np.mean hyperedge head cardinality in the graph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.mean_hyperedge_tail_cardinality(H)[source]¶

Returns the hypergraph’s mean hyperedge tail cardinality.

Parameters:	H – the hypergraph whose np.mean hyperedge tail cardinality is to be determined.
Returns:	float – the np.mean hyperedge tail cardinality in the graph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.mean_indegree(H)[source]¶

Returns the hypergraph’s mean indegree.

Parameters:	H – the hypergraph whose mean indegree is to be determined.
Returns:	float – the mean indegree in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.mean_outdegree(H)[source]¶

Returns the hypergraph’s mean outdegree.

Parameters:	H – the hypergraph whose mean outdegree is to be determined.
Returns:	float – the mean outdegree in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.min_hyperedge_cardinality_ratio(H)[source]¶

Returns the hypergraph’s smallest hyperedge cardinality ratio.

Parameters:	H – the hypergraph whose min hyperedge cardinality ratio is to be determined.
Returns:	int – the min hyperedge cardinality ratio in the graph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.min_hyperedge_head_cardinality(H)[source]¶

Returns the hypergraph’s smallest hyperedge head cardinality.

Parameters:	H – the hypergraph whose min hyperedge head cardinality is to be determined.
Returns:	int – the min hyperedge head cardinality in the graph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.min_hyperedge_tail_cardinality(H)[source]¶

Returns the hypergraph’s smallest hyperedge tail cardinality.

Parameters:	H – the hypergraph whose min hyperedge tail cardinality is to be determined.
Returns:	int – the min hyperedge tail cardinality in the graph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.min_indegree(H)[source]¶

Returns the hypergraph’s smallest indegree.

Parameters:	H – the hypergraph whose min indegree is to be determined.
Returns:	int – the min indegree in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.min_outdegree(H)[source]¶

Returns the hypergraph’s smallest outdegree.

Parameters:	H – the hypergraph whose min outdegree is to be determined.
Returns:	int – the min outdegree in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.number_of_hyperedges(H)[source]¶

Returns the number of hyperedges in the given hypergraph.

Parameters:	H – the hypergraph whose hyperedges are to be counted.
Returns:	int – number of hyperedges in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.number_of_nodes(H)[source]¶

Returns the number of nodes in the given hypergraph.

Parameters:	H – the hypergraph whose nodes are to be counted.
Returns:	int – number of nodes in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.directed_statistics.outdegree_list(H)[source]¶

Returns a list of the hypergraph’s nodes’ outdegrees. Use this to manually perform statistics on the hypergraph’s nodes’ outdegrees or to avoid the performance cost of calling several built-in statistics functions.

Parameters:	H – the hypergraph whose outdegrees are to be returned.
Returns:	list – outdegrees for each node in the hypergraph.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.utilities.priority_queue module¶

class halp.utilities.priority_queue.PriorityQueue[source]¶

Bases: object

Priority queue implementation based on the suggested “mark-as-invalid” technique by Python’s heapq documentation: https://docs.python.org/3.4/library/heapq.html#priority-queue-implementation-notes

Note:	This implementation only allows unique elements.

add_element(priority, element, count=None)[source]¶

Adds an element with a specific priority.

Parameters:	priority – priority of the element. element – element to add.

contains_element(element)[source]¶

Determines if an element is contained in the priority queue.”

Returns:	bool – true iff element is in the priority queue.

delete_element(element)[source]¶

Deletes an element (lazily).

Raises:	ValueError – No such element in the priority queue.

get_top_priority()[source]¶

Pops the element that has the top (smallest) priority.

Returns:	element with the top (smallest) priority.
Raises:	IndexError – Priority queue is empty.

is_empty()[source]¶

Determines if the priority queue has any elements. Performs removal of any elements that were “marked-as-invalid”.

Returns:	true iff the priority queue has no elements.

peek()[source]¶

Returns the element with top (lowest) priority without popping it.

Returns:	element with top (lowest) priority.
Raises:	IndexError – Priority queue is empty.

reprioritize(priority, element)[source]¶

Updates the priority of an element.

Raises:	ValueError – No such element in the priority queue.

halp.utilities.undirected_graph_transformations module¶

halp.utilities.undirected_graph_transformations.from_networkx_graph(nx_graph)[source]¶

Returns an UndirectedHypergraph object that is the graph equivalent of the given NetworkX Graph object.

Parameters:	nx_graph – the NetworkX undirected graph object to transform.
Returns:	UndirectedHypergraph – H object equivalent to the NetworkX undirected graph.
Raises:	TypeError – Transformation only applicable to undirected NetworkX graphs

halp.utilities.undirected_graph_transformations.to_graph_decomposition(H)[source]¶

Returns an UndirectedHypergraph object that has the same nodes (and corresponding attributes) as the given H, except that for all hyperedges in the given H, each node in the hyperedge is pairwise connected to every other node also in that hyperedge in the new H. Said another way, each of the original hyperedges are decomposed in the new H into cliques (aka the “2-section” or “clique graph”).

Parameters:	H – the H to decompose into a graph.
Returns:	UndirectedHypergraph – the decomposed H.
Raises:	TypeError – Transformation only applicable to undirected Hs

halp.utilities.undirected_graph_transformations.to_networkx_graph(H)[source]¶

Returns a NetworkX Graph object that is the graph decomposition of the given H. See “to_graph_decomposition()” for more details.

Parameters:	H – the H to decompose into a graph.
Returns:	nx.Graph – NetworkX Graph object representing the decomposed H.
Raises:	TypeError – Transformation only applicable to undirected Hs

halp.utilities.undirected_matrices module¶

halp.utilities.undirected_matrices.fast_inverse(M)[source]¶

Computes the inverse of a diagonal matrix.

Parameters:	H – the diagonal matrix to find the inverse of.
Returns:	sparse.csc_matrix – the inverse of the input matrix as a sparse matrix.

halp.utilities.undirected_matrices.get_hyperedge_degree_matrix(M)[source]¶

Creates the diagonal matrix of hyperedge degrees D_e as a sparse matrix, where a hyperedge degree is the cardinality of the hyperedge.

Parameters:	M – the incidence matrix of the hypergraph to find the D_e matrix on.
Returns:	sparse.csc_matrix – the diagonal hyperedge degree matrix as a sparse matrix.

halp.utilities.undirected_matrices.get_hyperedge_id_mapping(H)[source]¶

Generates mappings between the set of hyperedge IDs and integer indices (where every hyperedge ID corresponds to exactly 1 integer index).

Parameters:	H – the hypergraph to find the hyperedge ID mapping on.
Returns:	dict – for each integer index, maps the index to the hyperedge ID. dict – for each hyperedge ID, maps the hyperedge ID to the integer index.
Raises:	TypeError – Algorithm only applicable to undirected hypergraphs

halp.utilities.undirected_matrices.get_hyperedge_weight_matrix(H, hyperedge_ids_to_indices)[source]¶

Creates the diagonal matrix W of hyperedge weights as a sparse matrix.

Parameters:	H – the hypergraph to find the weights. hyperedge_weights – the mapping from the indices of hyperedge IDs to the corresponding hyperedge weights.
Returns:	sparse.csc_matrix – the diagonal edge weight matrix as a sparse matrix.

halp.utilities.undirected_matrices.get_incidence_matrix(H, nodes_to_indices, hyperedge_ids_to_indices)[source]¶

Creates the incidence matrix of the given hypergraph as a sparse matrix.

Parameters:	H – the hypergraph for which to create the incidence matrix of. nodes_to_indices – for each node, maps the node to its corresponding integer index. hyperedge_ids_to_indices – for each hyperedge ID, maps the hyperedge ID to its corresponding integer index.
Returns:	sparse.csc_matrix – the incidence matrix as a sparse matrix.
Raises:	TypeError – Algorithm only applicable to undirected hypergraphs

halp.utilities.undirected_matrices.get_node_mapping(H)[source]¶

Generates mappings between the set of nodes and integer indices (where every node corresponds to exactly 1 integer index).

Parameters:	H – the hypergraph to find the node mapping on.
Returns:	dict – for each integer index, maps the index to the node. dict – for each node, maps the node to the integer index.

halp.utilities.undirected_matrices.get_vertex_degree_matrix(M, W)[source]¶

Creates the diagonal maxtrix D_v of vertex degrees as a sparse matrix, where a vertex degree is the sum of the weights of all hyperedges in the vertex’s star.

Parameters:	M – the incidence matrix of the hypergraph to find the D_v matrix on. W – the diagonal hyperedge weight matrix of the hypergraph.
Returns:	sparse.csc_matrix – the diagonal vertex degree matrix as a sparse matrix.

Module contents¶