Welche Struktur für Repräsentation eines Netzwerks

[prolog]

Hallo,

Ich hab ein privates Projekt in Angriff genommen, bei dem es darum geht Firewallregeln ala ipchains zu testen. Zu diesem Zweck brauche ich eine Struktur die es mir ermöglicht das Netzwerk darzustellen. Obwohl ich am Anfang recht optimistisch war seh ich in der jetzigen Planungsphase schon Probleme. Ich weiss nicht recht welche Struktur ich am besten wählen soll. So ein Netzwerk kann sehr komplex werden. Später soll ein generiertes Packet über das Netzwerk gesendet werden. Es muss mir also möglich sein einen bestimmten Pfad im Netzwerk zu gehen. Es existieren Routerknoten die Subnetze verbinden. Und genau da ist auch schon das Problem. Da ich nicht weiss wie das Netz später aufgebaut ist muss ich einen Weg finden auf der Netzstruktur zu arbeiten, jeden Knoten erreichen können und verhindern das bei ungünstigen Konstellationen das Packet im Kreis läuft. Rein formal habe ich mir folgendes überlegt.

Ein Netzwerk ist eine Menge von 1 bis N Subnetzen die über spezielle Netzknoten(Router) verbunden sind.

Ein Subnetz ist eine Menge von Netzknoten die über ein Backbone verbunden sind.
(Für Subnetze denke ich ist ein vector gut geeignet)

Die Router ist ein Netzknoten der Mitglied zweier oder mehr Subnetze ist.
(Auch das lässt sich noch gut nachvollziehen)

Mein Problem ist die Struktur des Netzwerks. Wie stelle ich soetwas dar.
Es ist ja möglich dass sich innerhalb der Subnetze durch die Router Ringe bilden.

Wenn ich die günstigste Struktur gefunden hab muss ich mir natürlich noch einen Algorithmus zum "ablaufen" des Netzwerks nach bestimmten Regeln überlegen. Aber das kann ich erst machen wenn ich mir über die Struktur im klaren bin.

Ich hab an eine Baum gedacht dessen Knoten die Subnetze sind und jenachdem von wo das Packet los geschickt wird muss dieser Startpunkt dann die Baum-root sein. Ein Binärbaum ist aber nicht möglich, da nicht immer nur 2 Subnetze vorhanden sind.

Wie würdet ihr an sowas ran gehen. Ich brauch keinen Code oder sowas. "Nur" ne Idee (formal) wie man sowas repräsentieren kann.

Dank schon mal

[Gregor]

Wie wäre es mit nem Graphen? Einen Baum halte ich für schlecht, weil er keine Zyklen darstellen kann, die ja offensichtlich vorhanden sind.

[Gregor]

Hier ist als Beispiel mal eine Implementierung eines gerichteten Graphen in Java. Du wirst sicherlich einen nicht gerichteten Graphen benötigen, deshalb kannst du das nicht direkt übernehmen. Der prinzipielle Aufbau eines Graphen sollte aber klar werden. (natürlich gibt es auch andere Arten, einen Graphen zu implementieren)

package container;

import java.util.*;

public class DirectedGraph<ElementType> extends AbstractCollection<ElementType>
{
   private final HashMap <ElementType , Node> nodeMap;

   public DirectedGraph ()
   {
      nodeMap = new HashMap <ElementType, Node> ();
   }

   public DirectedGraph (final int initialCapacity)
   {
      assert(initialCapacity >= 0);
      nodeMap = new HashMap <ElementType, Node> (initialCapacity);
   }

   @Overrides
   public boolean add (final ElementType value)
   {
      if (value == null) return false;
      if (nodeMap.keySet().contains(value)) return false;
      nodeMap.put (value, new Node (value));
      return true;
   }

   @Overrides
   public void clear ()
   {
      nodeMap.clear();
   }

   @Overrides
   public boolean contains (final Object o)
   {
      return nodeMap.keySet().contains(o);
   }

   @Overrides
   public int size()
   {
      return nodeMap.size();
   }

   @Overrides
   public boolean remove (final Object value)
   {
      final Node node = nodeMap.get(value);
      if (node == null) return false;
      nodeMap.remove(value);
      removeConnections(node);
      return true;
   }

   private void removeConnections (final Node node)
   {
      final LinkedList<Node> successorList =
         node.getNeighborNodes(NeighborType.SUCCESSOR);
      final LinkedList<Node> predecessorList =
         node.getNeighborNodes(NeighborType.PREDECESSOR);
      for (final Node currentNode : successorList)
      {
         currentNode.removeNeighborNode(NeighborType.PREDECESSOR,node);
      }
      for (final Node currentNode : predecessorList)
      {
         currentNode.removeNeighborNode(NeighborType.SUCCESSOR,node);
      }
   }

   @Overrides
   public Iterator<ElementType> iterator()
   {
      return new GraphIterator ();
   }

   public void addEdge (final ElementType predecessor, final ElementType successor)
   {
      assert(predecessor != null);
      assert(successor != null);
      add(predecessor);
      add(successor);
      final Node predecessorNode = nodeMap.get(predecessor);
      final Node successorNode = nodeMap.get(successor);
      predecessorNode.addNeighborNode(NeighborType.SUCCESSOR,successorNode);
      successorNode.addNeighborNode(NeighborType.PREDECESSOR,predecessorNode);
   }

   public void removeEdge (final ElementType predecessor, final ElementType successor)
   {
      final Node predecessorNode = nodeMap.get(predecessor);
      if (predecessorNode == null) return;
      final Node successorNode = nodeMap.get(successor);
      if (successorNode == null) return;
      predecessorNode.removeNeighborNode(NeighborType.SUCCESSOR,successorNode);
      successorNode.removeNeighborNode(NeighborType.PREDECESSOR,predecessorNode);
   }

