-
-
Save flavius/e15aedb7fabe7abd44c1 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// needed for Rc::clone().downgrade() | |
#![feature(alloc)] | |
/// A hypergraph is a data structure consisting of nodes and edges which go | |
/// through those edges. | |
/// | |
/// If an edge goes through only two nodes, then we say that the nodes are | |
/// connected. | |
/// | |
/// If an edge goes through multiple nodes, then we say that the nodes are | |
/// hyperconnected. | |
/// | |
/// Hypergraphs can also be nested, i.e. a hypergraph contains other | |
/// hypergraphs. | |
/// | |
/// This property arises from the fact that there is only one data structure, | |
/// a `Graph`, which can be either a Hypergraph, a Hypernode, a Hyperedge, | |
/// or any combination thereof. | |
/// | |
/// Ultimately, you end up with a tree of graphs, ordered in layers. Each | |
/// simple hypergraph occupies a layer within this tree. At the very top, there | |
/// is only one root hypergraph which contains everything, directly or | |
/// through its children. | |
/// | |
/// Under some circumstances, a node may change the layer it belongs to. | |
/// For example: let's say you have a tree of hypergraphs: at the top, the | |
/// Hypergraph `H`, which contains the subhypergraphs `A` and `B`. `A` contains | |
/// the hyperedge `(c, d, e)` and `B` contains the hyperedge `(f, g, h, i)`. | |
/// | |
/// These bottom-most hypernodes are owned by their respective subhypergraphs. | |
/// | |
/// If you then pass a new hyperedge through the hypernodes `c`, `e` and `i`, | |
/// which together have different owners, this new hyperedge will belong | |
/// to the node `H`, since `H` is their lowest common ancestor. | |
/// | |
/// Due to the isomorphism mentioned above (*a `Graph` can be either a | |
/// Hypergraph, a Hypernode, a Hyperedge, or any combination thereof*), you | |
/// can pass new hyperedges through existing subhypergraphs or even other | |
/// hyperedges. | |
/// | |
/// TODO | |
/// ---- | |
/// * example for the case when an existing node changes its owner. | |
/// * implement all basic operations on hypergraphs as nodes themselves. | |
pub mod hypergraph { | |
use std::vec::Vec; | |
use std::option::Option; | |
use std::rc::Weak; | |
use std::rc::Rc; | |
use std::cell::RefCell; | |
use std::cmp::PartialEq; | |
/// A Hypergraph, Hypernode or Hyperedge, all in one. | |
/// | |
/// Every Hypergraph, Hypernode or Hyperedge carries a payload - for now | |
/// it's only a string. | |
/// | |
/// When storing a regular graph in a Hypergraph, you have the root graph | |
/// containing the list of nodes, and a `None` parent. | |
/// The edges contain only two elements each. | |
/// | |
/// The next more complex data to store are hypergraphs as defined in the | |
/// textbooks: There is one root Hypergraph which contains everything: the | |
/// hypernodes, and some hyperedges which go through more than one | |
/// hypernode. | |
/// | |
/// Hypergraphs can be nested, and this is where additional complexity | |
/// arises from - but it also lends more structure to the data. | |
#[derive(Debug)] | |
pub struct Graph { | |
contained_nodes: RefCell<Vec<Rc<Graph>>>, | |
parent: Option<Weak<Graph>>, | |
edges: Vec<Vec<Weak<Graph>>>, | |
pass_through_edges: Vec<Weak<Graph>>, | |
data: String, | |
} | |
impl Graph { | |
/// Returns the payload of this node / edge / graph. | |
pub fn data(&self) -> &String { | |
&self.data | |
} | |
/// The list of nodes and edges that are inside this graph. disregarding | |
/// nestedness. | |
pub fn contained_nodes(&self) -> Vec<Rc<Graph>> { | |
self.contained_nodes.borrow().clone() | |
} | |
/// Is this node the topmost hypergraph? | |
pub fn is_root(&self) -> bool { | |
match self.parent { | |
None => true, | |
Some(_) => false, | |
} | |
} | |
/// Gets a weak reference to the parent, if any. | |
pub fn parent(&self) -> Option<Rc<Graph>> { | |
match &self.parent { | |
&None => None, | |
&Some(ref weakref) => weakref.upgrade(), | |
} | |
} | |
/// Does this hypergraph have edges? | |
pub fn has_edges(&self) -> bool { | |
!self.edges.is_empty() | |
} | |
/// Is this node actually a hypernode, i.e. are there hyperedges | |
/// which go through it? | |
pub fn is_hypernode(&self) -> bool { | |
!self.pass_through_edges.is_empty() | |
} | |
} | |
pub trait SafeGraphMethods { | |
/// Creates a new node as a child of self with the given payload data. | |
fn new_contained_node(&self, data: &str) -> Rc<Graph>; | |
} | |
impl SafeGraphMethods for Rc<Graph> { | |
fn new_contained_node(&self, data: &str) -> Rc<Graph> { | |
let new_node = new(data.to_string(), Some(self.downgrade())); | |
self.contained_nodes.borrow_mut().push(new_node.clone()); | |
new_node | |
} | |
} | |
impl PartialEq for Graph { | |
fn eq(&self, other: &Graph) -> bool { | |
self as *const Graph == other as *const Graph | |
} | |
} | |
/// Creates a new hypergraph. | |
pub fn new(data: String, parent: Option<Weak<Graph>>) -> Rc<Graph> { | |
Rc::new(Graph { | |
contained_nodes: RefCell::new(Vec::new()), | |
parent: parent, | |
edges: Vec::new(), | |
pass_through_edges: Vec::new(), | |
data: data, | |
}) | |
} | |
#[cfg(test)] | |
mod tests { | |
use super::*; | |
#[test] | |
fn create_root_hypergraph() { | |
let g = new("G".to_string(), None); | |
assert_eq!("G", g.data()); | |
assert!(g.contained_nodes().is_empty()); | |
assert!(g.is_root()); | |
assert_eq!(false, g.has_edges()); | |
assert_eq!(false, g.is_hypernode()); | |
} | |
#[test] | |
fn right_parent_relation() { | |
let g1 = new("G1".to_string(), None); | |
let g2 = new("G2".to_string(), None); | |
let new_node = g1.new_contained_node("A"); | |
assert!(g1 == new_node.parent().unwrap()); | |
assert!(g2 != new_node.parent().unwrap()); | |
} | |
#[test] | |
fn create_simple_hypergraph_with_one_node() { | |
let g = new("G".to_string(), None); | |
let new_node = g.new_contained_node("A"); | |
//println!("Strong count: {}", ::std::rc::strong_count(&new_node)); | |
//println!("Weak count: {}", ::std::rc::weak_count(&new_node)); | |
assert_eq!(2, ::std::rc::strong_count(&new_node)); | |
assert_eq!(0, ::std::rc::weak_count(&new_node)); | |
assert_eq!("A", new_node.data()); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
extern crate hypergraph; | |
#[cfg(not(test))] | |
use hypergraph::hypergraph as H; | |
#[cfg(not(test))] | |
use hypergraph::hypergraph::SafeGraphMethods; | |
#[cfg(not(test))] | |
fn main() { | |
let g = H::new("G".to_string(), None); | |
println!("is root: {}", g.is_root()); | |
println!("Root data: '{}'", g.data()); | |
let node = g.new_contained_node("A"); | |
println!("child data: '{}'", node.data()); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment