Tools to perform bipartite graph matching.
 
The code in this module was originally used as described in:
 
Bermejo, G. A. and Llinas, M.; J. Am. Chem. Soc. 2008, 130, 3797-3805.
 
Please, cite the above reference if you find it useful. Coded by Guillermo A.
Bermejo.

Classes
		builtins.object Graph Bigraph TreeNode   class Bigraph(Graph)     Bigraph(links=None)   A Graph that represents an undirected bipartite graph (or bigraph).   The constructor call is something like:   g = Bigraph({'A': {'C': 2},              'B': {'C':1, 'D':2},              'dummy': {'E': 0, 'F': 0}})   This makes a bigraph with bipartition (V1, V2), where V1 = ['A', 'B'] and V2 = ['C', 'D', 'E', 'F'].  Note how the keys of the input dictionary are put into V1, while nodes (vertices) in their associated values into V2.  A 'dummy' node key can be used to add nodes into V2 which are not connected to any node in V1; the 'dummy' node itself is not kept. The partition method returns the (V1, V2) tuple representing the bipartition.     Method resolution order: Bigraph Graph builtins.object Methods defined here: __init__(self, links=None) Initialize self.  See help(type(self)) for accurate signature. partition(self) Return a tuple with two node lists representing the bipartition. remove_nodes(self, *nodes) Remove specified node(s) and the corresponding incident edges. Methods inherited from Graph: connect(self, a, b, weight=1) Add a link from a to b only if both a and b exist in the graph.   If the graph is undirected also the inverse link is added.  The weight of the link(s) is specified by the weight argument. disconnect(self, a, b) Remove link from a to b.   Also the inverse link is removed if the graph is undirected. get(self, a, b=None) Return a link weight or a dict of {node: weight} entries.   .get(A,B) returns the weight or None if link doesn't exist; .get(A) returns a dict of {node: weight} entries (possibly {}) or None if A doesn't exist. nodes(self) Return a list of nodes in the graph. update_weight(self, a, b, weight=1) Update weight of link from a to b (if the link already exists).   Also the weight of the inverse link is updated if the graph is undirected. Data descriptors inherited from Graph: __dict__   dictionary for instance variables (if defined) __weakref__   list of weak references to the object (if defined)   class Graph(builtins.object)     Graph(links=None, directed=True)   A general graph.   A graph connects nodes (vertices) by edges (links).  Each edge can also have a weight associated with it.  The constructor call is something like:     g = Graph({'A': {'B': 1, 'C': 2}}) This makes a graph with 3 nodes, A, B, and C, with an edge of weight 1 from A to B, and an edge of weight 2 from A to C.  You can also do:     g = Graph({'A': {'B': 1, 'C': 2}}, directed=False) This makes an undirected graph, so inverse links are also added.  The graph stays undirected; if you add more links with g.connect('B', 'C', 3), then inverse link is also added.  You can use g.nodes() to get a list of nodes, g.get('A') to get a dict of links out of A, and g.get('A', 'B') to get the weight of the link from A to B (or None if link doesn't exist).  'Weights' can actually be any object at all, and nodes can be any hashable object.   Extra functionality: g.disconnect('A', 'B') removes link from A to B (and the inverse link if graph is undirected). g.update_weight('A', 'B', 3) sets weight of A->B link to 3, only if link exists (the inverse link's weight is also updated in undirected case). g.remove_nodes('A', 'B') removes the specified nodes and their incident edges (in our example, the updated g contains C only).   This class has been adapted from:  Russell, S. J.; Norvig, P. Artificial Intelligence: a Modern Approach, 2nd ed.; Prentice Hall/Pearson Education: Upper Saddle River, NJ, 2003. The original class is covered by the MIT licence:     http://www.opensource.org/licenses/MIT     Methods defined here: __init__(self, links=None, directed=True) Initialize self.  See help(type(self)) for accurate signature. connect(self, a, b, weight=1) Add a link from a to b only if both a and b exist in the graph.   If the graph is undirected also the inverse link is added.  The weight of the link(s) is specified by the weight argument. disconnect(self, a, b) Remove link from a to b.   Also the inverse link is removed if the graph is undirected. get(self, a, b=None) Return a link weight or a dict of {node: weight} entries.   .get(A,B) returns the weight or None if link doesn't exist; .get(A) returns a dict of {node: weight} entries (possibly {}) or None if A doesn't exist. nodes(self) Return a list of nodes in the graph. remove_nodes(self, *nodes) Remove specified node(s) and its (their) incident edges. update_weight(self, a, b, weight=1) Update weight of link from a to b (if the link already exists).   Also the weight of the inverse link is updated if the graph is undirected. Data descriptors defined here: __dict__   dictionary for instance variables (if defined) __weakref__   list of weak references to the object (if defined)   class TreeNode(builtins.object)     TreeNode(element=None, parent=None)   A node in a tree data structure.   Contains a pointer to the parent node and to the element this node represents.  (Based on the search.Node class.)  A tree can be represented by a list of nodes, each of them being a tree leaf.  Recursive inquiries of parent attribute starting at a leaf, leads to the root node.     Methods defined here: __init__(self, element=None, parent=None) Create a search tree Node, derived from a parent. __repr__(self) Return repr(self). path(self) Create a list of nodes from the root to this node. Data descriptors defined here: __dict__   dictionary for instance variables (if defined) __weakref__   list of weak references to the object (if defined)

