Feature request: identify connected components of undirected graph

[osrf-migration]

Original report (archived issue) by Steve Peters (Bitbucket: Steven Peters, GitHub: scpeters).

---

It could return a vector of undirected sub graphs?

• https://en.wikipedia.org/wiki/Connected_component_(graph_theory)

[osrf-migration]

Original comment by Steve Peters (Bitbucket: Steven Peters, GitHub: scpeters).

---

The BreadthFirstSort or DepthFirstSort should be useful for this.

[osrf-migration]

Original comment by Steve Peters (Bitbucket: Steven Peters, GitHub: scpeters).

---

I suppose a ConnectedGraph could be a derived type of Graph?

[osrf-migration]

Original comment by Steve Peters (Bitbucket: Steven Peters, GitHub: scpeters).

---

My motivation is for identifying connected components of a directed graph (see also #80), but I think it's easier to implement with the Sort functions on an undirected graph.

[osrf-migration]

Original comment by Steve Peters (Bitbucket: Steven Peters, GitHub: scpeters).

---

• changed title from "Feature request: identify connected components of undirected graph" to "Feature request: identify connected components of directed graph"

retitled to address directed graphs, which may be harder, but it's what I'm interested in

[osrf-migration]

Original comment by Carlos Agüero (Bitbucket: caguero, GitHub: caguero).

---

It's clear to me how connected components are defined for undirected graphs but no so evident with directed graphs.

E.g.: Imagine this graph with 5 vertices (v1, v2, v3, v4, v5) and 2 edges e1: (v1)->(v2) and e2: (v4)->(v5):

(v1)->(v2) (v3) (v4)->(v5)

How many connected components does this graph have? 3?

From v1's perspective, v2 is in its same component. However, from v2's perspective, v1 might be in a different component, as it cannot be reached from v2.

[osrf-migration]

Original comment by Steve Peters (Bitbucket: Steven Peters, GitHub: scpeters).

---

copied from a comment in issue 80:

"For example, if we represent a multibody kinematic chain as a directed graph, it can be useful to analyze as an undirected graph in order to identify connected components (see #81), which are also known as islands in Open Dynamics Engine."

A multibody "island" is based on connectivity in an undirected sense; the parent-child direction doesn't matter, which is different than other applications I suppose. My main concern is not losing edge information by converting back and forth between directed and undirected.

[osrf-migration]

Original comment by Steve Peters (Bitbucket: Steven Peters, GitHub: scpeters).

---

Maybe we could convert to an undirected graph with #80, then identify the connected vertices, then copy the directed edges for those vertices from the original directed graph to a sub-graph. Maybe that will work?

[osrf-migration]

Original comment by Steve Peters (Bitbucket: Steven Peters, GitHub: scpeters).

---

• changed title from "Feature request: identify connected components of directed graph" to "Feature request: identify connected components of undirected graph"

I changed title back to focus on undirected graph, since I think the following could be done for the use case I mentioned:

• convert directed graph to undirected graph (with #80)
• partition undirected graph into subgraphs consisting of connected components (this issue)
• partition original directed graph into sub-graphs consisting of the same vertices as the undirected connected subgraphs, with directed edges copied from original graph

[osrf-migration]

Original comment by Carlos Agüero (Bitbucket: caguero, GitHub: caguero).

---

See pull request #190.

[osrf-migration]

Original comment by Steve Peters (Bitbucket: Steven Peters, GitHub: scpeters).

---

• changed state from "new" to "resolved"

pull request #190