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: GPL-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 Graph.__init__(self, viter, eiter, directed)
32
34 """\
35 Add an edge to the fuzzy graph.
36
37 @param edge: The edge to add.
38 @type edge: L{FuzzyElement} of L{GraphEdge}
39 """
40 try:
41 if not isinstance(edge.obj, GraphEdge):
42 raise TypeError("edge must be a GraphEdge")
43 except AttributeError:
44 Graph.add_edge(self, edge)
45 if not edge.obj.tail in self.vertices \
46 or not edge.obj.head in self.vertices:
47 raise KeyError("tail and head must be in vertex set")
48 if edge.obj in self.edges():
49 raise ValueError("edge already exists")
50 self._E.add(edge)
51
52 @property
54 """\
55 Return a set of vertices in the fuzzy graph.
56
57 @rtype: C{set}
58 """
59 return set(self._V.keys())
60
61 - def edges(self, tail = None, head = None):
62 """\
63 Return a fuzzy set of edges with tail and/or head optionally
64 specified.
65
66 @param tail: The tail vertex constraint (optional).
67 @type tail: C{object}
68 @param head: The head vertex constraint (optional).
69 @type head: C{object}
70 @return: The fuzzy set of edges specified.
71 @rtype: L{FuzzySet}
72 """
73 if (tail is not None and not tail in self.vertices) \
74 or (head is not None and not head in self.vertices):
75 raise KeyError("specified tail/head must be in vertex set")
76 eset = set([edge.obj for edge in self._E \
77 if (tail is None or edge.obj.tail == tail) \
78 and (head is None or edge.obj.head == head)])
79 if not self.directed:
80 eset |= set([edge.obj for edge in self._E \
81 if (tail is None or edge.obj.head == tail) \
82 and (head is None or edge.obj.tail == head)])
83 return eset
84
85 - def mu(self, tail, head = None):
86 """\
87 Return the membership degree of a vertex or edge.
88
89 @param tail: The vertex or tail vertex.
90 @type tail: C{object}
91 @param head: The head vertex.
92 @type head: C{object}
93 @return: The membership degree of the vertex or edge from tail to head.
94 @rtype: C{float}
95 """
96 if head is None:
97 return self._V.mu(tail)
98 elif self.directed:
99 return self._E.mu(GraphEdge((tail, head)))
100 else:
101 return max(self._E.mu(GraphEdge((tail, head))),
102 self._E.mu(GraphEdge((head, tail))))
103
104 - def weight(self, tail, head):
105 """\
106 Return the weight of an edge. Returns the inverse of the membership
107 degree for a fuzzy graph.
108
109 @param tail: The tail vertex.
110 @type tail: C{object}
111 @param head: The head vertex.
112 @type head: C{object}
113 @return: The weight of the edge from tail to head.
114 @rtype: C{float}
115 """
116 if tail == head:
117 return 0.0
118 try:
119 return 1.0 / self.mu(tail, head)
120 except ZeroDivisionError:
121 return float('inf')
122
123
124
126 """\
127 Add a fuzzy vertex to the fuzzy graph (without explicitly constructing
128 a FuzzyElement for it). Convenience wrapper for add_vertex().
129
130 @param vertex: The vertex to add.
131 @type vertex: C{object}
132 @param mu: The membership degree of the vertex (optional).
133 @type mu: C{float}
134 """
135 self.add_vertex(FuzzyElement(vertex, mu))
136
138 """\
139 Add a fuzzy edge to the fuzzy graph (without explicitly constructing
140 a FuzzyElement for it). Convenience wrapper for add_edge().
141
142 @param edge: The edge to add.
143 @type edge: L{GraphEdge}
144 @param mu: The membership degree of the edge (optional).
145 @type mu: C{float}
146 """
147 self.add_edge(FuzzyElement(edge, mu))
148
150 """\
151 Connect a pair of vertices with a new fuzzy edge. Convenience wrapper
152 for add_edge().
153
154 @param tail: The tail vertex.
155 @type tail: C{object}
156 @param head: The head vertex.
157 @type head: C{object}
158 @param mu: The membership degree of the edge (optional).
159 @type mu: C{float}
160 """
161 self.add_edge(FuzzyElement(GraphEdge((tail, head)), mu))
162
163
164
165 @staticmethod
167 """\
168 Check that the other argument to a binary operation is also a fuzzy
169 graph, raising a TypeError otherwise.
170
171 @param other: The other argument.
172 @type other: L{FuzzyGraph}
173 """
174 if not isinstance(other, FuzzyGraph):
175 raise TypeError("binary operation only permitted between fuzzy \
176 graphs")
177
178
179
181 """\
182 Alpha cut function. Returns the crisp graph for which both vertex and
183 edge membership values meet or exceed the alpha value.
184
185 @param alpha: The alpha value for the cut in [0, 1].
186 @type alpha: C{float}
187 @return: The crisp graph result of the alpha cut.
188 @rtype: L{Graph}
189 """
190 Va = self._V.alpha(alpha)
191 Ea = set()
192 for edge in self._E.alpha(alpha):
193 if edge.tail in Va and edge.head in Va:
194 Ea.add(edge)
195 return Graph(Va, Ea, self.directed)
196
198 """\
199 Strong alpha cut function. Returns the crisp graph for which both
200 vertex and edge membership values exceed the alpha value.
201
202 @param alpha: The alpha value for the cut in [0, 1].
203 @type alpha: C{float}
204 @return: The crisp graph result of the strong alpha cut.
205 @rtype: L{Graph}
206 """
207 Va = self._V.salpha(alpha)
208 Ea = set()
209 for edge in self._E.salpha(alpha):
210 if edge.tail in Va and edge.head in Va:
211 Ea.add(edge)
212 return Graph(Va, Ea, self.directed)
213
215 """\
216 Normalize the fuzzy graph by normalizing its vertex and edge sets.
217 """
218 self._V.normalize()
219 self._E.normalize()
220