4
$\begingroup$

Consider a list (edge) as

edge = {{{1, 1}, {1, 2}}, {{1, 1}, {1, 3}}, {{1, 1}, {1, 4}}, {{1, 1}, {2, 
   1}}, {{1, 1}, {2, 4}}, {{1, 1}, {3, 4}}, {{1, 1}, {4, 1}}, {{1, 
   1}, {4, 4}}, {{1, 2}, {1, 3}}, {{1, 2}, {1, 4}}, {{1, 2}, {2, 
   1}}, {{1, 2}, {2, 4}}, {{1, 2}, {3, 4}}, {{1, 2}, {4, 1}}, {{1, 
   2}, {4, 4}}, {{1, 3}, {1, 4}}, {{1, 3}, {2, 1}}, {{1, 3}, {2, 
   4}}, {{1, 3}, {3, 4}}, {{1, 3}, {4, 1}}, {{1, 3}, {4, 4}}, {{1, 
   4}, {2, 1}}, {{1, 4}, {2, 4}}, {{1, 4}, {3, 4}}, {{1, 4}, {4, 
   1}}, {{1, 4}, {4, 4}}, {{2, 1}, {2, 4}}, {{2, 1}, {3, 4}}, {{2, 
   1}, {4, 1}}, {{2, 1}, {4, 4}}, {{2, 4}, {3, 4}}, {{2, 4}, {4, 
   1}}, {{2, 4}, {4, 4}}, {{3, 4}, {4, 1}}, {{3, 4}, {4, 4}}, {{4, 
   1}, {4, 4}}};

Each pair (e.g. {{1, 1}, {1, 2}}) indicates the existence of an edge between the corresponding points. Now I wish to find the set of connected points from edge.

For example, from the given set, I can manually find

set1= {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 
   1}, {2, 4}, {3, 4}, {4, 1}, {4, 4}}

Basically, if there exists a path between {1,1} and {x,y}, {x,y} should be included in set1. I wish to find all such sets which are mutually exclusive (disjoint) and all the vertices within any set are connected.

How can I do this for a large set of points (edge is just a small subset)?

$\endgroup$
3
  • 4
    $\begingroup$ ConnectedComponents[UndirectedEdge @@@ edge]? $\endgroup$
    – Szabolcs
    Commented Feb 6, 2018 at 11:41
  • $\begingroup$ For this dataset, it does give exactly the result you said you needed. If it is not connected components that you need, can you update the question and clarify? $\endgroup$
    – Szabolcs
    Commented Feb 6, 2018 at 15:53
  • $\begingroup$ @Szabolcs Sorry for my earlier comment. It works and works perfectly. I have deleted that comment. $\endgroup$
    – user36426
    Commented Feb 6, 2018 at 18:32

1 Answer 1

4
$\begingroup$
ConnectedComponents[UndirectedEdge @@@ edge]

{{{1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 4}, {3, 4}, {4, 1}, {4, 4}}}

In general, you can use a list or a pattern of vertices as the second argument of ConnectedComponents to get the components that contain at least one vertex from the specified list of vertices. In OP's example, since there is a single connected component and it contains the vertex {1,1}, we get the same result with ConnectedComponents[UndirectedEdge @@@ edge, {{1,1}}].

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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