Hi Leute,
Ich muss einen ungerichteten Graphen zufällig erstellen. Das ist eigentlich nicht das Problem, das Problem, vor dem ich stehe ist viel eher, dass ich auch die Zeichenpositionen mitgeben muss. Weiß jemand von euch, wie man das machen kann, oder welche Library man benutzen kann?
Danke schoneinmal im Vorraus.
hello_world
Was haben Zeichenpositionen mit ungerichteten Graphen zu tun?
Ich stelle mir unter einem ungerichteten Graphen etwas in der Art vor:
private Set<Edge> edges;
// ...
}```
```public class Edge {
private Node target;
private Edge inverse;
// ...
}```
*** Edit ***
Meinst du mit "Zeichenposition" den Ort auf einer Zeichenfläche? Dann geht es sicherlich um die Anordnung der Knoten. Eine mir bekannte Bibliothek ist [yFiles](http://www.yworks.com/de/products_yfiles_about.html). Dort sind auch Layoutalgorithmen implementiert.
*** Edit ***
Zur Lizenz:
> Für die Benutzung in akademischer Forschung und Lehre sind akademische Lizenzen erhältlich.
Naja, schreib erstmal, was du genau benötigst.Ich bekomme das ohne externe Lib hin
[spoiler]```public class GraphTest {
private static final Random RANDOM = new Random();
public static class NodePair {
private Node node1;
private Node node2;
public NodePair(Node node1, Node node2) {
this.node1 = node1;
this.node2 = node2;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime
* result
+ (((node1 == null) ? 0 : node1.hashCode()) + ((node2 == null) ? 0
: node2.hashCode()));
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
NodePair other = (NodePair) obj;
List<Node> thisNodes = Arrays.asList(node1, node2);
return thisNodes.contains(other.node1)
&& thisNodes.contains(other.node2);
}
}
static class Node {
private final int xPos;
private final int yPos;
private Collection<Node> neighbours = new HashSet<GraphTest.Node>();
public Node(int xPos, int yPos) {
super();
this.xPos = xPos;
this.yPos = yPos;
}
public void addNeighbour(Node node) {
neighbours.add(node);
node.addNeighbourInternal(this); // ungertichtet= beide Knoten kennen sich...
}
private void addNeighbourInternal(Node node) {
neighbours.add(node);
}
public void paint(Graphics2D g, Set<NodePair> drawnPairs) {
drawPoint(g,this);
for (Node node : neighbours) {
NodePair nodePair = new NodePair(this, node);
if (!drawnPairs.contains(nodePair)) { // endlosschleife verhindern, aben ja keinen BlueGene/L, der das in 10 Min schafft...
drawnPairs.add(nodePair);
g.drawLine(xPos, yPos, node.xPos, node.yPos);
drawPoint(g,node);
}
}
}
private void drawPoint(Graphics2D g, Node node) {
g.drawOval(node.xPos - 2, node.yPos - 2, 5, 5);
g.drawOval(node.xPos - 3, node.yPos - 3, 7, 7);
}
}
private static final int PANEL_SIZE_X = 500;
private static final int PANEL_SIZE_Y = 500;
public static void main(String[] args) {
final List<Node> graph = new ArrayList<GraphTest.Node>();
for (int i = 0; i < 10; i++) {
Node node = new Node(RANDOM.nextInt(PANEL_SIZE_X),
RANDOM.nextInt(PANEL_SIZE_Y));
for (Node previousNode : graph) {
if (RANDOM.nextBoolean() && RANDOM.nextBoolean()) {
previousNode.addNeighbour(node);
}
}
graph.add(node);
}
JPanel jPanel = new JPanel() {
private static final long serialVersionUID = 1L;
@Override
public void paint(Graphics g) {
super.paint(g);
for (Node node : graph) {
Set<NodePair> drawnPairs = new HashSet<GraphTest.NodePair>();
node.paint((Graphics2D) g, drawnPairs);
}
}
@Override
public Dimension getMinimumSize() {
return new Dimension(PANEL_SIZE_X, PANEL_SIZE_Y);
}
@Override
public Dimension getPreferredSize() {
return super.getMinimumSize();
}
@Override
public Dimension getSize(Dimension rv) {
return getMinimumSize();
}
};
JFrame jFrame = new JFrame("test");
jFrame.getContentPane().add(jPanel);
jFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
jFrame.setSize(PANEL_SIZE_X+5,PANEL_SIZE_Y+5);
jFrame.setVisible(true);
}
}```[/spoiler]
Gelegentlich bleiben einzelne Punkte ohne Nachbarn übrig, die könnte man beim Zeichnen raus filtern…
bye
TT
Ich denke auch, dass genauer geklärt werden müßte, was mit “Zeichenposition” gemeint ist. Das Layout ist im besten Fall weitgehend unabhängig von der eigentlichen Struktur des Graphen. yFiles ist natürlich eine Hausnummer, aber je nach Budget und Anwendungsbereich gibt es auch Alternativen, von der (schon etwas älteren, aber sehr verbreiteten) http://jung.sourceforge.net/ bis zu sowas wie https://github.com/jgraph/jgraphx oder 1000 anderen…
Das kommt ganz darauf an, was man machen möchte. Automatische Layoutalgorithmen (das sind eigentlich „nur“ Constraintsolver) sind nicht ganz so leicht umzusetzen. Das ist (im wahrsten Sinne des Wortes) eine Wissenschaft für sich.
Außerdem würde ich die Kanten explizit modellieren, siehe mein obiger Ansatz. Ein „NodePair“ hat den Nachteil, dass man nicht genau weiß, ob der zu betrachtende Knoten der erste oder der zweite ist.
Das Modell mit zwei halben Kanten hat den Vorteil, dass sie jeweils gerichtet sind und man somit den Graphen sehr leicht traversieren kann. Die entgegengesetzte Kante gehört immer zur Kante dazu, wodurch ein ungerichteter Graph entsteht.
Ich hatte mich nur daran erinnert, dass wir damit in der Uni gearbeitet haben. Das war aber glaube ich nur das kostenlose yEd, in das wir generierte Daten importiert haben. Damit kann man dann verschiedene Layoutalgorithmen ausprobieren.
Aber vielleicht war das mit den „Zeichenpositionen“ ganz anders gemeint. Ich hatte „Zeichenpositionen“ zuerst im Sinne von „Buchstabenpositionen“ verstanden… Die Sprache ist nicht eindeutig 
[quote=cmrudolph]Das kommt ganz darauf an, was man machen möchte.[/quote]Richtig.
Ich denke aber dass mein Ansatz die Anforderungen des TO voll erfüllt.
bye
TT
Erst mal sagst du uns, was ein Knoten und was eine Kante für dich ist (was du dir darunter vorstellst), und dann, was du mit Zeichenposition(en) meinst. Ungerichtet heißt für mich so was wie bidirektional. Erstelle 'ne Liste mit Knoten, mische sie, verbinde wiederholt (paarweise) Knoten (i+0+x), (i+1+x), (i+2+x), etc. mit x=0, x=3 usw. :grr: