jeron@irisa.fr (jeron) (04/09/91)
I am looking for an algorithm (and not a naive one)
of graph theory which deals with circuits in directed graphs.
I know a naive algorithm but I am looking for an efficient one
but that seems to be more difficult.
The question is:
Given a directed graph G=(V,E) and a subset W of V,
find an algorithm which tells whether every circuit of G contains
at least one vertice w in W.
Now this problem is equivalent to:
Given a directed graph G=(V,E) and a subset W of V,
find an algorithm which tells whether every elementary circuit of G contains
at least one vertice w in W.
I can simplify this problem if I first build the strongly connected
components by Tarjan's algorithm. The problem is now:
Given a strongly connected directed graph G=(V,E) and a subset W of V,
find an algorithm which tells whether every circuit of G contains
at least one vertice w in W.
I know that a depth first algorithm in which you only detect circuits
can perform this. But you can travel some circuits several time.
Example:
G : 0->1, 0->4
1->2, 1->4
2->3, 2->5
3->6
4->5
5->6, 5->0
6->1
0
The depth first algorithm travels / \
the following tree where (v) means that / \
a loop is detected. / \
1 4
We can see that there are 9 detected circuits: / \ |
1236 0125 1256 0145 1456 / \ |
045 6123 5612 4561 2 4 5
/ | | / \
But there are only 6 different ones: / | | / \
1236 0125 1256 0145 1456 045 3 5 5 (0) 6
/ / \ / \ |
/ / \ / \ |
6 (0) 6 (0) 6 1
/ | | / \
/ | | / \
(1) (1) (1) 2 (4)
/ \
/ \
3 (5)
|
|
(6)
Thus I would like to find an algorithm which detects every elementary circuit
once and only once.
I found no pointer to this in the literature but I think that it is possible.
An other interesting question is whether there exists and how can I find
a subset S of (elementary) circuits such that every elementary circuit has
a vertice in W if and only if every circuit of S has one.
In the example above, it is not necessary to test the circuit 0145 if
045 has already been tested:
if there is a v in W in 045 then it is also in 0145.
If you have any idea about those questions or pointers to articles or books,
please contact me by e-mail to:
jeron@irisa.irisa.fr
------------------------------------------------------------------------------
Jeron Thierry
IRISA Campus de Beaulieu
35000 RENNES, FRANCE
e-mail: jeron@irisa.irisa.fr
------------------------------------------------------------------------------sethb@Morgan.COM (Seth Breidbart) (04/11/91)
In article <1991Apr9.161805.6764@irisa.fr> jeron@irisa.fr (jeron) writes: >I am looking for an algorithm (and not a naive one) >of graph theory which deals with circuits in directed graphs. >The question is: >Given a directed graph G=(V,E) and a subset W of V, >find an algorithm which tells whether every circuit of G contains >at least one vertice w in W. Why not just delete W from G, and check for circuits in the remaining graph? I realize that that's probably naive, but at least it's efficient :-). Seth sethb@fid.morgan.com
karsten@tfl.dk (04/11/91)
In article <1991Apr9.161805.6764@irisa.fr>, jeron@irisa.fr (jeron) writes: > I am looking for an algorithm (and not a naive one) > of graph theory which deals with circuits in directed graphs. > I know a naive algorithm but I am looking for an efficient one > but that seems to be more difficult. > > > The question is: > Given a directed graph G=(V,E) and a subset W of V, > find an algorithm which tells whether every circuit of G contains > at least one vertice w in W. > > Now this problem is equivalent to: > Given a directed graph G=(V,E) and a subset W of V, > find an algorithm which tells whether every elementary circuit of G contains > at least one vertice w in W. > > I can simplify this problem if I first build the strongly connected > components by Tarjan's algorithm. The problem is now: > Given a strongly connected directed graph G=(V,E) and a subset W of V, > find an algorithm which tells whether every circuit of G contains > at least one vertice w in W. > > I know that a depth first algorithm in which you only detect circuits > can perform this. But you can travel some circuits several time. > > Example: > G : 0->1, 0->4 > 1->2, 1->4 > 2->3, 2->5 > 3->6 > 4->5 > 5->6, 5->0 > 6->1 > > 0 > The depth first algorithm travels / \ > the following tree where (v) means that / \ > a loop is detected. / \ > 1 4 > We can see that there are 9 detected circuits: / \ | > 1236 0125 1256 0145 1456 / \ | > 045 6123 5612 4561 2 4 5 > / | | / \ > But there are only 6 different ones: / | | / \ > 1236 0125 1256 0145 1456 045 3 5 5 (0) 6 > / / \ / \ | > / / \ / \ | > 6 (0) 6 (0) 6 1 > / | | / \ > / | | / \ > (1) (1) (1) 2 (4) > / \ > / \ > 3 (5) > | > | > (6) > > Thus I would like to find an algorithm which detects every elementary circuit > once and only once. > I found no pointer to this in the literature but I think that it is possible. > > An other interesting question is whether there exists and how can I find > a subset S of (elementary) circuits such that every elementary circuit has > a vertice in W if and only if every circuit of S has one. > In the example above, it is not necessary to test the circuit 0145 if > 045 has already been tested: > if there is a v in W in 045 then it is also in 0145. > If you have any idea about those questions or pointers to articles or books, > please contact me by e-mail to: > > jeron@irisa.irisa.fr > ------------------------------------------------------------------------------ > Jeron Thierry > IRISA Campus de Beaulieu > 35000 RENNES, FRANCE > e-mail: jeron@irisa.irisa.fr > ------------------------------------------------------------------------------ HI, The probelm is equivalent to deciding whether or not there is a circuit in the graph G(V-W,E') where E' is the subset of edges from E that connect vertices in V-W. You don't need Tarjan's algorithm for that, though it will of course do the job. You can simply start by marking all vertices as not visited. Then you make a deeb first search. When you visit a vertice you check that the node is not currently being visited, mark it as being currently visited, traverse all vertices that can be reached from the current vertice, and finaly mark the current vertice as having been visited. You will notice that the described algorithm is a cut down version of Tarjan's algorithm. Karsten Nyblad TFL, A Danish Telecommunication Research Laboratory E-mail: karsten@tfl.dk