python-igraph API reference

List of all classes, functions and methods in python-igraph

class documentation

class Matching:

View In Hierarchy

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
graphthe graph the matching belongs to
matchinga 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.
typesthe 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
ValueErrorif 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
vertexthe 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
valuethe 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
ValueErrorif 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