Come cercare su e giù un grafico dal punto centrale?

Potresti implementarlo con due funzioni ricorsive molto semplici: una che trova tutti gli antenati (può viaggiare solo a sinistra) e un'altra che trova tutti i discendenti (può viaggiare solo a destra).

Esempio di pseudo-codice:

get_family(node a)
{
    list family = get_ancestors(a) + get_children(a)

    return family
}

get_ancestors(node a)
{
   list ancestors

   foreach anc in a.ancestors
   {
      ancestors = ancestors + anc + get_ancestors(anc)
   }

   return ancestors
}

get_children(node a)
{
   list children

   foreach child in a.children
   {
      children = children + child + get_children(child)
   }

   return children
}

Aggiornamento: come sottolineato da Derek Elkins, se è possibile che due percorsi divergano per unirsi nuovamente, allora è necessario un modo per impedire che i nodi vengano visitati più volte. Ad esempio contrassegnando ciascun nodo come visitato.

Ecco una soluzione procedurale. L'ho scritto in C #, ma spero che i commenti chiariscano cosa sta succedendo anche se non hai familiarità con C #.

L'idea alla base di questo algoritmo è che possiamo trovare tutti i discendenti guardando il nodo radice, e anche guardando i figli di ogni nodo che guardiamo. Manteniamo un elenco di nodi "da fare" che dobbiamo ancora esaminare, in modo da non perdere la nostra strada.

(Probabilmente c'è un nome per questo algoritmo, ma non so cosa sia.)

// This method defines how to find the descendants of a node "rootNode".
// It returns a set of nodes.
static HashSet<Node> FindDescendants(Node rootNode)
{
    // Let "descendants" and "descendantsToCheck" initially be
    // the set containing only rootNode.
    HashSet<Node> descendants = new HashSet<Node> { rootNode };
    HashSet<Node> descendantsToCheck = new HashSet<Node> { rootNode };

    // While there are still descendants left to check...
    while (descendantsToCheck.Count > 0)
    {
        // Let thisDescendant be an arbitrary descendant
        // which still needs to be checked. We will check this descendant.
        Node thisDescendant = descendantsToCheck.First();

        // For each child of thisDescendant...
        foreach (Node child in thisDescendant.Children)
        {
            // We have found a descendant. If it is already in our "descendants"
            // set, then we don't need to do anything, because this descendant
            // either has been checked or will be checked.

            // However, if this descendant is not in "descendants"...
            if (!descendants.Contains(child))
            {
                // We need to add this child to our set of descendants,
                // as well as our set of descendants that need to be checked.

                descendants.Add(child);
                descendantsToCheck.Add(child);
            }
        }

        // We are done checking thisDescendant,
        // so remove it from the set of descendants to check.
        descendantsToCheck.Remove(thisDescendant);
    }

    // At this point, there are no descendants left to check.
    // This means that we have found all of the descendants. Return them.
    return descendants;
}

Questo algoritmo ti dà solo i discendenti, non gli antenati. Per trovare gli antenati dei discendenti e , usa l'algoritmo due volte: una volta per i discendenti, una volta per gli antenati.

Per trovare antenati, hai un paio di opzioni. Un'opzione è scrivere una funzione FindAncestors identica alla funzione FindDescendants , eccetto che guarda i genitori invece dei figli. Un'altra opzione è quella di modificare l'opzione FindDescendants per prendere un parametro che indichi se deve riguardare bambini o genitori.

Devi fare due semplici attraversamenti grafici dai tuoi punti di partenza, uno che segue solo i bordi del grafico da sinistra a a destra (direzione da genitore a figlio) e un secondo nella direzione opposta.

Se preferisci eseguire l'attraversamento in profondità o in ampiezza, dipende da te, entrambi funzioneranno e nessuno è "generalmente migliore" dell'altro se non hai vincoli aggiuntivi o requisiti rispetto alla semplice selezione di tutti i nodi.