Tamara Dominguez Poncelas Tamara Dominguez Poncelas - 4 months ago 7
Java Question

Degree of connectivity of a graph

I'm trying to calculate the degree of each node in a graph. However I'm having trouble because the nodes are part of the node class and I don't know how to convert them to

String
. At least I think that's what's wrong.
Here's what I've been trying, I have a
Hashset
where I store the nodes and another one for the edges (undirected graph), and I need to get a table with all the degrees that exists followed by the nodes that have those degrees:

public void DegreeList () {
List<Nodes> listnodes = new ArrayList<Nodes>(Node);
Map <Integer, List<Nodes>> DegreeList = new HashMap<Integer, List<Nodes>>();
for (Nodes n: Node){
int degree=0;
for (Edges e: Edge){
if (n.equals(e.start)||n.equals(e.end)){
degree++;
DegreeList.put(degree,n);
}
}
}

}


The error from Eclipse is for the last line and says:


The method put(Integer, List) in the type Map> is not applicable for the arguments (int, Nodes).


I'm open to try other approach.

Edit:
Nodes
and
Edges
are classes.
Edge
and
Node
are the
Hashsets
storing the values. (Sorry for any confusion)

Answer

Working Assumptions

It looks from your code as if the type Nodes represents a single node, and Node represents a Collection of nodes. (And that assumption was confirmed by your edit.) Those names seem backwards, but I'm going by what the code is doing with them. Please correct me if I'm wrong.

The Immediate Question

There are several problems here, but the immediate one is pretty simple: your Map expects a value of type List<Nodes>, but you're giving it a single instance of Nodes. If you can change your Map to a Guava Multimap then please do so. Otherwise, instead of

DegreeList.put(degree, n);

you'll need something like

List<Nodes> innerList = DegreeList.get(degree);
if (innerList == null) {
    innerList = new ArrayList<Nodes>();
    DegreeList.put(degree, innerList);
}
innerList.add(n);

That way there's a List associated with each degree. You need this because a Map can only store one value with each key. If your Map was defined like Map<Integer, Nodes> then you could only store one node with each distinct degree number. But that doesn't make any sense, does it? Any number of nodes could share the same degree number. So you need a Map that associates an Integer (representing degree) with a Collection of nodes. You seem to be using List as your chosen Collection. Set would probably be better.

Using Set, you'd define your Map as

Map<Integer, Set<Nodes>> degreeMap = new HashMap<>();

Then, when it came time to put something into the Map you'd do it like this:

Set<Nodes> innerSet = degreeMap.get(degree);
if (innerSet == null) {
    innerSet = new HashSet<>();
    degreeMap.put(degree, innerSet);
}
innerSet.add(n);

In either case you no longer need your listNodes List.

Other Observations

The code above describes how to put something into the Map. But we also need to think about when to put something into the Map. Right now you have code inserting into the Map each time there's an edge that matches the node you're evaluating:

for (Edges e: Edge){
    if (n.equals(e.start)||n.equals(e.end)){
        degree++;
        DegreeList.put(degree,n); // this shouldn't be here
    }
}
// instead, it belongs here

Instead, you should insert into the Map only once per node, after determining the node's degree:

for (Edges e: Edge){
    if (n.equals(e.start)||n.equals(e.end)){
        degree++;
    }
}

// insert into Map here
Set<Nodes> innerSet = degreeMap.get(degree);
if (innerSet == null) {
    innerSet = new HashSet<>();
    degreeMap.put(degree, innerSet);
}
innerSet.add(n);
Comments