Struct biodivine_lib_param_bn::SdGraph

pub struct SdGraph { /* private fields */ }

A more efficient representation of a signed directed graph that can be used for studying the properties of a RegulatoryGraph.

TODO: If we rewrite the API at some point, this should just merge with a RegulatoryGraph.

Implementations

impl SdGraph

pub fn mk_all_vertices(&self) -> HashSet<VariableId>

impl SdGraph

pub fn forward_reachable( &self, initial: HashSet<VariableId>, ) -> HashSet<VariableId>

Return the set of vertices forward-reachable from the initial set.

pub fn backward_reachable( &self, initial: HashSet<VariableId>, ) -> HashSet<VariableId>

Return the set of vertices backward-reachable from the initial set.

pub fn restricted_forward_reachable( &self, restriction: &HashSet<VariableId>, initial: HashSet<VariableId>, ) -> HashSet<VariableId>

Return the set of vertices forward-reachable from the initial set within the restriction set.

pub fn restricted_backward_reachable( &self, restriction: &HashSet<VariableId>, initial: HashSet<VariableId>, ) -> HashSet<VariableId>

Return the set of vertices backward-reachable from the initial set within the restriction set.

impl SdGraph

pub fn strongly_connected_components(&self) -> Vec<HashSet<VariableId>>

Find all non-trivial strongly connected components of this SdGraph.

The result is sorted by component size.

pub fn restricted_strongly_connected_components( &self, restriction: &HashSet<VariableId>, ) -> Vec<HashSet<VariableId>>

Find all non-trivial strongly connected components in the given restriction of this SdGraph.

The result is sorted by component size.

pub fn _restricted_strongly_connected_components<E, F: Fn() -> Result<(), E>>( &self, restriction: &HashSet<VariableId>, log_level: usize, interrupt: &F, ) -> Result<Vec<HashSet<VariableId>>, E>

A version of SdGraph::restricted_strongly_connected_components with cancellation and logging.

impl SdGraph

pub fn weakly_connected_components(&self) -> Vec<HashSet<VariableId>>

The list of all weakly connected components in this graph.

pub fn restricted_weakly_connected_components( &self, restriction: &HashSet<VariableId>, ) -> Vec<HashSet<VariableId>>

Weakly connected components within the sub-graph induced by the given restriction set.

pub fn _restricted_weakly_connected_components<E, F: Fn() -> Result<(), E>>( &self, restriction: &HashSet<VariableId>, log_level: usize, interrupt: &F, ) -> Result<Vec<HashSet<VariableId>>, E>

A version of SdGraph::restricted_weakly_connected_components with cancellation and logging.

impl SdGraph

pub fn shortest_cycle( &self, restriction: &HashSet<VariableId>, pivot: VariableId, upper_bound: usize, ) -> Option<Vec<VariableId>>

Compute the shortest cycle (or one of the shortest cycles) within restriction that also contains the pivot vertex. The result is a vector with pivot at position zero and other vertices in the order in which they appear on the cycle. If no such cycle exists, returns None.

The result is similar to shortest_cycle_length, but there is non-trivial overhead associated with actually computing the cycle, not just its length, hence we separate the two algorithms. Panics if pivot is not a member of restriction.

Finally, you can restrict the search to only include cycles of a specific length by providing an inclusive upper_bound (the length is counted as the number of edges in the cycle, i.e. a cycle is returned only if edge_count <= upper_bound).

pub fn shortest_parity_cycle( &self, restriction: &HashSet<VariableId>, pivot: VariableId, target_parity: Sign, upper_bound: usize, ) -> Option<Vec<VariableId>>

Same as shortest_cycle, but in this scenario, only cycles of prescribed parity are considered.

Cycle parity is calculated over the monotonicity of its edges (i.e. + and - is negative, - and - is positive). Naturally, we only consider simple cycles (i.e. no vertex appears more than one). Otherwise, a negative parity cycle can be always made into positive parity cycle by repeating it twice.

