python-igraph manual

For using igraph from Python

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

Source Code for Module igraph.cut

  1  # vim:ts=4:sw=4:sts=4:et 
  2  # -*- coding: utf-8 -*- 
  3  """Classes representing cuts and flows on graphs.""" 
  4   
  5  from igraph.clustering import VertexClustering 
  6   
  7  __license__ = """\ 
  8  Copyright (C) 2006-2012  Tamás Nepusz <ntamas@gmail.com> 
  9  Pázmány Péter sétány 1/a, 1117 Budapest, Hungary 
 10   
 11  This program is free software; you can redistribute it and/or modify 
 12  it under the terms of the GNU General Public License as published by 
 13  the Free Software Foundation; either version 2 of the License, or 
 14  (at your option) any later version. 
 15   
 16  This program is distributed in the hope that it will be useful, 
 17  but WITHOUT ANY WARRANTY; without even the implied warranty of 
 18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 19  GNU General Public License for more details. 
 20   
 21  You should have received a copy of the GNU General Public License 
 22  along with this program; if not, write to the Free Software 
 23  Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA  
 24  02110-1301 USA 
 25  """ 
26 27 -class Cut(VertexClustering):
28 """A cut of a given graph. 29 30 This is a simple class used to represent cuts returned by 31 L{Graph.mincut()}, L{Graph.all_st_cuts()} and other functions 32 that calculate cuts. 33 34 A cut is a special vertex clustering with only two clusters. 35 Besides the usual L{VertexClustering} methods, it also has the 36 following attributes: 37 38 - C{value} - the value (capacity) of the cut. It is equal to 39 the number of edges if there are no capacities on the 40 edges. 41 42 - C{partition} - vertex IDs in the parts created 43 after removing edges in the cut 44 45 - C{cut} - edge IDs in the cut 46 47 - C{es} - an edge selector restricted to the edges 48 in the cut. 49 50 You can use indexing on this object to obtain lists of vertex IDs 51 for both sides of the partition. 52 53 This class is usually not instantiated directly, everything 54 is taken care of by the functions that return cuts. 55 56 Examples: 57 58 >>> from igraph import Graph 59 >>> g = Graph.Ring(20) 60 >>> mc = g.mincut() 61 >>> print mc.value 62 2.0 63 >>> print min(map(len, mc)) 64 1 65 >>> mc.es["color"] = "red" 66 """ 67 68 # pylint: disable-msg=R0913
69 - def __init__(self, graph, value=None, cut=None, partition=None, 70 partition2=None):
71 """Initializes the cut. 72 73 This should not be called directly, everything is taken care of by 74 the functions that return cuts. 75 """ 76 # Input validation 77 if partition is None or cut is None: 78 raise ValueError("partition and cut must be given") 79 80 # Set up a membership vector, initialize parent class 81 membership = [1] * graph.vcount() 82 for vid in partition: 83 membership[vid] = 0 84 VertexClustering.__init__(self, graph, membership) 85 86 if value is None: 87 # Value of the cut not given, count the number of edges 88 value = len(cut) 89 self._value = float(value) 90 91 self._partition = sorted(partition) 92 self._cut = cut 93
94 - def __repr__(self):
95 return "%s(%r, %r, %r, %r)" % \ 96 (self.__class__.__name__, self._graph, \ 97 self._value, self._cut, self._partition) 98
99 - def __str__(self):
100 return "Graph cut (%d edges, %d vs %d vertices, value=%.4f)" % \ 101 (len(self._cut), len(self._partition), 102 self._graph.vcount() - len(self._partition), self._value) 103 104 # pylint: disable-msg=C0103 105 @property
106 - def es(self):
107 """Returns an edge selector restricted to the cut""" 108 return self._graph.es.select(self.cut) 109 110 @property
111 - def partition(self):
112 """Returns the vertex IDs partitioned according to the cut""" 113 return list(self) 114 115 @property
116 - def cut(self):
117 """Returns the edge IDs in the cut""" 118 return self._cut 119 120 @property
121 - def value(self):
122 """Returns the sum of edge capacities in the cut""" 123 return self._value
124
125 126 -class Flow(Cut):
127 """A flow of a given graph. 128 129 This is a simple class used to represent flows returned by 130 L{Graph.maxflow}. It has the following attributes: 131 132 - C{graph} - the graph on which this flow is defined 133 134 - C{value} - the value (capacity) of the flow 135 136 - C{flow} - the flow values on each edge. For directed graphs, 137 this is simply a list where element M{i} corresponds to the 138 flow on edge M{i}. For undirected graphs, the direction of 139 the flow is not constrained (since the edges are undirected), 140 hence positive flow always means a flow from the smaller vertex 141 ID to the larger, while negative flow means a flow from the 142 larger vertex ID to the smaller. 143 144 - C{cut} - edge IDs in the minimal cut corresponding to 145 the flow. 146 147 - C{partition} - vertex IDs in the parts created 148 after removing edges in the cut 149 150 - C{es} - an edge selector restricted to the edges 151 in the cut. 152 153 This class is usually not instantiated directly, everything 154 is taken care of by L{Graph.maxflow}. 155 156 Examples: 157 158 >>> from igraph import Graph 159 >>> g = Graph.Ring(20) 160 >>> mf = g.maxflow(0, 10) 161 >>> print mf.value 162 2.0 163 >>> mf.es["color"] = "red" 164 """ 165 166 # pylint: disable-msg=R0913
167 - def __init__(self, graph, value, flow, cut, partition):
168 """Initializes the flow. 169 170 This should not be called directly, everything is 171 taken care of by L{Graph.maxflow}. 172 """ 173 super(Flow, self).__init__(graph, value, cut, partition) 174 self._flow = flow 175
176 - def __repr__(self):
177 return "%s(%r, %r, %r, %r, %r)" % \ 178 (self.__class__.__name__, self._graph, \ 179 self._value, self._flow, self._cut, self._partition) 180
181 - def __str__(self):
182 return "Graph flow (%d edges, %d vs %d vertices, value=%.4f)" % \ 183 (len(self._cut), len(self._partition), 184 self._graph.vcount() - len(self._partition), self._value) 185 186 @property
187 - def flow(self):
188 """Returns the flow values for each edge. 189 190 For directed graphs, this is simply a list where element M{i} 191 corresponds to the flow on edge M{i}. For undirected graphs, the 192 direction of the flow is not constrained (since the edges are 193 undirected), hence positive flow always means a flow from the smaller 194 vertex ID to the larger, while negative flow means a flow from the 195 larger vertex ID to the smaller. 196 """ 197 return self._flow
198

   Home       Trees       Indices       Help