plag-mangler reads and writes its own file format, which is a representation of an undirected planar graph, and its embedding.
For the non-graph-theorist: A planar graph is one which can be laid out on a sheet of paper without any of the edges crossing. A planar embedding also specifies the precise layout. (Many planar graphs have multiple possible embeddings.)
The embedding is represented a an adjacency list for each vertex - that is, for each vertex, a list of the neighbouring vertices _in_order_.
plag-mangler looks at everything in anticlockwise order (following the the mathematicians' convention for positive angles).
Important for planar graphs is the concept of the face. (The 'outside' of the graph is regarded as a face too.) plag-mangler does not represent faces directly, but it can do various things to faces by finding the faces within the graph; data can be associated with faces by associating it with edge sides.
plag-mangler has a limited ability to associate additional information with each vertex and with each edge or each edge side:
- Each vertex has a unique name.
- Each vertex may be flagged as an outer vertex. The precise semantics of this vary depending on the operation.
- Each vertex may have a pair of floating point X/Y coordinates.
- Each edge has a flag indicating whether it was added (eg by the triangulation algorithm).
- Each side of each edge may be flagged as part of an outer face. It is not an error for only some of the edges to be so flagged.
- Each side of each edge may be annotated with a face name. It is not an error for the face names to be inconsistent on the edges of a face, or for different faces to have the same name.
Edge data which relates to a side of an edge is associated with the left hand side of the edge, or the face to the left of the edge, from the point of view of the direction of the edge currently being specified.
vertex-name
adjacent-vertex-1
adjacent-vertex-2
...
The plag file format is line-oriented. Lines are terminated by newlines. It is relevant whether a line is indented (ie, whether it starts with whitespace) but not by how much.
Lines starting with # (perhaps indented) are comments and are ignored. (Only whole line comments are allowed.) Blank lines are ignored.
Names and other strings may either start with an alphanumeric and be composed entirely of printing characters, or be quoted in "". Within ", plag-mangler understands the following escape sequences with their conventional meaning:
\\ \' \" \n \r \t \[0-7]{1,3} \xXX \uXXXX \UXXXXXXXX
A line starting with a % introduces a special-purpose section with its own syntax and semantics. Such a section ends with a line containing only a %.
An unindented name introduces a vertex. It starts a section of the file in which all indented lines refer to this vertex.
The vertex is identified by the name. The section will contain the adjacency list, vertex properties, and so on. Each vertex may have only one section.
An indented vertex name B within a vertex section A specifies that the vertex A has an edge to B. All the edges incident on A must appear in the section for A, in anticlockwise order. (Therefore if there is an occurrence of B in the section for A, there must also be an an occurrence of A in the section for B.)
Each edge may only occur once. Multi-edges are not supported.
Additional information relating to the whole graph may be specified, at any point, with an unindented line starting with a :.
The global directives are:
- :face-outer-exact
- Declares that the ^lface-outer directive will appear for every edge side in an outer face. An error will then reported if this is not the case.
Additional information relating to the whole graph may be specified within a vertex section with an indented line starting with a :, or with coordinates prefixed by @:
- :outer
- Marks this vertex as outer. Idempotent if repeated, although this is deprecated.
- @ x , y
- Specifies this vertex's coordinates, as floating point numbers. Any syntax supported by Rust's parser for f64 is allowed. Whitespace around the coordinates is also allowed. It is an error to specify multiple sets of coordinates for one vertex.
Additional information relating to an edge or an edge side may be specified within the section for one vertex (A) after an edge (to another vertex B) has been specified. For an edge side, the information relates to the left hand side, or the face to the left, of the edge A-B.
- ^added
- Sets the added flag for the edge. Idempotent if repeated, although this is deprecated. May be specified on either instance of the edge, or both, with equivalent effect.
- ^lface-outer
- States that the face to the left is an outer face. Without :face-outer-exact, the outer face flag will be propagated (idempotently) to all edge sides in this face.
- ^lface face-name
- Annotates this edge side with the string face-name. Different edge sides in the same face may have different annotations.