Finally, you can restrict the search to only include cycles of a specific length by providing an inclusive upper_bound (the length is counted as the number of edges in the cycle, i.e. a cycle is returned only if edge_count <= upper_bound).

impl SdGraph

pub fn restricted_feedback_vertex_set( &self, restriction: &HashSet<VariableId>, ) -> HashSet<VariableId>

Compute a feedback vertex set of the subgraph induced by the vertices in the given restriction set.

A feedback vertex set is a set of vertices such that when these vertices are removed, the resulting graph is acyclic.

The algorithm attempts to minimize the size of the resulting FVS, but it is not guaranteed that the result is minimal, as the minimal FVS problem is NP complete.

The algorithm works by greedily picking vertices from the shortest cycles, prioritising vertices with the highest overall degree.

pub fn _restricted_feedback_vertex_set<E, F: Fn() -> Result<(), E>>( &self, restriction: &HashSet<VariableId>, log_level: usize, interrupt: &F, ) -> Result<HashSet<VariableId>, E>

A version of SdGraph::restricted_feedback_vertex_set with cancellation and logging.

pub fn restricted_parity_feedback_vertex_set( &self, restriction: &HashSet<VariableId>, parity: Sign, ) -> HashSet<VariableId>

Compute a feedback vertex set of the desired parity, considered within the subgraph induced by the vertices in restriction.

A parity feedback vertex set is a set of vertices such that when removed, the graph has no cycles of the specified parity. See also restriction_feedback_vertex_set for notes about determinism, minimality and complexity.

pub fn _restricted_parity_feedback_vertex_set<E, F: Fn() -> Result<(), E>>( &self, restriction: &HashSet<VariableId>, parity: Sign, log_level: usize, interrupt: &F, ) -> Result<HashSet<VariableId>, E>

A version of SdGraph::restricted_parity_feedback_vertex_set with cancellation and logging.

impl SdGraph

pub fn restricted_independent_cycles( &self, restriction: &HashSet<VariableId>, ) -> Vec<Vec<VariableId>>

Compute a collection of independent cycles of this directed graph within the given restriction set.

Independent cycles are cycles that do not intersect, but together cover every cycle in the graph. The method tries to maximize the number of the returned cycles, but the result is not guaranteed to be maximal.

The cycles are expected to be sorted by length, but otherwise the result is not guaranteed to be deterministic.

pub fn _restricted_independent_cycles<E, F: Fn() -> Result<(), E>>( &self, restriction: &HashSet<VariableId>, log_level: usize, interrupt: &F, ) -> Result<Vec<Vec<VariableId>>, E>

A version of SdGraph::restricted_independent_cycles with cancellation and logging.

pub fn restricted_independent_parity_cycles( &self, restriction: &HashSet<VariableId>, parity: Sign, ) -> Vec<Vec<VariableId>>

Compute a collection of independent cycles of the given parity within the desired restriction space.

Independent parity cycles are cycles that are disjoint but together cover every cycle of the desired parity in the graph. The method tries to maximize the number of the returned cycles, but the result is not guaranteed to be maximal.

The cycles are expected to be sorted by length, but otherwise the result is not guaranteed to be deterministic.

pub fn _restricted_independent_parity_cycles<E, F: Fn() -> Result<(), E>>( &self, restriction: &HashSet<VariableId>, parity: Sign, log_level: usize, interrupt: &F, ) -> Result<Vec<Vec<VariableId>>, E>

A version of SdGraph::restricted_independent_parity_cycles with cancellation and logging.

Trait Implementations

impl Clone for SdGraph

fn clone(&self) -> SdGraph

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for SdGraph

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

Formats the value using the given formatter.

impl From<&RegulatoryGraph> for SdGraph

fn from(rg: &RegulatoryGraph) -> Self

Converts to this type from the input type.