Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » Graphiti » Manhattan Connection routing
Manhattan Connection routing [message #1002803] Sat, 19 January 2013 13:23 Go to next message
Robert Brodt is currently offline Robert BrodtFriend
Messages: 625
Registered: August 2010
Location: Colorado Springs, CO
Senior Member

Hi all,

Because the draw2d ManhattanConnectionRouter wasn't exactly what I was looking for, I've decided to implement my own as a LayoutFeature. The result is quite usable, but could still use some improvement (Shape collision avoidance, optimal path, etc.)

I've created a screencast to demonstrate its current functionality here:

http://eclipse.org/bpmn2-modeler/videos/BPMN2Modeler-ConnectionRouterFeature.htm

If anyone's interested in collaborating on this, please let me know.

Cheers!
Bob
Re: Manhattan Connection routing [message #1003523 is a reply to message #1002803] Mon, 21 January 2013 12:38 Go to previous messageGo to next message
Michael Wenz is currently offline Michael WenzFriend
Messages: 1640
Registered: July 2009
Location: Walldorf, Germany
Senior Member
Bob,

better Manhattan connection routing would be interesting for the Graphiti
framework as well, as there were already some question on this...

Do I understand you correctly in that you build a layout feature that can be
applied to freeform connections so that they behave like better Manhattan
connections? That would be somewhat different to what the current ideas for
Manhattan conenctions in Graphiti is, but maybe this is an alternative.
Would it also be possible to hook your coding in as an alternative
connection router on GEF edit part level?

Michael
Re: Manhattan Connection routing [message #1003563 is a reply to message #1003523] Mon, 21 January 2013 14:19 Go to previous messageGo to next message
Robert Brodt is currently offline Robert BrodtFriend
Messages: 625
Registered: August 2010
Location: Colorado Springs, CO
Senior Member

Yes, that's exactly right; I use a LayoutFeature to apply routing constraints to a FreeFormConnection "after the fact", that is after a Connection handle has been added, moved or removed, after a connected Shape has been moved or resized, or one of the FixPointAnchors has been moved.

Not sure how easy this would be to add to an EditPart - I haven't looked at GEF in a long time, so would have to familiarize myself with this again. The routing algorithm itself is relatively simple and I'm sure the concepts could be reused easily enough.
Re: Manhattan Connection routing [message #1004021 is a reply to message #1003563] Tue, 22 January 2013 12:54 Go to previous messageGo to next message
Michael Wenz is currently offline Michael WenzFriend
Messages: 1640
Registered: July 2009
Location: Walldorf, Germany
Senior Member
Thanks,

I think this would be interesting for the framework as well, but I would
need some hands-on to get an impression what introducing such a layout
feature would mean for clients using it.

I have just opened https://bugs.eclipse.org/bugs/show_bug.cgi?id=398730 to
track possible Manhattan improvements. Could you please add your idea to
that bug, describe the usage and maybe add the layout feature (in case you
would like to contribute it)?

Thanks,
Michael
Re: Manhattan Connection routing [message #1067830 is a reply to message #1002803] Wed, 10 July 2013 18:34 Go to previous messageGo to next message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

I wonder if there is any progress on this issue so that the enhanced ManhattanConnectionRouter can be reused in a generic Graphiti diagram editor. The code in bpmn2 editor has too much dependency on bpmn2 core components.

Or anyone can point me to the right direction?

Thanks

Jack
Re: Manhattan Connection routing [message #1067971 is a reply to message #1067830] Thu, 11 July 2013 13:38 Go to previous messageGo to next message
Robert Brodt is currently offline Robert BrodtFriend
Messages: 625
Registered: August 2010
Location: Colorado Springs, CO
Senior Member

Hi Jack,

The existing manhattan router is a bit primitive because it tries to blindly calculate a route without prior knowledge of shapes and connections that may cause collisions or intersections. It works well enough for now, but I'm still working on a different algorithm which will be robust enough to navigate any topography and find routing solutions. This will eventually become what I hope to contribute to Graphiti.

This new router (the RouteSolver and RoutingNet classes) is still experimental and takes a different approach: it first calculates a navigable net of "empty space" (rectangles) between shapes, and then finds one or more optimal solutions that represent a minimal chain leading from the source to the target shape. The screen capture here illustrates what I mean:

http://content.screencast.com/users/rbrodt/folders/Jing/media/1de2a34d-34ea-4b42-a9a5-f88868ec3a63/2013-07-11_0717.png

The green rectangles are the empty spaces that are adjacent to the source shape, red are those adjacent to the target shape and light gray is everything in between. The light blue arrows are the navigable links that connect all of the empty spaces. All that needs to be done is to determine an optimal solution, and then route the connection inside the empty spaces that form this solution. The connection could consist of either orthogonal (manhattan) line segments, or diagonals (direct routing) depending on preference; the resulting connection would avoid shape collisions and intersections with other connections.

As I mentioned, this route solver can handle any topography, and will be able to find a solution for, e.g. the case where the target shape is "hidden" inside the "U" shape formed by the 3 tasks. Of course, if a shape is completely surrounded by other shapes, there is no solution.

If anyone is interested in helping expand on this idea (or if there are better ideas out there) I'm open to suggestions Wink

BTW, the RoutingNet class has Graphiti features to draw the emtpy spaces and links and I've been using this to visualize an optimal solution to the routing problem.

Bob
Re: Manhattan Connection routing [message #1067977 is a reply to message #1067971] Thu, 11 July 2013 13:57 Go to previous messageGo to next message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

Robert,

Our company is interested in learning and using it as a Graphiti feature(API), so any plan or schedule on your mind yet?

Thanks

Jack
Re: Manhattan Connection routing [message #1067987 is a reply to message #1067977] Thu, 11 July 2013 15:04 Go to previous messageGo to next message
Robert Brodt is currently offline Robert BrodtFriend
Messages: 625
Registered: August 2010
Location: Colorado Springs, CO
Senior Member

Sadly this is not very high on my priority list at the moment, because it's just me working on this project (with the occasional patch contributed by generous community members Wink )

Right now, I'm focused on bug fixing and getting ready for integration with jBPM, so we're looking at end of 2013 before I can start thinking about this feature again. If your company has any free resources to help out with this, it would be a big help.

Bob
Re: Manhattan Connection routing [message #1070203 is a reply to message #1067987] Wed, 17 July 2013 12:46 Go to previous messageGo to next message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

Robert,

I have spent a few days trying out the code from BPMN2. I have done some experiments with it. I figure out a way to use the router in my plugin. What I did was copying the layout feature and remove the preference API calls and invoke the static connect method.

In the mean time, I am also trying to figure out how to remove the dependency from bpmn model and edit bundles. But it is time consuming. If I got any result, I will post it here.

Thanks

Jack
Re: Manhattan Connection routing [message #1070205 is a reply to message #1070203] Wed, 17 July 2013 12:51 Go to previous messageGo to next message
Robert Brodt is currently offline Robert BrodtFriend
Messages: 625
Registered: August 2010
Location: Colorado Springs, CO
Senior Member

Cool! Thanks Jack Smile
Please keep us informed on your progress. Hopefully it can be contributed back to the Graphiti project.

Cheers,
Bob
Re: Manhattan Connection routing [message #1070245 is a reply to message #1070205] Wed, 17 July 2013 14:37 Go to previous messageGo to next message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

Robert,

I made an example on how to use Manhattan connection router in a plugin outside of bpmn2 product. The code is very simple. However, it still depends on bpmn2 product.

Developers need to clone a few bpmn2 repositories in their environment.

Below are a few repository locations.

https://git.eclipse.org/c/bpmn2/
https://git.eclipse.org/c/bpmn2-modeler/org.eclipse.bpmn2-modeler.git/
https://github.com/eclipseconsultant/.ManhattanConnectionRouter

Also, you need a target used to build bpmn2.

Thanks

Jack
Re: Manhattan Connection routing [message #1070788 is a reply to message #1070245] Thu, 18 July 2013 17:24 Go to previous messageGo to next message
Robert Brodt is currently offline Robert BrodtFriend
Messages: 625
Registered: August 2010
Location: Colorado Springs, CO
Senior Member

Thanks Jack, I'll take a look at this, maybe I can figure out how to remove those dependencies.

Bob
Re: Manhattan Connection routing [message #1072335 is a reply to message #1070788] Mon, 22 July 2013 14:44 Go to previous messageGo to next message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

Robert,

We need some help.

Can you change a few instance variables from (default) to protected and remove final keyword ManhattanConnectionRouter if that is possible or allowed at all.

We tried to extend MnahattanConnectionRouter in my local environment. You can sync to my git repository to see what need to be changes.

Thanks

Jack
Re: Manhattan Connection routing [message #1072772 is a reply to message #1072335] Tue, 23 July 2013 13:15 Go to previous messageGo to next message
Robert Brodt is currently offline Robert BrodtFriend
Messages: 625
Registered: August 2010
Location: Colorado Springs, CO
Senior Member

OK, done. I've sent a pull request for some changes required in your BaseManhattanConnectionRouter.
The changes in BPMN2 Modeler will be available in tonight's build, or you can just pull the latest code from the eclipse git repo.

Thanks,
Bob
Re: Manhattan Connection routing [message #1072799 is a reply to message #1072772] Tue, 23 July 2013 14:16 Go to previous messageGo to next message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

Robert,

I think you may have not checked in some of your changes yet as r.setRank() is not compiled yet.

I am thinking to extend ManhattanConnectionRouter directly, but it is final. Do you think it is OK to remove the final keyword? I attach a patch to help explain what needs to be changed so that I can use it in my app.

Thanks

Jack



Re: Manhattan Connection routing [message #1072811 is a reply to message #1072799] Tue, 23 July 2013 14:52 Go to previous messageGo to next message
Robert Brodt is currently offline Robert BrodtFriend
Messages: 625
Registered: August 2010
Location: Colorado Springs, CO
Senior Member

Hmm, I'm pretty sure all of the required changes are in the eclipse git repository, here's a link to the git commit record:

https://git.eclipse.org/c/bpmn2-modeler/org.eclipse.bpmn2-modeler.git/commit/?id=c48b4326cb258f3bd249de74b35b2a94d28e2654

Are you sure you're not pulling code from the github mirror?
Re: Manhattan Connection routing [message #1072817 is a reply to message #1072811] Tue, 23 July 2013 15:15 Go to previous messageGo to next message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

Robert,

I got it from git url:

git://git.eclipse.org/gitroot/bpmn2-modeler/org.eclipse.bpmn2-modeler.git

Never mind, I may get it later as the system may to to refresh itself.

But I have fixed another issue in updateConnection. We have more level of nested ContainerShapes so this code is changed to:

public static void updateConnections(IFeatureProvider fp, AnchorContainer ac) {
		List<Connection> alreadyUpdated = new ArrayList<Connection>();
		if (ac instanceof ContainerShape) {
			TreeIterator<EObject> itr = ac.eAllContents();
			while (itr.hasNext()) {
				EObject child = itr.next();
//				for (Shape child : ((ContainerShape)ac).getChildren()) {
				if (child instanceof ContainerShape)
					updateConnections(fp, (AnchorContainer)child, alreadyUpdated);
			}
		}
		updateConnections(fp, ac, alreadyUpdated);
	}


I am not familar with git command but I can try to figure out how to submit a push to upstream so you can get it from within Eclipse.

Thanks

Jack
Re: Manhattan Connection routing [message #1076538 is a reply to message #1072817] Wed, 31 July 2013 14:59 Go to previous messageGo to next message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

Robert,

I create a patch so that you can apply to the modeler.core project, see if this change can work for your implementation as well.

Thanks

Jack
Re: Manhattan Connection routing [message #1076721 is a reply to message #1076538] Wed, 31 July 2013 19:38 Go to previous messageGo to next message
Robert Brodt is currently offline Robert BrodtFriend
Messages: 625
Registered: August 2010
Location: Colorado Springs, CO
Senior Member

OK will do.

I'm not sure if the quality of this (my) code is good enough to be considered as a contribution to Graphiti, but at least it's a starting point.
Re: Manhattan Connection routing [message #1076724 is a reply to message #1076721] Wed, 31 July 2013 19:41 Go to previous messageGo to next message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

Robert,

Our company is satisfied with what your code can do for us and I am happy too. I also think it is some good staring point.

Thanks

Jack
Re: Manhattan Connection routing [message #1076726 is a reply to message #1076724] Wed, 31 July 2013 19:44 Go to previous message
Jack Chi is currently offline Jack ChiFriend
Messages: 26
Registered: July 2011
Location: Pennsylvania
Junior Member

The task to integrate the ManhattanConnectionRouter in our project is complete, we have good experience with the model.core bundle. We are thankful for your helps.

Jack
Previous Topic:Trying to use Graphiti with Juno SR2 but getting dependency error
Next Topic:Moving shapes and bendpoints
Goto Forum:
  


Current Time: Fri Dec 19 13:48:35 GMT 2014

Powered by FUDForum. Page generated in 0.02401 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software