search

nkiru-ede / MavenNetworkStudy

Other
0 stars 0 forks source link

Compute transitive closures for GAV/GA/G graphs #12

Open jensdietrich opened 2 weeks ago

jensdietrich commented 2 weeks ago

Add additional processing step (with tests, readme description etc) to compute the TC of those three graphs, create plots for vertex and edge counts.

nkiru-ede commented 6 days ago

done @jensdietrich

jensdietrich commented 5 days ago

@nkiru-ede I just reviewed this -- some questions:

  1. the code in /Transitive_deps.py looks pretty complex, did you write this from scratch ? Is there a lib that can do this (I think boost can be used from python - link has TC function) ?
  2. I cannot see any tests -- we always need them !
  3. the script seems to operate on the input graph - we would need this using any directed graph as input so that we can compute this for GA and G graphs as well
nkiru-ede commented 5 days ago

yes, it looks complex because I firstly identified and removed cycles/loops before using topological sorting to get the transitive dependencies (this is done to a depth on 10) - as I was getting hundreds of millions of relationships otherwise as it kept going into endless loops.

There are algorithms such as Floyd-Warshall, Tarjan, etc. I tried them but they were very memory intensive and kept crashing because of the size of the graph.

jensdietrich