Directed Graph

[Nestharus]

Directed graph supporting both standard anonymous vertices and tabular keyed vertices with bitmask support along edges. Keyed breadth-first iterator support with correct expansion behavior. Phase 1 in compiler construction.



Example

   public static void main(String[] args)
{
   int privateAccessModifier = 0b11;
   int protectedAccessModifier = 0b10;
   int publicAccessModifier = 0b00;

   int scopeEdge = 0b001;
   int inheritanceEdge = 0b010;
   int symbolEdge = 0b100;

   Graph<Integer, Integer> graph = new Graph();
   Vertex<Integer, Integer> root = graph.getRoot();


   /*
            9 {
               private 10
               public 11
            }
            1 {
               private 2
               public 3
               public 4 extends public 9 {
                  private 8
                  private {
                     private 5
                     public 6
                     public 7
                  }
               }
            }
    */

   // searching for 11
   // our origin is 4
   // only search symbol edges

   Vertex<Integer, Integer>[] vertex = new Vertex[12];

   vertex[0] = new Vertex<Integer, Integer>(null, null);

   for (int i = 1; i <= 11; ++i)
   {
      vertex[i] = new Vertex<Integer, Integer>(i, i);
   }

   vertex[0].addExplicitEdge(symbolEdge, privateAccessModifier, publicAccessModifier, vertex[5]);
   vertex[0].addExplicitEdge(symbolEdge, publicAccessModifier, publicAccessModifier, vertex[6]);
   vertex[0].addExplicitEdge(symbolEdge, publicAccessModifier, publicAccessModifier, vertex[7]);
   vertex[0].addImplicitEdge(scopeEdge, privateAccessModifier, privateAccessModifier, vertex[4]);

   vertex[4].addExplicitEdge(symbolEdge, privateAccessModifier, publicAccessModifier, vertex[0]);
   vertex[4].addExplicitEdge(symbolEdge, privateAccessModifier, publicAccessModifier, vertex[8]);
   vertex[4].addImplicitEdge(scopeEdge, privateAccessModifier, privateAccessModifier, vertex[1]);
   vertex[4].addExplicitEdge(symbolEdge | scopeEdge | inheritanceEdge, publicAccessModifier, protectedAccessModifier, vertex[9]);
   vertex[4].addImplicitEdge(scopeEdge | inheritanceEdge, publicAccessModifier, protectedAccessModifier, vertex[9]);

   vertex[9].addExplicitEdge(symbolEdge, privateAccessModifier, publicAccessModifier, vertex[10]);
   vertex[9].addExplicitEdge(symbolEdge, publicAccessModifier, publicAccessModifier, vertex[11]);
   vertex[9].addImplicitEdge(scopeEdge, privateAccessModifier, privateAccessModifier, root);

   vertex[1].addExplicitEdge(symbolEdge, privateAccessModifier, publicAccessModifier, vertex[2]);
   vertex[1].addExplicitEdge(symbolEdge, publicAccessModifier, publicAccessModifier, vertex[3]);
   vertex[1].addExplicitEdge(symbolEdge | scopeEdge, publicAccessModifier, publicAccessModifier, vertex[4]);
   vertex[1].addImplicitEdge(scopeEdge, privateAccessModifier, privateAccessModifier, root);

   root.addExplicitEdge(symbolEdge | scopeEdge, publicAccessModifier, publicAccessModifier, vertex[1]);
   root.addExplicitEdge(symbolEdge | scopeEdge, publicAccessModifier, publicAccessModifier, vertex[9]);

   Graph.Iterator<Integer, Integer> iterator = new Graph.Iterator<>(symbolEdge, 0, vertex[4], 11);
   Graph.Iterator.Match<Integer, Integer> bestMatch = null;
   Graph.Iterator.Match<Integer, Integer> currentMatch;

   /*


            BRB

    */


   // a.b.c
   while (iterator.hasNext() && (bestMatch == null || !bestMatch.isLegal() || bestMatch.getDistance() > 0))
   {
      currentMatch = iterator.next();

      if (currentMatch != null && !currentMatch.getEdge().isImplicit() && currentMatch.getDistance() >= 0 && (bestMatch == null || (currentMatch.getDistance() > bestMatch.getDistance() && (bestMatch.isLegal() || !currentMatch.isLegal()))))
      {
         bestMatch = currentMatch;
      }
   }

   System.out.println(String.valueOf(bestMatch.getEdge().getDestination().getValue()) + " " + bestMatch.isLegal());
   }

