3
$\begingroup$

I'm trying to represent a directed acyclic graph using a structure similar to an adjacency list. The difference is, for a given vertex v, I need to know precisely which nodes are inwardly adjacent to v, and which nodes are outwardly adjacent to v. To get around this, my idea was to use a list of pairs, where each pair consists of two sets - which correspond directly to the inward and outward adjacency sets of any vertex in the graph.

I understand that the maximum number of edges in a directed acyclic graph of size $n$ is $\frac{n(n-1)}{2}$. In the proposed graph encoding, the existence of a vertex u in vertex v's 'in' set implies the existence of an edge (u, v). The existence of a vertex u in vertex v's 'out' set implies the existence of an edge (v, u). Additionally, $u \in in(v) \iff v \in out(u)$. Therefore, my intuition tells me that this representation of a directed acyclic graph has a space complexity of $\mathcal{O}(2|E|)$, since the existence of each edge $(v, u)$ is implied twice; once by $v \in in(u)$ and once by $u \in out(v)$.

My question is, does my intuition fail me?

Improve this question
$\endgroup$
2
  • $\begingroup$ Correct, but you should also store nodes. I would say $O(2|E| + |V|)$. $\endgroup$
    – fade2black
    Commented Jul 20, 2017 at 18:09
  • $\begingroup$ Thanks for your response. This was my initial thought too, however, the representation is being used for a specific task which doesn't actually require me to explicitly reference any vertices. For such a specialised case, would you still say that separate storage of the vertices is required? $\endgroup$
    – swingballchamp42
    Commented Jul 20, 2017 at 18:53

1 Answer 1

Reset to default
2
$\begingroup$

You say "using a structure similar to an adjacency list". So space complexity required for storing undirected graph using adjacency list is $O(|V| + |E|)$, in your case $O(|V| + 2|E|)$. That is implemented using a list of nodes where each node has two fields: label of the vertex and pointer to the list of adjacent nodes (in your case two lists).

But I don't know how you are going to use the graph. If you are interested in simply a set of edges then you could store them in a list as triples $<u,v,weight>$. But if at some point for a node $v$ you want to systematically loop on all adjacent vertices (inward or outward) then you should use adjacency list.

Finally if you want to decide in $O(1)$ if there is an edge $<u,v>$ then you should use hash like data structure to store pairs $<u,v>$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I plan to use a graph represented in this way to model a problem in automatic differentiation. In short, the process of Jacobian accumulation can be modelled on a directed acyclic graph, where vertices are seperated into three distinct groups - input, intermediate and output. All input vertices have indegree of 0, all output have outdegree of 0 and all intermediate have positive indegree and outdegree. We eliminate an intermediate vertex v by joining all nodes $u \in in(v)$ to all nodes $w \in out(v)$. By eliminating all intermediate vertices, we obtain a bi-partite graph. $\endgroup$
    – swingballchamp42
    Commented Jul 20, 2017 at 20:07
  • $\begingroup$ Each elimination is associated with a cost (its indegree * outdegree). The combinatorial optimisation problem requires us to minimise the total cost, which is the sum of all elimination costs required to render the graph bipartite. Therefore, establishing the cost of an elimination in constant time is important, aswell as generating the necessary edges for each elimination. I believe that this data structure supports this operation in $\mathcal{O}(|in(v)| * |out(v)|)$ time $\endgroup$
    – swingballchamp42
    Commented Jul 20, 2017 at 20:11
  • $\begingroup$ Isn't it NP-complete? The whole problem I mean "The combinatorial optimisation problem requires us to minimise the total cost" $\endgroup$
    – fade2black
    Commented Jul 20, 2017 at 20:20
  • $\begingroup$ Yes, it's NP complete. However, what I'm doing is applying the ACO metaheuristic to the problem and comparing it experimentally to some existing sub-optimal methods (simulated annealing, and some greedy heuristic based methods). I just feel the work will be more complete if I can back up my algorithm design choices with a theoretical analysis. Would you agree that the edges created by an elimination can be generated in $\mathcal{O}(|in(v)| * |out(v)|)$ time using this representation? $\endgroup$
    – swingballchamp42
    Commented Jul 20, 2017 at 20:27
  • $\begingroup$ In fact you could explain that part of the task in graph theoretic terms, and post on the forum. I am sure forum members will suggest you possible solution(s). $\endgroup$
    – fade2black
    Commented Jul 20, 2017 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.