by When using the UNIX System Laboratories (USL) C++ Standard Components
"Graph" library, is it possible to have a "dangling" Edge, i.e. an Edge with
zero or one destinations instead of two? Clearly, the dfs and bfs routines
wouldn't work with these Edges, but if, for example, one has auxiliary data
associated with these Edges (i.e. the Edge is a base class), one might not
always want to destroy an Edge every time an Edge is detached from one or more
of its Vertices.
It would appear, though, that the idea of such a "dangling" Edge is a
no-no, as the USL C++ Standard Components don't even provide constructors
that allow for the 0- or 1-destination Edge case.
This leaves the less-than-desirable option of having your
application's "edge" and "vertex" classes be derived from the same base class
which would, in turn, inherit the class Vertex so that the application's
"edge" and "vertex" classes would be bona fide Vertices, and all Graph
operations would be done with the assumption that there is an object of type
"edge" (derived from Vertex) between two "vertex" (also derived from Vertex)
objects. The problems here would be that
1. This adds an additional layer of complexity in that the Vertex class is
being made to do something it wasn't intended to do, and the Edge class
is being under-used. The GraphAlg algorithms would be similarly
compromised, as the doubling of the Vertex class as both a "vertex" and an
"edge" implies additional constraints that are impossible to impose on
routines like dfs() and bfs(). The GraphAlg algorithms would be rendered
next to useless (although the Ticket/set/etc. routines would still be
useful).
2. The fact that two types -- "edges" and "vertices" -- would be represented
by the Vertex class, and that programmer's convention would be the sole
determinant of which type is "connected" to what via the brain-dead Edge,
indicates to me that somewhere down the line, the type system would have
to be broken in order to do any but the most trivial of graph operations.
It's true that the notion of an edge without two defined reference
pointers violates the definition of a graph -- but if we forget about that for
a second, the problem at hand essentially boils down to this question:
+----------------------------------------------------------+
| Is the USL Graph/GraphAlg pair of components |
| powerful enough to handle a single Graph whose Vertices |
| can be of more than one class without some serious |
| stylistic transgressions? |
+----------------------------------------------------------+
Any replies, either posted to comp.lang.c++ or electronically mailed
bounce), are _greatly_ appreciated.
I am really not sure where to post this article, since the USL C++
Standard Components aren't totally tied into UNIX (although they do feature
special support for things like UNIX command-line arguments and UNIX
pathnames) and aren't really a part of the C++ language either (although if
any component libraries besides the ones already included in USL C++ Language
System Release 3.0.1 were candidates for inclusion, it should be these, at
least from the standpoint that USL is more closely tied in with C++ than any
other company due to cfront), so please be kind in your comments if you have
a better idea of where articles like these should go.
Thank you!
--
(Otherwise your mail will bounce!) The stuff contained in this article isn't
necessarily representative of what goes on at BNR; shame on you if you think it
does.