package com.nes.sym.graph;

import java.util.*;

// anonymous edges ALWAYS require bitmask
// keyed do not require bitmask for iterator or search
// for search, find the BEST match
// any legal match is better than an illegal match, but an illegal match due to insufficient bitmask is better than nothing

public class Graph<K extends Comparable, V>
{
   private Vertex<K, V> root;

   public Graph()
   {
      root = new Vertex<K, V>(null, null);
   }

   public Vertex<K, V> getRoot()
   {
      return root;
   }

   // between each search, need to store the privileges by the new origin
   // whenever a new origin is returned, check if that origin already exists and use the privileges
   // that were previously assigned to that origin if it does already exist
   // this is to prevent privileges from being stripped when they shouldn't be
   // single search is ok. Multi-search requires history.
   public static class Iterator<K extends Comparable, V> implements java.util.Iterator
   {
      @Override
      public void remove()
      {

      }

      public static class SearchResult<K extends Comparable, V>
      {
         private Stack<Match<K, V>> matches;
         private Map<Vertex<K, V>, Integer> maskTable;

         public SearchResult()
         {
            matches = new Stack<>();
            maskTable = new HashMap<>();
         }

         public Stack<Match<K, V>> getMatches()
         {
            return matches;
         }

         public Map<Vertex<K, V>, Integer> getMaskTable()
         {
            return maskTable;
         }
      }

      public SearchResult<K, V> search(int edgeTypeMask, int bitmask, Vertex<K, V> origin, Collection<K> keys)
      {
         Graph.Iterator<Integer, Integer> iterator = new Graph.Iterator<>(symbolEdge, 0, vertex[4], 11);
         Graph.Iterator.Match<Integer, Integer> bestMatch = null;
         Graph.Iterator.Match<Integer, Integer> currentMatch;

         SearchResult<K, V> searchResult = new SearchResult<>();
         searchResult.getMaskTable().put(origin, bitmask);

         for (K key : keys)
         {

         }

         // a.b.c
         while (iterator.hasNext() && (bestMatch == null || !bestMatch.isLegal() || bestMatch.getDistance() > 0))
         {
            currentMatch = iterator.next();

            if (currentMatch != null && !currentMatch.getEdge().isImplicit() && currentMatch.getDistance() >= 0 && (bestMatch == null || (currentMatch.getDistance() > bestMatch.getDistance() && (bestMatch.isLegal() || !currentMatch.isLegal()))))
            {
               bestMatch = currentMatch;
            }
         }

         System.out.println(String.valueOf(bestMatch.getEdge().getDestination().getValue()) + " " + bestMatch.isLegal());
      }

      public static class Match<K extends Comparable, V>
      {
         private int bitmask;
         private boolean legal;
         private int distance;
         private Edge<K, V> edge;

         public void setBitmask(int bitmask)
         {
            this.bitmask = bitmask;
         }

         public int getBitmask()
         {
            return bitmask;
         }

         public boolean isLegal()
         {
            return legal;
         }

         public void isLegal(boolean legality)
         {
            this.legal = legality;
         }

         public void setDistance(int distance)
         {
            this.distance = distance;
         }

         public int getDistance()
         {
            return distance;
         }

         public void setEdge(Edge<K, V> edge)
         {
            this.edge = edge;
         }

         public Edge<K, V> getEdge()
         {
            return edge;
         }

