Graph::InDegree and IncidentsTo are slower than OutDegree and IncidentsFrom

[osrf-migration]

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

---

The Graph class uses an adjacency list internally to assist with computations. This is stored internally as a map of Edges departing from each Vertex. This allows the IncidentsFrom and OutDegree functions to look up a list of edges directly given a vertex id.

There is no equivalent data structure for storing a list of edges arriving at a given vertex, however. This means that IncidentsTo and InDegree need to iterate over all vertices and then all edges to see if any of those edges arrive at the specified vertex.

I've added a test that illustrates this performance difference for graphs with large numbers of nodes in branch edgeless_performance_test (a4edbb1). These test cases instantiates a graph with many vertices and no edges, then call InDegree and OutDegree for each vertex, expecting 0, since there are no edges. The test case that calls InDegree is much slower than OutDegree:

# DirectedEdge
[ RUN      ] GraphTestFixture/0.EdgelessInDegree
[       OK ] GraphTestFixture/0.EdgelessInDegree (936 ms)
[ RUN      ] GraphTestFixture/0.EdgelessOutDegree
[       OK ] GraphTestFixture/0.EdgelessOutDegree (8 ms)

# UndirectedEdge
[ RUN      ] GraphTestFixture/1.EdgelessInDegree
[       OK ] GraphTestFixture/1.EdgelessInDegree (1270 ms)
[ RUN      ] GraphTestFixture/1.EdgelessOutDegree
[       OK ] GraphTestFixture/1.EdgelessOutDegree (8 ms)

For cases when a graph with directed edges represents the kinematics of a multibody system with vertices as Links and edges as Joints, the IncidentsTo function is equivalent to GetParentJoints, which is used in many places in gazebo physics.

This is an issue of performance not correctness, so it may not be a priority, but I wanted to mention it.

[osrf-migration]

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

---

Thanks for bringing this up and the detail description. See pull request #188.

[osrf-migration]

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

---

• changed state from "new" to "resolved"

pull request #188