use std::collections::{HashMap, HashSet};
use crate::workers::crawl::ScoringContext;
use crate::workers::crawl::UrlScorer;
#[derive(Debug, Clone, Hash, Eq, PartialEq, Serialize, Deserialize)]
pub enum EntityType {
Person,
Organization,
Location,
Product,
Event,
Concept,
Custom(String),
}
impl EntityType {
pub fn label(&self) -> &str {
match self {
EntityType::Person => "person",
EntityType::Organization => "organization",
EntityType::Location => "location",
EntityType::Product => "product",
EntityType::Event => "event",
EntityType::Concept => "concept",
EntityType::Custom(s) => s.as_str(),
}
}
}
#[derive(Debug, Clone, Hash, Eq, PartialEq, Serialize, Deserialize)]
pub enum RelationType {
WorksAt,
LocatedIn,
PartOf,
RelatedTo,
CreatedBy,
Custom(String),
}
impl RelationType {
pub fn label(&self) -> &str {
match self {
RelationType::WorksAt => "works_at",
RelationType::LocatedIn => "located_in",
RelationType::PartOf => "part_of",
RelationType::RelatedTo => "related_to",
RelationType::CreatedBy => "created_by",
RelationType::Custom(s) => s.as_str(),
}
}
}
use serde::{Deserialize, Serialize};
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Entity {
pub id: String,
pub entity_type: EntityType,
pub name: String,
pub source_urls: HashSet<String>,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Relation {
pub source_id: String,
pub target_id: String,
pub relation_type: RelationType,
pub source_urls: HashSet<String>,
}
#[derive(Debug, Clone)]
pub struct StructuralHole {
pub kind: HoleKind,
pub adjacent_entities: Vec<String>,
pub suggested_url_patterns: Vec<String>,
}
#[derive(Debug, Clone)]
pub enum HoleKind {
MissingEntityType(String),
MissingRelation {
entity_a: String,
entity_b: String,
relation_type: String,
},
UnderrepresentedType {
entity_type: String,
current_count: usize,
expected_min: usize,
},
}
pub struct KnowledgeGraphAccumulator {
entities: HashMap<String, Entity>,
relations: Vec<Relation>,
type_counts: HashMap<String, usize>,
known_entity_types: HashSet<String>,
known_relation_types: HashSet<String>,
crawled_urls: HashSet<String>,
}
impl KnowledgeGraphAccumulator {
pub fn new() -> Self {
Self {
entities: HashMap::new(),
relations: Vec::new(),
type_counts: HashMap::new(),
known_entity_types: HashSet::new(),
known_relation_types: HashSet::new(),
crawled_urls: HashSet::new(),
}
}
pub fn register_entity_type(&mut self, type_label: &str) {
self.known_entity_types.insert(type_label.to_string());
}
pub fn register_relation_type(&mut self, type_label: &str) {
self.known_relation_types.insert(type_label.to_string());
}
pub fn add_entity(&mut self, id: &str, entity_type: EntityType, name: &str, source_url: &str) {
self.crawled_urls.insert(source_url.to_string());
let entry = self
.entities
.entry(id.to_string())
.or_insert_with(|| Entity {
id: id.to_string(),
entity_type: entity_type.clone(),
name: name.to_string(),
source_urls: HashSet::new(),
});
entry.source_urls.insert(source_url.to_string());
if entry.source_urls.len() == 1 {
let count = self
.type_counts
.entry(entity_type.label().to_string())
.or_insert(0);
*count += 1;
}
}
pub fn add_relation(
&mut self,
source_id: &str,
target_id: &str,
relation_type: RelationType,
source_url: &str,
) {
self.crawled_urls.insert(source_url.to_string());
let exists = self.relations.iter().any(|r| {
r.source_id == source_id
&& r.target_id == target_id
&& r.relation_type.label() == relation_type.label()
});
if exists {
if let Some(r) = self.relations.iter_mut().find(|r| {
r.source_id == source_id
&& r.target_id == target_id
&& r.relation_type.label() == relation_type.label()
}) {
r.source_urls.insert(source_url.to_string());
}
} else {
let mut source_urls = HashSet::new();
source_urls.insert(source_url.to_string());
self.relations.push(Relation {
source_id: source_id.to_string(),
target_id: target_id.to_string(),
relation_type,
source_urls,
});
}
}
pub fn find_structural_holes(&self) -> Vec<StructuralHole> {
let mut holes = Vec::new();
self.push_missing_entity_type_holes(&mut holes);
self.push_underrepresented_type_holes(&mut holes);
self.push_missing_relation_holes(&mut holes);
holes
}
fn push_missing_entity_type_holes(&self, holes: &mut Vec<StructuralHole>) {
for type_label in &self.known_entity_types {
if !self.type_counts.contains_key(type_label) {
holes.push(StructuralHole {
kind: HoleKind::MissingEntityType(type_label.clone()),
adjacent_entities: self.get_all_entity_ids(),
suggested_url_patterns: vec![format!("**/{}/**", type_label)],
});
}
}
}
fn push_underrepresented_type_holes(&self, holes: &mut Vec<StructuralHole>) {
let expected_min = 2;
for (type_label, &count) in &self.type_counts {
if count < expected_min {
holes.push(StructuralHole {
kind: HoleKind::UnderrepresentedType {
entity_type: type_label.clone(),
current_count: count,
expected_min,
},
adjacent_entities: self.get_entity_ids_by_type(type_label),
suggested_url_patterns: vec![format!("**/{}/**", type_label)],
});
}
}
}
fn push_missing_relation_holes(&self, holes: &mut Vec<StructuralHole>) {
for rel_type in &self.known_relation_types {
let has_any = self
.relations
.iter()
.any(|r| r.relation_type.label() == rel_type);
if !has_any {
let entity_ids: Vec<String> = self.entities.keys().cloned().collect();
if entity_ids.len() >= 2 {
holes.push(StructuralHole {
kind: HoleKind::MissingRelation {
entity_a: entity_ids[0].clone(),
entity_b: entity_ids[1].clone(),
relation_type: rel_type.clone(),
},
adjacent_entities: entity_ids,
suggested_url_patterns: vec![format!("**/{}/**", rel_type)],
});
}
}
}
}
pub fn estimate_coverage(&self) -> f64 {
let s_obs = self.type_counts.len() as f64;
if s_obs == 0.0 {
return 1.0; }
let f1 = self.type_counts.values().filter(|&&c| c == 1).count() as f64;
let f2 = self.type_counts.values().filter(|&&c| c == 2).count() as f64;
let s_est = if f2 > 0.0 {
s_obs + (f1 * f1) / (2.0 * f2)
} else if f1 > 0.0 {
s_obs + (f1 * (f1 - 1.0)) / 2.0
} else {
s_obs
};
let coverage = s_obs / s_est;
coverage.min(1.0)
}
pub fn entity_count(&self) -> usize {
self.entities.len()
}
pub fn relation_count(&self) -> usize {
self.relations.len()
}
pub fn crawled_url_count(&self) -> usize {
self.crawled_urls.len()
}
fn get_all_entity_ids(&self) -> Vec<String> {
self.entities.keys().take(5).cloned().collect()
}
fn get_entity_ids_by_type(&self, type_label: &str) -> Vec<String> {
self.entities
.values()
.filter(|e| e.entity_type.label() == type_label)
.map(|e| e.id.clone())
.take(5)
.collect()
}
pub fn get_neighbors(&self, entity_id: &str) -> Vec<(String, String)> {
self.relations
.iter()
.filter_map(|r| {
if r.source_id == entity_id {
Some((r.target_id.clone(), r.relation_type.label().to_string()))
} else if r.target_id == entity_id {
Some((r.source_id.clone(), r.relation_type.label().to_string()))
} else {
None
}
})
.collect()
}
pub fn url_priority_boost(&self, url: &str) -> f64 {
let holes = self.find_structural_holes();
if holes.is_empty() {
return 1.0;
}
if self.matches_hole_pattern(url, &holes) {
return 2.0; }
1.0
}
fn matches_hole_pattern(&self, url: &str, holes: &[StructuralHole]) -> bool {
for hole in holes {
for pattern in &hole.suggested_url_patterns {
if self.url_matches_pattern(url, pattern) {
return true;
}
}
}
false
}
fn url_matches_pattern(&self, url: &str, pattern: &str) -> bool {
let parts: Vec<&str> = pattern.split("**").collect();
if parts.len() == 1 {
return url == pattern;
}
let mut pos = 0;
for part in &parts {
if part.is_empty() {
continue;
}
if let Some(found) = url[pos..].find(part) {
pos += found + part.len();
} else {
return false;
}
}
true
}
}
pub struct KgBoostScorer {
kg: std::sync::Arc<std::sync::RwLock<KnowledgeGraphAccumulator>>,
}
impl KgBoostScorer {
pub fn new(kg: std::sync::Arc<std::sync::RwLock<KnowledgeGraphAccumulator>>) -> Self {
Self { kg }
}
}
impl UrlScorer for KgBoostScorer {
fn score(&self, url: &str, _context: &ScoringContext) -> f32 {
let kg = self.kg.read().unwrap_or_else(|e| e.into_inner());
let boost = kg.url_priority_boost(url);
((boost - 1.0) as f32 + 0.5).clamp(0.0, 1.0)
}
}
impl Default for KnowledgeGraphAccumulator {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_add_entity_and_count() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
kg.add_entity(
"e2",
EntityType::Organization,
"Acme",
"http://example.com/2",
);
kg.add_entity("e3", EntityType::Person, "Bob", "http://example.com/3");
assert_eq!(kg.entity_count(), 3);
assert_eq!(kg.crawled_url_count(), 3);
}
#[test]
fn test_add_entity_same_id_merges_sources() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/2");
assert_eq!(kg.entity_count(), 1);
assert_eq!(kg.crawled_url_count(), 2);
assert_eq!(kg.entities["e1"].source_urls.len(), 2);
}
#[test]
fn test_add_relation() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
kg.add_entity(
"e2",
EntityType::Organization,
"Acme",
"http://example.com/1",
);
kg.add_relation("e1", "e2", RelationType::WorksAt, "http://example.com/1");
assert_eq!(kg.relation_count(), 1);
}
#[test]
fn test_add_duplicate_relation_merges_sources() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
kg.add_entity(
"e2",
EntityType::Organization,
"Acme",
"http://example.com/1",
);
kg.add_relation("e1", "e2", RelationType::WorksAt, "http://example.com/1");
kg.add_relation("e1", "e2", RelationType::WorksAt, "http://example.com/2");
assert_eq!(kg.relation_count(), 1);
assert_eq!(kg.relations[0].source_urls.len(), 2);
}
#[test]
fn test_find_structural_holes_missing_type() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.register_entity_type("person");
kg.register_entity_type("location");
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
let holes = kg.find_structural_holes();
assert!(
holes
.iter()
.any(|h| matches!(&h.kind, HoleKind::MissingEntityType(t) if t == "location")),
"should detect missing 'location' type"
);
}
#[test]
fn test_find_structural_holes_underrepresented() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
let holes = kg.find_structural_holes();
assert!(
holes.iter().any(|h| matches!(&h.kind, HoleKind::UnderrepresentedType { entity_type, .. } if entity_type == "person")),
"should detect underrepresented 'person' type"
);
}
#[test]
fn test_find_structural_holes_missing_relation() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.register_relation_type("works_at");
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
kg.add_entity(
"e2",
EntityType::Organization,
"Acme",
"http://example.com/2",
);
let holes = kg.find_structural_holes();
assert!(
holes.iter().any(|h| matches!(&h.kind, HoleKind::MissingRelation { relation_type, .. } if relation_type == "works_at")),
"should detect missing 'works_at' relation"
);
}
#[test]
fn test_get_neighbors() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
kg.add_entity(
"e2",
EntityType::Organization,
"Acme",
"http://example.com/1",
);
kg.add_relation("e1", "e2", RelationType::WorksAt, "http://example.com/1");
let neighbors = kg.get_neighbors("e1");
assert_eq!(neighbors.len(), 1);
assert_eq!(neighbors[0].0, "e2");
assert_eq!(neighbors[0].1, "works_at");
}
#[test]
fn test_estimate_coverage_all_types_well_represented() {
let mut kg = KnowledgeGraphAccumulator::new();
for i in 0..5 {
kg.add_entity(
&format!("p{}", i),
EntityType::Person,
&format!("Person {}", i),
&format!("http://example.com/p{}", i),
);
kg.add_entity(
&format!("o{}", i),
EntityType::Organization,
&format!("Org {}", i),
&format!("http://example.com/o{}", i),
);
kg.add_entity(
&format!("l{}", i),
EntityType::Location,
&format!("Loc {}", i),
&format!("http://example.com/l{}", i),
);
}
let coverage = kg.estimate_coverage();
assert!(
coverage > 0.9,
"coverage should be high when all types well represented, got {}",
coverage
);
}
#[test]
fn test_estimate_coverage_with_singletons() {
let mut kg = KnowledgeGraphAccumulator::new();
for i in 0..10 {
kg.add_entity(
&format!("p{}", i),
EntityType::Person,
&format!("Person {}", i),
&format!("http://example.com/p{}", i),
);
}
kg.add_entity(
"o1",
EntityType::Organization,
"Org1",
"http://example.com/o1",
);
kg.add_entity("l1", EntityType::Location, "Loc1", "http://example.com/l1");
let coverage = kg.estimate_coverage();
assert!(
coverage < 1.0,
"coverage should be < 1.0 with singletons, got {}",
coverage
);
assert!(
coverage > 0.5,
"coverage should still be reasonable, got {}",
coverage
);
}
#[test]
fn test_estimate_coverage_empty() {
let kg = KnowledgeGraphAccumulator::new();
let coverage = kg.estimate_coverage();
assert_eq!(coverage, 1.0, "empty KG should have default coverage 1.0");
}
#[test]
fn test_estimate_coverage_single_type() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
let coverage = kg.estimate_coverage();
assert!(
coverage >= 0.5,
"single type coverage should be reasonable, got {}",
coverage
);
}
#[test]
fn test_url_priority_boost_no_holes() {
let mut kg = KnowledgeGraphAccumulator::new();
for i in 0..3 {
kg.add_entity(
&format!("p{}", i),
EntityType::Person,
&format!("Person {}", i),
&format!("http://example.com/p{}", i),
);
}
let boost = kg.url_priority_boost("http://example.com/new");
assert!(boost >= 1.0);
}
#[test]
fn test_url_priority_boost_with_matching_hole() {
let mut kg = KnowledgeGraphAccumulator::new();
kg.register_entity_type("location");
kg.add_entity("e1", EntityType::Person, "Alice", "http://example.com/1");
kg.add_entity("e2", EntityType::Person, "Bob", "http://example.com/2");
let boost = kg.url_priority_boost("http://example.com/location/paris");
assert_eq!(boost, 2.0, "URL matching hole pattern should get 2x boost");
}
}