use std::collections::{HashSet};
use std::error::Error;
use std::fmt::Debug;
use std::hash::Hash;
use ordered_hashmap::OrderedHashMap;
pub const DEFAULT_EDGE_NAME: &str = "\x00";
pub const GRAPH_NODE: &str = "\x00";
pub const EDGE_KEY_DELIM: &str = "\x01";
#[derive(Debug, Clone)]
pub struct Edge {
pub v: String,
pub w: String,
pub name: Option<String>
}
#[derive(Default)]
pub struct GraphOption {
pub directed: Option<bool>,
pub multigraph: Option<bool>,
pub compound: Option<bool>
}
pub enum DefaultNodeLabel<N> {
Val(Option<N>),
Func(Box<dyn Fn(String) -> Option<N>>)
}
pub enum DefaultEdgeLabel<E> {
Val(Option<E>),
Func(Box<dyn Fn(String) -> Option<E>>)
}
pub enum EdgeOrString<E> {
Edge(E),
String(String)
}
pub enum EdgeLabelOrString<E> {
EdgeLabel(E),
String(String)
}
pub struct Graph<GL, N, E> where GL: Default {
_is_directed: bool,
_is_multigraph: bool,
_is_compound: bool,
_label: GL,
_default_node_label_fn: DefaultNodeLabel<N>,
_default_edge_label_fn: DefaultEdgeLabel<E>,
_nodes: OrderedHashMap<String, N>,
_in: OrderedHashMap<String, OrderedHashMap<String, Edge>>,
_preds: OrderedHashMap<String, OrderedHashMap<String, usize>>,
_out: OrderedHashMap<String, OrderedHashMap<String, Edge>>,
_sucs: OrderedHashMap<String, OrderedHashMap<String, usize>>,
_edge_objs: OrderedHashMap<String, Edge>,
_edge_labels: OrderedHashMap<String, E>,
_node_count: usize,
_edge_count: usize,
_parent: OrderedHashMap<String, String>,
_children: OrderedHashMap<String, OrderedHashMap<String, bool>>,
}
impl<GL: Default, N, E> Default for Graph<GL, N, E> {
fn default() -> Self {
Self {
_is_directed: true,
_is_multigraph: false,
_is_compound: false,
_label: GL::default(),
_default_node_label_fn: DefaultNodeLabel::Val(None),
_default_edge_label_fn: DefaultEdgeLabel::Val(None),
_nodes: OrderedHashMap::new(),
_in: OrderedHashMap::new(),
_preds: OrderedHashMap::new(),
_out: OrderedHashMap::new(),
_sucs: OrderedHashMap::new(),
_edge_objs: OrderedHashMap::new(),
_edge_labels: OrderedHashMap::new(),
_node_count: 0,
_edge_count: 0,
_parent: OrderedHashMap::new(),
_children: OrderedHashMap::new(),
}
}
}
impl<GL: Default, N: Default + Clone + Debug, E: Default + Clone + Debug> Graph<GL, N, E> {
pub fn new(opts: Option<GraphOption>) -> Self {
let mut graph = Self::default();
if let Some(_opts) = opts {
if _opts.directed.is_some() {
graph._is_directed = _opts.directed.unwrap();
} else {
graph._is_directed = true;
}
if _opts.multigraph.is_some() {
graph._is_multigraph = _opts.multigraph.unwrap();
} else {
graph._is_multigraph = false;
}
if _opts.multigraph.is_some() {
graph._is_multigraph = _opts.multigraph.unwrap();
} else {
graph._is_multigraph = false;
}
if _opts.compound.is_some() {
graph._is_compound = _opts.compound.unwrap();
} else {
graph._is_compound = false;
}
}
if graph._is_compound {
graph._parent = OrderedHashMap::new();
graph._children = OrderedHashMap::new();
graph._children.insert(GRAPH_NODE.clone().to_string(), OrderedHashMap::new());
}
graph
}
pub fn is_directed(&self) -> bool {
return self._is_directed;
}
pub fn is_multigraph(&self) -> bool {
return self._is_multigraph;
}
pub fn is_compound(&self) -> bool {
return self._is_compound;
}
pub fn set_graph(&mut self, label: GL) -> &mut Self {
self._label = label;
return self;
}
pub fn graph(&self) -> &GL {
return &self._label;
}
pub fn graph_mut(&mut self) -> &mut GL {
return &mut self._label;
}
pub fn set_default_node_label(&mut self, new_default: DefaultNodeLabel<N>) -> &mut Self {
self._default_node_label_fn = new_default;
return self;
}
pub fn default_node_label(&self, node_id: String) -> N {
let mut _node_label: Option<N> = None;
match &self._default_node_label_fn {
DefaultNodeLabel::Func(node_label_fn) => {
_node_label = node_label_fn(node_id.clone());
},
DefaultNodeLabel::Val(node_label_) => {
if node_label_.is_some() {
_node_label = Some(node_label_.clone().unwrap());
} else {
_node_label = Some(N::default());
}
}
}
return _node_label.unwrap();
}
pub fn node_count(&self) -> usize {
return self._node_count;
}
pub fn nodes(&self) -> Vec<String> {
return self._nodes.keys().cloned().collect();
}
pub fn sources(&self) -> Vec<String> {
return self.nodes().iter().filter(|n| {
if let Some(in_edges) = self._in.get(&n.to_owned().clone()) {
return in_edges.len() == 0;
}
return true;
}).map(|node_id| node_id.clone()).collect();
}
pub fn sinks(&self) -> Vec<String> {
return self.nodes().iter().filter(|n| {
if let Some(out_edges) = self._out.get(&n.to_owned().clone()) {
return out_edges.len() == 0;
}
return true;
}).map(|node_id| node_id.clone()).collect();
}
pub fn set_nodes(&mut self, node_ids: Vec<String>, value: Option<N>) -> &mut Self {
node_ids.iter().for_each(|node_id| {
self.set_node(node_id.to_owned(), value.clone());
});
return self;
}
pub fn set_node(&mut self, v: String, value: Option<N>) -> &mut Self {
if self._nodes.get(&v).is_some() {
if value.is_some() {
self._nodes.insert(v, value.unwrap());
}
return self;
}
if value.is_some() {
self._nodes.insert(v.clone(), value.unwrap());
} else {
self._nodes.insert(v.clone(), self.default_node_label(v.clone()));
}
if self._is_compound {
let _graph_node = GRAPH_NODE.clone().to_string();
self._parent.insert(v.clone(), _graph_node.clone());
self._children.insert(v.clone(), OrderedHashMap::new());
self._children
.entry(_graph_node.clone()).or_insert(OrderedHashMap::new())
.entry(v.clone()).or_insert(true);
}
self._in.insert(v.clone(), OrderedHashMap::new());
self._preds.insert(v.clone(), OrderedHashMap::new());
self._out.insert(v.clone(), OrderedHashMap::new());
self._sucs.insert(v.clone(), OrderedHashMap::new());
self._node_count += 1;
return self;
}
pub fn node(&self, v: &String) -> Option<&N> {
return self._nodes.get(v);
}
pub fn node_mut(&mut self, v: &String) -> Option<&mut N> {
return self._nodes.get_mut(v);
}
pub fn has_node(&self, v: &String) -> bool {
return self._nodes.contains_key(v);
}
pub fn remove_node(&mut self, v: &String) -> &mut Self {
if self._nodes.contains_key(v) {
self._nodes.remove(v);
if self._is_compound {
self._remove_from_parents_child_list(v);
if self._parent.contains_key(v) {
self._parent.remove(v);
}
self.children(v).iter().for_each(|child_id| {
let _ = self.set_parent(child_id, None);
});
self._children.remove(v);
}
if let Some(in_edges) = self._in.get(v) {
let edge_ids: Vec<String> = in_edges.keys().cloned().collect();
edge_ids.iter().for_each(|edge_id| {
if let Some(edge) = self._edge_objs.get(edge_id) {
self.remove_edge_with_obj(&edge.to_owned());
}
});
self._in.remove(v);
}
self._preds.remove(v);
if let Some(out_edges) = self._out.get(v) {
let edge_ids: Vec<String> = out_edges.keys().cloned().collect();
edge_ids.iter().for_each(|edge_id| {
if let Some(edge) = self._edge_objs.get(edge_id) {
self.remove_edge_with_obj(&edge.to_owned());
}
});
self._out.remove(v);
}
self._sucs.remove(v);
self._node_count -= 1;
}
return self;
}
pub fn set_parent(&mut self, v: &String, parent: Option<String>) -> Result<&mut Self, Box<dyn Error>> {
if !self._is_compound {
return Err("Cannot set parent in a non-compound graph".into());
}
let mut _parent: String = "".to_string();
if parent.is_none() {
_parent = GRAPH_NODE.to_string();
} else {
_parent = parent.unwrap().clone();
let mut ancestor = _parent.clone();
while let Some(new_ancestor) = self.parent(&ancestor) {
if &new_ancestor == &v {
return Err(format!("Setting {} as parent of {} would create a cycle", _parent.clone(), v).into());
}
ancestor = new_ancestor.clone();
}
self.set_node(_parent.clone(), None);
}
self.set_node(v.clone(), None);
self._remove_from_parents_child_list(v);
self._parent.insert(v.clone(), _parent.clone());
self._children.entry(_parent.clone()).or_insert_with(OrderedHashMap::new).insert(v.clone(), true);
Ok(self)
}
pub fn _remove_from_parents_child_list(&mut self, v: &String) {
if let Some(parent) = self._parent.get(v) {
if let Some(children) = self._children.get_mut(parent) {
children.remove(v);
}
}
}
pub fn parent(&self, v: &String) -> Option<&String> {
if self._is_compound {
if let Some(parent) = self._parent.get(v) {
if parent != GRAPH_NODE {
return Some(parent);
}
}
}
None
}
pub fn children(&self, v: &String) -> Vec<String> {
if self._is_compound {
if let Some(children) = self._children.get(v) {
return children.keys().cloned().collect();
}
} else if v == GRAPH_NODE {
return self._nodes.keys().cloned().collect();
} else if self.has_node(&v) {
return vec![];
}
vec![]
}
pub fn predecessors(&self, v: &String) -> Option<Vec<String>> {
if let Some(preds) = self._preds.get(v) {
return Some(preds.keys().cloned().collect());
}
None
}
pub fn successors(&self, v: &String) -> Option<Vec<String>> {
if let Some(sucs) = self._sucs.get(v) {
return Some(sucs.keys().cloned().collect());
}
None
}
pub fn neighbors(&self, v: &String) -> Option<Vec<String>> {
if let Some(preds) = self.predecessors(v) {
let mut union: HashSet<String> = HashSet::new();
preds.into_iter().for_each(|pred| {
union.insert(pred);
});
if let Some(sucs) = self.successors(v) {
sucs.into_iter().for_each(|successor| {
union.insert(successor);
});
}
return Some(union.into_iter().collect());
}
None
}
pub fn is_leaf(&self, v: &String) -> bool {
let mut _neighbors: Option<Vec<String>> = None;
if self.is_directed() {
_neighbors = self.successors(v);
} else {
_neighbors = self.neighbors(v);
}
if _neighbors.is_none() || _neighbors.unwrap().len() == 0 {
return true;
}
false
}
pub fn filter_nodes<F>(&self, filter: F) -> Self
where
F: Fn(&String) -> bool,
{
let mut copy: Graph<GL, N, E> = Graph::new(Some(GraphOption {
directed: Some(self._is_directed.clone()),
multigraph: Some(self._is_multigraph.clone()),
compound: Some(self._is_compound.clone()),
}));
for (v, value) in self._nodes.iter() {
if filter(v) {
copy.set_node(v.clone(), Some(value.clone()));
}
}
for e_v in self._edge_objs.values() {
if copy._nodes.contains_key(&e_v.v) && copy._nodes.contains_key(&e_v.w) {
if let Some(edge_label) = self.edge_with_obj(e_v) {
let _ = copy.set_edge_with_obj(e_v, Some(edge_label.to_owned()));
}
}
}
let mut parents: OrderedHashMap<String, String> = OrderedHashMap::new();
if self._is_compound {
let node_ids: Vec<String> = copy._nodes.keys().cloned().into_iter().collect();
for v in node_ids {
let parent = find_parent(&v, &mut parents, &mut copy, self);
let _ = copy.set_parent(&v, parent);
}
}
copy
}
pub fn set_default_edge_label(&mut self, new_default: DefaultEdgeLabel<E>) -> &mut Self {
self._default_edge_label_fn = new_default;
return self;
}
pub fn default_edge_label(&self, edge_id: String) -> E {
let mut _edge_label: Option<E> = None;
match &self._default_edge_label_fn {
DefaultEdgeLabel::Func(edge_label_fn) => {
_edge_label = edge_label_fn(edge_id.clone());
},
DefaultEdgeLabel::Val(edge_label_) => {
if edge_label_.is_some() {
_edge_label = Some(edge_label_.clone().unwrap());
} else {
_edge_label = Some(E::default());
}
}
}
return _edge_label.unwrap();
}
pub fn edge_count(&self) -> usize {
return self._edge_count.clone();
}
pub fn edges(&self) -> Vec<Edge> {
return self._edge_objs.values().cloned().collect();
}
pub fn set_path(&mut self, vs: &Vec<String>, value: Option<E>) {
vs.iter().reduce(|v1, v2| {
let _ = self.set_edge(v1, v2, value.clone(), None);
v2
});
}
pub fn set_edge(&mut self, v: &String, w: &String, edge_label: Option<E>, name: Option<String>) -> Result<&mut Self, Box<dyn Error>> {
let e = edge_args_to_id(&self._is_directed, v, w, &name);
if self._edge_labels.contains_key(&e) {
if edge_label.is_some() {
self._edge_labels.insert(e.clone(), edge_label.unwrap());
}
return Ok(self);
}
if name.is_some() && !self._is_multigraph {
return Err("Cannot set a named edge when isMultigraph = false".into());
}
self.set_node(v.clone(), None);
self.set_node(w.clone(), None);
if edge_label.is_some() {
self._edge_labels.insert(e.clone(), edge_label.clone().unwrap());
} else {
self._edge_labels.insert(e.clone(), self.default_edge_label(e.clone()));
}
let edge_obj = edge_args_to_obj(&self.is_directed(), v, w, &name);
self._edge_objs.insert(e.clone(), edge_obj.clone());
if let Some(preds) = self._preds.get_mut(w) {
increment_or_init_entry(preds, v);
}
if let Some(sucs) = self._sucs.get_mut(v) {
increment_or_init_entry(sucs, w);
}
let in_edges = self._in.entry(w.clone()).or_insert_with(OrderedHashMap::new);
in_edges.insert(e.clone(), edge_obj.clone());
let out_edges = self._out.entry(v.clone()).or_insert_with(OrderedHashMap::new);
out_edges.insert(e.clone(), edge_obj.clone());
self._edge_count += 1;
return Ok(self);
}
pub fn set_edge_with_obj(&mut self, e: &Edge, edge_label: Option<E>) -> Result<&mut Self, Box<dyn Error>> {
self.set_edge(&e.v, &e.w, edge_label, None)
}
pub fn edge(&self, v: &String, w: &String, name: Option<String>) -> Option<&E> {
let e = edge_args_to_id(&self._is_directed, v, w, &name);
return self._edge_labels.get(&e);
}
pub fn edge_with_obj(&self, edge: &Edge) -> Option<&E> {
let e = edge_obj_to_id(&self._is_directed, edge);
return self._edge_labels.get(&e);
}
pub fn edge_mut(&mut self, v: &String, w: &String, name: Option<String>) -> Option<&mut E> {
let e = edge_args_to_id(&self._is_directed, v, w, &name);
return self._edge_labels.get_mut(&e);
}
pub fn edge_mut_with_obj(&mut self, edge: &Edge) -> Option<&mut E> {
let e = edge_obj_to_id(&self._is_directed, edge);
return self._edge_labels.get_mut(&e);
}
pub fn has_edge(&self, v: &String, w: &String, name: Option<String>) -> bool {
let e = edge_args_to_id(&self._is_directed, v, w, &name);
self._edge_labels.contains_key(&e)
}
pub fn has_edge_with_obj(&self, edge: &Edge) -> bool {
let e = edge_obj_to_id(&self._is_directed, edge);
self._edge_labels.contains_key(&e)
}
pub fn remove_edge(&mut self, v: &String, w: &String, name: Option<String>) -> &mut Self {
let e: String = edge_args_to_id(&self._is_directed, v, w, &name);
if let Some(edge) = self._edge_objs.get_mut(&e) {
let v = edge.v.clone();
let w = edge.w.clone();
self._edge_labels.remove(&e);
self._edge_objs.remove(&e);
if self._preds.contains_key(&w) {
decrement_or_remove_entry(self._preds.get_mut(&w).unwrap(), &v);
}
if self._sucs.contains_key(&v) {
decrement_or_remove_entry(self._sucs.get_mut(&v).unwrap(), &w);
}
if self._in.contains_key(&w) {
self._in.get_mut(&w).unwrap().remove(&e);
}
if self._out.contains_key(&v) {
self._out.get_mut(&v).unwrap().remove(&e);
}
self._edge_count -= 1;
}
return self;
}
pub fn remove_edge_with_obj(&mut self, e: &Edge) -> &mut Self {
self.remove_edge(&e.v, &e.w, None);
return self;
}
pub fn in_edges(&self, v: &String, u: Option<String>) -> Option<Vec<Edge>> {
if let Some(in_edges) = self._in.get(v) {
let mut _in_edges: Vec<Edge> = in_edges.values().cloned().collect();
if u.is_none() {
return Some(_in_edges.clone());
}
let _u = u.unwrap();
return Some(_in_edges.into_iter().filter(|edge| edge.v == _u).collect());
}
None
}
pub fn out_edges(&self, v: &String, w: Option<String>) -> Option<Vec<Edge>> {
if let Some(out_edges) = self._out.get(v) {
let mut _out_edges: Vec<Edge> = out_edges.values().cloned().collect();
if w.is_none() {
return Some(_out_edges.clone());
}
let _w = w.unwrap();
return Some(_out_edges.into_iter().filter(|edge| edge.w == _w).collect())
}
None
}
pub fn node_edges(&self, v: &String, w: Option<String>) -> Option<Vec<Edge>> {
let _in_edges = self.in_edges(v, w.clone());
if let Some(mut in_edges) = _in_edges {
let _out_edges = self.out_edges(v, w.clone());
if let Some(out_edges) = _out_edges {
in_edges.append(out_edges.clone().as_mut());
}
return Some(in_edges);
}
None
}
}
fn increment_or_init_entry<K: Hash + Eq + Clone>(map: &mut OrderedHashMap<K, usize>, k: &K) {
if let Some(e) = map.get_mut(&k) {
*e += 1;
} else {
map.insert(k.clone(), 1);
}
}
fn decrement_or_remove_entry<K: Hash + Eq + Clone>(map: &mut OrderedHashMap<K, usize>, k: &K) {
if let Some(value) = map.get_mut(k) {
*value -= 1;
if *value <= 0 {
map.remove(k);
}
}
}
fn edge_args_to_id(is_directed: &bool, v_: &String, w_: &String, name: &Option<String>) -> String {
let mut v: &str = &*v_;
let mut w: &str = &*w_;
if !is_directed.to_owned() && v > w {
let tmp = v;
v = w;
w = tmp;
}
if name.is_some() {
return v.to_owned() + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + &*name.clone().unwrap();
}
return v.to_owned() + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + DEFAULT_EDGE_NAME;
}
fn edge_args_to_obj(is_directed: &bool, v_: &String, w_: &String, name: &Option<String>) -> Edge {
let mut v: &str = &*v_;
let mut w: &str = &*w_;
if !is_directed.to_owned() && v > w {
let tmp = v;
v = w;
w = tmp;
}
return Edge {
v: v.to_string(),
w: w.to_string(),
name: name.clone()
}
}
fn edge_obj_to_id(is_directed: &bool, edge: &Edge) -> String {
return edge_args_to_id(is_directed, &edge.v, &edge.w, &edge.name);
}
fn find_parent<GL: Default, N: Default + Clone + Debug, E: Default + Clone + Debug>(
v: &String,
parents: &mut OrderedHashMap<String, String>,
copy: &mut Graph<GL, N, E>,
graph: &Graph<GL, N, E>,
) -> Option<String> {
let parent = graph.parent(v);
if parent.is_none() || copy._nodes.contains_key(&parent.unwrap().clone()) {
if !parent.is_none() {
parents.insert(v.clone(), parent.unwrap().clone());
return parent.cloned();
}
None
} else if let Some(parent_value) = parents.get(&parent.unwrap().clone()) {
Some(parent_value.clone())
} else {
if parent.is_some() {
find_parent(parent.as_ref().unwrap(), parents, copy, graph)
} else {
None
}
}
}