Struct gardiz::graph::Graph

pub struct Graph<T>where
    T: Ord,{ /* private fields */ }

A simple graph of points in a plane. Being simple means two points can only be connected once with each other or not connected at all (with each other), no pair of points can be connected with each other more than once. Also, graphs might not be necessarily planar, although they can (this means two edges can overlap). Points can only be connected in “straight” 2D directions.

Implementations

impl<T> Graph<T>where T: Ord,

pub fn new() -> Self

Creates a new empty graph.

pub fn from_vertices<I>(vertices: I) -> Selfwhere I: IntoIterator<Item = Vec2<T>>, T: Clone,

Creates the graph from a list of vertices (and no vertices_edges!).

pub fn from_verts_and_edges<'vertex, U, I, J>( vertices: I, vertices_edges: J ) -> Selfwhere I: IntoIterator<Item = Vec2<T>>, T: Borrow<U> + Clone, U: 'vertex + Ord, J: IntoIterator<Item = (Vec2<&'vertex U>, Vec2<&'vertex U>)>,

Creates the graph from a list of vertices (and list of vertices-pair connected in vertices_edges).

pub fn extend_vertices<I>(&mut self, vertices: I)where I: IntoIterator<Item = Vec2<T>>, T: Clone,

Extend the set of vertices from a given list of vertices, creating vertices when not existing already. The created vertices have no edges.

pub fn extend_edges<'vertex, U, I>(&mut self, vertices_edges: I)where U: 'vertex + Ord, T: Borrow<U>, I: IntoIterator<Item = (Vec2<&'vertex U>, Vec2<&'vertex U>)>,

Extends the graph edge list from a list of vertices-pair connected in vertices_edges.

pub fn vertices_edges(&self) -> &Map<T, VertexEdges>

Returns the underlying map of vertices to edge flags.

pub fn vertex_edges<U>(&self, vertex: Vec2<&U>) -> Option<VertexEdges>where U: Ord, T: Borrow<U>,

Gets the edge flags of the given vertex, the vertex is in the graph in the first place.

pub fn are_connected<U>(&self, vertex_a: Vec2<&U>, vertex_b: Vec2<&U>) -> boolwhere U: Ord, T: Borrow<U>,

Tests if the given two vertices are connected.

pub fn connected_at<U>( &self, vertex: Vec2<&U>, direction: Direction ) -> Option<Vec2<&T>>where T: Borrow<U>, U: Ord,

Gets the vertex connected with the given vertex in the given direction, if there is an edge in this direction.

pub fn create_vertex(&mut self, vertex: Vec2<T>) -> boolwhere T: Clone,

Creates a new vertex in the graph (without creating vertices_edges!). Returns if the vertex was really created (i.e. vertex not already there).

pub fn connect<U>(&mut self, vertex_a: Vec2<&U>, vertex_b: Vec2<&U>) -> boolwhere U: Ord, T: Borrow<U>,

Connects the given two vertices and returns if they were really connected (i.e. they were previously disconnected).

pub fn disconnect<U>(&mut self, vertex_a: Vec2<&U>, vertex_b: Vec2<&U>) -> boolwhere U: Ord, T: Borrow<U>,

Disconnects the given two vertices and returns if they were really disconnected (i.e. they were previously connected).

pub fn connections(&self) -> Connections<'_, T>

Iterator over the connections of this graph: pairs of vertices in an edge. Note that two vertices cannot be connected twice.

pub fn remove_vertex<U>(&mut self, vertex: Vec2<&U>) -> boolwhere U: Ord, T: Borrow<U> + Clone,

Removes a vertex but attempts to connect vertices_edges between its neighbours, if the target vertex had vertices_edges in both directions. Returns if the vertex was really removed (i.e. it was in the graph).

pub fn remove_with_edges<U>(&mut self, vertex: Vec2<&U>) -> boolwhere U: Ord, T: Borrow<U> + Clone + Debug,

Removes a vertex and all its vertices_edges. Returns if the vertex was really removed (i.e. it was in the graph).

pub fn components(&self) -> Components<'_, T>

Creates iterator over connected components of the graph. E.g. each “island” in the graph makes a new subgraph yielded by the iterator.

pub fn make_path<'points, F>( &mut self, start: &'points Vec2<T>, goal: &'points Vec2<T>, penalty: &'points T, valid_points: F ) -> Option<Vec<DirecVector<T>>>where T: Clone + Hash + Zero + One + AddAssign + CheckedAdd + CheckedSub + AddAssign<&'points T>, F: FnMut(&Vec2<T>) -> bool,

Makes a path from the given starting point till the “goal” point and creates intermediate points in the graph. The algorithm chooses the smallest path between the two points. It is also possible to specify a “penalty” added to the cost of paths when they turn. Recomended values for “penalty” are 0, 1 or 2. For minimizing turns, 2 is strongly recommended. The only points actually used are the ones validated by the given function valid_points.

Examples

use gardiz::{
    coord::Vec2,
    graph::Graph,
    direc::{Direction, DirecVector},
};
use std::collections::HashSet;

// `i64` is the type of the coordinate of the points.
let mut graph = Graph::<i64>::new();
// Initial and final points.
let start = Vec2 { x: -3, y: -3 };
let goal = Vec2 { x: 2, y: 4 };
graph.create_vertex(start);
graph.create_vertex(goal);

// Penalty whenever the path takes a turn.
let penalty = 2;

// Valid points to be used in the path.
let mut valid_points = HashSet::new();
for x in -3 .. 1 {
    for y in -3 .. 0 {
        valid_points.insert(Vec2 { x, y });
    }
}
for x in 0 .. 3 {
    for y in 0 .. 2 {
        valid_points.insert(Vec2 { x, y });
    }
}
for x in -1 .. 2 {
    for y in 2 .. 3 {
        valid_points.insert(Vec2 { x, y });
    }
}
for x in -2 .. 0 {
    for y in 3 .. 5 {
        valid_points.insert(Vec2 { x, y });
    }
}
for x in -3 .. 7 {
    for y in 5 .. 7 {
        valid_points.insert(Vec2 { x, y });
    }
}
for x in 1 .. 9 {
    for y in 4 .. 9 {
        valid_points.insert(Vec2 { x, y });
    }
}

// Cloning the graph before making the path (which will modify it).
let mut expected = graph.clone();

// Runs A*
let directions = graph.make_path(
    &start,
    &goal,
    &penalty,
    |point| valid_points.contains(&point)
);

// Checks whether the computed directions are correct.
assert_eq!(
    directions,
    Some(vec![
        // x = -3, y = -3
        DirecVector { direction: Direction::Right, magnitude: 3 },
        // x = 0, y = -3
        DirecVector { direction: Direction::Down, magnitude: 5 },
        // x = 0, y = 2
        DirecVector { direction: Direction::Left, magnitude: 1 },
        // x = -1, y = 2
        DirecVector { direction: Direction::Down, magnitude: 3 },
        // x = -1, y = 5
        DirecVector { direction: Direction::Right, magnitude: 3 },
        // x = 2, y = 5
        DirecVector { direction: Direction::Up, magnitude: 1 },
        // x = 2, y = 4
    ])
);

// Insert the vertices created when making the path.
expected.create_vertex(Vec2 { x: 0, y: -3 });
expected.create_vertex(Vec2 { x: 0, y: 2 });
expected.create_vertex(Vec2 { x: -1, y: 2 });
expected.create_vertex(Vec2 { x: -1, y: 5 });
expected.create_vertex(Vec2 { x: 2, y: 5 });

// Connect the vertices in the path.
expected
    .connect(Vec2 { x: -3, y: -3 }.as_ref(), Vec2 { x: 0, y: -3 }.as_ref());
expected
    .connect(Vec2 { x: 0, y: 2 }.as_ref(), Vec2 { x: 0, y: -3 }.as_ref());
expected
    .connect(Vec2 { x: 0, y: 2 }.as_ref(), Vec2 { x: -1, y: 2 }.as_ref());
expected
    .connect(Vec2 { x: -1, y: 5 }.as_ref(), Vec2 { x: -1, y: 2 }.as_ref());
expected
    .connect(Vec2 { x: -1, y: 5 }.as_ref(), Vec2 { x: 2, y: 5 }.as_ref());
expected
    .connect(Vec2 { x: 2, y: 4 }.as_ref(), Vec2 { x: 2, y: 5 }.as_ref());

// Test if the graph produced by `make_path` is the expected one we built.
assert_eq!(graph, expected);

Trait Implementations

impl<T> Clone for Graph<T>where T: Ord + Clone,

fn clone(&self) -> Graph<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Debug for Graph<T>where T: Ord + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for Graph<T>where T: Ord,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, T> Deserialize<'de> for Graph<T>where T: Ord + Deserialize<'de> + Clone,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T> PartialEq<Graph<T>> for Graph<T>where T: Ord + PartialEq,

fn eq(&self, other: &Graph<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T> Serialize for Graph<T>where T: Ord + Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<T> Eq for Graph<T>where T: Ord + Eq,

impl<T> StructuralEq for Graph<T>where T: Ord,

impl<T> StructuralPartialEq for Graph<T>where T: Ord,