Extremely Fast CD-Index

xfast-cdindex is a Python package with a C++ extension for computing the CD-index on evolving directed citation graphs. It is based on the original cdindex and fast-cdindex packages and keeps the same core graph API while using optimized native code for faster full-graph evaluation. Its performance optimizations were developed with the assistance of the Codex AI agent.

Install

Install from PyPI:

pip install xfast_cdindex

Quick Start

from xfast_cdindex import cdindex, timestamp_from_datetime
import datetime

vertices = [
    {"name": "0Z", "time": datetime.datetime(1992, 1, 1)},
    {"name": "1Z", "time": datetime.datetime(1992, 1, 1)},
    {"name": "2Z", "time": datetime.datetime(1993, 1, 1)},
    {"name": "3Z", "time": datetime.datetime(1993, 1, 1)},
    {"name": "4Z", "time": datetime.datetime(1995, 1, 1)},
    {"name": "5Z", "time": datetime.datetime(1997, 1, 1)},
    {"name": "6Z", "time": datetime.datetime(1998, 1, 1)},
    {"name": "7Z", "time": datetime.datetime(1999, 1, 1)},
    {"name": "8Z", "time": datetime.datetime(1999, 1, 1)},
    {"name": "9Z", "time": datetime.datetime(1998, 1, 1)},
    {"name": "10Z", "time": datetime.datetime(1997, 1, 1)},
]

edges = [
    {"source": "4Z", "target": "2Z"},
    {"source": "4Z", "target": "0Z"},
    {"source": "4Z", "target": "1Z"},
    {"source": "4Z", "target": "3Z"},
    {"source": "5Z", "target": "2Z"},
    {"source": "6Z", "target": "2Z"},
    {"source": "6Z", "target": "4Z"},
    {"source": "7Z", "target": "4Z"},
    {"source": "8Z", "target": "4Z"},
    {"source": "9Z", "target": "4Z"},
    {"source": "9Z", "target": "1Z"},
    {"source": "9Z", "target": "3Z"},
    {"source": "10Z", "target": "4Z"},
]

graph = cdindex.Graph()

for vertex in vertices:
    timestamp = timestamp_from_datetime(vertex["time"])
    graph.add_vertex(vertex["name"], timestamp)

for edge in edges:
    graph.add_edge(edge["source"], edge["target"])

graph.prepare_for_searching()

time_delta = int(datetime.timedelta(days=1825).total_seconds())
cd_value = graph.cdindex("4Z", time_delta)
mcd_value = graph.mcdindex("4Z", time_delta)

print(cd_value)
print(mcd_value)

Agent-Guided Optimization

The current performance results were achieved through an automated optimization workflow built around GLM-5.3 and GPT-6-Astra. In this workflow, Codex iteratively inspected benchmark results, modified the allowed source files, rebuilt the package, validated correctness, and retained changes only when the core performance metrics improved. After 30 iterations, the model reached the performance shown below.

Benchmark Results

The full cit-Patents benchmark used 3,774,768 vertices and 16,518,948 edges. The optimized version preserves the same Python API and substantially improves graph construction and CD-index computation.

Environment: Intel Core i7-8700, Linux x86-64, Python 3.13.13, GCC 13.3.0, and NumPy 2.2.6.

License

Released under the GNU General Public License (GPL). See LICENSE.

Copyright (C) 2017 Russell J. Funk <russellfunk@gmail.com>
Copyright (C) 2023 Diomidis Spinellis <dds@aueb.gr>
Copyright (C) 2026 Pujun Zheng <pjzheng@stu.ecnu.edu.cn>