Welcome, guest | Sign In | My Account | Store | Cart

A directed Graph container can be useful for the collections module. This is a bare bones implementation, to show its basic API, a complete implementation is available. Many different graph implementations are possible, but I think this is flexible, fast and simple enough.

Python, 330 lines
  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
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
# Full implementation: http://sourceforge.net/projects/pynetwork/

class _GetterSetter(object):
    def __init__(self, g, n1):
        self._g = g
        self._n1 = n1
    def __setitem__(self, n2, arcw):
        self._g.addArc(self._n1, n2, arcw)
    def __getitem__(self, n2):
        return self._g.getArcw(self._n1, n2)
    def __str__(self):
        return "<Getter/setter of the arc starting from node: " + repr(self._n1) + ">"

class Graph(object):
    def __init__(self, nodesGraph=None, nodeData=None):
        if isinstance(nodesGraph, Graph):
            self.o = {}
            self.i = {}
            self_o = self.o
            self_i = self.i
            for n,a in nodesGraph.o.iteritems():
                self_o[n] = dict(a)
            for n,a in nodesGraph.i.iteritems():
                self_i[n] = dict(a)
            self.nodeData = dict(nodesGraph.nodeData)
            self.arcCount = nodesGraph.arcCount
            self.nextNode = nodesGraph.nextNode
        else:
            self.o = {} # Outbound arcs. Node name => outbound name arcs => arc weights.
            self.i = {} # Inbound arcs. Node name => inbound arc names => arc weights (oa transposed).
            self.nodeData = {} # Node data. Node name => optional data associated with the node
                               #   (not present means None).
            self.arcCount = 0  # Total number of directed arcs. Each self-loop is counted two times.
            self.nextNode = 0 # Next number that can be used by createID.
            if nodesGraph: # This can be made faster, but here controls are important.
                for n1, arcs in nodesGraph.iteritems():
                    self.addNode(n1)
                    for n2, w in arcs.iteritems():
                        self.addArc(n1, n2, w)
                if nodeData:
                    for node,data in nodeData.iteritems():
                        if node in self.o:
                            self.nodeData[node] = data

    def addNode(self, n, nodeData=None):
        if n not in self.o:
            self.o[n] = {}
            self.i[n] = {}
        if nodeData is None:
            if n in self.nodeData:
                del self.nodeData[n] # Not present nodeData is equivalent to None.
        else:
            self.nodeData[n] = nodeData

    add = addNode

    def __contains__(self, node):
        return node in self.o

    def getNodeData(self, n):
        if n in self.o and n in self.nodeData:
            return self.nodeData[n]

    def changeNodeData(self, n, newnd):
        if newnd is None:
            self.nodeData.pop(n, 0)
        elif n in self.o:
            self.nodeData[n] = newnd

    def renameNode(self, oldnode, newnode):
        self_o = self.o
        self_i = self.i
        if oldnode in self_o and oldnode in self_i and newnode not in self_o:
            self_o[newnode] = dict(self_o[oldnode])
            self_i[newnode] = dict(self_i[oldnode])
            for n,w in self_i[oldnode].iteritems():
                self_o[n][newnode] = w
                del self_o[n][oldnode]
            for n,w in self_o[oldnode].iteritems():
                self_i[n][newnode] = w
                del self_i[n][oldnode]
            if oldnode in self.nodeData:
                self.nodeData[newnode] = self.nodeData[oldnode]
                del self.nodeData[oldnode]
            del self_o[oldnode]
            del self_i[oldnode]

    def firstNode(self):
        if not self.o: return None
        return self.o.iterkeys().next()

    def delNode(self, n):
        self_o = self.o
        self_i = self.i
        if n in self_o and n in self_i:
            arcCount = self.arcCount
            if n in self_o[n]:
                del self_o[n][n]
                arcCount -= 2
            if n in self_i[n]:
                del self_i[n][n]
            for n1 in self_i[n].iterkeys():
                if n1 in self_o and n in self_o[n1]:
                    del self_o[n1][n]
                    arcCount -= 1
            for n1 in self_o[n].iterkeys():
                if n1 in self_i and n in self_i[n1]:
                    del self_i[n1][n]
            self.arcCount = arcCount - len(self_o[n])
            del self_o[n]
            del self_i[n]
            if n in self.nodeData:
                del self.nodeData[n]

    def popNode(self):
        if not self.o:
            raise IndexError("No items to select.")
        node = self.o.iterkeys().next()
        self.delNode(node) # remove it.
        return node

    def xinNodes(self, n):
        if n in self.i:
            return self.i[n].iterkeys()
        else:
            return []

    def xoutNodes(self, n):
        if n in self.o:
            return self.o[n].iterkeys()
        else:
            return []

    def __iter__(self):
        return self.o.iterkeys()

    def addArc(self, n1, n2, w=None):
        self_o = self.o
        self_i = self.i
        if n1 not in self_o:
            self_o[n1] = {}
            self_i[n1] = {}
        if n2 not in self_o:
            self_o[n2] = {}
            self_i[n2] = {}
        if n2 not in self_o[n1]:
            if n1 == n2:
                self.arcCount += 2
            else:
                self.arcCount += 1
        self_o[n1][n2] = w
        self_i[n2][n1] = w

    def __getitem__(self, n1):
        return _GetterSetter(self, n1)

    def hasArc(self, n1, n2):
        self_o = self.o
        self_i = self.i
        return ( n1 in self_o and n2 in self_o and n1 in self_i and n2 in self_i and
                 n2 in self_o[n1] and n1 in self_i[n2] )

    def getArcw(self, n1, n2):
        if n1 not in self.o:
            raise KeyError, repr(n1)
        if n2 not in self.o[n1]:
            raise KeyError, repr(n1) + " -> " + repr(n2)
        return self.o[n1][n2]

    def setArcw(self, n1, n2, neww):
        if n1 in self.o and n2 in self.o[n1]:
            self.o[n1][n2] = neww
        if n2 in self.i and n1 in self.i[n2]:
            self.i[n2][n1] = neww

    def delArc(self, n1, n2):
        if n1 in self.o and n2 in self.o[n1]:
            del self.o[n1][n2]
            if n1 == n2:
                self.arcCount -= 2
            else:
                self.arcCount -= 1
        if n2 in self.i and n1 in self.i[n2]:
            del self.i[n2][n1]

    def xinArcs(self, n):
        if n in self.i:
            return ((n1, n) for n1 in self.i[n].iterkeys())
        else:
            return []

    def xoutArcs(self, n):
        if n in self.o:
            return ((n, n1) for n1 in self.o[n].iterkeys())
        else:
            return []

    def xarcsw(self):
        self_o = self.o
        return ( (n1,n2,w) for n1,a in self_o.iteritems() for n2,w in a.iteritems() )

    def firstArc(self):
        if not self.arcCount: return None
        for n1,a in self.o.iteritems():
            if a: return n1, a.iterkeys().next()

    def copy(self):
        "copy(): return a shallow copy of the graph."
        return self.__class__(self)

    __copy__ = copy # For the copy module

    def clear(self):
        self.i.clear()
        self.o.clear()
        self.arcCount = 0
        self.nodeData.clear()
        self.nextNode = 0

    def __hash__(self):
        raise TypeError, "A Graph is a mutable, and cannot be hashed."

    def addUpdate(self, other):
        self._testBinary(other, "addUpdate")
        for n in other.o.iterkeys():
            if n not in self.o:
                self.o[n] = dict( other.o[n] )
                self.i[n] = dict( other.i[n] )
            else:
                self.o[n].update( other.o[n] )
                self.i[n].update( other.i[n] )
        self.nodeData.update( other.nodeData )
        self.nextNode = max(self.nextNode, other.nextNode)
        self._recountArcs()

    def subUpdate(self, other):
        self._testBinary(other, "subUpdate")
        for n1, a1 in other.o.iteritems():
            if n1 in self.o:
                for n2 in a1.iterkeys():
                    self.delArc(n1,n2)
                if not self.o[n1]:
                    self.delNode(n1)
        self._recountArcs()

    def intersection(self, other):
        self._testBinary(other, "intersection")
        common = self.__class__() # Necessary for a good subclassing.
        for n1 in set(self.o).intersection(other.o): # filter(d1_has_key, d2)
            if n1 not in common.o:
                common.o[n1] = {} # add empty node.
                common.i[n1] = {}
            for n2 in set(self.o[n1]).intersection(other.o[n1]):
                if n2 not in common.o:
                    common.o[n2] = {} # add empty node.
                    common.i[n2] = {}
                aux = self.o[n1][n2]
                if aux == other.o[n1][n2]:
                    w = aux
                else:
                    w = None
                common.o[n1][n2] = w
                common.i[n2][n1] = w
                if n1 == n2:
                    common.arcCount += 2
                else:
                    common.arcCount += 1
            nd = self.nodeData.get(n1)
            if nd != None and nd == other.nodeData.get(n1):
                common.nodeData[n1] = nd
        common.nextNode = max(self.nextNode, other.nextNode)
        return common

    def nodeIntersection(self, other):
        self._testBinary(other, "nodeIntersection")
        self_o_has_key = self.o.has_key
        other_o = other.o
        return filter(self_o_has_key, other_o)

    def __eq__(self, other):
        if isinstance(other, Graph):
            return self.o == other.o and self.i == other.i and \
                   self.arcCount == other.arcCount and self.nodeData == other.nodeData
        else:
            return False

    def __ne__(self, other):
        if isinstance(other, Graph):
            return self.o != other.o or self.i != other.i or \
                   self.arcCount != other.arcCount or self.nodeData != other.nodeData
        else:
            return True

    def _testBinary(self, other, sop):
        if not isinstance(other, type(self.__class__())):
            raise TypeError, sop + " only permitted between graphs."

    def order(self):
        return len(self.o)

    def size(self):
        return self.arcCount

    def __len__(self):
        return len(self.o)

    def __nonzero__(self):
        return bool(self.o)

    def __repr__(self):
        return "".join(["Graph(", repr(self.o), ", ", repr(self.nodeData), ")"])


