Note: this implementation is more practical for a lightweight problem, such as a programming competition or coding challenge.

The Classes

A lightweight implementation of the adjacency map still requires three classes, but can skimp on infrastructure. The three classes are:

Graph
Vertex
Edge

Class Implementations

Following is a list of methods and fields that each of the above classes should implement

Graph class:

Constructor: initializes list of vertices, list of edges
Add vertex method (identified by integers)
Add edge method (takes two integers)
(Optional) Depth first search (or any other methods/algorithms required specifically by the problem)

Vertex class:

Map of Vertex objects to Edge objects, to store connecting edges
Integer (element/identifier)
Method: get neighbors
Method: get element

Edge class:

List of Vertex objects
(Optional) int array (element/identifier)
Constructor: two vertices, set as endpoints
Method: get endpoints
Method: get element

Static Classes

To keep things simple, bundle everything as a single single class, and make the Graph, Vertex, and Edge classes static. The main objective here is implementing the algorithm and data structure, rather than coordinating permissions and access.

Exceptions

See Java/Exceptions

Easiest way to do this is to raise new IllegalArgumentException("Error message here")

Algorithms

// u is an empty dictionary
def dfs_connected(g):
    forest is empty dictionary
    for each vertex u in graph:
        if u not in forest:
            forest[u] = None
            do_dfs(g, u, forest)
    return forest

// complementary method: do depth first search
def do_dfs(g, u, discovered):
    for e in g.incident_edges(u):
        if v not in discovered:
            discovered[v] = e
            do_dfs(g, v, discovered)

Flags

Graphs/Java/Adjacency Map Lite

From charlesreid1

Contents