0
$\begingroup$

(larger context at the end)

My view of the problem

I have an undirected graph whose nodes can be categorized into three classes depending on some metadata (I have a function that can tell me the class of a node in constant time), let's name the classes $A$, $B$ and $C$.

I want to find an $A$ node and a $C$ node such that the distance between the two is the largest possible (if there are multiple candidates with the same distance, any will do). My current approach is to start a BFS from a random node in the graph to find all $A$ nodes, then, for all $A$ nodes I found, start a new BFS with level markers to find all $C$ nodes and their distance to that $A$ node.

Is there a more efficient way to do this? From my understanding this is kind of like computing the diameter of the graph, but with a constraint on which kind of nodes can be at both ends of the diameter. Algorithms such as those mentioned on all-pairs shortest paths are interesting but they either are as efficient as my current approach (like Floyd-Warshall) or they require an adjacency matrix to do efficient multiplications on (like Seidel's algorithm) and the size of my graph makes it unfeasible to build an adjacency matrix.

My more precise (but optional) context

I'm not sure to what extent this can is relevant to the problem so feel free to ignore that part, but more precisely, the graph I'm using is a graph of open source projects revision history, with forks and all1. Connected components in that graph are projects that are forks of one-another (connected since they have revisions (nodes) in common), identified by "origin" nodes (it's an available metadata and that's what I called class $C$ in my previous presentation). The graph is actually directed, but every $u \xrightarrow{succ} v$ edge ($v$ is an ancestor revision of $u$) has a symmetrical $v \xrightarrow{pred} u$ edge. I identify "root revisions" as nodes that have no $succ$ edge starting from them (this is class $A$ in my previous presentation, so testing that class isn't actually constant-time, but close enough). Class $B$ is any node that isn't an origin or root revision.

My goal is to find the origin node that gives me the longest branch (the origin that is the farthest from the farthest accessible root revision), I later use this origin as the "representative" project for that set of forks. Because of the way I scan the full graph, my current algorithm actually starts at a random origin (class $C$) node, does a BFS on $succ$ edges only to find root revisions, then, for all root revisions, another BFS on $pred$ edges only with level markers to find accessible origin nodes and their distance to that root revision.

1: https://docs.softwareheritage.org/devel/swh-dataset/graph/

$\endgroup$
6
  • $\begingroup$ (software heritage & undirected?) $\endgroup$
    – greybeard
    Aug 8 at 12:37
  • 1
    $\begingroup$ Is some All-pairs shortest paths procedure helpful? $\endgroup$
    – greybeard
    Aug 8 at 12:38
  • $\begingroup$ @greybeard thanks, but yeah I saw this solution along with floyd-warshall for undirected graphs, but they are as efficient or worse than my current approach (since they compute all distances). $\endgroup$
    – Dettorer
    Aug 8 at 14:28
  • 1
    $\begingroup$ What does "farthest from the farthest A node" mean? Do you mean you want to find an A node and a C node such that the distance between them is the largest possible? $\endgroup$
    – D.W.
    Aug 8 at 17:45
  • 1
    $\begingroup$ OK. Please edit your question to address the feedback you've received so far. We want questions to read well for someone who encounters them for the first time, and people to be able to understand what you are asking without having to read the comments. Thank you! $\endgroup$
    – D.W.
    Aug 9 at 19:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.