alle zusammanhaengenden teilgraphen

Status
Nicht offen für weitere Antworten.

peetpan

Mitglied
Hallo Java-Forum,

mein Problem ist eigentlich nicht java-spezifisch, aber ich versuche es mit java zu loesen. Gegeben habe ich einen ungerichteten, zusammenhaengenden Graphen G mit n Knoten (Vector von Knoten, ein Knoten besitzt einen Vector aller Nachbarknoten). Weiter habe ich integer d<n gegeben. Ich moechte mir nun alle Teilgraphen von G ausgeben lassen, die d Knoten besitzen und zusammenhaengend sind. (Ausgabe zB alle entsprechenden Knoten Arrays der groesse d)

Ich koennte nun natuerlich alle d-Kombinationen betrachten und pruefen, ob Sie zusammenhaengend sind oder eine beschraenkte Breite-/Tiefensuche (von jedem Knoten aus) machen. In beiden Faellen betrachte ich aber sehr viele unnoetige Kombinationen oder viele Kombinationen mehrfach.

Meine Frage also: kennt jemand einen geschickten Algorithmus, der das Problem loest?

Vielen Dank, peetpan

ps: Das ist keine Hausaufgabe, gehoert also nicht in das entsprechende Unter-Forum ;)
 

Landei

Top Contributor
Ungetestet - und keine Ahnung, wie schnell das ist:
Java:
Set<Set<Knoten>> sets = new HashSet<Set<Knoten>>();
for(Knoten k : graph) {
   Set<Knoten> subSet = new HashSet<Knoten>();
   subSet.add(k);
   sets.add(subset);
}
for(int size = 2; size <= d; size++) {
    Set<Set<Knoten>> newSets = new HashSet<Set<Knoten>>();
    for(Set<Knoten> set : sets) {
        for(Knoten k :graph) {
            boolean connected = false;
            if (! set.contains(k)) {
                for(Knoten sk : set) {
                   if (sk.connectedTo(k)) {
                      connected = true;
                      break; 
                   }   
                }
                if (connected) {
                  Set<Knoten> newSet = new HashSet<Knoten>();
                  newSet.add(k);
                  newSet.addAll(set); 
                  newSets.add(newSet); 
                }
            } 
        }
    }
    sets = newSets;
}
//sets enthält alle Teilgraphen der Größe d
 

peetpan

Mitglied
Vielen Dank. Dein Vorschlag hat auf meine Test-Eingaben wunderbar funktioniert. Auch, was die Geschwindigkeit angeht ist es um Welten besser als das, was ich bisher zusammengeschustert hatte.

Ich werde mich dann mal ransetzen um zu verstehen, was du da gemacht hast ;) ich bin sonst nicht so der Programmierer. Z.B. verschachtelte Set/HashSet Typisierung seh ich das erste mal ...

Gruesse, peetpan
 

Marco13

Top Contributor
Nur so als Randbemerkung: Wenn der Eingabegraph ein vollständiger Graph ist, dann ist die Lösung gerade "Alle d-elementigen Teilmengen der Knotenmenge" - da führt selbst der geschickteste Algorithmus nicht dran vorbei. In Anlehung daran könnte man prinzipiell eine ähnliche Strategie verwenden wie beim ChoiceIterable in http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html , und bei jeder neuen Kombination püfen, ob sie zwei nicht-benachbarte Knoten enthält ... aber vielleicht kommt das genau auf das raus, was Landei geschrieben hat, oder Landei's Lösung ist noch geschickter (hab' sie auch nicht nachvollzogen)
 

peetpan

Mitglied
ja marco, das war auch ein ansatz von mir. (wenn du mit zwei nicht benachbart meinst, dass es zwei gibt, zwischen denen kein pfad existiert). aber ich betrachte oft graphen, die weit von vollstaendig entfernt sind und dann ist eine betrachtung aller d-elementigen knotenmengen doch recht aufwendig. meine graphen weisen zusaetzlich noch wiederkehrende muster auf ... da muss ich mal sehen, ob man das noch geschickt einfliessen lassen kann.
 

Marco13

Top Contributor
Hmja, vielleicht war das etwas unpräzise ausgedrückt. Ich dachte da an eine Art iterativen Prozess, wo man immer neue Knoten zur "d"-Menge hinzunimmt - und sobald davon einer nicht zu den anderen verbunden ist, kann man aufhören. Aber es stimmt schon: Das wäre vermutlich ziemlich ungeschickt. Einen Moment lang hab ich auch an einen Gomory-Hu-Tree gedacht, aber den auf genau dieses Problem umzubiegen wäre vermutlich so aufwändig, dass man gleich einen passenden Algorithmus schreiben kann. Was mich an der vorschlagenen Lösung ein bißchen stört, ist dieses "connectedTo", das da sehr weit innen steht, und ja eine Pfadsuche bedeutet... Man könnte überlegen, ob man das noch vermeiden könnte, aber eine spontane Idee habe ich nicht, und... wenn's funktioniert, ist's ja (erstmal) OK :rolleyes:
 

Landei

Top Contributor
connectedTo ist nur "direkte Nachbarschaft", keine Pfadsuche. Vielleicht etwas doof benannt von mir.

Der Code ist eigentlich total simpel: Suche alle Teilgraphen mit d=1 ---> das sind die einzelnen Knoten.
Dann teste für jeden Teilgraphen, ob du einen zusätzlichen Knoten "andocken" kannst und werfe diesen in das Set newSets. Natürlich treten dabei jede Menge Duplikate auf (wenn ich (ab) mit c verbinde, bekomme ich den gleichen Teilgraphen wie wenn ich (ac) mit b verbinde), aber es ist ja ein Set. Am Ende habe ich in newSets alle Teilgraphen, die eins größer sind, und das Spiel treibe ich dann immer weiter bis zum gewünschten d. Natürlich zwingt ein größerer oder stark vernetzter Graph meinen Ansatz in die Knie, ich sehe aber keinen cleveren Weg, das zu vermeiden.
Eventuell kann man noch etwas Speed rauskitzeln, wenn man jeden Teilgraph als geordnetes Array repräsentiert, was es einfacher macht, zwei Teilgraphen zu vergleichen oder zu bestimmern, ob ein Knoten schon in einem Teilgraphen ist.
 

peetpan

Mitglied
so, is nun zwar schon nen bischn her und ich habe lange mit einem algorithmus gearbeitet, der auf der version von landei basiert, aber ich habe nach etwas recherche einen algorithmus gefunden, der auf viele eingaben eine noch bessere laufzeit besitzt. also, falls mal jemand das selbe problem hat: der algorithmus basiert auf einem algorithmus in Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products / DP-Counter Analytics section 3.2.

1. nummeriere die knoten nach einer bfs ordnung

Java:
Queue<Node> q = new LinkedList<Node>();
Node start = graph.getBeliebigenKnoten();
start.setBFSNumber(0);
q.add(start);
int bfsCount = 1;
while(q.size()!=0)
{
  Node k = q.remove();
  for(Node ns:n.neighbors)
  {
    if(ns.bfsNumber()==-1)
    {
      ns.setBFSNumber(bfsCount);
      bfsCount++;
      q.add(ns);
    }
   }
}

2. Rufe rekursiv Algorithmus auf (siehe link)

Java:
TreeSet<Node> sorted = new TreeSet<Node>(graph.nodes);
Iterator<Node> it = sorted.descendingIterator();
for(int i=0;i<d-1;i++)
  if(it.hasNext())
    it.next();
while(it.hasNext())
{
  Set<Node> set = new HashSet<Node>();
  Node n = it.next();
  set.add(n);
  rec(set,sorted.headSet(n,true));
}

3. der rekursive part

