Graph Windows (GraphWin)

Definition

GraphWin combines the two types graph and window and forms a bridge between the graph data types and algorithms and the graphics interface of LEDA. GraphWin can easily be used in LEDA programs for constructing, displaying and manipulating graphs and for animating and debugging graph algorithms.

• The user interface of GraphWin is simple and intuitive. When clicking a mouse button inside the drawing area a corresponding default action is performed that can be redefined by users. With the initial default settings, the left mouse button is used for creating and moving objects, the middle button for selecting objects, and the right button for destroying objects. A number of menues at the top of the window give access to graph generators, modifiers, basic algorithms, embeddings, setup panels, and file input and output.
• Graphwin can display and manipulate the data associated with the nodes and edges of LEDA's parameterized graph type GRAPH<vtype,etype>. When a GraphWin is opened for such a graph the associated node and edge labels of type vtype and etype can be displayed and edited.
• Most of the actions of GraphWin can be customized by modifying or extending the menues of the main window or by defining call-back functions. So the user can define what happens if a node or edge is created, selected, moved, or deleted.
• Graphwin offers a collection of graph generators, modifiers and tests. The generators include functions for constructing random, planar, complete, bipartite, grid graphs, connected graphs, biconnected, graphs ...

  There are also methods for modifying existing graphs (e.g. by removing or adding a certain set of edges) to fit in one of these categories and for testing whether a given graph is planar, connected, bipartite ...

• The standard menu includes a choice of fundamental graph algorithms and basic embedding algorithms.

For every node and edge of the graph GraphWin maintains a set of parameters. With every node is associated

• a position of type point,
• a shape of type gw_node_shape,
• a color, border color, and label color of type color,
• a pixmap of type char*,
• a width and height in pixels of type int,
• a radius1 and radius2 in real world coordinates of type double,
• a border width in pixels of type int,
• a label type of type gw_label_type,
• a user label of type string, and
• a label position of type gw_position.

With every edge is associated

• a list of bends of type list<point>,
• a color and label color of type color,
• a style of type gw_edge_style,
• a direction of type gw_edge_dir,
• a width of type int,
• a label type of type gw_label_type,
• a user label of type string, and
• a label position of type gw_position,
• a list of bends of type list<point>,
• a source anchor of type point,
• a target anchor of type point.

The corresponding types are:

gw_node_shape = { circle_node, ellipse_node, square_node, rectangle_node }
gw_node_style = { simple_node, filled_node }

gw_position = { central_pos, northwest_pos, north_pos,
                northeast_pos, east_pos, southeast_pos, 
                south_pos, southwest_pos, west_pos }

gw_edge_style = { solid_edge, dashed_edge, dotted_edge, dashed_dotted_edge }
gw_label_type = { no_label, user_label, data_label, index_label }
gw_edge_dir   = { undirected_edge, directed_edge, bidirected_edge, rdirected_edge };

Creation

GraphWin	gw(graph& G, int w, int h, const char* win_label="");
		creates a graph window for graph G with a display window of size w pixels x h pixels. If win_label is not empty it is used as the frame label of the window, otherwise, a default frame label is used.
GraphWin	gw(graph& G, const char* win_label="");
		creates a graph window for graph G with a display window of default size and frame label win_label.
GraphWin	gw(int w, int h, const char* win_label="");
		creates a graph window for a new empty graph with a display window of size w pixels x h pixels, and frame label win_label.
GraphWin	gw(const char* win_label="");
		creates a graph window for a new empty graph with a display window of default size and frame label win_label.
GraphWin	gw(window& W);	as above, but W is used as display window.
GraphWin	gw(graph& G, window& W);	as above, but makes G the graph of gw.

Operations

a) Window Operations

void	gw.display(int x, int y)	displays gw with upper left corner at (x,y). The predefined constant window::center can be used to center the window horizontally (if passed as x) or vertically (if passed as y).
void	gw.display()	displays gw at default position.
bool	gw.edit()	enters the edit mode of GraphWin that allows to change the graph interactively by operations associated with certain mouse events or by choosing operations from the windows menu bar (see section edit-mode for a description of the available commands and operations). Edit mode is terminated by either pressing the done button or by selecting exit from the file menu. In the first case the result of the edit operation is true and in the latter case the result is false.
bool	gw.open(int x, int y)	displays the window at position (x,y), enters edit mode and return the corresponding result.
bool	gw.open()	as above, but displays the window at default position.
void	gw.close()	closes the window.
void	gw.message(const char* msg)
		displays the message msg at the top of the window.
