Struct falcon::graph::Graph

pub struct Graph<V: Vertex, E: Edge> { /* fields omitted */ }

A directed graph.

Methods

impl<V, E> Graph<V, E> where     V: Vertex,     E: Edge,

pub fn new() -> Graph<V, E>

pub fn num_vertices(&self) -> usize

pub fn has_vertex(&self, index: usize) -> bool

Returns true if the vertex with the given index exists in this graph

pub fn set_head(&mut self, index: usize) -> Result<()>

Sets the head of this graph.

pub fn head(&self) -> Option<usize>

Returns the head of this graph.

pub fn remove_vertex(&mut self, index: usize) -> Result<()>

Removes a vertex, and all edges associated with that vertex.

pub fn remove_edge(&mut self, head: usize, tail: usize) -> Result<()>

Removes an edge

pub fn insert_vertex(&mut self, v: V) -> Result<()>

Inserts a vertex into the graph.

Errors

Error if the vertex already exists by index.

pub fn insert_edge(&mut self, edge: E) -> Result<()>

Inserts an edge into the graph.

Errors

Error if the edge already exists by indices.

pub fn successors(&self, index: usize) -> Result<Vec<&V>>

Returns all immediate successors of a vertex from the graph.

pub fn predecessors(&self, index: usize) -> Result<Vec<&V>>

Returns all immediate predecessors of a vertex from the graph.

pub fn compute_post_order(&self, root: usize) -> Result<Vec<usize>>

pub fn compute_dominance_frontiers(     &self,     start_index: usize ) -> Result<HashMap<usize, HashSet<usize>>>

Computes the dominance frontiers for all vertices in the graph

Warning

Unsure of correctness of this implementation

pub fn compute_immediate_dominators(     &self,     start_index: usize ) -> Result<HashMap<usize, usize>>

pub fn compute_dominators(     &self,     start_index: usize ) -> Result<HashMap<usize, HashSet<usize>>>

Computes dominators for all vertices in the graph

pub fn compute_predecessors(&self) -> Result<HashMap<usize, HashSet<usize>>>

Computes predecessors for all vertices in the graph

The resulting sets include all predecessors for each vertex in the graph, not just immediate predecessors.

Given A -> B -> C, both A and B will be in the set for C.

pub fn compute_acyclic(     &self,     start_index: usize ) -> Result<Graph<NullVertex, NullEdge>>

Creates an acyclic graph with NullVertex and NullEdge

pub fn vertices(&self) -> Vec<&V>

Returns all vertices in the graph.

pub fn vertices_mut(&mut self) -> Vec<&mut V>

pub fn vertex(&self, index: usize) -> Result<&V>

Fetches an index from the graph by index.

pub fn vertex_mut(&mut self, index: usize) -> Result<&mut V>

pub fn edge(&self, head: usize, tail: usize) -> Result<&E>

pub fn edge_mut(&mut self, head: usize, tail: usize) -> Result<&mut E>

pub fn edges(&self) -> Vec<&E>

Get a reference to every Edge in the Graph.

pub fn edges_mut(&mut self) -> Vec<&mut E>

Get a mutable reference to every Edge in the Graph.

pub fn edges_out(&self, index: usize) -> Result<&Vec<E>>

Return all edges out for a vertex

pub fn edges_in(&self, index: usize) -> Result<&Vec<E>>

Return all edges in for a vertex

pub fn dot_graph(&self) -> String

Returns a string in the graphviz format

Trait Implementations

impl<V: Clone + Vertex, E: Clone + Edge> Clone for Graph<V, E>

fn clone(&self) -> Graph<V, E>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<V: Debug + Vertex, E: Debug + Edge> Debug for Graph<V, E>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<V: Eq + Vertex, E: Eq + Edge> Eq for Graph<V, E>

impl<V: Hash + Vertex, E: Hash + Edge> Hash for Graph<V, E>

fn hash<__HVE: Hasher>(&self, state: &mut __HVE)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where     H: Hasher,

Feeds a slice of this type into the given [Hasher].

impl<V: Ord + Vertex, E: Ord + Edge> Ord for Graph<V, E>

fn cmp(&self, other: &Graph<V, E>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

impl<V: PartialEq + Vertex, E: PartialEq + Edge> PartialEq for Graph<V, E>

fn eq(&self, other: &Graph<V, E>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Graph<V, E>) -> bool

This method tests for !=.

impl<V: PartialOrd + Vertex, E: PartialOrd + Edge> PartialOrd for Graph<V, E>

fn partial_cmp(&self, other: &Graph<V, E>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Graph<V, E>) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Graph<V, E>) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Graph<V, E>) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Graph<V, E>) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.