boost::graph find the cycle
The following code http://ideone.com/MbvUI outputs 'false', why?
On Mon, 24 Sep 2012, tolik levchik wrote:
The following code http://ideone.com/MbvUI outputs 'false', why?
Your graph does not actually have a cycle. Here is a drawing of it: A ---> B | ^ | / | / | / | / | / v/ C In particular, notice that there is a topological order for the graph: A, C, B; all edges go forward in that order. -- Jeremiah Willcock
Yes, but it set bidirectionalS in adjacency_list. Doesn't it say that we could walk in both ways? 2012/9/24 Jeremiah Willcock <jewillco@osl.iu.edu>
On Mon, 24 Sep 2012, tolik levchik wrote:
The following code http://ideone.com/MbvUI **outputs 'false', why?
Your graph does not actually have a cycle. Here is a drawing of it:
A ---> B | ^ | / | / | / | / | / v/ C
In particular, notice that there is a topological order for the graph: A, C, B; all edges go forward in that order.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mon, 24 Sep 2012, tolik levchik wrote:
Yes, but it set bidirectionalS in adjacency_list. Doesn't it say that we could walk in both ways?
No -- it means that the edges are single-directional, but that you can find all edges into a particular vertex. You might want undirectedS, which means that edges don't have directions. -- Jeremiah Willcock
Ok, but then graph (A, B) also have cycles. Is that right too? 2012/9/24 Jeremiah Willcock <jewillco@osl.iu.edu>
On Mon, 24 Sep 2012, tolik levchik wrote:
Yes, but it set bidirectionalS in adjacency_list. Doesn't it say that we
could walk in both ways?
No -- it means that the edges are single-directional, but that you can find all edges into a particular vertex. You might want undirectedS, which means that edges don't have directions.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hm, if i understood you correctly then the following code should outputs false http://ideone.com/4NiqP, isn't it? 2012/9/24 Jeremiah Willcock <jewillco@osl.iu.edu>
On Mon, 24 Sep 2012, tolik levchik wrote:
Ok, but then graph (A, B) also have cycles. Is that right too?
Not if there is only one edge between A and B -- the same edge won't be considered twice in a cycle in an undirected graph.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mon, 24 Sep 2012, tolik levchik wrote:
Hm, if i understood you correctly then the following code should outputs false http://ideone.com/4NiqP, isn't it?
Yes, it should. -- Jeremiah Willcock
But it's not :0, also here in 'Cycle Graphs' http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/defEx.htm one of examples is a such graph and it also called cycle. 2012/9/24 Jeremiah Willcock <jewillco@osl.iu.edu>
On Mon, 24 Sep 2012, tolik levchik wrote:
Hm, if i understood you correctly then the following code should outputs
false http://ideone.com/4NiqP, isn't it?
Yes, it should.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mon, 24 Sep 2012, tolik levchik wrote:
But it's not :0, also here in 'Cycle Graphs' http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/defEx.htm one of examples is a such graph and it also called cycle.
It looks like you might be seeing the issue talked about in the back_edge section of <URL:http://www.boost.org/doc/libs/1_51_0/libs/graph/doc/DFSVisitor.html>. You might also want to look at the undirected_dfs function. -- Jeremiah Willcock
Thank you! 2012/9/24 Jeremiah Willcock <jewillco@osl.iu.edu>
On Mon, 24 Sep 2012, tolik levchik wrote:
But it's not :0, also here in 'Cycle
Graphs' http://www.personal.**kent.edu/~rmuhamma/** GraphTheory/MyGraphTheory/**defEx.htm<http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/defEx.htm> one of examples is a such graph and it also called cycle.
It looks like you might be seeing the issue talked about in the back_edge section of <URL:http://www.boost.org/doc/**libs/1_51_0/libs/graph/doc/** DFSVisitor.html<http://www.boost.org/doc/libs/1_51_0/libs/graph/doc/DFSVisitor.html>>. You might also want to look at the undirected_dfs function.
-- Jeremiah Willcock
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Yes it is, sorry for dumb questions. 2012/9/24 tolik levchik <endight@gmail.com>
Ok, but then graph (A, B) also have cycles. Is that right too?
2012/9/24 Jeremiah Willcock <jewillco@osl.iu.edu>
On Mon, 24 Sep 2012, tolik levchik wrote:
Yes, but it set bidirectionalS in adjacency_list. Doesn't it say that we
could walk in both ways?
No -- it means that the edges are single-directional, but that you can find all edges into a particular vertex. You might want undirectedS, which means that edges don't have directions.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
Jeremiah Willcock
-
tolik levchik