A graph data structure with approximation algorithms for finding a minimum dominating set and minimum connected dominating set. Apart from being a study in class design and architecture, it was created to demonstrate Clean Code principles and experiment with thorough testing during development.
This library consists of two graph data structures, DirectedGraph and UndirectedGraph, descending from a parent abstract Graph class. Both types of graphs can be taken as parameters to the static methods of a calculations class, DominatingSetCalculations, which implements approximation algorithms to find an approximate minimum dominating set and minimum connected dominating set for the input Graph. The output sets are approximations due to the minimum dominating set problem being NP-complete.
This library was designed with the intent of storing social media data from both Facebook and Twitter. This use case of approximating minimum dominating sets is to model the approximate smallest group of users among a set of connected users who would need to share information in order to reach all users in the data set.
- I wanted to create a DominatingSetCalculations class whose static methods could take any Graph as an input, but I wanted the Graph objects themselves to be distinguished as instances of DirectedGraph or UndirectedGraph for clarity in future use of this data structure. This caused me to explore generics and discover the hard way what kinds of difficulties that can arise from their use. I ultimately kept the use of generics within my abstract Graph class, but I had to dial things back a number of times in order to avoid generics hell.
- From a design standpoint, the biggest consideration I had to make was figuring out where to store Vertex adjacency and Edge directionality with as little reference duplication as possible. I ultimately decided to store two references for each Edge in a DirectedGraph, one from the value of the origin Vertex and one from the value of the destination Vertex, so that, given any Vertex, one could find both the in-Edges and the out-Edges. This was necessary for my minimum dominating set algorithm. For an UndirectedGraph, I stored only one reference to each Edge, always indexed from the lower Vertex value between the origin and destination vertices. That last point was a fairly simple concept, but it solved a host of problems for me in the way of preventing writing duplicate code for my calculations class, as the edges were always stored in a uniform fashion.
- Making a graph
- Finding an unconnected dominating set graph
- Finding a connected dominating set of a graph
To create a graph instance, invoke DirectedGraph or UndirectedGraph as a constructor function.
DirectedGraph directedGraph = new DirectedGraph();
UndirectedGraph undirectedGraph = new UndirectedGraph();Add vertices with addVertex
directedGraph.addVertex(0)
directedGraph.addVertex(1)
directedGraph.addVertex(2)
undirectedGraph.addVertex(0)
undirectedGraph.addVertex(1)
undirectedGraph.addVertex(2)Add edges with addEdge.
directedGraph.addEdge(0, 1);
directedGraph.addEdge(0, 2);
undirectedGraph.addEdge(0, 1);
undirectedGraph.addEdge(2, 0); // Ordering of edges does not matter for undirected graphsNow we have the following graphs:
Calculate an approximate minimum dominating set of either type of graph with the static greedy method of the DominatingSetCalculations class.
Set<Vertex> dominatingSetA = DominatingSetCalculations.greedy(directedGraph);
Set<Vertex> dominatingSetB = DominatingSetCalculations.greedy(undirectedGraph);The output for both calculations would be [0]. The following illustrates these sets:
Use the static connectedGreedy() method of the DominatingSetCalculations class.
Set<Vertex> dominatingSet = DominatingSetCalculations.connectedGreedy(graph)For the following graph containing an unconnected vertex, the output would be an empty set, as a connected dominating set cannot be generated:
For the following graph, the output would be [1, 2, 6], as the set must include vertex 2 in order to be connected:
# DirectedGraph()
Constructs a DirectedGraph instance.
# UndirectedGraph()
Constructs an UndirectedGraph instance.
# graph.addVertex(vertex)
Adds a vertex of value vertex. Throws an exception if a vertex of value vertex already exists.
# graph.removeVertex(vertex)
Removes the vertex with value vertex. Throws an exception if a vertex of value vertex does not exist.
# graph.addEdge(u, v)
Adds an edge between vertices u and v. The direction of the edge will only be stored if the calling Graph is a DirectedGraph instance. Throws an exception if either vertex u or vertex v already exists.
# graph.removeEdge(u, v)
Removes the edge between vertices u and v. The ordering of u and v are only considered if the calling Graph is a DirectedGraph instance. Throws an exception if the edge does not exist.
# graph.getVertexMap()
Returns a Map<Integer, Vertex> object representing all vertices within the graph mapped from their corresponding Integer values.
# graph.getEdgeMap()
Returns a Map<Integer, Set<Edge>> object representing all edges within the graph.
In a DirectedGraph instance, each Edge reference is stored in the Set corresponding to the value of its origin Vertex.
In an UndirectedGraph instance, each Edge has a reference stored at value of each of its corresponding vertices.
# graph.getNumEdges()
Computes the number of edges within the graph.
# graph.clone()
Returns a new Graph instance of the caller's type with the same vertices and edges as the calling graph. This new graph be altered without altering the original graph.
The DominatingSetCalculations class comes with the following three static methods:
# greedy(graph)
Returns a Set<Vertex> object representing an approximate minimum dominating set for the input graph using a greedy algorithm.
# connectedGreedy(graph)
Returns an Optional<Set<Vertex>> object representing an approximate minimum connected dominating set for the input graph using a greedy algorithm. If no set can be found due to the graph being disconnected, an empty Optional object is returned.
# verify(dominatingSet, graph)
Returns true if the input Set<Vertex> object represents a Dominating Set for input graph and false if not.