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