Hi, I'm trying to research Graph Layout to find some algorithms. I basically have to assign geometric data to some lines and nodes as part of an electrical system.
I'm not necessarily looking for code, but perhaps pseudo code or algorithms which would help me generate a graph which could be analyzed.

I've done several searches on the web, but I just get programs which implement these algorithms but do not necesarily show or teach you how.

Does anyone have any suggestions for me?

Thanks!

Are you hoping to actually generate graphics on the screen, or just analyze the geometric data? And what kind of algorithms are you looking for, exactly? (there are many different kinds of algorithms)

Actually I will need to generate the geometric data myself, as well as display some layout on a screen. I'm thinking some type of hierarchichal layout will do.

Thanks for the question.

Well, there are a lot of different ways you can display graphics. You can use an existing library or use OpenGL or whatever; without knowing what language you want to work in, I don't know what to suggest for what. Look around and I'm sure you'll find something.

What else do you need to do, though, aside from showing graphics on the screen?

The actual graphical part is what I am least worried about. I need to learn how to generate a Graph (of Vertices and Edges) and display it for analysis.

Displaying it will be easy... generating it is difficult.

The situation is this:

I have a list of vertices and edges, and I know which edges belong to which vertices, but they have no geometrical data.

This is called "Graph Layout" or "Graph Drawing". I've done many searches and found many programs which implement algorithms I'm looking for, but I cannot find the actual algorithms themselves!

Thanks for any help.

Ah, I see what you're asking. A little searching turned up this package which is very expensive, but the link for "Smart diagramming" opens up a nifty little applet that shows some of what it can do - it might give you some ideas about what kind of layout you need to do. Depending on the structure of your graphs, you might need different algorithms, although I suppose a really simple algorithm would just layout the nodes in a rectangular grid and then connect them with straight lines. Wouldn't be pretty, but it's probably the easiest. A more complex algorithm would have to take into account which edges cross one another, and rearrange some nodes in order to minimize edge crossings and stuff like that. If your graphs are relatively simple, maybe some simple heuristics would help clean things up - like arranging the grid depending on which nodes have the most edges connected to them. The node with the most edges could be in the center, with the rest of the nodes arranged farther from the center if they have fewer edges.

Though, the best solution I can come up with is to make the graphical display interactive - let your program throw all the nodes up there, and then include some functionality so the user can drag nodes around and rearrange them to clean up the mess.

You may want to look at Graphviz : http://www.research.att.com/sw/tools.../download.html it is an open source project about graph view, it is very powerfull. With a simple langage that you can generate, you can have a descriptive return about how to display (also an image if you prefer). Many program use it (like doxygen for collaboration diagram) to generate a graph view.

But as it's open source you can also check for algorithm and so on.

Hope this help