From 96b0849a5ff3f510377499a353ae73239416c489 Mon Sep 17 00:00:00 2001
From: Julian T <julian@jtle.dk>
Date: Mon, 28 Oct 2019 20:55:21 +0100
Subject: Added graph structure in rust. Not working very well

---
 Readme.md                    | 12 +++++++
 sem1/algo/graph/Cargo.lock   |  6 ++++
 sem1/algo/graph/Cargo.toml   |  9 +++++
 sem1/algo/graph/src/graph.rs | 85 ++++++++++++++++++++++++++++++++++++++++++++
 sem1/algo/graph/src/main.rs  | 23 ++++++++++++
 5 files changed, 135 insertions(+)
 create mode 100644 Readme.md
 create mode 100644 sem1/algo/graph/Cargo.lock
 create mode 100644 sem1/algo/graph/Cargo.toml
 create mode 100644 sem1/algo/graph/src/graph.rs
 create mode 100644 sem1/algo/graph/src/main.rs

diff --git a/Readme.md b/Readme.md
new file mode 100644
index 0000000..f44390e
--- /dev/null
+++ b/Readme.md
@@ -0,0 +1,12 @@
+# Notes
+
+Collection of notes and implementation for courses.
+
+## Implementations
+
+- [ Dijkstra ](sem1/algo/mm12)
+- [ Breath first search ](sem1/algo/mm10/bfs.c)
+- [ Calculator in flex and bison ]( sem1/osc/mm11/regn )
+- [ Binary tree ](sem1/algo/mm6)
+- [ Merge sort ](sem1/algo/lek1/merge.c)
+
diff --git a/sem1/algo/graph/Cargo.lock b/sem1/algo/graph/Cargo.lock
new file mode 100644
index 0000000..74fba54
--- /dev/null
+++ b/sem1/algo/graph/Cargo.lock
@@ -0,0 +1,6 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+[[package]]
+name = "graph"
+version = "0.1.0"
+
diff --git a/sem1/algo/graph/Cargo.toml b/sem1/algo/graph/Cargo.toml
new file mode 100644
index 0000000..896f437
--- /dev/null
+++ b/sem1/algo/graph/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "graph"
+version = "0.1.0"
+authors = ["Julian T <julian@jtle.dk>"]
+edition = "2018"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/sem1/algo/graph/src/graph.rs b/sem1/algo/graph/src/graph.rs
new file mode 100644
index 0000000..cefd24f
--- /dev/null
+++ b/sem1/algo/graph/src/graph.rs
@@ -0,0 +1,85 @@
+use std::rc::{Rc, Weak};
+use std::cell::RefCell;
+use std::vec::Vec;
+use std::string::String;
+use std::collections::HashMap;
+use std::fmt;
+
+type EdgeRef = RefCell<Edge>;
+type VertexRef = RefCell<Vertex>;
+
+pub struct Edge {
+    from: Weak<VertexRef>,
+    to: Weak<VertexRef>,
+    weight: i32,
+}
+
+pub struct Vertex {
+    name: String,
+    pub adj: Vec<Rc<EdgeRef>>,
+}
+
+pub struct Graph {
+    vertexes: HashMap<String, Rc<VertexRef>>,
+    edges: Vec<Rc<EdgeRef>>,
+}
+
+impl Vertex {
+    pub fn new(name: &str) -> VertexRef {
+        RefCell::new( Vertex { name: String::from(name), adj: Vec::new() })
+    }
+}
+
+impl Graph {
+    pub fn new() -> Graph {
+        Graph { vertexes: HashMap::new(), edges: Vec::new() }
+    }
+
+    pub fn edge(&mut self, from: &str, to: &str, weight: i32) {
+        let from = match self.vertexes.get(from) {
+            Some(rc) => Rc::clone(rc),
+            None => self.add_vertex(from),
+        };
+
+        let to = match self.vertexes.get(to) {
+            Some(rc) => Rc::clone(rc),
+            None => self.add_vertex(to),
+        };
+
+        // Create edge
+        let e = Rc::new(RefCell::new( Edge { from: Rc::downgrade(&from), to: Rc::downgrade(&to), weight } ));
+
+        // Add to stuff
+        from.borrow_mut().adj.push(Rc::clone(&e));
+        self.edges.push(e);
+        
+    }
+
+    pub fn borrow_vertex(&self, name: &str) -> Option<Rc<VertexRef>> {
+        self.vertexes.get(name).and_then(|rc| Some(Rc::clone(rc)))
+    }
+
+    fn add_vertex(&mut self, name: &str) -> Rc<VertexRef> {
+        let v = Rc::new( Vertex::new(name) );
+
+        // Insert in hashmap
+        self.vertexes.insert(String::from(name), Rc::clone(&v));
+
+        // Return vertex
+        v
+    }
+
+}
+
+impl fmt::Display for Edge {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        let rc = self.to.upgrade().unwrap();
+        write!(f, "{}", Rc::clone(&rc).borrow())
+    }
+}
+
+impl fmt::Display for Vertex {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.name)
+    }
+}
diff --git a/sem1/algo/graph/src/main.rs b/sem1/algo/graph/src/main.rs
new file mode 100644
index 0000000..4f732e7
--- /dev/null
+++ b/sem1/algo/graph/src/main.rs
@@ -0,0 +1,23 @@
+
+mod graph;
+
+use graph::Graph;
+
+fn main() {
+
+    let mut g = Graph::new();
+
+    g.edge("a", "b", 10);
+    g.edge("a", "c", 10);
+    g.edge("a", "d", 10);
+
+    // Ahh this is hard
+    let v = g.borrow_vertex("a").unwrap();
+    let v23 = v.borrow();
+    let mut it = v23.adj.iter();
+    for e in it {
+        println!("{}", e.borrow());
+    }
+
+    println!("Hello, world!");
+}
-- 
cgit v1.2.3