Graphs and HypergraphsGraph definitionsAPIs for ADTsMy graph APIGraph methodsNode methodsEdge methodsWhere is...?Why do I have...?HypergraphsPlexPlex data and constructorsPlex methodsImplementing hypergraphs with plexesImplementing graphs with plexesThe Graph classThe Node classThe Edge classA slightly amusing helper methodDeep ThoughtsThe EndJan 13, 2019Graphs and HypergraphsGraph definitionsA directed graph consists of zero or more nodes and zero or more edgesAn edge connects an origin node to a destination nodeThe origin and destination nodes need not be distinct, but they must be on the same graphAn undirected graph can be represented as a directed graph in which all edges come in pairsAPIs for ADTsRequirements of an API:The co nstructors and transforme rs must together be able to create all legal values of the ADTOr, at least, any needed by the applications that use itFor a general use ADT, this means all legal valuesThe ac c e ssors must be able to extract any dataOr, at least, any needed by the applications that use itDesirable properties of an API:The API should be simpleConvenience methods should be provided if:They are likely to be used oftenThe user would expect them to be present (e.g. toString())They simplify the use of the API more than they add complexity to itThey provide serious gains in efficiencyMy graph APIIn my design:There are three classes: Graph, Node, and EdgeThe Graph class has a print() methodMy goals for my design were completeness and simplicity (in that order)I am not claiming that my design is the best possible, but I think it’s very goodGraph methodsConstructorpublic Graph(Object value)Mutative transformerspublic void add(Node n)public void delete(Node node)public void delete(Edge edge)Accessorspublic Set<Node> nodes()@Override public String toString()public void print()public void dump() // debugging aidNode methodsConstructorpublic Node(Object value, Graph g)Mutative transformerpublic void delete()Accessorspublic Graph getGraph()public Set<Edge> getOutpointingEdges()public Set getInpointingEdges()@Override public String toString()Edge methodsConstructorpublic Edge(Node fromNode, Object value, Node toNode, Graph g) Mutative transformerpublic void delete()Accessorspublic Graph getGraph()public Node getOrigin()public Node getDestination()@Override public String toString()Where is...?Where’s the data? (Node names, edge labels, etc.)My classes all extend Plex, which has public Object valueI didn’t see a need for getValue and setValue methods (why not?)Where are the equals(Object obj) methods?I claim node equality means: Same node, same graph. In other words, ==Similarly for edgesEquality for graphs could mean graph isomorphism: There exist NodeG1NodeG2 and EdgeG1EdgeG2 mappings that make the graphs have identical structureThis is an intractable (exponential) problem, and I don’t deal with itWhere are the hashCode() methods?The inherited hashCode methods are consistent with equals meaning ==Where are the applicative transformers?I couldn’t see any use for themThey’re easy enough for the user to writeWhy do I have...?A deleteEdge(Edge edge) method in Graph, when I already have a delete() method in Edge?It’s just a convenience methodSince I have deleteNode (which is necessary), it’s reasonable for the user to expect a corresponding deleteEdge methodA getInpointingEdges() in Node?Most programs only use outpointing edgesIf the method is needed, it’s easy for me to provide, much much more complex for the userAll those toString() methods?I think toString() is always a good idea—for debugging, if nothing elseHypergraphsA hypergraph is a collection of zero or more graphs, with many fewer restrictions.There is no generally accepted definition of a hypergraph, but here are some of the things that might be allowedNodes may reside simultaneously on many graphs, or on none at allEdges may originate from multiple nodes, or none at allEdges may terminate at (point to) multiple nodes, or none at allThe origin and destination nodes of an edge need not be on the same graphEdges may originate from and/or point to graphs or other edgesGraphs may contain other graphs as nodes. Nodes may contain graphs Even edges may contain graphsObviously, a hypergraph is a much more complex structure than a simple directed graphWith the right approach, hypergraphs are actually much simpler than “ordinary” graphsPlexI don’t know where the notion of a plex came fromYou won’t find this term in the literatureA plex consists of four sets:containers: The other plexes in which this plex occursFor example, nodes and arcs may occur in a graph contents: The other plexes contained in this plexFor example, a graph may contain nodes and arcsorigins: The other plexes “from which” this plex comesFor example, an edge comes from a nodedestinations: The other plexes “to which” this plex goesFor example, an edge goes to a nodeThere are two simple validity rules:If plex X is a container of plex Y, then plex Y is a content of plex X, and vice versaIf plex X is a destination of plex Y, then plex Y is an origin of plex X, and vice versaThis redundancy is for reasons of efficiencyPlex data and constructorspublic class Plex { Set<Plex> containers = new HashSet<Plex>(); Set<Plex> contents = new HashSet<Plex>(); Set<Plex> origins = new HashSet<Plex>(); Set<Plex> destinations = new HashSet<Plex>(); public Object value; protected Plex() { } protected Plex(Object value) { this.value = value; }Plex methodsSimilarly for addContent, removeContent, addOrigin, removeOrigin, addDestination, and removeDestination void addContainer(Plex that) { this.containers.add(that); that.contents.add(this); } void removeContainer(Plex that) { this.containers.remove(that); that.contents.remove(this); }Implementing hypergraphs with plexesA plex can represent a graphIts contents can hold the nodes on this graphA plex can represent a nodeIts containers can hold the graph(s) on which it occursIts origins can hold its outpointing edgesIts destinations can hold its inpointing edgesA plex can represent an edgeIts containers can hold the graph(s) on which it
View Full Document