Найти общего предка для двух коммитов

«дерево» в CVS не является как таковым деревом из теории графов - так как тут возможны слияния (циклы).

считай его ориентированным ациклическим графом. ориентированных циклов не будет.

будут возможны ситуации, в которых у двух узлов несколько ближайших общих предков, но в твоем примере все просто: общий предок D

Честно, на самом деле это усложняет задачу. :( Мне нужен алгоритм для нахождения для двух любых узлов общего предка.

Я нацарапал алгоритм.. и он находил для них общего предка B.

Дело в том, что я строил историю для каждого коммита справа налево.. таким образом, для G я получил A-B-E-F-G. Почему именно эта ветка - случайно получилось... в алгоритме я выбирал кратчайший путь до A. Прихожу к выводу, что это неправильно.

Так вот, в этой истории A-B-E-F-G нет D, следовательно, общий узел для A-B-E-F-G и A-B-C-D у меня оказался B.

выдай, кстати, определение LCA, которое тебе нужно. а то я тут подумал, что в контексте vcs, A может оказаться правильным ответом.

Это одно из тестовых заданий.В том именно и дело, что определения там чёткого нет. Может, в этом и вся соль задания? :) Написано вот так вот, одним предложением.

Implement a function that will find the most recent common ancestor of any two commits from a given commit graph.

И чуть дальше второе

If one commit is an ancestor of the other, return the commit that is the ancestor

То есть наверное да, в моём случае будет D общим предком.

Боже мой, CVS. Он где-то еще используется?

Зашёл сюда написать эту фразу.

тьфу. я буквами ошибся. опять

Кстати, я слышал, он правда используется. Но я имел ввиду VCS вообще... любую. Тут принципы одинаковые. И, наверное, скорее что-то похожее на git, чем что-то централизованное.

если эффективность не важна, проще всего так:

пусть надо найти LCA узлов X и Y

идешь параллельно от данных узлов bfs-ом в сторону корня, каждый пройденный узел добавляешь в X_set или Y_set. Если очередной узел в X_set уже присутствует в Y_set, или наоборот, то вуаля.

http://stackoverflow.com/questions/1549146/find-common-ancestor-of-two-branches

Но я имел ввиду VCS вообще... любую

В «VCS вообще» никто не говорит о дереве. Только о DAG.

граф, да

Эты ссылку я нашёл. Правда, не догадался заглянуть к документацию по git merge-base - там, оказывается, картинки есть.

посмотри тут и ещё вроде в комментах, советы были

http://habrahabr.ru/post/137408/

вообще git blame может помочь

Да не нужен мне конкретно git :) я же говорю, задачка чисто логическая (или математическая) - на графы. Не буду же я в исходниках git копаться, разбираясь, как там реализовано?

Общим предком для F и D является B, это очевидно. А что является общим предком для D и G?

Почему здесь не очевидно что B?