Struct gdsl::digraph::Graph

pub struct Graph<K, N, E>where
    K: Clone + Hash + Display + PartialEq + Eq,
    N: Clone,
    E: Clone,{ /* private fields */ }

A directed graph containing nodes and edges. The graph is represented as a map of nodes, where each node is identified by a unique key. Each node contains a value and a map of edges. An edge may hold a value as well. Generic types K, N, and E represent the key, node value, and edge value, respectively.

Implementations

impl<K, N, E> Graph<K, N, E>where K: Clone + Hash + Display + PartialEq + Eq, N: Clone, E: Clone,

pub fn new() -> Self

Create a new Graph

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

pub fn with_capacity(capacity: usize) -> Self

Create a new Graph with a given capacity

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::with_capacity(42);

pub fn contains(&self, key: &K) -> bool

Check if a node with the given key exists in the Graph

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));

assert!(g.contains(&"A"));

pub fn len(&self) -> usize

Get the length of the Graph (amount of nodes)

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));
g.insert(Node::new("B", 0));

let len = g.len();

assert!(len == 2);

pub fn get(&self, key: &K) -> Option<Node<K, N, E>>

Get a node by key

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));
g.insert(Node::new("B", 0));
g.insert(Node::new("C", 0));

let node = g.get(&"A").unwrap();

assert!(node.key() == &"A");

pub fn is_empty(&self) -> bool

Check if Graph is empty

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

assert!(g.is_empty());

pub fn insert(&mut self, node: Node<K, N, E>) -> bool

Insert a node into the Graph

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));

assert!(g.contains(&"A"));
assert!(g.insert(Node::new("A", 0)) == false);

pub fn remove(&mut self, node: &K) -> Option<Node<K, N, E>>

Remove a node from the Graph

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));
g.insert(Node::new("B", 0));

assert!(g.contains(&"A"));

g.remove(&"A");

assert!(g.contains(&"A") == false);

pub fn to_vec(&self) -> Vec<Node<K, N, E>>

Collect nodes into a vector

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));
g.insert(Node::new("B", 0));
g.insert(Node::new("C", 0));

let nodes = g.to_vec();

assert!(nodes.len() == 3);

pub fn roots(&self) -> Vec<Node<K, N, E>>

Collect roots into a vector

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));
g.insert(Node::new("B", 0));
g.insert(Node::new("C", 0));

g["A"].connect(&g["B"], 0x1);
g["A"].connect(&g["C"], 0x1);
g["B"].connect(&g["C"], 0x1);

let roots = g.roots();

assert!(roots.len() == 1);

pub fn leaves(&self) -> Vec<Node<K, N, E>>

Collect leaves into a vector

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));
g.insert(Node::new("B", 0));
g.insert(Node::new("C", 0));

g["A"].connect(&g["B"], 0x1);
g["A"].connect(&g["C"], 0x1);

let leaves = g.leaves();

assert!(leaves.len() == 2);

pub fn orphans(&self) -> Vec<Node<K, N, E>>

Collect orpahn nodes into a vector

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));
g.insert(Node::new("B", 0));
g.insert(Node::new("C", 0));
g.insert(Node::new("D", 0));

g["A"].connect(&g["B"], 0x1);

let orphans = g.orphans();

assert!(orphans.len() == 2);

pub fn iter(&self) -> Iter<'_, K, Node<K, N, E>>

Iterate over nodes in the graph in random order

Examples

use gdsl::digraph::*;

let mut g = Graph::<&str, u64, u64>::new();

g.insert(Node::new("A", 0));
g.insert(Node::new("B", 0));
g.insert(Node::new("C", 0));

for (key, _) in g.iter() {
   println!("{}", key);
}

pub fn scc(&self) -> Vec<Vec<Node<K, N, E>>>

Find the strongly connected components of the graph. Can be used to find cycles in the graph and for topological sorting.

Examples

use gdsl::digraph::*;

let mut g: Graph<usize, (), ()> = Graph::new();

g.insert(Node::new(0, ()));
g.insert(Node::new(1, ()));
g.insert(Node::new(2, ()));
g.insert(Node::new(3, ()));
g.insert(Node::new(4, ()));
g.insert(Node::new(5, ()));
g.insert(Node::new(6, ()));
g.insert(Node::new(7, ()));
g.insert(Node::new(8, ()));
g.insert(Node::new(9, ()));

g[0].connect(&g[1], ());    // ---- C1
g[1].connect(&g[2], ());    //
g[2].connect(&g[0], ());    //
g[3].connect(&g[4], ());    // ---- C2
g[4].connect(&g[5], ());    //
g[5].connect(&g[3], ());    //
g[6].connect(&g[7], ());    // ---- C3
g[7].connect(&g[8], ());    //
g[8].connect(&g[6], ());    //
g[9].connect(&g[9], ());    // ---- C4

let mut scc = g.scc();

// Since the graph container is a hash map, the order of the SCCs is
// not deterministic. We sort the SCCs by their size to make the test
// deterministic.
scc.sort_by(|a, b| a.len().cmp(&b.len()));

assert!(scc.len() == 4);
assert!(scc[0].len() == 1);
assert!(scc[1].len() == 3);
assert!(scc[2].len() == 3);
assert!(scc[3].len() == 3);

pub fn to_dot(&self) -> String

pub fn to_dot_with_attr( &self, gattr: &dyn Fn(&Self) -> Option<Vec<(String, String)>>, nattr: &dyn Fn(&Node<K, N, E>) -> Option<Vec<(String, String)>>, eattr: &dyn Fn(&Node<K, N, E>, &Node<K, N, E>, &E) -> Option<Vec<(String, String)>> ) -> String

pub fn sizeof(&self) -> usize

Trait Implementations

impl<K, N, E> Default for Graph<K, N, E>where K: Clone + Hash + Display + Eq, N: Clone, E: Clone,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, K, N, E> Deserialize<'de> for Graph<K, N, E>where K: Clone + Hash + PartialEq + Eq + Display + Deserialize<'de>, N: Clone + Deserialize<'de>, E: Clone + Deserialize<'de>,

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

Deserialize this value from the given Serde deserializer.

impl<'a, K, N, E> Index<&'a K> for Graph<K, N, E>where K: Clone + Hash + Display + Eq, N: Clone, E: Clone,

type Output = Node<K, N, E>

The returned type after indexing.

fn index(&self, key: &'a K) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K, N, E> Index<K> for Graph<K, N, E>where K: Clone + Hash + Display + Eq, N: Clone, E: Clone,

type Output = Node<K, N, E>

The returned type after indexing.

fn index(&self, key: K) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K, N, E> Serialize for Graph<K, N, E>where K: Clone + Hash + PartialEq + Eq + Display + Serialize, N: Clone + Serialize, E: Clone + Serialize,

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

Serialize this value into the given Serde serializer.