Building an oriented graph in a graphical application

• Download graph classes - 6.8 KB
• Download Graph Editor - 24.1 KB

Introduction

I have developed a docflow application which includes a process module which provides document flow by different routes (depends on user answer). For example action 1 if "Yes" then action 2, if "No", action 3, and etc.

The process is an oriented graph where nodes are stages and edges are connections. The simple way for building routes is a using graphical editor (where user can build it by mouse move and click). I was looking for a similar module on C#, but found only the piccolo.net framework, but it was too "hard" for my task. Therefore I decided to develop a simple graph editor module by myself.

Graph Editor builds a simple oriented graph using modified Button and Panel controls (GraphNode, GraphPanel - classes). User can add, remove, drag node, remove, and add connection, mark node as the first element. The GraphNode and GraphPanel classes allow the user to use any event (mouse click, drag, move, and etc.).  

Background 

The main task was a building an oriented graph:

1. Every node has maximum two outgoing connections ("Yes" and "No" connection) and unlimited incoming connections.
2. Edges are highlighted on mouse over and an event handler allows drag nodes with edges.
3. Popup menu calls on mouse right click by the edge or node.
4. The first node has an other colour.
5. Node can connect to itself.

At first I had to choose a container (or background) for drawing my graph. It was a Panel control. It allows to add new controls and has autoscroll for controls disposing out of bounds. GraphPanel is a child class of the Panel control. It includes methods for node building and management. Mouse events for the GraphNode class are defined in it.  

Second, choose the base class for the node. I chose Button control, but you can use any control (ListView, PictureBox, Label, etc.).  I called it the GraphNode class. This class has its own fields and methods. GraphNode includes two arrays of points (start point and end point for every outgoing edge) and links to connected nodes. It's very easy to modify it. 

I use a very simple way to solve my task:

I move the Node control using an offset between the previous and current location:

//Set Node offset
//Params: offset
public void SetOffset(Point offset )
{
    //Get current location
    Point p=this.Location;
    ///set offset
    p.Offset(offset);
    //set new location
    this.Location = p;
}

For edge drawing I use the standard Graphics methods DrawLine and DrawCurve which draw on my GraphPanel. At first I use the absolute coordinate (in the panel)  for saving edges, but using these absolute values has a problem when you scroll the panel and all the coordinates shift), therefore the best way is using relative coordinates from the current and connected nodes. For example, EdgeYes[0] is a point on the current node and EdgeYes[1] is a point on the NodeYes control. Every time the panel invalidates, all edges redraw using relative coordinates.

The other problem was checking mouse events over Edge, because Edge is a simple line drawn on the GraphPanel. I wrote a function which solves an equation of line (x-x1)/(x2-x1)=(y-y1)/(y2-y1). If left side is equal to the right side then point(x,y) on the line  (x1,y1),(x2,y2). 

private bool isPointIn(Point p1, Point p2, Point px)
{
    //Check line bounds
    if (((px.X > p1.X) && (px.X > p2.X)) || ((px.X < p1.X) && (px.X < p2.X)))
        return false;

    double r1 = (double)(px.X - p1.X) / (p2.X - p1.X);
    double r2 = (double)(px.Y - p1.Y) / (p2.Y - p1.Y);
    //if r1==r2 or r1=0 or r2=0 then px belongs to the line p1;p2 
    
    if ((r1 == 0) || (r2 == 0))
                return true;
    return Math.Round(r1, 1) == Math.Round(r2, 1);
} 

Using the code 

If you want to use classes  in your own application, simply include classes GraphNode and GraphPanel and change the namespace and you can use it.

I defined some fields in the GraphPanel, which helps user to set up graph:

//Edge width
public int LineWidth = 2;
//Edge color
public Color LineColor = Color.Black;

LineWidth is the edge line width, LineColor is the edge line color.

You can change the default GraphNode properties (color, size, control, and etc.) as you wish. If you want to add a popup menu on mouse right click on the node, you can define it:

public Form1()
{
    InitializeComponent();
    pnGraph.NodeMenu = mnuNode;
}

mnuNode.Tag contains a link to the current GraphNode object. 

Manual

Add Node

Mouse right click on the panel and click on the "Add" menu item.

Drag Node 

Mouse left click and move it until mouse up. 

Add connection (edge)

• Mouse right click on the Node and move it to another node and mouse button up.
• Yes connection has to start from the left side, no connection from the right side.
• If we need to make a cycle node to itself - mouse right button click then mouse up and select "Cycle" from popup menu.
• Using this menu we can Delete node and mark it as a First Node (Yellow color).

Select Edge

Set mouse cursor over the edge (it becomes red) and then mouse right click.

Saving oriented graph 

I use serialization for saving and opening a graph, therefore in the GraphNode class, I defined the method:

public virtual void GetObjectData(SerializationInfo info, StreamingContext context) {
	info.AddValue("Name",this.Name);
    info.AddValue("Location", this.Location);
    info.AddValue("Width", this.Width);
    info.AddValue("Text", this.Text);
    info.AddValue("isFirst", this.isFirst,typeof(Boolean));
    info.AddValue("NodeYes", this.NodeYes,typeof(GraphNode));
    info.AddValue("NodeNo", this.NodeNo, typeof(GraphNode));
    info.AddValue("EdgeYes", this.EdgeYes, typeof(Point[]));
    info.AddValue("EdgeNo", this.EdgeNo, typeof(Point[]));		
}

It saves only fields enumerated in this method. This method allows to save a graph into a file, array, database, and load from the source. 

Honestly, the source code of these classes is very simple for understanding and using.

P.S. 

It was my first article here, please don't judge me harshly. I hope it will be useful for somebody and help them in their projects. As for me, I have successfully used these classes in my projects.