Last active
May 3, 2019 05:33
-
-
Save elbaro/5dbe9ba7b0ce91340a32cd26059ef5d7 to your computer and use it in GitHub Desktop.
Graph in Rust
This file contains hidden or 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
| https://github.com/nrc/r4cppp/blob/master/graphs/README.md | |
| 1. lifetime | |
| - 1. User creates node/edge and provide their ref to Graph | |
| - 2. Let Graph owns nodes/edges. | |
| - Some helpers like from_adjacency_matrix() allocates on its own | |
| 2. mutability | |
| 3. Trait design | |
| - is Node aware of Edge? node.iter_neighbors() instead of graph.iter_neighbors(&node) | |
| - is Node aware of Graph? node.remove() instead of graph.remove(node.handle()) | |
| => Use NodeHandle{graph: &Graph, data: &Node} | |
| trait Graph { | |
| type NodeHandle; | |
| type EdgeHandle; | |
| type NodeHandleIterator; | |
| type EdgeHandleIterator; | |
| fn iter_nodes() -> NodeHandleIterator; | |
| fn iter_edges() -> EdgeHandleIterator; | |
| } | |
| trait Node { | |
| fn iter_outgoing_edges() { | |
| } | |
| } | |
| struct Edge { | |
| a: &Node, | |
| b: &Node, | |
| } | |
| mod dense_graph { | |
| impl Graph for DenseGraph { | |
| fn add_node() { | |
| } | |
| fn to_adjacency_list() { | |
| } | |
| } | |
| struct NodeHandle { | |
| ; | |
| } | |
| } | |
| impl Graph for AdjacencyList { | |
| } | |
| impl Graph for StaticAdjacencyList { | |
| // this type is not mutable | |
| } | |
| fn bfs(start, fn_outgoing_edges, end) { | |
| let q = Vec::new(); | |
| while q.is_non_empty() { | |
| q.pop_front(); | |
| for node in fn_outgoing_edges() { | |
| q.push_back(); | |
| if let && is_end() { | |
| break while; | |
| } | |
| } | |
| } | |
| return dist; | |
| } | |
| impl Node { | |
| fn bfs(&self, end) { | |
| } | |
| } | |
| undirected_graph.to_directed().bfs() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment