Geek Answers Handbook

Implementing a list of graphs

I look at the implementation of the graph data structure and look at the case list view. This is a brief description here:

List of cases

Thus, each vertex in the graph stores a list of those edges on which it falls.

Given that my graph is a directed graph, I do not really understand this description for a couple of points:

  • Does the graph itself also keep a list of all edges?
  • Do vertices only retain outgoing edges or inbound and outbound?
  • If both of them are in separate lists?

I am well acquainted with other representations of the graph (adjacency list, adjacency matrix, list of edges, incident matrix), so this is not a question about the implementation of the graphs in general, but only this specific one.

Any pointers would be much appreciated.

+3
source share
3 answers

After studying and thinking about this further, I came to the conclusion that the data structure of the incident list graph is missing. I think the Wikipedia article was the result of some confusion in the minds of the author. Thanks to everyone who read this question and spent some time on it.

Armand

0
source

I know that perhaps I posed the old question from the dead, but I found it appropriate to comment.

You can create a chart structure for the incident list, and you can also configure it for digraphs.

Consider a LinkedList<Vertex> object and a LinkedList<Edge> object. This will allow you to iterate over all edges and all vertices, but does not contain information about how everything is connected.

Let's say we add some LinkedList<Connection> objects. In fact, one for each Vertex . A Connection is just where a Edge and a Vertex Meet are. This way, Edge will have two Connection objects (for an undirected graph), and Vertex will have one LinkedList<Connection> object representing the connections to each Edge connected to it. This is essentially a list of cases.

You can change this to represent a digraph if you delete some of these Connection objects. More specifically, you will have to choose where to not have these links. You can remove Connection from the associated LinkedList<Connection> if you do not want to see Edge from Vertex (for the example above, N2 will have an empty LinkedList<Connection> ). Instead, you can make optional links to Edge (In the above example, E1 will have one Connection pointing to N2 and one Connection null, allowing you to bypass from E1 to N2, but not return to N1. Your choice of how to implement this will be entirely yours. One of them is more intuitive - Edges are directed, therefore removal connections on Edges to dictate how they go seems logical. e may seem a little more difficult, but useless to stop you jumping on the edge that never lead to the fact that the first searches for depth and depth.

In the form of a point:

  • In my implementations, I have a list of incidents. Do you need to complete this task?

  • Strictly speaking, you can get by saving only outgoing edges. However, backtracking algorithms can benefit from being able to follow the links they made. You can, of course, realize some kind of story around this, so probably this is not so important.

  • If you do both, you will probably need some way to distinguish between incoming and outgoing. Regardless of whether there are two LinkedList<Connection> objects on top, either using the boolean pointingToVertex primitive boolean pointingToVertex to Connection or whatever. Perhaps your Edge will be directed, and the non-oriented edges will be made of two edges indicating opposite paths. Considerations should be made depending on the needs of your structure.

+2
source

I implemented the incident list as follows and could not find any problem for undirected graphs . I also performed several graph topology algorithms.

 HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

Using a set map guarantees O (1) for finding vertices and amortization of O (1) complexity for inserting and removing edges. Saving a list of edge cuts instead of an adjacent list of vertices is just a way to carry some specific information of the edge itself. This is also useful for abstract algorithms when, for example, you associate weight with edges.

EDIT:

I updated on wikipedia for the topic "incident list".

+2
source

More articles:


All Articles