new graph algorithms
Locked
new graph algorithms
 
|
Hi,
A few days ago, I added new graph algorithms into MooseAlgos but I did not communicate about that. I added 2 complementary algorithms: - MalGraphReducer : it takes as input a graph and ouputs a graph without circuits. Nodes forming a circuit (or cycle if you prefer) are merged into a single node. A merge node has a reference to merged nodes. It uses the MalTarjan algorithm. - MalTopologicalSorting : the well known graph sorting algorithm that can only be applied on graphs without circuits (cycles). the latter could be useful for some layouting strategies of graphs for example. Regards, Christophe. _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: new graph algorithms
|
|
Re: new graph algorithms
|
|
hi,
Le 8 avr. 2015 à 17:59, Alexandre Bergel a écrit : > Hi! > > Can you provide some (graphical) illustrations about the graph algo? I added 2 examples method on the MalGraphReducer class to easily display the graph with roassal but the default layouting is not very good. The best I got was with the circle layout. Here is the graph I gave as input to the graph reducer: and the output: With the same input graph, the MalToplogicalSorting gives this result: #($h #($f $d $e $b) $i $a $g $c). Cheers, Christophe. > > I know that Moose has some, but they are presented in a very cryptic way. > > Graph algos are very important, and we are seriously under-using them. > > Cheers, > Alexandre > > >> On Apr 8, 2015, at 12:53 PM, Christophe Demarey <[hidden email]> wrote: >> >> Hi, >> >> A few days ago, I added new graph algorithms into MooseAlgos but I did not communicate about that. >> I added 2 complementary algorithms: >> - MalGraphReducer : it takes as input a graph and ouputs a graph without circuits. Nodes forming a circuit (or cycle if you prefer) are merged into a single node. A merge node has a reference to merged nodes. It uses the MalTarjan algorithm. >> - MalTopologicalSorting : the well known graph sorting algorithm that can only be applied on graphs without circuits (cycles). >> >> the latter could be useful for some layouting strategies of graphs for example. >> >> Regards, >> Christophe._______________________________________________ >> Moose-dev mailing list >> [hidden email] >> https://www.iam.unibe.ch/mailman/listinfo/moose-dev > > -- > _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: > Alexandre Bergel http://www.bergel.eu > ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;. > > > > > _______________________________________________ > Moose-dev mailing list > [hidden email] > https://www.iam.unibe.ch/mailman/listinfo/moose-dev _______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev  complex-cycle-graph2-reduced.png (38K) Download Attachment complex-cycle-graph2.png (13K) Download Attachment smime.p7s (5K) Download Attachment |
Re: new graph algorithms
|
|
Hi!
This is great!! I have improved a bit your scripts. For example: -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= | graphReducer view | graphReducer := MalGraphReducer new. MalGraphFixture complexCycleGraph2: graphReducer. graphReducer run. view := RTMondrian new. view shape rectangle withText: [:n| n model printString]. view nodes: graphReducer nodes. view shape arrowedLine color: (Color gray alpha: 0.5). view shape shortestDistanceAttachPoint. view edges moveBehind; objects: graphReducer nodes from: #yourself toAll: #nextNodes. view layout forceWithCharge: -3000. ^ view -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= The produced graphs are now:   This leads to an interesting points. Where should we put these examples? Examples are crucially missing in Moose. I could create an example browser that is hooked into the roassal example world menu. Opinion on this? Cheers, Alexandre
--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
_______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: new graph algorithms
|
|
In reply to this post by demarey
Hi!
This is great!! I have improved a bit your scripts. For example: -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= | graphReducer view | graphReducer := MalGraphReducer new. MalGraphFixture complexCycleGraph2: graphReducer. graphReducer run. view := RTMondrian new. view shape rectangle withText: [:n| n model printString]. view nodes: graphReducer nodes. view shape arrowedLine color: (Color gray alpha: 0.5). view shape shortestDistanceAttachPoint. view edges moveBehind; objects: graphReducer nodes from: #yourself toAll: #nextNodes. view layout forceWithCharge: -3000. ^ view -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= The produced graphs are now:   This leads to an interesting points. Where should we put these examples? Examples are crucially missing in Moose. I could create an example browser that is hooked into the roassal example world menu. Opinion on this? Cheers, Alexandre
--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
_______________________________________________ Moose-dev mailing list [hidden email] https://www.iam.unibe.ch/mailman/listinfo/moose-dev |
Re: new graph algorithms
|
|
Re: new graph algorithms
|
|
| Free forum by Nabble | Edit this page |