void	gw.del_message()	deletes a previously written message.
double	gw.get_xmin()	returns the minimal x-coordinate of the window.
double	gw.get_ymin()	returns the minimal y-coordinate of the window.
double	gw.get_xmax()	returns the maximal x-coordinate of the window.
double	gw.get_ymax()	returns the maximal y-coordinate of the window.
void	gw.win_init(double xmin, double xmax, double ymin)
		sets the coordinates of the window to (xmin,xmax,ymin).
void	gw.redraw()	redraws the graph. If the flush parameter of gw is set to false (see set_flush) this operation can be used to display the current state of the graph after a number of update operations.
void	gw.set_frame_label(const char* label)
		makes label the frame label of the window.
int	gw.open_panel(panel& P)	displays panel P centered on the drawing area of gw, disables the menu bar of gw and returns the result of P.open().
window&	gw.get_window()	returns a reference to the window of gw.

b) Graph Operations

node	gw.new_node(point p)	adds a new node at position p to gw.
void	gw.del_node(node v)	deletes v and all edges incident to v from gw.
edge	gw.new_edge(node v, node w)
		adds a new edge (v,w) to gw.
edge	gw.new_edge(node v, node w, list<point> P)
		adds a new edge (v,w) with bend sequence P to gw.
void	gw.del_edge(edge e)	deletes edge e from gw.
void	gw.clear_graph()	deletes all nodes and egdes.
graph&	gw.get_graph()	returns a reference of the graph of gw.
void	gw.update_graph()	this operation has to be called after any update operation that has been performed directly (not by Graph Win) on the underlying graph, e.g., deleting or inserting nodes or edges.

c) Node Parameters

Node parameters can be retrieved or changed by a collection of get- and set- operations. We use param_type for the type and param for the value of the corresponding parameter.

Individual Parameters

param_type	gw.get_param(node v)	returns the value of parameter param for node v.
param_type	gw.set_param(node v, param_type x)
		sets the value of parameter param for node v to x. and returns its previous value.
void	gw.set_param(list<node>& L, param_type x)
		sets the value of parameter param for all nodes in L to x.

Default Parameters

param_type	gw.get_node_param()	returns the current default value of parameter param.
param_type	gw.set_node_param(param_type x, bool apply=true)
		sets the default value of parameter param to x. and returns its previous value. If apply == true the parameter is changed for all existing nodes as well.

d) Edge Parameters

Individual Parameters

param_type	gw.get_param(edge e)	returns the value of parameter param for edge e.
param_type	gw.set_param(edge e, param_type x)
		sets the value of parameter param for edge e to x. and returns its previous value.
void	gw.set_param(list<edge>& L, param_type x)
		sets the value of parameter param for all edges in L to x.

Default Parameters

param_type	gw.get_edge_param()	returns the current default value of parameter param.
param_type	gw.set_edge_param(param_type x, bool apply=true)
		sets the default value of parameter param to x. and returns its previous value. If apply == true the parameter is changed for all existing edges as well.

e) Global Options

int	gw.set_gen_nodes(int n)	sets the default number of nodes n for all graph generator dialog panels.
int	gw.set_gen_edges(int m)	sets the default number of edges m for all graph generator dialog panels.
int	gw.set_edge_distance(int d)
		sets the distance of multi-edges to d pixels.
grid_style	gw.set_grid_style(grid_style s)
		sets the grid style to s.
int	gw.set_grid_dist(int d)	sets the grid distance to d.
int	gw.set_grid_size(int n)	sets the grid distance such that n vertical grid lines lie inside the drawin area.
bool	gw.set_show_status(bool b)
		display a status window (b= true) or not (b= false).
color	gw.set_bg_color(color c)	sets the window background color to c.
char*	gw.set_bg_pixmap(char* pr, double xorig=0, double yorig=0)
		sets the window background pixmap to pr and the tiling origin to (xorig,yorig).
void	gw.set_bg_xpm(char** xpm_data)
		sets the window background pixmap to the pixmap defined by xpm_data.
void	gw.set_node_label_font(gw_font_type t, int sz)
		sets the node label font type and size.
void	gw.set_edge_label_font(gw_font_type t, int sz)
		sets the edge label font type and size.
string	gw.set_node_index_format(string s)
		sets the node index format string to s.
string	gw.set_edge_index_format(string s)
		sets the edge index format string s.

Animation and Zooming

int	gw.set_animation_steps(int s)
		move a node in s steps to its new position.
bool	gw.set_flush(bool b)	show operations on gw instantly (b= true) or not (b= false).
double	gw.set_zoom_factor(double f)
		sets the zoom factor to f used when zooming from menu.
