Algorithme de sous-graphe

Question

Je voudrais savoir s'il existe un algorithme efficace S = F (v, G) pour construire un sous-graphe S sur un DAG G = (V, E) tel que tous les chemins de S contiennent le sommet v de V. Si oui, il est possible d'étendre efficacement F à F '(N, G) pour un ensemble de sommets N. Je suis ouvert à toutes les structures de données pour stocker le DAG G initialement.

En fait, une condition que j'ai oublié d'ajouter serait que G ait un sommet unique r sans bord entrant et un chemin doit être de la forme où d est un sommet sans bord sortant. Une autre condition que j'ai manquée est donnée l'étendue F '(N, G) tel que pour tout v, w de N si < r, .., v, .., w> où w est un puits, alors nous ne devrions pas tenir compte des chemins < r, .., v, .., x> où x! = w.

J'ai en fait une solution, mais il ne se classe pas, quand #V> 2000 et #N> 2.

Answer 1

Je suppose que vous êtes à la recherche de la plus grande sous-graphe S de G = ({r} + V + {d}, E) où r est le nœud source unique et d est le puits de telle sorte que tous les chemins de r à d passe un nœud spécifique v

Mon algorithme proposé.

1. Trouver tous chemins entre r et v en utilisant par exemple les réponses fournies dans Find the paths between two given nodes?

2. Trouver tous les chemins entre v et utiliser le même algorithme. Puisque G est acyclique, pas de chemin de v à d peut conduire sur une trajectoire déjà trouvé à l'étape 1. Ainsi, dans le graphique résultant tous les chemins entre r et d passeront v.

Answer 2

graphique Résultante contient des nœuds qui sont accessibles à partir de v et les nœuds v sont accessibles depuis (ou, les nœuds qui sont accessibles depuis v dans un sous-graphe transposé). Obtenir l'ensemble des noeuds accessibles peut être fait efficacement.

Ceci peut être étendu facilement pour un ensemble de nœuds: vous devez simplement les ajouter tous au début de votre recherche en largeur d'abord.