1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
impl FixedGraphBuilder {
#[must_use]
pub fn new(config: GraphConfig) -> Self {
Self {
max_nodes: config.max_nodes,
max_edges: config.max_edges,
namer: SemanticNamer::new(),
}
}
/// Sets the maximum number of nodes in the output graph
///
/// # Examples
///
/// ```rust
/// use pmat::services::fixed_graph_builder::{FixedGraphBuilder, GraphConfig, GroupingStrategy};
///
/// let config = GraphConfig {
/// max_nodes: 100,
/// max_edges: 500,
/// grouping: GroupingStrategy::Module,
/// };
///
/// let builder = FixedGraphBuilder::new(config)
/// .with_max_nodes(50);
/// // Builder will now limit to 50 nodes instead of 100
/// ```
#[must_use]
pub fn with_max_nodes(mut self, max_nodes: usize) -> Self {
self.max_nodes = max_nodes;
self
}
/// Sets the maximum number of edges in the output graph
///
/// # Examples
///
/// ```rust
/// use pmat::services::fixed_graph_builder::{FixedGraphBuilder, GraphConfig, GroupingStrategy};
///
/// let config = GraphConfig {
/// max_nodes: 100,
/// max_edges: 500,
/// grouping: GroupingStrategy::Module,
/// };
///
/// let builder = FixedGraphBuilder::new(config)
/// .with_max_edges(200);
/// // Builder will now limit to 200 edges instead of 500
/// ```
#[must_use]
pub fn with_max_edges(mut self, max_edges: usize) -> Self {
self.max_edges = max_edges;
self
}
/// Build a fixed-size graph from a dependency graph
pub fn build(&self, graph: &DependencyGraph) -> Result<FixedGraph> {
// 1. Group nodes by module
let groups = self.group_by_module(graph);
// 2. Calculate PageRank scores
let scores = self.calculate_pagerank(graph, &groups);
// 3. Select top N nodes
let selected_nodes = self.select_top_nodes(scores, &groups);
// 4. Build graph with edge budget
self.build_with_budget(selected_nodes, graph)
}
/// Group nodes by module path
fn group_by_module(&self, graph: &DependencyGraph) -> HashMap<String, Vec<String>> {
let mut groups: HashMap<String, Vec<String>> = HashMap::new();
for (node_id, node) in &graph.nodes {
let module_name = self.get_module_name(node);
groups.entry(module_name).or_default().push(node_id.clone());
}
groups
}
/// Get the module name for a node
fn get_module_name(&self, node: &NodeInfo) -> String {
// Extract module from file path
if !node.file_path.is_empty() {
let parts: Vec<&str> = node.file_path.split('/').collect();
if parts.len() > 1 {
// For src/services/foo.rs -> services
// For src/models/bar.rs -> models
if let Some(module) = parts.get(1) {
return (*module).to_string();
}
}
}
// Fallback to node type
match node.node_type {
NodeType::Module => "modules".to_string(),
NodeType::Function => "functions".to_string(),
NodeType::Class => "classes".to_string(),
NodeType::Trait => "traits".to_string(),
NodeType::Interface => "interfaces".to_string(),
}
}
/// Calculate `PageRank` scores for nodes
fn calculate_pagerank(
&self,
graph: &DependencyGraph,
groups: &HashMap<String, Vec<String>>,
) -> HashMap<String, f64> {
let damping_factor = 0.85;
let iterations = 10;
let num_nodes = graph.nodes.len() as f64;
// Initialize scores
let mut scores: HashMap<String, f64> = HashMap::new();
for node_id in graph.nodes.keys() {
scores.insert(node_id.clone(), 1.0 / num_nodes);
}
// Build adjacency lists
let mut incoming: HashMap<String, Vec<String>> = HashMap::new();
let mut outgoing_count: HashMap<String, usize> = HashMap::new();
for edge in &graph.edges {
incoming
.entry(edge.to.clone())
.or_default()
.push(edge.from.clone());
*outgoing_count.entry(edge.from.clone()).or_default() += 1;
}
// PageRank iterations
for _ in 0..iterations {
let mut new_scores = HashMap::new();
for node_id in graph.nodes.keys() {
let mut rank = (1.0 - damping_factor) / num_nodes;
if let Some(incoming_nodes) = incoming.get(node_id) {
for incoming_node in incoming_nodes {
if let (Some(&score), Some(&count)) =
(scores.get(incoming_node), outgoing_count.get(incoming_node))
{
rank += damping_factor * score / count as f64;
}
}
}
new_scores.insert(node_id.clone(), rank);
}
scores = new_scores;
}
// Aggregate scores by group
let mut group_scores: HashMap<String, f64> = HashMap::new();
for (group_name, node_ids) in groups {
let group_score: f64 = node_ids.iter().filter_map(|id| scores.get(id)).sum();
group_scores.insert(group_name.clone(), group_score);
}
group_scores
}
/// Select top nodes based on `PageRank` scores
fn select_top_nodes(
&self,
scores: HashMap<String, f64>,
groups: &HashMap<String, Vec<String>>,
) -> Vec<String> {
// Sort groups by score
let mut sorted_groups: Vec<(String, f64)> = scores.into_iter().collect();
sorted_groups.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
// Select top groups up to max_nodes
let mut selected_nodes = Vec::new();
let mut node_count = 0;
for (group_name, _score) in sorted_groups {
if let Some(node_ids) = groups.get(&group_name) {
// Add all nodes from this group if we have room
if node_count + node_ids.len() <= self.max_nodes {
selected_nodes.extend(node_ids.clone());
node_count += node_ids.len();
} else {
// Add as many as we can
let remaining = self.max_nodes - node_count;
selected_nodes.extend(node_ids.iter().take(remaining).cloned());
break;
}
}
}
selected_nodes
}
/// Build the final graph with edge budget
fn build_with_budget(
&self,
selected_nodes: Vec<String>,
original_graph: &DependencyGraph,
) -> Result<FixedGraph> {
let selected_set: HashSet<_> = selected_nodes.iter().cloned().collect();
let mut nodes = BTreeMap::new();
let mut edges = Vec::new();
// Add selected nodes with semantic names
for node_id in &selected_nodes {
if let Some(node) = original_graph.nodes.get(node_id) {
let semantic_name = self.namer.get_semantic_name(node_id, node);
let fixed_node = FixedNode {
id: node_id.clone(),
display_name: semantic_name.clone(),
node_type: node.node_type.clone(),
complexity: u64::from(node.complexity),
};
nodes.insert(semantic_name, fixed_node);
}
}
// Add edges between selected nodes
let mut edge_count = 0;
for edge in &original_graph.edges {
if selected_set.contains(&edge.from) && selected_set.contains(&edge.to) {
edges.push(edge.clone());
edge_count += 1;
if edge_count >= self.max_edges {
break;
}
}
}
Ok(FixedGraph { nodes, edges })
}
}