Custom Network Graphing Ideas

[LaVolpe]

Got your thinking caps on?
I'm in the process of trying to create an auto-generating graph/diagram of a network. There are over 300 of these networks that can change from week to week.

Looking for some ideas, specifically: Logic/psuedo algos that can arrange network nodes in a way that minimal distance exists between nodes that are directly connected.

Here's some more details to better understand the problem.
1. Network changes weekly -- nodes are added, removed, rerouted
2. How many nodes exist and which nodes they connect to, are always known
3. Each node may connect to one or several other nodes in the same network
4. Each of the connected nodes, in turn, can connect to several other nodes
5. Currently, largest network graph contains 150 nodes, most interconnected to each other (some connect outside of the network and are handled differently). Each node may have upwards of 30+ ports or as little as just one, each having a circuit that connects the nodes. An entire graph may consist of over 100 nodes and several hundred circuits and over 1,000 ports (though these are not involved in the placement problem).

This is for a real-world project. We have personnel that must continually place nodes in most visual pleasing positions to minimize crossing network circuits/edges. Once placed, the individuals must "draw" the cicuits/edges and some of these can end up looking like a maze before they get to the connecting node. Breaking down each graph to restart and reposition can take a single person in excess of 6 hours (we have over 300 of these graphs/diagrams) that can change weekly. Restarting from scratch currently occurs only when so many nodes have been added, removed, re-positioned that the circuits literally end up running all over the graph. A graph in paper size can exceed 3x3 feet, so you kinda get the idea of how massive the undertaking is. Thank goodness most of the graphs are not nearly that large.

P.S. Professional tools are out of the question. The application that displays these graphs are proprietary and the graphs themselves are custom coded for that application. The task is do-able, just a matter of getting ideas on ways to proceed. I have several of my own and would like some more input before I dig in; don't want to waste several weeks/months on a weak strategy. I already have some nice path-finding algorithms that can be used to draw the circuits.

[jcis]

And the question is..?
A possible approach, to start talking about this, would be something like..
A PictureBox inside Another PictureBox (Pic1 - Pic2). Pic1 would be the Container, and you would draw into Pic2. Using custom cursors for doing that would be a good idea, like hand cursors in Acrobat Reader. By holding LMB pressed you can move Pic2 to reach any part of the graphic. Or you could use scrollbars to move Pic2 and then use LMB to do things like moving Nodes/Connectors.

All that would be easy, but i think the real problem here would be how to draw. Possible ways..

1) You can use controls as nodes, like PictureBoxes, but not for connectors (line control is not very flexible). this way each control would be loaded at runtime using a control array and Load().

Advantages: By moving PictureBoxes at runtime, you don't need to worry about redrawing everything on every move. Also, PictureBoxes doesn't flicker as bad as other controls, like Image Control.

Disadvantages: Using controls to make complex graphic stuff (like games) is very "noobish", you won't get nice-looking graphics and sometimes you can't avoid flickering. Also, your limit is what your controls have to offer.

2) PaintPicture / Bitblt: Using these you have to draw everything, the simplest way would be clearing and redrawing when something moves, but this is almost impossible since Flickering would be horrendous, so you need to use some other technique like using a back buffer (drawing into the back buffer and when drawing is done you swap buffers).

Advantages: Better graphics, no flicker when using backbuffer.

Disadvantages: Not very easy. No event will fire when you click/mousemove/mousedown on something, you need to handle all (positions, inside or outside figures, collisions..). I mean, all events will be taken by the drawing surface (Picturebox/Form)

3) Using a powerfull graphic library like OPENGL or DX, but maybe this is too much for your needs.

I might be forgetting some ways but offcourse they exist, these are just some ideas.

[LaVolpe]

Sorry for not being more clear. The question isn't how to draw the items -- that is easy. Besides, this will all be done via code, no human intervention. The question is: Methods, logic, pseudo algos for placing the nodes. Can't simply just drop then willy-nilly anywhere on a graph. They should be in a logical organization that allows those connected to each other to be nearly adjacent to each other if at all possible. To compliicate the issue, it can't just be as simple as an organizational chart type structure where the graph can continue for dozens of pages in any direction -- that would be too easy . Visually, think more of a circuit board.

My initial idea is to determine which single node connects to the most other nodes on the graph, start with that one. Place the other adjacent nodes around this 1st node. Then process the adjacents to that next layer and so on, however, since many nodes internconnect, can't just keep moving further out, rather some nodes will need to be inserted between layers for a more professional appearance. Can't have circuits travelling across an entire graph when more efficient node placement could prevent that. The 1st couple of layers appear to be relatively easy, it is the next couple dozen that needs better logic

[zeezee]

Just waiting for more explanation.
Have you considered the commonly known algorithms for this. (To find shortest path) ?

http://en.wikipedia.org/wiki/Open_Shortest_Path_First

The layers which you are talking are they the Common Network Layers ?
Not OSI , buyt like Switching Layers ? eg: Switch, Bridge, Router ?

How about considering how the routing algorithms work?

[LaVolpe]

zeezee, thanks for the link. Though not quite applicable since that link primarily discusses routing of data (i.e., shortest path between two nodes for swtiching/routing of packets). My problem is efficient node placements on the graph. However, the mention of Dijkstra's Algorithm got my attention. Definitely worthy of consideration.

[zeezee]

Oh very sorry. Its the wrong link.

http://en.wikipedia.org/wiki/Shortest_path_problem