### The Graph Product Line

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:

• Vertex Numbering
• Connected components
• Strongly connected components
• Cycle checking
• Minimum spanning trees
• Single-Source Shortest Path

with the following types of graphs:

• Directed  graphs
• Undirected graphs
• Weighted graphs
• Unweighted graphs

Note: we assume that the weights in weighted graphs are always nonnegative and integer.

with the following graph search algorithms:

• Depth First Search (DFS)

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.

## On Implementation Issues

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  Sections 23.2, 23.3 Connected Components  Section 22.1, 23.2, 23.3 Strongly Connected Components  Section 23.5 Cycle Checking  Section 23.3 using DFS to detect back edges Minimum Spanning Trees  Section 24.2. Kruskal or Prim Algorithms Single-Source Shortest Path  Section 25.2. Dijkstra's Algorithm.