bool	gw.set_zoom_objects(bool b)
		resize nodes and edges when zooming (b==true) or not (b==false).
bool	gw.set_zoom_labels(bool b)
		resize labels when zooming (b==true) or not (b==false).

f) Node and Edge Selections

void	gw.select(node v)	adds v to the list of selected nodes.
void	gw.select_all_nodes()	selects all nodes.
void	gw.deselect(node v)	deletes v from the list of selected nodes.
void	gw.deselect_all_nodes()	clears the current node selection.
bool	gw.is_selected(node v)	returns true if v is selected and false otherwise.
list<node>	gw.get_selected_nodes()	returns the current node selection.
void	gw.select(edge e)	adds e to the list of selected edges.
void	gw.select_all_edges()	selects all edges.
void	gw.deselect(edge e)	deletes e from the list of selected edges.
void	gw.deselect_all_edges()	clears the current node selection.
bool	gw.is_selected(edge e)	returns true if e is selected and false otherwise.
list<edge>	gw.get_selected_edges()	returns the current edge selection.

g) Layout Operations

void	gw.set_position(node_array<point> pos)
		for every node v of G the position of v is set to pos[v].
void	gw.set_position(node_array<double> x, node_array<double> y)
		for every node v of G the position of v is set to (x[v],y[v]).
void	gw.set_layout(node_array<point> pos, edge_array<list<point> > bends, bool reset_anchors=true)
		for every node v the position is set to pos[v] and for every edge e the list of bends is set to bends[e].
void	gw.set_layout(node_array<point> pos)
		for every node v the position is set to pos[v] and for every edge e the list of bends is made empty.
void	gw.set_layout(node_array<double> x, node_array<double> y)
		for every node v the position is set to (x[v],y[v]) and for every edge e the list of bends is made empty.
void	gw.set_layout()	same as gw.remove_bends().
void	gw.place_into_box(double x0, double y0, double x1, double y1)
		moves and stretches the graph to fill the given rectangular box (x0,y0,x1,y1) by appropriate scaling and translating operations.
void	gw.place_into_win()	moves and stretches the graph to fill the entire window by appropriate scaling and translating operations.
void	gw.remove_bends(edge e)	removes all bends from edge e.
void	gw.remove_bends()	removes the bends of all edges of the graph.
void	gw.reset_edge_anchors()	resets all edge anchor positions to (0,0).
int	gw.load_layout(istream& istr)
		read layout from stream istr.
void	gw.save_layout(ostream& ostr)
		save layout to stream ostr.

h) Zooming

void	gw.zoom(double f)	zooms the window by factor f.
void	gw.zoom_area(double x0, double y0, double x1, double y1)
		performs a zoom operation for the recangular area with current coordinates (x0,y0,x1,y0).
void	gw.zoom_graph()	performs a zoom operation, such that the graph fills the entire window.
void	gw.unzoom()	undoes last zoom operation.

i) Operations in Edit-mode

Before entering edit mode with gw.edit() or gw.open() it is possible to define Graph Win's actions in certain kinds of situations.

The firstway is to define what to do when a certain condition of mouse and key events occurs. Events are: A_LEFT (left mouse-button), A_MIDDLE (middle mouse-button), A_RIGHT (right mouse-button), A_SHIFT (shift-key), A_CTRL (control-key), A_ALT (alt-key), A_DRAG (button not released), A_NODE (node-hit) A_EDGE (edge-hit). To describe an event combine these constants using operator , for instance (A_LEFT A_NODE) starts a new edge by default.

void	gw.set_action(long mask, gw_action f)
		set action on condition mask to f. gw_action is defined as void *(GraphWin&, const point&). For f == NULL the corresponding action is deleted.
gw_action	gw.get_action(long mask)	returns the action associated with condition mask.
void	gw.reset_actions()	resets all actions to their defaults.
void	gw.clear_actions()	deletes all actions.

The second way to control Graph Win's behavior in edit mode is to supply call-back functions which are called in certain edit operations. Call-back functions exist in two kinds. Functions of the first kind (pre-handler) are called before the corresponding operation is executed, functions of the second kind (post-handler) are called after the operation has been completed. Every pre-handler returns a boolean value that can be used to cancel the corresponding operation (if it returns false). about what happened. It is possible to define only one of it.

void	gw.set_new_node_handler(bool (*f)(GraphWin& , point ))
		f(gw,p) is called every time before a node is to be created at position p.
void	gw.set_new_node_handler(void (*f)(GraphWin& , node)=NULL)
		f(gw,v) is called after node v has been created.