# -------------------------
# A small demo, towns less then 1000 Km from Amsterdam:
table = (("Amsterdam", "Nijmegen",    122),
         ("Paris",     "Amsterdam",   490),
         ("Paris",     "Rome",       1140),
         ("Berlin",    "Amsterdam",   705),
         ("Amsterdam", "Kobenhaven",  764),
         ("Amsterdam", "Rome",       1640),
         ("Moscow",    "Amsterdam",  2523))
g = Graph()
for n1, n2, dist in table:
    g[n1][n2] = dist
    g[n2][n1] = dist
print g, "\n"
for city in g.xoutNodes("Amsterdam"):
    if g["Amsterdam"][city] < 1000:
        print city, g["Amsterdam"][city]

Any comment about the API (or on bugs, expecially in the full version) is appreciated.

A much longer and complete implementation with comments, docstrings, documentation, a test suite, various forms of nicer and shortened graph printing/showing, I/O in standard formats, 2D plotting with Tkinter and GraphPlotLib, shortest path and other basic algorithms, graph statistics, some other useful methods to manage many nodes or arcs at the same time, non iterative versions of methods like xnodes, graph visits like BFS and DFS, methods to manage bidirectional arcs, etc: http://sourceforge.net/projects/pynetwork/

For a faster C++ implementation the Boost Graph library can be used from Python too: http://www.boost.org/libs/graph/

