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

source

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:

  1. Undirected graph:
let mut g: graphs::Graph = graphs::Graph::new(false);
  1. Directed graph:
let mut g: graphs::Graph = graphs::Graph::new(true);
source

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
source

pub fn get_topological_order(&mut self) -> Vec<String>

Returns topological sorted order of the vertice of the graph

source

pub fn get_order(&mut self, node: &String, order: &mut Vec<String>)

source

pub fn get_vertices(&mut self) -> &mut HashMap<String, Vertex>

source

pub fn get_edges(&mut self) -> &mut HashMap<(String, String), Edge>

source

pub fn add_vertex(&mut self, label: String)

Add vertex to the graph

Parameters:
  1. label - the label of the vertex which should be of type String

  2. 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
source

pub fn remove_vertex(&mut self, label: String)

Remove vertex and all of its adjacent edges.

Parameters
  1. label: The label of the vertex
Example
g.remove_vertex(String::from("A")); // Remove vertex A from the graph G
source

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
  1. (endpoint1, endpoint2) - the two endpoints of the edge each will be of type String

  2. 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),
);
source

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
  1. (endpoint1, endpoint2) - the two endpoints of the edge each will be of type String

  2. 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),
);
source

pub fn remove_edge(&mut self, e: (String, String))

Removes an edge from a graph (Endpoint vertices are not affected)

Parameters
  1. (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')),
);
source

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:
  1. 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
source

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:
  1. 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
source

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:
  1. 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
source

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>>

source

pub fn write_adjacency_matrix( matrix: &[Vec<u32>], filename: &str ) -> Result<(), Error>

Writes an adjacency matrix to a file.

source

pub fn get_vertex(&mut self, label: &String) -> Option<&mut Vertex>

Function to get the vertex given the label

Parameters:
  1. 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)

Trait Implementations§

source§

impl Clone for Graph

source§

fn clone(&self) -> Graph

Returns a copy of the value. Read more
1.0.0 · source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more

Auto Trait Implementations§

§

impl RefUnwindSafe for Graph

§

impl Send for Graph

§

impl Sync for Graph

§

impl Unpin for Graph

§

impl UnwindSafe for Graph

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.