python-igraph API reference

class documentation

class Matching(object):

A matching of vertices in a graph.

A matching of an undirected graph is a set of edges such that each vertex is incident on at most one matched edge. When each vertex is incident on exactly one matched edge, the matching called perfect. This class is used in igraph to represent non-perfect and perfect matchings in undirected graphs.

This class is usually not instantiated directly, everything is taken care of by the functions that return matchings.

Examples:

>>> from igraph import Graph
>>> g = Graph.Famous("noperfectmatching")
>>> matching = g.maximum_matching()

Method	`__init__`	Initializes the matching.
Method	`__len__`	Undocumented
Method	`__repr__`	Undocumented
Method	`__str__`	Undocumented
Method	`edges`	Returns an edge sequence that contains the edges in the matching.
Method	`is_matched`	Returns whether the given vertex is matched to another one.
Method	`is_maximal`	Returns whether the matching is maximal.
Method	`match_of`	Returns the vertex a given vertex is matched to.
Method	`matching.setter`	Sets the matching vector.
Method	`types.setter`	Undocumented
Property	`graph`	Returns the graph corresponding to the matching.
Property	`matching`	Returns the matching vector where element i contains the ID of the vertex that vertex i is matched to.
Property	`types`	Returns the type vector if the graph is bipartite.
Instance Variable	`_graph`	Undocumented
Instance Variable	`_matching`	Undocumented
Instance Variable	`_num_matched`	Undocumented
Instance Variable	`_types`	Undocumented

def __init__(self, graph, matching, types=None): ¶

Initializes the matching.

Parameters
graph	the graph the matching belongs to
matching	a numeric vector where element i corresponds to vertex i of the graph. Element i is -1 or if the corresponding vertex is unmatched, otherwise it contains the index of the vertex to which vertex i is matched.
types	the types of the vertices if the graph is bipartite. It must either be the name of a vertex attribute (which will be retrieved for all vertices) or a list. Elements in the list will be converted to boolean values `True` or `False`, and this will determine which part of the bipartite graph a given vertex belongs to.
Raises
`ValueError`	if the matching vector supplied does not describe a valid matching of the graph.

def __len__(self): ¶

Undocumented

def __repr__(self): ¶

Undocumented

def __str__(self): ¶

Undocumented

def edges(self): ¶

Returns an edge sequence that contains the edges in the matching.

If there are multiple edges between a pair of matched vertices, only one of them will be returned.

def is_matched(self, vertex): ¶

Returns whether the given vertex is matched to another one.

def is_maximal(self): ¶

Returns whether the matching is maximal.

A matching is maximal when it is not possible to extend it any more with extra edges; in other words, unmatched vertices in the graph must be adjacent to matched vertices only.

def match_of(self, vertex): ¶

Returns the vertex a given vertex is matched to.

Parameters
vertex	the vertex we are interested in; either an integer index or an instance of `Vertex`.
Returns
the index of the vertex matched to the given vertex, either as an integer index (if vertex was integer) or as an instance of `Vertex`. When the vertex is unmatched, returns `None`.

@matching.setter
def matching(self, value): ¶

Sets the matching vector.

Parameters
value	the matching vector which must contain the ID of the vertex matching vertex i at the ith position, or `-1` if the vertex is unmatched.
Raises
`ValueError`	if the matching vector supplied does not describe a valid matching of the graph.

@types.setter
def types(self, value): ¶

Undocumented

@property
graph = ¶

Returns the graph corresponding to the matching.

@property
matching = ¶

Returns the matching vector where element i contains the ID of the vertex that vertex i is matched to.

The matching vector will contain -1 for unmatched vertices.

@property
types = ¶

Returns the type vector if the graph is bipartite.

Element i of the type vector will be False or True depending on which side of the bipartite graph vertex i belongs to.

For non-bipartite graphs, this property returns None.

_graph = ¶

Undocumented

_matching = ¶

Undocumented

_num_matched = ¶

Undocumented

_types = ¶

Undocumented

python-igraph API reference

igraph.matching.Matching

`igraph.matching.Matching`