Crate graph

source ·
Expand description

Universidad Panamericana, Mexico City. Facultad de Ingeniería.

Daniel Alejandro Osornio López (0244685@up.edu.mx), Daniel Hernandez Toledo (0243179@up.edu.mx)

A graph is a collection of nodes and edges. This is a wrapper around the petgraph crate. It provides a set of methods to manipulate the graph. It also provides a set of macros to create graphs with ease. The graph is generic over the following types:

  • I: The type of the node identifier
  • N: The type of the node data
  • E: The type of the edge data
  • Ty: The type of the edge
  • Ix: The type of the index

petgraph uses an adjacency list to represent the graph.

The traversal algorithms are implemented in the walkers module. The walkers are state machines that implement the Walker<T> trait that provides the step method to move the walker to the next node in the graph according to the algorithm.

All solutions are represented as a singly linked list of Step<T, Ix> instances.

The rrand module provides a set of random graph generators.

Re-exports

Modules

  • rrand
    Random number generator based on the getrandom crate. You may want to take a look at:
  • step
    Implementation of the Step struct for traversal representation.
  • walkers
    Implementations of the Walker<T> trait for various traversal algorithms.

Macros

  • count
    Counts the number of nodes and edges of the graph
  • graph
    Declarative way to create Graph instances with ease.

Structs

  • EdgeIndex
    Edge identifier.
  • Graph
    The library’s principal Graph structure.
  • Node
    A node in the graph with a name and a location.
  • NodeIndex
    Node identifier.
  • PGraph
    StableGraph<N, E, Ty, Ix> is a graph datastructure using an adjacency list representation.

Enums

Traits

  • Coords
    A trait to extract the coordinates of a node.
  • EdgeType
    A graph’s edge type determines whether it has directed edges or not.
  • IndexType
    Trait for the unsigned integer type used for node and edge indices.

Functions