Group Abstract Group Abstract

Message Boards Message Boards

DepthFirstScan to work properly on Graph

GROUPS:
This is the raw data for the graph
matr1 = {{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 // ColumnForm

Here 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
POSTED BY: Gregory Fridman
Answer
2 months 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 BY: Daniel Lichtblau
Answer
2 months 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.
POSTED BY: Gregory Fridman
Answer
2 months ago