Struct easy_graph::Graph

pub struct Graph<T: Hash + Eq> { /* fields omitted */ }

Data structure that represent generic vertices and undirected connections between them - edges.

Methods

impl<T: Hash + Eq + Clone> Graph<T>

pub fn new() -> Self

Creates new empty graph.

pub fn with_capacity(
    vertices_capacity: usize,
    edge_per_vertex_capacity: usize
) -> Self

Creates empty graph with preallocated memory for vertices and edges.

Arguments:

vertices_capacity - capacity for collection of vertices. edge_per_vertex_capacity - capacity for connections collections for each vertex. Default value const DEFAULT_CONNECTIONS_PER_VERTEX: usize = 4

pub fn from_data(
    vertices: impl Iterator<Item = T>,
    edges: impl Iterator<Item = (T, T)>
) -> Self

Creates graph filled by vertices with edges.

Arguments:

vertices - iterator of vertices. edges - iterator of pairs of vertices indices, which must be connected.

pub fn contains(&self, v: &T) -> bool

Tests if graph contains v.

pub fn add_vertex(&mut self, v: T) -> bool

Adds vertex to graph.

Arguments:

vertex - vertex, that must be added.

Returns:

true if vertex is new and was really added

pub fn remove_vertex(&mut self, v: &T) -> Option<HashSet<T>>

Removes vertex from graph.

Arguments:

vertex - vertex, that must be removed.

Returns:

If vertex exist, than set of its connections. Else None.

pub fn add_edge(&mut self, v1: &T, v2: &T) -> bool

Adds edge to graph.

Arguments:

v1 - vertex, that will be connected with v2. v2 - vertex, that will be connected with v1.

Returns:

true if edge was added actualy; false if edge was presented already;

pub fn remove_edge(&mut self, v1: &T, v2: &T) -> bool

Removes edge from graph. If edge is not present, that function does nothing.

Arguments:

v1 - vertex, that will be disconnected with v2. v2 - vertex, that will be disconnected with v1.

Returns:

true if edge was removed actualy; false if edge wasn't presented already;

pub fn is_connected(&self, v1: &T, v2: &T) -> bool

Checks if edge, that connects specified vertices, is present. Connections are undirectional, thats why always is_connected(v1, v2) == is_connected(v2, v1)

Arguments:

v1 - first vertex to check. v2 - second vertex to check.

pub fn connects_of(&self, v: &T) -> Option<&HashSet<T>>

Connects of vertices with specified index.

Arguments:

v - vertex of interest;

Returns:

Set of vertices, that connected to v, or None if v is not in graph.

pub fn vertices(&self) -> impl Iterator<Item = &T>

Iterator of all current vertices.

pub fn len(&self) -> usize

Current count of vertices.

pub fn is_empty(&self) -> bool

True, if graph does not contain vertices.

pub fn remove_weak_connected(&mut self, weak_level: usize) -> HashSet<T>

Removes all points, that have less connections than weak_level. In other words, only vertices with more or equal connections than weak_level remains. Complexity: O(n)

Returns:

Set of removed vertices

Example:

use easy_graph::Graph;
let verts = vec![0,1,2,3];
let conns = vec![(0, 1), (1, 2), (2, 0), (2, 3)];
let mut graph = Graph::from_data(verts.into_iter(), conns.into_iter());
graph.remove_weak_connected(2);
assert_eq!(graph.len(), 3);
assert!(graph.contains(&0));
assert!(graph.contains(&1));
assert!(graph.contains(&2));
assert!(!graph.contains(&3));
assert!(!graph.connects_of(&2).unwrap().contains(&3));

pub fn verts_with_path_to(&self, vertex: &T) -> HashSet<T>

Returns set of vertices, for which exists path to vertex.

pub fn take_connected_graph(&mut self, vertex: &T) -> Self

Takes connected graph that contains vertex.

pub fn into_connected_graphs(self) -> Vec<Self>

Split self into connected graphs.

Trait Implementations

impl<T: Clone + Hash + Eq> Clone for Graph<T>

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 + Hash + Eq> Debug for Graph<T>

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

Formats the value using the given formatter.

impl<T: Default + Hash + Eq> Default for Graph<T>

fn default() -> Graph<T>

Returns the "default value" for a type.

impl<T: Eq + Hash> Eq for Graph<T>

impl<T: Eq + Hash> PartialEq<Graph<T>> for Graph<T>

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

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.