Multigraph

Goal

Implement support in the graph data structure to handle a multigraph.

For some usecases this is very convenient and it can also improve the code used to load data:

Perhaps we should consider two steps in loading the network. Because duplicate edges are not allowed we prevent them by adding intermediate vertices along the edge shape, that's probably whats going wrong here. If we work in two steps we could greatly simplify this process:

• Load from OSM while allowing duplicate edges.
• Postprocess network to remove the duplicates.

This has only advantages:

• Performance should be better because it takes some work checking for duplicates and fixing on the fly when adding edges.
• This will also benefit the plan to keep orginal id's if needed along with vertices.
• The postprocessing code can be shared between IO.Osm and IO.Shape or any other future network loader, now that code it specific for each.

We also need to:

• Implement an algorithm to convert a multigraph into a simple graph because the routing code relies on this being the case.
• Make sure to check the type of the graph before routing or contracting to prevent routing bugs.

Approach

Unknown yet but a list could be:

• [x] Implement support for a multigraph.
  • [x] Enable support to add duplicate edges.
  • [x] Enable support enumerating duplicate edge.
  • [x] Make the edge-enumeration depend on the graph type, simple or multi.
  • [x] Add support for loops, edges with the same first and last vertex.
• [x] Implement a conversion method to remove loops and doubles to convert to simple.
• [x] Implement support for an algorithm to split overly long edges.
• [x] Check for graph type where needed.
  • [x] Check before contraction.
  • ([ ] Check before routing.)

Status

Done