- Joined
- Jul 10, 2007
- Messages
- 6,306
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
Example
Java:
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());
}
Java:
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();
}
}
}
Java:
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));
}
}
Java:
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;
}
}
Last edited:
