trabalhando com grafos e matriz em php

[aguiaverde]

Olá,

Sou novata em PHP, alguém pode me ajudar por favor!?

Estou a desenvolver uma aplicação que terei que representar todos os percursos possíveis de um grafo de precedências.

Estive a pesquisar, mas até agora a única coisa que encontrei que é mais parecida com o que preciso fazer é usar o algoritmo DFS (Depth First Search ) para percurso em profundidade, mas o que acontece é que esse algoritmo dá apenas para ter um dos percursos possíveis, mas eu preciso de todos os percursos possíveis e sem repetição.

Tenho a seguinte matiz de precedências:

0     L1   L2    L3  L4   L5   L6
L1    0    1     1    1    1    1 
L2    0    0     0    1    1    1
L3    0    0     0    1    1    1
L4    0    0     0    0    0    1
L5    0    0     0    0    0    0
L6    0    0     0    0    0    0

1 Significa que o elemento que está na primeira linha da coluna correspondente deve aparecer no percurso, depois do elemento que está na primeira coluna da linha correspondente ao 1.

Explicando melhor,

L2 deve aparecer depois do L1;

L3 deve aparecer depois do L1;

L4 deve aparecer depois do L1, do L2 e do L3;

L5 deve aparecer depois do L1, do L2 e do L3;

L6 deve aparecer depois do L1, do L2, do L3 e do L4.

Sendo assim tenho os seguintes percursos possíveis:

L1 -> L2 -> L3 -> L4 -> L5 -> L6

L1 -> L3 -> L2 -> L4 -> L5 -> L6

L1 -> L2 -> L3 -> L4 -> L6 -> L5

L1 -> L3 -> L2 -> L4 -> L6 -> L5

L1 -> L2 -> L3 -> L5 -> L4 -> L6

L1 -> L3 -> L2 -> L5 -> L4 -> L6

Alguém pode me dar alguma dica de algum algoritmo que posso utilizar para esse efeito ou de como implementar isso em PHP. Estou mesmo aflita e preciso disto pronto com alguma urgência.

Todas as sugestões são bem vidas.

Obrigada