class Matching:
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 |
Returns whether the given vertex is matched to another one. |
Method | is |
Returns whether the matching is maximal. |
Method | match |
Returns the vertex a given vertex is matched to. |
Method | matching |
Sets the matching vector. |
Method | types |
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 |
Undocumented |
Instance Variable | _types |
Undocumented |
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. |
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.
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.
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. |
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. |
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.