python-igraph manual

For using igraph from Python

   Home       Trees       Indices       Help   
Package igraph :: Module matching :: Class Matching
[hide private]

Class Matching

source code

object --+
         |
        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()
Instance Methods [hide private]
 
__init__(self, graph, matching, types=None)
Initializes the matching.
source code
 
__len__(self) source code
 
__repr__(self)
repr(x)
source code
 
__str__(self)
str(x)
source code
 
edges(self)
Returns an edge sequence that contains the edges in the matching.
source code
 
is_maximal(self)
Returns whether the matching is maximal.
source code
 
is_matched(self, vertex)
Returns whether the given vertex is matched to another one.
source code
 
match_of(self, vertex)
Returns the vertex a given vertex is matched to.
source code

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __setattr__, __sizeof__, __subclasshook__

Properties [hide private]
  graph
Returns the graph corresponding to the matching.
  matching
Returns the matching vector where element i contains the ID of the vertex that vertex i is matched to.
  types
Returns the type vector if the graph is bipartite.

Inherited from object: __class__

Method Details [hide private]

__init__(self, graph, matching, types=None)
(Constructor)

source code 

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.
Overrides: object.__init__

__repr__(self)
(Representation operator)

source code 

repr(x)

Overrides: object.__repr__
(inherited documentation)

__str__(self)
(Informal representation operator)

source code 

str(x)

Overrides: object.__str__
(inherited documentation)

edges(self)

source code 

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.

is_maximal(self)

source code 

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.

match_of(self, vertex)

source code 

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.

Property Details [hide private]

graph

Returns the graph corresponding to the matching.

Get Method:
unreachable.graph(self) - Returns the graph corresponding to the matching.

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.

Get Method:
unreachable.matching(self) - Returns the matching vector where element i contains the ID of the vertex that vertex i is matched to.
Set Method:
unreachable.matching(self, value) - Sets the matching vector.

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.

Get Method:
unreachable.types(self) - Returns the type vector if the graph is bipartite.
Set Method:
unreachable.types(self, value)

   Home       Trees       Indices       Help