fso_graph_builder/builder.rs
1use std::{convert::TryFrom, marker::PhantomData};
2
3use crate::{
4 graph::csr::{CsrLayout, NodeValues},
5 index::Idx,
6 input::{edgelist::EdgeList, InputCapabilities, InputPath},
7 prelude::edgelist::{EdgeIterator, EdgeWithValueIterator},
8 Error,
9};
10use std::path::Path as StdPath;
11
12pub struct Uninitialized {
13 csr_layout: CsrLayout,
14}
15
16pub struct FromEdges<NI, Edges>
17where
18 NI: Idx,
19 Edges: IntoIterator<Item = (NI, NI)>,
20{
21 csr_layout: CsrLayout,
22 edges: Edges,
23 _node: PhantomData<NI>,
24}
25
26pub struct FromEdgeListAndNodeValues<NI, NV, EV>
27where
28 NI: Idx,
29{
30 csr_layout: CsrLayout,
31 node_values: NodeValues<NV>,
32 edge_list: EdgeList<NI, EV>,
33}
34
35pub struct FromEdgesWithValues<NI, Edges, EV>
36where
37 NI: Idx,
38 Edges: IntoIterator<Item = (NI, NI, EV)>,
39{
40 csr_layout: CsrLayout,
41 edges: Edges,
42 _node: PhantomData<NI>,
43}
44
45#[cfg(feature = "gdl")]
46#[cfg_attr(all(feature = "gdl", has_doc_cfg), doc(cfg(feature = "gdl")))]
47pub struct FromGdlString<NI>
48where
49 NI: Idx,
50{
51 csr_layout: CsrLayout,
52 gdl: String,
53 _node: PhantomData<NI>,
54}
55
56#[cfg(feature = "gdl")]
57#[cfg_attr(all(feature = "gdl", has_doc_cfg), doc(cfg(feature = "gdl")))]
58pub struct FromGdlGraph<'a, NI>
59where
60 NI: Idx,
61{
62 csr_layout: CsrLayout,
63 gdl_graph: &'a gdl::Graph,
64 _node: PhantomData<NI>,
65}
66
67pub struct FromInput<NI, P, Format>
68where
69 P: AsRef<StdPath>,
70 NI: Idx,
71 Format: InputCapabilities<NI>,
72 Format::GraphInput: TryFrom<InputPath<P>>,
73{
74 csr_layout: CsrLayout,
75 _idx: PhantomData<NI>,
76 _path: PhantomData<P>,
77 _format: PhantomData<Format>,
78}
79
80pub struct FromPath<NI, P, Format>
81where
82 P: AsRef<StdPath>,
83 NI: Idx,
84 Format: InputCapabilities<NI>,
85 Format::GraphInput: TryFrom<InputPath<P>>,
86{
87 csr_layout: CsrLayout,
88 path: P,
89 _idx: PhantomData<NI>,
90 _format: PhantomData<Format>,
91}
92
93/// A builder to create graphs in a type-safe way.
94///
95/// The builder implementation uses different states to allow staged building of
96/// graphs. Each individual state enables stage-specific methods on the builder.
97///
98/// # Examples
99///
100/// Create a directed graph from a vec of edges:
101///
102/// ```
103/// use fso_graph_builder::prelude::*;
104///
105/// let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
106/// .edges(vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
107/// .build();
108///
109/// assert_eq!(graph.node_count(), 4);
110/// ```
111///
112/// Create an undirected graph from a vec of edges:
113///
114/// ```
115/// use fso_graph_builder::prelude::*;
116///
117/// let graph: UndirectedCsrGraph<usize> = GraphBuilder::new()
118/// .edges(vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
119/// .build();
120///
121/// assert_eq!(graph.node_count(), 4);
122/// ```
123pub struct GraphBuilder<State> {
124 state: State,
125}
126
127impl Default for GraphBuilder<Uninitialized> {
128 fn default() -> Self {
129 GraphBuilder::new()
130 }
131}
132
133impl GraphBuilder<Uninitialized> {
134 /// Creates a new builder
135 pub fn new() -> Self {
136 Self {
137 state: Uninitialized {
138 csr_layout: CsrLayout::default(),
139 },
140 }
141 }
142
143 /// Sets the [`CsrLayout`] to use during CSR construction.
144 ///
145 /// # Examples
146 ///
147 /// Store the neighbors sorted:
148 ///
149 /// ```
150 /// use fso_graph_builder::prelude::*;
151 ///
152 /// let graph: UndirectedCsrGraph<usize> = GraphBuilder::new()
153 /// .csr_layout(CsrLayout::Sorted)
154 /// .edges(vec![(0, 7), (0, 3), (0, 3), (0, 1)])
155 /// .build();
156 ///
157 /// assert_eq!(graph.neighbors(0).copied().collect::<Vec<_>>(), &[1, 3, 3, 7]);
158 /// ```
159 ///
160 /// Store the neighbors sorted and deduplicated:
161 ///
162 /// ```
163 /// use fso_graph_builder::prelude::*;
164 ///
165 /// let graph: UndirectedCsrGraph<usize> = GraphBuilder::new()
166 /// .csr_layout(CsrLayout::Deduplicated)
167 /// .edges(vec![(0, 7), (0, 3), (0, 3), (0, 1)])
168 /// .build();
169 ///
170 /// assert_eq!(graph.neighbors(0).copied().collect::<Vec<_>>(), &[1, 3, 7]);
171 /// ```
172 #[must_use]
173 pub fn csr_layout(mut self, csr_layout: CsrLayout) -> Self {
174 self.state.csr_layout = csr_layout;
175 self
176 }
177
178 /// Create a graph from the given edge tuples.
179 ///
180 /// # Example
181 ///
182 /// ```
183 /// use fso_graph_builder::prelude::*;
184 ///
185 /// let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
186 /// .edges(vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
187 /// .build();
188 ///
189 /// assert_eq!(graph.node_count(), 4);
190 /// assert_eq!(graph.edge_count(), 5);
191 /// ```
192 pub fn edges<NI, Edges>(self, edges: Edges) -> GraphBuilder<FromEdges<NI, Edges>>
193 where
194 NI: Idx,
195 Edges: IntoIterator<Item = (NI, NI)>,
196 {
197 GraphBuilder {
198 state: FromEdges {
199 csr_layout: self.state.csr_layout,
200 edges,
201 _node: PhantomData,
202 },
203 }
204 }
205
206 /// Create a graph from the given edge triplets.
207 ///
208 /// # Example
209 ///
210 /// ```
211 /// use fso_graph_builder::prelude::*;
212 ///
213 /// let graph: DirectedCsrGraph<usize, (), f32> = GraphBuilder::new()
214 /// .edges_with_values(vec![(0, 1, 0.1), (0, 2, 0.2), (1, 2, 0.3), (1, 3, 0.4), (2, 3, 0.5)])
215 /// .build();
216 ///
217 /// assert_eq!(graph.node_count(), 4);
218 /// assert_eq!(graph.edge_count(), 5);
219 /// ```
220 pub fn edges_with_values<NI, Edges, EV>(
221 self,
222 edges: Edges,
223 ) -> GraphBuilder<FromEdgesWithValues<NI, Edges, EV>>
224 where
225 NI: Idx,
226 Edges: IntoIterator<Item = (NI, NI, EV)>,
227 {
228 GraphBuilder {
229 state: FromEdgesWithValues {
230 csr_layout: self.state.csr_layout,
231 edges,
232 _node: PhantomData,
233 },
234 }
235 }
236
237 /// Creates a graph using Graph Definition Language (GDL).
238 ///
239 /// Creating graphs from GDL is recommended for small graphs only, e.g.,
240 /// during testing. The graph construction is **not** parallelized.
241 ///
242 /// See [GDL on crates.io](https://crates.io/crates/gdl) for more
243 /// information on how to define graphs using GDL.
244 ///
245 /// # Example
246 ///
247 /// ```
248 /// use fso_graph_builder::prelude::*;
249 ///
250 /// let g: UndirectedCsrGraph<usize> = GraphBuilder::new()
251 /// .gdl_str::<usize, _>("(a)-->(),(a)-->()")
252 /// .build()
253 /// .unwrap();
254 ///
255 /// assert_eq!(g.node_count(), 3);
256 /// assert_eq!(g.edge_count(), 2);
257 /// ```
258 ///
259 /// One can also create weighted graphs using GDL. There needs to be exactly
260 /// one edge property with the same type as specified for the edge value.
261 /// The property key is not relevant.
262 ///
263 /// ```
264 /// use fso_graph_builder::prelude::*;
265 ///
266 /// let g: UndirectedCsrGraph<usize, (), f32> = GraphBuilder::new()
267 /// .csr_layout(CsrLayout::Sorted)
268 /// .gdl_str::<usize, _>("(a)-[{f: 0.42}]->(),(a)-[{f: 13.37}]->()")
269 /// .build()
270 /// .unwrap();
271 ///
272 /// assert_eq!(g.node_count(), 3);
273 /// assert_eq!(g.edge_count(), 2);
274 ///
275 /// let mut neighbors = g.neighbors_with_values(0);
276 /// assert_eq!(neighbors.next(), Some(&Target::new(1, 0.42)));
277 /// assert_eq!(neighbors.next(), Some(&Target::new(2, 13.37)));
278 /// assert_eq!(neighbors.next(), None);
279 /// ```
280 #[cfg(feature = "gdl")]
281 #[cfg_attr(all(feature = "gdl", has_doc_cfg), doc(cfg(feature = "gdl")))]
282 pub fn gdl_str<NI, S>(self, gdl: S) -> GraphBuilder<FromGdlString<NI>>
283 where
284 NI: Idx,
285 S: Into<String>,
286 {
287 GraphBuilder {
288 state: FromGdlString {
289 csr_layout: self.state.csr_layout,
290 gdl: gdl.into(),
291 _node: PhantomData,
292 },
293 }
294 }
295
296 /// Creates a graph from an already constructed GDL graph.
297 ///
298 /// Creating graphs from GDL is recommended for small graphs only, e.g.,
299 /// during testing. The graph construction is **not** parallelized.
300 ///
301 /// See [GDL on crates.io](https://crates.io/crates/gdl) for more
302 /// information on how to define graphs using GDL.
303 ///
304 /// # Example
305 ///
306 /// ```
307 /// use fso_graph_builder::prelude::*;
308 ///
309 /// let gdl_graph = "(a)-->(),(a)-->()".parse::<::gdl::Graph>().unwrap();
310 ///
311 /// let g: DirectedCsrGraph<usize> = GraphBuilder::new()
312 /// .gdl_graph::<usize>(&gdl_graph)
313 /// .build()
314 /// .unwrap();
315 ///
316 /// assert_eq!(g.node_count(), 3);
317 /// assert_eq!(g.edge_count(), 2);
318 ///
319 /// let id_a = gdl_graph.get_node("a").unwrap().id();
320 ///
321 /// assert_eq!(g.out_neighbors(id_a).len(), 2);
322 /// ```
323 #[cfg(feature = "gdl")]
324 #[cfg_attr(all(feature = "gdl", has_doc_cfg), doc(cfg(feature = "gdl")))]
325 pub fn gdl_graph<NI>(self, gdl_graph: &::gdl::Graph) -> GraphBuilder<FromGdlGraph<'_, NI>>
326 where
327 NI: Idx,
328 {
329 GraphBuilder {
330 state: FromGdlGraph {
331 csr_layout: self.state.csr_layout,
332 gdl_graph,
333 _node: PhantomData,
334 },
335 }
336 }
337
338 /// Creates a graph by reading it from the given file format.
339 ///
340 /// # Examples
341 ///
342 /// Read a directed graph from an edge list file:
343 ///
344 /// ```
345 /// use std::path::PathBuf;
346 ///
347 /// use fso_graph_builder::prelude::*;
348 ///
349 /// let path = [env!("CARGO_MANIFEST_DIR"), "resources", "example.el"]
350 /// .iter()
351 /// .collect::<PathBuf>();
352 ///
353 /// let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
354 /// .file_format(EdgeListInput::default())
355 /// .path(path)
356 /// .build()
357 /// .expect("loading failed");
358 ///
359 /// assert_eq!(graph.node_count(), 4);
360 /// assert_eq!(graph.edge_count(), 5);
361 /// ```
362 pub fn file_format<Format, Path, NI>(
363 self,
364 _format: Format,
365 ) -> GraphBuilder<FromInput<NI, Path, Format>>
366 where
367 Path: AsRef<StdPath>,
368 NI: Idx,
369 Format: InputCapabilities<NI>,
370 Format::GraphInput: TryFrom<InputPath<Path>>,
371 {
372 GraphBuilder {
373 state: FromInput {
374 csr_layout: self.state.csr_layout,
375 _idx: PhantomData,
376 _path: PhantomData,
377 _format: PhantomData,
378 },
379 }
380 }
381}
382
383impl<NI, Edges> GraphBuilder<FromEdges<NI, Edges>>
384where
385 NI: Idx,
386 Edges: IntoIterator<Item = (NI, NI)>,
387{
388 pub fn node_values<NV, I>(
389 self,
390 node_values: I,
391 ) -> GraphBuilder<FromEdgeListAndNodeValues<NI, NV, ()>>
392 where
393 I: IntoIterator<Item = NV>,
394 {
395 let edge_list = EdgeList::from(EdgeIterator(self.state.edges));
396 let node_values = node_values.into_iter().collect::<NodeValues<NV>>();
397
398 GraphBuilder {
399 state: FromEdgeListAndNodeValues {
400 csr_layout: self.state.csr_layout,
401 node_values,
402 edge_list,
403 },
404 }
405 }
406
407 /// Build the graph from the given vec of edges.
408 pub fn build<Graph>(self) -> Graph
409 where
410 Graph: From<(EdgeList<NI, ()>, CsrLayout)>,
411 {
412 Graph::from((
413 EdgeList::from(EdgeIterator(self.state.edges)),
414 self.state.csr_layout,
415 ))
416 }
417}
418
419impl<NI, Edges, EV> GraphBuilder<FromEdgesWithValues<NI, Edges, EV>>
420where
421 NI: Idx,
422 EV: Sync,
423 Edges: IntoIterator<Item = (NI, NI, EV)>,
424{
425 pub fn node_values<NV, I>(
426 self,
427 node_values: I,
428 ) -> GraphBuilder<FromEdgeListAndNodeValues<NI, NV, EV>>
429 where
430 I: IntoIterator<Item = NV>,
431 {
432 let edge_list = EdgeList::from(EdgeWithValueIterator(self.state.edges));
433 let node_values = node_values.into_iter().collect::<NodeValues<NV>>();
434
435 GraphBuilder {
436 state: FromEdgeListAndNodeValues {
437 csr_layout: self.state.csr_layout,
438 node_values,
439 edge_list,
440 },
441 }
442 }
443
444 /// Build the graph from the given vec of edges.
445 pub fn build<Graph>(self) -> Graph
446 where
447 Graph: From<(EdgeList<NI, EV>, CsrLayout)>,
448 {
449 Graph::from((
450 EdgeList::new(self.state.edges.into_iter().collect()),
451 self.state.csr_layout,
452 ))
453 }
454}
455
456impl<NI: Idx, NV, EV> GraphBuilder<FromEdgeListAndNodeValues<NI, NV, EV>> {
457 pub fn build<Graph>(self) -> Graph
458 where
459 Graph: From<(NodeValues<NV>, EdgeList<NI, EV>, CsrLayout)>,
460 {
461 Graph::from((
462 self.state.node_values,
463 self.state.edge_list,
464 self.state.csr_layout,
465 ))
466 }
467}
468
469#[cfg(feature = "gdl")]
470#[cfg_attr(all(feature = "gdl", has_doc_cfg), doc(cfg(feature = "gdl")))]
471impl<NI> GraphBuilder<FromGdlString<NI>>
472where
473 NI: Idx,
474{
475 /// Builds the graph from the given GDL string.
476 pub fn build<Graph>(self) -> Result<Graph, Error>
477 where
478 Graph: From<(gdl::Graph, CsrLayout)>,
479 {
480 let gdl_graph = self.state.gdl.parse::<gdl::Graph>()?;
481 let graph = Graph::from((gdl_graph, self.state.csr_layout));
482 Ok(graph)
483 }
484}
485
486#[cfg(feature = "gdl")]
487#[cfg_attr(all(feature = "gdl", has_doc_cfg), doc(cfg(feature = "gdl")))]
488impl<'a, NI> GraphBuilder<FromGdlGraph<'a, NI>>
489where
490 NI: Idx,
491{
492 /// Build the graph from the given GDL graph.
493 pub fn build<Graph>(self) -> Result<Graph, Error>
494 where
495 Graph: From<(&'a gdl::Graph, CsrLayout)>,
496 {
497 Ok(Graph::from((self.state.gdl_graph, self.state.csr_layout)))
498 }
499}
500
501impl<NI, Path, Format> GraphBuilder<FromInput<NI, Path, Format>>
502where
503 Path: AsRef<StdPath>,
504 NI: Idx,
505 Format: InputCapabilities<NI>,
506 Format::GraphInput: TryFrom<InputPath<Path>>,
507{
508 /// Set the location where the graph is stored.
509 pub fn path(self, path: Path) -> GraphBuilder<FromPath<NI, Path, Format>> {
510 GraphBuilder {
511 state: FromPath {
512 csr_layout: self.state.csr_layout,
513 path,
514 _idx: PhantomData,
515 _format: PhantomData,
516 },
517 }
518 }
519}
520
521impl<NI, Path, Format> GraphBuilder<FromPath<NI, Path, Format>>
522where
523 Path: AsRef<StdPath>,
524 NI: Idx,
525 Format: InputCapabilities<NI>,
526 Format::GraphInput: TryFrom<InputPath<Path>>,
527 crate::Error: From<<Format::GraphInput as TryFrom<InputPath<Path>>>::Error>,
528{
529 /// Build the graph from the given input format and path.
530 pub fn build<Graph>(self) -> Result<Graph, Error>
531 where
532 Graph: TryFrom<(Format::GraphInput, CsrLayout)>,
533 crate::Error: From<Graph::Error>,
534 {
535 let input = Format::GraphInput::try_from(InputPath(self.state.path))?;
536 let graph = Graph::try_from((input, self.state.csr_layout))?;
537
538 Ok(graph)
539 }
540}