/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2006 Gabor Csardi <csardi@rmki.kfki.hu>
MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA
*/
#include "bfsiter.h"
#include "vertexobject.h"
#include "common.h"
#include "error.h"
/**
* \ingroup python_interface
* \defgroup python_interface_bfsiter BFS iterator object
*/
PyTypeObject igraphmodule_BFSIterType;
/**
* \ingroup python_interface_bfsiter
* \brief Allocate a new BFS iterator object for a given graph and a given root
* \param g the graph object being referenced
* \param vid the root vertex index
* \param advanced whether the iterator should be advanced (returning distance and parent as well)
* \return the allocated PyObject
*/
PyObject* igraphmodule_BFSIter_new(igraphmodule_GraphObject *g, PyObject *root, igraph_neimode_t mode, igraph_bool_t advanced) {
igraphmodule_BFSIterObject* o;
long int no_of_nodes, r;
o=PyObject_GC_New(igraphmodule_BFSIterObject, &igraphmodule_BFSIterType);
o->gref=PyWeakref_NewRef((PyObject*)g, NULL);
o->graph=&g->g;
if (!PyInt_Check(root) && !PyObject_IsInstance(root, (PyObject*)&igraphmodule_VertexType)) {
PyErr_SetString(PyExc_TypeError, "root must be integer or igraph.Vertex");
return NULL;
}
no_of_nodes=igraph_vcount(&g->g);
o->visited=(char*)calloc(no_of_nodes, sizeof(char));
if (o->visited == 0) {
PyErr_SetString(PyExc_MemoryError, "out of memory");
return NULL;
}
if (igraph_dqueue_init(&o->queue, 100)) {
PyErr_SetString(PyExc_MemoryError, "out of memory");
return NULL;
}
if (igraph_vector_init(&o->neis, 0)) {
PyErr_SetString(PyExc_MemoryError, "out of memory");
igraph_dqueue_destroy(&o->queue);
return NULL;
}
if (PyInt_Check(root)) {
r=PyInt_AsLong(root);
} else {
r=((igraphmodule_VertexObject*)root)->idx;
}
if (igraph_dqueue_push(&o->queue, r) ||
igraph_dqueue_push(&o->queue, 0) ||
igraph_dqueue_push(&o->queue, -1)) {
igraph_dqueue_destroy(&o->queue);
igraph_vector_destroy(&o->neis);
PyErr_SetString(PyExc_MemoryError, "out of memory");
return NULL;
}
o->visited[r]=1;
if (!igraph_is_directed(&g->g)) mode=IGRAPH_ALL;
o->mode=mode;
o->advanced=advanced;
PyObject_GC_Track(o);
RC_ALLOC("BFSIter", o);
return (PyObject*)o;
}
/**
* \ingroup python_interface_bfsiter
* \brief Support for cyclic garbage collection in Python
*
* This is necessary because the \c igraph.BFSIter object contains several
* other \c PyObject pointers and they might point back to itself.
*/
int igraphmodule_BFSIter_traverse(igraphmodule_BFSIterObject *self,
visitproc visit, void *arg) {
int vret;
RC_TRAVERSE("BFSIter", self);
if (self->gref) {
vret=visit(self->gref, arg);
if (vret != 0) return vret;
}
return 0;
}
/**
* \ingroup python_interface_bfsiter
* \brief Clears the iterator's subobject (before deallocation)
*/
int igraphmodule_BFSIter_clear(igraphmodule_BFSIterObject *self) {
PyObject *tmp;
PyObject_GC_UnTrack(self);
tmp=self->gref;
self->gref=NULL;
Py_XDECREF(tmp);
igraph_dqueue_destroy(&self->queue);
igraph_vector_destroy(&self->neis);
free(self->visited);
self->visited=0;
return 0;
}
/**
* \ingroup python_interface_bfsiter
* \brief Deallocates a Python representation of a given BFS iterator object
*/
void igraphmodule_BFSIter_dealloc(igraphmodule_BFSIterObject* self) {
igraphmodule_BFSIter_clear(self);
RC_DEALLOC("BFSIter", self);
PyObject_GC_Del(self);
}
PyObject* igraphmodule_BFSIter_iter(igraphmodule_BFSIterObject* self) {
Py_INCREF(self);
return (PyObject*)self;
}
PyObject* igraphmodule_BFSIter_iternext(igraphmodule_BFSIterObject* self) {
if (!igraph_dqueue_empty(&self->queue)) {
long int vid = igraph_dqueue_pop(&self->queue);
long int dist = igraph_dqueue_pop(&self->queue);
long int parent = igraph_dqueue_pop(&self->queue);
long int i;
if (igraph_neighbors(self->graph, &self->neis, vid, self->mode)) {
igraphmodule_handle_igraph_error();
return NULL;
}
for (i=0; i<igraph_vector_size(&self->neis); i++) {
long int neighbor=VECTOR(self->neis)[i];
if (self->visited[neighbor]==0) {
self->visited[neighbor]=1;
if (igraph_dqueue_push(&self->queue, neighbor) ||
igraph_dqueue_push(&self->queue, dist+1) ||
igraph_dqueue_push(&self->queue, vid)) {
igraphmodule_handle_igraph_error();
return NULL;
}
}
}
if (self->advanced) {
PyObject *vertexobj, *parentobj, *result;
vertexobj = igraphmodule_Vertex_New(self->gref, (long)vid);
if (!vertexobj) return NULL;
if (parent>=0) {
parentobj = igraphmodule_Vertex_New(self->gref, (long)parent);
if (!parentobj) return NULL;
} else {
Py_INCREF(Py_None);
parentobj=Py_None;
}
result=PyTuple_New(3);
PyTuple_SetItem(result, 0, vertexobj);
PyTuple_SetItem(result, 1, PyInt_FromLong(dist));
PyTuple_SetItem(result, 2, parentobj);
return result;
} else
return igraphmodule_Vertex_New(self->gref, (long)vid);
} else {
return NULL;
}
}
/**
* \ingroup python_interface_bfsiter
* Method table for the \c igraph.BFSIter object
*/
PyMethodDef igraphmodule_BFSIter_methods[] = {
{NULL}
};
/** \ingroup python_interface_bfsiter
* Python type object referencing the methods Python calls when it performs various operations on
* a BFS iterator of a graph
*/
PyTypeObject igraphmodule_BFSIterType =
{
PyObject_HEAD_INIT(NULL) //
0, // ob_size
"igraph.BFSIter", // tp_name
sizeof(igraphmodule_BFSIterObject), // tp_basicsize
0, // tp_itemsize
(destructor)igraphmodule_BFSIter_dealloc, // tp_dealloc
0, // tp_print
0, // tp_getattr
0, // tp_setattr
0, // tp_compare
0, // tp_repr
0, // tp_as_number
0, // tp_as_sequence
0, // tp_as_mapping
0, // tp_hash
0, // tp_call
0, // tp_str
0, // tp_getattro
0, // tp_setattro
0, // tp_as_buffer
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC, // tp_flags
"igraph BFS iterator object", // tp_doc
0, // tp_traverse
0, // tp_clear
0, // tp_richcompare
0, // tp_weaklistoffset
(getiterfunc)igraphmodule_BFSIter_iter, /* tp_iter */
(iternextfunc)igraphmodule_BFSIter_iternext, /* tp_iternext */
0, /* tp_methods */
0, /* tp_members */
0, /* tp_getset */
0, /* tp_base */
0, /* tp_dict */
0, /* tp_descr_get */
0, /* tp_descr_set */
0, /* tp_dictoffset */
0, /* tp_init */
0, /* tp_alloc */
0, /* tp_new */
0, /* tp_free */
};
syntax highlighted by Code2HTML, v. 0.9.1