   private LinkedList<ElementType> getValuesFromNodes(final LinkedList<Node> nodeList)
   {
      final LinkedList<ElementType> valueList = new LinkedList<ElementType>();
      for (final Node node : nodeList)
      {
         valueList.add(node.getValue());
      }
      return valueList;
   }

   public LinkedList<ElementType> getDirectSuccessors (final ElementType value)
   {
      return getDirectNeighbors(NeighborType.SUCCESSOR, value);
   }

   public LinkedList<ElementType> getDirectPredecessors (final ElementType value)
   {
      return getDirectNeighbors(NeighborType.PREDECESSOR, value);
   }

   private LinkedList<ElementType> getDirectNeighbors (final NeighborType type,
                                                       final ElementType value)
   {
      assert(type != null);
      final Node node = nodeMap.get(value);
      if (node == null) return null;
      return getValuesFromNodes(node.getNeighborNodes(type));
   }

   public LinkedList<ElementType> getAllSuccessors (final ElementType value)
   {
      return getAllNeighbors(NeighborType.SUCCESSOR, value);
   }

   public LinkedList<ElementType> getAllPredecessors (final ElementType value)
   {
      return getAllNeighbors(NeighborType.PREDECESSOR, value);
   }

   private LinkedList<ElementType> getAllNeighbors (final NeighborType type,
                                                    final ElementType value)
   {
      assert(type != null);
      final Node node = nodeMap.get(value);
      if (node == null) return null;
      LinkedList<Node> currentNeighbors = node.getNeighborNodes(type);
      final LinkedList<ElementType> neighborList = new LinkedList<ElementType>();
      while (currentNeighbors.size() != 0)
      {
         final LinkedList<Node> nextNeighbors = new LinkedList<Node>();
         for (Node currentNode : currentNeighbors)
         {
            final ElementType currentValue = currentNode.getValue();
            if (neighborList.contains(value)) continue;
            neighborList.add(currentValue);
            nextNeighbors.addAll(currentNode.getNeighborNodes(type));
         }
         currentNeighbors = new LinkedList<Node>();
         for (Node currentNode : nextNeighbors)
         {
            if (currentNeighbors.contains(currentNode)) continue;
            currentNeighbors.add(currentNode);
         }
      }
      return neighborList;
   }

   private static enum NeighborType
   {
      PREDECESSOR(0), SUCCESSOR(1);

      private final int value;

      NeighborType(final int value)
      {
         this.value = value;
      }

      public int value()
      {
         return value;
      }
   }

   private class Node
   {
      private final ArrayList<LinkedList<Node>> neighbors;
      private final ElementType value;

      public Node (final ElementType value)
      {
         assert(value != null);
         neighbors = new ArrayList<LinkedList<Node>> (2);
         for (NeighborType type : NeighborType.values())
         {
            neighbors.add(type.value(),new LinkedList<Node>());
         }
         this.value = value;
      }

      public void addNeighborNode (final NeighborType type, final Node neighbor)
      {
         assert(neighbor != null);
         final LinkedList<Node> list = neighbors.get(type.value());
         if (list.contains(neighbor)) return;
         list.add(neighbor);
      }

      public void removeNeighborNode (final NeighborType type, final Node neighbor)
      {
         neighbors.get(type.value()).remove(neighbor);
      }

      public LinkedList<Node> getNeighborNodes (final NeighborType type)
      {
         return neighbors.get(type.value());
      }

      public ElementType getValue()
      {
         assert(value != null);
         return value;
      }
   }

   private class GraphIterator implements Iterator<ElementType>
   {
      private final Iterator<ElementType> keyIterator;
      private ElementType current;

      public GraphIterator ()
      {
         keyIterator = nodeMap.keySet().iterator();
      }

      public boolean hasNext()
      {
         return keyIterator.hasNext();
      }

      public ElementType next()
      {
         current = keyIterator.next();
         assert(current != null);
         return current;
      }

      public void remove()
      {
         if (current == null) throw new IllegalStateException();
         final Node node = nodeMap.get(current);
         assert(node != null);
         keyIterator.remove();
         removeConnections(node);
         current = null;
      }
   }
}

[prolog]

Hallo,

Danke für die schnelle Antwort. Das sieht sehr gut aus. Ich hatte an eine ähnliches Struktur bereits früher gedacht. Ich denke das ist eine Richtung in der ich weiter denken kann. Ich muss mich allerdings nochmal eingehend jetzt mit deinem Code beschäftigen um ihn vollständig zu verstehen. Ich hab auch an eine map von vectoren gedacht, bin aber über die Verbindungen gestolpert. Die Graphenstruktur scheint mir ja auf den ersten Blick etwas ähnliches zu sein.
Doch ich denk das ist was ich gesucht habe. Ich werde auch nochmal googlen um mehr über diese Struktur zu erfahren. Danke dir.

[prolog]

Hi

So ich hab mich jetzt eingehend mit dieser Datenstruktur beschäftigt und rausgefunden dass es definitiv das ist was ich brauche. Ich hab zunächst selbst einen Graphen in C++ implementiert, was auch gut funktionierte, ich stand dann allerdings vor dem Problem die Algorithmen die auf den Graphen arbeiten ebenfalls implementieren zu müssen. Dahinter steckt ne Menge Graphentheorie und das ist naturgemäß nicht so ganz einfach. Zum Glück hab ich entdeckt dass Boost die BGL anbietet womit Graphen recht einfach implementiert werden können.
Also wer mal was mit Graphen zu tun hat boost::graph. Es gibt auch noch andere Bibliotheken die sind aber i.d.R. nicht opensource.

Also danke nochmal dass du mich auf diese ADT aufmerksam gemacht hast. Nun kanns ja los gehen.