-
Notifications
You must be signed in to change notification settings - Fork 0
Graph Crate
The Graph Module provides shared and common functionalities that are:
- required by multiple algorithms (includes not yet implemented algorithms)
- not algorithm-specific (e.g. adding an edge)
It also contains the necessary data structures for a graph such as the Node struct (for vertices) and Link struct (for edges).
/// Available node colors
pub enum Color {
Red,
Blue,
Green,
Yellow,
White,
Cyan,
Black,
// ...
}
/// Semantics and color encoding
impl Color {
pub const DEFAULT: Color = Color::Lightsteelblue;
pub const NODE_ACTIVE: Color = Color::Red;
pub const NODE_VISITED: Color = Color::Green;
pub const EDGE_ACTIVE: Color = Color::Red;
pub const EDGE_VISITED: Color = Color::Blue;
pub const EDGE_VISITED_TREE: Color = Color::Green;
pub const EDGE_SHORTEST_PATH: Color = Color::Yellow;
pub const EDGE_MIN_COST_WITHIN_ACTIVE_EDGES: Color = Color::Cyan;
pub const EDGE_VISITED_NOT_TREE: Color = Color::Black;
}Feel free to add more colors* if your visualization concept requires it.
*In order for them to work with react-d3-graph, they have to be valid svg colors see https://johndecember.com/html/spec/colorsvg.html for a coprehensive list.
Every the information we want to visualize, for example the set of visited edges, is encoded in the algorithm specific visualisation state. This is for example the visualisation state for prims algorithm:
pub struct PrimVisualisationState {
pub graph: Graph<PrimConfiguration>,
pub helptext: String
// needed for visualisation
pub start_node: usize,
pub tree_edges: HashSet<(usize, usize)>,
pub tree_nodes: HashSet<usize>,
pub outgoing_edges: HashSet<(usize, usize)>,
pub best_outgoing: Option<(usize, usize)>,
}the fronend then uses this information to perform the concrete coloring of the
graph inside the colorGraph method inside hook.ts. For this is uses the color
values that are configured in colorConfig in config.ts.
/// Available node shapes
pub enum SymbolType {
Circle,
Cross,
Diamond,
Square,
Star,
Triangle,
Wye,
}pub struct Node {
pub id: usize,
/// visualization variables
name: String,
pub color: Color,
pub size: usize,
pub symbol_type: SymbolType,
pub x: usize,
pub y: usize,
}Sidenote: The x and y variables refer to the coordinates in the node layout.
pub struct Link {
pub source: usize,
pub target: usize,
pub weight: usize,
/// visualization variables
pub color: Color,
}Sidenote: The source and target value refer to a node id.
pub struct Graph {
pub nodes: Vec<Node>,
pub links: Vec<Link>,
}Each property must get a string name defined in Property::name(&self) since that name is used when rendering a property error.
pub enum Property {
UnweightedLinks,
PositiveWeightedLinks,
NonNegativeWeightedLinks,
WeightedLinks,
Connected,
Unconnected,
Empty,
Complete,
NotComplete
}impl Graph {
/// creates and adds a new node to the Graph
pub fn add_node(&mut self, index: usize);
/// adds a node to the Graph
pub fn add_node_with_value(&mut self, value: Node);
/// creates and adds a link to the Graph
pub fn add_edge(&mut self, from: usize, to: usize, new_weight: usize);
/// Gets the edge going from node with id `from` to `to`, if it exists
pub fn get_edge(&mut self, from: usize, to: usize) -> Option<usize>;
/// attempts to find previously unvisited neighbors of a specified node
pub fn find_unvisited_neighbours(&mut self, from: usize) -> Vec<usize>;
/// generates an adjacency matrix from the Graph
pub fn generate_adj_matrix(&mut self) -> Vec<Vec<usize>>;
}
Sidenote: The method `find_unvisited_neighbours` is Dijkstra-specific. It should not belong here.Additionally some standalone functions are available
/// create a new graph based on an adjacency matrix
pub fn generate_graph_by_matrix(matrix: Vec<Vec<usize>>) -> Graph;
/// reposition nodes (e.g. in a Circle)
pub fn node_layout(mut Graph, layout: NodeLayout) -> Graph;You can generate a Graph in two ways: via the adjacency matrix, or by defining every node and link in in a JSON file.
let data = vec![vec![1, 2, 99], vec![2, 1, 99], vec![1, 3, 99]];
let g = graph::generate_graph_by_matrix(data);Meanwhile, the generate_adj_matrix function allows you to convert a graph to an adjacency matrix.
Here is an example JSON file which contains minimum information to generate a simple graph:
{
"links": [
{
"source": 0,
"target": 1,
"weight": 10
}
],
"nodes": [
{
"id": 0,
"name": "A"
},
{
"id": 1,
"name": "B"
}
]
}Using this approach you may also set color, positions, sizes, etc.
Once you have the JSON, you need to pass it from the frontend via the set_graph function (since this operation is algorithm specific, you will find this function in algorithm models, e.g. rust/dijkstra/src/lib.rs).
Nodes are placed counterclockwise in a circle.
The aim is to arrange the nodes in a rectangle formation.
Implemented based on: Fruchterman, T. M. J., & Reingold, E. M. (1991). Graph Drawing by Force-Directed Placement. Software: Practice and Experience, 21(11).
Collisions with worldborder were not solved as in the paper but by subsequent rescaling.
Source is always placed on the far left and sink on the far right. All other nodes are arranged hierarchically in between. Nodes with the same distance from the start node are on the same level and stacked vertically.
If you want to add a feature that is going to be used by many algorithms (shared feature) you should simple add your code to the Graph module. Make sure to update the Typescript adapter accordingly!
If you want to implement a feature that is only need on few algorithms (e.g. multi edges) you should import the Graph struct to your algorithm module and implement additional traits locally (in said algorithm module).