← Back to branch summary

~ubuntu-branches/ubuntu/vivid/python-igraph/vivid

« back to all changes in this revision

Viewing changes to src/bfsiter.c

  • Committer: Package Import Robot
  • Author(s): TANIGUCHI Takaki
  • Date: 2012-03-17 17:23:55 UTC
  • Revision ID: package-import@ubuntu.com-20120317172355-e9iki37igmxnlq38
Tags: upstream-0.5.4
Import upstream version 0.5.4

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/bfsiter.c
 
1
/* -*- mode: C -*-  */
 
2
/* 
 
3
   IGraph library.
 
4
   Copyright (C) 2006  Gabor Csardi <csardi@rmki.kfki.hu>
 
5
   MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
 
6
   
 
7
   This program is free software; you can redistribute it and/or modify
 
8
   it under the terms of the GNU General Public License as published by
 
9
   the Free Software Foundation; either version 2 of the License, or
 
10
   (at your option) any later version.
 
11
   
 
12
   This program is distributed in the hope that it will be useful,
 
13
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
15
   GNU General Public License for more details.
 
16
   
 
17
   You should have received a copy of the GNU General Public License
 
18
   along with this program; if not, write to the Free Software
 
19
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
 
20
   02110-1301 USA
 
21
 
 
22
*/
 
23
 
 
24
#include "bfsiter.h"
 
25
#include "vertexobject.h"
 
26
#include "common.h"
 
27
#include "error.h"
 
28
 
 
29
/**
 
30
 * \ingroup python_interface
 
31
 * \defgroup python_interface_bfsiter BFS iterator object
 
32
 */
 
33
 
 
34
PyTypeObject igraphmodule_BFSIterType;
 
35
 
 
36
/**
 
37
 * \ingroup python_interface_bfsiter
 
38
 * \brief Allocate a new BFS iterator object for a given graph and a given root
 
39
 * \param g the graph object being referenced
 
40
 * \param vid the root vertex index
 
41
 * \param advanced whether the iterator should be advanced (returning distance and parent as well)
 
42
 * \return the allocated PyObject
 
43
 */
 
44
PyObject* igraphmodule_BFSIter_new(igraphmodule_GraphObject *g, PyObject *root, igraph_neimode_t mode, igraph_bool_t advanced) {
 
45
  igraphmodule_BFSIterObject* o;
 
46
  long int no_of_nodes, r;
 
47
  
 
48
  o=PyObject_GC_New(igraphmodule_BFSIterObject, &igraphmodule_BFSIterType);
 
49
  Py_INCREF(g);
 
50
  o->gref=g;
 
51
  o->graph=&g->g;
 
52
  
 
53
  if (!PyInt_Check(root) && !PyObject_IsInstance(root, (PyObject*)&igraphmodule_VertexType)) {
 
54
    PyErr_SetString(PyExc_TypeError, "root must be integer or igraph.Vertex");
 
55
    return NULL;
 
56
  }
 
57
  
 
58
  no_of_nodes=igraph_vcount(&g->g);
 
59
  o->visited=(char*)calloc(no_of_nodes, sizeof(char));
 
60
  if (o->visited == 0) {
 
61
    PyErr_SetString(PyExc_MemoryError, "out of memory");
 
62
    return NULL;
 
63
  }
 
64
  
 
65
  if (igraph_dqueue_init(&o->queue, 100)) {
 
66
    PyErr_SetString(PyExc_MemoryError, "out of memory");
 
67
    return NULL;
 
68
  }
 
69
  if (igraph_vector_init(&o->neis, 0)) {
 
70
    PyErr_SetString(PyExc_MemoryError, "out of memory");
 
71
    igraph_dqueue_destroy(&o->queue);
 
72
    return NULL;
 
73
  }
 
74
  
 
75
  if (PyInt_Check(root)) {
 
76
    r=PyInt_AsLong(root);
 
77
  } else {
 
78
    r=((igraphmodule_VertexObject*)root)->idx;
 
79
  }
 
80
  if (igraph_dqueue_push(&o->queue, r) ||
 
81
      igraph_dqueue_push(&o->queue, 0) ||
 
82
      igraph_dqueue_push(&o->queue, -1)) {
 
83
    igraph_dqueue_destroy(&o->queue);
 
84
    igraph_vector_destroy(&o->neis);
 
85
    PyErr_SetString(PyExc_MemoryError, "out of memory");
 
86
    return NULL;
 
87
  }
 
88
  o->visited[r]=1;
 
89
  
 
90
  if (!igraph_is_directed(&g->g)) mode=IGRAPH_ALL;
 
91
  o->mode=mode;
 
92
  o->advanced=advanced;
 
93
  
 
94
  PyObject_GC_Track(o);
 
95
  
 
96
  RC_ALLOC("BFSIter", o);
 
97
  
 
98
  return (PyObject*)o;
 
99
}
 
100
 
 
101
/**
 
102
 * \ingroup python_interface_bfsiter
 
103
 * \brief Support for cyclic garbage collection in Python
 
104
 * 
 
105
 * This is necessary because the \c igraph.BFSIter object contains several
 
106
 * other \c PyObject pointers and they might point back to itself.
 
107
 */
 
108
int igraphmodule_BFSIter_traverse(igraphmodule_BFSIterObject *self,
 
109
                                  visitproc visit, void *arg) {
 
110
  int vret;
 
111
 
 
112
  RC_TRAVERSE("BFSIter", self);
 
113
  
 
114
  if (self->gref) {
 
115
    vret=visit((PyObject*)self->gref, arg);
 
116
    if (vret != 0) return vret;
 
117
  }
 
118
  
 
119
  return 0;
 
120
}
 
121
 
 
122
/**
 
123
 * \ingroup python_interface_bfsiter
 
124
 * \brief Clears the iterator's subobject (before deallocation)
 
125
 */
 
126
int igraphmodule_BFSIter_clear(igraphmodule_BFSIterObject *self) {
 
127
  PyObject *tmp;
 
128
 
 
129
  PyObject_GC_UnTrack(self);
 
130
  
 
131
  tmp=(PyObject*)self->gref;
 
132
  self->gref=NULL;
 
133
  Py_XDECREF(tmp);
 
134
 
 
135
  igraph_dqueue_destroy(&self->queue);
 
136
  igraph_vector_destroy(&self->neis);
 
137
  free(self->visited);
 
138
  self->visited=0;
 
139
  
 
140
  return 0;
 
141
}
 
142
 
 
143
/**
 
144
 * \ingroup python_interface_bfsiter
 
145
 * \brief Deallocates a Python representation of a given BFS iterator object
 
146
 */
 
147
void igraphmodule_BFSIter_dealloc(igraphmodule_BFSIterObject* self) {
 
148
  igraphmodule_BFSIter_clear(self);
 
149
 
 
150
  RC_DEALLOC("BFSIter", self);
 
151
  
 
152
  PyObject_GC_Del(self);
 
153
}
 
154
 
 
155
PyObject* igraphmodule_BFSIter_iter(igraphmodule_BFSIterObject* self) {
 
156
  Py_INCREF(self);
 
157
  return (PyObject*)self;
 
158
}
 
159
 
 
160
PyObject* igraphmodule_BFSIter_iternext(igraphmodule_BFSIterObject* self) {
 
161
  if (!igraph_dqueue_empty(&self->queue)) {
 
162
    long int vid = igraph_dqueue_pop(&self->queue);
 
163
    long int dist = igraph_dqueue_pop(&self->queue);
 
164
    long int parent = igraph_dqueue_pop(&self->queue);
 
165
    long int i;
 
166
    
 
167
    if (igraph_neighbors(self->graph, &self->neis, vid, self->mode)) {
 
168
      igraphmodule_handle_igraph_error();
 
169
      return NULL;
 
170
    }
 
171
        
 
172
    for (i=0; i<igraph_vector_size(&self->neis); i++) {
 
173
      long int neighbor=VECTOR(self->neis)[i];
 
174
      if (self->visited[neighbor]==0) {
 
175
        self->visited[neighbor]=1;
 
176
        if (igraph_dqueue_push(&self->queue, neighbor) ||
 
177
            igraph_dqueue_push(&self->queue, dist+1) ||
 
178
            igraph_dqueue_push(&self->queue, vid)) {
 
179
          igraphmodule_handle_igraph_error();
 
180
          return NULL;
 
181
        }
 
182
      }
 
183
    }
 
184
 
 
185
    if (self->advanced) {
 
186
      PyObject *vertexobj, *parentobj, *result;
 
187
      vertexobj = igraphmodule_Vertex_New(self->gref, (long)vid);
 
188
      if (!vertexobj) return NULL;
 
189
      if (parent>=0) {
 
190
        parentobj = igraphmodule_Vertex_New(self->gref, (long)parent);
 
191
        if (!parentobj) return NULL;
 
192
      } else {
 
193
        Py_INCREF(Py_None);
 
194
        parentobj=Py_None;
 
195
      }
 
196
      result=PyTuple_New(3);
 
197
      PyTuple_SetItem(result, 0, vertexobj);
 
198
      PyTuple_SetItem(result, 1, PyInt_FromLong(dist));
 
199
      PyTuple_SetItem(result, 2, parentobj);
 
200
      return result;
 
201
    } else
 
202
      return igraphmodule_Vertex_New(self->gref, (long)vid);
 
203
  } else {
 
204
    return NULL;
 
205
  }
 
206
}
 
207
 
 
208
/**
 
209
 * \ingroup python_interface_bfsiter
 
210
 * Method table for the \c igraph.BFSIter object
 
211
 */
 
212
PyMethodDef igraphmodule_BFSIter_methods[] = {
 
213
  {NULL}
 
214
};
 
215
 
 
216
/** \ingroup python_interface_bfsiter
 
217
 * Python type object referencing the methods Python calls when it performs various operations on
 
218
 * a BFS iterator of a graph
 
219
 */
 
220
PyTypeObject igraphmodule_BFSIterType =
 
221
{
 
222
  PyObject_HEAD_INIT(NULL)                  //
 
223
  0,                                        // ob_size
 
224
  "igraph.BFSIter",                         // tp_name
 
225
  sizeof(igraphmodule_BFSIterObject),       // tp_basicsize
 
226
  0,                                        // tp_itemsize
 
227
  (destructor)igraphmodule_BFSIter_dealloc, // tp_dealloc
 
228
  0,                                        // tp_print
 
229
  0,                                        // tp_getattr
 
230
  0,                                        // tp_setattr
 
231
  0,                                        // tp_compare
 
232
  0,                                        // tp_repr
 
233
  0,                                        // tp_as_number
 
234
  0,                                        // tp_as_sequence
 
235
  0,                                        // tp_as_mapping
 
236
  0,                                        // tp_hash
 
237
  0,                                        // tp_call
 
238
  0,                                        // tp_str
 
239
  0,                                        // tp_getattro
 
240
  0,                                        // tp_setattro
 
241
  0,                                        // tp_as_buffer
 
242
  Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC, // tp_flags
 
243
  "igraph BFS iterator object",             // tp_doc
 
244
  (traverseproc) igraphmodule_BFSIter_traverse, /* tp_traverse */
 
245
  (inquiry) igraphmodule_BFSIter_clear,     /* tp_clear */
 
246
  0,                                        // tp_richcompare
 
247
  0,                                        // tp_weaklistoffset
 
248
  (getiterfunc)igraphmodule_BFSIter_iter,   /* tp_iter */
 
249
  (iternextfunc)igraphmodule_BFSIter_iternext, /* tp_iternext */
 
250
  0,                                        /* tp_methods */
 
251
  0,                                        /* tp_members */
 
252
  0,                                        /* tp_getset */
 
253
  0,                                        /* tp_base */
 
254
  0,                                        /* tp_dict */
 
255
  0,                                        /* tp_descr_get */
 
256
  0,                                        /* tp_descr_set */
 
257
  0,                                        /* tp_dictoffset */
 
258
  0,                                        /* tp_init */
 
259
  0,                                        /* tp_alloc */
 
260
  0,                                        /* tp_new */
 
261
  0,                                        /* tp_free */
 
262
};
 
263