performance - JAVA Graph/DFS implementation -

i have small dilemma advised -

i'm implementing graph (directed) , want make generic - graph t data in the node(vertex). add vertex graph - add(t t). graph wrap t vertex hold t inside.

next run dfs on graph - here comes dilemma - should keep "visited" mark in vertex (as member) or initiate map while running dfs (map of vertex -> status)?

keeping in vertex less generic (the vertex shouldn't familiar dfs algo , implementation). creating map (vertex -> status) space consuming.

what think?

thanks lot!

if need run algorithms, more complex ones, find have associate kinds of data vertices. having generic way store data graph items idea , of course access time reading , writing data should o(1), ideally. simple implementations use hashmap, have o(1) acess time cases, factor relatively high.

for yfiles graph drawing library added mechanism data stored @ elements themselves, can allocate many data slots like. similar managing object[] each element , using index data array "map". if graph not change, strategy store index of elements in graph elements (just integer) , using index index array, each "data map" have 1 array size of number of elements. both techniques scale , provide best possible access times, unless data sparse (only fraction of elements need store data).

the "object[] @ elements" approach:

• in vertex , edge class, add field of type object[] package private.
• implement map interface provides t getdata(vertex) , void setdata(vertex, t)
• one implementation of interface backed hashmap<vertex,t> 1 suggesting stores integer index used index object[] arrays @ vertices.
• in graph class add method createmap keeps track of used , free indices , creates new instance of above class getter , setter implementations use package private field of vertex class access data

the "one array" approach:

• add package private integer field vertex class
• keep integer fields in sync order of vertices in graph - first vertex has index 0, etc.
• in alternative map implementation, allocate 1 t[] has size of number of vertices.
• in getter , setter implementations take index of vertex , use access values in array.

for dfs algorithm choose "one array"-approach use byte[] (or if "visited" required use bitset) space efficiency , populate data vertices in dfs if graph connected. should perform lot better hashmap based approach , not require boxing , unboxing storing data in object[].