Подскажите алгоритм/структуру данных

Не знаю насчёт именно эффективной структуры, но вообще у вас тут двудольный граф.

Думаю, никакой дополнительной к двудольному графу структуры тут найти не удастся. Разве что какой-нибудь «разреженный» двудольный граф, если такие существуют — как противоположность полного двудольного графа.

В перле не силён, псевдокод:

// для каждого .cpp множество всех .h которые включаются в него
map<string, set<string>> cpp2h;

// для каждого .h множество всех .cpp в которые он включается
map<string, set<string>> h2cpp;

string hasSameTranslationUnit(string h1, string h2)
{
    for (cpp in h2cpp[h1])
    {
        if (cpp2h[cpp].contains(h2))
            return true;
    }

    return false;
}

При желании можно хранить не все вхождения, а только прямые, но при просмотре тогда придётся сделать рекурсивный проход.

Можно ещё оптимизировать сравнив количество элементов в h2cpp[h1] и h2cpp[h2] и делать перебор по меньшему множеству.

Раз имя единицы трансляции не важно и надо оптимизировать проверку, то мне кажется, что лучше так:

map<string, set<string>> hNeighbours;

void
init(std::vector<SourceFile> files)
{
    for (SourceFile source : files) {
        for (string hdrA : file.headers()) {
            for (string hdrB : file.headers()) {
                if (hdrA != hdrB) {
                    hNeighbours[hdrA].insert(hdrB);
                }
            }
        }
    }
}

bool
contains(string hdrA, string hdrB)
{
    return hNeighbours[hdrA].contains(hdrB)
        || hNeighbours[hdrB].contains(hdrA);
}

около 9681 файлов исходников

как будто это много

1) предпроход: для каждого файла запоминаем модули, в которые он инклудится. отсортированный массив подойдет

files = {name: [] for name in dir()}
for module in dir() {
    for includes in module {
        files[includes] += module
    }
}

2) по запросу: для данных двух файлов просто сверяешь их массивы на предмет общего элемента

2) по запросу: для данных двух файлов просто сверяешь их массивы на предмет общего элемента

Это надо делать рекурсивно. Каждый раз. Потому не эффективно.

К примеру ситуация:

bar.h # цикл 
  |
foo.h
  \
  bar.h  baz.h
    \     /
    baz.cpp

f(foo.h, baz.h) == true

Я сейчас пытаюсь выровнять граф до леса деревьев по 1 уровню:

bar.h foo.h baz.h    bar.h  foo.h
  \    |   /           |   /
   baz.cpp           foo.h

С такой структурой проверка f(x,y) будет О(1) (не считая поиска нужного дерева)

К сожалению, такой алгоритм не охватывает проблему цепочки #include (а еще есть циклы). Надо еще добавлять рекурсию или трансформировать граф.

Мне кажется надо использовать матрицу смежности. Каждый файл (заголовочный и исходный) - это вершина неориентированного графа. Помещаем 1 в матрицу смежности если h включен в cpp. Матрица смежности неор. графа - симметрична, поэтому достаточно хранить половину данных. По скольку у вас очень разряженная матрица получится (количество включений сравнимо с количеством файлов-вершин), то можно матрица смежности хранить списком строк матрицы с массивов смежных вершин. Если файл включается большего одного раза, то в матрице смежности будет число связей больше 1. Чтобы чуть ускорить поиск в имени файла в матрице можно построить доп. индекс (бинарное дерево) для быстрого перехода на нужную строку матрицу смежности.

contains

к ситингу? удачи тебе братишка (переписал на джаваскрипте наверное)

Это надо делать рекурсивно. Каждый раз

просто кешируй результат рекурсии

просто кешируй результат рекурсии

Так практически и делаю.

Только если кешировать по ключу {file1,file2} — то не сильно помогает (cache miss около 90%). В процессе рекурсии я «сворачиваю» всю часть графа, которую видел при проходе (как в комментариях раньше написал).

И в чём проблема? Если найти все хидеры для каждого сорс файла, то потом легко сделать то что было предложено.

По первому сообщению думал, что оно уже в подходящем виде. Список заголовков для cpp-файла это же множество узлов, достижимых из его узла в оригинальном или инвертированном ориентированном графе. И, наверное, для каждого промежуточного узла можно этот список кешировать и таким образом сократить время построения списков для исходников.

contains

к ситингу?

Очевидно, что это было продолжение псевдокода.

Не спора ради, а просто любопытно: а зачем это нужно?

А в чем проблема собрать мапу где ключем будет имя инклудника, а значением список CPP файлов при компиляции которых используется этот инклудник ?

std::map< std::string, std::list<std::string> >

std::map<std::string, unsigned>

std::map< unsigned, std::vector<unsigned> >

Еще момент, если этот проект собирается через чтото основаное на «make» (autotools, cmake) - то можно использовать его дерево зависимостей (там уже все просщитано какие CPP нужно пересобрать при изменении данного хедера).

Не спора ради, а просто любопытно: а зачем это нужно?

Есть специфичный для проекта механизм из defensive programming. Точнее переключалки старый/новый код. Когда удаляется одна из таких переключалок, иногда остается мусор: например неиспользуемые обьявления (из-за обычной людской невнимательности). Скрипт должен помогать находить такой мусор.

А в чем проблема собрать мапу где ключем будет имя инклудника,

Если простую мапу: без разрешения цепочки инклудов и циклов, то довольно просто. Проблема появляется когда таки надо ходить по цепочкам инклюдов.

чтото основаное на «make» (autotools, cmake) - то можно использовать его дерево зависимостей

Интересная идея. Надо будет глянуть.

Если у тебя там только инклюдгарды (без прагма уанс), то: а) распарси гарды всех заголовочников, б) пройдись препроцессором по спп, в) грепни результат препроцессора по нужным гардам. Быстро, грязно, топорно, рабоче.

Там какой-то граф уже есть. А если заново парсить, то проще пропустить cpp через препроцессор и глянуть на #line директивы, там будут пути к заголовкам и не надо на гарды смотреть.

Если у тебя там только инклюдгарды

Мешанина там

См. опцию -M gcc.