Kotoba Graph

High-performance graph data structures for the Kotoba graph processing system. Provides efficient implementations of vertices, edges, and graph operations optimized for graph rewriting and query processing.

🎯 Overview

Kotoba Graph serves as the core data layer for graph processing, providing:

• Efficient Graph Structures: Column-oriented graph representation for optimal performance
• Rich Metadata: Labels and properties on vertices and edges
• Thread-Safe Operations: Concurrent access patterns with GraphRef
• Fast Traversal: Optimized adjacency lists and indexing

🏗️ Architecture

Core Data Structures

Graph Structure (graph.rs)

// Main graph with column-oriented storage
#[derive(Debug, Clone)]
pub struct Graph {
    // Vertex storage (ID → Data)
    pub vertices: HashMap<VertexId, VertexData>,

    // Edge storage (ID → Data)
    pub edges: HashMap<EdgeId, EdgeData>,

    // Adjacency lists for fast traversal
    pub adj_out: HashMap<VertexId, HashSet<VertexId>>, // Outgoing edges
    pub adj_in: HashMap<VertexId, HashSet<VertexId>>,   // Incoming edges

    // Label-based indexing
    pub vertex_labels: HashMap<Label, HashSet<VertexId>>,
    pub edge_labels: HashMap<Label, HashSet<EdgeId>>,
}

Vertex & Edge Data

// Vertex with metadata
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct VertexData {
    pub id: VertexId,
    pub labels: Vec<Label>,
    pub props: Properties,
}

// Edge with source/destination and metadata
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct EdgeData {
    pub id: EdgeId,
    pub src: VertexId,
    pub dst: VertexId,
    pub label: Label,
    pub props: Properties,
}

📊 Quality Metrics

🔧 Usage

Basic Graph Operations

use kotoba_graph::prelude::*;
use kotoba_core::types::*;
use std::collections::HashMap;

// Create empty graph
let mut graph = Graph::empty();

// Add vertices with properties
let alice_id = VertexId::new_v4();
let alice = VertexData {
    id: alice_id,
    labels: vec!["Person".to_string()],
    props: {
        let mut props = HashMap::new();
        props.insert("name".to_string(), Value::String("Alice".to_string()));
        props.insert("age".to_string(), Value::Int(30));
        props
    },
};
graph.add_vertex(alice);

// Add edges
let bob_id = VertexId::new_v4();
let bob = VertexData {
    id: bob_id,
    labels: vec!["Person".to_string()],
    props: HashMap::new(),
};
graph.add_vertex(bob);

// Create relationship
let follows_edge = EdgeData {
    id: EdgeId::new_v4(),
    src: alice_id,
    dst: bob_id,
    label: "FOLLOWS".to_string(),
    props: HashMap::new(),
};
graph.add_edge(follows_edge);

// Query operations
assert!(graph.has_vertex(&alice_id));
assert_eq!(graph.vertex_count(), 2);
assert_eq!(graph.edge_count(), 1);

Advanced Operations

use kotoba_graph::GraphRef;

// Thread-safe graph reference
let graph_ref = GraphRef::new(graph);

// Concurrent access
let vertices = graph_ref.read().vertices.clone();
// ... perform operations

🔗 Ecosystem Integration

Kotoba Graph is the foundation for:

🧪 Testing

cargo test -p kotoba-graph

Test Coverage:

• ✅ Graph creation and basic operations
• ✅ Vertex addition, retrieval, and validation
• ✅ Edge operations with adjacency tracking
• ✅ Graph statistics and metadata
• ✅ Serialization/deserialization
• ✅ Label-based indexing

📈 Performance

• O(1) Lookups: Direct hash map access for vertices and edges
• Efficient Traversal: Pre-computed adjacency lists
• Memory Optimized: Column-oriented storage minimizes overhead
• Concurrent Access: RwLock-based thread safety
• Label Indexing: Fast queries by vertex/edge labels

🔒 Security

• Type Safety: Strongly typed graph operations
• Memory Safety: Rust guarantees prevent buffer overflows
• Thread Safety: Safe concurrent access patterns
• Property Validation: Type-safe property access

📚 API Reference

Core Types

• [Graph] - Main graph data structure
• [VertexData] - Vertex with metadata and properties
• [EdgeData] - Edge with source, destination, and properties
• [GraphRef] - Thread-safe graph reference

Operations

• [Graph::add_vertex()] - Add vertex to graph
• [Graph::add_edge()] - Add edge with adjacency updates
• [Graph::has_vertex()] - Check vertex existence
• [Graph::vertex_count()] / [Graph::edge_count()] - Graph statistics

Traversal

• [Graph::adj_out] - Outgoing adjacency list
• [Graph::adj_in] - Incoming adjacency list
• [Graph::vertex_labels] - Label-based vertex indexing

🤝 Contributing

See the main Kotoba repository for contribution guidelines.

📄 License

Licensed under MIT OR Apache-2.0. See LICENSE for details.