halp.algorithms package¶

Submodules¶

halp.algorithms.directed_paths module¶

halp.algorithms.directed_paths.b_visit(H, source_node)[source]¶

Executes the ‘B-Visit’ algorithm described in the paper: Giorgio Gallo, Giustino Longo, Stefano Pallottino, Sang Nguyen, Directed hypergraphs and applications, Discrete Applied Mathematics, Volume 42, Issues 2-3, 27 April 1993, Pages 177-201, ISSN 0166-218X, http://dx.doi.org/10.1016/0166-218X(93)90045-P. (http://www.sciencedirect.com/science/article/pii/0166218X9390045P)

The B-Visit algorithm begins from a source node and traverses a hyperedge after all nodes in the hyperedge’s tail have been reached.

Parameters:	H – the hypergraph to perform the ‘B-Visit’ algorithm on. source_node – the initial node to begin traversal from.
Returns:	set – nodes that were B-visited in this traversal. dict – mapping from each node visited to the ID of the hyperedge that preceeded it in this traversal. dict – mapping from each hyperedge ID to the node that preceeded it in this traversal. dict – mapping from each node to an integer representing the cardinality of the path from the source node to that node.

halp.algorithms.directed_paths.distance_function(tail_nodes, W)[source]¶

Additive distance (max) function for nodes in the tail of a hyperedge. Also commonly referred to as the ‘rank’ function.

Parameters:	tail_nodes – nodes in the tail of a hyperedge that, in conjunction with the weight of the hyperedge, will additively constitute the weight of the head node. W – node weighting function.
Returns:	int – max of the weights of tail_nodes.

halp.algorithms.directed_paths.f_visit(H, source_node)[source]¶

Executes the ‘F-Visit’ algorithm alluded to in the paper: Giorgio Gallo, Giustino Longo, Stefano Pallottino, Sang Nguyen, Directed hypergraphs and applications, Discrete Applied Mathematics, Volume 42, Issues 2-3, 27 April 1993, Pages 177-201, ISSN 0166-218X, http://dx.doi.org/10.1016/0166-218X(93)90045-P. (http://www.sciencedirect.com/science/article/pii/0166218X9390045P)

The F-Visit algorithm performs a B-Visit on the hypergraph’s symmetric image, beginning at the source node. Refer to ‘b_visit’s documentation for more details.

Parameters:	H – the hypergraph to perform the ‘F-Visit’ algorithm on. source_node – the initial node to begin traversal from.
Returns:	set – nodes that were F-visited in this traversal. dict – mapping from each node to the ID of the hyperedge that preceeded it in this traversal. dict – mapping from each hyperedge ID to the node that preceeded it in this traversal. dict – mapping from each node to an integer representing the cardinality of the path from the source node to that node.

halp.algorithms.directed_paths.gap_function(tail_nodes, W)[source]¶

Additive min function for nodes in the tail of a hyperedge.

Parameters:	tail_nodes – nodes in the tail of a hyperedge that, in conjunction with the weight of the hyperedge, will additively constitute the weight of the head node W – node weighting function
Returns:	int – max of the weights of tail_nodes

halp.algorithms.directed_paths.get_hyperpath_from_predecessors(H, Pv, source_node, destination_node, node_weights=None, attr_name='weight')[source]¶

Gives the hyperpath (DirectedHypergraph) representing the shortest B-hyperpath from the source to the destination, given a predecessor function and source and destination nodes.

Note:	The IDs of the hyperedges in the subhypergraph returned may be different than those in the original hypergraph (even though the tail and head sets are identical).
Parameters:	H – the hypergraph which the path algorithm was executed on. Pv – dictionary mapping each node to the ID of the hyperedge that preceeded it in the path. source_node – the source node of the path. destination_node – the destination node of the path.
Returns:	DirectedHypergraph – shortest B-hyperpath from source_node to destination_node.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs
Raises:	KeyError – Node key in predecessor is not in H
Raises:	KeyError – Hyperedge key in predecessor is not in H
Raises:	ValueError – Multiple nodes without predecessor
Raises:	ValueError – Hypertree does not have source node

halp.algorithms.directed_paths.get_hypertree_from_predecessors(H, Pv, source_node, node_weights=None, attr_name='weight')[source]¶

Gives the hypertree (i.e., the subhypergraph formed from the union of the set of paths from an execution of, e.g., the SBT algorithm) defined by Pv beginning at a source node. Returns a dictionary mapping each node to the ID of the hyperedge that preceeded it in the path (i.e., a Pv vector). Assigns the node weights (if provided) as attributes of the nodes (e.g., the rank of that node in a specific instance of the SBT algorithm, or the cardinality of that node in a B-Visit traversal, etc.).

Note:	The IDs of the hyperedges in the subhypergraph returned may be different than those in the original hypergraph (even though the tail and head sets are identical).
Parameters:	H – the hypergraph which the path algorithm was executed on. Pv – dictionary mapping each node to the ID of the hyperedge that preceeded it in the path. source_node – the root of the executed path algorithm. node_weights – [optional] dictionary mapping each node to some weight measure. attr_name – key into the nodes’ attribute dictionaries for their weight values (if node_weights is provided).
Returns:	DirectedHypergraph – subhypergraph induced by the path algorithm specified by the predecessor vector (Pv) from a source node.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.algorithms.directed_paths.is_b_connected(H, source_node, target_node)[source]¶

