Timeline for Remove redundant dependencies from a directed acyclic graph
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:55 | history | edited | CommunityBot |
replaced http://mathematica.stackexchange.com/ with https://mathematica.stackexchange.com/
|
|
| Oct 10, 2013 at 15:23 | comment | added | asterix314 |
@halmir yes exactly. See my answer. I got rid of all logical operations (I didn't know Unitize so i used Sign instead).
|
|
| Oct 10, 2013 at 14:42 | comment | added | halmir | @asterix314 you don't need to define your dot with Inner. You could do the following and it makes code much faster with sparse array: reduce3[x_] := BitAnd[x, 1 - BitOr @@ Drop[FixedPointList[Unitize[Dot[#1, x]] &, Unitize[Dot[x, x]]], -2]] | |
| Oct 10, 2013 at 8:19 | comment | added | asterix314 | OK I'll put it up later after I learn some formating basics ... | |
| Oct 10, 2013 at 7:57 | comment | added | István Zachar | @asterix314 Still I suggest to put it up as an answer as it is really concise and reflects the nice synergies of matrix operations on graphs. | |
| Oct 10, 2013 at 7:42 | comment | added | asterix314 | @IstvánZachar Sorry the -2 is for Drop[] actually, because the last 2 elements in the FixedPointList[] are all 0s. Without the Drop the code should also work though. It is worth mentioning that the run time of this concise solution is not so good as yours. | |
| Oct 10, 2013 at 6:53 | comment | added | István Zachar |
@asterix314 Nice solution, I think you should make that an individual answer! Just to note, the last argument (-2) for FixedPointList doesn't seem to work on my machine, drops error messages. Without it the code is fine.
|
|
| Oct 10, 2013 at 6:11 | comment | added | asterix314 | Here is a more concise formulation based on @IstvánZachar's method: Let A be the adjacency matrix of the original graph. A represents also the single hop reachablility, and A^k for k hops, etc. Here we use And for Times and Or for Plus. The reachability matrix of more than 1 hop is thus S = A^2 + A^3 + ... + A^(n-1). The reduced adjacency matrix is thus And[A, !S]. Or in code: reduce2[x_] := Block[{CenterDot = Function[{a, b}, Inner[BitAnd, a, b, BitOr]]}, BitAnd[x, 1 - BitOr @@ Drop[FixedPointList[CenterDot[#, x] &, CenterDot[x, x], -2]]]] | |
| Oct 8, 2013 at 15:13 | history | edited | István Zachar | CC BY-SA 3.0 |
added 1501 characters in body
|
| Oct 8, 2013 at 14:05 | comment | added | István Zachar |
@asterix314 Yes, Simplify could be a huge bottleneck. If you really have to work on huge graphs, I'll try to come up with a more direct approach that only uses adjacency matrices. That could be a few magnitudes faster than working on Graph objects. Thanks for the accept.
|
|
| Oct 8, 2013 at 12:28 | comment | added | asterix314 | I'm going to accept this for now as it wins in terms of performance. The run time of @Kubma's Simplfy-based algorithm is quite intractable when the number of edges gets large, say 100. | |
| Oct 8, 2013 at 12:16 | vote | accept | asterix314 | ||
| Oct 18, 2013 at 14:01 | |||||
| Oct 8, 2013 at 10:32 | comment | added | István Zachar | @Kuba Oh, sure, that buglike feature got me once. Quite annoying! | |
| Oct 8, 2013 at 10:23 | comment | added | Kuba |
Or rather pay attention to 1 an 0 which are interpreted by logical functions ;) Implies["a", 1] // Simplify
|
|
| Oct 8, 2013 at 10:12 | comment | added | István Zachar |
@Kuba It removes the 1 because Simplify@Implies[(3 => 1) && (3 => 2), 2 => 1] returns True, though it shouldn't for a graph (if you have edges 3->1 and 3->2 you don't necessarily have 2->1)!
|
|
| Oct 8, 2013 at 10:02 | comment | added | István Zachar | @Kuba It should keep 1. I still cannot figure out whether there is always one exact reduction or it could depend on the order edges are removed. | |
| Oct 8, 2013 at 10:01 | history | edited | István Zachar | CC BY-SA 3.0 |
added 184 characters in body
|
| Oct 8, 2013 at 9:55 | comment | added | Kuba |
Strange, my reduce drops 1 and leaves 5->4->3->2 for the last case of yours.
|
|
| Oct 8, 2013 at 9:54 | history | edited | István Zachar | CC BY-SA 3.0 |
deleted 29 characters in body
|
| Oct 8, 2013 at 9:46 | history | edited | István Zachar | CC BY-SA 3.0 |
deleted 189 characters in body
|
| Oct 8, 2013 at 9:40 | history | answered | István Zachar | CC BY-SA 3.0 |