hypergraph.rs

// 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());
        }
    }
}

main.rs

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