Java:
private void rec(Set<Node> S,Set<Node> X)
{
  Set<Node> N = new HashSet<Node>();
  for(Node k:S)
    N.addAll(n.neighbors);
  N.removeAll(X);
  BPSIterator<Node> psi = new BPSIterator<Node>(N,1,d-S.size());
  while(psi.hasNext())
  {
    Set<Node> SSs = new HashSet<Node>(S);
    SSs.addAll(psi.next());
    if(SSs.size()==d)
    {
      // SSs ist ein gesuchter teilgraph
    }
    else
    {
      Set<Node> XN = new HashSet<Node>(X);
      XN.addAll(N);
      rec(SSs,XN);
    }
  }
}

4. BPSIterator ist ein "bounded powerset iterator", der ueber alle teilmengen der groesse groesser gleich from, kleiner gleich to iteriert

Java:
private class BPSIterator<E> implements Iterator<Set<E>>
{
  private E[] ele;
  private int[] pos;
  private boolean next;
  private int subSize;
  private int to;
		
  public BPSIterator(Set<E> set,int from,int to)
  {
    this.ele = (E[]) set.toArray();
    this.to=Math.min(to,set.size());
    this.subSize = from;
    if(this.subSize>this.to)
      this.next=false;
    else
      this.next = true;
    this.pos = new int[to];
    for(int i=0;i<this.subSize;i++)
      pos[i]=i;
  }
		
  public boolean hasNext()
  {
     return this.next;
  }
		
  public Set<E> next()
  {
    Set<E> subset = new HashSet<E>();
    for(int i=0;i<subSize;i++)
      subset.add(ele[pos[i]]);	
    incPos();
    return subset;
  }
		
  private void incPos()
  {
    boolean erw = true;
    for(int i=subSize-1;i>=0;i--)
    {
      if(pos[i]<ele.length-subSize+i)
      {
        pos[i]++;
        for(int j=1;j<subSize-i;j++)
          pos[j+i]=pos[i]+j;
        erw = false;
        break;
      }
    }
    if(erw)
    {
      if(subSize<to)
      {
         subSize++;
         for(int i=0;i<subSize;i++)
           pos[i]=i;
      }
      else
        next = false;
    }
  }
		
  public void remove() {}
}

falls jemand diesen ansatz verwenden sollte und verbesserungen hat, wuerde ich mich freuen die hier zu sehen ;)

lg, peetpan
 
