****************************************************************** * * * The Graph File Formats used by AGD Server * * ========================================= * * * ****************************************************************** 1. The GraphWin File Format: ---------------------------- a) The LEDA graph input/output format The following passage describes the format of the output produced by the function graph::write(ostream& out). The output consists of several lines which are separated by endl. Comment-lines have a # character in the first column and are ignored. The output can be partitioned in three sections: i) Header Section The first line always contains the string LEDA.GRAPH. If the graph type is not parameterized, i.e. graph or ugraph, the following two lines both contain the string void. In case the graph is parameterized ,i.e., GRAPH or UGRAPH, these lines contain a description of the node type and the edge type, which is obtained by calling the macro LEDA_TYPE_NAME. ii) Nodes Section The first line contains n, the number of nodes in the graph. The nodes are ordered and numbered according to their position in the node list of the graph. Each of the following n lines contains the information which is associated with the respective node of the graph. When the information of a node (or an edge) is sent to an output stream, it is always enclosed by the strings |{ and }|. If the graph is not parameterized, then the string between these parantheses is empty, so that all the n lines contain the string |{}|. iii) Edges Section The first line contains m, the number of edges in the graph. The edges of the graph are ordered by two criteria: first according to the number of their source node and second according to their position in the adjacency list of the source node. Each of the next m lines contains the description of an edge which consists of four space-separated parts: * the number of the source node * the number of the target node * the number of the reversal edge or 0, if no such edge is set * the information associated with the edge (cf. nodes section) Note: For the data type planar_map the order of the edges is important, because the ordering of the edges in the adjacency list of a node corresponds to the counter-clockwise ordering of these edges around the node in the planar embedding. And the information about reversal edges is also vital for this data type. b) The GraphWin (GW) File Format The gw-format is the external graph format of GraphWin. It extends LEDA's graph format described in the previous section by additional parameters and attributes for describing graph drawings. Note that the gw-format was not defined to be a readable or easy to extend file format (in contrast to the GML format that is also supported by GraphWin). Each gw file starts with a LEDA graph followed by a (possibly empty) layout section. An empty layout section indicates that no drawing of the graph is known, e.g. in the input file of a layout algorithm. If a layout section is given, it consists of three parts: 1) global parameters 2) node attributes 3) edge attributes i) Global Parameters The global parameter section consists of 7 lines (with an arbitrary number of inter-mixed comment-lines). * version line The version line specifies the version of of the gw-format. It consists of the string GraphWin followed by a floating-point number (1.32 for the current version of GraphWin). * window parameters scaling wxmin wymin wxmax wymax This line consists of 5 floating-point numbers specifiying the scaling, minimal/maximal x- and y-coordinates of the window (see the window class of LEDA). * node label font type size This line defines the font used for node labels. The type value of of type int. Possible values (see gw_font_type}) are 0 ( roman_font}) 1 ( bold_font}) 2 ( italic_font}) 3 ( fixed_font}). The size value is of type int and defines the size of the font in points. * edge label font type size as above, but defines the font used for edge labels. * node index format format This line contains a printf-like format string used for constructing the index label of nodes (e.g. %d}). * edge index format format This line contains a printf-like format string used for constructing the index label of edges (e.g. %d}). * multi-edge distance dist This line contains a floating-point parameter dist that defines the distance used to draw parallel edges. We close the description of the global parameter section with an example. # version GraphWin 1.32 # window parameters 1.0 -10.0 -5.0 499.0 517.0 # node font 0 12 # edge font 0 12 # node index string %d # edge index string %d # multi-edge distance 4.0 ii) Node Attributes The node attribute section contains for each node of the graph a line consisting of the following attributes (separated by blanks). More precisely, the i-th line in this section defines the attributes of the i-th node of the graph. * x-coordinate an attribute of type double defining the x-coordinate of the center of the node. * y-coordinate an attribute of type double defining the y-coordinate of the center of the node. * shape an attribute of type int defining the shape of the node. Possible values are (see gw_node_shape of GraphWin) 0 (circle_node) 1 (ellipse_node) 2 (square_node) 3 (rectangle_node) * border color an attribute of type int defining the color used to draw the boundary line of the node. Possible values are (see the LEDA color type) -1 (invisible) 0 (black) 1 (white) 2 (red) 3 (green) 4 (blue) 5 (yellow) 6 (violet) 7 (orange) 8 (cyan) 9 (brown) 10 (pink) 11 (green2) 12 (blue2) 13 (grey1) 14 (grey2) 15 (grey3) 16 (ivory). * border width an attribute of type double defining the width of the border line of the node. * radius1 an attribute of type double defining the horizontal radius of the node * radius2 an attribute of type double defining the vertical radius of the node * color an attribute of type int defining the color used to fill the interior of the node. See the LEDA color type for possible values. * label type an attribute of type int specifying the label type. Possible values (see gw_label_type of GraphWin) are 0 (no_label) 1 (user_label) 2 (data_label) 3 (index_label). * label color an attribute of type int defining the color used to draw the label of the node. See the LEDA color type for possible values. * label position an attribute of type int defining the label position. Possible values (see gw_position of GraphWin) are 0 ( central_pos) 1 ( northwest_pos) 2 ( north_pos) 3 ( northeast_pos) 4 ( east_pos) 5 ( southeast_pos) 6 ( south_pos) 7 ( southwest_pos) 8 ( west_pos). * user label an attribute of type string defining the user label of the node. We close this section with an example of a node attribute line that describes a circle node at position (189,260) with border color black, border width 0.5, horizontal and vertical radius 12, interior color ivory, label type index_label, label position east_pos, and an empty user label. # x y shape b-clr b-width radius1 radius2 clr l-type l-clr l-pos l-str 189.0 260.0 0 1 0.5 12.0 12.0 16 3 -1 4 iii) Edge Attributes: The edge attribute section contains for each edge of the graph a line consisting of the following attributes (separated by blanks). More precisely, the i-th line in this section defines the attributes of the i-th edge of the graph. * width an attribute of type double defining the width of the edge. * color an attribute of type color defining the color of the edge. * shape an attribute of type int defining the shape of the edge. Possible values (see gw_edge_shape of GraphWin) are 0 (poly_edge) 1 (circle_edge) 2 (bezier_edge) 3 (spline_edge). * style an attribute of type int defining the line style of the edge. Possible values (see the LEDA line_style type) are o (solid) 1 (dashed) 2 (dotted) 3 (dashed_dotted). * direction an attribute of type int defining whether the edge is drawn as a directed or an undirected edge. Possible values (see gw_edge_dir of GraphWin) are 0 (undirected_edge) 1 (directed_edge) 2 (redirected_edge) 3 (bidirected_edge). * label type an attribute of type int defining the label type of the edge. Possible values (see gw_label_type of GraphWin) are 0 (no_label) 1 (user_label) 2 (data_label) 3 (index_label). * label color an attribute of type int defining the color of the edge label. See the LEDA color type for possible values. * label position an attribute of type int defining the position of the label. Possible values (see gw_position of GraphWin) are 3 (central_pos) 4 (east_pos) 5 (west_pos blue ). * source anchor an attribute of type point defining the starting point of the edge relative to the position of the source node and the radii r1 and r2 of the node. Let (x,y) be the position of the source node of the edge and r1 and r2 the corresponding radii. Then the source anchor (dx,dy) means that the edge starts at (x + dx*r1, y + dy*r2) * target anchor an attribute of type point defining the ending point of the edge relative to the position of the target node and the radii r1 and r2 of the node. Let (x,y) be the position of the target node of the edge and r1 and r2 the corresponding radii. Then the target anchor (dx,dy) means that the edge ends at (x + dx*r1, y + dy*r2) * polyline an attribute of type list defining the polyline used to draw the edge. The list is represented by the number n of elements followed by n points (x_i,y_i) for i=1,...,n. The first element of the list is the point where the edge leaves the interior of the source node, the last element is the point where the edge enters the interior of the target node. The remaining elements give the sequence of bends (or control points in case of a bezier or spline edge). * user label an attribute of type string defining the user label of the edge. We close this section with an example of an edge attribute line that describes a blue solid polygon edge of width 0.5 drawn directed from source to target, with a black user-defined label "my label" at position east_pos, centered source and target anchors, and with a bend at position (250,265). # width clr shape style dir ltype lclr lpos sanch tanch poly lstr 0.5 4 0 0 1 1 1 4 (0,0) (0,0) 3 (202.0,262.0) (250.0,265.0) (328.0,274.0) my label iv) A complete example: Here is a complete example of a graph in LEDA GraphWin format: LEDA.GRAPH void void 5 |{}| |{}| |{}| |{}| |{}| 7 1 2 0 |{}| 1 3 0 |{}| 2 3 0 |{}| 3 4 0 |{}| 3 5 0 |{}| 4 5 0 |{}| 5 1 0 |{}| # version string GraphWin 1.320000 # scaling wxmin wymin wxmax wymax 1.117676 -10 -5.6875 499.8828 517.6133 # node label font and size 0 13.6121 # edge label font and size 0 11.79715 # node index format %d # edge index format %d # multi-edge distance 4.537367 # # node infos # x y shape bclr bwidth r1 r2 clr ltype lclr lpos lstr 189.4805 260.8828 0 1 0.544484 12.70463 12.70463 16 4 -1 4 341.5508 276.0898 0 1 0.544484 12.70463 12.70463 16 4 -1 4 384.4883 175.9023 0 1 0.544484 12.70463 12.70463 16 4 -1 4 294.1406 114.1797 0 1 0.544484 12.70463 12.70463 16 4 -1 4 186.7969 114.1797 0 1 0.544484 12.70463 12.70463 16 4 -1 4 # # edge infos # width clr shape style dir ltype lclr lpos sanch tanch poly lstr 0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (202.122,262.147) (328.9092,274.8257) 0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (201.1272,255.8074) (372.8415,180.9778) 0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (346.5554,264.4124) (379.4837,187.5797) 0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (373.998,168.7357) (304.6309,121.3463) 0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (372.361,172.116) (198.9242,117.966) 0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (281.436,114.1797) (199.5015,114.1797) 0.9074733 1 0 0 1 1 1 5 (0,0) (0,0) 2 (187.0292,126.8822) (189.2481,248.1803)