1
2
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
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
77 if partition is None or cut is None:
78 raise ValueError("partition and cut must be given")
79
80
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
88 value = len(cut)
89 self._value = float(value)
90
91 self._partition = sorted(partition)
92 self._cut = cut
93
95 return "%s(%r, %r, %r, %r)" % \
96 (self.__class__.__name__, self._graph, \
97 self._value, self._cut, self._partition)
98
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
105 @property
107 """Returns an edge selector restricted to the cut"""
108 return self._graph.es.select(self.cut)
109
110 @property
112 """Returns the vertex IDs partitioned according to the cut"""
113 return list(self)
114
115 @property
117 """Returns the edge IDs in the cut"""
118 return self._cut
119
120 @property
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
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
177 return "%s(%r, %r, %r, %r, %r)" % \
178 (self.__class__.__name__, self._graph, \
179 self._value, self._flow, self._cut, self._partition)
180
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
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