python-igraph manual

For using igraph from Python

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

Source Code for Module igraph.matching

  1  # vim:ts=4:sw=4:sts=4:et 
  2  # -*- coding: utf-8 -*- 
  3  """Classes representing matchings on graphs.""" 
  4   
  5  from igraph.clustering import VertexClustering 
  6  from igraph._igraph import Vertex 
  7   
  8  __license__ = u"""\ 
  9  Copyright (C) 2006-2012  Tamás Nepusz <ntamas@gmail.com> 
 10  Pázmány Péter sétány 1/a, 1117 Budapest, Hungary 
 11   
 12  This program is free software; you can redistribute it and/or modify 
 13  it under the terms of the GNU General Public License as published by 
 14  the Free Software Foundation; either version 2 of the License, or 
 15  (at your option) any later version. 
 16   
 17  This program is distributed in the hope that it will be useful, 
 18  but WITHOUT ANY WARRANTY; without even the implied warranty of 
 19  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 20  GNU General Public License for more details. 
 21   
 22  You should have received a copy of the GNU General Public License 
 23  along with this program; if not, write to the Free Software 
 24  Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA  
 25  02110-1301 USA 
 26  """ 
27 28 -class Matching(object):
29 """A matching of vertices in a graph. 30 31 A matching of an undirected graph is a set of edges such that each 32 vertex is incident on at most one matched edge. When each vertex is 33 incident on I{exactly} one matched edge, the matching called 34 I{perfect}. This class is used in C{igraph} to represent non-perfect 35 and perfect matchings in undirected graphs. 36 37 This class is usually not instantiated directly, everything 38 is taken care of by the functions that return matchings. 39 40 Examples: 41 42 >>> from igraph import Graph 43 >>> g = Graph.Famous("noperfectmatching") 44 >>> matching = g.maximum_matching() 45 """ 46
47 - def __init__(self, graph, matching, types=None):
48 """Initializes the matching. 49 50 @param graph: the graph the matching belongs to 51 @param matching: a numeric vector where element I{i} corresponds to 52 vertex I{i} of the graph. Element I{i} is -1 or if the corresponding 53 vertex is unmatched, otherwise it contains the index of the vertex to 54 which vertex I{i} is matched. 55 @param types: the types of the vertices if the graph is bipartite. 56 It must either be the name of a vertex attribute (which will be 57 retrieved for all vertices) or a list. Elements in the list will be 58 converted to boolean values C{True} or C{False}, and this will 59 determine which part of the bipartite graph a given vertex belongs to. 60 @raise ValueError: if the matching vector supplied does not describe 61 a valid matching of the graph. 62 """ 63 self._graph = graph 64 self._matching = None 65 self._num_matched = 0 66 self._types = None 67 68 if isinstance(types, basestring): 69 types = graph.vs[types] 70 71 self.types = types 72 self.matching = matching 73
74 - def __len__(self):
75 return self._num_matched 76
77 - def __repr__(self):
78 if self._types is not None: 79 return "%s(%r,%r,types=%r)" % \ 80 (self.__class__.__name__, self._graph, self._matching, self._types) 81 else: 82 return "%s(%r,%r)" % \ 83 (self.__class__.__name__, self._graph, self._matching) 84
85 - def __str__(self):
86 if self._types is not None: 87 return "Bipartite graph matching (%d matched vertex pairs)" % len(self) 88 else: 89 return "Graph matching (%d matched vertex pairs)" % len(self) 90
91 - def edges(self):
92 """Returns an edge sequence that contains the edges in the matching. 93 94 If there are multiple edges between a pair of matched vertices, only one 95 of them will be returned. 96 """ 97 get_eid = self._graph.get_eid 98 eidxs = [get_eid(u, v, directed=False) \ 99 for u, v in enumerate(self._matching) if v != -1 and u <= v] 100 return self._graph.es[eidxs] 101 102 @property
103 - def graph(self):
104 """Returns the graph corresponding to the matching.""" 105 return self._graph 106
107 - def is_maximal(self):
108 """Returns whether the matching is maximal. 109 110 A matching is maximal when it is not possible to extend it any more 111 with extra edges; in other words, unmatched vertices in the graph 112 must be adjacent to matched vertices only. 113 """ 114 return self._graph._is_maximal_matching(self._matching, types=self._types) 115
116 - def is_matched(self, vertex):
117 """Returns whether the given vertex is matched to another one.""" 118 if isinstance(vertex, Vertex): 119 vertex = vertex.index 120 return self._matching[vertex] >= 0 121
122 - def match_of(self, vertex):
123 """Returns the vertex a given vertex is matched to. 124 125 @param vertex: the vertex we are interested in; either an integer index 126 or an instance of L{Vertex}. 127 @return: the index of the vertex matched to the given vertex, either as 128 an integer index (if I{vertex} was integer) or as an instance of 129 L{Vertex}. When the vertex is unmatched, returns C{None}. 130 """ 131 if isinstance(vertex, Vertex): 132 matched = self._matching[vertex.index] 133 if matched < 0: 134 return None 135 return self._graph.vs[matched] 136 137 matched = self._matching[vertex] 138 if matched < 0: 139 return None 140 return matched 141 142 @property
143 - def matching(self):
144 """Returns the matching vector where element I{i} contains the ID of 145 the vertex that vertex I{i} is matched to. 146 147 The matching vector will contain C{-1} for unmatched vertices. 148 """ 149 return self._matching 150 151 @matching.setter
152 - def matching(self, value):
153 """Sets the matching vector. 154 155 @param value: the matching vector which must contain the ID of the 156 vertex matching vertex I{i} at the I{i}th position, or C{-1} if 157 the vertex is unmatched. 158 @raise ValueError: if the matching vector supplied does not describe 159 a valid matching of the graph. 160 """ 161 if not self.graph._is_matching(value, types=self._types): 162 raise ValueError("not a valid matching") 163 self._matching = list(value) 164 self._num_matched = sum(1 for i in self._matching if i >= 0) // 2 165 166 @property
167 - def types(self):
168 """Returns the type vector if the graph is bipartite. 169 170 Element I{i} of the type vector will be C{False} or C{True} depending 171 on which side of the bipartite graph vertex I{i} belongs to. 172 173 For non-bipartite graphs, this property returns C{None}. 174 """ 175 return self._types 176 177 @types.setter
178 - def types(self, value):
179 types = [bool(x) for x in value] 180 if len(types) < self._graph.vcount(): 181 raise ValueError("type vector too short") 182 self._types = types
183

   Home       Trees       Indices       Help