real_data_test.cpp

#include "graph_operations.cpp"
#include <fstream>
#include <sstream>
#include <chrono>
#include <iomanip>
#include <cmath>
#include <windows.h>
#include <psapi.h>

using namespace std;
using namespace std::chrono;

// Function to get current memory usage in bytes
size_t getCurrentMemoryUsage() {
    PROCESS_MEMORY_COUNTERS_EX pmc;
    if (GetProcessMemoryInfo(GetCurrentProcess(), (PROCESS_MEMORY_COUNTERS*)&pmc, sizeof(pmc))) {
        return pmc.WorkingSetSize;
    }
    return 0;
}

// Function to format memory size
string formatMemory(size_t bytes) {
    if (bytes < 1024) {
        return to_string(bytes) + " B";
    } else if (bytes < 1024 * 1024) {
        return to_string(bytes / 1024) + " KB";
    } else {
        double mb = bytes / (1024.0 * 1024.0);
        char buffer[50];
        sprintf(buffer, "%.2f MB", mb);
        return string(buffer);
    }
}

// ADJACENCY CRITERIA 1: Original Edges (Direct Connections)
// Loads the graph exactly as provided in the dataset.
// Adjacency: Two vertices u and v are adjacent if there exists an edge (u,v) 
// in the original YouTube social network data.

Graph loadGraphFromFile(const string& filename) {
    Graph g;
    ifstream file(filename);
    
    if (!file.is_open()) {
        cerr << "Error: Could not open file " << filename << endl;
        return g;
    }
    
    cout << "Loading graph from file: " << filename << endl;
    
    string line;
    int edgeCount = 0;
    int lineCount = 0;
    
    while (getline(file, line)) {
        lineCount++;
        
        // Skip comment lines
        if (line.empty() || line[0] == '#') {
            continue;
        }
        
        // Parse edge: fromNode  toNode
        istringstream iss(line);
        int fromNode, toNode;
        
        if (iss >> fromNode >> toNode) {
            g.addEdge(fromNode, toNode);
            edgeCount++;
            
            // Progress indicator every 100,000 edges
            if (edgeCount % 100000 == 0) {
                cout << "  Loaded " << edgeCount << " edges..." << endl;
            }
        }
    }
    
    file.close();
    
    cout << "Graph loading complete!" << endl;
    cout << "  Total vertices: " << g.numVertices() << endl;
    cout << "  Total edges: " << g.numEdges() << endl;
    
    return g;
}

 
// ADJACENCY CRITERIA 2: High-Activity Users Filter
// Adjacency: Two vertices u and v are adjacent if:
//   1. An edge (u,v) exists in the original graph, AND
//   2. Both u and v have degree ≥ minDegree in the original graph
Graph loadGraphFiltered(const string& filename, int minDegree) {
    // First pass: load original graph to compute degrees
    cout << "\n--- Adjacency Criteria 2: High-Activity Filter ---" << endl;
    cout << "Minimum degree threshold: " << minDegree << endl;
    Graph originalGraph = loadGraphFromFile(filename);
    
    cout << "Computing degree distribution..." << endl;
    
    // Count degrees
    map<int, int> degrees;
    for (int v : originalGraph.getVertices()) {
        const auto& adjList = originalGraph.getAdjList();
        if (adjList.find(v) != adjList.end()) {
            degrees[v] = adjList.at(v).size();
        }
    }
    
    // Create filtered graph
    cout << "Creating filtered graph (keeping high-activity users)..." << endl;
    Graph filteredGraph;
    int filteredEdges = 0;
    
    for (int u : originalGraph.getVertices()) {
        const auto& adjList = originalGraph.getAdjList();
        if (adjList.find(u) != adjList.end()) {
            for (int v : adjList.at(u)) {
                // Only add edge if both vertices meet the degree threshold
                if (u < v && degrees[u] >= minDegree && degrees[v] >= minDegree) {
                    filteredGraph.addEdge(u, v);
                    filteredEdges++;
                }
            }
        }
    }
    
    cout << "Filtered graph created!" << endl;
    cout << "  Vertices: " << filteredGraph.numVertices() << endl;
    cout << "  Edges: " << filteredGraph.numEdges() << endl;
    
    return filteredGraph;
}

// ADJACENCY CRITERIA 3: Degree Similarity
// Adjacency: Two vertices u and v are adjacent if:
//   1. An edge (u,v) exists in the original graph, AND
//   2. The degrees of u and v are within a similarity threshold:
//      |degree(u) - degree(v)| / max(degree(u), degree(v)) ≤ (1 - threshold)
//   i.e., similarity ≥ threshold means degrees are similar

