data-structures - estructura - ejemplo de colas

Implementar una estructura de datos de tipo gráfico en Rust

Question

Tengo una estructura de datos que se puede representar como un gráfico unidireccional entre algunas estructuras vinculadas con objetos de enlace porque los enlaces contienen metadatos.

Se ve algo como esto:

struct StateMachine {
    resources: Vec<Resource>,
    links: Vec<Link>,
}
struct Resource {
    kind: ResourceType,
      // ...
}

enum LinkTarget {
    ResourceList(Vec<&Resource>),
    LabelSelector(HashMap<String, String>),
}

struct Link {
    from: LinkTarget,
    to: LinkTarget,
    metadata: SomeMetadataStruct,
}

Toda la estructura debe ser mutable porque necesito poder agregar y eliminar enlaces y recursos en tiempo de ejecución. Debido a esto, no puedo usar el modelo de vida normal y vincular los recursos a la vida de la estructura principal.

Entiendo que debo "elegir mi propia garantía" eligiendo el tipo apropiado, pero no estoy seguro de cuál es la mejor manera de resolver este problema.

Answer 1

En realidad, para una estructura de tipo gráfico, la solución más simple es usar un escenario como TypedArena .

La duración de los nodos dependerá únicamente de la duración de la instancia de la arena tipada desde la que se crearon, lo que simplificará enormemente la gestión de los recursos.

Advertencia : evite una situación en la que agregue / elimine dinámicamente nodos en el gráfico, ya que los nodos NO se eliminarán de la arena hasta que se suelte dicha arena, por lo que el tamaño de la arena crecerá, sin límites.

Si se encuentra en una situación en la que agregará / eliminará nodos en el tiempo de ejecución, otra solución es:

• tener una colección de Resources
• los bordes solo se refieren indirectamente a los Resources (no a los propietarios, ni tampoco a los prestatarios)

Dos ejemplos:

• HashMap<ResourceId, (Resource, Vec<ResourceId>)>
• type R = RefCell<Resource> , Vec<Rc<R>> y Vec<(Weak<R>, Vec<Weak<R>>)>

en cualquier caso, usted es responsable de limpiar los bordes al eliminar un recurso, y el olvido puede provocar una pérdida de memoria y pánico (al desreferenciar) pero, de lo contrario, es seguro.

Hay, probablemente, infinitas variaciones en lo anterior.

Answer 2

Modelar estructuras similares a gráficos en Rust no es un problema simple. Aquí hay dos discusiones valiosas de Nick Cameron y Niko Matsakis (dos desarrolladores principales de Rust en Mozilla).

Gráficos y asignación de arena

Modelado de gráficos en moho usando índices de vectores

Answer 3

La solución más simple para una estructura tipo gráfico es usar una biblioteca que modele gráficos . Petgraph es una buena opción:

extern crate petgraph;

use std::rc::Rc;
use std::collections::HashMap;

use petgraph::Graph;

struct Resource;

enum LinkTarget {
    ResourceList(Vec<Rc<Resource>>),
    LabelSelector(HashMap<String, String>),
}

struct SomeMetadataStruct;

fn main() {
    let mut graph = Graph::new();

    let n1 = graph.add_node(LinkTarget::LabelSelector(Default::default()));
    let n2 = graph.add_node(LinkTarget::LabelSelector(Default::default()));

    let l2 = graph.add_edge(n1, n2, SomeMetadataStruct);
}

Las garantías que tiene que elegir aquí se centran en el miembro de ResourceList . Supongo que desea tener Resource compartidos inmutables de un solo hilo.

• si necesita compartirlos entre subprocesos, use un Vec<Arc<Resource>>
• si no se comparten, Vec<Resource> - Vec<Resource>
• si necesitan ser mutables, use un Vec<Rc<RefCell<Resource>>> (O un Mutex si también es multihilo)