search

gazebosim / gz-math

General purpose math library for robot applications.
https://gazebosim.org/libs/math
Apache License 2.0
54 stars 67 forks source link

Feature request: helper function to convert DirectedGraph to UndirectedGraph #80

Closed osrf-migration closed 5 years ago

osrf-migration commented 7 years ago

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

Should this be a static function in Graph.hh or something in GraphAlgorithms.hh?

It should keep the same Vertex Id's and Edge Id's.

osrf-migration commented 7 years ago

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

osrf-migration commented 7 years ago

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

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.

osrf-migration commented 7 years ago

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

What about the weight of the edges?

E.g.: There are two vertices v1 and v2 and two edges e1: (v1)->(v2) and e2: (v2)->(v1). e1 has weight 2.0 and e2 has weight 4.0. If we convert it to an undirected graph, the vertices don't change and there's only one edge e: (v1)-(v2). But what value do we assign for the weight?

Proposal: Maybe we could offer a function as an argument that the user should pass (or a lambda) that given the two vertices of the undirected edge, it assigns the weight.

osrf-migration commented 7 years ago

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

That's a good point; I hadn't thought about the edge weights, or that edges would be lost. My real goal is identifying connected components of a directed graph, but I expressed parts of that as this issue and #81, since I thought this would be easiest by converting first to an undirected graph, computing connected components, then converting back to a directed graph. If edge information is lost in that process, then maybe that isn't so helpful.

I could re-title #81 to be about directed graphs and then close this, unless someone thinks it's a useful feature.

osrf-migration commented 7 years ago

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

I talked myself out of closing #81.

Do the edges need to be merged? I think an undirected graph can have duplicate edges between the same vertices.

osrf-migration commented 7 years ago

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

I just added a test case for an undirected graph with duplicate edges between the same vertices in pull request #189. I think we might not need to merge edges / weights for this functionality.

osrf-migration commented 7 years ago

Original comment by Nate Koenig (Bitbucket: Nathan Koenig).

I think you're right. There is no need to merge multiple edges.

osrf-migration commented 5 years ago

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

see pull request #332

osrf-migration commented 5 years ago

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

pull request #332