UndirectedEdges

<<TableOfContents: execution failed [Argument "maxdepth" must be an integer value, not "[2]"] (see also the log)>>

About this document

This is an official Request for Comment (RFC) for Making undirected edges first-class citizens.

For details on RFCs in general, check out the Wikipedia Entry: Request for Comments (RFCs)

Status

Open for public comment, implementation being done as a Google Summer of Code project. See DanielAbel/EdgeDirectionality.

To view/add comments, click on any of 'Comment' links below. By adding your ideas to the Wiki directly, we can more easily organize everyone's ideas, and keep clear records. Be sure to include today's date and your name for each comment. Here is an example to get things started: /Comment.

Try to keep your comments as concrete and constructive as possible. For example, if you find a part of the RFC makes no sense, please say so, but don't stop there. Take the extra step and propose alternatives.

Proposal

Although the current base libraries Cytoscape is built on support undirected edges (see for example CyEdge.isDirected() or the "directed" flag of one of the Cytoscape.getCyEdge() methods), Cytoscape as a whole doesn't really handle undirected edges. The aim of this RFC is to fix this by fixing all the places where undirected edges not handled correctly:

• the two endpoints of an undirected edge must look the same, so vizmapper should make it impossible the set separate start and end graphics for them.
• file-formats should explicitly handle or drop undirected edges. For example currently sif treats edges as directed. This should be codified by declaring that sif files contain undirected edges, and when doing an export, warning if the network that is exported contains undirected edges, too.

Open Issues

Backward Compatibility

As the sorry state of undirected edges can be seen as a bug, none of these changes can possibly break backward compatibility.

References

• from Notes from the 2006 hackathon: "refactor Cytoscape to deprecate methods that contain boolean directed in the signature (and add a new method that doesn't have the directed flag to replace them)."

  I (DanielAbel) think this (i.e. removing undirected edges completely) should be avoided.

• discussion on cytoscape-discuss at http://groups.google.com/group/cytoscape-discuss/browse_thread/thread/0b76566844557012

Implementation Plan

• declare that handling undirected edges is important
• fix all places where undirected edges are handled incorrectly:
  • check all fileformats. For each, decide whether having the fileformat store only directed edges is acceptable. If yes, document that (if needed) and add a check to the writer code (i.e. the code that export files in that fileformat) to check that the network being imported has only directed edges. (If it has at least 1 undirected edge, warn the user or abort the export altogether.) If needed, new filetypes can be added (for example a .suf format, for "simple undirected format" which is the same as .sif. exempt is treated as undirected).

  • add a "import as directed / undirected" radiobutton-pair to TableImport (see also bug no. 1324)

  • add an "undirected edge end" settable option to vizmapper (at the same place where "edge source arrow" and "edge target arrow" is currently).

  • add the possibilty of creating UndirectedEdge type undirected edges with the default editor

  • write unittests as needed.
• (if needed) check that other parts of the code (for example, plugins) don't assume that all edges are directed. If they do, despite the low-level support for undirected edges, those are bugs anyway, which need to be fixed. I don't know of any parts of the code that has such problems, but the "edges are directed" assumption might be too ingrained.

Comments

The directed flag of Cytoscape.getCyEdge() doesn't mean "make sure that the edge returned is of that directionality" but means "if set to false, check in other direction, as well" this means that getCyEdge() will return edges with the opposite directionality. (i.e. if 'directed' is set to false, it can still return directed edges, and if it is set to true, it can return undirected edges). I don't know whether this 'misfeature' should be kept or fixed. It is only triggered if directed and undirected edges are created with the same interaction-type.

In general, a decision needs to be made about the identity of edges: currently the unique identifying features of an edge are its source and target vertices (or endpoints for undirected edges), and the interaction type. directedness is not used. I don't know whether this should be corrected or not. (For example it means that after creating an a->b directed edge, asking for an b-a undirected edge with getCyEdge(b,a,...,'foo', false, false) will return that directed edge.) -- DanielAbel

See also bug no. 1351 -- DanielAbel