scirs2_graph/base/
mod.rs

1//! Base graph structures and operations
2//!
3//! This module provides the core graph data structures and interfaces
4//! for representing and working with graphs.
5
6pub mod graph;
7pub mod types;
8
9// Re-export main types
10pub use graph::Graph;
11pub use types::{Edge, EdgeWeight, Node};
12
13// Re-export petgraph IndexType
14pub use petgraph::graph::IndexType;
15
16// Legacy imports for backward compatibility - include remaining graph types here
17use petgraph::graph::{Graph as PetGraph, NodeIndex};
18use petgraph::visit::EdgeRef;
19use petgraph::{Directed, Undirected};
20use scirs2_core::ndarray::{Array1, Array2};
21use std::collections::HashMap;
22use std::fmt::Debug;
23use std::hash::Hash;
24
25use crate::error::{GraphError, Result};
26
27/// A directed graph structure
28pub struct DiGraph<N: Node, E: EdgeWeight, Ix: IndexType = u32> {
29    graph: PetGraph<N, E, Directed, Ix>,
30    node_indices: HashMap<N, NodeIndex<Ix>>,
31}
32
33/// A multigraph structure (allows multiple edges between same nodes)
34pub struct MultiGraph<N: Node, E: EdgeWeight, Ix: IndexType = u32> {
35    graph: PetGraph<N, Vec<E>, Undirected, Ix>,
36    node_indices: HashMap<N, NodeIndex<Ix>>,
37}
38
39/// A directed multigraph structure
40pub struct MultiDiGraph<N: Node, E: EdgeWeight, Ix: IndexType = u32> {
41    graph: PetGraph<N, Vec<E>, Directed, Ix>,
42    node_indices: HashMap<N, NodeIndex<Ix>>,
43}
44
45/// A bipartite graph structure
46pub struct BipartiteGraph<N: Node, E: EdgeWeight, Ix: IndexType = u32> {
47    graph: PetGraph<N, E, Undirected, Ix>,
48    node_indices: HashMap<N, NodeIndex<Ix>>,
49    left_nodes: std::collections::HashSet<N>,
50    right_nodes: std::collections::HashSet<N>,
51}
52
53/// A hypergraph structure
54pub struct Hypergraph<N: Node, E: EdgeWeight, Ix: IndexType = u32> {
55    nodes: HashMap<N, NodeIndex<Ix>>,
56    hyperedges: Vec<Hyperedge<N, E>>,
57    _phantom: std::marker::PhantomData<Ix>,
58}
59
60/// Represents a hyperedge in a hypergraph
61#[derive(Debug, Clone)]
62pub struct Hyperedge<N: Node, E: EdgeWeight> {
63    /// Nodes connected by this hyperedge
64    pub nodes: Vec<N>,
65    /// Weight of the hyperedge
66    pub weight: E,
67    /// Unique identifier for the hyperedge
68    pub id: usize,
69}
70
71// Simplified implementations for backward compatibility
72impl<N: Node + std::fmt::Debug, E: EdgeWeight, Ix: IndexType> Default for DiGraph<N, E, Ix> {
73    fn default() -> Self {
74        Self::new()
75    }
76}
77
78impl<N: Node + std::fmt::Debug, E: EdgeWeight, Ix: IndexType> DiGraph<N, E, Ix> {
79    /// Create a new empty directed graph
80    pub fn new() -> Self {
81        DiGraph {
82            graph: PetGraph::default(),
83            node_indices: HashMap::new(),
84        }
85    }
86
87    /// Add a node to the graph
88    pub fn add_node(&mut self, node: N) -> NodeIndex<Ix> {
89        if let Some(idx) = self.node_indices.get(&node) {
90            return *idx;
91        }
92
93        let idx = self.graph.add_node(node.clone());
94        self.node_indices.insert(node, idx);
95        idx
96    }
97
98    /// Add a directed edge from source to target with a given weight
99    pub fn add_edge(&mut self, source: N, target: N, weight: E) -> Result<()> {
100        let source_idx = self.add_node(source);
101        let target_idx = self.add_node(target);
102
103        self.graph.add_edge(source_idx, target_idx, weight);
104        Ok(())
105    }
106
107    /// Get all nodes in the graph
108    pub fn nodes(&self) -> Vec<&N> {
109        self.graph.node_weights().collect()
110    }
111
112    /// Number of nodes in the graph
113    pub fn node_count(&self) -> usize {
114        self.graph.node_count()
115    }
116
117    /// Number of edges in the graph
118    pub fn edge_count(&self) -> usize {
119        self.graph.edge_count()
120    }
121
122    /// Check if the graph contains a specific node
123    pub fn contains_node(&self, node: &N) -> bool {
124        self.node_indices.contains_key(node)
125    }
126
127    /// Check if the graph has a specific node (alias for contains_node)
128    pub fn has_node(&self, node: &N) -> bool {
129        self.contains_node(node)
130    }
131
132    /// Get the internal petgraph structure for more advanced operations
133    pub fn inner(&self) -> &PetGraph<N, E, Directed, Ix> {
134        &self.graph
135    }
136
137    /// Get neighbors of a node
138    pub fn neighbors(&self, node: &N) -> Result<Vec<N>>
139    where
140        N: Clone,
141    {
142        if let Some(&idx) = self.node_indices.get(node) {
143            let neighbors: Vec<N> = self
144                .graph
145                .neighbors(idx)
146                .map(|neighbor_idx| self.graph[neighbor_idx].clone())
147                .collect();
148            Ok(neighbors)
149        } else {
150            Err(GraphError::node_not_found("unknown node"))
151        }
152    }
153
154    /// Get successors (outgoing neighbors) of a node
155    pub fn successors(&self, node: &N) -> Result<Vec<N>>
156    where
157        N: Clone,
158    {
159        if let Some(&idx) = self.node_indices.get(node) {
160            let successors: Vec<N> = self
161                .graph
162                .neighbors_directed(idx, petgraph::Direction::Outgoing)
163                .map(|neighbor_idx| self.graph[neighbor_idx].clone())
164                .collect();
165            Ok(successors)
166        } else {
167            Err(GraphError::node_not_found("unknown node"))
168        }
169    }
170
171    /// Get predecessors (incoming neighbors) of a node
172    pub fn predecessors(&self, node: &N) -> Result<Vec<N>>
173    where
174        N: Clone,
175    {
176        if let Some(&idx) = self.node_indices.get(node) {
177            let predecessors: Vec<N> = self
178                .graph
179                .neighbors_directed(idx, petgraph::Direction::Incoming)
180                .map(|neighbor_idx| self.graph[neighbor_idx].clone())
181                .collect();
182            Ok(predecessors)
183        } else {
184            Err(GraphError::node_not_found("unknown node"))
185        }
186    }
187
188    /// Get the weight of an edge between two nodes
189    pub fn edge_weight(&self, source: &N, target: &N) -> Result<E>
190    where
191        E: Clone,
192    {
193        if let (Some(&src_idx), Some(&tgt_idx)) =
194            (self.node_indices.get(source), self.node_indices.get(target))
195        {
196            if let Some(edge_ref) = self.graph.find_edge(src_idx, tgt_idx) {
197                Ok(self.graph[edge_ref].clone())
198            } else {
199                Err(GraphError::edge_not_found("unknown", "unknown"))
200            }
201        } else {
202            Err(GraphError::node_not_found("unknown node"))
203        }
204    }
205
206    /// Get all edges in the graph
207    pub fn edges(&self) -> Vec<Edge<N, E>>
208    where
209        N: Clone,
210        E: Clone,
211    {
212        let mut result = Vec::new();
213        let node_map: HashMap<NodeIndex<Ix>, &N> = self
214            .graph
215            .node_indices()
216            .map(|idx| (idx, self.graph.node_weight(idx).unwrap()))
217            .collect();
218
219        for edge in self.graph.edge_references() {
220            let source = node_map[&edge.source()].clone();
221            let target = node_map[&edge.target()].clone();
222            let weight = edge.weight().clone();
223
224            result.push(Edge {
225                source,
226                target,
227                weight,
228            });
229        }
230
231        result
232    }
233
234    /// Check if an edge exists between two nodes
235    pub fn has_edge(&self, source: &N, target: &N) -> bool {
236        if let (Some(&src_idx), Some(&tgt_idx)) =
237            (self.node_indices.get(source), self.node_indices.get(target))
238        {
239            self.graph.contains_edge(src_idx, tgt_idx)
240        } else {
241            false
242        }
243    }
244
245    /// Get the degree of a node (total number of incident edges)
246    pub fn degree(&self, node: &N) -> usize {
247        if let Some(idx) = self.node_indices.get(node) {
248            self.graph.neighbors(*idx).count()
249        } else {
250            0
251        }
252    }
253
254    /// Get the node index for a specific node
255    pub fn node_index(&self, node: &N) -> Option<NodeIndex<Ix>> {
256        self.node_indices.get(node).copied()
257    }
258
259    /// Get the adjacency matrix of the graph
260    pub fn adjacency_matrix(&self) -> Array2<f64>
261    where
262        E: Clone + Into<f64>,
263    {
264        let n = self.node_count();
265        let mut matrix = Array2::zeros((n, n));
266
267        // Create mapping from NodeIndex to matrix index
268        let mut node_to_idx = HashMap::new();
269        for (i, node_idx) in self.graph.node_indices().enumerate() {
270            node_to_idx.insert(node_idx, i);
271        }
272
273        // Fill the adjacency matrix
274        for edge in self.graph.edge_references() {
275            let src_idx = node_to_idx[&edge.source()];
276            let tgt_idx = node_to_idx[&edge.target()];
277            let weight: f64 = edge.weight().clone().into();
278            matrix[[src_idx, tgt_idx]] = weight;
279        }
280
281        matrix
282    }
283
284    /// Get the out-degree vector (number of outgoing edges for each node)
285    pub fn out_degree_vector(&self) -> Array1<usize> {
286        let n = self.node_count();
287        let mut degrees = Array1::zeros(n);
288
289        // Create mapping from NodeIndex to array index
290        let mut node_to_idx = HashMap::new();
291        for (i, node_idx) in self.graph.node_indices().enumerate() {
292            node_to_idx.insert(node_idx, i);
293        }
294
295        // Count out-degrees
296        for node_idx in self.graph.node_indices() {
297            let out_degree = self
298                .graph
299                .neighbors_directed(node_idx, petgraph::Direction::Outgoing)
300                .count();
301            let idx = node_to_idx[&node_idx];
302            degrees[idx] = out_degree;
303        }
304
305        degrees
306    }
307
308    /// Get the in-degree vector (number of incoming edges for each node)
309    pub fn in_degree_vector(&self) -> Array1<usize> {
310        let n = self.node_count();
311        let mut degrees = Array1::zeros(n);
312
313        // Create mapping from NodeIndex to array index
314        let mut node_to_idx = HashMap::new();
315        for (i, node_idx) in self.graph.node_indices().enumerate() {
316            node_to_idx.insert(node_idx, i);
317        }
318
319        // Count in-degrees
320        for node_idx in self.graph.node_indices() {
321            let in_degree = self
322                .graph
323                .neighbors_directed(node_idx, petgraph::Direction::Incoming)
324                .count();
325            let idx = node_to_idx[&node_idx];
326            degrees[idx] = in_degree;
327        }
328
329        degrees
330    }
331}
332
333// Placeholder implementations for other graph types to maintain compilation
334impl<N: Node + std::fmt::Debug, E: EdgeWeight, Ix: IndexType> Default for MultiGraph<N, E, Ix> {
335    fn default() -> Self {
336        MultiGraph {
337            graph: PetGraph::default(),
338            node_indices: HashMap::new(),
339        }
340    }
341}
342
343impl<N: Node + std::fmt::Debug, E: EdgeWeight, Ix: IndexType> Default for MultiDiGraph<N, E, Ix> {
344    fn default() -> Self {
345        MultiDiGraph {
346            graph: PetGraph::default(),
347            node_indices: HashMap::new(),
348        }
349    }
350}
351
352impl<N: Node + std::fmt::Debug, E: EdgeWeight, Ix: IndexType> Default for BipartiteGraph<N, E, Ix> {
353    fn default() -> Self {
354        BipartiteGraph {
355            graph: PetGraph::default(),
356            node_indices: HashMap::new(),
357            left_nodes: std::collections::HashSet::new(),
358            right_nodes: std::collections::HashSet::new(),
359        }
360    }
361}
362
363impl<N: Node + std::fmt::Debug, E: EdgeWeight, Ix: IndexType> Hypergraph<N, E, Ix> {
364    /// Create a new empty hypergraph
365    pub fn new() -> Self {
366        Hypergraph {
367            nodes: HashMap::new(),
368            hyperedges: Vec::new(),
369            _phantom: std::marker::PhantomData,
370        }
371    }
372
373    /// Get all nodes in the hypergraph
374    pub fn nodes(&self) -> impl Iterator<Item = &N> {
375        self.nodes.keys()
376    }
377
378    /// Get all hyperedges in the hypergraph
379    pub fn hyperedges(&self) -> &Vec<Hyperedge<N, E>> {
380        &self.hyperedges
381    }
382
383    /// Check if the hypergraph has a node
384    pub fn has_node(&self, node: &N) -> bool {
385        self.nodes.contains_key(node)
386    }
387
388    /// Add a node to the hypergraph
389    pub fn add_node(&mut self, node: N) -> NodeIndex<Ix> {
390        if let Some(&idx) = self.nodes.get(&node) {
391            return idx;
392        }
393
394        let idx = NodeIndex::new(self.nodes.len());
395        self.nodes.insert(node, idx);
396        idx
397    }
398
399    /// Add a hyperedge from a vector of nodes
400    pub fn add_hyperedge_from_vec(&mut self, nodes: Vec<N>, weight: E) -> Result<usize>
401    where
402        N: Clone,
403    {
404        // Add all nodes to the hypergraph
405        for node in &nodes {
406            self.add_node(node.clone());
407        }
408
409        let id = self.hyperedges.len();
410        self.hyperedges.push(Hyperedge { nodes, weight, id });
411        Ok(id)
412    }
413
414    /// Add a hyperedge
415    pub fn add_hyperedge(&mut self, nodes: Vec<N>, weight: E) -> Result<usize>
416    where
417        N: Clone,
418    {
419        self.add_hyperedge_from_vec(nodes, weight)
420    }
421
422    /// Check if two nodes are connected through any hyperedge
423    pub fn are_connected(&self, source: &N, target: &N) -> bool
424    where
425        N: PartialEq,
426    {
427        for hyperedge in &self.hyperedges {
428            if hyperedge.nodes.contains(source) && hyperedge.nodes.contains(target) {
429                return true;
430            }
431        }
432        false
433    }
434
435    /// Get hyperedges that connect two nodes
436    pub fn connecting_hyperedges(&self, source: &N, target: &N) -> Vec<&Hyperedge<N, E>>
437    where
438        N: PartialEq,
439    {
440        self.hyperedges
441            .iter()
442            .filter(|hyperedge| {
443                hyperedge.nodes.contains(source) && hyperedge.nodes.contains(target)
444            })
445            .collect()
446    }
447
448    /// Get all hyperedges containing a specific node
449    pub fn hyperedges_containing_node(&self, node: &N) -> Vec<&Hyperedge<N, E>>
450    where
451        N: PartialEq,
452    {
453        self.hyperedges
454            .iter()
455            .filter(|hyperedge| hyperedge.nodes.contains(node))
456            .collect()
457    }
458
459    /// Get neighbors of a node (all nodes connected through hyperedges)
460    pub fn neighbors(&self, node: &N) -> Vec<N>
461    where
462        N: Clone + PartialEq,
463    {
464        let mut neighbors = std::collections::HashSet::new();
465
466        for hyperedge in &self.hyperedges {
467            if hyperedge.nodes.contains(node) {
468                for neighbor in &hyperedge.nodes {
469                    if neighbor != node {
470                        neighbors.insert(neighbor.clone());
471                    }
472                }
473            }
474        }
475
476        neighbors.into_iter().collect()
477    }
478
479    /// Convert hypergraph to a regular graph (2-section)
480    pub fn to_graph(&self) -> Graph<N, E, Ix>
481    where
482        N: Clone,
483        E: Clone + Default,
484    {
485        let mut graph = Graph::new();
486
487        // Add all nodes
488        for node in self.nodes() {
489            graph.add_node(node.clone());
490        }
491
492        // Add edges between nodes that are in the same hyperedge
493        for hyperedge in &self.hyperedges {
494            for i in 0..hyperedge.nodes.len() {
495                for j in (i + 1)..hyperedge.nodes.len() {
496                    let _ = graph.add_edge(
497                        hyperedge.nodes[i].clone(),
498                        hyperedge.nodes[j].clone(),
499                        hyperedge.weight.clone(),
500                    );
501                }
502            }
503        }
504
505        graph
506    }
507
508    /// Get the number of nodes in the hypergraph
509    pub fn node_count(&self) -> usize {
510        self.nodes.len()
511    }
512
513    /// Get the number of hyperedges in the hypergraph
514    pub fn hyperedge_count(&self) -> usize {
515        self.hyperedges.len()
516    }
517
518    /// Get the degree of a node (number of hyperedges it belongs to)
519    pub fn degree(&self, node: &N) -> usize
520    where
521        N: PartialEq,
522    {
523        self.hyperedges
524            .iter()
525            .filter(|hyperedge| hyperedge.nodes.contains(node))
526            .count()
527    }
528
529    /// Remove a hyperedge by its ID
530    pub fn remove_hyperedge(&mut self, hyperedge_id: usize) -> Result<Hyperedge<N, E>>
531    where
532        N: Clone,
533        E: Clone,
534    {
535        if hyperedge_id < self.hyperedges.len() {
536            Ok(self.hyperedges.remove(hyperedge_id))
537        } else {
538            Err(GraphError::Other("Hyperedge ID out of bounds".to_string()))
539        }
540    }
541
542    /// Get the incidence matrix of the hypergraph
543    /// Returns a matrix where rows represent nodes and columns represent hyperedges
544    /// A value of 1.0 indicates the node is in the hyperedge, 0.0 otherwise
545    pub fn incidence_matrix(&self) -> Vec<Vec<f64>>
546    where
547        N: Clone + PartialEq,
548    {
549        let nodes: Vec<N> = self.nodes().cloned().collect();
550        let mut matrix = vec![vec![0.0; self.hyperedges.len()]; nodes.len()];
551
552        for (edge_idx, hyperedge) in self.hyperedges.iter().enumerate() {
553            for node in &hyperedge.nodes {
554                if let Some(node_idx) = nodes.iter().position(|n| n == node) {
555                    matrix[node_idx][edge_idx] = 1.0;
556                }
557            }
558        }
559
560        matrix
561    }
562
563    /// Find maximal cliques in the hypergraph
564    /// This is a simplified implementation that finds connected components
565    /// A more sophisticated algorithm would be needed for true maximal cliques
566    pub fn maximal_cliques(&self) -> Vec<Vec<N>>
567    where
568        N: Clone + PartialEq,
569    {
570        let mut cliques = Vec::new();
571        let mut visited_nodes = std::collections::HashSet::new();
572
573        for hyperedge in &self.hyperedges {
574            let mut clique = Vec::new();
575            for node in &hyperedge.nodes {
576                if !visited_nodes.contains(node) {
577                    clique.push(node.clone());
578                    visited_nodes.insert(node.clone());
579                }
580            }
581            if !clique.is_empty() {
582                cliques.push(clique);
583            }
584        }
585
586        cliques
587    }
588
589    /// Get statistics about hyperedge sizes
590    /// Returns (min_size, max_size, avg_size)
591    pub fn hyperedge_size_stats(&self) -> (usize, usize, f64) {
592        if self.hyperedges.is_empty() {
593            return (0, 0, 0.0);
594        }
595
596        let sizes: Vec<usize> = self.hyperedges.iter().map(|e| e.nodes.len()).collect();
597        let min_size = *sizes.iter().min().unwrap_or(&0);
598        let max_size = *sizes.iter().max().unwrap_or(&0);
599        let avg_size = sizes.iter().sum::<usize>() as f64 / sizes.len() as f64;
600
601        (min_size, max_size, avg_size)
602    }
603
604    /// Check if the hypergraph is uniform (all hyperedges have the same size)
605    pub fn is_uniform(&self) -> bool {
606        if self.hyperedges.is_empty() {
607            return true;
608        }
609
610        let first_size = self.hyperedges[0].nodes.len();
611        self.hyperedges.iter().all(|e| e.nodes.len() == first_size)
612    }
613}
614
615impl<N: Node + std::fmt::Debug, E: EdgeWeight, Ix: IndexType> Default for Hypergraph<N, E, Ix> {
616    fn default() -> Self {
617        Self::new()
618    }
619}
scirs2_graph/base/mod.rs

scirs2_graph/base/
mod.rs