Graph loadGraphDegreeSimilarity(const string& filename, double similarityThreshold) {
    // First pass: load original graph to compute degrees
    cout << "\n--- Adjacency Criteria 3: Degree Similarity ---" << endl;
    cout << "Similarity threshold: " << similarityThreshold << " (1.0 = identical degrees)" << endl;
    Graph originalGraph = loadGraphFromFile(filename);
    
    cout << "Computing degree distribution..." << endl;
    
    // Count degrees
    map<int, int> degrees;
    for (int v : originalGraph.getVertices()) {
        const auto& adjList = originalGraph.getAdjList();
        if (adjList.find(v) != adjList.end()) {
            degrees[v] = adjList.at(v).size();
        } else {
            degrees[v] = 0;
        }
    }
    
    // Create similarity-based graph
    cout << "Creating degree similarity graph..." << endl;
    Graph similarityGraph;
    int similarityEdges = 0;
    
    for (int u : originalGraph.getVertices()) {
        const auto& adjList = originalGraph.getAdjList();
        if (adjList.find(u) != adjList.end()) {
            for (int v : adjList.at(u)) {
                if (u < v) { // Avoid duplicate edges
                    // Calculate degree similarity
                    int degU = degrees[u];
                    int degV = degrees[v];
                    double maxDeg = max(degU, degV);
                    
                    if (maxDeg > 0) {
                        double similarity = 1.0 - (abs(degU - degV) / maxDeg);
                        
                        // Add edge if similarity meets threshold
                        if (similarity >= similarityThreshold) {
                            similarityGraph.addEdge(u, v);
                            similarityEdges++;
                        }
                    }
                }
            }
        }
    }
    
    cout << "Degree similarity graph created!" << endl;
    cout << "  Vertices: " << similarityGraph.numVertices() << endl;
    cout << "  Edges: " << similarityGraph.numEdges() << endl;
    
    return similarityGraph;
}

void testGraphWithCriteria(const string& criteriaName, Graph& g, size_t memBefore, long long loadTime) {
    cout << "\n========================================" << endl;
    cout << "TESTING: " << criteriaName << endl;
    cout << "========================================" << endl;
    cout << "Vertices: " << g.numVertices() << ", Edges: " << g.numEdges() << endl;
    cout << "Graph loading time: " << loadTime << " ms (" << (loadTime / 1000.0) << " seconds)" << endl;
    
    size_t memAfterLoad = getCurrentMemoryUsage();
    cout << "Memory after load: " << formatMemory(memAfterLoad) << endl;
    cout << endl;
    
    auto totalStart = high_resolution_clock::now();
    
    // Test 1: Connected Components
    cout << "Test 1: Connected Components (DFS)" << endl;
    auto start = high_resolution_clock::now();
    auto components = g.connected_components();
    auto end = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(end - start);
    
    cout << "  Number of connected components: " << components.size() << endl;
    
    // Show size of largest components
    vector<int> componentSizes;
    for (const auto& comp : components) {
        componentSizes.push_back(comp.size());
    }
    sort(componentSizes.begin(), componentSizes.end(), greater<int>());
    
    if (componentSizes.size() > 0) {
        cout << "  Largest component: " << componentSizes[0];
        if (componentSizes.size() == 1) cout << " (entire graph connected)";
        cout << endl;
    }
    
    cout << "  Time: " << duration.count() << " ms (" << (duration.count() / 1000.0) << " sec)" << endl;
    
    size_t memAfterComponents = getCurrentMemoryUsage();
    cout << "  Memory: " << formatMemory(memAfterComponents) << endl;
    cout << endl;
    
    // Test 2: Cycle Detection
    cout << "Test 2: Cycle Detection (DFS)" << endl;
    start = high_resolution_clock::now();
    auto cycle = g.one_cycle();
    end = high_resolution_clock::now();
    duration = duration_cast<milliseconds>(end - start);
    
    if (cycle.empty()) {
        cout << "  No cycle found" << endl;
    } else {
        cout << "  Cycle found! Length: " << cycle.size() - 1 << endl;
    }
    
    cout << "  Time: " << duration.count() << " ms" << endl;
    
    size_t memAfterCycle = getCurrentMemoryUsage();
    cout << "  Memory: " << formatMemory(memAfterCycle) << endl;
    cout << endl;
    
    // Test 3: Shortest Paths (Dijkstra)
    cout << "Test 3: Shortest Paths (Dijkstra)" << endl;
    
    int sourceVertex = 0;
    if (!components.empty() && !components.front().empty()) {
        sourceVertex = components.front().front();
    }
    
    cout << "  Computing shortest paths from vertex " << sourceVertex << "..." << endl;
    
    start = high_resolution_clock::now();
    auto paths = g.shortest_paths(sourceVertex);
    end = high_resolution_clock::now();
    duration = duration_cast<milliseconds>(end - start);
    
    cout << "  Reachable vertices: " << paths.size() << endl;
    
    map<int, int> pathLengthDistribution;
    int maxLength = 0;
    for (const auto& p : paths) {
        int length = p.second.size() - 1;
        pathLengthDistribution[length]++;
        if (length > maxLength) maxLength = length;
    }
    
    cout << "  Maximum distance: " << maxLength << endl;
    cout << "  Time: " << duration.count() << " ms (" << (duration.count() / 1000.0) << " sec)" << endl;
    
    size_t memAfterPaths = getCurrentMemoryUsage();
    cout << "  Memory: " << formatMemory(memAfterPaths) << endl;
    cout << endl;
    
    // Summary
    auto totalEnd = high_resolution_clock::now();
    auto totalDuration = duration_cast<milliseconds>(totalEnd - totalStart);
    
    size_t peakMemory = max({memAfterLoad, memAfterComponents, memAfterCycle, memAfterPaths});
    cout << "SUMMARY - " << criteriaName << endl;
    cout << "  Peak Memory: " << formatMemory(peakMemory) << " (+" << formatMemory(peakMemory - memBefore) << " from baseline)" << endl;
    cout << "  Total Test Time: " << totalDuration.count() << " ms (" << (totalDuration.count() / 1000.0) << " sec)" << endl;
    cout << "========================================" << endl;
}

