Struct falcon::graph::Graph

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

A directed graph.

Methods

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

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

pub fn num_vertices(&self) -> usize

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

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

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

Sets the head of this graph.

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

Returns the head of this graph.

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

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

pub fn remove_edge(&mut self, head: u64, tail: u64) -> 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: u64) -> Result<Vec<&V>>

Returns all immediate successors of a vertex from the graph.

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

Returns all immediate predecessors of a vertex from the graph.

pub fn compute_dominance_frontiers(
    &self,
    start_index: u64
) -> Result<BTreeMap<u64, BTreeSet<u64>>>

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: u64
) -> Result<BTreeMap<u64, u64>>

pub fn compute_dominators(
    &self,
    start_index: u64
) -> Result<BTreeMap<u64, BTreeSet<u64>>>

Computes dominators for all vertices in the graph

pub fn compute_predecessors(&self) -> Result<BTreeMap<u64, BTreeSet<u64>>>

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: u64
) -> 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: u64) -> Option<&V>

Fetches an index from the graph by index.

pub fn vertex_mut(&mut self, index: u64) -> Option<&mut V>

pub fn edge(&self, head: u64, tail: u64) -> Option<&E>

pub fn edge_mut(&mut self, head: u64, tail: u64) -> Option<&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: u64) -> Option<&Vec<E>>

Return all edges out for a vertex

pub fn edges_in(&self, index: u64) -> Option<&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, E: Clone> 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, E: Debug> Debug for Graph<V, E>

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

Formats the value using the given formatter.

impl<V: Eq, E: Eq> Eq for Graph<V, E>

impl<V: Hash, E: Hash> Hash for Graph<V, E>

fn hash<__HVE: Hasher>(&self, __arg_0: &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, E: Ord> Ord for Graph<V, E>

fn cmp(&self, __arg_0: &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, E: PartialEq> PartialEq for Graph<V, E>

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

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

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

This method tests for !=.

impl<V: PartialOrd, E: PartialOrd> PartialOrd for Graph<V, E>

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

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

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

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

fn le(&self, __arg_0: &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, __arg_0: &Graph<V, E>) -> bool

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

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

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