Struct DirectedGraph 

pub struct DirectedGraph { /* private fields */ }

A simple unweighted directed graph.

Arcs are represented as ordered pairs (u, v) meaning there is an arc from vertex u to vertex v. Self-loops are permitted.

Example

use problemreductions::topology::DirectedGraph;

let g = DirectedGraph::new(3, vec![(0, 1), (1, 2)]);
assert_eq!(g.num_vertices(), 3);
assert_eq!(g.num_arcs(), 2);
assert!(g.is_dag());

let cyclic = DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]);
assert!(!cyclic.is_dag());

Implementations

impl DirectedGraph

pub fn new(num_vertices: usize, arcs: Vec<(usize, usize)>) -> Self

Creates a new directed graph with the given vertices and arcs.

Arguments

• num_vertices - Number of vertices in the graph
• arcs - List of arcs as (source, target) pairs

Panics

Panics if any arc references a vertex index >= num_vertices.

pub fn empty(num_vertices: usize) -> Self

Creates an empty directed graph with the given number of vertices and no arcs.

pub fn num_vertices(&self) -> usize

Returns the number of vertices in the graph.

pub fn num_arcs(&self) -> usize

Returns the number of arcs in the graph.

pub fn arcs(&self) -> Vec<(usize, usize)>

Returns all arcs as (source, target) pairs.

pub fn has_arc(&self, u: usize, v: usize) -> bool

Returns true if there is an arc from u to v.

pub fn successors(&self, v: usize) -> Vec<usize>

Returns the outgoing neighbors (successors) of vertex v.

These are all vertices w such that there is an arc v → w.

pub fn predecessors(&self, v: usize) -> Vec<usize>

Returns the incoming neighbors (predecessors) of vertex v.

These are all vertices u such that there is an arc u → v.

pub fn is_dag(&self) -> bool

Returns true if the graph is a directed acyclic graph (DAG).

Uses petgraph’s topological sort to detect cycles: if a topological ordering exists, the graph is acyclic.

pub fn induced_subgraph(&self, keep: &[bool]) -> Self

Returns the induced subgraph on vertices where keep[v] == true.

Vertex indices are remapped to be contiguous starting from 0. An arc (u, v) is included only if both u and v are kept. The new index of a kept vertex is its rank among the kept vertices in increasing order.

Panics

Panics if keep.len() != self.num_vertices().

Trait Implementations

impl Clone for DirectedGraph

fn clone(&self) -> DirectedGraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for DirectedGraph

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for DirectedGraph

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl PartialEq for DirectedGraph

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for DirectedGraph

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl VariantParam for DirectedGraph

const CATEGORY: &'static str = "graph"

Category name (e.g., "graph", "weight", "k").

const VALUE: &'static str = "DirectedGraph"

Type name within the category (e.g., "SimpleGraph", "i32").

const PARENT_VALUE: Option<&'static str> = None

Parent type name in the subtype hierarchy, or None for root types.

impl Eq for DirectedGraph