Struct graphalgos::graphs::Graph
source · pub struct Graph {
pub vertices: HashMap<String, Vertex>,
pub edges: HashMap<(String, String), Edge>,
pub edge_type: EdgeType,
}
Expand description
This is the basic graph structure. Graph consists of vertices, edges and edge_type
Vertices:
Vertices - Hashmap of type String, Vertex. Vertex has a label and a value
Example: A vertex with label A and value 10 will look like this
self.vertices.insert(
String::from("A");
Vertex {
label: String::from("A"),
value: 10,
},
);
The structure of the vertex
pub struct Vertex<T> {
pub label: VLT,
pub value: T,
}
Edges:
Edges - Hashmap of type (VLT, VLT), Edge.
(VLT, VLT) are two end points of the edge.
Edge has weight and edge type
Example:
HashMap - Key: (String::from("A"), String::from("B")) | Value: Edge
Edge Looks like this:
pub struct Edge {
pub endpoints: (VLT, VLT),
pub weight: GNumber,
pub edge_type: EdgeType,
}
Edge Type
edge_type: EdgeType - Directed or Undirected
Fields§
§vertices: HashMap<String, Vertex>
§edges: HashMap<(String, String), Edge>
§edge_type: EdgeType
Implementations§
source§impl Graph
impl Graph
sourcepub fn new(directed: bool) -> Graph
pub fn new(directed: bool) -> Graph
Creates a new Graph
Parameters:
directed - type boolean
directed = true if we want a directed graph
directed = false if we want an undirected graph
Return value
This function returns Graph - directed or undirected based on the parameter passed (Graph)
Example
Basic Usage:
- Undirected graph:
let mut g: graphs::Graph = graphs::Graph::new(false);
- Directed graph:
let mut g: graphs::Graph = graphs::Graph::new(true);
sourcepub fn print(&self)
pub fn print(&self)
Prints the graph
usage:
let mut g: graphs::Graph = graphs::Graph::new(false); // creates undirected graph
g.print() // prints the graph
sourcepub fn get_topological_order(&mut self) -> Vec<String>
pub fn get_topological_order(&mut self) -> Vec<String>
Returns topological sorted order of the vertice of the graph
pub fn get_order(&mut self, node: &String, order: &mut Vec<String>)
pub fn get_vertices(&mut self) -> &mut HashMap<String, Vertex>
pub fn get_edges(&mut self) -> &mut HashMap<(String, String), Edge>
sourcepub fn add_vertex(&mut self, label: String)
pub fn add_vertex(&mut self, label: String)
Add vertex to the graph
Parameters:
-
label - the label of the vertex which should be of type String
-
value - value of the vertex, any generic
Example
let mut G: graphs::Graph = graphs::Graph::new(false); // create undirected graph
g.add_vertex(String::from("A")); // add vertex to the graph with label A and value 0
sourcepub fn remove_vertex(&mut self, label: String)
pub fn remove_vertex(&mut self, label: String)
Remove vertex and all of its adjacent edges.
Parameters
- label: The label of the vertex
Example
g.remove_vertex(String::from("A")); // Remove vertex A from the graph G
sourcepub fn add_edge(&mut self, e: (String, String), weight: GNumber)
pub fn add_edge(&mut self, e: (String, String), weight: GNumber)
Adds an edge to the graph (Endpoint vertices must be present in graph)
Parameters
-
(endpoint1, endpoint2) - the two endpoints of the edge each will be of type String
-
weight - The weight of the edge
Example
// Edge with I32 weights having endpoints "A" and "B"
g.add_edge(
(String::from("A"), String::from('B')),
graphs::GNumber::I32(4),
);
// Edge with F32 weights having endpoints "A" and "B"
g2.add_edge(
(String::from("A"), String::from('B')),
graphs::GNumber::F32(4.),
);
// Edge with U32 weights having endpoints "A" and "B"
g3.add_edge(
(String::from("A"), String::from('B')),
graphs::GNumber::U32(2),
);
sourcepub fn update_edge(&mut self, e: (String, String), weight: GNumber)
pub fn update_edge(&mut self, e: (String, String), weight: GNumber)
Update the weight of an edge to the graph (Edge must be present in graph)
Parameters
-
(endpoint1, endpoint2) - the two endpoints of the edge each will be of type String
-
weight - The weight of the edge
Example
// This will update the value of the edge with endpoint (A, B) to 10 (I32 value)
g.update_edge(
(String::from("A"), String::from('B')),
graphs::GNumber::I32(10),
);
sourcepub fn remove_edge(&mut self, e: (String, String))
pub fn remove_edge(&mut self, e: (String, String))
Removes an edge from a graph (Endpoint vertices are not affected)
Parameters
- (endpoint1, endpoint2) - the two endpoints of the edge (type String)
Example
// This will remove edge with endpoints A and B
g.remove_edge(
(String::from("A"), String::from('B')),
);
sourcepub fn get_neighbors(&self, label: &String) -> Vec<String>
pub fn get_neighbors(&self, label: &String) -> Vec<String>
Input a vertex label (Returns a vector of vertex labels which correspond to the neighbors of the input vertex)
Parameter:
- label - Label of type String
Return Value:
Returns a vector of labels of all the vertices that are neighbors of this vertex
Example
G.get_neighbors(String::from("A")) // returns all the neighbors of A
// example return: ["B", "C", "D"]. If B, C and D are neighbors of A
sourcepub fn get_out_neighbors(&self, label: &String) -> Vec<String>
pub fn get_out_neighbors(&self, label: &String) -> Vec<String>
Input a vertex label. Returns a vector of vertex labels which correspond to the outgoing neighbors of the input vertex.
Parameter:
- label - Label of type String
Return Value:
Returns a vector of labels of all the vertices that are outgoing neighbors of this vertex. This is for a directed graph
Example
g.get_out_neighbors(String::from("A")) // returns all the outgoing neighbors of A
// example return: ["B", "C", "D"].
// A -> B, A -> C, A -> D
sourcepub fn get_in_neighbors(&self, label: &String) -> Vec<String>
pub fn get_in_neighbors(&self, label: &String) -> Vec<String>
Input a vertex label. Returns a vector of vertex labels which correspond to the incoming neighbors of the input vertex.
Parameter:
- label - Label of type String
Return Value:
Returns a vector of labels of all the vertices that are incoming neighbors of this vertex. This is for a directed graph
Example
G.get_in_neighbors(String::from("A")) // returns all the incoming neighbors of A
// example return: ["B", "C", "D"].
// B -> A, C -> A, D -> A
sourcepub fn read_adjacency_matrix(filename: &str) -> Result<Vec<Vec<u32>>, Error>
pub fn read_adjacency_matrix(filename: &str) -> Result<Vec<Vec<u32>>, Error>
Reads an adjacency matrix from a file and returns it as a Vec<Vec<u32>>
sourcepub fn write_adjacency_matrix(
matrix: &[Vec<u32>],
filename: &str
) -> Result<(), Error>
pub fn write_adjacency_matrix( matrix: &[Vec<u32>], filename: &str ) -> Result<(), Error>
Writes an adjacency matrix to a file.
sourcepub fn get_vertex(&mut self, label: &String) -> Option<&mut Vertex>
pub fn get_vertex(&mut self, label: &String) -> Option<&mut Vertex>
Function to get the vertex given the label
Parameters:
- label - Label of the vertex - type String
Return Type:
Returns an Option of type mutable Vertex
. If there are no vertex with the provided label - None will be returned
Example
let vertex_A = g.get_vertex(String::from("A")); // this wil return the vertex A which is mutable (We can change the value of the vertex)