¿Listas, colecciones...?
Mi pregunta es meramente teórica. Necesito un consejo.
Estoy realizando un proyecto relacionado con la música. En el integro aspectos visuales a través de las librería GLScene.
Me encuentro con una duda teórica.:
El usuario debe poder crear en tiempo de ejecución una estructura gráfica (un grafo pesado dirigido en notación algebraica) compuesto de: nodos en los que se especifican las notas y aristas en las que se indica el retardo entre la ejecución de dos nodos.
Para esto he definido un par de clases que heredan de la librería GLScene, o sea que son fundamentalmente visuales. Pero la parte visual ya está solucionada.
Mi problema es que el usuario debe poder crear tantas instancias como desee y que debe poder modificarlas en tiempo de ejecución y no sé en que tipo de estructura hacerlo para no perder demasiado tiempo cuando se modifiquen los enlaces o se eliminen elementos. El usuario no debe notar eso.
¿Listas, colecciones...? ¿Qué es más eficiente, más óptimo?. ¿Qué clases concretas debo usar?.
Datos relevantes:
- Las clases que he creado (TNodo y TArista) descienden de las clases GLScene: TGLSphere y TGLLines, que a su vez descienden de la conocida TComponent.
- Una arista tiene únicamente un nodo origen y un nodo destino que no se pueden modificar.
- Las aristas se crean (y se destruyen) sin ningún tipo de limitación.
- Una arista puede partir y llegar al mismo nodo. Puede haber ciclos (o sea, no es un árbol).
- De un nodo pueden partir (o llegar) de 0 a n aristas.
- Existe un nodo inicial (una simple propiedad true-false) que puede ser cambiado. Pero siempre habrá uno (único).
- Habrá un proceso (este no tiene que ser en tiempo real) que recorra la estructura al completo partiendo del inicio y desde ahí según indiquen las aristas para alamacenar únicamente la parte acústica de esta estructura.
- También debe poder almacenarse el grafo generado en su estado actual.
Estoy realizando un proyecto relacionado con la música. En el integro aspectos visuales a través de las librería GLScene.
Me encuentro con una duda teórica.:
El usuario debe poder crear en tiempo de ejecución una estructura gráfica (un grafo pesado dirigido en notación algebraica) compuesto de: nodos en los que se especifican las notas y aristas en las que se indica el retardo entre la ejecución de dos nodos.
Para esto he definido un par de clases que heredan de la librería GLScene, o sea que son fundamentalmente visuales. Pero la parte visual ya está solucionada.
Mi problema es que el usuario debe poder crear tantas instancias como desee y que debe poder modificarlas en tiempo de ejecución y no sé en que tipo de estructura hacerlo para no perder demasiado tiempo cuando se modifiquen los enlaces o se eliminen elementos. El usuario no debe notar eso.
¿Listas, colecciones...? ¿Qué es más eficiente, más óptimo?. ¿Qué clases concretas debo usar?.
Datos relevantes:
- Las clases que he creado (TNodo y TArista) descienden de las clases GLScene: TGLSphere y TGLLines, que a su vez descienden de la conocida TComponent.
- Una arista tiene únicamente un nodo origen y un nodo destino que no se pueden modificar.
- Las aristas se crean (y se destruyen) sin ningún tipo de limitación.
- Una arista puede partir y llegar al mismo nodo. Puede haber ciclos (o sea, no es un árbol).
- De un nodo pueden partir (o llegar) de 0 a n aristas.
- Existe un nodo inicial (una simple propiedad true-false) que puede ser cambiado. Pero siempre habrá uno (único).
- Habrá un proceso (este no tiene que ser en tiempo real) que recorra la estructura al completo partiendo del inicio y desde ahí según indiquen las aristas para alamacenar únicamente la parte acústica de esta estructura.
- También debe poder almacenarse el grafo generado en su estado actual.
3 respuestas
Respuesta
1
Es una pregunta bien compleja.
Si lo que que quieres es una estructura de datos que soporte un grafo, puedes utilizar varias posibilidades.
Pa mi gusto, lo mejor es que cada objeto que utilices para representar un nodo en el grafo contenga en sí mismo una lista (Un Tlist de aristas puede valerte) de los demás nodos a los que está conectado. Si quieres un grafo dirigido, puedes mantener en cada nodo dos listas, una de entradas y otra de salidas, o sólo una de las dos.
La ventaja es que desde cualquier nodo podrás seguir la pista hacia otros. Sólo tienes que mantener una variable que apunte a un nodo raíz del grafo.
En cuanto a poder crear y destruir, un detalle. Si son muchas creaciones/destrucciones (hablo de por ejemplo 200 o más, dependiendo de su tamaño también) por sesión de ejecución, puede producirse una degradación del sistema, ya que se va ocupando memoria, ya que no se recupera realmente la memoria de los objetos destruidos hasta que se cierra la aplicación. ( A mí me ha pasado en programas de este tipo...)
En ese caso tendrías que recurrir a técnicas de "garbage collection". Por ejemplo, en vez de destruir los objetos (aristas y nodos), cuando el usuario mande borrarlos, los guardas en una lista de objetos borrados, pero reutilizables. Si el usuario decide volver a crear un nodo, por ejemplo, si hay alguno en esta lista, echas mano de él, cambiándole las propiedades a las nuevas que el usuario quiera.
Por último, para guardar semejante estructura en disco... ánimo!
Te sugiero que identifiques cada nodo y arista de alguna manera (un nº clave). Cuando los guardes a disco, guardas su nº, las propiedades, y los números de los otros objetos con los que se conecta. Así podrás reconstruirlo.
Eso, sí, no es siempre sencillo.
Otra posibilidad es usar streaming (TStream) de los componentes, pero eso no me ha dado demasiado buen resultado.
Suerte!
Si lo que que quieres es una estructura de datos que soporte un grafo, puedes utilizar varias posibilidades.
Pa mi gusto, lo mejor es que cada objeto que utilices para representar un nodo en el grafo contenga en sí mismo una lista (Un Tlist de aristas puede valerte) de los demás nodos a los que está conectado. Si quieres un grafo dirigido, puedes mantener en cada nodo dos listas, una de entradas y otra de salidas, o sólo una de las dos.
La ventaja es que desde cualquier nodo podrás seguir la pista hacia otros. Sólo tienes que mantener una variable que apunte a un nodo raíz del grafo.
En cuanto a poder crear y destruir, un detalle. Si son muchas creaciones/destrucciones (hablo de por ejemplo 200 o más, dependiendo de su tamaño también) por sesión de ejecución, puede producirse una degradación del sistema, ya que se va ocupando memoria, ya que no se recupera realmente la memoria de los objetos destruidos hasta que se cierra la aplicación. ( A mí me ha pasado en programas de este tipo...)
En ese caso tendrías que recurrir a técnicas de "garbage collection". Por ejemplo, en vez de destruir los objetos (aristas y nodos), cuando el usuario mande borrarlos, los guardas en una lista de objetos borrados, pero reutilizables. Si el usuario decide volver a crear un nodo, por ejemplo, si hay alguno en esta lista, echas mano de él, cambiándole las propiedades a las nuevas que el usuario quiera.
Por último, para guardar semejante estructura en disco... ánimo!
Te sugiero que identifiques cada nodo y arista de alguna manera (un nº clave). Cuando los guardes a disco, guardas su nº, las propiedades, y los números de los otros objetos con los que se conecta. Así podrás reconstruirlo.
Eso, sí, no es siempre sencillo.
Otra posibilidad es usar streaming (TStream) de los componentes, pero eso no me ha dado demasiado buen resultado.
Suerte!
Hola de nuevo.
Antes de nada se trata de un grafo dirigido, así que la dirección de las aristas es importante.
En general tu propuesta se ajusta mucho a una de las versiones que estaba probando, y ya que somos dos los que creemos que esa es una buena solución... seguiré por ahí.
Después de leer tu respuesta me surgen un par de dudas.
Utilizo Delphi7, por si es determinante. Mis clases descienden de clases GLScene (TGLSphere y TGLLines) que en ultima instancia parten de TComponent y esto me plantea una pequeña duda:
¿No existirá ya algún método que guarde los objetos a disco?. Si no existe y debo crearlo yo, ¿debo almacenar todas y cada una de la propiedades del objeto o sólo las fundamentales o las que modifico durante la ejecución?, es que al ser componentes gráficos tienen muchísimas propiedades.
¿Cómo se hace esa grabación y cómo se recupera? (Más o menos, con un ejemplo simple o una referencia a una clase que implemente ese método y pueda consultar me llega). Porque no tengo muy claro como sería la recarga de la estructura almacenada ni el modo correcto de hacerlo.
Gracias de antemano.
Antes de nada se trata de un grafo dirigido, así que la dirección de las aristas es importante.
En general tu propuesta se ajusta mucho a una de las versiones que estaba probando, y ya que somos dos los que creemos que esa es una buena solución... seguiré por ahí.
Después de leer tu respuesta me surgen un par de dudas.
Utilizo Delphi7, por si es determinante. Mis clases descienden de clases GLScene (TGLSphere y TGLLines) que en ultima instancia parten de TComponent y esto me plantea una pequeña duda:
¿No existirá ya algún método que guarde los objetos a disco?. Si no existe y debo crearlo yo, ¿debo almacenar todas y cada una de la propiedades del objeto o sólo las fundamentales o las que modifico durante la ejecución?, es que al ser componentes gráficos tienen muchísimas propiedades.
¿Cómo se hace esa grabación y cómo se recupera? (Más o menos, con un ejemplo simple o una referencia a una clase que implemente ese método y pueda consultar me llega). Porque no tengo muy claro como sería la recarga de la estructura almacenada ni el modo correcto de hacerlo.
Gracias de antemano.
:-D Miles de millones de gracias, tu opinión me ha sido de gran ayuda. (Si no te "acoso" más con este tema es que ha salido bien.)
Efectivamente existen clases que permiten guardar componentes en disco. No las conozco a fondo, pero son las relacionadas con TStream. En cualquier caso, por mi experiencia, son complicadas de utilizar, y en tu caso no creo que sea lo mejor.
Te sugiero que determines qué propiedades de tus clases necesitas almacenar para luego poder restaurarlas.
Luego, puedes hacerte tu propio formato de almacenamiento. Yo tengo usado simplemente un formato del estilo
clave=valor
Algo así como los ficheros INI que había antes.
Por ejemplo, creas un objeto TSTRINGLIST, y vas guardando la información. Y puedes hacer un método que, para cada nodo del grafo, añade al Tstringlist una serie de línea de texto, del estilo:
Num_nodos=5
Nodo1_nombre=x
Color_nodo1=5565
aristas_salientes_nodo1=2
arista_hacia_nodo1=3
arista_hacia_nodo2=5
Nodo2_nombre=y
...
Y así para cada nodo y arista, por ejemplo. El tstringlist tiene una propiedad VALUES muy práctica para esto, porque puede añadir líneas de la forma:
stringlist['nodo1_nombre']='x';
Cuando acabas de meter todas las líneas en el tstringlist, basta usar el método Savetofile de este objeto para guardarlo en disco como un fichero de texto.
Para reconstruirlo a partir del fichero, operación inversa. Lees el fichero en un stringlist usando loadfromfile, y vas tratando cada línea del fichero. Por ejemplo, en la primera línea puedes haber guardado cuantos nodos hay que crear. Pues lees la línea y creas el nº de nodos indicado. Luego a cada nodo le asignas las propiedades que vayas leyendo, luego las aristas, etc...
Es laborioso, ya te lo digo, pero tiene la ventaja de que al tratarse de ficheros de texto, es fácil de depurar errores y ver qué es lo que funciona mal, o lo que sea.
Te sugiero que determines qué propiedades de tus clases necesitas almacenar para luego poder restaurarlas.
Luego, puedes hacerte tu propio formato de almacenamiento. Yo tengo usado simplemente un formato del estilo
clave=valor
Algo así como los ficheros INI que había antes.
Por ejemplo, creas un objeto TSTRINGLIST, y vas guardando la información. Y puedes hacer un método que, para cada nodo del grafo, añade al Tstringlist una serie de línea de texto, del estilo:
Num_nodos=5
Nodo1_nombre=x
Color_nodo1=5565
aristas_salientes_nodo1=2
arista_hacia_nodo1=3
arista_hacia_nodo2=5
Nodo2_nombre=y
...
Y así para cada nodo y arista, por ejemplo. El tstringlist tiene una propiedad VALUES muy práctica para esto, porque puede añadir líneas de la forma:
stringlist['nodo1_nombre']='x';
Cuando acabas de meter todas las líneas en el tstringlist, basta usar el método Savetofile de este objeto para guardarlo en disco como un fichero de texto.
Para reconstruirlo a partir del fichero, operación inversa. Lees el fichero en un stringlist usando loadfromfile, y vas tratando cada línea del fichero. Por ejemplo, en la primera línea puedes haber guardado cuantos nodos hay que crear. Pues lees la línea y creas el nº de nodos indicado. Luego a cada nodo le asignas las propiedades que vayas leyendo, luego las aristas, etc...
Es laborioso, ya te lo digo, pero tiene la ventaja de que al tratarse de ficheros de texto, es fácil de depurar errores y ver qué es lo que funciona mal, o lo que sea.
Respuesta de friki
1
En Delphi, las colecciones se implementan en la clase TCollection y las listas en la clase genérica TList.
Tcollection
-----------
Un TCollection es una lista de TCollectionItem o descendientes de este. Internamente el TCollection usa un TList para guardar
Los TCollectionItems. El modo de uso es crear clases descendientes de TCollectionItem para que la clase TCollection (o
Descendiente de esta) los almacene en su lista interna. La característica más revelante de TCollectionItem es su propiedad
"Collection" en la que se guarda el TCollection propietario del elemento.
El uso de TCollections&TCollectionItems es indicada para el desarrollo de componentes VCL (o CLX) que posean una colección de
Otros componentes: la lista de columnas de un TListView o de un TDBGrid, los parámetros de una consulta SQL, los campos de
Una tabla, etc... Los elementos de la colección no tienen porque ser componentes visuales, pero si que se resalta la
Necesidad de la propiedad "Collection" en la que se indica quién es el propietario del elemento. Esto puede ser útil si dado
Un elemento (un TCollectionItem) necesitamos saber cual es la colección que lo alberga. Asimismo, un TCollection guarda como
Propiedad su indice en la colección, así como un Id único (que sirve para identificar unívocamente al elemento dentro de la
Colección). Resumiendo: una colección es una lista especializada.
Ejemplos de TCollection: TCoolBands, TListColumns, TParams, TFieldDefs, ...
Ejemplos de TCollectionItem: TCoolBand, TListColumn, TParam, TFieldDef, ...
En cuanto a la eficiencia, al ser el TCollection un envoltorio de TList, la eficiencia es similar (está claro que el
TCollection sobrecarga el TList pero es constante y para un cierto nro. de elementos, despreciable). Más abajo analizo la
Eficiencia en los TList.
Sin embargo, el TCollection tiene una pega primordial para tus propósitos y es que los elementos de un TCollection deben
Descender de TCollectionItem y tus componentes ya descienden de otras clases y Delphi no permite la herencia múltiple.
TLIST
-----
Un TList implementa el Tipo Abstracto de Datos LISTA mediante un array de punteros. El array es creado dinámicamente y puede
Ser ampliado si es necesario. La propiedad Capacity indica el nro. de elementos que puede albergar y la propiedad Count el
nro. De elemento que alberga. Al añadir un elemento, si Count=Capacity, el TList incrementa Capacity en uno. Se puede
Aumentar la eficiencia si se dispone un valor inicial adecuado para Capacity, ya que incrementar esta propiedad supone
Ampliar la memoria reservada mediante la función ReallocMem.
Eficiencia:
- La inserción y el borrado son proporcionales al tamaño de la lista ya que requiere un movimiento del bloque contiguo a la
Posición donde se va a insertar/borrar el elemento. En el peor caso, requiere mover N-1 elementos de la lista una posición.
- La búsqueda es lineal respecto al tamaño de la lista. En el peor caso, se debe recorrer toda la lista para encontrar un
Elemento.
Lo mejor de los TList es su generalidad, pero no destaca por su eficiencia.
Puedes probar a tener dos TList: uno para tus TNodo y otro para almacenar TArista.
Ahora bien, si lo que deseas es mayor control y eficiencia sobre tu grafo deberás crear tu propia clase contenedora de nodos
Y aristas. El tipo de datos abstracto que creo que necesitas es el de GRAFO DIRIGIDO. En este tipo de grafo, las aristas van
En un sentido único. Es decir, si dos nodos v y w se conectan mediante la arista (v, w), entonces la arista (w, v) es otra
Diferente arista (o no se permite). Esto es solo una suposición por lo que he leído de tu pregunta (puedo estar equivocado) y
Es crucial para plantearse la estructura de datos necesaria.
La implementación de los grafos dirigidos variará según el uso que se haga de ellos, pero se suelen usar "matrices de
adyacencia". De manera algebraica:
Sea G={V,A} un grafo "G" dirigido de nodos o vértices "V" conectados mediante aristas "A". Si V={1,2,...,n}, entonces la
Matriz de adyacencia para G es una matriz n por n de elementos booleanos donde A[i, j] es verdadero si existe un arco que vaya
del vértice i al j.
Con esta representación, es sencillo (y eficiente) saber si dos nodos están unidos por una arista. El inconveniente es su
Tamaño: n por n. Para solucionar esto, se suele emplear las "listas de adyacencia". La lista de adyacencia para un vértice i es
Una lista, en algún orden, de todos los vértices (nodos) adyacentes a i. De esta manera, se necesita un espacio proporcional
A la suma del número de vértices más el número de aristas. Se usa bastante cuando el nro. de aristas es menor que n^2.
Hay muchos problemas clásicos respecto a los grafos dirigidos. Por ejemplo: Búsqueda de caminos más cortos -> algoritmo de
Dijkstra. En fin, que lo que más te puede ayudar es un buen libro del tema. Te he puesto uno en la bibliografía, pero hay
Muchos más.
Bibliografía:
"Estructuras de datos y algoritmos" Alfred V. Aho y otros. Ed. Addison-Wesley.
Tcollection
-----------
Un TCollection es una lista de TCollectionItem o descendientes de este. Internamente el TCollection usa un TList para guardar
Los TCollectionItems. El modo de uso es crear clases descendientes de TCollectionItem para que la clase TCollection (o
Descendiente de esta) los almacene en su lista interna. La característica más revelante de TCollectionItem es su propiedad
"Collection" en la que se guarda el TCollection propietario del elemento.
El uso de TCollections&TCollectionItems es indicada para el desarrollo de componentes VCL (o CLX) que posean una colección de
Otros componentes: la lista de columnas de un TListView o de un TDBGrid, los parámetros de una consulta SQL, los campos de
Una tabla, etc... Los elementos de la colección no tienen porque ser componentes visuales, pero si que se resalta la
Necesidad de la propiedad "Collection" en la que se indica quién es el propietario del elemento. Esto puede ser útil si dado
Un elemento (un TCollectionItem) necesitamos saber cual es la colección que lo alberga. Asimismo, un TCollection guarda como
Propiedad su indice en la colección, así como un Id único (que sirve para identificar unívocamente al elemento dentro de la
Colección). Resumiendo: una colección es una lista especializada.
Ejemplos de TCollection: TCoolBands, TListColumns, TParams, TFieldDefs, ...
Ejemplos de TCollectionItem: TCoolBand, TListColumn, TParam, TFieldDef, ...
En cuanto a la eficiencia, al ser el TCollection un envoltorio de TList, la eficiencia es similar (está claro que el
TCollection sobrecarga el TList pero es constante y para un cierto nro. de elementos, despreciable). Más abajo analizo la
Eficiencia en los TList.
Sin embargo, el TCollection tiene una pega primordial para tus propósitos y es que los elementos de un TCollection deben
Descender de TCollectionItem y tus componentes ya descienden de otras clases y Delphi no permite la herencia múltiple.
TLIST
-----
Un TList implementa el Tipo Abstracto de Datos LISTA mediante un array de punteros. El array es creado dinámicamente y puede
Ser ampliado si es necesario. La propiedad Capacity indica el nro. de elementos que puede albergar y la propiedad Count el
nro. De elemento que alberga. Al añadir un elemento, si Count=Capacity, el TList incrementa Capacity en uno. Se puede
Aumentar la eficiencia si se dispone un valor inicial adecuado para Capacity, ya que incrementar esta propiedad supone
Ampliar la memoria reservada mediante la función ReallocMem.
Eficiencia:
- La inserción y el borrado son proporcionales al tamaño de la lista ya que requiere un movimiento del bloque contiguo a la
Posición donde se va a insertar/borrar el elemento. En el peor caso, requiere mover N-1 elementos de la lista una posición.
- La búsqueda es lineal respecto al tamaño de la lista. En el peor caso, se debe recorrer toda la lista para encontrar un
Elemento.
Lo mejor de los TList es su generalidad, pero no destaca por su eficiencia.
Puedes probar a tener dos TList: uno para tus TNodo y otro para almacenar TArista.
Ahora bien, si lo que deseas es mayor control y eficiencia sobre tu grafo deberás crear tu propia clase contenedora de nodos
Y aristas. El tipo de datos abstracto que creo que necesitas es el de GRAFO DIRIGIDO. En este tipo de grafo, las aristas van
En un sentido único. Es decir, si dos nodos v y w se conectan mediante la arista (v, w), entonces la arista (w, v) es otra
Diferente arista (o no se permite). Esto es solo una suposición por lo que he leído de tu pregunta (puedo estar equivocado) y
Es crucial para plantearse la estructura de datos necesaria.
La implementación de los grafos dirigidos variará según el uso que se haga de ellos, pero se suelen usar "matrices de
adyacencia". De manera algebraica:
Sea G={V,A} un grafo "G" dirigido de nodos o vértices "V" conectados mediante aristas "A". Si V={1,2,...,n}, entonces la
Matriz de adyacencia para G es una matriz n por n de elementos booleanos donde A[i, j] es verdadero si existe un arco que vaya
del vértice i al j.
Con esta representación, es sencillo (y eficiente) saber si dos nodos están unidos por una arista. El inconveniente es su
Tamaño: n por n. Para solucionar esto, se suele emplear las "listas de adyacencia". La lista de adyacencia para un vértice i es
Una lista, en algún orden, de todos los vértices (nodos) adyacentes a i. De esta manera, se necesita un espacio proporcional
A la suma del número de vértices más el número de aristas. Se usa bastante cuando el nro. de aristas es menor que n^2.
Hay muchos problemas clásicos respecto a los grafos dirigidos. Por ejemplo: Búsqueda de caminos más cortos -> algoritmo de
Dijkstra. En fin, que lo que más te puede ayudar es un buen libro del tema. Te he puesto uno en la bibliografía, pero hay
Muchos más.
Bibliografía:
"Estructuras de datos y algoritmos" Alfred V. Aho y otros. Ed. Addison-Wesley.
Hola otra vez.
Antes de nada se trata de un grafo dirigido con arcos etiquetados (según la nomenclatura del libro que me recomiendas) en el que puede haber ciclos, y aristas que partan y lleguen al mismo nodo.
A priori puedo determinar el número máximo de nodos posibles en el sistema, pero no el número máximo de aristas. Por lo que la matriz de adyacencia no es demasiado viable.
No tengo que encontrar ningún camino mínimo, ni lo voy a emplear para el típico tratamiento matemático. Lo uso para crear música y lo único que tengo que hacer con él (a parte de crearlo y mantenerlo en tiempo real) es recorrerlo para rellenar una partitura con el contenido del grafo.
Tengo un nodo origen, que se define en tiempo de ejecución y puede cambiarse. Las aristas relacionan 2 nodos (mediante un puntero a estos): se crean o se destruyen y únicamente permito cambiar el "coste".
Creo que necesitaré una lista de punteros a nodos en la que el nodo origen sea el primer elemento. Y me inclino por definir dentro del nodo una propiedad lista que incluya punteros a las aristas que parten de él. Lo que me facilitaría recorrerlo (creo que es algo parecido a una lista de adyacencia).
¿Puede ser esta una solución adecuada para la utilización parcial del grafo que implemento o ves algún problema que se me escapa?.
Por último
Utilizo Delphi7, por si es determinante. Mis clases descienden de clases GLScene (TGLSphere y TGLLines) que en ultima instancia parten de TComponent y esto me plantea una duda:
¿Cómo guardo esta estructura en disco?, ¿Existe algún método que pueda consultar que haga algo así?
Gracias de antemano.
Antes de nada se trata de un grafo dirigido con arcos etiquetados (según la nomenclatura del libro que me recomiendas) en el que puede haber ciclos, y aristas que partan y lleguen al mismo nodo.
A priori puedo determinar el número máximo de nodos posibles en el sistema, pero no el número máximo de aristas. Por lo que la matriz de adyacencia no es demasiado viable.
No tengo que encontrar ningún camino mínimo, ni lo voy a emplear para el típico tratamiento matemático. Lo uso para crear música y lo único que tengo que hacer con él (a parte de crearlo y mantenerlo en tiempo real) es recorrerlo para rellenar una partitura con el contenido del grafo.
Tengo un nodo origen, que se define en tiempo de ejecución y puede cambiarse. Las aristas relacionan 2 nodos (mediante un puntero a estos): se crean o se destruyen y únicamente permito cambiar el "coste".
Creo que necesitaré una lista de punteros a nodos en la que el nodo origen sea el primer elemento. Y me inclino por definir dentro del nodo una propiedad lista que incluya punteros a las aristas que parten de él. Lo que me facilitaría recorrerlo (creo que es algo parecido a una lista de adyacencia).
¿Puede ser esta una solución adecuada para la utilización parcial del grafo que implemento o ves algún problema que se me escapa?.
Por último
Utilizo Delphi7, por si es determinante. Mis clases descienden de clases GLScene (TGLSphere y TGLLines) que en ultima instancia parten de TComponent y esto me plantea una duda:
¿Cómo guardo esta estructura en disco?, ¿Existe algún método que pueda consultar que haga algo así?
Gracias de antemano.
Tu solución para recorrer un camino del grafo me parece correcta. Con un TList te bastará, ya que solo necesitas recorrer la
Lista de manera lineal. No creo que te cause problemas.
Un grafo se compone de:
- Un conjunto de nodos, cada uno con sus atributos, en este caso una nota musical (que no tengo ni idea como la representas:
¿Un integer, un float, un record?). Este conjunto lo puedes guardar en memoria como una lista de punteros a los nodos
(TList), igual que para el camino, pero que alcance a todos los nodos y solo una vez.
- Las aristas que unen los nodos, además de unirlos, posee otra información adicional: el tiempo o retardo entre las dos
Notas.
Bien, ¿cómo representar las aristas? Si sabes de antemano el nro. máximo de nodos N, entonces como mucho habrán N por N aristas
Que los unan. Es decir, el producto cartesiano de los nodos. Esto incluye a las aristas que unen en ambos extremos al mismo
Nodo.
Date cuenta que no estoy hablando de caminos, en los que puede haber ciclos, sino de la estructura general del grafo. Los
Caminos los podemos representar, como tú muy bien propones, mediante una lista de punteros a los nodos. Tantos caminos
Podemos codificar como tantas listas de nodos tengamos. Ahora bien, si tienes la lista de nodos, fácilmente recorrible,
Necesitarás saber también qué arista une el nodo "i" con el nodo "i+1". Y para eso la matriz de adyacencia, que podrías
Implementarla (es una sugerencia), así:
type
TRetardo = double; // mera suposición de como lo has implementado
var
matriz_ady : array[1..N, 1..N] of TRetardo;
v: TRetardo;
En esta estructura, si:
v := matriz_ady[5,6];
En la variable "V" tenemos el retardo entre las notas 5 y 6. Si v = 0 (ó -1, quizás), podríamos decir que no hay arista entre
los nodos 5 y 6.
Como a una matriz se accede mediante un indice, cada nodo deberá guardar (como atributo) el indice que le corresponda dentro
De la matriz de adyacencia. Te sugiero una propiedad privada (o quizás protected) para el indice del nodo en la matriz. El
Indice puede ser de una o dos dimensiones, dependiendo de como implementes la matriz. (Es que se puede hacer de varias
Formas).
Ahora bien, si tus grafos poseen relativamente pocas aristas, la matriz tendrá muchos ceros y se desaprovechará espacio en
Memoria (y en el disco cuando se vuelque). Por esto, tenemos la alternativa de lista de adyacencias, que guarda solo lo que
Necesitamos. Casi con toda seguridad, es lo que te recomiendo para almacenar el grafo, junto con la lista completa de los
Mismos.
La lista de adyacencias yo la veo así:
var
lista_ady : array [1..N] of TList;
Donde
lista_ady[1] es la lista de nodos adyacentes al nodo 1
Otra alternativa, quizás más eficaz:
type
TElemNodo = record (* o class... *)
nodo: TNodo, (* ptro. al nodo inicial !!! *)
lista_ady: TList;
end;
var
ArrayAdy = array[1..N] of TElemNodo;
Para guardar estas estructuras en el disco, generalmente se suelen recorrer y guardar su contenido. También es aconsejable
Guardar las dimensiones de las listas para que cuando el archivo se precise para su lectura saber donde acaba una lista y
Acaba otra.
Por supuesto, todas estas estructuras de datos yo las implementaría mediante clases.
En cuanto a la librería GLScene, no la conozco, aunque me imagino que será una librería OpenGL. Es posible que tenga algún
Método de guardado de los objetos en archivos tipo vectorial o algo así. Mira en la documentación.
El hecho de que tus clases deriven de TComponent y este de TPersistent hace que sean serializables, por lo que se podrían
Guardar en el disco como un flujo. Esto te puede ser útil si deseas guardar tus nodos y aristas de igual manera de como los
Guarda Delphi.
Lo mejor es un ejemplo:
function ComponentToString(Component: TComponent): string;
var
BinStream:TMemoryStream;
StrStream: TStringStream;
s: string;
begin
BinStream := TMemoryStream.Create;
try
StrStream := TStringStream.Create(s);
try
BinStream.WriteComponent(Component);
BinStream.Seek(0, soFromBeginning);
ObjectBinaryToText(BinStream, StrStream);
StrStream.Seek(0, soFromBeginning);
Result:= StrStream.DataString;
finally
StrStream.Free;
end;
finally
BinStream.Free
end;
end;
function StringToComponent(Value: string): TComponent;
var
StrStream:TStringStream;
BinStream: TMemoryStream;
begin
StrStream := TStringStream.Create(Value);
try
BinStream := TMemoryStream.Create;
try
ObjectTextToBinary(StrStream, BinStream);
BinStream.Seek(0, soFromBeginning);
Result := BinStream.ReadComponent(nil);
finally
BinStream.Free;
end;
finally
StrStream.Free;
end;
end;
Con las 2 rutinas anteriores puedes leer/escribir toda clase descendiente de TComponent en un string. Si traduces todos los
tnodos y taristas a string perfectamente los puedes guardar en un fichero de texto. Por ejemplo, para guardar:
procedure Form1.OnClickButton(Sender: TObject);
var
i: Integer;
s: String;
F: TextFile;
begin
Assign(F, 'c:\programa musical\datos\datos00.txt');
Rewrite(F);
for i:= 0 to Self.ComponentCount-1 do
if Self.Components is TNodo then begin
s:= ComponentToString(Self.Components);
Write(F, s);
end;
CloseFile(F);
end;
Habría que hacer el proceso que leyera del archivo los componentes y los fuera creando dinámicamente.
Puedes simplificar el proceso usando unicamente TMemoryStream y guardando los componentes deseados en binario en vez de
Texto.
Lista de manera lineal. No creo que te cause problemas.
Un grafo se compone de:
- Un conjunto de nodos, cada uno con sus atributos, en este caso una nota musical (que no tengo ni idea como la representas:
¿Un integer, un float, un record?). Este conjunto lo puedes guardar en memoria como una lista de punteros a los nodos
(TList), igual que para el camino, pero que alcance a todos los nodos y solo una vez.
- Las aristas que unen los nodos, además de unirlos, posee otra información adicional: el tiempo o retardo entre las dos
Notas.
Bien, ¿cómo representar las aristas? Si sabes de antemano el nro. máximo de nodos N, entonces como mucho habrán N por N aristas
Que los unan. Es decir, el producto cartesiano de los nodos. Esto incluye a las aristas que unen en ambos extremos al mismo
Nodo.
Date cuenta que no estoy hablando de caminos, en los que puede haber ciclos, sino de la estructura general del grafo. Los
Caminos los podemos representar, como tú muy bien propones, mediante una lista de punteros a los nodos. Tantos caminos
Podemos codificar como tantas listas de nodos tengamos. Ahora bien, si tienes la lista de nodos, fácilmente recorrible,
Necesitarás saber también qué arista une el nodo "i" con el nodo "i+1". Y para eso la matriz de adyacencia, que podrías
Implementarla (es una sugerencia), así:
type
TRetardo = double; // mera suposición de como lo has implementado
var
matriz_ady : array[1..N, 1..N] of TRetardo;
v: TRetardo;
En esta estructura, si:
v := matriz_ady[5,6];
En la variable "V" tenemos el retardo entre las notas 5 y 6. Si v = 0 (ó -1, quizás), podríamos decir que no hay arista entre
los nodos 5 y 6.
Como a una matriz se accede mediante un indice, cada nodo deberá guardar (como atributo) el indice que le corresponda dentro
De la matriz de adyacencia. Te sugiero una propiedad privada (o quizás protected) para el indice del nodo en la matriz. El
Indice puede ser de una o dos dimensiones, dependiendo de como implementes la matriz. (Es que se puede hacer de varias
Formas).
Ahora bien, si tus grafos poseen relativamente pocas aristas, la matriz tendrá muchos ceros y se desaprovechará espacio en
Memoria (y en el disco cuando se vuelque). Por esto, tenemos la alternativa de lista de adyacencias, que guarda solo lo que
Necesitamos. Casi con toda seguridad, es lo que te recomiendo para almacenar el grafo, junto con la lista completa de los
Mismos.
La lista de adyacencias yo la veo así:
var
lista_ady : array [1..N] of TList;
Donde
lista_ady[1] es la lista de nodos adyacentes al nodo 1
Otra alternativa, quizás más eficaz:
type
TElemNodo = record (* o class... *)
nodo: TNodo, (* ptro. al nodo inicial !!! *)
lista_ady: TList;
end;
var
ArrayAdy = array[1..N] of TElemNodo;
Para guardar estas estructuras en el disco, generalmente se suelen recorrer y guardar su contenido. También es aconsejable
Guardar las dimensiones de las listas para que cuando el archivo se precise para su lectura saber donde acaba una lista y
Acaba otra.
Por supuesto, todas estas estructuras de datos yo las implementaría mediante clases.
En cuanto a la librería GLScene, no la conozco, aunque me imagino que será una librería OpenGL. Es posible que tenga algún
Método de guardado de los objetos en archivos tipo vectorial o algo así. Mira en la documentación.
El hecho de que tus clases deriven de TComponent y este de TPersistent hace que sean serializables, por lo que se podrían
Guardar en el disco como un flujo. Esto te puede ser útil si deseas guardar tus nodos y aristas de igual manera de como los
Guarda Delphi.
Lo mejor es un ejemplo:
function ComponentToString(Component: TComponent): string;
var
BinStream:TMemoryStream;
StrStream: TStringStream;
s: string;
begin
BinStream := TMemoryStream.Create;
try
StrStream := TStringStream.Create(s);
try
BinStream.WriteComponent(Component);
BinStream.Seek(0, soFromBeginning);
ObjectBinaryToText(BinStream, StrStream);
StrStream.Seek(0, soFromBeginning);
Result:= StrStream.DataString;
finally
StrStream.Free;
end;
finally
BinStream.Free
end;
end;
function StringToComponent(Value: string): TComponent;
var
StrStream:TStringStream;
BinStream: TMemoryStream;
begin
StrStream := TStringStream.Create(Value);
try
BinStream := TMemoryStream.Create;
try
ObjectTextToBinary(StrStream, BinStream);
BinStream.Seek(0, soFromBeginning);
Result := BinStream.ReadComponent(nil);
finally
BinStream.Free;
end;
finally
StrStream.Free;
end;
end;
Con las 2 rutinas anteriores puedes leer/escribir toda clase descendiente de TComponent en un string. Si traduces todos los
tnodos y taristas a string perfectamente los puedes guardar en un fichero de texto. Por ejemplo, para guardar:
procedure Form1.OnClickButton(Sender: TObject);
var
i: Integer;
s: String;
F: TextFile;
begin
Assign(F, 'c:\programa musical\datos\datos00.txt');
Rewrite(F);
for i:= 0 to Self.ComponentCount-1 do
if Self.Components is TNodo then begin
s:= ComponentToString(Self.Components);
Write(F, s);
end;
CloseFile(F);
end;
Habría que hacer el proceso que leyera del archivo los componentes y los fuera creando dinámicamente.
Puedes simplificar el proceso usando unicamente TMemoryStream y guardando los componentes deseados en binario en vez de
Texto.
Respuesta de apocalipsis0
1
No se si tienes conocimiento de que existen modos eficientes para implementar un grafo(que es realmente lo que tienes). Son las siguientes: utilizando una matriz de nxn, donde n es el numero de vértices(esto te limita, ya que si quieres crear un nuevo vértice, no puedes) y que guarda el coste o simplemente, la existencia del arco: Si existe una arista o arco que va desde el vértice nº5 al vértice nº10, y hacer eso me cuesta 5 unidades(podríamos decirse que cada vértice es una ciudad y cada arco una carretera, siendo el coste los litros de gasolina que se gastan)se debe colocar un numero(si es coste) o un 1(si solo se necesita saber si existe o no).
La implementación es muy sencilla, pero tiene el inconveniente que si el grafo tiene muchos vértices y pocos arcos, tendrás una matriz enorme llena de ceros(aun así, te beneficia en el tiempo de acceso)
Hay otra implementación, y se denomina lista de adyacencias. Consiste en una lista encadenada, donde solo se guardan los arcos que van de un vértice a otro. El problema es que hay que realizar una prebúsqueda para mirar si hay arco o no(no se si te interesaría). Seria más o menos así la lista:
Lista de vértices
a -> a
b -> c,d
c -> c,b,a
d -> nulo
En el ejemplo que te pongo habría un arco que partiría del vértice a y que vuelve al mismo vértice
Del vértice b habría un arco dirigido hacia el c, y otro hacia el d
Y por ultimo, el arco d es nulo.
Si quieres más información, te recomendaría buscar implementaciones y más teoría por internet, ya que esto es solo un atisbo de todo un mundo(se usa mucho en heurística y en inteligencia artificial). Suerte, y vuelve a preguntar si quieres.
La implementación es muy sencilla, pero tiene el inconveniente que si el grafo tiene muchos vértices y pocos arcos, tendrás una matriz enorme llena de ceros(aun así, te beneficia en el tiempo de acceso)
Hay otra implementación, y se denomina lista de adyacencias. Consiste en una lista encadenada, donde solo se guardan los arcos que van de un vértice a otro. El problema es que hay que realizar una prebúsqueda para mirar si hay arco o no(no se si te interesaría). Seria más o menos así la lista:
Lista de vértices
a -> a
b -> c,d
c -> c,b,a
d -> nulo
En el ejemplo que te pongo habría un arco que partiría del vértice a y que vuelve al mismo vértice
Del vértice b habría un arco dirigido hacia el c, y otro hacia el d
Y por ultimo, el arco d es nulo.
Si quieres más información, te recomendaría buscar implementaciones y más teoría por internet, ya que esto es solo un atisbo de todo un mundo(se usa mucho en heurística y en inteligencia artificial). Suerte, y vuelve a preguntar si quieres.