Graph Operations - University of Pennsylvania

Graph Operations - University of Pennsylvania

Graphs and Hypergraphs Jan 30, 2020 Graph 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 pairs APIs for ADTs

Requirements of an API: The constructors and transformers must together be able to create all legal values of the ADT The accessors must be able to extract any data Or, at least, any needed by the applications that use it For a general use ADT, this means all legal values 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 efficiency My 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 its very good Graph methods Constructor Mutative transformers public Graph(Object value) public void delete(Node node) public void delete(Edge edge) Accessors

public Set nodes() @Override public String toString() public void print() public void dump() // debugging aid Node methods Constructor Mutative transformer public Node(Object value, Graph g) public void delete()

Accessors public Graph getGraph() public Set getOutpointingEdges() public Set getInpointingEdges() @Override public String toString() Edge methods Constructor Mutative transformer public Edge(Node fromNode, Object value,

Node toNode) public void delete() Accessors public Graph getGraph() public Node getOrigin() public Node getDestination() @Override public String toString() Where is...? Wheres the data? (Node names, edge labels, etc.) My classes all extend Plex, which contains Object value Plex has getValue and setValue methods

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 NodeG1NodeG2 and EdgeG1EdgeG2 mappings that make the graphs have identical structure Where are the hashCode() methods? This is an intractable (exponential) problem, and I dont deal with it The inherited hashCode methods are consistent with equals meaning == Where are the applicative transformers?

I couldnt see any use for them Theyre easy enough for the user to write Why do I have...? A deleteEdge(Edge edge) method in Graph, when I already have a delete() method in Edge? A getInpointingEdges() in Node? Its just a convenience method Since I have deleteNode (which is necessary), its reasonable for the user to expect a corresponding deleteEdge method Most programs only use outpointing edges

If the method is needed, its easy for me to provide, much much more complex for the user All those toString() methods? I think toString() is always a good ideafor debugging, if nothing else Hypergraphs 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 graphs Plex I dont know where the notion of a plex came from You wont find this term in the literature

A plex consists of four sets: containers: The other plexes in which this plex occurs contents: The other plexes contained in this plex For example, an edge comes from a node destinations: The other plexes to which this plex goes For example, a graph may contain nodes and arcs origins: The other plexes from which this plex comes

For example, nodes and arcs may occur in a graph 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 efficiency Validity Rules Plex1 contains Plex2 <=> Plex2 is contained in Plex1 Plex4 is an origin of Plex3 <=> Plex3 is a destination of Plex4 Plex data and constructors public class Plex {

Set containers = new HashSet(); Set contents = new HashSet(); Set origins = new HashSet(); Set destinations = new HashSet(); public Object value; protected Plex() { } protected Plex(Object value) { Plex methods void addContainer(Plex that) { this.containers.add(that); that.contents.add(this); } void removeContainer(Plex that) { this.containers.remove(that); that.contents.remove(this); }

Similarly for addContent, removeContent, addOrigin, removeOrigin, addDestination, and removeDestination Implementing hypergraphs with plexes A plex can represent a graph A plex can represent a node Its containers can hold the graph(s) on which it occurs Its origins can hold its inpointing edges Its destinations can hold its outpointing edges A plex can represent an edge

Its contents can hold the nodes on this graph Its containers can hold the graph(s) on which it occurs Its origins can hold its origin node(s) Its destinations can hold its destination node(s) Aside from what we call things, once we have implemented plexes, we have implemented hypergraphs! Implementing graphs with plexes We can model graphs, nodes, and edges by putting restrictions on their plexes Graph: Node:

The origins, destinations, and containers sets are empty The nodes of the graph are in the contents set The contents set is empty The containers set contains a single element, the graph that the node resides on The origins set contains the edges that point to the node The destinations set contains the edges that come out of the node. Edge: The contents set is empty The containers set contains only the graph that the edge resides on The origins set contains only the one node from which the edge originates The destinations set contains only the one node that the edge points to

A slightly amusing helper method Suppose you have a Set containing at most one element--how do you get that element? class Extractor { protected static Plex getOne(Set set) { for (Plex plex : set) { return plex; } return null; } } Deep Thoughts Probably the earliest flyswatters were nothing more than some sort of striking surface attached to the end of a long stick. -- Jack Handy

If I had a mine shaft, I don't think I would just abandon it. There's got to be a better way. -- Jack Handy The data structure you choose can make a huge difference in the complexity of your program. -- me The End

Recently Viewed Presentations

  • Get Ready, Get Set, Go 1/5/2015 Rebecca Brown

    Get Ready, Get Set, Go 1/5/2015 Rebecca Brown

    2 So the king asked me, "Why are you looking so sad? You don't look sick to me. You must be deeply troubled." Then I was terrified, 3 but I replied, "Long live the king! How can I not be...
  • The company secretary  the power behind the board!

    The company secretary the power behind the board!

    Being a company secretary. the Companies Act 2006 requires all public companies to appoint a company secretary. private companies are not required by law to hire a company secretary, but most large firms and many mid-sized firms and not-for-profit organisations...
  • Technology in Aircraft Maintenance

    Technology in Aircraft Maintenance

    [Note.C Procedures and facilities requirements for simultaneous operations on parallel or near-parallel instrument runways are contained in the ICAO PANS-RAC (Doc 4444), Part IV and the PANS-OPS (Doc 8168), Volume I, Part VII and Volume II, Parts II and III...
  • Diapositive 1

    Diapositive 1

    À la suite du décès accidentel du Dr. Camille Marcoux, reconnu pour son dévouement à la Basse-Côte-Nord et sa contribution au développement de la région, ses parents et amis ont mis sur pied une fondation en son honneur en 1973...
  • Celebrating the Sacrament of Reconciliation - Sdc

    Celebrating the Sacrament of Reconciliation - Sdc

    FORGIVEN The Priest's absolution Forgiving sins in the name of God I forgive your sins in the name of the Father, and of the Son and of the Holy Spirit. † The word of God was made flesh Resources for...
  • Leinster Rugby Academy Player development / Academic development

    Leinster Rugby Academy Player development / Academic development

    Lifestyle. The glue that holds the above pillars together. Organised. Planned and prepared with respect to , workshops, training, matches, work, study. Time Management. Allocates and managers appropriate time to effectively undertake commitments. Balance.
  • Problem-Based History - Miami-Dade County Public Schools

    Problem-Based History - Miami-Dade County Public Schools

    Problem-Based History. America and Great Britain: Reaching a Point of No-Return?. This power point presentation is for educational purposes. It may contain copyrighted material. Please do not post, redistribute or copy without the permission of the author or Dr. Kevin...
  • Protecting Individual Rights - Princeton University

    Protecting Individual Rights - Princeton University

    Protecting Individual Rights. Altman & Wellman, A Liberal Theory of International Justice Human rights: "individual moral rights to the protections generally needed against the standard and direct threats to leading a minimally decent human life in modern society" (3).