3 comments

Zoran Isailovski 18 years, 2 months ago  # | flag

kjBuckets by Aaron Watters ... ... at http://starship.python.net/crew/aaron_watters/kjbuckets/ provides another graph implementation, and incorparates some nice ideas about combining sets, graphs, and dictionaries. You might want to check it out (in case you haven't already).

Ed Suominen 18 years, 2 months ago  # | flag

NetworkX. Cool, but this particular wheel's already been invented with the NetworkX package, "High Productivity Software for Complex Networks." See https://networkx.lanl.gov/. Perhaps you can look through your code to see if you could find some way to contribute parts of it to the NetworkX code base.

bearophile - (author) 18 years, 2 months ago  # | flag

Re: NetworkX. Wheels keep being re-invented all the time, and sometimes they improve other wheels. Some wheels look like "wheels" but their API is different, or they work in a different way, or they have different functions. Or maybe they are just older. Designing a good API is difficult, often you have to do it more than one time before finding a good one. I can count 6 other graph libraries beside NetworkX and Graph.

Perhaps you can look through your code to see if you could find some way to contribute parts of it to the NetworkX code base.

I think Graph already contains a small part of NetworkX, thank you for the offer. Looking at other people code is a strength of Open Source.

The purpose of this Recipe is mostly to show an API that can be discussed.

Created by bearophile - on Sat, 21 Jan 2006 (PSF)
Python recipes (4591)
bearophile -'s recipes (15)

Required Modules

  • (none specified)

Other Information and Tasks