void	gw.set_new_edge_handler(bool (*f)(GraphWin& , node, node))
		f(gw,v,w) is called before the edge (v,w) is to be created.
void	gw.set_new_edge_handler(void (*f)(GraphWin& , edge)=NULL)
		f(gw,e) is called after the edge e has been created.
void	gw.set_start_move_node_handler(bool (*f)(GraphWin& , node)=NULL)
		f(gw,v) is called before node v is to be moved.
void	gw.set_move_node_handler(void (*f)(GraphWin& , node)=NULL)
		f(gw,v) is called every time node v reaches a new position during a move operation.
void	gw.set_end_move_node_handler(void (*f)(GraphWin& , node))
		f(gw,v) is called after node v has been moved.
void	gw.set_del_node_handler(bool (*f)(GraphWin& , node))
		f(gw,v) is called before the node v is to be deleted.
void	gw.set_del_node_handler(void (*f)(GraphWin& )=NULL)
		f(gw) is called every time after a node was deleted.
void	gw.set_del_edge_handler(bool (*f)(GraphWin& , edge))
		f(gw,e) is called before the edge e is to be deleted.
void	gw.set_del_edge_handler(void (*f)(GraphWin& )=NULL)
		f(gw) is called every time after an edge was deleted.
void	gw.set_start_edge_slider_handler(void (*f)(GraphWin& , edge, double)=NULL, int sl=0)
		f(gw,e,pos) is called before slider sl of edge e is to be moved. Here pos is the current slider position.
void	gw.set_edge_slider_handler(void (*f)(GraphWin& , edge, double)=NULL, int sl=0)
		f(gw,e,pos) is called every time slider sl of edge e reaches a new position pos during a slider move.
void	gw.set_end_edge_slider_handler(void (*f)(GraphWin& , edge, double)=NULL, int sl=0)
		f(gw,e,pos) is called after slider sl of edge e has been moved to the final position pos.
void	gw.set_init_graph_handler(bool (*f)(GraphWin& ))
		f is called every time before the entire graph is replaced, e.g. by a clear, generate, or load operation.
void	gw.set_init_graph_handler(void (*f)(GraphWin& )=NULL)
		f is called every time after the entire graph was replaced.

j) Menus

The default menu ...

void	gw.set_default_menu(long mask)
		...
void	gw.add_menu(long menu_id)	...
void	gw.del_menu(long menu_id)	...

Menus of Graph Win are not fixed. New buttons and menus are easy includable to it, for instance to pass a graph - created in an edit-session - through your own function and to show its results. To add your function f of type function_t, use (non-member-function!)

int  gw_add_call(GraphWin& gw, function_t f, string label, 
                 int submenu = 0)

EXAMPLE:

have written a function

void mydfs(graph& G, node s, node_array<bool>& reached) { ... }

that performs a depth first search starting at s. To make it available from menu, type

gw_add_call(gw,mydfs,"My dfs");

for an existing object gw of class Graph Win.

Since Graph Win does not know, how to handle the arguments and the result of function f, you have to define

void gw_call(GraphWin& gw, function_t f) {...}

for all your above used functions f. In gw_call you create needed arguments, call f with it and possibly show the results (set_color(..), set_position(..) etc.).

EXAMPLE:

you know, what preconditions to meet when calling mydfs. Let's assume that argument s from mydfs is a node of graph G. Define a function as follows:

void gw_call(GraphWin& gw, void (*dfs)(graph&,node,node_array<bool>&)) {
  graph& G=gw.get_graph();
  node s=gw.get_node();
  node_array<bool> reached(G,false);
  dfs(G,s,reached);
  node v;
  forall_nodes(v,G) if (reached[v]) gw.set_color(v,red);
}

That's all.

Another possibility to extend the menu is to make the above used gw_call variable:

int  gw_add_call(GraphWin& gw, function_t f, 
                 void (*call)(GraphWin&, function_t),	
                 string label, int submenu=0)

In this version call is executed whenever the assigned button is pressed.

EXAMPLE:

function gw_call you'll get the same effect as above by writing

gw_add_call(gw,mydfs,gw_call,"My dfs");

For simple functions, that only change parameters of a Graph Win, can be used:

int  gw_add_simple_call(GraphWin& gw, void (*f)(GraphWin&),
                        string label, int submenu=0);

Graph Win offers a lot of functions, that combine many single actions in one call, for instance gw.reset_nodes(). These functions are of type void (GraphWin::*f)(void) and may also be added to the menu by:

int  gw_add_member_call(GraphWin& gw, void (GraphWin::*f)(void),
                        string label, int submenu=0)

or

int  gw_add_member_call(GraphWin& gw, void (GraphWin::*f)(Void),
                        void (*call)(GraphWin&, void (GraphWin::*f)(void)), 
           		string label, int submenu=0).

Within call the member-function f can be called using:

void  gw.call(void (GraphWin::*f)(void))

All functions discussed above return an integer. With it you are able to forbid calls from menu using set_call_enabled(int,bool). See below.

To add a submenu, use:

int  gw_add_menu(GraphWin& gw, string label, int submenu=0),

which returns an integer corresponding to a submenu you can use as parameter submenu in all gw_add...-commands.

int	gw.get_menu(string label)	returns the number of the submenu with label label or -1 if no such menu exists.
void	gw.enable_call(int c)	enable call to function c when chosen from menu.
void	gw.disable_call(int c)	disable call to function c when chosen from menu.
bool	gw.is_call_enabled(int c)	checks if call to function c is enabled.
void	gw.enable_calls()	enable all calls added with gw_add... .
void	gw.disable_calls()	disable all calls added with gw_add... .

k) Input/Output

int	gw.read(istream& in)	reads graph from stream in.
int	gw.read(string fname, bool ask_override=false)
		reads graph from file fname.
bool	gw.save(ostream& out)	writes graph to output stream out.
bool	gw.save(string fname, bool ask_override=false)
		saves graph to file fname.
int	gw.read_gml(istream& in)	reads graph in GML format from stream in.
int	gw.read_gml(string fname, bool ask_override=false)
		reads graph in GML format from file fname. Returns 1 if fname can not be opened, 2 if a parser error occurs, and 0 on success.
bool	gw.save_gml(ostream& out)	writes graph in GML format to output stream out.
bool	gw.save_gml(string fname, bool ask_override=false)
		saves graph to file fname in GML format.
bool	gw.save_ps(string fname, bool ask_override=false)
		saves a postscript representation of the graph to fname.
bool	gw.save_latex(string fname, bool ask_override=false)
		saves a postscript/latex representation of the graph to fname.
bool	gw.unsaved_changes()	returns true if the graph has been changed after the last save (gw or gml) operation.
bool	gw.save_defaults(string fname)
		saves the default attributes of nodes and edges to file fname.
bool	gw.read_defaults(string fname)
		reads the default attributes of nodes and edges from file fname.

l) Miscellaneous

bool	gw.wait()	waits until the done button is pressed (true returned) or exit is selected from the file menu (false returned).
bool	gw.wait(const char* msg)	displays msg and waits until the done button is pressed (true returned) or exit is selected from the file menu (false returned).
bool	gw.wait(float sec, const char* msg="")
		as above but waits no longer than sec seconds returns ?? if neither button was pressed within this time interval.
void	gw.acknowledge(string s)	displays string s and asks for acknowledgement.
node	gw.read_node()	asks the user to select a node with the left mouse button. If a node is selected it is returned otherwise nil is returned.
edge	gw.read_edge()	asks the user to select an edge with the left mouse button. If an edge is selected it is returned otherwise nil is returned.
bool	gw.define_area(double& x0, double& y0, double& x1, double& y1, const char* msg="")
		displays message msg and returns the coordinates of a rectangular area defined by clicking and dragging the mouse.
list<node>	gw.get_nodes_in_area(double x0, double y0, double x1, double y1)
		returns the list of nodes intersecting the rectangular area (x0,y0,x1,y1).
list<edge>	gw.get_edges_in_area(double x0, double y0, double x1, double y1)
		returns the list of edges intersecting the rectangular area (x0,y0,x1,y1).
void	gw.save_node_attributes()	...
void	gw.restore_node_attributes()
		...
void	gw.save_edge_attributes()	...
void	gw.restore_edge_attributes()
		...
void	gw.reset_nodes(long mask=N_ALL)
		reset node parameters to their default values.
void	gw.reset_edges(long mask=E_ALL)
		reset edge parameters to their default values.
void	gw.reset()	reset node and edge parameters to their default values.
void	gw.reset_defaults()	resets default parameters to their original values.
void	gw.get_bounding_box(double& x0, double& y0, double& x1, double& y1)
		computes the coordinates (x0,y0,x1,y1) of a minimal bounding box for the current layout of the graph.
void	gw.get_bounding_box(list<node> V, list<edge> E, double& x0, double& y0, double& x1, double& y1)
		computes the coordinates (x0,y0,x1,y1) of a minimal bounding box for the current layout of subgraph (V,E).