Struct prepona::algo::Eulerian

pub struct Eulerian<W, E: Edge<W>, Ty: EdgeDir, G: Graph<W, E, Ty>> { /* fields omitted */ }

Finds Eulerian trail and circuit.

Examples

use prepona::prelude::*;
use prepona::algo::Eulerian;
use prepona::storage::Mat;
use prepona::graph::MatGraph;

// Given:
//
//      a --- b --.
//     /  \       |
//    e    \      |
//     \    \     |
//      c -- d    |
//      |_________'
//
let mut graph = MatGraph::init(Mat::<usize>::init());
let a = graph.add_vertex();
let b = graph.add_vertex();
let c = graph.add_vertex();
let d = graph.add_vertex();
let e = graph.add_vertex();
graph.add_edge_unchecked(a, b, 1.into());
graph.add_edge_unchecked(a, e, 1.into());
graph.add_edge_unchecked(a, d, 1.into());
graph.add_edge_unchecked(b, c, 1.into());
graph.add_edge_unchecked(c, d, 1.into());
graph.add_edge_unchecked(c, e, 1.into());

// When: Performing Eulerian trail detection algorithm.
let trail = Eulerian::init(&graph).find_trail(&graph).unwrap();

// Then:
assert_eq!(trail.len(), 7);
assert_eq!(trail, vec![a, b, c, d, a, e, c]);

Implementations

impl<W, E, Ty, G> Eulerian<W, E, Ty, G> where
    E: Edge<W>,
    Ty: EdgeDir,
    G: Graph<W, E, Ty> + Vertices + Edges<W, E>, 

pub fn init(graph: &G) -> Self

Initializes the structure.

Arguments

graph: The graph to find the Eulerian trail or circuit in.

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

Finds id of the vertex to start the Eulerian trail from.

Returns

• Some: Containing the id of the starting vertex of Eulerian trail.
• None: If can not find a starting vertex for Eulerian trail.

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

Finds id of the vertex to start the Eulerian circuit from.

Returns

• Some: Containing the id of the starting vertex.
• None: If can not find a starting vertex for Eulerian circuit.

pub fn find_trail(self, graph: &G) -> Result<Vec<usize>>

Finds the Eulerian trail if there is one.

Arguments

graph: Graph to search the Eulerian trail in it.

Returns

• Ok: Containing list of vector ids that will get visited during the Eulerian trail.
• Err: If graph does not have Eulerian trail.

pub fn find_circuit(self, graph: &G) -> Result<Vec<usize>>

Finds the Eulerian circuit if there is one.

Arguments

graph: Graph to search the eulerian circuit in it.

Returns

• Ok: Containing list of vector ids that will get visited during the eulerian circuit.
• Err: If graph does not have Eulerian circuit.