forked from argriffing/xgcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
20080617b.py
76 lines (69 loc) · 2.52 KB
/
20080617b.py
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
"""Given an adjacency matrix, use its eigendecomposition to find a bipartition.
Given a weighted adjacency matrix,
use its eigendecomposition to find a bipartition.
"""
from StringIO import StringIO
import numpy as np
from SnippetUtil import HandlingError
import Util
import MatrixUtil
import Form
import FormOut
def get_form():
"""
@return: the body of a form
"""
# define the default matrix and its ordered labels
A = np.array([
[0, 2, 2],
[2, 0, 2],
[2, 2, 0]])
labels = list('abc')
# define the form objects
form_objects = [
Form.Matrix('matrix', 'weighted adjacency matrix',
A, MatrixUtil.assert_weighted_adjacency),
Form.MultiLine('labels', 'ordered labels', '\n'.join(labels)),
Form.RadioGroup('criterion', 'threshold criterion', [
Form.RadioItem('sign', 'sign cut', True),
Form.RadioItem('median', 'median cut')])]
return form_objects
def get_form_out():
return FormOut.Report()
def get_response_content(fs):
# read the matrix from the form data
A = fs.matrix
n = len(A)
if n < 3:
raise HandlingError('expected at least a 3x3 matrix')
# read the ordered labels
ordered_labels = Util.get_stripped_lines(StringIO(fs.labels))
# do the eigendecomposition
w, v = np.linalg.eigh(A)
eigenvalue_info = list(sorted((abs(x), i) for i, x in enumerate(w)))
stationary_eigenvector_index = eigenvalue_info[0][1]
fiedler_eigenvector_index = eigenvalue_info[1][1]
fiedler_eigenvector = v.T[fiedler_eigenvector_index]
# respond according to the criterion
out = StringIO()
selected_indices = None
if fs.sign:
selected_indices = set(i
for i, el in enumerate(fiedler_eigenvector) if el < 0)
elif fs.median:
element_index_pairs = list(sorted((el, i)
for i, el in enumerate(fiedler_eigenvector)))
selected_indices = set(index
for el, index in element_index_pairs[:n/2])
if not selected_indices:
raise HandlingError('found a degenerate bipartition')
# show the bipartition
selection = set(ordered_labels[i] for i in selected_indices)
complement = set(ordered_labels) - selection
smallest_cluster = min((len(selection), selection),
(len(complement), complement))[1]
print >> out, 'labels belonging to the smaller cluster:'
for label in sorted(smallest_cluster):
print >> out, label
# return the response
return out.getvalue()