1
|
4553 Views
|
2 Replies
|
3 Total Likes
View groups...
Share

DepthFirstScan to work properly on Graph

Posted 11 years ago
 This is the raw data for the graphmatr1 = {{0, 0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0,0, 1},          {0, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0}};g = AdjacencyGraph[matr1, VertexLabels -> "Name", ImagePadding -> 10]That's what gives me a built-in function. If you try a littl it's easy to get all the paths which have 4 vertices.Reap[DepthFirstScan[g, #, {"ForwardEdge" -> Sow, "BackEdge" -> Sow,        "FrontierEdge" -> Sow, "CrossEdge" -> Sow}]][[2]] & /@ Range@Length@matr1 // ColumnFormHere is the 2nd answer that I got with my own function of in-depth-search (each path passes through 4 vertices, ie it consists of 3 edges): {  {1, 5, 1, 5},  {1, 5, 1, 6},  {1, 6, 1, 5},  {1, 6, 1, 6},  {1, 6, 2, 6},  {2, 6, 1, 5},  {2, 6, 1, 6},  {2, 6, 2, 6}, {3, 7, 3, 7}, {5, 1, 5, 1}, {5, 1, 6, 1}, {5, 1, 6, 2}, {6, 1, 5, 1}, {6, 1, 6, 1}, {6, 1, 6, 2}, {6, 2, 6, 1}, {6, 2, 6, 2}, {7, 3, 7, 3}}Of course, I want DepthFirstScan to gave the same result. And I do not know how to make it. Any advice?Thanks,Gregory
2 Replies
Sort By:
Posted 11 years ago
 Vertices 3 and 7 are only connected to each other. I do not see how a depth-first scan would have a path of length four involving those vertices.Danny
Posted 11 years ago
 I got this answer (paths) using my own recursive function with the name FindAllPaths (a brilliant one, is it not?). And I just wonder if I can get the same result using built-in graph functions. In my function I have to introduce two additional vertices, a source and a sink, and then I search for all paths from the former to the latter.