Clever Geek Handbook

JAVA Graph / DFS implementation

I have a little dilemma that I would like to consult -

I am implementing a graph (directional) and I want to make it extra generic - this is Graph, where T is the data in the node (top). To add a vertex to the graph, (T t) will be added. The graph will move T to the vertex, which will hold T inside.

Next, I would like to start DFS on the graph - now here is my dilemma - Should I store the "visited" sign at the vertex (as a member) or initiate some map when starting DFS (vertex map -> status)?

Keeping it at the top is less general (the top doesn't need to be familiar with the DFS algorithm and implementation). But map creation (vertex -> status) takes up a lot of space.

What do you think?

Thank you so much!

+3


source to share


1 answer


If you need to run algorithms, especially more complex ones, you will quickly find that you have to bind all kinds of data to your vertices. Having a common way of storing data using graph elements is a good idea, and of course the access times to read and write this data should be O (1) ideally. Simple implementations could be using a HashMap, which in most cases is O (1) time consuming, but the ratio is relatively high.

For the yFiles Graph Drawing Library, they added a mechanism where the data is actually stored by the elements themselves, but you can allocate as many data slots as you like. It's like manipulating Object[]

each element and using the index in the dataset as a "map". If your graph does not change, another strategy is to store the index of the elements in the graph with the elements themselves (integer only) and then using that index to index into an array where for each "data map" you have basically one array - size number of elements. Both methods scale very well and provide the best access times, unless your data is sparse enough (only a fraction of the elements actually need to store data).

The " Object[]

at Elements" approach :

  • In your vertex and border class, add a type field Object[]

    that is a private package.
  • Implement an interface Map

    that provides T getData(Vertex)

    and void setData(Vertex, T

    )
  • One implementation of this interface may be supported HashMap<Vertex,T>

    , but the one I assumed actually only stores an integer index

    , which is used for indexing in arrays Object[]

    at the vertices.
  • In your graph class, add a method createMap

    that keeps track of used and free indices and creates a new instance of the specified class, whose getter and setter implementations use the private field of the Vertex class package to actually access the data


One Array approach:

  • Add batch integer package field to Vertex class
  • Keep whole fields in sync with the order of the vertices in your graph - the first vertex has an index 0

    , etc.
  • In an alternative map implementation, you first select one T[]

    that is the size of the number of vertices.
  • In getter and setter implementations, you take the Vertex index and use that to access the values ​​in the array.

For the DFS algorithm, I would choose the "one array" -approach, as you could use byte [] (or if "Visit" is all it takes, you can even use BitSet

) for space efficiency and you will probably fill data for all vertices in DFS if your graph is connected. This should work much better than the HashMap approach and doesn't require boxing and unboxing to store the data in Object[]

.

+3


source






More articles:


All Articles