Struct Graph

Source

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

Expand description

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

Implementations§

Source §

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

Source

pub fn new() -> Self

Creates new empty graph.

Source

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

Source

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.

Source

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

Tests if graph contains v.

Source

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

Source

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.

Source

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;

Source

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;

Source

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.

Source

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.

Source

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

Iterator of all current vertices.

Source

pub fn len(&self) -> usize

Current count of vertices.

Source

pub fn is_empty(&self) -> bool

True, if graph does not contain vertices.

Source

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));