search

drewnoakes / dependency-analyser

Shows the dependencies between .NET projects and assemblies as a graph.
https://drewnoakes.com/code/dependency-analyser/
GNU Lesser General Public License v3.0
46 stars 5 forks source link

Add option to remove implied dependencies #16

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago

Consider a graph of dependencies:

a -> b
a -> c
b -> c

The direct link from a->c is implied via a->b->c.

Add an option to the UI that removes dependencies which are implied transitively.

This blog post shows the benefit this can have on complex diagrams:

http://mg.pov.lt/blog/simplifying-dependency-graphs.html

Original issue reported on code.google.com by drewnoakes on 24 Mar 2014 at 9:54

jeremysimmons commented 9 years ago

Need to determine if the WinGraphViz component supports tred

drewnoakes commented 9 years ago

Seems that tred is actually open source:

http://opensource.apple.com/source/graphviz/graphviz-622/graphviz/tools/src/tred.c

The algorithm looks simple enough -- though might get complex in space/time for large graphs. I'd think taking a stab at this manually would be a fun little project.

jeremysimmons commented 9 years ago

Tree is part of graphviz. I was hoping the com dll you started with already supported this module...

drewnoakes commented 9 years ago

Don't know if it's in that library.

If not: https://en.m.wikipedia.org/wiki/Transitive_reduction

On Fri, 16 Oct 2015 04:34 Jeremy Simmons notifications@github.com wrote:

Tree is part of graphviz. I was hoping the com dll you started with already supported this module...

— Reply to this email directly or view it on GitHub https://github.com/drewnoakes/dependency-analyser/issues/16#issuecomment-148590306 .

drewnoakes commented 9 years ago

I implemented transitive reduction on the DependencyGraph class in 845760c21397c4ab79bf2adb2062873f7ec48872.

Currently it's not wired up in the UI. That'll need some thinking, as filtering should be applied before the reduction, so that relationships are not lost when intermediary nodes are filtered out.

Before:

dependencygraph-before

After:

dependencygraph-after

jeremysimmons commented 9 years ago

nice job. i love the result. for my purposes, filter then simplify is fine. if i loose an edge because i filtered, thats on me.

did you code this up from scratch ? i did not see any pseudo code in the referenced wikipedia article.

Sent from my iPhone

On Oct 17, 2015, at 2:38 PM, Drew Noakes notifications@github.com wrote:

I implemented transitive reduction on the DependencyGraph class in 845760c.

Currently it's not wired up in the UI. That'll need some thinking, as filtering should be applied before the reduction, so that relationships are not lost when intermediary nodes are filtered out.

Before:

After:

— Reply to this email directly or view it on GitHub.

drewnoakes commented 9 years ago

if i loose an edge because i filtered, thats on me.

If this is to be a useful app for others, it shouldn't have any surprises in it. To surface this reduction as a feature, I think it really needs to happen after filtering.

did you code this up from scratch?

Sure. It took a few tries to make it work properly in the face of cycles as the standard algorithms assume a DAG, and .NET assemblies actually can have circular references.

jeremysimmons commented 9 years ago

I'm fine going either direction, so long as the expected behavior is stated.

Congratulations on coding from scratch. You're obviously getting more sleep than I am and not suffering from 'daddy brain'.

jeremysimmons commented 9 years ago

I think we're talking about the same thing here.

What I said.

for my purposes, filter then simplify is fine.

What you said

I think it really needs to happen after filtering.

Same thing. Filter then Simplify.

Maybe a UI that allows for clicking on the edges or nodes and clicking 'delete' would scratch a certain kind of itch for folks?