recherche efficace dans un graphe orienté

Question

J'ai un graphe orienté avec des millions de sommets et d'arêtes. Un ensemble de sommets sont donnés, supposons qu'ils sont appelés « START_POINTS ». Une autre série de sommets, appelés « END_POINTS » sont également donnés. Le problème est de trouver ce qui END_POINTS peut être atteint à partir de laquelle START_POINTS.

Voici un exemple:

START_POINTS: S1 S2 S3 S4 S5 S6 S7 ... 
END_POINTS  : E1 E2 E3 E4 E5 E6 E7 ... 

L'algorithme doit pouvoir dire ceci:

S1 can reach to E1, E2, E6
S2 can reach to E9, E10
S3 cannot reach any END_POINT
S4 can reach to .....
....

Certains des END_POINTS pourrait ne pas être atteint de toute point_départ.

Maintenant, la question est: Quelle est la façon la plus efficace de mettre en œuvre

J'ai essayé à partir de chaque point_départ un par un et de trouver les END_POINTS accessibles en utilisant la recherche en profondeur d'abord (ou BFS, cela ne change le plus d'exécution). Cependant, il faut beaucoup de temps, car il y a tellement de START_POINTS (il y a aussi beaucoup de END_POINTS).

La recherche peut être optimisé car il y a un énorme chevauchement entre les chemins tracés de START_POINTS. Il faut se rappeler que les chemins qui peuvent atteindre END_POINTS. Quel est le moyen le plus efficace pour y parvenir? Cela pourrait être un problème bien connu, mais je ne pouvais pas trouver une solution encore.

EDIT le 6 Jan:

J'ai essayé de mettre en œuvre l'idée de HighBandwidth (d'une manière similaire à ce que Keith Randall a proposé). Pour chaque nœud, si ce noeud est ne démarre pas ou le point final, connectez toutes les entrées aux sorties, puis retirez le noeud

foreach NODE in NODES
    Skip if NODE is START_POINT or END_POINT
    foreach OUTPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
    end
    foreach INPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
        foreach OUTPUT_NODE of NODE
            Connect INPUT_NODE to OUTPUT_NODE
        end
    end
    Remove NODE from NODES
end

Cela commence très vite et devient rapidement très lent, surtout parce que les comptes d'entrées / sorties des noeuds restants deviennent très grandes et imbriqués pour les boucles tue la performance. Toute idée comment il peut être plus efficace?

Answer 1

Il suffit de pruneau le graphique pour se débarrasser de tous les nœuds qui ne figurent pas dans les noeuds début ou la fin des nœuds, en les remplaçant par des arêtes de leurs noeuds entrants vers leurs cibles sortants. Une fois cela fait, passer par tous les autres noeuds (qui sont des noeuds début ou de fin) et ajouter des bordures de leurs noeuds entrants vers leurs noeuds sortants, sans supprimer ces nœuds. Dans quelques Djikstra comme itérations, vous devez être laissé avec le début pour mettre fin à bords.

Answer 2

Cela pourrait être exagéré, mais vous pouvez consulter Dijkstra . Je l'ai utilisé dans le passé lors de la création de mon propre table de routage des nœuds virtuels. Dans ce cas, tous les nœuds auraient une valeur de 1, ce qui signifie chaque noeud coûte le même Voyage sage.

Answer 3

Tout d'abord, exécutez une fortement connecté. Ensuite, contractez tous les composants connectés à un seul nœud. Effectuez ensuite une topologique sorte du graphique. Puis, en une seule passe, vous pouvez calculer qui commencent noeuds peuvent atteindre chaque nœud dans le graphe (initialiser chaque nœud de démarrage de l'ensemble {s}, puis effectuer l'union des bords entrants à chaque noeud dans l'ordre topologique).

Vous avez un problème potentiel que la réponse pourrait être aussi grand que # * # départ noeuds noeuds d'extrémité, qui peut être grand. Nous espérons que vous avez quelques grands CSC qui contractent à des nœuds individuels, car cela pourrait rendre la réponse beaucoup plus concis (tous les nœuds de départ dans le même SCC peut atteindre les mêmes lieux, si vous avez besoin que d'utiliser un représentant dans vos jeux).