DOC PREVIEW
Penn CIT 594 - Graphs and Hypergraphs

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 definitionsA directed graph consists of zero or more nodes and zero or more edgesAn edge connects an origin node to a destination nodeThe origin and destination nodes need not be distinct, but they must be on the same graphAn undirected graph can be represented as a directed graph in which all edges come in pairsAPIs for ADTsRequirements of an API:The co nstructors and transforme rs must together be able to create all legal values of the ADTOr, at least, any needed by the applications that use itFor a general use ADT, this means all legal valuesThe ac c e ssors must be able to extract any dataOr, at least, any needed by the applications that use itDesirable properties of an API:The API should be simpleConvenience methods should be provided if:They are likely to be used oftenThe user would expect them to be present (e.g. toString())They simplify the use of the API more than they add complexity to itThey provide serious gains in efficiencyMy graph APIIn my design:There are three classes: Graph, Node, and EdgeThe Graph class has a print() methodMy 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 methodsConstructorpublic Graph(Object value)Mutative transformerspublic void add(Node n)public void delete(Node node)public void delete(Edge edge)Accessorspublic Set<Node> nodes()@Override public String toString()public void print()public void dump() // debugging aidNode methodsConstructorpublic Node(Object value, Graph g)Mutative transformerpublic void delete()Accessorspublic Graph getGraph()public Set<Edge> getOutpointingEdges()public Set getInpointingEdges()@Override public String toString()Edge methodsConstructorpublic Edge(Node fromNode, Object value, Node toNode, Graph g) Mutative transformerpublic void delete()Accessorspublic 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 valueI 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 edgesEquality for graphs could mean graph isomorphism: There exist NodeG1NodeG2 and EdgeG1EdgeG2 mappings that make the graphs have identical structureThis is an intractable (exponential) problem, and I don’t deal with itWhere 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 themThey’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 methodSince I have deleteNode (which is necessary), it’s reasonable for the user to expect a corresponding deleteEdge methodA getInpointingEdges() in Node?Most programs only use outpointing edgesIf the method is needed, it’s easy for me to provide, much much more complex for the userAll those toString() methods?I think toString() is always a good idea—for debugging, if nothing elseHypergraphsA 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 allowedNodes may reside simultaneously on many graphs, or on none at allEdges may originate from multiple nodes, or none at allEdges may terminate at (point to) multiple nodes, or none at allThe origin and destination nodes of an edge need not be on the same graphEdges may originate from and/or point to graphs or other edgesGraphs may contain other graphs as nodes. Nodes may contain graphs Even edges may contain graphsObviously, a hypergraph is a much more complex structure than a simple directed graphWith the right approach, hypergraphs are actually much simpler than “ordinary” graphsPlexI don’t know where the notion of a plex came fromYou won’t find this term in the literatureA plex consists of four sets:containers: The other plexes in which this plex occursFor example, nodes and arcs may occur in a graph contents: The other plexes contained in this plexFor example, a graph may contain nodes and arcsorigins: The other plexes “from which” this plex comesFor example, an edge comes from a nodedestinations: The other plexes “to which” this plex goesFor example, an edge goes to a nodeThere 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 versaIf plex X is a destination of plex Y, then plex Y is an origin of plex X, and vice versaThis 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 methodsSimilarly 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 plexesA plex can represent a graphIts contents can hold the nodes on this graphA plex can represent a nodeIts containers can hold the graph(s) on which it occursIts origins can hold its outpointing edgesIts destinations can hold its inpointing edgesA plex can represent an edgeIts containers can hold the graph(s) on which it


View Full Document

Penn CIT 594 - Graphs and Hypergraphs

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Graphs and Hypergraphs
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Graphs and Hypergraphs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Graphs and Hypergraphs 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?