1 """\
2 Graph module. Contains fuzzy graph class definitions.
3
4 @author: Aaron Mavrinac
5 @organization: University of Windsor
6 @contact: mavrin1@uwindsor.ca
7 @license: LGPL-3
8 """
9
10 from .fset import FuzzyElement, FuzzySet
11 from .graph import GraphEdge, Graph
15 """\
16 Fuzzy graph class.
17 """
18 _setcls = FuzzySet
19
20 - def __init__(self, viter=None, eiter=None, directed=True):
21 """\
22 Construct a fuzzy graph from optional iterables.
23
24 @param viter: The iterable for the vertex set (optional).
25 @type viter: C{object}
26 @param eiter: The iterable for the edge set (optional).
27 @type eiter: C{object}
28 @param directed: Defines the graph as directed or undirected.
29 @type directed: C{bool}
30 """
31 super(FuzzyGraph, self).__init__(viter=viter, eiter=eiter,
32 directed=directed)
33
35 """\
36 Add a fuzzy vertex to the fuzzy graph, optionally constructing the
37 vertex with the given membership degree.
38
39 @param vertex: The vertex to add.
40 @type vertex: C{object}
41 @param mu: The membership degree of the vertex (optional).
42 @type mu: C{float}
43 """
44 if not isinstance(vertex, FuzzyElement):
45 vertex = FuzzyElement(vertex, mu)
46 Graph.add_vertex(self, vertex)
47
49 """\
50 Add an edge to the fuzzy graph.
51
52 @param edge: The edge to add.
53 @type edge: L{FuzzyElement} of L{GraphEdge}
54 @param mu: The membership degree of the edge (optional).
55 @type mu: C{float}
56 """
57 if not isinstance(edge, FuzzyElement):
58 edge = FuzzyElement(edge, mu)
59 try:
60 if not isinstance(edge.index, GraphEdge):
61 raise TypeError('edge must be a GraphEdge')
62 except AttributeError:
63 Graph.add_edge(self, edge)
64 if not edge.index.tail in self.vertices() \
65 or not edge.index.head in self.vertices():
66 raise KeyError('tail and head must be in vertex set')
67 if edge.index in self.edges():
68 raise ValueError('edge already exists')
69 self._E.add(edge)
70
72 """\
73 Return a set of vertices in the fuzzy graph.
74
75 @rtype: C{set}
76 """
77 return set(self._V.keys())
78
79 - def edges(self, tail=None, head=None):
80 """\
81 Return a fuzzy set of edges with tail and/or head optionally
82 specified.
83
84 @param tail: The tail vertex constraint (optional).
85 @type tail: C{object}
86 @param head: The head vertex constraint (optional).
87 @type head: C{object}
88 @return: The fuzzy set of edges specified.
89 @rtype: L{FuzzySet}
90 """
91 if (tail is not None and not tail in self.vertices()) \
92 or (head is not None and not head in self.vertices()):
93 raise KeyError('specified tail/head must be in vertex set')
94 eset = set([edge.index for edge in self._E \
95 if (tail is None or edge.index.tail == tail) \
96 and (head is None or edge.index.head == head)])
97 if not self.directed:
98 eset |= set([edge.index for edge in self._E \
99 if (tail is None or edge.index.head == tail) \
100 and (head is None or edge.index.tail == head)])
101 return eset
102
103 - def mu(self, tail, head=None):
104 """\
105 Return the membership degree of a vertex or edge.
106
107 @param tail: The vertex or tail vertex.
108 @type tail: C{object}
109 @param head: The head vertex.
110 @type head: C{object}
111 @return: The membership degree of the vertex or edge from tail to head.
112 @rtype: C{float}
113 """
114 if head is None:
115 return self._V.mu(tail)
116 elif self.directed:
117 return self._E.mu(GraphEdge((tail, head)))
118 else:
119 return max(self._E.mu(GraphEdge((tail, head))),
120 self._E.mu(GraphEdge((head, tail))))
121
122 - def weight(self, tail, head):
123 """\
124 Return the weight of an edge. Returns the inverse of the membership
125 degree for a fuzzy graph.
126
127 @param tail: The tail vertex.
128 @type tail: C{object}
129 @param head: The head vertex.
130 @type head: C{object}
131 @return: The weight of the edge from tail to head.
132 @rtype: C{float}
133 """
134 if tail == head:
135 return 0.0
136 try:
137 return 1.0 / self.mu(tail, head)
138 except ZeroDivisionError:
139 return float('inf')
140
141 - def connect(self, tail, head, mu=1.0):
142 """\
143 Connect a pair of vertices with a new (fuzzy) edge.
144
145 @param tail: The tail vertex.
146 @type tail: C{object}
147 @param head: The head vertex.
148 @type head: C{object}
149 @param mu: The membership degree of the edge (optional).
150 @type mu: C{float}
151 """
152 self.add_edge(FuzzyElement(GraphEdge((tail, head)), mu))
153
154
155
156 @staticmethod
158 """\
159 Check that the other argument to a binary operation is also a fuzzy
160 graph, raising a TypeError otherwise.
161
162 @param other: The other argument.
163 @type other: L{FuzzyGraph}
164 """
165 if not isinstance(other, FuzzyGraph):
166 raise TypeError('operation only permitted between fuzzy graphs')
167
168
169
171 """\
172 Alpha cut function. Returns the crisp graph for which both vertex and
173 edge membership values meet or exceed the alpha value.
174
175 @param alpha: The alpha value for the cut in [0, 1].
176 @type alpha: C{float}
177 @return: The crisp graph result of the alpha cut.
178 @rtype: L{Graph}
179 """
180 Va = self._V.alpha(alpha)
181 Ea = set()
182 for edge in self._E.alpha(alpha):
183 if edge.tail in Va and edge.head in Va:
184 Ea.add(edge)
185 return Graph(viter=Va, eiter=Ea, directed=self.directed)
186
188 """\
189 Strong alpha cut function. Returns the crisp graph for which both
190 vertex and edge membership values exceed the alpha value.
191
192 @param alpha: The alpha value for the cut in [0, 1].
193 @type alpha: C{float}
194 @return: The crisp graph result of the strong alpha cut.
195 @rtype: L{Graph}
196 """
197 Va = self._V.salpha(alpha)
198 Ea = set()
199 for edge in self._E.salpha(alpha):
200 if edge.tail in Va and edge.head in Va:
201 Ea.add(edge)
202 return Graph(viter=Va, eiter=Ea, directed=self.directed)
203
205 """\
206 Normalize the fuzzy graph by normalizing its vertex and edge sets.
207 """
208 self._V.normalize()
209 self._E.normalize()
210