Python: module bigraphMatching

bigraphMatching

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