algograph/graph/
trait.rs

1use crate::graph::*;
2
3/// A trait for low-level growable graphs.
4pub trait GrowableGraph {
5    /// Generate a new and empty graph.
6    fn new() -> Self;
7    /// Add a new vertex into the graph.
8    fn add_vertex(&mut self) -> VertexId;
9    /// Add a new edge from `source` to `sink` for directed graphs or between them for undirected graphs.
10    fn add_edge(&mut self, source: VertexId, sink: VertexId) -> EdgeId;
11}
12
13/// A trait for low-level graphs whose edges can be removed.
14pub trait EdgeShrinkableGraph {
15    /// Remove an edge from the graph.
16    ///
17    /// If the edge ID is not in the graph, `None` is returned;
18    /// otherwise, it returns complete information about the edge.
19    fn remove_edge(&mut self, edge: &EdgeId) -> Option<Edge>;
20}
21
22/// A trait for low-level graphs whose vertices can be removed.
23pub trait VertexShrinkableGraph: EdgeShrinkableGraph {
24    /// Removes a vertex from the graph and all edges connected to this vertex.
25    ///
26    /// It returns an iterator over all edges connected to the vertex.
27    /// Each edge will occur exactly once during the iteration.
28    /// Thus, self-loops will occur once as well.
29    ///
30    /// * For undirected graphs, the removed vertex can be either the sources or the sinks of returned edges.
31    ///   It is implementation-specific.
32    /// * If the vertex is not in the graph, it returns an empty iterator.
33    fn remove_vertex(&mut self, vertex: &VertexId) -> Box<dyn Iterator<Item = Edge> + 'static>;
34}
35
36/// A trait for querying vertices and edges about low-level graphs.
37pub trait QueryableGraph {
38    /// Number of vertices in the graph.
39    fn vertex_size(&self) -> usize;
40    /// Iteration over all vertices in the graph.
41    fn iter_vertices(&self) -> Box<dyn Iterator<Item = VertexId> + '_>;
42    /// Whether a vertex is in the graph or not.
43    fn contains_vertex(&self, v: &VertexId) -> bool;
44
45    /// Number of edges in the graph.
46    fn edge_size(&self) -> usize;
47    /// Iteration over all edges in the graph.
48    fn iter_edges(&self) -> Box<dyn Iterator<Item = Edge> + '_>;
49    /// Whether an edge is in the graph or not.
50    fn contains_edge(&self, e: &EdgeId) -> bool;
51    /// Returns information about a specified edge in the graph.
52    fn find_edge(&self, e: &EdgeId) -> Option<Edge>;
53    /// Iteration over all edges between two vertices in undirected graphs
54    /// or those from `source` to `sink` in directed graphs.
55    fn edges_connecting(
56        &self,
57        source: &VertexId,
58        sink: &VertexId,
59    ) -> Box<dyn Iterator<Item = Edge> + '_>;
60    /// Iteration over all edges going into the vertex `v`.
61    ///
62    /// For undirected graphs, the sinks of returned edges must be `v`.
63    fn in_edges(&self, v: &VertexId) -> Box<dyn Iterator<Item = Edge> + '_>;
64    /// Iteration over all edges going out of `v`.
65    ///
66    /// For undirected graphs, the sources of returned edges must be `v`.
67    fn out_edges(&self, v: &VertexId) -> Box<dyn Iterator<Item = Edge> + '_>;
68
69    /// Returns something can inspect into the graph.
70    fn debug(&self) -> Box<dyn std::fmt::Debug + '_>
71    where
72        Self: Sized,
73    {
74        self.debug_with_indent(0, 2)
75    }
76
77    /// Returns something can inspect into the graph, with customzied indentation.
78    fn debug_with_indent(
79        &self,
80        init_indent: usize,
81        indent_step: usize,
82    ) -> Box<dyn std::fmt::Debug + '_>
83    where
84        Self: Sized,
85    {
86        Box::new(super::graph_debug::GraphDebug::new(
87            self,
88            init_indent,
89            indent_step,
90        ))
91    }
92}
93
94/// Whether a graph is directed or not.
95pub trait DirectedOrNot {
96    /// When the graph is directed, it is true; otherwise, it is false.
97    const DIRECTED_OR_NOT: bool;
98}
99
100/// A trait for subgraphs.
101///
102/// New vertices and edges are disallowed to add into subgraphs.
103/// But those from the underlying graph can be uncovered.
104pub trait Subgraph {
105    type LowerGraph;
106
107    fn new(lower_graph: Self::LowerGraph) -> Self;
108    /// Discloses a vertex.
109    ///
110    /// * Shadowed edges connecting to this vertex will not automatically be disclosed.
111    /// * It takes no effect at all to disclose an already disclosed vertex.
112    fn disclose_vertex(&mut self, v: VertexId) -> &mut Self;
113    /// Discloses an edge, and both endpoints of this edge as well.
114    ///
115    /// * It takes no effect at all to disclose an already disclosed edge.
116    fn disclose_edge(&mut self, v: EdgeId) -> &mut Self;
117}
118
119/// A trait with default implementation for dumping a (directed or not) graph in graphviz format.
120pub trait DumpInGraphviz: QueryableGraph + DirectedOrNot {
121    fn dump_in_graphviz<W>(&self, out: &mut W, graph_name: &str) -> std::io::Result<()>
122    where
123        W: std::io::Write,
124    {
125        if Self::DIRECTED_OR_NOT {
126            writeln!(out, "digraph {} {{", graph_name)?;
127        } else {
128            writeln!(out, "graph {} {{", graph_name)?;
129        }
130        for v in self.iter_vertices() {
131            writeln!(out, "  {} ;", v.0)?;
132        }
133        for e in self.iter_edges() {
134            if Self::DIRECTED_OR_NOT {
135                writeln!(out, "  {} -> {} ;", e.source.0, e.sink.0)?;
136            } else {
137                writeln!(out, "  {} -- {} ;", e.source.0, e.sink.0)?;
138            }
139        }
140        writeln!(out, "}}")?;
141        Ok(())
142    }
143}
144
145impl<G: QueryableGraph + DirectedOrNot> DumpInGraphviz for G {}
algograph/graph/trait.rs

algograph/graph/
trait.rs
