Возвращает количество ребер каждой вершины в орграфе (jgrapht)

У меня есть орграф, созданный с использованием:

    public static DirectedGraph<Point, DefaultEdge> directedGraph = new DefaultDirectedGraph<Point, DefaultEdge>(DefaultEdge.class);

 void setup() { 

  Point myPoint = new Point(x, y);
  Point myNextPoint = new Point(xToFillNext, yToFillNext);
  directedGraph.addVertex(myPoint);
  directedGraph.addVertex(myNextPoint);
  directedGraph.addEdge(myPoint, myNextPoint);

  Point mySecondPoint = new Point(x, y);
  Point mySecondNextPoint = new Point(xToFillNext, yToFillNext);
  directedGraph.addVertex(mySecondPoint);
  directedGraph.addVertex(mySecondNextPoint);
  directedGraph.addEdge(mySecondPoint, mySecondNextPoint);

System.out.println("#vertices: "+ directedGraph.vertexSet());

}

 public static class Point {

  public int x;
  public int y;

  public  Point(int x, int y) 
  {

    this.x = x;
    this.y = y;
  }
  @Override
    public String toString() {
    return ("[x="+x+" y="+y+"]");
  }

  @Override
public int hashCode() {
    int hash = 7;
    hash = 71 * hash + this.x;
    hash = 71 * hash + this.y;
    return hash;
}



@Override
public boolean equals(Object other) 
{
    if (this == other)
       return true;

    if (!(other instanceof Point))
       return false;

    Point otherPoint = (Point) other;
    return otherPoint.x == x && otherPoint.y == y;
}
}

Я хотел бы получить количество внешних ребер на вершину, используя:

directedGraph.outDegreeOf()

но я не хочу делать это вершина за вершиной (это простой код, чтобы его было проще пройти, во всей моей программе у меня гораздо больше вершин) и я хотел бы пройти набор вершин и вернуться количество внешних ребер для каждой вершины набора автоматически, независимо от того, сколько вершин есть.

Как мне это сделать?

(Я использую обработку, основанную на java)


java digraphs processing jgrapht
person Graham Slick    schedule 29.07.2015    source источник
comment
Что именно вы имеете в виду, когда говорите, что я не хочу делать это вершина за вершиной?   -  person Kevin Workman    schedule 29.07.2015

Ответы (2)


arrow_upward
1
arrow_downward

Ознакомьтесь с JGrapht API.

Интерфейс DirectedGraph содержит vertexSet(). Вы можете использовать это для перебора добавленных вами вершин, и вы можете получить outDegreeValue() каждой из них:

for(Point p : directedGraph.vertexSet()){
   int degree = directedGraph.outDegreeOf(p);
   System.out.println("Degree of " p.toString() + ": " + degree);
}
person Kevin Workman    schedule 29.07.2015

arrow_upward
0
arrow_downward

Я не уверен, хранит ли DirectedGraph эту информацию по своей сути или нет, но вы можете легко сохранить эту информацию при добавлении ребра, используя hasmap.

HashMap<Integer,Integer>  outEdgesMap = new HashMap<Integer,Integer>();

ты делаешь

directedGraph.addEdge(myPoint, myNextPoint);

после этого также сделать

outEdgesMap.put(myPoint,outEdgesMap.getOrDefault(myPoint,0)+1);

Просто для ясности, это будет

directedGraph.addEdge(myPoint, myNextPoint);
outEdgesMap.put(myPoint,outEdgesMap.getOrDefault(myPoint,0)+1);

Таким образом, ваш directedGraph.outDegreeOf() будет

        for(Integer i : outEdgesMap.keySet()){
             sout(i+ " : " +outEdgesMap.get(i) );
        }
person Karthik    schedule 29.07.2015
comment
Спасибо за вашу помощь! работает ли это после того, как я сделаю: System.out.println(outEdgedMap); отображать количество внешних ребер для каждой вершины? - person Graham Slick; 29.07.2015
comment
Нет, я добавил и эту часть. - person Karthik; 29.07.2015
comment
является ли outEdgesMap частью библиотеки jgrapht? Не могу ничего найти об этом, и моя программа, похоже, не распознает его. Нужно ли мне его определять? - person Graham Slick; 29.07.2015
comment
Это не часть библиотеки. Это простой HashMap, вы должны его определить. Я добавил это. - person Karthik; 29.07.2015