Checks if a target node is B-connected to a source node.

A node t is B-connected to a node s iff:

t is s, or
there exists an edge in the backward star of t such that all nodes in

the tail of that edge are B-connected to s

In other words, this method determines if a target node can be B-visited from the source node in the sense of the ‘B-Visit’ algorithm. Refer to ‘b_visit’s documentation for more details.

Parameters:	H – the hypergraph to check B-connectedness on. source_node – the node to check B-connectedness to. target_node – the node to check B-connectedness of.
Returns:	bool – whether target_node can be visited from source_node.

halp.algorithms.directed_paths.is_connected(H, source_node, target_node)[source]¶

Checks if a target node is connected to a source node. That is, this method determines if a target node can be visited from the source node in the sense of the ‘Visit’ algorithm.

Refer to ‘visit’s documentation for more details.

Parameters:	H – the hypergraph to check connectedness on. source_node – the node to check connectedness to. target_node – the node to check connectedness of.
Returns:	bool – whether target_node can be visited from source_node.

halp.algorithms.directed_paths.is_f_connected(H, source_node, target_node)[source]¶

Checks if a target node is F-connected to a source node.

A node t is F-connected to a node s iff s if B-connected to t. Refer to ‘f_visit’s or ‘is_b_connected’s documentation for more details.

Parameters:	H – the hypergraph to check F-connectedness on. source_node – the node to check F-connectedness to. target_node – the node to check F-connectedness of.
Returns:	bool – whether target_node can be visited from source_node.

halp.algorithms.directed_paths.shortest_b_tree(H, source_node, F=<function sum_function at 0x0000000004DA8128>, valid_ordering=False)[source]¶

Executes the Shortest B-Tree (SBT) algorithm described in the paper: Giorgio Gallo, Giustino Longo, Stefano Pallottino, Sang Nguyen, Directed hypergraphs and applications, Discrete Applied Mathematics, Volume 42, Issues 2-3, 27 April 1993, Pages 177-201, ISSN 0166-218X, http://dx.doi.org/10.1016/0166-218X(93)90045-P. (http://www.sciencedirect.com/science/article/pii/0166218X9390045P)

SBT finds a set of minimum weight B-paths from a source node to all the nodes y which are B-connected to it (when additive weight functions are used). Refer to ‘is_b_connected’s documentation for more details.

Parameters:	H – the hypergraph to perform the ‘SBT’ algorithm on. source_node – the root of the tree to be found. F – function pointer to any additive weight function; that is, any function that is only a function of the weights of the nodes in the tail of a hyperedge. valid_ordering – a boolean flag to signal whether or not a valid ordering of the nodes should be returned.
Returns:	dict – mapping from each node to the ID of the hyperedge that preceeded it in this traversal. dict – mapping from each node to the node’s weight. list – [only if valid_ordering argument is passed] a valid ordering of the nodes.

halp.algorithms.directed_paths.shortest_f_tree(H, source_node, F=<function sum_function at 0x0000000004DA8128>, valid_ordering=False)[source]¶

Executes the Shortest F-Tree algorithm, which is simply an execution of the Shorest B-Tree procedure from the source node on the hypergraph’s symmetric image. Refer to ‘shortest_b_tree’s documentation for more details.

Parameters:

Parameters:	hypergraph – the hypergraph to perform the ‘SFT’ algorithm on. source_node – the root of the tree to be found. F – function pointer to any additive weight function; that is, any function that is only a function of the weights of the nodes in the tail of a hyperedge. valid_ordering – a boolean flag to signal whether or not a valid ordering of the nodes should be returned.
Returns:	dict – mapping from each node to the ID of the hyperedge that preceeded it in this traversal. dict – mapping from each node to the node’s weight. list – [only if valid_ordering argument is passed] a valid ordering of the nodes.

hypergraph – the hypergraph to perform the ‘SFT’ algorithm on.
source_node – the root of the tree to be found.
F – function pointer to any additive weight function; that is, any function that is only a function of the weights of the nodes in the tail of a hyperedge.
valid_ordering – a boolean flag to signal whether or not a valid ordering of the nodes should be returned.

Returns:

dict – mapping from each node to the ID of the hyperedge that preceeded it in this traversal. dict – mapping from each node to the node’s weight. list – [only if valid_ordering argument is passed] a valid ordering of the nodes.

halp.algorithms.directed_paths.sum_function(tail_nodes, W)[source]¶

Additive sum function for nodes in the tail of a hyperedge.

Parameters:	tail_nodes – nodes in the tail of a hyperedge that, in conjunction with the weight of the hyperedge, will additively constitute the weight of the head node W – node weighting function.
Returns:	int – sum of the weights of tail_nodes.

halp.algorithms.directed_paths.visit(H, source_node)[source]¶

