How to do a toposort; creating in-degrees

Question

I am building a graph structure for a school assignment. It's currently represented as an adjacency list: I'm using a hashmap in which the keys are the nodes (vertices) of the graph and the values are lists of Edges (objects containing a source node and destination node pointer along with a "weight") associated with the key Node.

My next task is to code a topological sort, but I'm stuck. I think the best way to begin would be by giving each of my node objects an integer field for the indegree (amount of edges which lead to the node), but I can't come up with a way to assign this to all my nodes given what I already have.

Any suggestions?

Answer 1

I would suggest you to create also the concept of Node. Meaning besides you're Edge object you would also have the Node object, better modeling always helps you solve your problems faster. Having a HashMap defined with Node has a key Integer will help in this case, because you can store additional info in the Node instance.

But if you want/need to keep your current structure, in order to know how many edges are leading to a given node you'll have to iterate through the various values of the HashMap entrySet (which based on what you said will be lists of edges) and see which edges have the node you're looking for has a destination node, this information would have to be stored in an auxiliary structure though (such has another map)