int main() {
    cout << "========================================" << endl;
    cout << "REAL-WORLD GRAPH ANALYSIS" << endl;
    cout << "Dataset: YouTube Social Network (SNAP)" << endl;
    cout << "========================================" << endl;
    cout << endl;
    
    cout << "Testing ALL THREE Adjacency Criteria:" << endl;
    cout << "1. Original Edges - Direct connections from dataset" << endl;
    cout << "2. High-Activity Filter - Edges between users with degree >= 10" << endl;
    cout << "3. Degree Similarity - Edges between users with 70% degree similarity" << endl;
    cout << endl;
    
    size_t memBefore = getCurrentMemoryUsage();
    cout << "Baseline Memory: " << formatMemory(memBefore) << endl;
    cout << endl;
    
    // CRITERIA 1: Original Edges
    cout << "\n>>>>> LOADING CRITERIA 1: Original Edges <<<<<" << endl;
    auto loadStart = high_resolution_clock::now();
    Graph g1 = loadGraphFromFile("com-youtube.ungraph.txt");
    auto loadEnd = high_resolution_clock::now();
    auto loadDuration = duration_cast<milliseconds>(loadEnd - loadStart);
    
    if (g1.numVertices() > 0) {
        testGraphWithCriteria("CRITERIA 1: Original Edges", g1, memBefore, loadDuration.count());
    }
    
    // CRITERIA 2: High-Activity Filter
    cout << "\n>>>>> LOADING CRITERIA 2: High-Activity Filter <<<<<" << endl;
    loadStart = high_resolution_clock::now();
    Graph g2 = loadGraphFiltered("com-youtube.ungraph.txt", 10);
    loadEnd = high_resolution_clock::now();
    loadDuration = duration_cast<milliseconds>(loadEnd - loadStart);
    
    if (g2.numVertices() > 0) {
        testGraphWithCriteria("CRITERIA 2: High-Activity Filter (degree >= 10)", g2, memBefore, loadDuration.count());
    }
    
    // CRITERIA 3: Degree Similarity
    cout << "\n>>>>> LOADING CRITERIA 3: Degree Similarity <<<<<" << endl;
    loadStart = high_resolution_clock::now();
    Graph g3 = loadGraphDegreeSimilarity("com-youtube.ungraph.txt", 0.7);
    loadEnd = high_resolution_clock::now();
    loadDuration = duration_cast<milliseconds>(loadEnd - loadStart);
    
    if (g3.numVertices() > 0) {
        testGraphWithCriteria("CRITERIA 3: Degree Similarity (70% threshold)", g3, memBefore, loadDuration.count());
    }
    
    return 0;
}