Functions
		UndirectedGraph(links=None) Return a Graph where every edge (including future ones) goes both ways. best_assign_Kuhn_Munkres(bigraph) Return optimal assignment in bigraph via the Kuhn-Munkres algorithm.   It follows the treatment by Bondy, J. and Murty R. (1976) "Graph theory with applications", New York, North Holland (Chapter 5, Fig. 5.17).  Given an input complete bipartite graph (a Bigraph), return a set of (x, y) ordered node pairs where x belongs to graph.partition()[0] and y to graph.partition()[1], representing the optimal assignment. build_Knn(bigraph, minimization=False) Return Knn based on an input bigraph.   Knn is a complete bigraph with n nodes in each partition subset.  Knn is build from the input bigraph by, if necessary,  adding ("dummy") nodes to the smaller node subset until its cardinality equals that of the bigger subset (i.e., n).  The edges of the input bigraph ("original edges") are kept in Knn, but new zero-weight edges are added to make the output bigraph complete.  If minimization=False [default] the weights of the original edges are kept.  If minimization=True the weights of the original edges are modified so that for each edge: new_weight = W - old_weight, where W is bigger (by 1) than the maximum weight in the input bigraph.  As a result, edges with big weight in input bigraph have small weight on output, and vice versa. build_equal_subgraph(bigraph, label) Return the equality subgraph of bigraph given the vertex labeling. edge_weights_sum(graph, edges) Return the sum of weights of the input edges in graph.   "edges" can be any container suporting membership test.  An edge within edges is a sequence of two of the graph vertices. get_path_edges(tree, element) Return a set with M-augmenting path egdes.   The M-augmenting path is the (root-element)-path in input tree. invert_graph_weights(graph) Update link weights of input graph (return nothing).   For all ij edges with non-zero weight wij, new_wij = W - wij, where W is larger than all the wij's.  Zero-weight edges are not updated. After the update, the originally maximum weight becomes the minimum (but not zero), the minimum (non-zero) becomes the maximum and so on.  This process can be thought as a sort of weight "inversion", hence the function name. k_best_assign(bigraph, K) Return a sorted list with the K best assignments in bigraph.   The matchings within the output list are sorted in non-increasing order of their weights.  It uses the general algorithm outlined by Asratian, A. S. et al. (1998) "Bipartite graphs and their applications", Cambridge, U.K. New York, Cambridge University Press. The restriction on this function to be used only for the assignment problem (in a bigraph) and not for the more general perfect matching problem (not in a bigraph) lies in its reliance on the Kuhn-Munkres algorithm for finding best matchings (assignments). new_tree(bigraph, tree, y, x=None) Return new M-alternating tree by adding elements y and x to input tree.   Input:  a tree (list of TreeNode inst.) with at list one node (the root).         y and (optional) x, where root and x belong to         bigraph.partition()[0] and y to bigraph.partition()[1] of input         bigraph.  If provided, x is a match of y (i.e., they are paired in         current matching in bigraph. Output: a new tree with added y and (optional) x.   Rules for tree growing: y is added anywhere in the tree, as long as the corresponding edge exists in bigraph.  If provided, x will be a child of y in the new tree. run_k_best_assign(bigraph, K) Return k_best_assign(bigraph, K).   This function handles any exeption raised by running k_best_assign and runs it again until it terminates properly.  k_best_assign may crash due to the randomization process introduced to deal with degeneracy. safe_eq(number1, number2) Return "safe" number1 == number2.   Compares the two input numbers taking into account floating-point inexactness.  It can also be used for integers.  Based on "The Perils of Floating Point" by Bruce M. Bush (http://www.lahey.com/float.htm). second_best_assign(bigraph, M_best) Return 2nd best assignment on bigraph given the best one.   An empty set is returned if the second best assignment doesn't exist.  It uses the general algorithm outlined in Chegireddy, C.R. & Hamacher, H. W. "Algorithms for finding k-best perfect matchings." Discrete Appl. Math. 18: 155-165, 1987. The restriction on this function to be used only for the assignment problem (in a bigraph) and not for the more general perfect matching problem (not in a bigraph) lies in its reliance on the Kuhn-Munkres algorithm for finding best matchings (assignments). second_best_restricted(bigraph, I, O) Return 2nd best assignment in bigraph from restricted solution space.   The restriction on the solution space is determined by Omega(I, O). The restriction on this function to be used only for the assignment problem (in a bigraph) and not for the more general perfect matching problem (not in a bigraph) lies in its reliance on the Kuhn-Munkres algorithm for finding best matchings (assignments). update(x, **entries) Update a dict; or an object with slots; according to entries. >>> update({'a': 1}, a=10, b=20) {'a': 10, 'b': 20} >>> update(Struct(a=1), a=10, b=20) Struct(a=10, b=20) update_labels(bigraph, label, S, T) Update vertex labeling in input bigraph (no return value).

Data
		EPSILON = 5e-07 infinity = 1e+100