         @Override
         public Match<K, V> clone()
         {
            Match<K, V> match = new Match<>();

            match.bitmask = bitmask;
            match.legal = legal;
            match.distance = distance;
            match.edge = edge;

            return match;
         }
      }

      public static class Path<K extends Comparable, V>
      {
         private Collection<Edge<K, V>> frontier;
         private int bitmask;

         public Collection<Edge<K, V>> getFrontier()
         {
            return frontier;
         }

         public void setFrontier(Collection<Edge<K, V>> frontier)
         {
            this.frontier = frontier;
         }

         public int getBitmask()
         {
            return bitmask;
         }

         public void setBitmask(int bitmask)
         {
            this.bitmask = bitmask;
         }
      }

      private Match<K, V> match;
      private Collection<Path<K, V>> frontier;
      private java.util.Iterator<Path<K, V>> frontierPathIterator;
      private java.util.Iterator<Edge<K, V>> frontierEdgeIterator;

      private Path<K, V> currentPath;

      private K key;
      private int edgeTypeMask;

      public Iterator(int edgeTypeMask, int bitmask, Vertex<K, V> origin, K key)
      {
         this.key = key;
         this.edgeTypeMask = edgeTypeMask;

         match = new Match<>();
         match.setBitmask(bitmask);
         match.setDistance(-1);
         match.isLegal(false);
         match.setEdge(null);

         frontier = new LinkedList<>();
         Path<K, V> path = new Path<>();
         path.setBitmask(bitmask);
         path.setFrontier(new LinkedList<>());
         frontier.add(path);

         origin.getEdges(key, path.getFrontier());
         origin.getEdges(origin, bitmask, path.getFrontier());

         frontierPathIterator = frontier.iterator();
         currentPath = frontierPathIterator.next();
         frontierEdgeIterator = currentPath.getFrontier().iterator();
      }

      private boolean nextEdge()
      {
         Edge<K, V> edge;
         int distance;
         boolean search = true;

         while (frontierEdgeIterator.hasNext() && search)
         {
            edge = frontierEdgeIterator.next();

            if ((edge.getEdgeTypeMask() & this.edgeTypeMask) == edge.getEdgeTypeMask())
            {
               if (edge.isImplicit())
               {
                  match.setEdge(edge);
                  match.setBitmask(currentPath.getBitmask());
                  match.isLegal(true);
                  match.setDistance(-1);

                  search = false;
               }
               else
               {
                  distance = edge.getDestination().getKey().compareTo(key);

                  if (distance >= 0)
                  {
                     match.setEdge(edge);
                     match.setBitmask(currentPath.getBitmask());
                     match.isLegal(edge.canCross(currentPath.getBitmask()));
                     match.setDistance(distance);

                     search = false;
                  }
               }
            }
         }

         return !search;
      }

      private void expandFrontier()
      {
         Collection<Path<K, V>> nextFrontier = new LinkedList<>();
         Path<K, V> nextPath;

         for (Path<K, V> path : frontier)
         {
            for (Edge<K, V> edge : path.getFrontier())
            {
               if (edge.isImplicit() && (edge.getEdgeTypeMask() & this.edgeTypeMask) == edge.getEdgeTypeMask())
               {
                  nextPath = new Path<>();

                  nextPath.setFrontier(new LinkedList<>());
                  nextPath.setBitmask(edge.cross(path.getBitmask()));

                  // nextPath.getBitmask is the calculated bitmask as a result of crossing the edge
                  edge.getDestination().getEdges(key, nextPath.getFrontier());
                  edge.getDestination().getEdges(edge.getOrigin(), nextPath.getBitmask(), nextPath.getFrontier());

                  if (!nextPath.getFrontier().isEmpty())
                  {
                     nextFrontier.add(nextPath);
                  }
               }
            }
         }

         frontier = nextFrontier;
         frontierPathIterator = frontier.iterator();
      }

