We offer the following domain as an example to compare and contrast approaches to the definition and implementation of product-line architectures. We believe this a good example, because it deals with a classical domain whose algorithms (i.e., graph algorithms) are common-knowledge to computer scientists. This relieves readers of burden and overhead that accompanies the understanding of an unfamiliar domain. (Also, there are lots of texts that discuss these very algorithms, so obtaining information on the domain should be easy).
In the following paragraphs we describe the family by stating the features -- i.e., algorithms, types of graphs, and searches -- a member could implement. A member of the family implements any valid combination of the following algorithms:
with the following types of graphs:
Note: we assume that the weights in weighted graphs are always nonnegative and integer.
with the following graph search algorithms:
That is, a family member can implement a valid combination of one or more graph algorithms, one directed or undirected graph that is weighted or unweighted, and exactly one search algorithm if required by the graph algorithms combination. For example, a family member could implement { vertex numbering, cycle checking, and strongly connected component} algorithms using an unweighted directed graph and depth-first search.
As in typical product-lines, not all combinations of features are valid. The table below summarizes the constraints for each algorithm. For example the combination of Connected Components and Strongly Connected Components is not valid because it would require that the graph be both directed and undirected at the same time.
| Algorithm | Searches that can be used | Graph Types Allowed | Weight Allowed |
| Vextex Numbering | BFS, DFS | Directed, Undirected | Weighted, Unweighted |
| Connected Components | BFS, DFS | Undirected | Weighted, Unweighted |
| Strongly Connected Components | DFS | Directed | Weighted, Unweighted |
| Cycle Checking | DFS | Directed, Undirected | Weighted, Unweighted |
| Minimum Spanning Trees | None | Undirected* | Weighted |
| Single-Source Shortest Path | None | Directed | Weighted |
* For simplicity we dont consider MST for directed graphs.
For example, if we want a member of our graph product line to implement Vertex Numbering, we could use either directed or undirected graphs, and either weighted or unweighted graphs. However if we want a member to implement Minimum Spanning Trees we are required to use weighted and undirected graphs, and no implementation of DFS or BFS is required. Similarly, to compute Single-Source Shortest Paths the member must implement directed and weighted graphs, and no implementation of DFS or BFS is required.
How you formally represent this domain is up to you and the method that you use. Regarding the implementation, we would appreciate if the resulting code is in Java, because this is the language we have used for our implementations and this would make the comparison more meaningful and accurate.
We provide references to the algorithms we are considering in the following table :
| Algorithm | Reference |
| Vextex Numbering | [1] Sections 23.2, 23.3 |
| Connected Components | [1] Section 22.1, 23.2, 23.3 |
| Strongly Connected Components | [1] Section 23.5 |
| Cycle Checking | [1] Section 23.3 using DFS to detect back edges |
| Minimum Spanning Trees | [1] Section 24.2. Kruskal or Prim Algorithms |
| Single-Source Shortest Path | [1] Section 25.2. Dijkstra's Algorithm. |
Please direct questions to: