7
$\begingroup$

I'm trying to determine how I can test if a path exists from one side of a graph to another as efficiently as possible. If I have the Lines given by:

coords={Line[{{0, 2}, {0, 3}}], Line[{{0, 3}, {0, 4}}], Line[{{1, 0}, {1, 1}}], Line[{{1, 2}, {1, 3}}], Line[{{1, 3}, {1, 4}}], Line[{{2, 0}, {2, 1}}], Line[{{2, 1}, {2, 2}}], Line[{{2, 2}, {2, 3}}], Line[{{2, 3}, {2, 4}}], Line[{{3, 0}, {3, 1}}], Line[{{3, 3}, {3, 4}}], Line[{{4, 0}, {4, 1}}], Line[{{4, 1}, {4, 2}}], Line[{{4, 3}, {4, 4}}], Line[{{0, 0}, {1, 0}}], Line[{{0, 2}, {1, 2}}], Line[{{0, 3}, {1, 3}}], Line[{{0, 4}, {1, 4}}], Line[{{1, 1}, {2, 1}}], Line[{{1, 2}, {2, 2}}], Line[{{1, 3}, {2, 3}}], Line[{{2, 0}, {3, 0}}], Line[{{2, 1}, {3, 1}}], Line[{{2, 3}, {3, 3}}], Line[{{2, 4}, {3, 4}}], Line[{{3, 2}, {4, 2}}], Line[{{3, 4}, {4, 4}}]}

Which can easily be displayed by Graphics[coords], is there an easy way to test if I can create a path from one side of the graph to the other? That is, a coordinate that starts with y=0 to a point that has y=4? I realize this can be done easily by eye, but I have code that generates the coords and I want to be able to do this in masse. Thanks!

$\endgroup$
3
  • 1
    $\begingroup$ Your data isn't technically a Graph, but it can be converted into one with a suitable script. Once you've done that, you can use the FindPath function to determine if a path exists. I don't know how efficient FindPath is, but I imagine it should be able to handle very large graphs quickly, so performance shouldn't be an issue. $\endgroup$ Nov 27 '14 at 2:45
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$
    – user9660
    Nov 27 '14 at 3:05
  • $\begingroup$ Thanks for the responses. Is there an easy way to convert the points to a graph? I'm not sure what the best way to do that is. I think that combining that with the method from user2903966 would be the ideal method. $\endgroup$
    – Mark
    Nov 27 '14 at 3:05
7
$\begingroup$
edges = coords /. Line[{a_, b_}] :> UndirectedEdge[a, b];
g = Graph[edges];
starts = VertexList[g, {_, 0}];
ends = VertexList[g, {_, 4}];
Intersection[Join @@ ConnectedComponents[g, starts], ends] != {}

(*True*)

And we can show all of them ...

g = Graph[edges];
g1 = SetProperty[g, VertexCoordinates -> VertexList@g];
paths = DeleteCases[FindShortestPath[g1, #1, #2] & @@@ Tuples[{ends, starts}], {}];
uds = UndirectedEdge @@@ Partition[#, 2, 1] & /@ paths;
Partition[HighlightGraph[g1, #, GraphHighlightStyle -> {Red, "Thick"}] & /@  uds, 4] // Grid

Mathematica graphics

$\endgroup$
1
  • $\begingroup$ Very nice indeed ! $\endgroup$
    – chris
    Dec 1 '14 at 14:24
1
$\begingroup$

So in fact, this is a graph search problem, Right? The normal approaches is to use Depth-First-Search(DFS) or Breadth-First-Search(BFS) to test connected relation of two points.

For example, if you want to test whether coordinate (3,0) is connected to coordinate (2, 4), you can just use DFS or BFS to do the test.

I think the trick point in your problem is that you want to test whether there is a path from like y = 0 to y = 4. For this scenario, there is a tricky method to do this. Add two fake points, we call them f1 and f2, make edges from f1 to every points of y = 0 with length 0, and also make edges(also of length 0) from every points from y = 4 to f2. And then test the connected relation(you can use FindShortestPath function) of f1 and f2. If it is connected, there is definitively a path from y = 0 to y = 4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.