      private void nextPath()
      {
         if (!frontierPathIterator.hasNext())
         {
            expandFrontier();

            if (frontierPathIterator.hasNext())
            {
               currentPath = frontierPathIterator.next();
               frontierEdgeIterator = currentPath.getFrontier().iterator();
            }
            else
            {
               currentPath = null;
            }
         }
         else
         {
            currentPath = frontierPathIterator.next();
            frontierEdgeIterator = currentPath.getFrontier().iterator();
         }
      }

      public Match<K, V> next()
      {
         boolean foundMatch = false;

         while (hasNext() && !(foundMatch = nextEdge()))
         {
            nextPath();
         }

         return foundMatch? match.clone() : null;
      }

      public boolean hasNext()
      {
         return !frontier.isEmpty();
      }
   }
}

package com.nes.sym.graph;

import java.util.*;

public class Vertex<K extends Comparable,  V>
{
   private Collection<Edge<K, V>> edgeCollection;
   private Map<K, Collection<Edge<K, V>>> edgeMap;

   private final Collection<Edge<K, V>> empty = new Vector<Edge<K, V>>(0);

   private final K key;
   private final V value;

   public Vertex(K key, V value)
   {
      edgeCollection = new LinkedList<Edge<K, V>>();
      edgeMap = new HashMap<K, Collection<Edge<K, V>>>();

      this.key = key;
      this.value = value;
   }

   public K getKey()
   {
      return key;
   }
   public V getValue() { return value; }

   public void getEdges(Vertex<K, V> origin, int bitmask, Collection<Edge<K, V>> edges)
   {
      for (Edge<K, V> edge : edgeCollection)
      {
         if (edge.canCross(bitmask) && !origin.equals(edge.getDestination()))
         {
            edges.add(edge);
         }
      }
   }

   public void getEdges(K key, Collection<Edge<K, V>> edges)
   {
      if (key != null)
      {
         edges.addAll(edgeMap.getOrDefault(key, empty));
      }
   }

   public void addExplicitEdge(int edgeTypeMask, int requiredBitMask, int assignedBitMask, Vertex<K, V> vertex)
   {
      if (vertex.key != null)
      {
         Collection<Edge<K, V>> edges = edgeMap.getOrDefault(vertex.key, null);

         if (edges == null)
         {
            edges = new LinkedList<>();
            edgeMap.put(vertex.key, edges);
         }

         edges.add(new Edge<K, V>(edgeTypeMask, false, requiredBitMask, assignedBitMask, this, vertex));
      }
   }

   public void addImplicitEdge(int edgeTypeMask, int requiredBitMask, int assignedBitMask, Vertex<K, V> vertex)
   {
      edgeCollection.add(new Edge<K, V>(edgeTypeMask, true, requiredBitMask, assignedBitMask, this, vertex));
   }
}

package com.nes.sym.graph;

/**
* Created by nessy on 5/29/2017.
*/
public class Edge<K extends Comparable, V>
{
   private final int requiredBitMask;
   private final int assignedBitMask;
   private final boolean implicit;
   private final Vertex<K, V> origin;
   private final Vertex<K, V> destination;
   private final int edgeTypeMask;

   public Edge(int edgeTypeMask, boolean implicit, int requiredBitmask, int assignedBitMask, Vertex<K, V> origin, Vertex<K, V> destination)
   {
      this.requiredBitMask = requiredBitmask;
      this.assignedBitMask = assignedBitMask;

      this.implicit = implicit;

      this.origin = origin;
      this.destination = destination;
      this.edgeTypeMask = edgeTypeMask;
   }

   public boolean canCross(int bitmask)
   {
      return (bitmask & requiredBitMask) == requiredBitMask;
   }

   public int cross(int bitmask)
   {
      return bitmask & assignedBitMask;
   }

   public int getEdgeTypeMask()
   {
      return edgeTypeMask;
   }

   public Vertex<K, V> getOrigin()
   {
      return origin;
   }

   public Vertex<K, V> getDestination()
   {
      return destination;
   }

   public boolean isImplicit()
   {
      return implicit;
   }
}