Zuletzt bearbeitet:
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
Zrebna Wie ermittelt man alle testbaren (zu testenden) Klassen in seinem Maven-Projekt? Allgemeine Java-Themen 23
_user_q Alle Kombinationen von "0000" bis "FFFF" kompakt schrieben Allgemeine Java-Themen 13
_user_q JavaFX Robot alle Unicode-Zeichen schreiben lassen können Allgemeine Java-Themen 12
S Bookmark HTML Datei einlesen, alle Links erhalten und manche editieren..? (aktuell JSoup) Allgemeine Java-Themen 4
Sachinbhatt Sind alle Methoden in Java implizit virtuell Allgemeine Java-Themen 2
Kingamadeus2000 Alle mehrfach vorkommenden Buchstaben rekursiv aus einem String entfernen. Allgemeine Java-Themen 6
Drachenbauer wie kann ich alle instanzen einer Klasse durchsehen, ohne, dass diese in einer Liste erzeugt wurden? Allgemeine Java-Themen 11
8u3631984 Generelle Log4j.xml für alle Module Allgemeine Java-Themen 5
L Farbverlauf RGB alle Farben Allgemeine Java-Themen 28
W Server-Thread schreibt nicht alle Dateien Allgemeine Java-Themen 6
S Alle Dateinamen ermitteln Allgemeine Java-Themen 22
F Wie bekommt man alle Filenamen eines Webserver Verzeichnisses Allgemeine Java-Themen 6
S Kann ich eine Methode schreiben die alle Arten von funktionalen Interfaces akzeptiert..? Allgemeine Java-Themen 21
L Operatoren Java Reflections: Alle Methoden einer Klasse aufrufen ohne Exceptions Allgemeine Java-Themen 5
MaxG. Best Practice Alle Kombinationen berechnen Allgemeine Java-Themen 3
J Best Practice Objekt an alle Klassen verteilen ( Discord Bot ) Allgemeine Java-Themen 7
C BufferedReader/BufferedWriter schreibt nicht alle Bytes Allgemeine Java-Themen 2
J Alle Unit Tests in Maven Modul Projekt ausführen Allgemeine Java-Themen 7
S Anwendung die alle Abhaengigkeiten einer Library listet..? Allgemeine Java-Themen 5
T Alle Kombinationen aus zwei Arrays Allgemeine Java-Themen 8
K Nicht alle class-Dateien im JRE? Allgemeine Java-Themen 2
I Alle logs von Logger bekommen Allgemeine Java-Themen 3
U javax.mail.Folder.list() zeigt nicht alle Ordner Allgemeine Java-Themen 5
K Classpath Alle Classen aus einem Package lesen Allgemeine Java-Themen 7
L Alle möglichen Additionen (Rekursiv) Allgemeine Java-Themen 3
KaffeeFan Methoden replace alle Buchstaben Allgemeine Java-Themen 3
S Alle Methodenaufrufe eines Threads notieren..? Allgemeine Java-Themen 7
U Koordinaten alle Pixel eines Dreiecks zeichnen ausgeben Allgemeine Java-Themen 5
Z Eclipse hängt sich alle paar Sekunden auf (Keine Rückmeldung). Allgemeine Java-Themen 4
Seikuassi Alle Escape-Sequenzen in einem String ersetzen Allgemeine Java-Themen 4
F Java Spintax: Alle Kombinationen Erzeugen Allgemeine Java-Themen 2
Sogomn Klassen Alle in eine Klasse Allgemeine Java-Themen 11
P Methoden Alle Kombinationen aus 2 Karten berechnen Allgemeine Java-Themen 2
B Threads Barrier mit wait()/notify() aber nicht alle Prozesse terminieren Allgemeine Java-Themen 2
S .jar hat nicht alle Klassen ??? Allgemeine Java-Themen 10
T Wie kann ich alle existierenden Java-Klassen anzeigen lassen? Allgemeine Java-Themen 10
M Zufälligen String generieren und alle 5 Minuten ändern Allgemeine Java-Themen 2
M RegEx alle Matches ausgeben Allgemeine Java-Themen 5
A Applet Alle Threads beim schließen des Applets beenden Allgemeine Java-Themen 8
C SwingWorker.cancle(true) tötet alle Worker Allgemeine Java-Themen 3
B Methoden Alle Methoden und Variablen aus Java-Dateien auslesen. Allgemeine Java-Themen 7
T Alle Instancen einer Klasse auflisten Allgemeine Java-Themen 13
S Programm das alle aufgerufenen Methoden ausgibt..? Allgemeine Java-Themen 6
S Alle Kombinationen aus ArrayList - Potenzmenge Allgemeine Java-Themen 7
D Alle Variablen final setzen ? Allgemeine Java-Themen 26
brunothg Alle Kombiationen von n Ziffern Allgemeine Java-Themen 2
M Erste Schritte alle xmlFiles in zugehörige pdfFiles einlesen Allgemeine Java-Themen 4
B Variablen Alle RenderingHints.Keys (KEY_*) in Array + alle RenderingHints.Keys (VALUE_*) in Object[] Allgemeine Java-Themen 8
D generische Klasse für alle Maps (nicht Collections :-)) Allgemeine Java-Themen 11
E Logger loggt nicht alle Level Allgemeine Java-Themen 2
S Aus einer Liste<Oberklasse> alle Elemente die eine bestimmte Unterklasse von Oberklasse haben filter Allgemeine Java-Themen 8
K String: alle X Zeichen Zeilenumbruch Allgemeine Java-Themen 3
F Alle Exceptions abfangen Allgemeine Java-Themen 4
nrg JS als ScriptEngine - alle Punkte ersetzen Allgemeine Java-Themen 4
A Bildschirmauflösung geändert - alle Bildschirminhalte verschoben - was tun? Allgemeine Java-Themen 7
C Alle Klassen eines Packages lesen und instanzieren? Allgemeine Java-Themen 9
B Alle Exceptions auf einmal abfangen Allgemeine Java-Themen 4
S Warum packt er nicht alle Dateien? Allgemeine Java-Themen 13
J Alle Tage eines Jahres Allgemeine Java-Themen 2
AlexSpritze Alle Domains oder FQDN von einem Server erfragen? Allgemeine Java-Themen 2
Spot84 alle kombinationen einer string arraylist Allgemeine Java-Themen 2
S Alle Elemente von zwei Listen vergleichen Allgemeine Java-Themen 10
J Konstrukt um alle Paare und Tripel einer Punkte-Menge bilden Allgemeine Java-Themen 12
B Alle möglichen Buchstabenkombinationen in einem String Allgemeine Java-Themen 7
A alle nicht-dplikate finden Allgemeine Java-Themen 14
M Wie kann ich alle System.out Strings in ein log window umleiten? Allgemeine Java-Themen 6
E Alle unter Prozesse der beim schließen mit schließen Allgemeine Java-Themen 3
A An alle Cracks: Anwendung beenden mit ShutdownHook? Allgemeine Java-Themen 13
J Logger gibt nicht alle Level aus Allgemeine Java-Themen 3
M alle möglichen Zahlenkombinationen Allgemeine Java-Themen 5
B in welchem verzeichnis liegen alle installierten klassen? Allgemeine Java-Themen 6
hdi Für alle fleissigen Helfer! Allgemeine Java-Themen 15
N Alle Fehler ausgeben? Allgemeine Java-Themen 4
J Zweiter Prozess der alle x Sekunden etwas abfragen soll Allgemeine Java-Themen 2
O Auf alle Events reagieren Allgemeine Java-Themen 3
B J-Unit Tests. Alle Tests eines Package einsammen. Allgemeine Java-Themen 4
U alle Dateien eines Ordners innerhalb einer JAR auflisten Allgemeine Java-Themen 6
S toString() für alle Member einer Klasse. Allgemeine Java-Themen 6
G Alle möglichen Konfigurationen eines Baumes Allgemeine Java-Themen 4
C Alle Möglichen Substrings der Länge k aus String extrahieren Allgemeine Java-Themen 9
C Alle Bilder eines binären Arrays ausgeben Allgemeine Java-Themen 3
G Alle möglichen Permutationen einer Folge n Allgemeine Java-Themen 3
V Alle Klassen eines Package auflisten? Allgemeine Java-Themen 6
H JTable Löschen [Alle Zeilen aufeinmal Löschen] Allgemeine Java-Themen 6
@ RegEx: Alle Sonderzeichen ausser dem Punkt Allgemeine Java-Themen 4
G Alle Möglichen Kombinationen einer Liste Allgemeine Java-Themen 11
H Alle möglichen Hochkommata ausschließen Allgemeine Java-Themen 6
M Gibt es ein Jar - das alle Componente Automatisch anpasst? Allgemeine Java-Themen 14
K Suche alle Objekte einer bestimmten Klasse Allgemeine Java-Themen 2
N Unter Mac Os X alle laufenden Prozesse ausgeben Allgemeine Java-Themen 3
S Änderung an Proberties datei an alle User weitergeben? Allgemeine Java-Themen 7
P Observer, nicht alle updates bearbeiten Allgemeine Java-Themen 2
der JoJo [TreeSelection] wie bekomme ich alle Elemente Allgemeine Java-Themen 4
G Alle Zeichen des Alphabets ausgeben Allgemeine Java-Themen 4
G Alle Möglichkeiten n Elemente Anzuordnen. Allgemeine Java-Themen 13
0 Alle Teiler einer Zahl performant berechnen? Allgemeine Java-Themen 9
J Funktion alle Möglichkeiten berücksichtigen Allgemeine Java-Themen 5
O Warten bis alle gestarteten Threads beendet sind? Allgemeine Java-Themen 6
G HTML file Alle relativen URL in absolute URL umschreiben? Allgemeine Java-Themen 12
D FileWriter, PrintWriter und wie sie alle heißen. Allgemeine Java-Themen 13

Ähnliche Java Themen

Neue Themen


Oben