search

loot / libloot

A C++ library for accessing LOOT's metadata and sorting functionality.
GNU General Public License v3.0
32 stars 12 forks source link

Experiment with adding specific edges depth-first to reduce total number of edges #58

Closed Ortham closed 4 years ago

Ortham commented 5 years ago

At the moment, building the plugin graph involves a step like:

for plugin in plugins:
  add master flag edges
  add load after edges
  add master edges
  add requirement edges
  //etc.

Try rewriting that step to recursively run the loop for each plugin that an edge is added going to, so that the graph is built depth-first. Doing this should result in longer paths existing earlier, and being created in a way that allows the paths being created to be cached relatively efficiently, so more duplicate paths can be avoided, cutting down on the number of edges in the graph.

Ortham commented 4 years ago

This doesn't have much of an impact (1% edge reduction) because the graph is very wide and shallow, so the longest path is still only a few vertices long.