Executes the ‘Visit’ algorithm described in the paper: Giorgio Gallo, Giustino Longo, Stefano Pallottino, Sang Nguyen, Directed hypergraphs and applications, Discrete Applied Mathematics, Volume 42, Issues 2-3, 27 April 1993, Pages 177-201, ISSN 0166-218X, http://dx.doi.org/10.1016/0166-218X(93)90045-P. (http://www.sciencedirect.com/science/article/pii/0166218X9390045P)

The Visit algorithm begins from a source node and traverses a hyperedge after any node in the hyperedge’s tail has been reached.

Parameters:	H – the hypergraph to perform the ‘Visit’ algorithm on. source_node – the initial node to begin traversal from.
Returns:	set – nodes that were visited in this traversal. dict – mapping from each node to the ID of the hyperedge that preceeded it in this traversal; will map a node to None if that node wasn’t visited or if that node is the source node. dict – mapping from each hyperedge ID to the node that preceeded it in this traversal.
Raises:	TypeError – Algorithm only applicable to directed hypergraphs

halp.algorithms.directed_random_walk module¶

halp.algorithms.directed_random_walk.stationary_distribution(H, pi=None, P=None)[source]¶

Computes the stationary distribution of a random walk on the given hypergraph using the iterative approach explained in the paper: Aurelien Ducournau, Alain Bretto, Random walks in directed hypergraphs and application to semi-supervised image segmentation, Computer Vision and Image Understanding, Volume 120, March 2014, Pages 91-102, ISSN 1077-3142, http://dx.doi.org/10.1016/j.cviu.2013.10.012. (http://www.sciencedirect.com/science/article/pii/S1077314213002038)

Parameters:	H – the hypergraph to find the ‘Stationary Distribution’ algorithm on. pi – the initial distribution over the nodes. If not provided, it will be created with a random distribution. P – the transition matrix for the hypergraph. If not provided, it will be created.
Returns:	list – list of the stationary probabilities for all nodes in the hypergraph.
Raises:	TypeError – Algorithm only applicable to undirected hypergraphs
Raises:	AssertionError – Each node must have at least 1 outgoing hyperedge (even if it’s only a self-loop).

halp.algorithms.k_shortest_hyperpaths module¶

halp.algorithms.k_shortest_hyperpaths.k_shortest_hyperpaths(H, source_node, destination_node, k, F=<function sum_function at 0x0000000004DA8128>)[source]¶

Computes the k shortest hyperpaths from a source node to every other node in the hypergraph. This algorithm is only applicable to directed B-hypergraphs. The algorithm is described in the paper: Lars Relund Nielsen, Kim Allan Andersen, Daniele Pretolani, Finding the K shortest hyperpaths, Computers & Operations Research, Volume 32, Issue 6, June 2005, Pages 1477-1497, ISSN 0305-0548, http://dx.doi.org/10.1016/j.cor.2003.11.014. (http://www.sciencedirect.com/science/article/pii/S0305054803003459)

Parameters:	H – the hypergraph for which the function will compute the shortest hyperpaths. source_node – the source node in H for the path computation. destination_node – the destination node in H for the path computation. k – a positive integer indicating how many paths to compute. F – [optional] function used for the shortest path computation. See algorithms.directed_paths module for expected format of function.
Returns:	a list containing at most k hyperpaths (DirectedHypergraph) from source to destination in ascending order of path length.
Raises:	TypeError – Input hypergraph must be a B-hypergraph
Raises:	TypeError – Algorithm only applicable to directed hypergraphs
Raises:	ValueError – source_node must be a node in H
Raises:	ValueError – destination_node must be a node in H
Raises:	TypeError – k must be an integer
Raises:	ValueError – k must be a positive integer

halp.algorithms.undirected_partitioning module¶

halp.algorithms.undirected_partitioning.normalized_hypergraph_cut(H, threshold=0)[source]¶

Executes the min-cut algorithm described in the paper: Zhou, Dengyong, Jiayuan Huang, and Bernhard Scholkopf. “Learning with hypergraphs: Clustering, classification, and embedding.” Advances in neural information processing systems. 2006. (http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2006_630.pdf)

This algorithm uses the normalized Laplacian to partition the hypergraph into two disjoint components.

Parameters:	H – the hypergraph to perform the hypergraph-cut algorithm on. threshold – The threshold value for the partitioning algorithm. Typically, the value zero is selected for this purpose.
Returns:	set – the S set of nodes in the S-T partition set – the T set of nodes in the S-T partition
Raises:	TypeError – Algorithm only applicable to undirected hypergraphs

halp.algorithms.undirected_partitioning.stationary_distribution(H, pi=None, P=None)[source]¶

Computes the stationary distribution of a random walk on the given hypergraph using the iterative approach explained in the paper: (http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec15.pdf)

Parameters:	H – the hypergraph to find the stationary distribution on. pi – the initial distribution over the nodes. If not provided, it will be created with a random distribution. P – the transition matrix for the hypergraph. If not provided, it will be created.
Returns:	list – list of the stationary probabilities for all nodes in the hypergraph.
Raises:	TypeError – Algorithm only applicable to undirected hypergraphs

halp 1.0 documentation